My first PL/I program

My first PL/I program [1] was a few dozen lines transliterated from Algol. I compiled it using IBM's PL/I F compiler for the IBM System/360.

The PL/I F compiler was a wondrous beast. To borrow Brian Randell's phrase, it was "a triumph of engineering over design." PL/I was one of the largest and most complex programming languages of its time--perhaps of all time--intended to replace FORTRAN, COBOL, Algol, and most other programming languages in use at the time. But IBM's F level compilers had to run on relatively small machines. [2] To resolve this dilemma, the compiler was divided into a large number of "phases." [3]

My program compiled on the first try, went into execution, and then crashed with a divide by zero, producing perhaps 100 pages of error messages and core dump. The odd thing was that I wasn't aware of any divisions in my program.

It took some detective work to figure out what had happened. To explain my difficulties, I should mention some more characteristics of the compiler:

• It always converted its input into legal PL/I; whenever it encountered an error, it modified the program to a form it could deal with; and it always executed the compiled result, no matter how many errors had been encountered. [4][5]
• Each phase's error messages were in terms of the program as modified to that point. [6]
• Error messages were printed out sorted by severity; within a severity level, by phase; within a phase, by position in the program. So messages relating to a single statement could be widely scattered.

I eventually discovered that the offending statement was something like

PUT LIST("PL/I VERSION OF MSP ANALYZER");

This was my first time using the 029 keypunch; unlike the 026, it had both single and double quotation mark characters. Being an American, I naturally used double quotes, but PL/I used single quotes as string delimiters. I should have punched

PUT LIST('PL/I VERSION OF MSP ANALYZER');

An early phase of the compiler determined the type of a statement. Since my statement was not a valid PUT statement, it was classified by default as an assignment statement.

A later phase of the compiler noticed that the assignment statement was missing an equal sign, so it inserted one:

PUT = LIST("PL/I VERSION OF MSP ANALYZER");

Because PL/I had no reserved words, this implicitly declared the variable PUT and the array variable LIST. Another phase had trouble processing the double quotes, so it deleted them:

PUT = LIST(PL/I VERSION OF MSP ANALYZER);

PL and I also became implicitly declared variables, but there were no further operators in the "expression," so the rest of it was deleted:

PUT = LIST(PL/I);

This was the statement that was finally compiled.

Of course, the variable I had not been initialized, and it happened to be zero when the program encountered this statement, so the program crashed with a divide by zero error. What could be more informative?

Notes:
[1] Circa spring 1967.
[2] More specifically, on machines with 44 KB of core storage (exclusive of storage requirements for the Operating System), without benefit of virtual memory. The FORTRAN level H compiler got more space: "A source program of about 600 cards can be compiled in 200 KB of main storage." [FORTRAN INFORMATION BULLETIN NO. 1, February 1968]
[3] I counted in the Program Logic Manual. The compiler had 112 distinct named phases. All but a dozen or so would be invoked in compiling any non-trivial program. The FORTRAN H level compiler had 5 phases, named 10, 15, 20, 25, and 30, divided into 13 overlay segments.
[4] At the Stanford help desk I once saw the output that resulted when a user who was confused about JCL compiled and executed his FORTRAN program using the PL/I F compiler. That, too, went into execution and then crashed.
[5] A misguided policy that has been adopted by too many of its successors.
[6] To compound the difficulty, I don't believe it said what changes it made, you had to infer them.

PIXIE: A small debugger

Bendix G-15 programmers were often obsessed with space: squeezing a little more functionality into a fixed amount of memory [example], or trimming the amount of memory required for fixed functionality[example]. (I suppose that programmers today who have only 8 KB to work with--for watches, pocket calculators, washing machines, etc.--are similarly obsessed.) This obsession was particularly manifest when debugging. Unlike today's programmers, we did not have tools like cross-compilers and emulators that ran on bigger, faster machines. Our emulators had to run on the G-15 itself.



The G-15 hardware provided some features that assisted in debugging, notably 27 front-panel indicator lights that displayed most of the non-recirculating state accessible to the programmer, such as the current command line and the source and destination of the next instruction to be executed. However, much of the state critical to debugging (including the contents of memory and the time and next fields of the next instruction) was recirculating, and not easily accessed this way.



The G-15 also had some useful keyboard commands. When the typewriter's ENABLE switch was ON, many of the typewriter keys had special control functions, such as Execute One Command (single step) or Type AR.

Bendix also provided a Program Preparation Routine to facilitate converting programs to binary, rearranging them from programming sheet order to drum location (word time) order, program (paper) tape preparation, duplication, and listing, and program inspection and correction during checkout. However, PPR required quite a lot of memory: lines 05, 16-19, and 23 plus all four of the arithmetic registers (lines 24-26 and 28), also line 15 if decimal number conversion was needed. This was pretty heavyweight for program inspection and correction on a small machine. Furthermore, lines 19 and 23 were involved in most I/O, and the registers were naturally central to the execution of most programs. Translation: PPR stomped on any program you wanted to debug.

At the Pacific Union College Data Processing Lab (DPL), we often used a lighter-weight one-line debugger, which was ultimately named PIXIE (more on that later). I'm afraid that I don't remember its provenance, whether it originated at the DPL or elsewhere. I do remember that it evolved considerably, at a number of hands, while I was there. Using today's terminology, PIXIE provided a virtual machine that was just like a G-15, except that

• it was missing one memory line (generally 04 or 05, henceforth the PL), which was used by the emulator, and
  
• it provided a number of additional keyboard commands not supplied by the real hardware.

The emulated machine had 95% of the memory of the real machine, 7 out of 8 command lines, including lines 19 and 23, and all four registers. PL contained 108 29-bit words (3132 bits, or 391.5 bytes), which provided the entire memory, program and data, for the PIXIE emulator.

Strong Emulation Invariant: At each critical time, the entire state of memory, including the four registers, but excluding PL, must have exactly the content it would in the G-15 being emulated. [1]

Critical times were, among others, when a memory location was being inspected, or when control was being transferred back to the program being debugged.

For each register or other piece of memory temporarily used by PIXIE, this invariant imposed a three-fold cost: a command to save its value before the use, memory to store the value, and another command to restore it after the use. Since the emulator simply could not provide its basic functionality without using line 28 (AR) for arithmetic and output, line 23 (4 words) for input, and at least one word of line 03 for the output format, saving and restoring them was essential. [2]

New Keyboard Commands: PIXIE provided a very simple interface, with different commands being primarily distinguished by length. [3] If the user typed

• four digits: the current location was set to the line given by the first two digits and the word given by the last two; then the contents of the current location were printed.
• just a minus sign: a breakpoint was set in the current location.
• just a space: the breakpoint in the current location (if any) was removed.
• three digits: control was transferred to the command line given by the first at the word given by the last two.
• seven digits: the hexadecimal value was stored in the current location.
• nine digits: the hexadecimal instruction given by seven digits was executed at the time given by the other two.

To implement the last two commands, it was necessary to store the value or execute the specified instruction from AR (to enable it to execute at the proper word time), so it was necessary to weaken the invariant.

Weak Emulation Invariant: Same as the strong invariant, but excluding AR. Applied only to executing those two commands, but user beware of using the emulated AR.

Reflection: The G-15 had no memory protection, so PIXIE could inspect itself (that is, the contents of PL). For that matter, it could modify itself, but user strongly beware.

Loading was from paper tape. The G-15 I/O system used line 19 for all paper tape input and output, so its initial value was lost when PIXIE was loaded. [4] (To debug I/O, PIXIE had to be loaded in advance.) PIXIE was responsible for initially copying itself from line 19 to PL. But it didn't have space to determine the relocation dynamically. Line 04 PIXIE and line 05 PIXIE were stored on different tapes, and hand-selected by the user.

Features were added from time to time. One that I remember was the equivalent of today's DEL or BS key, to take back a mistaken input (this was not available as a hardware command).

Space to implement new features was gotten by a wide variety of down-and-dirty tricks. I remember being very proud of myself for arranging to make productive use of the same 29-bit value in three distinct ways: as an executable instruction, as the increment for a loop counter, and as an output format.

Oh, yes, the name: One of the last things that I added was the instructions that caused the debugger to print its name upon being loaded. This required choosing a name--previously we just called it "the one-line debugger," but that was way too long to print. In fact, the space that I found for this purpose (which, once the program was in its main loop, was used for temporary storage) was only adequate to type a single machine word. 29 bits. Not quite four characters. So the name had to start with P, because that was already printed by the ENABLE-P command that booted the program. Then it could have three arbitrary characters, and a final character that could be E, M, or U, because the hardware would supply zero for three last three bits. P???E, P???M, or P???U. It could have been PAUSE, PRATE, PRUNE, PSALM, or PILAU. But PIXIE had the connotations of being small (remember, 391.5 bytes) and clever, so that's what I chose.

Notes:
[1] We wouldn't have said it that way; in fact, we didn't have a good way to say it. "Invariant" was not yet in our vocabularies.
[2] Using any other registers and memory locations involved a cost/benefit tradeoff, rather than being essential.
[3] The command set grew over time, and I may not have remembered them all.
[4] However, by a clever trick, the initial value of line 23 was preserved, even though it was also used for paper tape input.

University of Toronto Horoscopes

I first heard this story from Kelly Gotlieb more than 30 years ago, [1] but I have retold it so often that it has come to seem like one of my own.

The president of the University of Toronto received a letter from an alumna complaining that she had noticed a display of "University of Toronto Horoscopes" at Eaton's Department Store. She enclosed as evidence a sample that she had purchased. It was a computer printout, cleverly folded so that the University of Toronto crest in the lower right corner was prominently displayed.

The president was unaware of any work on astrology being conducted at the university, let alone any enterprise of selling horoscopes to the public. But the sample seemed to establish a direct link with a U of T computer. He asked the director of the Computation Centre to investigate.

Talking to the operators, Kelly soon figured out what had happened. The Computation Centre acted as a small service bureau, selling computer time that would otherwise be idle to users outside the university. The company generating the horoscopes had bought some time, and printed the horoscopes on the paper in the line printer, which bore the U of T crest.

Kelly reported back to the president, explaining what had happened. He also said that he'd instituted a new policy to always use plain white paper in the line printer when outside jobs were being run, so they wouldn't appear to be linked to the university, whatever their nature. But he considered the astrology program to be harmless, although frivolous, and planned to continue selling computer time to that company.

The president informed the alumna of the investigation and policy change, but she was not mollified in the least. She was one of Toronto's leading astrologers, and her real complaint was not that selling horoscopes would reflect badly on the university, but rather that the horoscopes being sold were inaccurate!

Note:
[1] Kelly undoubtedly has many more tales to tell, but I'll leave that up to him. He and I co-chair the ACM's Awards Committee.

My third computer: The Bendix G-20

In 1962, during my second summer internship at Bendix Computer Division, in addition to my regular assignment [1], I was given the opportunity to spend my spare cycles writing a Bendix G-20 program for something that interested my boss. [2] Since I didn't work with it for long, my memories of the G-20 are less vivid than for some other computers. [3] Mainly what I remember are some of the differences from the Bendix G-15.

The G-15 was a physically small and relatively inexpensive ($50K) first-generation computer, using vacuum tubes for its logic circuitry, and a magnetic drum for its primary memory. At the time, the G-20 could hardly have been more different: It was a physically large and relatively expensive ($500K) second-generation computer, using transistorized logic [4] and magnetic core memory. Its instruction set architecture was closer to Intercom than to the G-15's ISA. It was a classic example of the second system effect.

Memory: It seemed big and fast to me. A minimum of 4K, and a maximum of 32K, 32-bit words (16-128KB), compared with 2K 29-bit words on the G-15. The memory was random access, and any location could be loaded or stored in just 8 microseconds (us). Each memory word also had a single parity bit for error-checking.

Arithmetic: All floating point, with a 42-bit mantissa and an 18-bit (octal) exponent. (There was provision for loading and storing single words in scaled fixed point.) Operations were 42-bit-parallel, rather than bit-serial. Excluding memory access time, addition took 13 us, multiplication took 56 us, and division took 98 us.

Instructions: Straightforward single-address instructions with a single floating-point accumulator. 7-bit operation code, 6-bit index register field, 15-bit base address, 2-bit mode, and 2 flags.

Addressing: Single 15-bit linear address space [5]. There were four addressing modes, which I believe were

• Immediate: The operand was the value of the address field.
• Direct: The operand was the value whose location was given by the address field.
• Indirect: The operand was the value whose location was given by the value whose location was given by the address field.
• Doubly indirect: The operand was the value whose location was given by the value whose location was given by the value whose location was given by the address field.

Indexing: 63 index registers, the most I can recall on any machine I've used. [6] However, index registers were stored in main memory, locations 1-63. This meant that indexing an instruction added 8 us to its execution time. However, there was a convenient instruction to get the value of an index register, increment it, compare it to a limit, and store the new value back--all in one 8 us memory cycle.

Operand assembly: It would have been a waste to use the 42-bit accumulator and its floating point operations to do address calculations--and inefficient to save and restore the accumulator to do so. The G-20 had a separate operand assembly register (OA) for address calculations, something I've not seen in any other machine architecture. Addressing proceeded as above, except that the contents of OA were added to the 15-bit base address from the instruction before any indexing or indirection was done. There was a special class of instructions that did not affect the accumulator, but left their results in OA, instead. Normal instructions cleared OA before the next instruction.

Interrupts: There was a fairly conventional interrupt system, that could be triggered by internal conditions (e.g., memory parity errors) or external conditions (e.g., completion of I/O). There was a mask register that determined which interrupts were enabled. Occurrence of an interrupt caused an instruction (normally a branch) in the interrupt vector to be executed.

Breakpoints: The G-15 reserved one bit in instructions for breakpoints. The G-20 reserved two bits in every word for flags that could be used to generate breakpoints. There were six bits in the mask register, that determined whether the presence of bit 31 or bit 30 would trigger an interrupt when the location was accessed to execute an instruction, to load a value, or to store a value.

Staff: For 24-hour operation, Bendix recommended a staff of 35: 3 supervisors, 5 analysts, 10 programmers, 12 coders, 1 clerk, 3 operators, and an input-output operator.

Software: There was a symbolic assembler, SNAP, the first I had ever used. RAM meant that the programmer no longer had to specify carefully where each instruction and variable was stored. An operating system and an Algol compiler were being prepared, but not ready for use that summer.

Some experienced Bendix programmers grumbled that the G-20 was "no fun" to program, because the hardware had taken over all the interesting work, like indexing and floating point. This was a fairly natural reaction to a machine making hard-earned skills obsolete.

The Bendix G-20 is probably best-known today as Carnegie's first mainframe computer, which became the core of their G-21 system.

[Other Sources]
Notes:
[1] Writing the Bendix G-15 CPM/PERT program.
[2] The Quine-McCluskey algorithm for simplifying Boolean functions; the program handled functions of up to 15 variables, storing intermediate results on magnetic tape.
[3] I would love to be able to download files from the Charles Babbage Institute.
[4] About 5K transistors.
[5] Virtual memory was still in the future in 1962, at least for American computers.
[6] As happens so often with an "infinite" resource, I managed to specify more than 63 index registers in my first program.

Memorable Messages

A couple of error messages from 40 years ago have stuck firmly in my memory. The first is one that I actually received from the IBM PL/I F compiler:

ERROR, THE PRECEDING ERROR MESSAGE CONTAINS AN ERROR. PLEASE SUBMIT AN APAR TO YOUR IBM REPRESENTATIVE.

The message was absolutely correct: There was an error in the previous message. (An APAR was an Authorized Program Analysis Report.)

The second is one that wasn't triggered by any of my programs. I noticed it in the list of error messages while looking up another runtime error message from the IBM FORTRAN H compiler:

ERROR, BRANCH TO CODE ELIMINATED BY OPTIMIZER.

Now it could be that these messages were so memorable because I was young and impressionable, but I like to think that it is because of the level of foresight required to recognize that these were problems that could occur in a large, complex compiler, and that they would be easier to track down if they were explicitly reported.

-23:59:59

The largest bill for computer time that I ever received was for a negative amount.

In 1967, the Stanford Computer Center installed an IBM System 360/67 mainframe. Because government contracts required that services charged to sponsored research projects be at the lowest rate charged to anybody, student research assistants had accounts billed at the same rate (although the department or the center paid the bill).

I seem to have been the first user to have a job running at the stroke of midnight. When I got my statement that month, I had a rather large balance in my favor. It turned out that the accounting routine used the time-of-day clock, and subtracted the time when the job started from the time when it ended. The resulting credit ran to five figures.

I thought that this was hilarious, but Jane was spooked by it: Never mind that little minus sign, she just didn't feel comfortable with a bill for an amount larger than our combined annual incomes.

This is one piece of paper I really wish I had saved. It would now be framed and hanging on my wall.