The Burroughs 205 and 220 Blog: 2015

Saturday, November 7, 2015

Knuth's Algol-58 Compiler

In the mid-1950s, a group of computer scientists from Europe and the United States began to lay the groundwork for a new programming language. Their idea was to define a universal notation for the expression of algorithms -- procedures for solving mathematical problems in a series of finite steps. Hence this new language was to be called "Algol" -- not to be confused with the trinary star of the same name in the constellation Perseus.

The focus of this new language was what, at the time, termed "scientific" (i.e., arithmetic) computing, as opposed to "commercial" computing, which was oriented mostly towards business record-keeping and accounting. The objectives set for for the new language were:

It should be as close as possible to standard mathematical notation.
It should be possible to use it to describe computing processes in publications.
It should be mechanically translatable into machine programs.

Design of the language proceeded to the point that a "Preliminary Report" [1] was published in the Communications of the ACM in 1958. This version of the language thus became known as Algol-58 and served as the basis for a number of early compiler implementations. The final ("revised") specification for the language, known as Algol-60, was not published until early 1963 [2].

This is Paul Kimpel again, with an update on the retro-205 emulator project. One of the primary goals of this project has been reconstruction of the Algol-58 compiler that Donald Knuth wrote for the 205. This post reports on our progress towards that goal.

A Tale of Two Compilers

As previously discussed in this blog [3], Knuth entered into a contract with the Burroughs Corporation in 1960 to write a compiler for the 205, which he did largely during the summer of that year at Burroughs in Pasadena, California. The compiler appears to have been finalized and released to customers in late 1960 or early 1961.

Knuth wrote two versions of an assembler to develop the compiler, EASY and MEASY [3]. He saved a MEASY-generated listing of the compiler, and in 2005 donated that listing, along with numerous other documents, to the Computer History Museum in Mountain View, California. Those documents have been scanned, and are available on the museum's web site. The scanned compiler listing can be downloaded as a PDF [4]; a full index to Knuth's documents can be found in [5].

I stumbled across this listing a few years ago and was fascinated both by it and by a similar listing Knuth donated for the Algol-58 ("BALGOL") compiler for the Burroughs 220. Those discoveries stimulated my interest in older computer systems, which evolved into emulating older computer systems, and eventually to this retro-205 emulator project. My main impetus for building a 205 emulator was the idea of reconstructing Knuth's compiler and getting it to work again.

Some years earlier, I also stumbled across Tom Sawyer's excellent web site devoted to the 205 [6]. As I started to research the 205 in preparation for designing my emulator, I contacted Tom, and we struck up an on-line relationship. As Tom discusses on his web site, he actually used a 205 while at the University of Portland (Oregon, USA). When he left Portland, he took with him a number of manuals and other technical documents for the 205, many of which he has generously shared with me during this project.

Tom was able to take something else of interest from Portland -- a listing of a raw-decimal dump from a tape for the "Burroughs Algebraic Compiler." This was just the object code for the compiler; there was no source. Long before I became interested in the 205, Tom had manually transcribed this listing (all 4600 11-digit words of it) and partially disassembled it by hand, as described in his blog post earlier this year [23]. He wrote is own emulator a few years ago and was able to get the transcribed object code to work with that emulator.

The existence of Tom's tape dump was quite a surprise when he revealed it to me a year ago. Of course, the question then naturally arose whether this was the same compiler as the one represented by Knuth's listing. Neither of us had heard of a second Algol compiler for the 205, but that was certainly possible. Thus, determining the relationship between Tom's tape dump and Knuth's listing became another goal for the project to pursue.

The text of Tom's transcription and partial disassembly (exported from his original Excel spreadsheet) [7] and a loadable tape image [8] in the format used by my emulator are available in the project's source code repository.

Tom also has a copy of the Programmers Manual for the Algol-58 compiler. This document does not appear to be otherwise publicly available. Until it can be properly archived, you can access a scan of it in [25].

Reconstructing the Compiler Source

Before we could assemble the compiler represented by Knuth's listing and compare its code to Tom's tape dump, let alone attempt to run that compiler in the emulator, that listing first had to be converted to source code.

Transcribing the Listing

There are basically two ways to convert a scanned listing into usable source code, either manually transcribe the listing to a text file, or use Optical Character Recognition software to convert the page images to a text file. Neither approach is easy, and neither is without its own set of problems. Both generally require a lot of manual proofing and correction. OCR software has come a long way in the last several years, but Knuth's listing is only 66 pages -- slightly more than 3600 lines. I decided that struggling with OCR was not worth the trouble, so simply transcribed it manually.

Since the listing was the product of a MEASY assembly, it had not only the text of the source code, but to the left of the source on each line, the numeric address and word that had been assembled. As with the recovery of the much smaller source code for the EASY and MEASY assemblers, I decided to transcribe the entire line image -- both source text and assembled code.

The reason for transcribing both the source and assembled code is to support validation of the transcription. Assembling the compiler with MEASY will produce another assembly listing, which can be captured as a text file and compared back to the transcribed file. The source code, of course, should match between the two, but most errors in transcription of the source code should result in differences in the assembled code. Since comparing two text files is something that software can easily and reliably do, I was thus hoping to avoid much of the line-by-line proofing that would otherwise be necessary.

Transcription of the compiler listing took about eight weeks, averaging a page or two per day, and was completed in late June of this year. Further work had to wait on debugging of the MEASY assembler, which in turn had to wait on development of magnetic tape support in the emulator. By the second week in July, I was finally ready to try to assemble the compiler.

To begin, I extracted the source code columns from the transcribed file to a separate text file, which became the input card deck to MEASY. I assembled that deck, captured the printer output as a text file, and compared that file to the original transcription using a side-by-side GUI diffing program. This first attempt revealed dozens of mismatches of exactly the sort you would expect -- missing or misspelled identifiers, improper column alignment, typos in the transcribed object code, confusion between letter "O" and digit "0," etc. After applying corrections to both the card deck and original transcription file, I assembled again, which revealed additional mismatches. It took only three such iterations of correction and reassembly over the course of an afternoon to achieve agreement between the transcription and the assembler output.

The project repository has copies of the corrected transcription from the listing [9], the corrected card deck extracted from that transcription [10], and the listing produced by MEASY from assembling that card deck [11]. This is not the original listing produced by MEASY, but one obtained by processing the MEASY output through a script [12] to perform the same type of leading-zero suppression that the IBM 407 would have. The emulator does not presently support leading-zero suppression for Cardatron output devices, but that is planned for a future release.

The repository also has a copy of the magnetic tape image of object code [13] produced by MEASY from assembly of the corrected card deck [10].

The Mysterious Assembly Mismatches

Most of the mismatches between the transcription and assembler output were trivial to understand and correct. There were half a dozen, however, that took a while to figure out. In all of these cases, the operand address in the assembled word did not match the one in the listing, and it was the assembled word from the original listing that did not make sense. For example, consider the instruction at address 0002 (line 608 in the transcribed file):

2 0 0000 15 7012             10 NOR        7

The "2" on the left is the address of the word being assembled, "0 0000 15 7012" is the assembled word, with 15 being the op code for the Normalize (NOR) instruction and 7012 being the operand address. The "10" to the left of "NOR" is an absolute address, which will be added to any symbolic address determined from other fields on the card. The "7" is a "loop tag," which serves to set the high-order digit of the operand address so that it references one of the high-speed memory-drum loops.

Alas, that line was coming out of MEASY looking like this:

2 0 0000 15 7010             10 NOR        7

Which seems right -- with no other symbolic address following the op code, the operand address should reference location 10 with the 7000-loop tag applied to it. But it turns out that the operand address in the scanned listing is correct after all. It had been transcribed properly, but that line in the scanned listing was missing something. What it must have contained was this:

2 0 0000 15 7012             10 NOR     0& 7

As described in the earlier blog post on EASY and MEASY [3], columns 37-38 of a source card can represent an optional "program point" address. This can be either a reference to a numeric program-point label forward or backward of the current line (nF, nB), or a relative address so many words before or after the current line (n&, n-). Note that on the IBM card equipment used with the 205, "&" and "+" are the same character, with the kind of print wheel installed in the 407 tabulator determining which glyph prints.

Therefore, for this line in the listing the operand address should be 10 plus the current location (0002) offset by zero, so 0010+0002+0000=0012, which after the loop tag is applied becomes 7012, thus agreeing with the assembled word on the listing.

What happened to the "0&" from the original source card? The answer turned out to be that the 407 ate it. I had to study a manual on the 407 to understand why:

Suppression of leading zeroes for numeric output to card devices was done by means of plugboard wiring in the card device, not by the 205 or the Cardatron.
IBM card equipment divided each column into two parts, "zone" punches (the top three rows on a punched card) and "numeric" punches (the bottom nine rows).
Under this scheme, "0" (the third row on a punched card) is a zone punch, not a numeric punch. Similarly, "&" or "+" (the top row on a card) is also a zone punch.
Pins on the 407 plugboard designated columns in which zero suppression was to begin. Printing in one of these and its immediate columns to the right was suppressed until the 407 encountered a column that contained a numeric punch. The intent is to replace leading zeroes by blanks, but note that printing will be suppressed for any leading character that does not have a numeric punch.
Since the "0" and the "&", do not have numeric punches, and were the leading characters in their field, their printing was suppressed. Not seeing them on the scan, of course I didn't initially transcribe those characters, resulting in the mismatch.

One of the perils associated with trying to recover software from old listings is that you can only recover what you can see, and the data always goes through some sort of transformation between its source medium and the listing. Occasionally that transformation hides or corrupts important information, as it did in this case. Of course, most listings were never intended as long-term archival software storage -- they're just what someone happened to save at the time -- but they are often the only record of the software that has survived, so we must suffer the archival limitations of listings as best we can.

In the rest of this post, I will refer to the compiler transcribed from Knuth's listing as the "recovered" compiler and the one from Tom Sawyer's tape dump as "Tom's" compiler.

The First Compile

Having successfully assembled the source for the recovered compiler and gotten its assembly listing to agree with the transcribed listing, there wasn't much left to do but try to run the compiler and see if it worked.

Tom had written a small program to exercise the compiler in his emulator, and as a first attempt, I decided to try compiling that:

2X=40$
2Y=50$
2Z=60$
2COMMENT HERE IS SOME COMPLICATED STUFF$
2X1=X + Y + 3.14.X + 7.98/Z + (X-Y).(X+Z)$
2X2=X-Y$
2X3=X.Y$
2X4=X/Z$
2STOP$
2FINISH$

The first column of the card has a "2" to select the format band in the Cardatron. The free-field program text is taken from columns 2-72, with columns 73-80 reserved for sequence numbers or identification. The "$" is a substitute for the semicolon (;), which the Cardatron and IBM equipment did not have. Depending on the print wheels installed in the 407 tabulator, "+" may print as "&", "=" may print as "#", "(" may print as "%", and ")" may print as "¤" (termed the "lozenge").

The compiler uses the asterisk (*) to denote exponentiation. Multiplication is denoted by a period (.). Where no ambiguity would be introduced, the compiler allows the multiplication symbol to be omitted. Thus, the fifth line could have been written as:

2X1=X + Y + 3.14X + 7.98/Z + (X-Y)(X+Z)$

On the morning of 11 July 2015, I loaded the tape produced by assembling the compiler with MEASY and ran the compiler, as described in the next section. I then loaded the card deck for the program above into the reader, pressed the reader's start button, and to my great surprise saw the following start to come out on the printer:

X=40$

Y=50$

Z=60$

COMMENT HERE IS SOME COMPLICATED STUFF$

X1=X + Y + 3.14.X + 7.98/Z + (X-Y).(X+Z)$
                        0071 0 0000 64 7086
                        0072 0 0004 12 6019
                        0073 0 0000 64 7087
                        0074 0 0004 12 6018
                        0075 0 0000 64 7088
                        0076 0 0004 12 6017
                        0077 0 0000 64 6019
                        0078 0 0000 82 7089
                        0079 0 0000 02 5019
                        0080 0 0000 64 7090
                        0081 0 0000 33 0010
                        0082 0 0000 83 6017
                        0083 0 0000 02 5018
                        0084 0 0000 65 6018
                        0085 0 0001 30 0091
                        0086 0 5240 00 0000
                        0087 0 5250 00 0000
                        0088 0 5260 00 0000
                        0089 0 5131 40 0000
                        0090 0 5179 80 0000

X2=X-Y$

X3=X.Y$

X4=X/Z$

STOP$
                        0091 0 0000 80 6019
                        0092 0 0000 02 5017
                        0093 0 0000 64 6017
                        0094 0 0000 80 6019
                        0095 0 0000 82 5017
                        0096 0 0000 80 5018
                        0097 0 0000 80 5019
                        0098 0 0000 80 6018
                        0099 0 0000 80 6019
                        0100 0 0004 12 6016
                        0101 0 0000 65 6018
                        0102 0 0000 80 6019
                        0103 0 0004 12 6015
                        0104 0 0000 64 6018
                        0105 0 0000 82 6019
                        0106 0 0004 12 6014
                        0107 0 0000 64 6019
                        0108 0 0000 33 0010
                        0109 0 0000 83 6017
                        0110 0 0001 30 0111

FINISH$
                        0111 0 0004 12 6013
                        0112 0 0000 08 0137
                        0113 0 0001 30 0114

The compiler was actually working!

The indented, all-numeric lines are object code generated by the compiler. The first four digits are the memory address, followed by the 11-digit word at that address.

Note that the compiled code is output in 20-word blocks. The compiler is generating the code so that it can be loaded into and executed from the 7000-loop on the memory drum. At the end of each block is a CUB (30) block-and-branch instruction to load the next 20-word block of code to the 7000-loop and branch to it. One of these occurs at address 0085, branching to the next block at 0091 (the words after that are floating-point constants referenced within that block); another occurs at 0110, branching to the next block at 0111. That is sophisticated code generation for the 205, as programs run almost ten times as fast from the high-speed loops on the memory drum as they do from main memory.

After reaching this point, the compiler halted with 5250 in the C-register address field. I didn't yet know it, but the compiler hadn't finished, and was waiting for more input, but I stopped there. The next section describes the detailed steps to run the compiler and what we have deduced it was waiting for at the end of the source deck.

Running the Recovered Compiler

MEASY writes its assembled code to magnetic tape unit 4. It prefixes the assembled code on tape with a three-block loader, which assumes the tape will be loaded later from unit 4. To run the program, you load the loader manually to address 1000 and then branch to location 1045. The loader then loads the assembled code from tape, fixes up any forward references and halts with 7555 in the C-register address field. Once the compiler is loaded, you execute it by manually branching to its entry point at address 3040.

To run the recovered compiler in the retro-205 emulator, perform the following steps. See [14] for information on operating the magnetic tape drive and [15] for information on the Cardatron devices.

On the Supervisory Panel, make sure the LOCK/NORMAL and CONTINUOUS/STEP switches are both in the down position.
Load magnetic tape unit 4 with the tape image of the assembled compiler. You can assemble this yourself from [10] or use the tape image in [13]. Place the unit in REMOTE status.
On the Control Console, set the INPUT switch to the KEYBOARD position.
On the Control Console, click the CLEAR button, then the STEP button. The KEYBOARD annunciator on the Console should light.
On your workstation's keyboard, enter 6 0340 40 1000 (without the spaces). This is a magnetic tape instruction to read the three-block loader from unit 4 into memory starting at address 1000. Check your entry in the D register; if you made a mistake, just start over keying the instruction. When finished, press your keyboard's Enter key. The system should execute the read and then halt.
On the Control Console, click CLEAR again, then the CONT button. The KEYBOARD annunciator on the Console should light.
On your workstation's keyboard, enter 6 0000 20 1045 and press the Enter key. This is a branch instruction to the entry point of the loader. The loader should start to execute and read the compiler from the tape. This process takes a little over four minutes.
Once the load has completed, click CLEAR on the Control Console again, then the CONT button again. The KEYBOARD annunciator on the Console should light.
On your workstation's keyboard, enter 6 0000 30 3040 and press the Enter key. This is a block-and-branch instruction to the start of the compiler. The compiler will run briefly to initialize its tables and load the Cardatron format bands, then stop with 44 in the C-register order field, trying the read the first card of the program to be compiled.
Load the card deck to be compiled into Cardatron input unit 1 and press START on that unit. The compiler should start reading cards, and a listing of the program and generated object code should appear on Cardatron output unit 3. The object code output can be suppressed by placing the SKIP switch on the Control Console in the up position. The compiled output code will be punched on Cardatron output unit 2.
If there are no errors, the compiler should halt after processing the program's FINISH$ statement with 5250 in the C-register address field.

This is as far as this version of the compiler can go. If at this point you would press the CONT button on the Control Console to continue past the halt, the system will almost immediately stop again with 44 in the C-register order field, a card-read instruction. What it appears to be trying to do is read an overlay from cards containing a library of standard routines. Alas, we do not have that library.

What the listing Knuth donated to the Computer History Museum appears to represent is the Algol-58 compiler in a fairly late state of development, but not the finished product. It reads cards, parses the source text, and generates what looks to be quite good object code. Without the library, however, it cannot finish its compilation and produce an executable program. This is disappointing, but there is more to the story, as will be revealed below.

The project repository contains a couple of small sample Algol programs, [16] and [18], with corresponding listings produced by this compiler, [17] and [19]. The program and listing in [16] and [17] are the same as the first-compile example above, except that the compile listing in [17] has been annotated to describe the generated instructions and data words. The object code card deck generated by compiling [16] can be viewed in [26].

Running Tom Sawyer's Compiler

It was not difficult to take Tom's transcription of the Burroughs Algebraic Compiler he obtained while at the University of Portland and convert it into the tape-image format used by my retro-205 emulator, then get it to run in that emulator.

The format of that tape image is quite a bit different from the one produced by the MEASY assembler. Tom's tape has a one-block loader on the front, followed by 200 blocks of code for the main compiler, followed by a couple of multi-block overlay segments. All of the object code has had its forward references resolved, so it can be loaded directly to memory and executed. Thus, it loads a lot faster than the tape image produced by MEASY.

To run Tom's compiler in the retro-205 emulator, perform the following steps:

On the Supervisory Panel, make sure the LOCK/NORMAL and CONTINUOUS/STEP switches are both in the down position.
Load magnetic tape unit 5 with the loadable tape image of the compiler available from [8]. Place the unit in REMOTE status.
Load magnetic tape unit 1 with a blank tape. Place the unit in REMOTE status.
On the Control Console, set the INPUT switch to the KEYBOARD position.
On the Control Console, click the CLEAR button, then the STEP button. The KEYBOARD annunciator on the Console should light.
On your workstation's keyboard, enter 6 0150 40 0000 (without the spaces) and press the Enter key. This is a magnetic tape instruction to read the one-block loader from unit 5 into memory starting at address 0000. The system should execute the read and then halt.
On the Control Console, click CLEAR again, then the CONT button. The KEYBOARD annunciator on the Console should light.
On your workstation's keyboard, enter 6 0000 30 0000 and press the Enter key. This is a block-and-branch instruction to the entry point of the loader. The loader should start to execute and read the compiler from the tape, which will only take a few seconds. The loader will then perform a checksum routine over the loaded code and branch to the compiler's entry point. If the checksum is correct, the compiler will initialize and then stop with 44 in the C-register order field, waiting to read the first card of the source deck.
Load the card deck to be compiled into Cardatron input unit 1 and press START on that unit. The compiler should start reading cards, and a listing of the program and generated object code should appear on Cardatron output unit 3. As with the recovered compiler, the object code output can be suppressed by placing the SKIP switch on the Control Console in the up position. The compiled object code will be written to magnetic tape unit 1.

After processing the FINISH$ statement in the source deck, the compiler will read another 22 blocks from magnetic tape unit 5. This appears to be the first overlay of library routines, similar to the one that is missing for the recovered compiler. Tom's compiler then generates additional object code, apparently emitting I/O routines from the overlay, and finally halts with 7570 in the C-register address field. This appears to signal successful end of compilation.

At least this is what happens for a very simple program, such as [16], that does not make use of library functions. The listing generated by Tom's compiler for that program can be viewed in [20]. It generates the same object code as the recovered compiler for this program, but then generates substantially more after loading the 22-block overlay.

When compiling a more complex program, however, such as [18], things do not turn out as well. The compiler processes the source deck without difficulty, then loads the 22-block overlay and generates additional code. Then it appears to attempt to load one or more additional overlays from tape unit 1, eventually stopping at block 260 on tape unit 5 and going into an endless loop, continuously printing the same object code instruction word. The listing for this compilation can be viewed in [21].

The interesting thing here is that the listing from the University of Portland that Tom transcribed did not have 260 blocks of data, only 230. The remaining blocks would be whatever was on the tape image after block 230, which in my case was words of all zeroes. Tom has confirmed that he had transcribed the entire listing, and after some research has concluded that his listing does not represent the entire tape. The looping behavior when compiling [18] is almost certainly a result of trying to execute the incomplete second overlay.

In sum, we have two versions of the Algol-58 compiler for the 205 that both appear to work, but due to missing or incomplete libraries, cannot generate fully executable programs.

Comparing the Two Compilers

With both compilers working, albeit unable to generate complete programs, the next task was to determine whether and how they are related. To do so, I decided to compare the object code generated by MEASY for the recovered compiler against the first 200 blocks of Tom Sawyer's transcribed tape dump. This represents just the main segment of the compiler, sans overlays, which the recovered compiler did not have.

The tape images for the two compilers have both different formats and different address sequences. Thus the first step was to convert both to a common format and sequence so they could be compared. The code for Tom's compiler is a straightforward memory image, with the words in memory-address sequence and all operand addresses in their final form. The code produced by MEASY consists of two-word pairs, with the first word containing address and forward-reference linkage, and the second word containing the assembled value. See [3] for more information on the format of the tape produced by MEASY. Addresses are in the same sequence as the source code for the compiler.

Preparation of the code for Tom's compiler was simple, as it was already in memory-address order with all addresses resolved. I simply discarded the one-block loader on the front of the tape image, along with the blocks for the overlays at the end of the image. Then I reformatted the remainder to create a text file with one word per line.

Preparation of the code for the recovered compiler was a little more work. Rather than try to fix up the forward-reference linkages and reorder the code myself, I simply cleared the 205's memory and loaded the MEASY object code tape as if I were going to run the compiler. That way, MEASY's loader resolved the forward references and placed the code in memory-address sequence for me. Then I manually entered two 100-block tape write instructions on the Control Console to write all 4000 words of main memory to a blank tape. I unloaded that tape, capturing its image as a text file. Finally, I reformatted that text file so that it also had one word per line.

These steps resulted in two text files of object code having the same format and address sequence. To both files I inserted four-digit numbers in front of each word that indicate their memory addresses. I then compared the two files using a Windows GUI diffing program (Compare It 4.2, http://www.grigsoft.com). The result of that comparison can be viewed in [22]. Note the following about this comparison:

The object code for the recovered compiler generated by MEASY is on the left; the object code from Tom Sawyer's transcription is on the right.
Sequences of lines that do not match (having a light green background) are surrounded by up to five matching lines (having a white background) on either end.
Sequences of more than 10 contiguous matching lines are not shown. Such longer sequences of matching lines are replaced by a horizontal line.

While there are numerous mismatches between these two files, there are also large runs where words at the same addresses match exactly -- 571 words starting at 0438, 481 words starting at 1010, and the big kahuna, 982 lines starting at line 1492 (almost 25% of the program). In total, 3722 of the object code words at the same addresses had the same value -- 93% of the program.

This degree of correspondence between the two sets of object code makes it clear that they represent the same compiler, but at different levels of development. The recovered compiler is obviously the earlier and less-complete one. Tom's compiler appears to be a production release.

Tom has analyzed the differences and reported to me that most of the changes appear to be related to initialization of the compiler and to input/output routines. In particular, his version:

Prints a heading line on the 407 at the beginning of compilation. This heading has the date "June 24, 1961."
Supports the use of magnetic tape for the compiled object code. The recovered compiler supports only punched cards and paper tape.
Supports loading the subroutine libraries from magnetic tape instead of cards.
When loading from magnetic tape, the loader computes a checksum of the main program segment. The compiler's initialization code will generate an error message if the checksum is incorrect.

There are no doubt other enhancements and corrections between the two versions that we have not yet uncovered.

Where Do We Go From Here?

It would be nice to get Tom's compiler to the point that it could generate complete, executable programs. Doing so, however, would be a lot like trying to restore a '57 Chevy that has a gutted passenger compartment -- it sort of runs, but you can't go anywhere in it. Significant parts are not available and will need to be recreated from scratch. Unlike a Chevy, though, we do not have any idea what those missing parts were like, other than that they appear to be library routines. They would need to be constructed from their apparent function and the interfaces to them generated by the compiler. What we would end up with would be not so much a reconstruction as a reinvention of those libraries. It is not clear to me this is worth attempting.

A much more achievable goal would be to reverse-engineer Tom's object-code transcription back into source code. Since 93% of the two compilers are identical, 93% of that job is already completed, and Tom's partial disassembly covers portions of the remainder. This would give us complete source code for the finished compiler (less the libraries, of course), and would make it easier to study the changes that took place between the time Knuth's listing was generated and the version that became Tom's tape image was released.

Another goal could be to disassemble as much of the library overlays as we have. This would allow us to understand better how they work and how the compiler uses the libraries. Tom has already done pieces of this during his analysis.

I have not attempted the same type of detailed analysis of the compiler's operation that I did for the EASY assembler [3], but Knuth had already done something similar. Among the papers he donated to the Computer History Museum is a document titled "The Internals of Algol 205" [24]. This describes the inner workings of the compiler at a fairly detailed level, and links that description to flowcharts of the control logic.

In summary, while Tom and I are disappointed that neither of our versions of the Algol-58 compiler are sufficiently complete to produce executable programs, we are both quite satisfied with the degree to which we have been able to reconstruct them and get them to work. Both versions appear to work quite well, given the limits of the source materials we had to start with.

Thus, I am happy to say that I consider this goal of the retro-205 project to have been met.

References

Sunday, August 16, 2015

Magnetic Tape for the retro-205 Emulator

Nothing in the popular concept of computing during the 1950s and 1960s is more iconic than that of a computer room with a line of tall magnetic tape drives, their reels jerking clockwise and counter-clockwise, or spinning rapidly in rewind. Tape has changed a lot over the intervening decades, increasing dramatically in capacity, speed, and reliability, but is now relegated almost entirely to a role as a backup medium. Prior to the widespread availability of inexpensive disk storage, however, tape was mass storage, and a large number of computer applications were designed around its capabilities and limitations.

This is Paul Kimpel again, with another update on the retro-205 emulator. Emulator version 0.05 was released on 15 August and is available from the hosting site at http://www.phkimpel.us/ElectroData/205/webUI/D205.html. The open-source project is hosted on GitHub at https://github.com/pkimpel/retro-205/.

The main feature of this new release is implementation of magnetic tape for the 205. Magnetic tape is required for both Knuth's MEASY assembler and Algol-58 compiler, so completion of this feature has been necessary in order to proceed with reconstruction of those two pieces of software.

Overview of 205 Magnetic Tape

The concept of magnetic storage was originally developed by Vladimir Poulsen of Denmark in 1899. Magnetic tape was derived from magnetic wire recording, both developed by the Germans during the 1920s and 1930s. In the early 1950s, audio recording techniques were extended to magnetic tape video recording, to support the burgeoning television industry. Magnetic tape for data storage started to appear about the same time.

ElectroData was an early pioneer in developing magnetic tape for data storage, producing a design for the Stanford Research Institute's ERMA project in the early 1950s. ERMA was a highly-successful attempt to automate customer checking account operations for Bank of America, producing, among other things, Magnetic Ink Character Recognition and the high-speed reading and sorting of checking account drafts. The ElectroData tape units were used in the prototype computer system SRI built for ERMA, but design and implementation of the production systems was awarded to General Electric, who never quite managed to turn that golden opportunity into a successful computer systems business.

By the time ElectroData had come out with the Datatron model 203 computer, several of their larger customers, particularly those in the insurance business, encouraged ElectroData to develop magnetic tape capability for the system. The result was the Datatron 204, which was a 203 with additional circuitry to support magnetic tape operations.

Initially, magnetic tape support included a Model 543 Tape Control Unit and Model 544 Tape Storage Units (or "DataReaders"). Later, this was extended to include the Model 560 DataFile, which although implemented using magnetic tape technology, actually behaved more like a very slow disk unit. The Tape Control Unit could support up to 10 DataReader and DataFile units in any combination.

Physical and Recording Characteristics

The DataReader was a transport of the open-reel type. It used a 0.75-inch wide tape with a plastic base, wound on metal reels. Each reel could hold up to 2500 feet of tape. Data was recorded in six tracks -- four data tracks encoded as BCD digits, an even-parity track, and a control track that indicated the start of a block. The tape physically supported 12 tracks, however, so data was recorded in two "lanes" along the length of the tape. The 205's tape-search instruction (MTS, 42) provided the ability to switch between lanes; read and write instructions operated on only the currently-selected lane.

Data was recorded on the tape in fixed, 20-word blocks. A full reel of tape could store 10,000 of these blocks. Each word in a block consisted of 11 data digits (including sign) plus a spacer digit -- the same format as on the memory drum. The tape moved at 60 inches/second, recording at 100 bits/inch. In addition to data words, each block had a header that contained the address of that block, numbered 0-9999. A block on tape required 2.4 inches for data, 0.08 inch for the header, and 0.3 inch for an inter-block gap, for a total of 2.78 inches. Read time was 46 ms per block, plus 6 ms start time to bring the tape up to speed at the start of an operation.

The Tape Control Unit supported reading or writing up to 100 blocks with a single instruction. The fixed-size, 20-word block format allowed a drive to overwrite existing blocks on a tape, something that was not practical with the variable-length block scheme of IBM tape drives that later became the de facto standard.

Based on the block numbers recorded in the block headers, the Tape Control Unit could search forward or backward for a specified block number in a specified lane. Standard read and write operations tied up the Processor for their duration, but tape search proceeded independently and asynchronously of the Processor.

Only one read, write, or search operation could take place at a time, although multiple drives could be rewinding simultaneously. Attempting to initiate a read, write, or search while another search was in progress, or to initiate an operation against a drive that was not ready or in rewind, set the overflow toggle in the Processor to indicate the requested operation could not be performed. Programs were required to test for this condition after a tape operation, the same as for any other operation that sets overflow.

Conditioning Tapes

To support block search and overwrite, tapes needed to be formatted, or "conditioned" before use. Conditioning was performed off-line by the Tape Control Unit in concert with one of the drives. The Processor could not use the tape subsystem while conditioning was taking place.

Conditioning worked by first driving the tape forward and writing a constant magnetic pattern on it. When the end of the tape was reached (indicated by a perforated section of tape), the tape reversed direction, and the Tape Control Unit read back the constant pattern, looking for flawed areas on the tape. When an unflawed section long enough to hold a block was detected, the Control Unit wrote a block header with the appropriate block number in it. This process continued until the block number counted down to zero or the beginning of the tape was reached. Only one lane at a time could be conditioned -- the entire process had to be repeated to condition the other lane. Once conditioned, a tape could be written upon and reused any number of times.

The 205 Operating Procedures manual contains a good description of the DataReader and Control Unit, along with descriptions of the steps necessary to load, unload, and condition tapes.

The retro-205 emulator does not require conditioning of tape images, thus does not implement the manual conditioning features of the Tape Control Unit.

Tape Data Transfer and Buffering

The speed of data transfer to and from tape was a real problem for the 205. At 100 digits/inch and 60 inches/second, a word was transferred every two milliseconds to or from the tape drive. The high-speed loops on the memory drum (with a maximum access time of 1.68ms) were fast enough to handle this data rate, but main memory (with a maximum access time of 16.8ms) was not. Obviously, some sort of buffering was needed, and it had to handle I/O operations up to 100 blocks in length.

Discounting the 6ms startup time for tape motion, a 20-word block could be read or written in 46ms. That is a lot longer than the 16.8ms required for a main memory access, but 20 consecutive main-memory accesses would require 336ms. The Block-to-Loop and Block-from-Loop instructions, however, can transfer 20 words to or from main memory and a high-speed loop in a maximum of 1.1 drum revolutions, or about 18.5ms.

Thus, the designers of the magnetic tape subsystem decided to use the high-speed loops as buffers between the tape and main memory and use the existing blocking mechanism to rapidly transfer data between main memory and the loop buffers. Two buffers were needed, so that one could be transferring a block of data to or from the tape, while the other one could be transferring another block from or to main memory.

The designers chose to use the 4000 and 5000 loops for these buffers, in such a way that data transfer always ended with the 4000 loop. Thus if a even number of blocks were to be transferred, the transfer began with the 5000 loop; if an odd number were to be transferred, it began with the 4000 loop.

During a read operation, one buffer would be filling a block from tape while the other buffer was transferring the previous block to main memory. During a write, one buffer would be sending a block to tape while the other buffer was loading the next block from main memory. The buffers would switch roles at the end of each block, alternating between servicing main memory and servicing the tape drive.

As a special case, tape instructions that used a main memory address of 8000 or higher read or stored data the 4000 and 5000 loops directly, and did not transfer data to or from main memory.

Magnetic Tape Instructions

The Datatron 205 Processor supports four instructions that operate on magnetic tape:

0 nnup 40 aaaa: read nn blocks into address aaaa
0 nnup 50 aaaa: write nn blocks from address aaaa
0 llup 42 bbbb: search on lane ll for block bbbb
0 xxup 52 xxxx: rewind unit u

where:

aaaa is the memory address at which data transfer into or out of main memory will begin. If the address is 8000 or greater, then data transfer will take place directly to or from the 4000 and 5000 loops and main memory will not be accessed. It is not possible to read or write directly to the 6000 and 7000 loop addresses.
bbbb is the zero-relative block address sought by a search command. The system will automatically determine whether a forward or backward search is necessary.
ll is the lane number on which to search. On a DataReader unit, which supports only two lanes, only the low-order bit of this value is relevant. DataFile units have 100 lanes, so two full digits are required for a lane number on those drives.
nn is the number of consecutive blocks to read or write. A value of 00 indicates 100 blocks.
p is the standard breakpoint digit in 205 instructions.
u is the logical unit number to which the operation will be directed. Each drive has a selector switch on its panel that designated the unit number to which it will respond.
x indicates digits in an instruction word that are ignored.

Note that the lane can be selected only by a search command. Thereafter, read and write instructions will use the last lane selected. Also note that based on the value of the sign digit, the low-order four digits of each instruction word could be modified by the contents of the B register in the usual manner.

Magnetic Tape User Interface

This section describes the user interface for the Control Unit and DataReader as presently implemented in the retro-205 emulator. The DataFile has not yet been implemented in the emulator.

Release 0.05 of the emulator supports three tape drives, identified as MTA, MTD, and MTE. A facility to control the number and kind of peripheral devices on the system is planned for a future release.

Magnetic Tape Control Unit

The Control Unit is the interface between the drives and the 205 Processor and memory. It controlled all tape operations except rewind, which was handled locally by the drive. Since there was only one Control Unit per system, there could be only one tape operation (except rewind) active at a time.

In the emulator, the Control Unit has a small window with a number of lamps, two buttons, and a toggle switch.

Magnetic Tape Control Unit

The physical Control Unit had two additional panels on either end, plus additional buttons and switches, as can be seen from Figure 9-3 in the 205 Operating Procedures manual. The lamps on the two additional panels reflected the status of circuits involved with physical recording on tape, parity generation and checking, and maintenance of the unit. The additional switches and buttons dealt with manipulation of the T register and manual calibration of tapes. None of these have any meaning in the context of the emulator, and thus have been omitted. Of the remaining panels:

The two columns of lamps comprising the BZ register in the left-most panel indicate the currently-selected lane for the currently-selected tape unit. The lane is a decimal number displayed in BCD. For DataReader units, which have only two lanes, only the bottom lamp in the second column is relevant. DataFile units have up to 100 lanes, so both columns of lamps are used with those drives.
The column of lamps comprising the Z register in the left-most panel indicates the currently selected tape unit. The unit number is also displayed in BCD. A value of zero indicates unit number 10.
The four-digit T register in the center panel is used for two purposes:

During search operations, the T register holds the BCD representation of the target block number. Once the desired block is located on the tape, the contents of the T register will be rotated one digit to the right.
During read and write operations, the low-order digit position holds the selected unit number. The next two digits hold the number of blocks to be read or written -- these digits will be counted down as blocks are read or written. The high-order digit will always be zero during read or write operations.

The right-most panel holds three columns of five lamps, but only four of these lamps are used by the emulator; the remaining lamps were for maintenance purposes:

The S lamp indicates a search operation is in progress.
The R lamp indicates a write (record) operation is in progress.
The B lamp indicates backward tape motion.
The F lamp indicates forward tape motion.

The CLEAR button clears the internal state of the Control Unit, including all of the lamps on the panels. This button should seldom be needed in the emulator.

The NORMAL/SUPPRESS B switch controls how sign digits of incoming words are interpreted during read operations. In the NORMAL position, sign digits with the second (2) bit set will cause the current value of the Processor's B register to be added to the word before it is stored in memory. The 2-bit is also reset before the resulting word is stored. In the SUPPRESS B position, no action is taken based on the value of the sign digits, and they are stored with their words as-is. SUPPRESS B is normally used when loading programs from tape, to prevent altering the sign digits in words for Cardatron format bands. For normal operations, this switch should be left in the **SUPPRESS B** position.

The DISABLE button stopped all tape movement as long as it was depressed. This could be used, for example, to interrupt a search for a non-existent block. When this button is clicked in the emulator, it aborts the current tape read, write, or search operation. It has no effect on tape rewind.

Magnetic Tape Storage Unit (DataReader)

The DataReader handles open-reel tapes. In the emulator, these units are physically labeled MTA through MTJ. Each unit has a separate window in the browser:

Tape Storage Unit (DataReader)

The POWER lamp, STOP REWIND button, and the ON/OFF and FORWARD/OFF/REVERSE toggle switches from the physical DataReader have been eliminated, as they have no function in the emulator. Two new buttons have been added to enable loading and unloading of tape images in the emulator version of the drive.

The DESIGNATED lamp lights when this unit is currently selected for a tape operation. Except for rewind, it remains lit while the operation is in progress.

Clicking the REWIND button while the unit has a tape mounted and is in local status will rewind the tape to its load point (BOT). The button is inactive when no tape is loaded or the unit is in remote status.

The pull-down DESIGNATE list determines the logical unit number of the drive. This is the unit number that tape instructions in the Processor reference. No two drives should have the same logical number at the same time. If two or more drives are assigned the same number simultaneously, tape operations against that unit number will act as if the unit is not ready. ~~Unit numbers are initially assigned based on the drive's physical identifier, A=1, B=2, etc.~~ [Update 2017-04-15] Unit numbers and switch settings except for the REMOTE/LOCAL switch are now persisted in the system configuration.

The REMOTE/LOCAL switch controls the status of the drive. If a tape is mounted, placing this switch in the REMOTE position will place the drive in remote status and make it ready; otherwise it is in local status and not-ready. Tape operations against a not-ready unit will result in the Processor's Overflow toggle being set.

The NOT READY lamp indicates the remote (ready) or local (not-ready) status of the drive.

The REWIND-READY/REWIND-NOT READY switch determines the status of the drive after a rewind operation completes. In the REWIND-READY position, the drive will be placed in remote (ready) status after rewind completes, provided the LOCAL/REMOTE switch is in the REMOTE position. Otherwise, the drive will be in local (not-ready) status after a rewind.

The NOT WRITE lamp will be lit when the NOT WRITE/WRITE switch is in the NOT WRITE position. This indicates any tape that is loaded is write-protected.

The NOT WRITE/WRITE switch controls whether a tape can be written upon by the drive. In the NOT WRITE position, the NOT WRITE lamp illuminates and the tape is write-protected. Write operations will cause the tape to move the designated number of blocks, but data on the tape will not be overwritten.

The progress meter at the bottom of the window shows the relative amount of tape left on the supply reel. As the tape moves forward, the meter bar will diminish towards the left; as the tape moves backward, the bar will increase towards the right

Above the progress meter is the name of the tape image file currently loaded into the drive, if any. If a blank tape has been loaded, this will read simply "(blank tape)".

Loading and Unloading Tape Image Files

The LOAD button is used to mount a reel of tape, in the form of a tape-image file, into the DataReader. This button is active only when no tape is loaded to the drive. Clicking this button will open a tape-loader dialog box:

Tape Loader Dialog Window

To load a blank tape into the drive, simply click the OK button. To load an existing tape-image file, use the file picker on the window to select the file, then click the OK button. All tape images are treated as if their reels had been calibrated to hold 10,000 blocks (numbered 0-9999). Blank tapes are implicitly calibrated. The emulator does not support manual calibration of tapes, nor tapes containing other than 10,000 blocks.

When a tape is loaded into the drive, a small tape-reel icon will display on the right side of the tape drive window. This icon will rotate as tape commands move the tape in the drive. Below the icon are a set of orange annunciators that indicate the status of the tape image:

UNLOADED: no tape is mounted in the drive.
AT BOT: a tape is loaded and is positioned at the tape's load point.
AT EOT: the tape is now positioned at physical end-of-tape. No further forward motion is possible. Either a backward search command must be executed, or a manual or programmatic rewind must be done.
REWINDING: the tape is currently rewinding.

The UNLOAD button dismounts a tape from the drive. This button is inactive unless a tape is mounted, the drive is in local (not-ready) status, and the tape is positioned at its load point (BOT).

If the tape has been written upon while it has been mounted, clicking this button will display a dialog box asking if you want to save the tape image data. If you respond by clicking the dialog's OK button, the emulator will render the contents of the tape as lines of ASCII text and display them in a new, temporary window. You may save the contents of this window to your local file system, or copy/paste the data into another program. When you are finished with the window, simply close it.

Format of Tape Image Files

Tape images are maintained externally as simple ASCII text files. Lines in the file may be delimited by carriage-return followed by line-feed, carriage-return only, or line-feed only. Empty lines (those containing no characters or only spaces) are ignored. Each non-empty line of text in the file represents two blocks, one in each lane. Words in the blocks are represented as hexadecimal numbers with BCD encoding, which you can think of simply as decimal numbers. Words within a block are delimited by commas.

The first 40 comma-delimited numbers on a line will be converted to the tape drive's internal format. The first 20 words will become the contents of lane 0; the second 20 words will become the contents of lane 1. If a line contains fewer than 40 numbers, it will be implicitly extended to 40 with zeroes. If a line contains more than 40 numbers, those after 40 will be ignored. Two adjacent commas imply a zero word between them. Spaces before or after the text between commas are ignored.

When loading an existing tape image file, parsing of the lines in the file proceeds as follows:

Each line is extracted in turn from the file. If the line is empty, it is ignored and the load proceeds to the next line of the file.
The text of the line is separated into individual strings of text at the point they are delimited by commas.
Any leading or trailing spaces in each string are discarded.
Each resulting string is converted to a numeric value by the Javascript parseInt(...,16) function. This function will convert any leading hexadecimal characters (0-9, A-F) to internal numeric form. The number may optionally be prefixed by a hyphen ("-") to indicate it is negative. Any trailing, non-hexadecimal characters in the string are ignored.
Each converted number is reduced to 11 hexadecimal digits by discarding any higher-order digits. If the number was prefixed by a hyphen, the low-order bit of the sign (11th) digit is set to one. Negative values may be indicated either by preceding the number with a hyphen, or setting the low-order bit of the 11th (highest order) digit to one, or both.

If a tape-image file contains fewer than 10,000 non-empty lines, the emulator will extend the drive's internal tape image to 10,000 blocks when it is loaded by appending blocks of zero words in each lane. If a file contains more than 10,000 lines, the extraneous blocks are ignored. A blank tape image initially consists entirely of blocks of zero words.

When unloading a tape image, the emulator will trim all blocks consisting entirely of zero words from the end of the tape-image text it creates. It will also trim zero words from the end of each line. If the blocks from both lanes are entirely zero, the unloaded image will have only a single comma rendered on that line. These trimming actions minimize the amount of redundant text in the resulting tape image file.

This format has been designed to create and maintain tape image files with a simple text editor. Most spreadsheet programs will read and write comma-delimited text files, so they can be used as well to view and edit tape image files. Note that if a block in lane 1 is non-zero, the corresponding block in lane 0 must be padded as necessary in the image file out to a full 20 words.

Other Changes and Enhancements in Release 0.05

In addition to the implementation of magnetic tape, this release contains the following enhancements and corrections:

Addition and subtraction of words having signs other than zero or one now works properly.
The algorithm that compensates for timer deviation in the setCallback() mechanism has been significantly improved. In addition, separate timing categories have been established for main memory and the high-speed loops.
The handling of blocking instructions for the high-speed loops has been changed to accommodate the way they worked on systems with magnetic tape. In addition, BTn instructions with an operand address of 8000 or greater will now clear the designated loop to zeroes instead of transferring words from the mod-4000 congruent address.
The INPUT SETUP and GENERAL CLEAR buttons have been implemented on the Cardatron Control Unit. GENERAL CLEAR functions the same as the CLEAR buttons on the Control Console and Supervisory Panel. INPUT SETUP presets the Processor registers to execute a card-read instruction for input unit 1 when the Processor is next started or stepped.
Unit numbers for Cardatron output units have changed: the card punch is unit 1 and the line printer is unit 3. These are the unit numbers required by MEASY and the Algol-58 compiler.
On the text panes for Cardatron output units, double-clicking anywhere in the text area will now open a new, temporary window, copy the text from the pane to that new window, and clear the text in the pane. This is an additional method to save line printer or card punch output, and is consistent with the method used on the Flexowriter and paper-tape punch.
The overly-generic END OF SUPPLY and RUNOUT SUPPLY button captions on Cardatron output units have been changed to reflect "paper" for line printers and "cards" for card punch devices.
The ALGOL GLYPHS option on Cardatron output units now works properly.
The large, round knobs on the Control Console and Supervisiory Panel now work differently. Previously, when a knob that was in its last position was clicked, it would jump to its first position. Now, the knob reverses direction, and subsequent clicks move it in that reverse direction. This is more in keeping with how real knobs work.
The Supervisory Panel window is now opened last, to avoid timing problems with the opening of the Cardatron and magnetic tape unit windows.
The ability for the emulator to run off-line in the browser's "application cache" has been reinstated.
Minor changes to the home window were made to accommodate the project's move from Google Code to the GitHub hosting service.

Future plans for the emulator include implementation of the magnetic-tape DataFile unit and a configuration facility to allow users to customize the number and kind of peripheral devices for their 205 emulator.

Saturday, August 8, 2015

Knuth's EASY Assembler

It is difficult to appreciate today, but there was a time when compilers were unheard of and assemblers were held in suspicion. In the late-1940s and early/mid-1950s, Real Programmers wrote raw, seething machine code. At first they did this because assemblers did not yet exist, but later because, well, they were Real Programmers, and things like mnemonic operator codes, symbolic addresses, resolution of forward references, and ease of modification were for sissies.

This is Paul Kimpel again, with an update on the retro-205 emulator and progress towards reconstruction of Donald Knuth's Algol-58 compiler for the ElectroData/Burroughs Datatron 205. This post focuses on the assemblers for the 205 he wrote to develop that compiler.

Origin of the EASY Assembler

In 1960, Knuth contracted with Burroughs Corporation in Pasadena, California, to write an Algol compiler for the 205. The specification for Algol 60 had not yet been published, so this compiler was to be for the preliminary version of the language, known as Algol-58.

The work was to be done that summer, between the time of Knuth's graduation from Case Institute of Technology (now Case Western Reserve University) in Cleveland, Ohio, and his start of graduate studies at the California Institute of Technology in Pasadena. Knuth discusses the project briefly in his Oral History for the Computer History Museum. The transcript from the 1985 Burroughs B5000 Conference, as well as Richard Waychoff's Stories of the B5000... memoir, also mention the project.

At that point in time, compilers had to be written in assembly language, although the B5000 project was to turn that notion on its head just a year or so later. Burroughs supported an assembler for the 205, named "STAR 0". There was also the "Shell" assembler developed by Shell Research. For reasons that are not clear, Knuth decided to use neither of these, and instead to write his own assembler for the 205, calling it EASY, the "Elegant Assembly System for the 205."

In notes for a later variant of this assembler, MEASY (described later in this post), Knuth indicated that the "elegant" in the title should be taken in its mathematical connotation of "short and sweet." Indeed, EASY is short -- the entire program is only 569 lines, of which more than half represent the constant data to initialize the symbol table and Cardatron format bands. The executing code, including the run-time loader the assembler emits, is little more than 250 instructions.

Reconstructing the Algol-58 compiler is a major goal of this project, but in order to do that, we first needed to reconstruct either EASY or MEASY. Eventually I did both of them. I am presently using MEASY for the compiler, but MEASY requires a tape drive. Magnetic tape has only recently been implemented in the retro-205 emulator, and as I write this, has not yet been officially released. When I started working on the assemblers back in March of this year, all I had working were card and paper tape devices. EASY is a card-based assembler, so I started with it, and later used EASY to bootstrap MEASY.

Using EASY

EASY is easy to use. You place its load deck in the reader followed by the source deck to be assembled, press the INPUT SETUP button on the Cardatron Control Unit to initialize the processor to load from cards, press START on the reader, and then either START on the Supervisory Console or CONT on the Control Console. Assembly terminates when EASY senses an END pseudo-instruction in the card deck.

EASY reads its source from cards and punches its output to cards. It does not generate a printed listing. The 205's Cardatron subsystem controls the card equipment, which was typically an IBM 089 collator for input and IBM 523 punch for output. As described in an earlier post, the Cardatron requires a numeric punch in a selected column of each card to specify the format band under which the card will be interpreted. The format band determines how columns from the card will be translated into decimal words before being sent to the 205 memory drum. Thus, EASY requires a "1" punch in the first column of each of its source cards to select input format band 1. That format band is part of the assembler object code, and is loaded to the Cardatron by EASY during its initialization.

Interestingly, each input card generates one output card. The left side of an output card holds the original source text; the right side holds the generated object code. EASY copies the "1" punch into the first column of the output card, but also places a "6" punch in the second column. Format band 6 is hard-wired in the Cardatron. It is used to load all-numeric data, and in particular, object code. Therefore, by changing the setting in the Cardatron Input Unit to select format from column 1, you read the output deck back in as source for another assembly. By changing the format selection to column 2, you load the object code from the deck to run the program. Sweet.

The numeric word in columns 70-80 of an output card is the assembled word to be loaded into memory. The numeric word in columns 59-69 is a card read instruction with a sign digit of 6. The Cardatron reads data backwards from the end of the card, thus under format band 6, the word in columns 70-80 is read first and stored at the effective memory address for the current card-read instruction. Since the second word read from columns 59-60 has a sign of 6, it is interpreted as an instruction to be executed rather than data to be stored. That sign value terminates the data transfer from the current card (ignoring the remainder of the card) and executes the new card-read instruction to read the next card into the effective address of that instruction.

Thus, when reading the output deck under format band 6, each card bootstraps the next one and specifies the address at which the object word on the next card will be loaded. Programs generally begin with a START pseudo-operator to specify the initial assembly address. Since a START operator does not generate a word of object code, the output card for it has the bootstrapping card-read instruction for the next card in columns 70-80, serving to set the address for the word to be read from the next card. Hence, it does not matter what address is used for the initial card-read instruction to load the deck -- the executable instructions embedded in the deck will relocate to the correct address automatically.

For a more detailed example of how loading code with format band 6 works, see this description of a short card-load program that clears the 205 memory drum.

Programming with EASY

Traditionally, assembly languages specify one computer instruction per line. Most assemblers require at least three fields on each line:

A field for a symbolic label. This symbol becomes defined as the memory address at which that line is assembled.
A field for an operation code. This holds a mnemonic for the type of instruction or data on that line. Many assemblers also have pseudo-instructions to control operation of the assembler. Lines with pseudo-instructions generally do not generate object code.
A field for the operand address or addresses used by the instruction. Usually this references the symbolic label for some other line in the program. A major task of an assembler is to assign addresses to these symbolic labels as they are defined in the first column of lines in the program, and to apply those addresses to the operand fields of other lines where the labels are referenced. Most assemblers also support some sort of "address arithmetic" for the operand addresses, e.g., specifying an address so many locations before or after that for a symbolic label.
Any remaining text on the line after the operand(s) is generally ignored, and considered to be a comment.

EASY follows this general idea, but uses more columns to simplify the parsing and processing of instructions. In particular, the specification of operand addresses is spread across four fields, as discussed below. With the exception of the START and END pseudo-instructions, each line of input generates one word of assembled object code. There is no provision for "comment lines" as with most assemblers.

Input cards to EASY must have the following format:

1 10 20 30 40 50 60
.........|.........|.........|.........|.........|.........|
1 P LLLLL SCCCCIIAAAA OOOOO YYYYY PP T XXXXXXXXXXXXXXX

Column 1: must contain a "1" to satisfy the Cardatron's requirement for format band selection.

Column 5: Program-point label: Program points can be thought of as local, reusable labels. Programs typically have numerous references to nearby locations, especially in branch instructions to implement control flow. These locations are often referenced only once or twice, so rather than require a globally-unique symbol for each of these briefly-used references, program points provide short labels the programmer can reuse multiple times throughout a program, but in different local scopes. EASY provides nine program-point symbols, 1-9. Placing one of these in column 5 labels that line with that program point. Other lines can then refer to the nearest program point before or after their location, but only the nearest one -- see the discussion for columns 37-38 below. Once a program-point label is reused, earlier definitions of it fall out of scope.

A number of assembly languages for Burroughs machines supported program-point labels. I first encountered them in the assembler for the B3500, and always wondered where they originated. In researching the Shell assembler, I found this footnote in its reference manual:¹

The idea of the program point address is apparently that of Melvin Conway of the Case Institute of Technology. It was incorporated into SOAP III, an assembler for the IBM 650, by Donald E. Knuth, also of Case Institute. See Case Institute Report 1005.

This explains why program points were in EASY, but also note that the Shell assembler predated EASY by at least two years.

Columns 7-11: Symbolic location label: the traditional label field for an assembly line. Labels defined in this field must be unique within the program. Labels are limited to five characters, since the 205 stored five alphanumeric characters per word.

Columns 13-23: Numeric word: this field can be used for several purposes, including specifying literal values, relative addresses, and additional digits in instruction words. The exact effect depends on what is specified in other fields on the line. To understand this, the 11-digit 205 instruction word can be thought of as containing four sub-fields: SCCCCIIAAAA, where S is the sign digit, CCCC are the so-called "control digits" used to specify breakpoints and by some I/O instructions for unit selection and control, II is the two-digit operation code, and AAAA is the operand address. Any values in these sub-fields on the card become the default values in corresponding fields of the assembled word, with blanks being interpreted as zeroes. The operation code (II) and operand address (AAAA) fields can be modified by other fields on the line, as discussed in the following.

Columns 25-29: Symbolic operation code: If this field is non-blank, the value of the symbol in that field, modulo 100, replaces the II digits (columns 18-19) in the assembled instruction word. The symbol table in EASY is initialized with a set of operation mnemonics and their corresponding numeric codes. Knuth chose a set of mnemonics somewhat different from those used by other 205 assemblers, apparently to be consistent with the assembler mnemonics for the Burroughs 220, a later machine with a very similar architecture:

EASY & MEASY Assembler Operation Codes

In addition, there are two pseudo-operators, START, the operand address for which specifies the next location at which instructions will be assembled, and END, which indicates the end of the program. The operand address for END specifies the location at which the loader routine will be placed during program load.

Columns 31-35: Symbolic operand address: If this field is non-blank, it modifies the operand address digits (AAAA, columns 20-23, which are most often blank or zero), in the following ways:

If the symbolic label has been previously defined (i.e., its address is already known), that address is added to the value for AAAA, modulo 10,000. This is a way to address a location relative to that of a symbolic label. To address relatively in a negative direction, the value in AAAA must be the 10s-complement of the desired relative offset (e.g., 9999 equates to -1).
If the symbolic label has not been previously defined (i.e., it's a forward reference), the value in AAAA is replaced by a link to any previous instructions referencing the same forward label. The reason for this forward-reference linkage is that EASY is a one-pass assembler. It does not resolve forward references at assembly time. Instead, such references are linked backwards through the address fields of all those instructions referencing a given forward address, with a zero address terminating the chain. At the end of the assembly, EASY emits a short loader routine and a table of head addresses for the forward-reference chains. Using this table, the loader works backward through the forward-reference chains and resolves the forward references each time the program is loaded.

Columns 37-38: Program-point address: This field is ignored if the symbolic operand address in columns 31-35 is non-blank. Otherwise, the first column in this field is interpreted as a numeric digit, and the second column indicates how that digit will modify the value of AAAA (which again is most often zero), thus:

n+: The current location address plus n words is added to the value in AAAA, modulo 10,000.
n-: The current location address minus n words is added to the value in AAAA, modulo 10,000.
nB: The location address of the immediately-prior program-point label n is added to the value in AAAA, modulo 10,000.
nF: The location address of the immediately-next program-point label n will eventually replace AAAA when it is resolved by the loader, as described above for forward symbolic operand addresses.

Column 40: High-speed loop tag: This column, if non-blank, must be in the range 4-7. When present, this digit eventually replaces the high-order digit in the address that is finally resolved into the AAAA field, causing that address to reference a location in one of the four, 20-word, high-speed loops on the 205 memory drum. A common 205 coding practice was to assemble instructions into locations in main memory and then transfer them using one of the "blocking" instructions to a high-speed loop for execution, where they would run almost ten times faster. Use of the loop tag allows instructions to be coded as if they were going to run from main memory, but the tag modifies the operand address to be relative to the loop where the code will actually run.

Columns 42-56: Remarks: These columns are ignored by the assembler, and can be used for comments.

Columns 59-80: Loadable code: These columns are ignored by the assembler on input cards. On output cards, they hold the assembled object word and card-read instruction for loading the assembled program into memory, as described earlier.

Any data on the card in columns other than the ones cited above is dropped by the Cardatron and never even reaches the 205 memory.

The following snippet of code from EASY (starting at line 183 in the source) illustrates most of the features described above:

1                  4000 START
1     TABLE             STC   HOLD       SYMBOL TABLE
1                       CAD         4F   SEARCH ROUTINE.
1                     4 SLT
1                       STA   EXIT       STORE EXIT.
1                       CAD   HOLD       GENERATE
1                       MUL   10101      STARTING
1                       STC   TEMP       PLACE, AND
1                     3 SLT              SEARCH FOR
1                       STA   TEMP       EMPTY OR
1                       LDB   TEMP       UNUSED PLACE
1   1       1      1900 CAD
1                       CNZ         2F
1                       CAD   HOLD       NOT IN TABLE
1     EXIT
1     10101 1 1 1001
1   3                   CAD   EXIT       IF SYMBOL IN
1                       ADD   TWO        TABLE, ADD 2
1                       STA   TEMP       TO EXIT LINE
1           1      2900 CAD              AND DISPLAY
1     TEMP                               EQUIVALENT

Reconstructing EASY

Fortunately, a listing of the EASY assembler survives in the papers Knuth donated to the Computer History Museum in 2005. Brief documentation for the program, accompanying a shorter listing (lacking the symbol table constants and Cardatron format bands), is also available at that site.

Since the source code existed only in the form of scanned listings, I had to transcribe it manually. Then, because EASY was written in itself, the next problem was to find a way to bootstrap the assembler source into 205 object code so it could be executed.

Both listings cited above include the assembled object code to the right of the source text. Even better, the shorter listing accompanying the documentation showed the forward references resolved to their final addresses. Having the forward references already resolved allowed me to write an off-line script to extract the object code directly from the transcribed text without having to resolve the forward references myself.

After transcribing the assembler source and carefully proofreading it, I extracted the object code from the right-most columns of the card images and reformatted those words into a standard seven-words-per-card deck that can be loaded using Cardatron format band 6. This deck has the same format as the short card-load program cited earlier. Using this load deck, I then assembled EASY with itself and compared the assembly output against my transcription. After a couple of cycles of correction and reassembly, I had an accurate transcription of EASY that would generate itself.

There were several anomalies in the reconstruction process that bear mentioning, though.

The unconditional branch instruction on line 129 (address 1733) is shown on the listing as assembling to 0000 00 0000. It should be 0000 20 4756. This was probably an error introduced during whatever process originally resolved the forward-reference addresses for the listing.
The START pseudo-instruction on line 304 is shown on the listing as "20 START", which would imply the next word should be assembled at location 0020. The effective address is actually 1478, however. I eventually learned that suppression of leading zeroes in numeric fields is something that was done by the IBM card equipment, not the 205 or Cardatron, and those machines suppressed any character that did not have a numeric 1-9 punch in its card code. There is actually a "0+" (or equivalently, "0&") for the program-point address in columns 37-38 on this line. Since those characters do not have a numeric punch in their card encoding, they were both zero-suppressed on the listing and printed as blanks. The presence of "0+" in the program-point address field changes the effective address of the START instruction from 0020 to the current address plus 20, or 1458+20=1478.
At line 425 (address 2712), the symbol table word for the BF7 operator (code 37, Block From Loop 7000) was shown on the listing as 0 4246 86 0007. The character codes in that word translate to BF6 instead, so I corrected the word to 0 4246 87 0007. This is very likely a day-one bug in the program, but was probably never encountered as BF7 is rarely used.
At lines 558-561 (addresses 1203-1206) in the initialization code for the program, the listing shows four Block To Loop instructions:
    1220 BT4
    1260 BT5
    1240 BT6
    1280 BT7
These each transfer 20-word blocks from the indicated main memory addresses to the 4000, 5000, 6000, and 7000 high-speed loops, respectively. Of course, when these are executed, they destroy whatever was previously in those loops. Alas, EASY had assembled very critical code and data into each of those loops (see lines 183-250 in the listing), so the initial attempts to run the assembler bombed. These BTn instructions made absolutely no sense, as nothing had been assembled into the 1220-1299 address range. I resolved the problem simply by changing the BTn instructions to BFn, which transferred words from the loops to unused memory addresses instead of the reverse. Later, I learned that MEASY uses all four high-speed loops for its loader, and any code assembled into loop addresses will not be loaded by that routine. My best guess at this point is that the version of EASY in the listing we have had been modified for assembly by MEASY, and that there is a missing piece that took care of loading the loops.
I modified the load deck to replace the HLT 1221 instruction that terminates the loader with an unconditional branch to the program's entry point (address 1200). This allows EASY to begin execution automatically after it is loaded.
I also modified the load deck to impose "reload lockout" on the reading of the last card of the load deck. This allows the source deck to be assembled to follow immediately after the load deck, by preventing the Cardatron from reading the first card of the source deck before EASY has a chance to load the format bands to the Cardatron.
The listing I transcribed did not have the mnemonics or operation codes for the four magnetic tape instructions. I added these to both the transcribed source and to the load deck.
As will become clear from the discussion of the symbol table below, EASY requires that memory be cleared prior to an assembly. It does not do this itself, so the short memory-clear program cited above has been prepended to the load deck mentioned in the next paragraph.

The transcribed source file, load deck, a sample output deck, and an annotated listing are all available from the software repository folder on our GitHub project site.

How EASY Works

The 205 was strictly a word-oriented machine. It had no native character manipulation facilities, and it being rather slow to begin with, free-form parsing of text was quite expensive. What the 205 did have, though, was the Cardatron, which was quite good at extracting columns from cards and transforming them into numeric words for the 205's memory. EASY took heavy advantage of this capability. The numerous fields of its input card format were designed to allow the Cardatron to do essentially all of the parsing of text on a card, converting each of the fields described in the "Programming with EASY" section above to a full word in memory as part of a single card-read instruction.

EASY reads each input card into locations 6005-6018 under control of Cardatron format band 1. You can examine the codes for that format band at memory locations 1400-1428 in the source.

The 6000-series addresses reference one of the 20-word high-speed loops on the memory drum. All loop addresses are congruent modulo 20, which means that ~~6005~~ 6015, 6135, 6675, 6815, etc., all address the same word on the drum [corrected 2015-12-08]. The layout of words in this loop is designed to facilitate both analysis of the columns on the card and formatting of the output card.

In the following, keep in mind that for both input and output, the Cardatron processes card columns in descending order, but reads and writes to memory in ascending order, so the fields in memory are in reverse order of those on the card:

Word 6000: the assembled word, but with its sign digit set to zero. This word will be punched into columns 71-80 on the output card.
Word 6001: the sign (in the low-order digit of the word) to be applied to the assembled word This will be punched into column 70 on the output card.
Word 6002: current value of the location counter (address of the instruction being assembled). This will be punched into columns 66-69 of the output card as the address field for the following card-read instruction.
Word 6003: skeleton card-read instruction (0 0810 44 xxxx) that will be punched into columns 60-69 on the output card. At load time, this will cause the next card in the output deck to be read; the address (xxxx, from word 6002 above) will specify the location into which the assembled word on that card will be stored.
Word 6004: a literal 6 applied by the Cardatron output band to the card-read instruction above and punched into column 59. This word is also used to supply a literal 6 elsewhere in the assembler (e.g., at 1732).
Word 6005: third word of comment field (columns 52-56).
Word 6006: second word of comment field (columns 47-51).
Word 6007: first word of comment field ( columns 42-46).
Word 6008: high-speed loop tag from column 40 of the card.
Word 6009: second program-point address reference character from column 38 on the card (+, -, F, B).
Word 6010: first program-point address reference character from column 37 (0-9).
Word 6011: symbolic address field from columns 31-15 on the card.
Word 6012: symbolic op code field from columns 25-29 on the card.
Word 6013: numeric address field from columns 20-23 on the card.
Word 6014: numeric op code field from columns 18-19 on the card.
Word 6015: numeric control digits from columns 14-17 on the card.
Word 6016: numeric sign from column 13 on the card.
Word 6017: symbolic label from columns 7-11 on the card.
Word 6018: program-point label from column 5 on the card.
Word 6019: literal 1600000999. The low-order four digits are used by the TABLE routine during symbol-table search wraparound to reload the B register. The high-order 16 gets punched into columns 1-2 in the output card to be used as Cardatron input format band select digits when the assembled deck is read back in.

Some fields are read numerically by the Cardatron, viz columns 5, 13, 14-17, 18-19, 20-23, 37, and 40. The rest of the fields are read alphanumerically. Blank columns read numerically are interpreted as zeroes. The internal code for a space character is decimal 00, so it is simple for EASY to determine if one of the symbolic fields is blank by checking its corresponding memory word for zero.

The numeric word from columns 13-23 becomes the default value for the assembled word. Literals can be specified simply by coding their value in these columns and leaving the remaining fields on the card blank. Coding a 1 in column 13 sets the sign digit in the assembled word, which for instructions indicates the operand address should be modified by the value of the B register prior to execution of the instruction.

EASY uses the program-point and symbol label fields on the left side of the card to create symbol table entries and detect when a forward reference to a symbol has been satisfied. If the symbolic operation code, symbolic operand address, program-point address reference, or high-speed loop tag are specified, their respective values are applied to the corresponding sub-fields in the assembled word.

The symbol table occupies memory locations 1900-3899, providing for a total of 1000 symbols. The table is in two parts: the first 1000 words hold the alphanumeric symbols, one symbol per word, left-justified over zeroes (i.e., blanks). The corresponding word 1000 locations higher in memory holds the value of the symbol, typically an address or instruction operation code. The table is initialized with the mnemonic operator codes and their numeric equivalents. The mnemonics have 7 added to their symbol value, probably to distinguish them from user-specified symbols having the same name. In effect, this places the operator mnemonics in a separate name space from the other symbols.

Symbols in the table are located by the TABLE routine, which resides in the 4000 and 5000 high-speed loops, using a hashing technique. The assembly routines that handle symbolic labels, mnemonic operation codes, and symbolic operand addresses call TABLE passing the target symbol in the A register. EASY multiplies the target symbol by 1001001001. This produces a 20-digit result in the A and R registers. EASY then extracts the high-order three digits of the R register as the modulus of the hash, producing an initial probe offset into the symbol words in addresses 1900-2899 of the table.

The hash modulus is loaded into the B register, which acts as an index register. The word at location 1900+B is loaded into the A register. If it is zero, that position in the symbol table is presently unused. This also means the target symbol is not in the table, and is therefore undefined. TABLE exits back to the caller one word after the address where it was called, with the target symbol restored to A and the offset to the unused symbol table entry in B.

If the symbol word in the table is not zero, TABLE subtracts the target symbol from it. If the result of that subtraction is zero, the symbol has been found, so TABLE loads the corresponding value of the symbol from 2900+B into A and returns to the caller three words after the address where it was called.

If the target symbol does not match the current symbol table entry, a hash collision has occurred. TABLE decrements B to test against the prior symbol in the table. The process in the above two paragraphs then repeats until either the symbol is found or an unused symbol table entry is encountered. If B decrements below zero, its value is reset to 999 to continue searching from the top of the table. Alas, if the symbol table fills up, TABLE will loop endlessly if it searches for an undefined symbol. There is no recovery from this situation.

Since words of all zeroes signify an unused entry in the symbol table, EASY will not work properly if at least addresses 1900-3959 in memory are not cleared to zero initially. Ensuring this is something that must be done prior to loading the program.

Program-point labels are stored in memory locations after the symbol table. Backward program points are stored beginning at 3900, indexed by the program-point number. Forward program points are stored beginning at 3950. Forward references to program points are handled in the same manner as for symbolic labels. Only the value word for a program point is stored, as the symbols are just the digits 1-9 and implicitly index the table entries.

Once all the fields of a card have been processed, the values of the words in the 6000 loop define the content of the output card to be punched. Cardatron output format 1 (at locations 1436-1457) defines the mapping of these words to columns on the output card, which is punched by the CWR instruction at location 7018.

A card containing the END pseudo-operator signals the end of input to the assembly. The operand address on this card specifies the memory location where the loader program will be placed when the output cards are loaded for execution.

The loader occupies 33 words plus one word for each forward-reference chain generated during the assembly. The loader is coded in locations 1761-1790 within EASY. The routine at 1740-1760 copies this code, at six words per card, to the output deck. Following the cards for the loader, this routine emits a table of chain descriptor words, again six words per card. As with the cards generated by the assembly process, a seventh word on each card (in columns 4-14) is a card-read instruction that bootstraps the next card in the deck. On the final card, that card-read instruction is replaced by a branch to the start of the loader.

Thus, when an output deck is loaded under format band 6, the assembled words go to their assigned locations, the loader and chain descriptor words go to locations starting with the one specified on the END card, and the last card of the deck automatically branches to the loader routine. After fixing the forward-reference chains, the loader halts with 1221 in the operand address register, and the program is ready to run. At this point the 205 operator would normally use one of the control panels to enter a branch instruction to the program's entry point.

Each chain descriptor word processed by the loader has its sign digit set to 1. The low-order four digits of this word, if non-zero, are the address of the last word in a forward-reference chain. The next four higher-order digits are the forward address to be applied to each of the words in the chain. As mentioned previously, each word in the chain has the address of the prior word in the chain, except for the last word, which has an address field of zero.

The foregoing is a highly condensed description of how EASY operates, with many significant details missing. I was interested in how this assembler worked, so studied it in detail and prepared an annotated listing of the program. If you are interested in a deeper understanding of EASY, you may find that to be a good place to start.

The MEASY Assembler

At some point during the summer of 1960, Knuth rewrote EASY to take advantage of magnetic tape, calling the new assembler MEASY ("Modified EASY Assembly System for the Burroughs 205"). It is not difficult to understand why he did so. The Algol-58 compiler eventually grew to more than 3600 cards, so each assembly with EASY would punch another 3600 cards, plus whatever was required for the loader. For those who remember punched cards, 3600 is almost two boxes worth.

Running under the retro-205 emulator within Google Chrome, EASY assembles the Algol-58 compiler in 41 minutes and punches 3737 cards. To load the compiler so it can be run, all of those cards need to be read back in again, which including the time to resolve forward addresses, takes another 17-18 minutes. Assembling to magnetic tape is faster and eliminates the waste in card stock on each assembly. Loading the assembled compiler from tape takes only a little over four minutes. When you may only get one time slot on the computer per day, this level of time savings could have a significant effect on productivity.

MEASY is not just a clone of EASY that has been patched to output to tape. It uses the same input card format and symbol table structure, and internally many of the coding techniques are similar, but it appears to be a complete rewrite. Like EASY, it is a one-pass assembler and relies on a loader to resolve forward-address references, but the output format is nothing like EASY's, and the loader works entirely differently than the one for cards. MEASY does not punch cards. Instead, it produces a printed listing on the Cardatron's IBM 407 tabulator.

Magnetic tape on the 205 is formatted in fixed, 20-word blocks. The output tape produced by MEASY has the loader routine in the first three blocks, followed by blocks of assembled code. Within a block of assembled code, each assembled word is represented by a pair of words:

The second word is the assembled word to be stored in memory.
The first word has two four-digit fields. The low-order four digits will be non-zero if assembly of this word resolved a forward-address reference. The value of this field is the address of the last word in the forward-reference chain, with subsequent words in the chain linked through their address fields, as with EASY. The next higher-order four digits are the address at which the second word should be stored. This is also the address that must be applied to any words in the forward-reference chain.

After the last block of assembled code, there is one additional block with its first word having a value of 9999999999. This signals the end of the program to the loader.

Running MEASY is a little more complicated than EASY. The assembler can be loaded either from cards (if assembled with EASY) or from tape (if assembled with itself). MEASY requires a scratch tape on magnetic tape unit 4 to receive the assembled output.

Loading from cards works the same as for EASY. As with EASY, I modified the load deck to replace the HLT 1221 at the end of the loader with a CUB (30, Change Unconditional and Block) instruction to the assembler's entry point, 1048. This instruction transfers 20 words from main memory to the 7000 loop, starting with the operand address. It then branches to the mod-20 congruent address in the loop (7008 in this case).

Loading from tape requires three steps. First, the three-block loader must be read from tape into memory at address 1000. This can be done with a magnetic tape read instruction of the form 0 0340 40 1000. Second, the loader must be initiated with a CUB to its entry point address at 1045 (0 0000 30 1045). Once the loader completes, it will HLT 7555. The final step is to initiate the assembler with a CUB 1048. This sequence of instructions could be entered manually from the Control Console keyboard, punched onto a paper tape, or punched onto a single card to be read with format band 6.

Reconstructing MEASY was done in a fashion similar to EASY. I transcribed the entire contents of the scanned listing, both source text and assembled object code. From that transcription, I created a card deck of the source text and assembled that with EASY, comparing the assembled output back to my transcription, applying corrections, and reassembling until the transcription and output matched.

Next, I extracted the MEASY object code from the EASY assembly output using an off-line script to produce a loadable card deck. Once magnetic tape devices were implemented in the emulator, I used that load deck to assemble MEASY with itself, this time checking the assembly output listing against the original scan. Once everything agreed, I had an accurate transcription, and executable versions of MEASY that could be loaded either from cards or tape.

As with EASY, the transcribed MEASY source file, assembly output listing, load deck, output deck from assembly with EASY, and output tape image from assembly with itself are all available from the software repository folder on our GitHub project site.

There are two anomalies in these materials. First, I transcribed MEASY using the same format as I had for EASY. The object code is in a different position on the MEASY listing than it is on the EASY listing. Second, the assembly output listing has been post-processed by an off-line script to apply leading-zero suppression to the numeric fields. Zero suppression was done by the IBM 407, and an equivalent facility has not yet been implemented in the emulator. The raw assembly output is also available in the project repository.

Why This Assembler?

If Burroughs had its STAR 0 assembler, and Shell Research had made its much more sophisticated assembler for the 205 available, why would Knuth have gone to the trouble to write an entirely different one on his own? I don't know the answer, but I can speculate a little.

First, it is likely that Knuth had never even seen a 205 prior to arriving in Pasadena early in the summer of 1960, let alone had any direct experience with one. He says in his oral history cited above that he had "learned about the 205 machine language" while still at Case. It's possible he was not aware of the other two assemblers, or had insufficient information on them to want to risk relying on them for such a short-term project.

Second, Knuth already had some experience with assemblers at Case Institute of Technology, and as cited above, had modified the SOAP III assembler for the IBM 650 to support program-point labels. It's possible he had some ideas about how an assembler could be constructed, and wanted to try those. It's also possible he wrote EASY as a warm-up exercise, to validate his understanding of the 205 and refine coding techniques for it. While the 205 and 650 had superficially similar architectures, programming to deal with the 205's high-speed loops was entirely different than that for addressing and flow control in the 650.

Third, it is clear from his comments in the oral history cited above that he had started working on the Algol-58 compiler before he got to Pasadena, and was coding portions of it at least by the time he was driving out to California. In order to do that, he had to have an assembly notation to code, and much of the notation in his draft coding form for the compiler closely resembles that of EASY.

Regardless of his reasons, his implementation of not one, but two 205 assemblers for the Algol compiler project worked, and no doubt helped him meet the project's ambitious schedule. Not only that, it turned out these relatively simple assemblers were quite fast. As Richard Waychoff recalls in his memoir, comparing assembly of Knuth's Algol-58 compiler with that of the 205 FORTRAN compiler he and Lloyd Turner were developing at the same time:

Our compilers were both punched on cards and were the same size. We had written ours in STAR 0, the only assembler that Burroughs supported on the 205. [...] Our compiler took one hour and 45 minutes to assemble. The first week of don’s project he spent in writing his own assembler. He could assemble his compiler in 45 minutes. We were green with envy. I am sure that don used only half the computer time that Lloyd and I used.

Running in the retro-205 emulator under Google Chrome, EASY can assemble its 574-card self in six minutes and 15 seconds. That is a rate of almost 92 cards/minute, which is pretty impressive, considering the assembler is ultimately limited by the 100 card/minute speed of the IBM 523 punch. The assembly of the Algol-58 compiler with EASY cited above -- producing 3737 cards in 41 minutes -- yields a similar rate.

Knuth comments in his notes for the MEASY assembler that it operates at about 120 cards/minute. Our experience with it in the emulator is nearly the same -- it compiles the Algol-58 compiler in approximately 30 minutes.

For whatever reasons drove Knuth to write his own assemblers, we are fortunate today that he did so, and that the source code for them has survived. The most reasonable alternative for him to use instead was probably the STAR 0 assembler. Nothing of that assembler appears to exist any longer -- not even a reference manual -- so if the Algol-58 compiler had been written in STAR 0, we would have been faced with the prospect of reverse-engineering that assembler from thin air.

Regardless, reconstruction of EASY and MEASY has been an interesting sideline to the overall goal of reconstructing of the Algol-58 compiler.

In Conclusion

As mentioned earlier, completion of the MEASY reconstruction has had to wait on implementation of magnetic tape in the retro-205 emulator. That work is now complete, and the next release of the emulator, scheduled shortly, will have tape support. Transcription of the Algol-58 source code was completed in June, and much progress has been made towards making it run.

The next blog posts will detail the magnetic tape implementation and the status of the compiler's reconstruction.

____________
¹ Shell Assembly Program for the Burroughs 205 Electronic Data Processing System, Burroughs Corporation Bulletin 3038, March 1960, Part I, page 2. Originally published as EPR Memorandum Report 37 by the Shell Development Company, Exploration and Production Research Division, Houston, Texas, September 1958.

The Burroughs 205 and 220 Blog

Welcome to the Datatron 205 and 220 Blog

Saturday, November 7, 2015

Knuth's Algol-58 Compiler

A Tale of Two Compilers

Reconstructing the Compiler Source

Transcribing the Listing

The Mysterious Assembly Mismatches

The First Compile

Running the Recovered Compiler

Running Tom Sawyer's Compiler

Comparing the Two Compilers

Where Do We Go From Here?

References

Sunday, August 16, 2015

Magnetic Tape for the retro-205 Emulator

Overview of 205 Magnetic Tape

Physical and Recording Characteristics

Conditioning Tapes

Tape Data Transfer and Buffering

Magnetic Tape Instructions

Magnetic Tape User Interface

Magnetic Tape Control Unit

Magnetic Tape Storage Unit (DataReader)

Loading and Unloading Tape Image Files

Format of Tape Image Files

Other Changes and Enhancements in Release 0.05

Saturday, August 8, 2015

Knuth's EASY Assembler

Origin of the EASY Assembler

Using EASY

Programming with EASY

Reconstructing EASY

How EASY Works

The MEASY Assembler

Why This Assembler?

In Conclusion

Contributors

Blog Archive