Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Some Programs Are Poorly Designed On Purpose

December 07, 2011

The title of this post is something that Robert Dewar told me in a phone conversation more than 30 years ago that we had about teaching programming.

We were talking about students' tendency to let the compiler substitute for thinking, along the lines of Jerry Schwarz' remark about rapid prototyping that I mentioned last week . I'm sure you've seen this phenomenon yourself, if not in yourself: A program doesn't compile, so its author looks at the part of the source code that the compiler identified as containing the first error, changes something that looks like it might fix the problem, and then compiles it again.

Professor Dewar argued that an important part of teaching students how to program was to get them into the habit of thinking about what they were doing before they did it, rather than letting the compiler think for them. He suggested, as one way of doing so, that students should use compilers that do not explain where the errors in the program are. Instead, the compiler should say something like This program contains one or more errors, and leave it to the student to find them.

I was both amazed and skeptical about the amount of discipline that this teaching approach would require — particularly because I had previously known Professor Dewar as the author of a major piece of software that used more dirty tricks than I had ever encountered before. When I asked him how he could reconcile his attitude with the software he had produced, he replied that some programs are poorly designed on purpose.

The software in question was a compiler for a dialect of SNOBOL4 named SPITBOL (SPeedy ImplemenTation of snoBOL4). It is still in use, and is now available under GPL should you wish to look at it. Written in IBM System/360 assembly language, SPITBOL was carefully and thoroughly documented — but that documentation revealed programming techniques that to this day make me cringe when I think about them.

One such technique was the way in which the compiler used floating-point arithmetic. System/360 had four 64-bit floating-point registers that were completely separate from the normal fixed-point registers. Because SNOBOL4 is not a floating-point-intensive language, the SPITBOL compiler used only one of those four registers for all floating-point computations in the program. It used the other three registers for more nefarious purposes.

We are normally taught to think of floating-point arithmetic as an abstraction of (and an approximation to) arithmetic on real numbers. Part of that abstraction is that we usually think of floating-point computation as being a little fuzzy — we do not expect to be able to count on the precise result of a floating-point computation. Despite this expectation, the behavior of System/360 floating-point arithmetic is precisely specified, and the SPITBOL compiler took advantage of this specification.

For example, part of the SNOBOL4 language was a runtime limit on the number of statements that the program would execute before terminating. The programmer could set that limit, and could even change it during execution. Such limits were useful in the world of batch processing, where programs would run to completion without human intervention, and where users were often charged for the amount of (then very expensive) computer time their programs would consume.

The SPITBOL compiler devoted two of the machine's four floating-point registers to keeping track of the statement limit. One of these registers would contain a large floating-point value; the other would contain an even larger one. At the beginning of every statement, the compiler would place an instruction that would add the two registers, storing the result in the second. Eventually, the sum would be so large that the computation would overflow, and the overflow interrupt would end the program's execution. The second register would start out with a value that was precomputed to overflow after exactly the right number of additions.

Why use floating-point computation — and especially floating-point interrupts — to count the number of statements? Four reasons:

  1. Fixed- and floating-point overflow were different conditions. By using floating-point arithmetic, the compiler assured that the statement limit would be checked even if fixed-point overflow checking was suppressed.
  2. Even though floating-point registers were scarce, they were used so much less often than fixed-point registers that it was worth devoting two of them to this purpose.
  3. Many models of the System/360 line had separate fixed- and floating-point processors. By doing this particular computation in the floating-point registers, SPITBOL made it possible to overlap it with other processing.
  4. Some error conditions in SNOBOL cause control to pass to the beginning of the next statement. The runtime library could find the beginning of that next statement by examining the machine code, one instruction at a time, until it found the appropriate floating-point addition instruction.

This last technique is so sneaky that it's worth explaining again: Rather than storing the location of the beginning of each statement in some kind of table, the SPITBOL compiler arranged that each statement would begin with a particular kind of floating-point add instruction. Accordingly, given the address of any code in the program, the runtime library could always find the beginning of the next statement by examining each machine instruction in turn until it found the appropriate floating-point add instruction.

With just one programming technique, the SPITBOL compiler violated several principles of good programming:

  • It used floating-point arithmetic for counting.
  • It used error conditions (i.e., floating-point overflow) to control the program's normal execution.
  • It devoted a large fraction of a scarce resource to a seemingly trivial purpose.
  • It relied on the particular format of machine instructions in order to be able to find where the code for each statement began.

Nevertheless, in this particular context, violating these principles was the right thing to do. One of SPITBOL's selling points was, indeed, its speed. Compared to the original implementation of SNOBOL4, it compiled programs about twice as fast and executed them about 10 times as fast. Part of this speed came from tricks such as this one.

Next week I'll explain how SPITBOL used that third floating-point register.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video