Recovering the 220 BALGOL Compiler

The retro-220 emulator for the Burroughs 220 computer system has been stable for almost two years. The recovered Burroughs Algebraic Compiler, better known as BALGOL, has been stable for nearly as long. Previous posts for this blog ([1], [2]) have discussed the architecture of the 220 and the retro-220 emulator. Other posts ([3], [4]) have discussed the syntax and features of BALGOL, as well as the preliminary version of the Algol programming language, Algol-58, upon which BALGOL was based.

The story that has not yet been told is how I recovered the BALGOL compiler and made it run again.

Compiler Assets and Components

The BALGOL compiler was first released by Burroughs in March 1960, then received a significant update in February 1962. The compiler was distributed to customers as a magnetic tape, termed the "Generator Tape," along with a few small card decks used for bootstrapping and utility functions.

The 220, first shipped in 1958, was one of the last of the major vacuum tube systems, and quickly became obsolete. Considering that the 220 had a highly unusual magnetic tape subsystem, the possibility that any software in machine-readable form may have survived to the present is remote.

There was another form of release for the compiler, however. For some reason, Burroughs generated complete assembly listings of the 1962 compiler, its standard library routines, and a configuration utility, then made sets of copies in 8.5x11-inch format. They must have made a lot of copies, apparently to be given away. Michael Mahon has told me that there was still a stack of these copies in a closet at the Pasadena plant when Burroughs decommissioned their internal 220 systems around 1968. He says he grabbed one of the copies and still has it.

Another person who had a copy and retained it was Donald Knuth. In 2005, Professor Knuth loaned a large number of documents from his files to the Computer History Museum in Mountain View, California. These documents were scanned by the museum, which then made the resulting PDFs publicly available on its web site [5]. Among those documents is Knuth's copy of the BALGOL compiler listings [6]. That PDF is about 17MB in size and comprises 267 pages.

It was the CHM scan of Professor Knuth's copy of the BALGOL listing that I used to recover the compiler source code and restore the compiler to operation.

The compiler source consists of four main parts:

1. Compiler main module, 4760 lines, 4663 cards.
   This is the one-pass BALGOL translator, which parses the language text and generates machine instructions for the 220.
2. Compiler overlay module, 2431 lines, 2388 cards.
   This is the second part of the compiler, which merged into the object program any required machine-language routines from the standard library, any optional user-supplied machine language routines on punched cards, and the code for any debugging aids specified in the BALGOL source (tracing, monitoring, symbolic dump). It produced a loadable program on magnetic tape.
3. Standard library routines, 1466 lines, 1381 cards.
   The standard BALGOL library of 28 subroutines, including math routines, integer/floating conversion routines, formatted I/O (input/output) routines, and debugging support. The standard routines are described in Appendix G of the compiler reference manual cited below.
   
4. Generator program, 2215 lines, 1954 cards.
   This was a "sysgen" program that, using the Generator Tape, created customized tapes from which the compiler could be run. It could prepare the compiler for a given computer configuration, update the standard library with new or modified routines, replace the default punched-card I/O interfaces for the compiler and library, and modify some aspects of the way the compiler operated.
   

The number of "lines" cited above reflects the number of printed lines on the scanned listings. Due to assembler-generated printing (extra spacing, multiple words generated by pseudo operators, etc.), the listings have more lines than would have been input as source code to the assembler. The number of "cards" reflects the number of lines of assembly source code that were extracted from the transcribed listings.

In addition to these listings, there are Burroughs 220 documents on the bitsavers.org web site [7]. The most important of these is the compiler reference manual from March 1963, 220-21017_B220_BALGOL_Mar63.pdf, prepared for the 1962 version of the compiler represented in Professor Knuth's listing. In addition to these documents, the bitsavers.org site has an older version of the reference manual and an incomplete listing of the compiler and library from 1961.

Thus, when starting the compiler recovery project, we had what appeared to be listings of the complete compiler, library, and generator program (this eventually proved to be true), and good documentation for the compiler, library, and generator program. But here's what we did not have:

1. The source code in machine-readable form.
   
2. Assembly software for the source code. The compiler main, overlay, and library were all written for one assembler. The generator program was written for an entirely different assembler.
3. Documentation in any form for either assembler. Not even their names were known.
   
4. Information on how the Generator Tape was formatted.

It therefore appeared that I would need to transcribe all of the text from the scanned listings (totaling almost 11,000 lines of assembly code), reverse-engineer the two assembler notations and write two different assemblers from scratch, assemble the 31 source modules (compiler, overlay, generator, and 28 library routines) into a form that could be used to construct a Generator Tape, somehow deduce what the format of that tape needed to be, combine the assembled modules to construct an initial tape, and from that use the generator to create a loadable compiler tape. Having done all that, I would then be ready to find some BALGOL source code and start debugging the whole mess. At the time, I found this list of tasks to be somewhat daunting.

Recovering the Source Code

I began transcribing the listings in early November 2016, before I started work on the retro-220 emulator at the end of that December. Initial transcription, proofing, and correction of the transcribed text continued through May 2017. I was usually able to transcribe four pages a day, about 180 lines, or proof about double that amount. I found that trying to do more than that at one sitting simply resulted in introducing more errors during transcription or failing to catch them during proofing, so I took my time and tried to work carefully.

The assembly listing for the generator program is in the traditional form, with memory addresses and words of assembled object code on the left, and the text of each line of assembly source on the right. My approach with listings of this type -- probably a common one -- is to transcribe the listing completely, as is, including the addresses, object code words, spacing, and any additional output by the assembler. The purpose of this is to ease the job of proofing the transcription. After extracting card images for the source code from the transcribed text and assembling it, you can capture the assembly listing as a text file and mechanically compare it to the text file from the transcription. Any differences between the two are easily identified. The assembler symbolic instructions and any comments will of course match, but if the assembled addresses and object code words also match, then there is a good probability that the symbolic instructions were transcribed correctly.

Before attempting to assemble the transcribed generator code, I completed a manual proofing pass to catch obvious errors and as many typos in the comments as I could. Next, I extracted a text file of card images from the transcription containing the symbolic instructions and comments in a form that could be input to the assembler discussed below. I wrote scripts to do this. Then I iterated between assembly runs and correction of the transcribed text until the assembler output matched the transcriptions. This is a fairly reliable proofing process, but it is not guaranteed to catch everything.

Proofing the transcription of the remaining modules, which comprise 80% of the lines, was more problematic. These listings appear to be from a first pass of the assembler. They show the memory addresses assigned to each symbolic instruction, but not the words of generated object code. That meant a mechanical match between the transcribed text and assembler output could only detect address assignment errors, not errors in the symbolic instructions. That in turn meant that for these modules I had to do a much more careful job of manual proofing.

In the end, I had to do two complete proofing passes on the compiler, overlay, and library transcriptions -- the second one after I had started to test the compiler with sample programs and was running into serious problems. I also made at least one extra proofing pass on the main tables in the compiler, which are dense and cryptic. The correctness of those tables are absolutely essential to the compiler's operation.

Creating Assemblers from Scratch

Without documentation on either of the assemblers required to reconstruct the compiler, I had to puzzle out for myself both of the symbolic assembly notations and from that design programs to parse each notation and generate the necessary words of object code and data. These programs were not intended to be recreations of the original assemblers, because those assemblers likely had features that were not used in the transcribed source code, and there was no way to know that those features had existed. Instead, these assembly programs were intended to support just whatever was necessary to successfully assemble the transcribed source code, plus whatever additional features I thought (a) might be useful for assembling 220 programs in general, and (b) would not be too difficult to implement.

The BAC-Assembler

The assembler that Burroughs used for the compiler, overlay, and library routines is fairly straightforward, at least as it was used with those modules. It has a classic columnar assembler format, with fields for an optional label, a mnemonic code for the hardware or pseudo instruction, an optional sign digit to be applied to the assembled word, and an operand field consisting of comma-delimited symbolic expressions for addresses and variant fields. The remainder of the source line, delimited by a space after the operands, is ignored and may be used for comments.

The mnemonic codes for the hardware instructions matched those documented in the 220 Operational Characteristics manual (in [7]), except for a few additional ones. These few, however, appeared to be convenience mnemonics for specialized forms of other instructions. For example, from its context, "BZA <address>" appeared to stand for a "branch if the A register is zero" instruction. There is no such instruction for the 220, but there is a "BFA <address>,<sL field>,<digits>" instruction (branch if the <sL field> of the A register matches <digits>). If <sL field> and <digits> are both zero, this is effectively a branch-on-zero instruction. These convenience mnemonics were easy to accommodate in the assembler.

To understand the operand formats, I wrote scripts to extract the operation codes and number of operand fields from the transcribed text and tabulate the frequencies of operation codes and their numbers of operands. This helped identify the operands that were required for each instruction, as well as cases where operand fields are optional.

The tabulation of mnemonic codes also helped identify the pseudo instructions used by the compiler modules. There were several of these, with most used for typical assembler functions such as defining the value of a symbol or label, setting the next memory address to be assigned, constructing data words from constant values, and signaling the end of the program.

The only challenging pseudo was FBGR, which generates the 29 words of digit codes for a format band used by the 220's Cardatron punched-card interface. See Chapter 6 in the Operational Characteristics manual (in [7]). The coding of a format band is quite complex. FBGR considerably eases that task by producing the necessary digit patterns from a list of parameters that are somewhat like COBOL PICTURE clauses. Fortunately, this assembler's formatting notation was very similar to that used in the Shell Assembler for the Burroughs 205 [11] and its Cardatron interface, so I found it relatively easy to implement this pseudo.

I christened the assembler for this symbolic notation the "BAC-Assembler," from the product code that Burroughs assigned to the BALGOL compiler, BAC-220. It is actually a cross-assembler, as it does not run in the 220 environment. The assembler is written in Javascript and runs from a web page in a standard browser. It can be run directly from the retro-220 project's hosting site, or downloaded from the project repository and run locally. Documentation and instructions for its use are in the retro-220 project wiki [12].

Although the BAC-Assembler was developed specifically to assemble the compiler and library modules, it has enough features that it can be used for general 220 programming. It generates absolute machine code that can be loaded into the retro-220 emulator and executed directly. It supports the following output formats:

• A standard, self-loading Cardatron format band 6 card deck. Format 6 is a hardwired band used to load numeric words of data.
• A self-loading paper tape image.
  
• A "machine language" (ML) card deck. This format is used by the compiler for machine-language routines to be merged with BALGOL programs at compile time, and by the generator program for updating the standard library. It is described in Appendix F of the compiler reference manual.
• A "media" card deck. This format is used with the generator program's INPUTMEDIA and OUTPUTMEDIA specifications to replace the default Cardatron I/O routines in the compiler and library. This format is documented in Appendix F of the compiler reference manual. See the BALGOL-INPUTMEDIA-OUTPUTMEDIA folder [14] in the retro-220 project repository for an example.
  
• A magnetic tape image.
  

The last three formats were implemented to support reconstruction of the compiler and generator program. The first two were implemented as a convenience for general 220 programming.

The GEN-Assembler

The assembler that Burroughs used for the generator program appeared to be quite a bit more sophisticated than the one used for the compiler and library. The columnar format it used was similar to but not compatible with that of the BAC-Assembler. This assembler supported more complex symbolic expressions as well as a more sophisticated notation for literal operands.

From an analysis of operation codes and operand formats like the one done for the BAC-Assembler, this assembler used the same hardware operation codes, although there were a few additional convenience mnemonics. It is likely that this assembler had a macro processing facility, as the generator source has many instances of a DO operator that generated two instruction words to execute a subroutine call. The cross-assembler discussed below simply implemented DO as a special pseudo operator.

This assembler also had a richer set of pseudo operators compared to the BAC-Assembler. It had equivalents for all of the ones mentioned above for BAC-Assembler, but in addition, ones to assign assembly addresses starting at one location but store the assembled code at another, specify the location of the literal pool, erase the internal symbol table and start a fresh assembly, construct words from multiple sub-fields, fill a range of words in memory with a constant value, and generate sequences of data words from lists of constant values and expressions. It had a FORMAT pseudo for generating Cardatron format band data similar to FBGR for the BAC-Assembler, but fortunately the notation was the same and I was able to transfer the FBGR implementation from BAC-Assembler with almost no change.

Since it was designed to reconstruct the generator, I christened this cross-assembler the "GEN-Assembler." It is also written in Javascript and runs in a standard web browser. Like the BAC-Assembler, it can be run from the retro-220 project's hosting site or downloaded and run locally. The user interface is identical to BAC-Assembler, and it can output object code in the same formats. It is in many ways a more capable assembler than BAC-Assembler, and is at least as well-suited for general 220 programming. Documentation and instructions for its use are also in the retro-220 project wiki [13].

Pre-Loading Cross-Assembler Literal Pools

Something that proved to be necessary with both cross-assemblers was a capability to pre-load the literal pool. A literal pool is a block of data the assembler constructs to hold values that are defined as literals in the operand fields of instructions. Rather than have the programmer manually declare a constant value, give the address of that constant a symbolic name, and then reference that name in operand expressions, literal pools allow the programmer to simply write the literal directly in an operand expression. The assembler automatically allocates storage for the value and essentially assigns the literal itself as the value's symbolic name. Multiple references to the same literal value throughout a program result in addressing the same value in the pool.

For example, the following instruction occurs at address 3182 in the compiler main module:

CAD   +6034037172

The assembler recognizes +6034037172 as a literal, assigns it address 4113 in the literal pool, assembles the value of the literal in that location, and assembles that CAD (Clear and Add) instruction with the pool address, resulting in an object word of 0 0000 10 4113.

A literal pool is not difficult to implement in an assembler, but what proved to be impractical was allocating the pool words at the same physical addresses as the original assembler did. The ordering of literal address assignments was probably some function of the original assembler's symbol-table structure and symbol lookup mechanism. Although assigning different pool addresses would not affect the correctness of the program, it produced undesirable differences in the mechanical matching of the generated assembler listing back to the transcription of the original documents.

I tried a few fairly obvious address assignment schemes without success before deciding that this was a problem not worth trying to solve the same way the original assembler did. Instead, I simply extracted the pool addresses and values from the transcriptions and designed a JSON format to hold them. You then load a file containing this JSON into the cross-assembler at the start of the assembly process to pre-populate the assembler's literal pool table with values at the specified addresses. This is a feature specifically intended for recovering the compiler and generator, and is not something you would expect to use with either cross-assembler for regular 220 programming.

Pre-loading the literal pool proved to be useful for resolving another problem. In the generator program there was one literal expression involving a symbolic value that was a forward reference to a symbol that in turn was defined after the point where the assembler was instructed to place the pool. See the LDB instruction at card sequence 1903, address 4310, with the literal operand "=BUF+1=".

 

The location of symbol BUF after the location of the pool, and the fact that the value of the symbol depended upon the size of the pool, meant that the literal value was also dependent on size of the pool. I could never get the assembler to assign locations correctly after the point where the pool was emitted to the object code. Since I was more in the business of recovering a compiler than writing an assembler, I decided not to try to fix what amounted to a GEN-Assembler design deficiency and let pre-loading of the pool resolve that problem for me.

Constructing the Generator Tape

After transcribing and proofing the original listings, writing two cross-assemblers, and getting everything to assemble and match back to the transcriptions, the next task was to take the assembled object code and construct a Generator Tape. The Generator Tape cannot be used to run the compiler; rather the generator program constructs a loadable compiler tape from it.

This task was not the most time-consuming part of the project, but it proved to be one of the most complex and challenging ones. Not having access to any documentation or an actual Generator Tape, the only way to approach the problem was to try to deduce from the generator program the layout of the tape and try to reproduce it.

The 220 Magnetic Tape Subsystem

Before discussing the Generator Tape, it will be useful to discuss the 220 magnetic tape subsystem, because it was quite different from the IBM standard that later became dominant, and the compiler took advantage of that subsystem's unique characteristics.

The tapes themselves were 3/4-inch Mylar on 3500-foot reels. The drive operated at 120 inches/second, recording at 208.3 bits/inch. Each 11-digit 220 word was recorded on the tape as 12 four-bit BCD (binary coded decimal) digits, with a "spacer" digit between words. Each six-bit recording frame on the tape held a BCD digit, an even-parity bit, and a control bit used to detect block boundaries. No longitudinal block-parity checking was used.

The tapes were recorded in two parallel, six-bit "lanes," a feature brought forward from the Burroughs 205 tape subsystem. There were two tape heads, but a drive could read or write only one lane at a time. Several tape instructions provided for switching between lanes, a process that took about 70ms.

Blocks could contain 10 to 100 words. Importantly, the design of the block format allowed drives to overwrite existing blocks reliably, something you could not do with the IBM format. Once a block was written, though, that structure was locked down. To overwrite the tape with a different block structure, the entire tape first had to be erased, something the drive could do off line. There were two forms of tape write instruction: MIW was an "initial" write, and only worked on erased tape. MOW was an "overwrite," only worked on existing blocks, and had to write data of exactly the same length as the existing block.

Single tape instructions could read or write up to 10 blocks at a time. The tape control unit also had two forms of search that operated independently of the processor. A "search" considered the first word of a block to be a numeric keyword and could search the tape bidirectionally, stopping at the first block with a keyword greater than or equal to a value provided by the search instruction. This obviously worked best if the keywords on tape were arranged in monotonically ascending order. A "scan" worked only in the forward direction, but would stop when it found a matching value in one of the first 10 words in a block. Due to the overwrite and search capabilities, 220 applications tended to use magnetic tape more like a semi-random device than a purely sequential one.

Because of the difference between the initial and overwrite modes of writing to tape, it was common practice for applications to be designed to work with pre-formatted tapes having blocks of a constant size. Because larger block sizes used tape more efficiently, it was also common to format tapes with the maximum block size.

This was the case with the BALGOL generator and compiler. Both the Generator Tape and the compiler tapes created from it required magnetic tapes that were pre-formatted with 100-word blocks. The BALGOL generator and compiler used both the block overwrite and the search capabilities.

Constructing the Compiler and Overlay

Appendix A in the compiler reference manual has a good description for creating a loadable compiler tape from the Generator Tape. It mentions using a bootstrap card deck, the "Generator Callout program," but this deck was apparently distributed only on cards and we did not have it. The operating instructions for the compiler in Appendix B mentions a similar deck for the "Compiler Callout program," which we did not have either. Fortunately, though, that appendix shows the code for an equivalent paper-tape compiler bootstrap routine:

6 1000 04 0002       PRB   2      READ BOOTSTRAP INTO ADDR 2
0 0000 39 0000       SOR          DO NOT HALT ON OVERFLOW
0 2008 50 0000       MRW   002    REWIND TAPE 2, SWITCH TO LANE 0
0 2001 52 0000       MNC   0,2,0  READ 10 BLOCKS FROM TAPE 2 TO ADDR 0
6 0000 30 0002       BUN   LOAD   BRANCH TO LOAD ROUTINE AT ADDR 2

From that five-instruction paper-tape bootstrap it was easy to understand both how the compiler loaded and how to construct a similar bootstrap routine for punched cards:

0 0000 39 0000       SOR          DO NOT HALT ON OVERFLOW
0 2008 50 0000       MRW   002    REWIND TAPE 2, SWITCH TO LANE 0
0 2001 52 0000       MNC   0,2,0  READ 10 BLOCKS FROM TAPE 2 TO ADDR 0
0 0000 30 0002       BUN   LOAD   BRANCH TO LOAD ROUTINE AT ADDR 2

From understanding the way the compiler loaded, I could see that the generator program loaded the same way. Both bootstraps read the first ten blocks (1000 words) from tape to memory starting at address 0000 and then branched to address 0002, which is the start of a routine that loads the rest of the program, validates and strips out the checksum words embedded in the code, and then branches to the beginning of the program proper. Thus, these small bootstrap programs were the first clues as to the layout of both the Generator and loadable compiler tapes.

The routine at address 0002 in both the generator and compiler assembly listings is labeled "LOAD." Immediately after that routine is another one labeled "STORE." Inspection of that routine in both programs revealed that it writes the program from memory to tape, calculating and inserting checksum words in the manner expected by the LOAD routine. So here was the second clue -- if we could arrange to get the assembled object code for these programs into memory, all we need to do is execute a branch to the STORE routine in order to get that code written properly to magnetic tape.

The overlay module, as its name implies, is loaded by the compiler to overlay a portion of the compiler's memory. Thus it does not have a load routine of its own, but does have a corresponding (and unlabeled) store routine located at its end, starting at address 4000.

These embedded store routines were sufficient to get the generator, compiler, and overlay written correctly to the Generator Tape. The compiler and overlay are written to lane 0 on the Generator Tape, while the generator is written to lane 1. I eventually wrote a few small 220 programs to partially automate this process by positioning the tapes and calling the internal LOAD/STORE routines within the modules.

The progress thus far was a good start on constructing a Generator Tape, but there were a number of other details that still needed to be resolved, the most significant of which was getting the standard library onto the tape.

Constructing the Standard Library

The Generator Tape as distributed by Burroughs would store the object code for the standard library in the form required by the generator program. Loadable compiler tapes produced by the generator would store the library in the form required by the overlay module to select individual routines and merge them into a program's executable image.

During the process of creating a loadable compiler tape, the generator program has the ability to modify the standard library, allowing sites to build a compiler tape having a customized library. Sites could alter the existing routines, add new library routines of their own, or even delete routines they did not want.

"Modify" is perhaps too generous a word here, because the process is one of total replacement. The complete set of library routines to be on the compiler tape must be fed to the generator program on cards in the "machine language" (ML) format mentioned earlier. Thus, you need the ML card decks for all of the routines that will make up the library, including the ones you are neither modifying nor adding.

The set of object code cards for each library routine must be prefixed by a card with the name of the routine, the type of its return value if any, and a list of the types of its parameters if any. If a library routine references other library routines, the name card must be followed by an "equivalence" card for each referenced routine. Using the equivalence information, an address-coding convention in the ML format allows a library routine to reference locations at relative offsets within other library routines.

To make the process of updating the library easier, the generator supports an option to punch a card deck in ML format containing the object code for the entire library, complete with name and equivalence cards, in the format required for feeding back into the generator on a subsequent run. A site wanting to modify the library could thus start by punching this deck and then modifying only parts of that deck as needed.

I started with the idea of somehow constructing the library structures for the Generator Tape myself from the assembled output of the transcribed library routines. I tried to determine the structure of the library on tape from the generator program, but the handling of the parameter signatures and equivalence information involved a lot of quite complex code, and I had trouble understanding how those structures should be constructed.

But then I had a thought -- instead of trying to construct the library structures for the Generator Tape myself, would it be possible to get the library update feature of the generator program to do it for me? It appeared from looking at the generator and overlay code that the structure of the library on tape was the same for both the Generator Tape and the loadable compiler tapes. The library comes at the end of the Generator Tape, after the overlay module, so inserting the library should be simply a matter of appending the library blocks to the end of the tape.

I decided to try the following scheme:

• Construct a preliminary Generator Tape with an empty library.
• Manually construct the complete card deck for updating the library as required by the generator from the assembled output for each routine, inserting the necessary name and equivalence cards.
  
• Use the generator program with the preliminary tape to create a compiler tape.
• During the creation of the compiler tape, use the card deck to replace the (empty) library coming from the preliminary Generator Tape and thus output the library routines from the card deck to the compiler tape.
  
• Finally, extract the tape blocks containing the library from that compiler tape and append them to the preliminary Generator Tape, thus creating a final Generator Tape.
  

To make a long story short, this approach worked. Of course, I had to assemble all 28 of the transcribed library routines individually to get their object code in ML card-deck format, as well as manually prepare their name and equivalence cards.

Fortunately, the information for the names and equivalences is embedded as constant strings in the source code for each of the routines, bracketed by words with special sign digits. For the ARCSIN function, it looks like this:

CNST  40000990000
CNST  $ARCSIN,REAL(REAL) ARCTAN=1 ROMXX=2 ERROR=3 $
CNST  90000000000

The 40000990000 word signals the end of the object code in an ML deck (see Appendix F in the compiler reference manual), while the 90000000000 word signals the end of the name/equivalence information. The complete library deck for the ARCSIN function that would be fed to the generator program thus looks like the following. The digits 2 and 6 in the first column allow the generator to distinguish between name/equivalence cards and ML object cards. Note how the 40000990000 word is now the last one on the last card of the deck and the name/equivalence information has been dropped, as the generator will not tolerate that additional data.

2 ARCSIN, REAL(REAL)
2   ARCTAN=1
2   ROMXX=2
2   ERROR=3
60600000100000000000100006000040035280000410011600004402006000030020480000420000
60600000200006600003602396000040034960000100352600002503496000030010280000000012
602000003000122416249550040000990000

The presence of the bracketing words for the name/equivalence information suggests that Burroughs probably had a Generator Tape-builder program that would process the ML decks for the library routines, extract the name and equivalence information, drop the words following the 40000990000 word, and write the remaining code with the necessary library structures directly to the Generator Tape. Not having such a builder program (and not knowing enough to write one), I had to use a much clumsier process, but it worked, and was only a one-time effort.

When speaking of "cards" and "decks" throughout this post, I am of course not referring to actual punched cards. The retro-220 emulator uses plain text files to simulate card decks, with the individual lines in the files simulating individual card images. A sample "deck" for generating a compiler tape from a preliminary Generator Tape with card images for the full standard library is available as a text file in the retro-220 project repository.

Documenting the Process

As I worked through the process of understanding the layout of the Generator Tape and marshaling all of the parts that needed to go into it, manual generation of that tape started to become quite complex. At first I was keeping all of this in my head, but as I got further along, the complexity reached a point where I had to start writing things down.

Those notes evolved into a 12-page document that describes a 24-step procedure for constructing a Generator Tape, starting from only the transcribed source code and a few utility decks in the retro-220 project's GitHub repository [9]. That document is available in the project wiki [10].

It is no longer necessary for anyone to work through that 24-step procedure, unless the Generator Tape needs to be corrected. To make using the compiler, creating customized compiler tapes, or reconstructing the Generator Tape easier, the following files are available in the project repository [9]:

• Two loadable compiler tape images -- one configured for a system with 5KW of memory (the minimum the compiler will support) and another for 10KW (the maximum the 220 supported).
• A pre-built Generator Tape image for the generator, compiler, and library in their current state.
• Files for the various bootstrap and utility card decks.
  
• Pre-assembled files of object code for the compiler, overlay, library routines, and generator.

Summarizing from the 12-page document, the layout of the Generator Tape turned out to be the following (all blocks are 100 words in length):

• Lane 0:
1. 50 blocks (#1-50) of the compiler main module. These are written in groups of 10 blocks containing 999 program words followed by a checksum word.
   
2. Two blocks (#51-52) reserved for compiler patches, also checksummed. These blocks are not used with the standard compiler.
3. Three blocks (#53-55) containing a copy of words 3996-4295 from the compiler main module, not checksummed. This is part of the compiler's initial symbol table, before entries for the library routines have been inserted. These blocks are used by the generator to rebuild the symbol table when replacing the library, after which the new symbol table containing information for the library routines is written back over blocks 41-43 of the generated compiler tape. This use of blocks #53-55 was the most obtuse part of the tape format to figure out.
4. Three blocks (#56-58) containing addresses 0000-0399 of the overlay module, not checksummed. This is the object code for the Symbolic Dump diagnostic routine.
   
5. 29 blocks (#59-87) containing addresses 0700-3599 of the overlay module, not checksummed. This is the code loaded by the compiler after the end of the user's BALGOL source program has been compiled. The 32 blocks of the overlay module in blocks #56-87 will be checksummed by the generator as one 3200-word unit before being written to a generated compiler tape.
6. Three blocks (#88-90) for the Library Table, a directory to the library routines.
7. One block (#91) with a zero as the first word. This appears to be a low-key stopper block for the 220's MTS (Magnetic Tape Search) instruction, which was used to position the tape efficiently to individual library routines.
8. n blocks (#92 - n+91) for library routines. The first word of each block is a search keyword for the MTS instruction. Each routine starts on a block boundary and may span multiple consecutive blocks.
9. One block (#n+92) with all nines in the first word. This serves as an end-of-file sentinel to the generator program and as a high-key stopper block for the MTS instruction.
• Lane 1:
• 50 blocks of the generator program, checksummed as for the compiler main module above.

A loadable compiler tape has a similar format to the Generator Tape, but with these differences:

• Lane 0:
• The initial symbol table for the generator's use in blocks #53-55 is omitted. Therefore, the overlay module (with its checksum word) starts at block #53 and the Library Table starts at #85.
• Following the all-nines sentinel block at the end of the library, the generator writes four blocks containing the code for the Object Dump and Program Card Loader routines described in Appendix B of the compiler reference manual. These routines are assembled as part of the generator program.
  
• Lane 1:
• Used as workspace by the compiler's Symbolic Dump diagnostic facility.
  

The tape images in the repository for the retro-220 emulator are plain ASCII text files with a ".tape" file name extension. You can look at these files with a text editor and view the structure of the Generator and compiler tapes. See the wiki page on the magnetic tape subsystem for details on the tape image format.

Debugging the Recovered Compiler

By the time I had finished the emulator, assembled all of the source code, puzzled out the format of the Generator Tape, gotten the generator program working, and created the first loadable compiler tape, it was December 2017. 

 

Obtaining sample BALGOL source code with which to test the compiler and debug the recovery effort was by far the simplest of the tasks in this project. Section 11 of the 1963 reference manual has four sample programs, apparently written by faculty at Stanford University, including such luminaries as J. G. Herriot and George Forsythe. The 1961 edition of the manual also includes these, plus a fifth sample program. None of them is very long, so I simply transcribed them from the manuals. There were a few typographical errors in the manuals, but these were easy to discover and correct once the compiler was starting to work. I also wrote a couple of small test programs from scratch.

The generator program proved to be very easy to debug and get working, largely because its assembly listing included the object code, which allowed the mechanical matching process discussed earlier to find the significant transcription errors. The biggest problems with the generator were not with the program, but in getting its specification cards properly prepared and getting the various modules of object code arranged on the preliminary Generator Tape so that the program would work properly.

Debugging the compiler and library was another matter. I started compiling some of the test programs, and by setting console switches to cause the compiler to print the object code it was compiling, could see that it was working -- somewhat.

The compiler would be parsing the BALGOL source text and generating what appeared to be correct code, but then would start reporting errors that were not related to the source code, including some strange ones like "INVALID PSEUDO-OP" that suggested internal compiler errors. In other cases, the compiler would go off into never-never land, eventually either halting without explanation or looping continuously.

This behavior was highly distressing, partly because something was clearly wrong with the compiler, or the emulator, or both, but mostly because I had no good idea how to start diagnosing these problems, let alone fixing them. The compiler is an extremely complex piece of software, written very cleverly and efficiently by people who really knew the 220, and I never got to the point of a comprehensive understanding of how the compiler worked internally. Plus, the problems were likely occurring long before any evidence of them was surfacing, resulting in a very murky trail to try to follow.

At this point, I decided to launch the complete second proofing of the transcriptions for the compiler, overlay, and library routines. That effort took several weeks to complete, and found a handful of errors, especially in the all-critical compiler tables. That solved a few problems, but still left a number of mysterious errors.

As always with such situations, the only thing one can do is to start with the evidence at hand and try to work backward from there to the cause. Since most of the evidence I had consisted of error messages produced by the compiler, it seemed logical to start at the point in the code where the error message was being generated and try to see which execution paths led to that point. In most cases this was straightforward to do, either by inspecting the transcribed code in the neighborhood of the error message, or by following subroutine return linkages and inspecting the code in the neighborhood of the originating calls.

Tracing the error messages revealed the cause of the error about half the time. For the rest, I had to try to reason about what the compiler was trying to do at that point and hypothesize what could have gone wrong. In other words, the other half of the problems were solved by making what amounted to lucky guesses and following up on them. I was surprised at how successful I was at this. Eventually I started to get error-free compilations and be able to run the resulting object programs.

One thing that helped in the debugging is that the 220 has a feature, the S Register, which allows you to set a trap address on the console. Before the processor executes an instruction at that address, it halts. From there you can see the contents of the registers and use the console keypad to inspect words in memory. I had also implemented a feature in the emulator that would generate a complete dump of the 220 memory. That proved to be much more convenient for inspecting variables and tables in the compiler than finger-boning the console one word at a time.

In the end, most of the trouble in the compiler was caused by a few subtle typos in the transcription. The following table shows the typos in the compiler main module uncovered by debugging:

Address	Assembly Text	Error
0621	NOPV1 CNST  00000100001	10 should be 01
0691	CNST  20176000000	17 should be 71
1480	*M    LDB   MODE	*M should be *H
1971	STA   SYMBL	SYMBL should be SMBL
2469	BUN   SMBL,BUNZ	SMBL should be ASMBL
2660	PRFSW F4241 1210,01,1	1 should be 0

The overlay module was much cleaner. The only significant problem was at address 0010: "MRD 4 100,OT,BMOD" should have been "MRD 4 100,OT,3,BMOD". MRD is a magnetic tape read instruction; the missing "3" is the number of blocks to read.

These types of problems just go to show that even with careful transcription and multiple careful proofing passes, it is almost impossible to recover software from listings without introducing errors, some of which will have nasty effects and be difficult to find.

Debugging the compiler revealed one serious error in the emulator. The 220 supports two similar instructions, CFA (Compare Field A) and CFR (Compare Field R). These compare either a whole word or a partial-word field between a word in memory and either the A or R register, setting the result in the processor's LOW/EQUAL/HIGH comparison toggles. That result can be acted upon by the 220's BCH/BCL/BCE/BCU conditional branch instructions.

Compare instructions like these are usually easy to implement -- the words in the register and in memory are virtually subtracted, and the comparison toggles are set based on the virtual difference being positive, negative, or zero. This is complicated in the 220, however, by the fact that the sign is a whole digit. The low-order bit in that four-bit digit indicates the arithmetic sign (1=negative), but the other bits have meaning in certain situations.

If the sign digit is part of the field to be compared, then CFA and CFR take the extra sign-digit bits into account and order the sign values in a strange way:

3 < 2 < 1 < 0 < 7 < 6 < 5 < 4 < 8 < 9

In addition, if the sign digit is 1, 2, or 3, the remaining digits in the word or field are compared using their nines-complement value.

To put it simply, I didn't get the implementation of this right the first time, nor the second, nor the third. It got to the point towards the end that, whenever I encountered strange behavior by the compiler, I started looking for CFA or CFR instructions in the code path leading up to the error and examining how those instructions were behaving in that specific case.

You would not think that weird comparisons of signs other than 0 or 1 would have much impact on something like a compiler, but BALGOL does extensive field packing in its internal tables to minimize their size, thus to allow compiling larger programs. The sign digits in these tables are frequently included as parts of fields or as fields on their own, and comparisons involving those fields are surprisingly frequent. The people writing the compiler knew exactly how CFA and CFR were supposed to work, and they took every advantage of the somewhat unorthodox behavior of those instructions. Once I had the comparison logic implemented properly in the emulator, the last of the strange compiler behavior simply disappeared.

Recovery of the BALGOL compiler was completed in mid-July 2018. The compiler and library seem to be working quite well now, but I will not be the least bit surprised if someone eventually finds additional errors in the transcriptions.

Recovering the BALGOL compiler for the 220 has been one of the most difficult and challenging software projects I ever tried to do. The retro-220 emulator, while hardly trivial, was a straightforward development task by comparison. Regardless of the difficulties involved, though, recovering the BALGOL compiler and getting to see it run again has been immensely gratifying.

Postscript

Compiling from Paper Tape

After finishing the compiler recovery project in the summer of 2018, I started working with Michael Mahon to enable paper tape input and SPO (console typewriter) output for the compiler. Michael has written a 220 emulator for the Apple II [15], based upon his experience at CalTech with a 220 that did not support the Cardatron punched card interface. As with that 220, his emulator does not support punched cards, thus he was unable to run the standard compiler.

 

The generator program has the ability to replace the I/O routines for the compiler and library using its aforementioned INPUTMEDIA and OUTPUTMEDIA specifications, which are described in Appendix A of the 1963 compiler reference manual. Thus we set out to try to customize the compiler so that it could be used with his emulator.

Appendix A mentions a document issued by Burroughs, "Supplemental Material for Use with the BAC-220 Generator," that purported to show examples of alternate input and output routines, but of course we did not have that. Appendix A describes how to generate a compiler tape with custom I/O routines, and Appendix F describes the calling conventions and "media deck" format for such routines, but actually figuring out how to write the routines was going to be up to us. We eventually were successful, and the results are available in the BALGOL-INPUTMEDIA-OUTPUTMEDIA folder of the retro-220 project's repository [14].

The interesting thing about this episode with respect to the compiler recovery effort is that it uncovered a few bugs in the generator program. These were not, however, due to errors in the transcription -- they appear to be original bugs present in Professor Knuth's copy of the generator listing:

1. The generator needs to know the location of several items in the compiler and overlay modules so it can adjust their code during the process of generating a compiler tape. It does this by means of symbolic address definitions, but these definitions need to be kept in sync with the actual locations in the compiler and overlay. One of the symbolic definitions, NUMB, was incorrect. It was defined in the generator as "4800+1335," but based on the location of that symbol in the overlay module, should have been "4800+1334." This error did not affect generation of a compiler tape with the default Cardatron I/O routines, but it did affect the code adjustments the generator had to do when replacing the default routines, resulting in words at the wrong memory addresses getting adjusted. This suggests that in the 1962 listings Burroughs distributed, the version of the generator may not quite have matched the versions of the compiler and overlay modules.
2. The generator is driven largely by a series of small tables that are selected for use in a given run based upon the specifications present in its input card deck. Each table consists of a series of words that encode operations the generator must perform to adjust a specific feature of the compiler. Each of these tables begins with a word indicating the number of words that follow it in the table. One of the tables, F2, had an incorrect length word, 6 instead of 8. This was another case where the error did not affect generation of a compiler with standard I/O routines. When replacing those routines, however, the truncated table resulted the generator failing to delete support for the compiler's standard output completely, which in turn resulted in processor alarms when the overlay module tried to execute a Cardatron instruction on a system without a Cardatron.
3. Another table, with the point-label "1" following the label PTVER, was missing two entries that adjusted the way the compiler output its heading line at the start of a compilation. The consequence of this was relatively benign, in that the compiler simply printed the wrong heading.

Each of these errors has been corrected in the source for the generator available on the retro-220 project repository, but the original version of the generator, matching the original assembly listing, remains available in the repository's BALGOL-Generator--ORIGINAL sub-folder.

Finally, an Assembler Manual

 

During a visit to the Charles Babbage Institute in Minneapolis during the Fall of 2019, I discovered a manual for what appears to be the assembler used for the compiler, overlay, and library modules [8]. That document indicates, not surprisingly, that this was a much more fully-featured assembler than is apparent from the 1962 listings. It has more powerful address expressions, additional pseudo instructions (termed "control ops"), provision for overlays and source code libraries, and a relatively sophisticated macro facility (termed "generators").

From inspecting that document, I had done a pretty good job of reverse-engineering its assembly notation, or at least those parts of it that were revealed in the compiler listings. My source card format is a little different, the pseudo op for comments is REMK instead of REM, and there are additional convenience operator mnemonics, but none of that was apparent from the transcribed listings. It would be interesting at some point to go through the document and bring the BAC-Assembler more in line with this specification, but implementing some of the more advanced features, such as the library support and generators, would probably require a complete rewrite.

References

[1] "Introducing the Burroughs 220," https://datatron.blogspot.com/2018/02/introducing-burroughs-220.html.

[2] "Introducing the retro-220 Emulator," https://datatron.blogspot.com/2018/06/introducing-retro-220-emulator.html.

[3] "Algol-58 -- The International Algebraic Language," https://datatron.blogspot.com/2018/07/algol-58-international-algebraic.html.

[4] "BALGOL -- The Burroughs Algebraic Compiler," https://datatron.blogspot.com/2018/08/balgol-burroughs-algebraic-compiler.html.

[5] "Knuth Digital Archive Project Table of Contents," https://archive.computerhistory.org/resources/text/Knuth_Don_X4100/PDF_index/KnuthDigitalArchive-Index.html.

[6] "Burroughs Balgol [sic] 220 compiler listing," https://archive.computerhistory.org/resources/text/Knuth_Don_X4100/PDF_index/k-1-pdf/k-1-u2196-balgol220compiler.pdf.

[7] Bitsavers archive of Burroughs 220 documents, http://bitsavers.org/pdf/burroughs/electrodata/220/.

[8] "Burroughs 220 Assembler-Compiler," Bulletin 5024, Burroughs Corporation, Data-Processing Systems Group, April 1960. Burroughs Corporation Records, Product Literature (CBI 90), Charles Babbage Institute, University of Minnesota, Minneapolis. https://archives.lib.umn.edu/repositories/3/resources/186. Series 74, box 5, folder 17.

[9] BALGOL section of retro-220 GitHub repository, https://github.com/pkimpel/retro-220/tree/master/software/BALGOL.

[10] "Building the BALGOL Compiler," retro-220 project wiki, https://github.com/pkimpel/retro-220/wiki/BuildingBALGOL.

[11] "The Shell Assembler - Part 2," https://datatron.blogspot.com/2016/06/the-shell-assembler-part-2.html.

[12] "Using the BAC-Assembler," retro-220 project wiki, https://github.com/pkimpel/retro-220/wiki/UsingBACAssembler.

[13] "Using the GEN-Assembler," retro-220 project wiki, https://github.com/pkimpel/retro-220/wiki/UsingBACAssembler.

[14] BALGOL-INPUTMEDIA-OUTPUTMEDIA section of the retro-220 GitHub repository, https://github.com/pkimpel/retro-220/tree/master/software/BALGOL/BALGOL-INPUTMEDIA-OUTPUTMEDIA.

[15] "Burroughs 220 Simulator, v1.1," Michael J. Mahon, http://www.michaeljmahon.com/.