Friday, October 13, 2006

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.

G-15 Front Panel

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.

G-15 Typewriter

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.

[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.