Welcome to Tom's Datatron Blog

I have a Web Page that outlines the history of the Burroughs Datatron 205. Please visit that page and return here for any comments.

Saturday, June 11, 2016

The Shell Assembler, Part 2

In Part 1 of this post, I introduced the Shell Assembler for the Burroughs 205 [1]. That part discussed the origin of the assembler, an overview of its features, its reconstruction from listings in its Part II manual [2], and how to operate the assembler in the retro-205 emulator.

This is Paul Kimpel, with another post on Tom Sawyer's 205 blog. In this second part, I will discuss programming with the Shell Assembler, along with its relatively advanced features for making the programmer's job easier and more productive. Unlike Knuth's EASY and MEASY assemblers [3], which were built to be lightweight and fast, Shell was built for power and convenience. It became the assembler of choice for shops that had to write and maintain a lot of code.

Operator and Pseudo-Operator Mnemonics

In contrast to EASY and MEASY, which use a set of operator mnemonic codes designed to be compatible between the Burroughs 205 and 220 computer systems, the Shell Assembler uses the standard set of mnemonics initially established by ElectroData and continued by Burroughs in their reference manuals:
     00 PTR     20 CU      40 MTR     60 M       80 FAD
     01 CIRA    21 CUR     41 --      61 DIV     81 FSU
     02 STC     22 DB      42 MTS     62 --      82 FM
     03 PTW     23 RO      43 --      63 EX      83 FDIV
     04 CNZ     24 BF4     44 CDR     64 CAD     84 --
     05 --      25 BF5     45 CDRI    65 CSU     85 --
     06 UA      26 BF6     46 --      66 CADA    86 --
     07 PTWF    27 BF7     47 --      67 CSUA    87 --
     08 STOP    28 CC      48 CDRF    68 --      88 --
     09 --      29 CCR     49 --      69 --      89 --
     10 DAD     30 CUB     50 MTW     70 MRO     90 (FAA)
     11 BA      31 CUBR    51 --      71 EXC     91 (FSA)
     12 ST      32 IB      52 MTRW    72 SB      92 (FMA)
     13 SR      33 CR      53 --      73 OSGD    93 (FDA)
     14 SL      34 BT4     54 CDW     74 AD      94 --
     15 NOR     35 BT5     55 CDWI    75 SU      95 --
     16 ADSC    36 BT6     56 --      76 ADA     96 --
     17 SUSC    37 BT7     57 --      77 SUA     97 --
     18 --      38 CCB     58 CDWF    78 --      98 --
     19 --      39 CCBR    59 --      79 --      99 --

It also implements a number of synonyms for some of the instructions, e.g., A for AD (Add) and S for SU (subtract). For some reason, the version of the assembler we have does not implement mnemonics for the floating-absolute instructions (90=FAA, 91=FSA, 92=FMA, 93=FDA). It would not be difficult, however, to add these to the assembler's symbol table.

In addition to supporting the mnemonic operator codes for the 205 machine instructions, the Shell Assembler offers these pseudo operators:
  • REM: a remark or comment. The remaining contents the card are ignored by the assembler, except that they are printed on the listing.
  • EQU: assign a value to a symbol. This is typically used to assign a symbol to an absolute address, or to assign the value of one symbol to another.
  • ORG: specify the next assembly address. Normally, the assembler increments its address counter by one after assembling an instruction. This pseudo operator is typically used to establish a starting address for a program or to position a section of a program at a particular address.
  • REG: reserve a block of memory locations. This simply adds the value of the operand field to the address counter. Any label for the line is assigned the value of the starting address of the block
  • MOD: advances the address counter forward as necessary so that it is a modulo 20 address. This is particularly useful for positioning the address of magnetic tape records in memory. Data transfers to and from tape can begin at any main memory address, but because magnetic tape I/Os are buffered through the 4000 and 5000 high-speed loops on the memory drum, and because of the way that blocking transfers between main memory and the high-speed loops work, the word at the first mod-20 congruent address is the first one read from or written to the tape. Thus a program must read data from a tape using the same mod-20 congruent address as was used to write data to the tape in order for the words end up in the same sequence in memory. Starting the memory buffers on mod-20 addresses helps eliminate any confusion as to the word ordering between tape and memory.
  • NUM: define a one-word numeric literal value. The value must be right-justified in the 10-character operand field, with the sign coded as either 0/1 or +/- in the tag field. Spaces in the operand and tag fields are interpreted as zeroes. See the "Input Card Layout" section below for the field locations.
  • ALF: define a one word (five character) alphanumeric literal encoded using Cardatron card codes.
  • ALFS: define an alphanumeric literal up to six words (30 characters) in length, encoded using Cardatron codes. The text of the literal is written in the remarks field of the card. The length of the literal in words (1-6) must be written right-justified in the address portion of the operand field. The resulting words are stored in reverse order in memory to support both the way the Cardatron accessed memory and the decrement-and-branch indexing native to the 205's B register.
  • FLX and FLXS: similar to ALF and ALFS, but generate words using the older Flexowriter code used on the Datatron 204 and earlier system models before the Cardatron was introduced.
  • TAG: specify the high-speed loop to which addresses in assembled instructions should be assigned. Efficient programming for the 205 requires that instructions be transferred to one of the high-speed loops (typically the 7000 loop) and executed from there. The TAG operator specifies the digit (4-7) that the assembler will automatically set in the high-order digit of the operand address for instructions that reference memory, saving the programmer the trouble of continually having to override that digit on individual instructions. This behavior can be overridden on individual instructions as described for the Loop Tag field below, or disabled altogether by coding a TAG operator with an "X" as the tag digit.
  • MACRO and NEW: define assembler macro instructions. The difference between them is that MACRO is used to define a temporary macro that will exist only for the current assembly run, while NEW defines a macro that can be used in the current assembly run, but will also be inserted into the macro library on magnetic tape. See the "Macro Definition and Usage" section below for more information on how these two pseudo-operators are used.
  • SUBR: causes a subroutine to be copied from the macro library and appended to the end of the program being assembled. No call linkage to the subroutine is provided. A given subroutine will be included only once, no matter how many references are made to it using SUBR. Thus a body of code can be written as a closed subroutine, and a macro written to provide parameters and linkage to the subroutine, using SUBR within the macro to call out the closed body of code from the library. Each macro invocation will generate unique linkage code at that point in memory, but the body of the closed subroutine will be included only once. Subroutines can be added to the library as if they are a parameter-less macro, using NEW.
  • RFB, WFB, and PFB: generate Cardatron format bands. RFB generates a format band for reading cards; WFB generates a format band for printing to a line printer; PFB generates a format band for punching cards. These operators use a simple notation to define the card or print line format, dramatically reducing the effort and potential for error compared to coding a band manually. See the "Cardatron Format Band Assembly" section below for more information.
  • END: signals the end of the main program or a macro. The card deck must always end with this pseudo-instruction.
As mentioned in Part 1 of this post, the Shell Assembler does rather extensive checking of the input text and assembled code, generating error messages in English and identifying the line on which they were detected. It also does "invalid pair" checking -- flagging instances of one instruction following another that are unreasonable or which could lead to incorrect results.

Programming with the Shell Assembler

Source program input to the Shell Assembler was punched on cards. This section describes the layout of the cards, how the fixed columns of that layout were used, and some special features of the assembler.

As described in an earlier post [4], the Cardatron input unit requires a punch in a specified column to select a format band from its small drum memory. The codes in this format band describe how the Cardatron will reformat and translate columns of data on the IBM card machine to the 205 memory. The Shell Assembler normally takes its band selection from column 1 and uses two format bands:
  1. Format for instruction cards.
  2. Format for a header card.

The Header Card

The first card in the deck must have a "2" in column 1, indicating it is the header card. The contents of this card are read using the format band defined in FMB7 of Movement 1 and output to the line printer using the band defined in FMB6. The contents of this card are not otherwise used by the assembler.
  • Columns 1-3 are read as a number.
  • Columns 4-53 are read alphanumerically (these are probably intended to be a title).
  • Columns 54-55 are also read alphanumerically.
  • Columns 56-61 are read numerically (these appear to be intended as a date in MMDDYY format).
  • The remaining 19 columns on the card are ignored.

Input Card Format

The remaining cards of the source program must have a "1" in column 1. These cards carry the instructions that comprise the program.

Cards for format band 1 have the following layout:

     1       10        20        30        40        50        60

Columns 2-9 and 66-80 are ignored by the assembler, and can be used for sequencing or identification of the deck.

Column 1: Cardatron format band code. The character in this column is used by the Cardatron, but otherwise ignored by the assembler.

Columns 10-14: Symbolic location label: the traditional label field for an assembly line. The symbol in this field is assigned the current value of the address counter. Labels are limited to five characters and must be unique within the program. They must be left-justified and start with an alphabetic character, but any characters, including punctuation, can be used in the other four positions.

Alternatively, this field could have a "program-point" label, written left-justified in the field as a period followed by a letter, e.g., ".A". Program points are temporary labels with a relative, local scope. They can be defined multiple times within a program. The program can refer to an address at the immediately-prior or immediately-next program point. Once a program-point label is redefined, its prior location falls out of scope and can no longer be referred to by subsequent instructions. See columns 26-30, below, for the way that these labels were referenced.

Program points allow a programmer to refer to locally-relevant locations, e.g. for short branches and local constants, without cluttering up the symbol table with labels that may be used only a few times within a small region of the program.

As discussed in a footnote on page 2 of the Part I manual for this assembler, the idea of program points apparently originated with Melvin Conway of the Case Institute of Technology (now Case Western Reserve University) and were first incorporated into the SOAP III assembler for the IBM 650 by Donald Knuth. Knuth later used program points in his EASY and MEASY assemblers. They also found their way into a number of later Burroughs assemblers. Program points were not available in STAR 0, the official Burroughs assembler for the 205, however.

Columns 15-19: "Spares": the sign and first four numeric digits of an instruction word. The sign must be coded in column 15, and can be a numeric digit, a space (which was translated to 0) or "-" (which was translated to 1). Odd-valued sign digits in instruction words cause the B-register to be added to the operand address to form the effective address used when the instruction executes. The other four digits are used for the breakpoint control digit (in column 19) and for control digits in I/O instructions. Programmers sometimes used this field for data. If all five columns are left blank, the sign and control digits are assembled as zeroes. If any of the four control digits are non-zero, all four must be coded.

Columns 20-24: Operation code: the symbolic operation code for the instruction or pseudo-instruction. This must be left-justified in the field. Alternatively, a numeric operation code can be entered in the last two positions of this field. The Shell Assembler uses the standard ElectroData/Burroughs mnemonics as discussed in the prior section.

Column 25: Loop tag: for instructions that reference memory addresses, a value of 4-7 in this column will cause the high-order digit of the assembled address to be set to this value, making it an address for one of the high-speed loops on the drum. If this field is left blank and a loop digit has been specified previously by the TAG pseudo-instruction, that loop digit will be placed in the high-order digit of the assembled instruction. If column 25 contains an "X", any effect of TAG is suppressed in the assembled instruction, and the high-order digit of the address is assembled normally.

Use of the TAG pseudo-instruction considerably eases the task of writing code to run in the 205's high-speed loops. Instructions must be assembled into main memory locations and then blocked to one of the loops. Instructions referencing locations within the loop, e.g., for short branches or local constants, must use loop addresses instead of the ones that would normally be assigned for their originally-assembled location, so the use of TAG allows this address modification to be applied automatically. Most of the code in the Shell Assembler itself is written under the influence of a TAG 7 directive, as most of the code is blocked into the 7000 loop by a CUB instruction for execution.

Columns 26-30: Operand address: the coding in this field specifies the address field to be assembled into the instruction (possibly modified by the increment field below). This field can hold one of the following:
  • Spaces: this causes the current value of the location counter to be assembled into the instruction. This is equivalent to the symbol "*" used by many other assemblers to designate the current value of the location counter.
  • Absolute address: a literal, decimal address, right-justified in the five columns of the field. Leading zeroes could be replaced by spaces. This was normally used only with instructions that require a numeric operand, such as shifts and console I/O.
  • Symbolic address: one of the alphanumeric symbols defined in columns 10-14 on some other line of the program.
  • Program-point address: a reference to a program-point label. This is coded in columns 26-27 as either "+L" or "-L", where "L" is a letter. "+L" refers to next line in the source labeled ".L". "-L" refers to the prior line in the source with that label. Only the immediately-next or immediately-prior lines with that label can be referenced with this notation. Note that, depending on the type of print wheels installed in the 407, "+" (a 12-row punch on a card) may print as "&".
Columns 31-35: Operand address increment: If this field is blank, the operand address specified in columns 26-30 is assembled as is. Otherwise, the value of this field modifies that operand address. Column 26 must be coded as a "+" ("&") or "-". The remaining four columns specify the increment, right-justified in the field. Leading zeroes may be replaced by spaces. This increment is then algebraically added to the operand address, modulo 10,000. Negative results are represented in 10s-complement form, e.g., 0000 - 0001 is 9999.

Columns 36-65: Remarks: These 30 columns can be used for comments, and are reproduced as-is on the output listing. This field is also used as the operand for the ALFS, FLXS, RFB, PFB, and WFB pseudo-instructions. Format-band coding for the three format-band instructions can overflow on up to eight continuation cards by leaving the operation code field on the continuation cards blank.

Cardatron Format Band Assembly

One of the most useful features of the Shell Assembler is its ability to construct Cardatron format bands from a fairly simple and intuitive notation.

Designing and coding format bands for the Cardatron is extremely tedious. As described in [4], a 205 format band consists of 315 digits, which occupy 29 words in memory before being loaded to the Cardatron drum. Bands are coded using values 0-3 in each digit position of a memory word, including the sign digits.

The Cardatron works by splitting each column on a card or line of print into two decimal digits, one for the numeric portion (the bottom nine rows on a card) and one for the zone portion (the top three rows on a card). The format band digits operate on the stream of numeric and zone digits coming from or going to the IBM device, by copying digits, deleting digits, or inserting zero digits into the stream. The result is a mapping between the 80 or 120 columns on the IBM device and up to 28 words in 205 memory. The format band digits can drop columns and insert sign, leading, and scaling digits on input. They can also insert blanks on output, control whether digits from memory words are output numerically or alphanumerically, reduce 10-digit memory word values to fewer columns on a card or print line, and position signs as either separate columns or overpunches.

This mapping is complicated by the order in which the Cardatron processes data. It starts with the last column on a card or print line and works towards the front, with the first word in memory mapped to the last columns on the card or print line. Thus the low-order digits in the first word of a format band in memory references the end of a card or print line. The band designer must code digits to account for exactly 80 columns on a card or 120 columns on a print line, and provide "3" (delete digit) codes in all remaining positions of the format band. On input, the designer must code a single additional "0" (insert zero digit) code at the end of the format band to push the last word being assembled out of the D register and into memory.

Electrodata developed a tabloid-size (11x17-inch) form to aid in designing and coding format bands. See page 6-11 in [5] for an example of the form used with the 220 Cardatron, which is almost identical to that for the 205. This form made it easier for the designer to keep track of columns on the IBM device, the mapping between those columns and words in 205 memory, and any padding required to fill the band data out to 29 memory words. Even with this form, though, the process of designing and coding the band digits was tedious and error-prone.

The format band pseudo-operators in the Shell Assembler dramatically simplify the task of designing and coding format bands. They use a free-field notation with letter codes and repeat factors, not unlike a FORTRAN FORMAT statement or a COBOL PICTURE clause. The band definition consists of phrases, one per 205 memory word, that define the mapping between digits in the memory word and columns on the IBM device. The word-phrases are delimited by "+" (or "&") characters. For example, consider the definition of format band 1 described in the prior section this is used to read the instruction card for the Shell Assembler:

FMB1     RFB            9B & 7¤P10Z¤ & 3¤P5A¤ & P8ZA
                           & 8¤P5A¤ & P10Z & 15B
The codes used in format band phrases have the following meanings:
  • A - translate a column alphanumerically. On input, two digits from the card (usually the numeric and zone digits from the same column) are translated to the Cardatron code and stored in the next two digits in memory, proceeding from right to left in the memory word. On output, two digits in Cardatron code are translated from the memory word to numeric and zone codes for the next column (again, proceeding from right to left) on the card or print line.
  • B - ignore a column. On input, the next two digits from the card are dropped and not stored in memory. On output, two zero digits are generated, producing a blank column on the IBM device.
  • N - translate a column numerically. On input this copies the numeric digit from a card column to memory and discards the zone digit. On output, it copies a digit from memory as the numeric digit for a column and supplies a zero for the zone digit in that column. As a special case on output, if the digit in memory is a zero, a zone digit is output that causes a zero to be printed or punched in the column. This was necessary because the IBM devices consider  a zero punch (third row on a card) to be a zone, not a numeric punch. Without this special case, zeroes in memory would be output as blank columns instead of zeroes.
  • P - ignore the sign digit in memory. This code is identical to the Z code below, except that the assembler will allow a P only for the leftmost digit in a word. The combination of a special code for the sign digit and delimiters between word-phases allows the assembler to verify that exactly 11 digits have been generated or consumed by the band for each memory word.
  • X - transfer zone digit. This is normally used to place the sign in a column. The combination XN will treat the sign as an over-punch on the numeric digit formatted by N. The combination XB will treat the sign as a separate column.
  • Z - ignore digit position in memory. On input, this will not consume a digit coming from the card and will store a zero digit in memory. On output, it will skip the next digit in memory and output nothing to the IBM device.
  • ¤ - the lozenge (which prints as a right-parenthesis on some tabulators) serves as a bracket character to group one or more phrases for repetition.
Any of these codes can be prefixed by an integer to designate that it will be repeated that number of times. A repeat count in front of a ¤-group indicates the entire group is to be repeated that number of times.

For the format band example above, the word-phrases can be understood to have the following meaning:
  • 9B - skip the first 9 positions on the card.
  • & 7¤P10Z¤ - store seven words of zeroes into memory. The P stores a zero in the sign-digit position and 10Z stores the other ten digits of the word.
  • & 3¤P5A¤ - transfer the next 15 columns on the card alphanumerically to the next three words in memory. This corresponds to the Symbolic Location, Spares, and Operation Code fields in columns 10-24 on the card. The P stores a zero in the sign digit of each five-character word.
  • & P8ZA - Store the alphanumeric code for next column (TAG in column 25) in the low-order two digits of the next word in memory. P8Z stores zeroes in the sign and high-order eight digits of that word.
  • & 8¤P5A¤ - Transfer the next 40 columns (26-65) from the card alphanumerically into the next eight words in memory. This comprises the Operand Address, Address Increment, and Remarks fields on the card.
  • & P10Z - Store another word of zeroes into memory.
  • & 15B - Skip the remaining 15 columns (66-80) on the card.
Note that the additional zero digit to push the last input word out of the D register is supplied automatically by the assembler when translating a RFB defnition.

The way that format bands are coded internally for input and output is slightly different. One very nice thing about the format-band phrase notation is that it is symmetric between input and output. Reading a card from an input device with a set of format phrases in an RFB specification and then writing that data using the same set of phrases in a WFB or PFB specification produces an identical set of columns on the output device. The digits in the format band will be somewhat different, but the assembler knows how to code the band differently based on the pseudo-operation code used.

The only difference between WFB and PFB is that bands for punching cards must format 80 columns, while bands for printing must format 120 columns. The band designer must still account for the appropriate number of columns on the IBM device, and the assembler will verify this, issuing an error message if the number of columns is incorrect. The designer does not need to worry about padding the band out to 315 digits, however -- the assembler does that automatically.

Macro Definition and Usage

Our word macro comes from the Greek word for long. In the context of computers and software, macro is typically used as an abbreviation for macroinstruction. There are many forms of macroinstructions, ranging from simple text replacement (e.g., named constants) to parameterized replacement of text (e.g., the C #define pre-processor) to the conditional and iterative generation of highly customized text.

Macro assemblers are assembler programs that implement the ability to create and invoke macroinstructions. The first assembler to employ macros appears to be Autocoder for the IBM 702 and 705 in 1956. The presence of macros in the Shell Assembler of 1958 is therefore a fairly early application of this concept. There were people at Shell at the time who had come from IBM, including Bob Barton, so it's possible that the idea of including macros in the Shell Assembler came from those former IBMers.

The main idea of macros in assembly languages is to take commonly-used sequences of instructions and encapsulate them, give that sequence a name, and call forth the sequence later, possibly specifying parameters that will customize the sequence at that point in the program. The invocation of a macro often looks like the coding of an instruction, but with the operation code naming the macroinstruction instead of the mnemonic for a machine instruction.

Macros and subroutines are related, in that both can be used to define a sequence of code once and then activate that sequence from many places later. Subroutines are generally stored in memory only once, the program transfers control to the subroutine when it is invoked, and the subroutine passes control back to the program when it is finished. Macros, on the other hand, generate code in the program at the point they are invoked. Each time the macro is invoked, additional code is generated at that point in the program, and the code may be customized based on the parameters passed as part of the macro invocation.

Another important difference is that while subroutines are executed at run time, macros are executed at assembly time -- invocation of a macro generates additional text to be assembled. The instructions resulting from assembling that additional text will be executed at run time, but not the macro itself.

Invoking Macros in the Shell Assembler

A macro in invoked by writing its name in the operation code field (columns 20-24) on a card. A label, if desired, can be written in the label field. Actual parameters to the macro, if any, are written in the operand address and increment fields (columns 26-35) just as they are for a normal instruction. The first parameter is written in the operand field to the right of the macro name. Any additional parameters are written in the operand fields of subsequent cards, one per card. The operation code of these continuation cards must be blank. There is no limit to the number of parameters a macro may have.

All forms of operands may be passed as macro parameters. The only exception to operand coding for macros as compared to normal instructions is that the loop tag is never applied to the parameter operand as part of the invocation -- a loop tag may be applied to the parameter when it is used inside the macro, of course, but operand parameters are passed to the macro as is, without loop address modification.

Thus, a macro instruction with three parameters might be coded as follows:
.G    CLEAR         0020
              TBL1 +0012

As discussed above, invocation of a macro generates code in the program at the point of invocation. The Shell Assembler does this a little differently than most macro assemblers, however. At the point of invocation, the assembler emits a CUB (30, Change Unconditionally and Block) instruction. The code generated by the macro is placed at the effective address of that instruction, which will be after the end of the non-macro instructions in the program.

Any return to the point of invocation is the responsibility of the macro, so it was typical to pass a label or relative address as one of the parameters to the macro. An example of this is shown in the third parameter above -- the +0001 is relative to the CUB instruction emitted by the assembler at the point the macro is invoked. Thus the return would be to the instruction immediately following the invocation.

The reason for using a CUB at the point of macro invocation is that, once again, efficient programming for the 205 requires that code be executed out of one of the high-speed memory loops as much as possible. Well-written 205 programs were coded mostly as short sequences of instructions linked by CUBs to load and execute the sequences. Thus, macro invocation automatically puts the generated code in the 7000 loop. It is the macro coder's responsibility to deal with macro expansion that exceeds the 20-word capacity of the 7000 loop.

Defining Macros in the Shell Assembler

Macros are defined using the pseudo-operators MACRO and NEW. MACRO defines a temporary macro that will available only during the current assembly run. NEW defines a macro that will be permanently cataloged on the library tape. Other than that distinction, the two pseudo-operators are identical and function the same. MACRO and NEW can also be used to define bodies of code to be called out using the SUBR pseudo-operator, although such definitions should not use parameters.

Temporary macros are stored on the library tape along with permanent macros; they are simply not recorded in the tape's catalog. For that reason, Section VII of the Part I manual recommends that MACRO definitions follow any NEW definitions to avoid leaving unusable gaps on the library tape. It also recommends that permanent updates to the library be done in a separate assembly run dedicated to that purpose.

To define a macro, code MACRO or NEW in the operation-code field and the name of the macro (up to five characters) in the operand address field of a card. In the middle two digits of the "spares" field (columns 17-18), code the number of cards that make up the macro definition, not including the MACRO/NEW card, but including the required END card that terminates the macro. The names of newly-defined macros must not match the name of any existing macro -- attempting to do so results in an error.

Within the body of the macro, instructions are written the same way they are in open code. Macros may invoke other macros. Parameters are referred to by their ordinal position in the invocation -- #0001, #0002, #0003, etc., and may be referenced as the operand address in instructions and other macro invocations. The effective address of these parameters may be modified by the operand address increment field and by means of loop tags.

Here is one possible implementation for the CLEAR macro invoked above. Note the count of cards in the first line of the macro definition (0080) and the negative sign on the second STC instruction, causing it to apply B-register modification to the operand address.
      0080 MACRO  CLEAR
           TAG  7
           SB     +C
           STC    +C
     -     STC  X #0002
           DB          -0001
           CUB  X #0003
.C            00X #0001-0001
When a macro invocation is encountered during Movement 1, the assembler emits a CUB with an unresolved forward address at that point in the program, then searches the macro library for the macro, and when found, makes an entry in a memory table for the macro and its parameters. After the END card is sensed in Movement 1, the assembler steps through this table, and for each macro invocation, re-positions the library tape to the macro in the library and appends its body on tape unit 1 after the records that were written there for the main portion of the program, partially assembling the instructions in the body in the same way that instructions in the main portion are during that first movement. In Movement 2, assembly of the instructions from the macro bodies is completed as for other instructions, and the addresses in the CUB instructions at the point of macro invocation are resolved to the location where the macro bodies are assembled.

The project repository has a folder [6] with small sample card decks and assembly listings, showing both definition and invocation of macros. The listings show how the CUB instructions emitted at the point of invocation branch to the code appended at the end of the program for each invocation.

Recovery of the Shell Assembler has been a very interesting part of this project. I wish we had more examples of its use in significant applications, especially ones demonstrating the macro facility, and perhaps some will surface in due time. In any case, it's an excellent example of a sophisticated piece of programming from the mid-late 1950s.


[1] Shell Symbolic Assembly Program for the Burroughs 205, Part I, Burroughs Corporation, Bulletin 3038, March 1960:

[2] Shell Symbolic Assembly Program for the Burroughs 205, Part II, Burroughs Corporation, Bulletin 3038, March 1960:

[3] "Knuth's EASY Assembler":

[4] "The Mighty CARDATRON":

[5] Burroughs 220 Operational Characteristics, Bulletin 5020A, Burroughs Corporation, August 1960:

[6] Folder of sample macro definitions and invocations:

Wednesday, June 8, 2016

The Shell Assembler, Part 1

There simply is not much point in building an emulator for an older computer system unless you have software to run in that emulator once you get it built.

Alas, we do not have much software for the ElectroData/Burroughs 205. Tom Sawyer has the decimal tape dump of the "Burroughs Algebraic Compiler." I have transcribed the EASY and MEASY assemblers, and the Algol-58 compiler that Donald Knuth donated to the Computer History Museum a decade ago. The recovery of these has been described in prior blog posts [1, 2]. Aside from a few demos and test routines Tom and I have written, that is all the software we have, or so I originally thought.

This is Paul Kimpel again, with another post on Tom's 205 blog. This is the first of a two-part post that describes another piece of software we have managed to recover -- the Shell Assembler. This part discusses the general features of the assembler, recovery of the source and object code, and how to operate the assembler in the retro-205 emulator. The second part will discuss the assembler's features in more detail, including its macro capability, and programming with the assembler.

The Shell Assembler

Tom Sawyer had yet another 205 manual in his collection -- a pair of them, actually -- published by Burroughs in March 1960 as Bulletin 3038, and titled Shell Symbolic Assembly Program for the Burroughs 205 Electronic Data-Processing System, Parts I and II [3, 4]. These were republications of documents originally issued in September 1958 as EPR Memorandum 37 by the Shell Development Company, Exploration and Production Research Division, Houston, Texas.


These two documents and the software they describe were authored by Joel C. Erdwinn, G. Clark Oliphint, C. M. Pearcy, and David M. Dahm. Erdwinn, Oliphint, and Dahm later went to Burroughs in Pasadena, California. All three worked on the highly-regarded Algol-58 compiler for the Burroughs 220, known as BALGOL. Erdwinn later went on to a distinguished career at Computer Sciences Corporation. Oliphint and Dahm worked on the software for the Burroughs B5000. Dahm continued to work and consult with Burroughs off and on for the rest of his career, and is probably best known as the designer, with Roy Guck, of the DMSII database management system. The Shell Assembler is an example of the talent and promise all three showed early in their careers.

The Part I manual describes the assembler, its coding notation, and operation. It also includes a detailed set of flowcharts. Part II contains an assembly listing of the assembler, written in itself. This listing is in two parts, corresponding to the two "movements" (today we would call them "passes") by which the assembler operated. These are remarkable documents. They give a full disclosure of the documentation, design, and coding of the assembler, apparently with the intent of allowing anyone to reconstruct the software from the documents alone. This effectively was open-source distribution, ca. 1958.


Of all the assemblers for the 205 we presently know about, the Shell Assembler is clearly the most sophisticated. The coding notation is based on a fixed-column input format, as is typical of most assemblers. Like Knuth's EASY and MEASY assemblers, the input format is even more columnar than most, designed for efficient processing by format bands in the 205's Cardatron card reader interface. This approach all but eliminates the need to parse the input text in software.

In addition to supporting a full set of mnemonic operator codes for the 205, the Shell Assembler has an extensive set of pseudo-operators for manipulating the address counter, managing addresses for the high-speed loops on the memory drum, coding numeric and alphanumeric literals, and defining and invoking both macros and library subroutines. The assembler also has the ability to maintain the libraries on magnetic tape. Perhaps its most unusual (and most-needed) pseudo-instructions provide a way to conveniently code the Cardatron format bands used to interface with IBM card readers, card punches, and tabulators (line printers). All of these are discussed in more detail in Part 2.
    The Shell Assembler does rather extensive checking of the input text and assembled code, generating error messages in English and identifying the line on which they were detected. Errors detected during Movement 1 are listed on the line printer during that pass. The corresponding lines are flagged with a letter in the first column of the listing when they were printed during Movement 2. Any additional errors detected during Movement 2 are listed on the Flexowriter.

    Perhaps the most unusual checking feature of the assembler is "invalid pair testing." It organizes the 205 machine instructions into a set of classes based on the processor state they require to execute and the state they establish during their execution. As each machine instruction is being assembled, the assembler determines whether that instruction is a reasonable one to follow the prior instruction, based on the states this instruction requires and the prior one leaves behind.

    For example, many instructions operate upon the processor's A register, and several instructions clear or invalidate the contents of that register. If one of the former instructions follows one of the latter, the assembler flags that sequence as an invalid pair -- the second instruction is attempting to use machine state that has been destroyed by the first one or the second instruction is destroying state left by the first one, e.g., AD (Add) followed by CAD (Clear and Add, i.e., load A from a memory location). The load destroys the state left by the add.

    Another example of invalid-pair testing concerns the processor's Overflow toggle. When execution of an instruction causes the Overflow toggle to be set, the next instruction executed must be one of the conditional branches; if it is not, the processor will halt on the Overflow condition. The assembler will flag as an invalid pair instances where Overflow could be set but the next instruction is not a conditional branch, e.g., AD (Add) followed immediately by SU (Subtract).

    The flagging of invalid pairs is just a warning, and the assembly will continue regardless. Section V in the Part I manual describes in detail the instruction classes and how instruction pairs are checked.

    Reconstructing the Shell Assembler

    As mentioned above, the Part II manual consists of complete listings of the two movements of the assembler. Movement 1 is 59 pages and 2109 lines; Movement 2 is 34 pages and 1220 lines. These are assembly listings, with the address and generated object code for each instruction printed to the left of the assembler source.

    Transcribing and Bootstrapping the Assembler

    As with other software reconstructions for the 205, I transcribed both source and object code from the listings. This was done for two reasons. First was the typical reason -- once the file was transcribed, the source images could be extracted from it, assembled, and the listing from that assembly compared to the transcription. Differences in the addresses or assembled code should indicate transcription errors. I could then correct the discrepancies and reassemble, iterating until the assembler output matched the transcription.

    Second, and more importantly in this case, the Shell Assembler is written in itself. Thus we have a chicken-and-egg problem -- where do we get the object code to assemble an assembler that is written in itself? By transcribing the object code along with the assembler source, the assembler can be bootstrapped by extracting the object code from the transcription, formatting it into a load tape, and then used to assemble the source.

    I began transcribing in early August 2015 and finished in late October, generally doing a couple of pages a day. Proofing, correction, and the resolution of a couple of frustrating anomalies (discussed below) carried on for a few more weeks. The first successful "round-trip" assembly (assembling the assembler from the source and object code extracted from the transcription, then using the resulting object code to assemble again, with the output of the two assemblies matching) occurred around 20 November.

    Assembly of Movement 1 requires about 26 minutes in the retro-205 emulator. The first pass (Movement 1 being assembled by Movement 1) requires about eight minutes. Its speed is limited by that of the card reader, emulating an IBM 087 collator at 240 cards/minute. The second pass (Movement 1 being assembled by Movement 2) requires about 18 minutes. Its speed is limited by the printer, emulating an IBM 407 tabulator at 150 lines per minute. The card punch (emulating an IBM 523 at 100 cards/minute) is slower than the printer, but only outputs a card every five words of assembled code. Since it is buffered by the Cardatron, its operation is normally overlapped by other processing.

    Assembly of Movement 2 requires about 15 minutes in retro-205. The first pass requires about six minutes, with the second requiring about nine minutes.

    Copies of the latest transcription, assembly listings, and tape and card outputs from assembling both movements are available in the project repository at [8]. The history of transcription and correction is also available in prior commits to that directory of the repository.

    Two utility scripts were written to support the reconstruction of the assembler. They are available in the software/tools/ directory of the project repository:
    • Shell-Xscript-Reformatter.wsf [9]: extracts the source and object code for each movement from their transcribed source files. It creates card decks for each movement in the form required for input to the assembler, and outputs a tape image with the object code formatted as a loadable tape. This was originally written to bootstrap the assembler from the transcription and ultimately do a "round-trip" test.
    • Shell-LoadTapeBuilder.wsf [10]: takes the output tapes from assembling the two movements of the assembler and reformats them into a loadable tape of the assembler object code.

    Problems and Anomalies

    The process of bootstrapping the assembler uncovered a couple of anomalies in the published listings and one very frustrating problem. That problem was encountered during the first assembly attempt: the pseudo-instructions that construct Cardatron format bands were generating errors. For example, consider this sequence of lines starting at sequence 0110 in Movement 1 (page 6 in the Part II manual):
    FMB3  WFB   3¤P10Z¤ & P5AB & P6Z4N3B
                       P6Z4N2B & NB4NB2NB4N3B
                  P5A2B & PAB4AB & P5AB
                       P8ZAB & 2¤P5A¤2B
                       6¤P5A¤ & 20B
    FMB3 is the label for the band data, representing its address in memory. WFB is the "Write Format Band" pseudo-instruction, used to describe how a line of data should be formatted for output to an IBM tabulator. The remainder of the text, continuing on to the next four lines, are the formatting strings themselves. The format band pseudo-instructions will be discussed more fully in Part 2 of this post, but for now accept that the strings between ampersands (&) describe the translation of one word in memory to columns on the tabulator, and the lozenge (¤) brackets a repeating word or group of words.

    The assembler was reporting two errors for this pseudo-instruction (see [7] for that version of the assembly listing):

    Note that the plus sign (+) and ampersand are the same character on the IBM 407 tabulator, as are the right parenthesis ()) and lozenge. Which glyphs print depends upon the type of print wheel that is installed in the tabulator.

    The first error is indicating there is a missing ampersand in the format; the second is indicating that one of the format phrases between ampersands does not account for all 11 digits of a 205 word. Yet those lines are transcribed exactly as they appear in the Part II manual. I spent quite a few hours staring at those lines, reading the discussion of format band generation in Section VI of the Part I manual, and studying the code in Movement 2 that generates the format bands, trying to understand what was wrong.

    Finally in desperation, I decided to let the error message be my guide. Notice that there are no ampersands between phrases on different lines, so I added them at the start of the continued lines. That fixed the problem. Adding an ampersand at end of a line being continued also works.

    With the additional ampersands in place, assembly of Movement 1 still generated errors for format bands FMB6 (format band too long) and FMB7 (wrong number of columns). What's worse, I noticed that the code for these bands in the Part II manual did not match what you would expect from the phrases in the WFB operand coding. For example, the listing in the manual shows this for FMB7:
    0226 1091 3 3333 33 3333 FMB7  RFB   B15¤P5A¤  &  P4Z3AB
    0227 1092 3 3333 33 3333                    P4Z6N19B
    0228 1093 3 3333 33 3333
    0229 1094 3 1313 13 3333
    0230 1095 0 0000 31 3131
    0231 1096 0 0000 00 1111
    0232 1097 0 1111 11 1111
    0233 1098 0 1111 11 1111
    0234 1099 0 1111 11 1111
    0235 1100 0 1111 11 1111
    0236 1101 0 1111 11 1111
    0237 1102 0 1111 11 1111
    0238 1103 0 1111 11 1111
    0239 1104 0 1111 11 1111
    0240 1105 0 1111 11 1111
    0241 1106 0 1111 11 1111
    0242 1107 0 0000 31 3131
    0243 1108 3 3333 33 0000
    0244 1109 3 3333 33 3333
    0245 1110 3 3333 33 3333
    0246 1111 3 3333 33 3333
    0247 1112 3 3333 33 3333
    0248 1113 3 3333 33 3333
    0249 1114 3 3333 33 3333
    0250 1115 3 3333 33 3333
    0251 1116 3 3333 33 3333
    0252 1117 3 3333 33 3333
    0253 1118 3 3333 33 3333
    0254 1119 3 3333 33 3333
    The assembler error is valid -- the phrases specify a format of one blank column, 15 groups of five alphanumeric columns, three alphanumeric columns, another blank column, six numeric columns, and finally 19 blank columns. That is a total of 105 columns, not the 80 required for a Read Format Band (card input) specification. What the generated code appears to represent is a format band specification like this:
    FMB7   RFB     P7Z3N & 10¤P5A¤ & P6Z2A
                         & P4Z6N19B
    That specifies a layout of three numeric columns, 10 groups of five alphanumeric columns, two alphanumeric columns, 6 numeric columns, and finally 19 blank columns, for the correct total of 80 columns.

    There is an additional anomaly in the original listing for Movement 1: at sequence 1826 (page 53 in the Part II manual), the listing shows this:
    1826 2689 0 0000 00 0000 ERR8  ALFS  0006  MEMORY OVERFLOW
    1827 2690 0 4956 55 6200
    1828 2691 0 5356 43 4163
    1829 2692 0 8480 80 8000
    1830 2693 0 6348 41 5500
    1831 2694 0 5456 59 4500
    ALFS is a pseudo-instruction that will encode up to six words (30 characters) of alphanumeric text into the numeric code used by the Cardatron. Alas, if you decode the generated words (they are stored in reverse order to match the way the Cardatron fetched data), they read "MORE THAN 4000 LOCATIONS," not "MEMORY OVERFLOW."

    There are three other anomalies in the listing for Movement 2. At sequence 0111 (page 68 in the Part II manual), the operation code and address are blank:
    0111 1271 0 0000 02 6010 .R    STC               CLEAR A AND TEMP&0003
    From both the comment and the generated code, however, it's clear that line should read:
    0111 1271 0 0000 02 6010 .R    STC   TEMP &0003  CLEAR A AND TEMP&0003

    At sequence 0390 (page 75 in the Part II manual), the operand address is invalidly formed (address increments must start in column 31 on the card, not column 30):
    0390 1550 0 0000 02 6014 .B    STC   TEMP&0007   ZERO TEMP&0007
    The line assembles correctly if the ampersand is shifted to the right by one position:
    0390 1550 0 0000 02 6014 .B    STC   TEMP &0007  ZERO TEMP&0007
    At sequence 0811 (page 87 in the Part II manual), the label field is ".1" but is never referenced. It should be ".A". I discovered this when the operand address assembled for the CNZ instruction two lines above it did not match the listing.

    Having identified these problems and anomalies in the original listing, what should be done about them? I finally decided to do the following:
    • The missing ampersands in the format band specifications may be the result of my old transcription nemesis on this project, suppression of leading zeroes by the 407 tabulator. "Leading zeroes" to the 407 are any characters that do not have a numeric punch in the IBM card code, so that includes the ampersand. In any case, the ampersands need to be there, thus I simply added them on the continuation lines of the format band specifications.
    • The only explanation I can come up with for the problems with FMB6 and FMB7 is that someone cut-and-pasted the listing before reproducing it in the report. The manuals we have are republications by Burroughs of the original Shell Research report, so it is difficult to guess where -- or why -- this change was made. Perhaps a patch to the assembler was released, and only the object code side of the page was updated in the manual. The format band specification phrases are clearly wrong, however, and the generated format band data seems reasonable, so I changed the phrases in the operand field of the pseudo-instructions to match the generated band data.
    • Similarly, the difference between the text and generated code for the ERR8 message is puzzling, but may have the same explanation as for the format bands above. Since the difference is not critical to the assembler's operation, and the error message as documented on page 11 of the Part I manual is "MEMORY OVERFLOW," I left the text alone and allowed the generated code to differ from the original listing.
    • It's possible the three anomalies in Movement 2 were due to transient hardware errors -- I have seen other listings where the 407 clearly printed incorrect characters -- but it is clear in all three cases what the source text should have been, so I changed it to match the generated code.
    Finally, as can be seen from the assembly listing for Movement 2 in the project repository [11], the assembler issued three invalid-pair warnings:
    • At sequence 0311, MTW (Magnetic Tape Write) follows CADA (Clear and Add Absolute). Magnetic tape instructions use the A register, which would thus destroy whatever CADA loaded into A.
    • At sequence 0376, CAD (Clear and Add) follows CADA, which would thus destroy whatever was loaded by CADA.
    • At sequence 0709, BA (Transfer B register to A) follows CAD, which would thus destroy whatever was loaded by CAD.
    It appears that in none of these cases does execution actually fall through from the first instruction to the second. In fact, the first instruction of the pair is never executed in place at all. It is simply a skeleton that is being loaded and modified by the code above it, and then stored for execution elsewhere in the program.Thus, all three of these invalid-pair warnings are benign.

    Using the Shell Assembler

    The assembler was designed to be used with a 205 that had a Cardatron and magnetic tape equipment. The Cardatron required at least one card reader, card punch, and line printer. The assembler required three magnetic tape drives.

    With all of this equipment in play, watching the assembly of a large program, especially one that invokes macros and subroutines from the library, can be quite entertaining. The emulator puts on a classic mainframe show of flashing lights, spinning tapes, and unit record equipment chunking through cards and print lines.

    Operating Environment

    The 205 supported two types of magnetic tape drive, the Model 544 DataReader and Model 560 DataFile. The DataReader was a typical vertically-standing cabinet housing a reel-to-reel drive.

    The DataFile was a semi-random access device that used fifty 250-foot strips of magnetic tape arranged in a series of parallel bins. It had a moving tape head assembly that could quickly select and read or write one of the strips at a time. The recording format for both DataReader and DataFile was the same -- tapes were 0.75 inches wide and supported two six-bit data lanes, only one of which could be read or written at a time. Thus, with 50 tape strips, the DataFile supported 100 lanes and a total of 100,000 blocks (10 million characters) of storage.

    Data was recorded on the tape in fixed, 20-word blocks. These blocks were addressable, and the tape control unit could search for a block on a drive asynchronously while the processor was doing other work. The blocks could also be overwritten in place.

    Between the search and block-overwrite capabilities, both the DataReader and DataFile could be used somewhat like a slow disk drive. In fact, the whole purpose of the DataFile design was simultaneously to increase capacity and reduce seek time, allowing it to be used as a true random-access device. Moving between tapes required 0.5 to 2.0 seconds; average search time along a tape strip was about 15.3 seconds, so average access time to an arbitrary block was about 16.3 seconds.

    That is three orders of magnitude slower than today's disk drives, but about 1.5 orders of magnitude faster than reel-to-reel drives. Morevoer, once the starting block was located, sequential access was much faster -- 46 milliseconds per block. In order to provide efficient processing for large data sets, ElectroData, Burroughs, and their customers developed a number of clever file-handling techniques to minimize seeks and maximize sequential access to these devices.

    The retro-205 emulator does not yet implement the DataFile, but its development is planned, and for now the assembler works fine with the three DataReader tape drives that the standard emulator configuration supports.

    The assembler, as configured in the listings in the Part II manual, assumes Movement 1 starts at block 120 on lane 89 of DataFile unit 0 (also designated as unit 10), with Movement 2 starting at block 290 on that lane. When using a DataReader unit, only the low-order bit of the lane number is significant, so that corresponds to blocks 120 and 270 on lane 1.

    In addition to the load tape on unit 0, the assembler requires scratch tapes on units 1 and 2, which would normally be DataReaders. The assembler also requires the card reader as Cardatron input unit 1, the card punch as Cardatron output unit 2, and the line printer as Cardatron output unit 3. The unit numbers and lane/block locations of the movements can be changed by patching the assembler, as described in Section IX of the Part I manual.

    Overview of Operation

    The assembler is most easily loaded and executed using a one-card bootstrap program, as described in Section XI of the Part I manual. A card image for that program is available in the project repository at [5]. A loadable tape image for the assembler is also available in the repository at [6]. The "===" characters in the first three characters of the bootstrap card specify format-band 6, but also impose reload-lockout on the card reader. This allows the assembler to load and initialize its format bands before the first card of the source deck to be assembled is read. This in turn allows the source deck to follow immediately behind the bootstrap card in the reader. The code for the bootstrap is:
    0000  4 0110 44 7000 CRD  redirect card data to address 7000
    7000  0 8900 42 0120 MTS  search tape 0 for lane 89, block 120
    7001  0 0000 28 7000 CCU  if tape busy, branch to 7000 and retry
    7002  0 0000 40 0900 MTR  read 100 blocks to address 900
    7003  0 0000 28 7002 CC   if tape busy, branch to 7002 and retry
    7004  0 0000 30 0900 CUB  block and branch from 900 to loop 7
    7005  6 0000 20 7000 CU   stop reading bootstrap; branch to 7000
    The first and last instructions on this card, with the 4-bit of their sign digit set, are executed at the time the card is read and are not stored in memory. They are not part of the program the card loads into memory.

    The bootstrap loads Movement 1 from the tape and branches to its entry point at address 0900. Movement 1 reads the source cards, partially assembles them, and writes a 20-word block of data for each card to the scratch tape on unit 1. Any errors detected in that pass are written to the line printer and the Flexowriter. If macros or subroutines are defined or called out from the library, you will see the tape on unit 0 move back and forth as the assembler seeks first to the catalog for the library, then to the lane table, and then to the position for the macro itself in the library.

    By default, the library is located starting at block 0000 on lane 80 (lane 0 on a DataReader), but this can be changed by modifying the lane table at addresses 2880-2899 in Movement 1. Much more efficient operation can be obtained by locating the library near the same block address as the lane table (219) but on a different lane, or on a different tape drive altogether.

    Once Movement 1 senses the END card in the source deck, it rewinds the tape on unit 1. Then it loads Movement 2 into memory from tape unit 0 and branches to its entry point at address 1200. The symbol table and other data developed by Movement 1 remain in memory at addresses 0000-1150 and 3000-3999. The second movement reads the partially-assembled instructions from tape unit 1, resolves addresses, generates Cardatron format bands, writes an updated block for each assembled word to the tape on unit 2, lists each assembled instruction to the printer, and outputs the assembled code, five words per card, to the card punch. Any errors detected during this movement are written to the Flexowriter.

    At the end of Movement 2, the assembler outputs a checksum for the assembled program and the word "LOAD" on the Flexowriter. It then attempts to read one digit from the Console input device (normally the Console numeric keypad).
    • If you enter a digit 1-9 at the Console, the assembler rewinds unit 0 and reads 15 blocks (300 words) from lane 89, block 0 to address 3700. From the comments in the assembler listing, this was intended to load an operating system named "SLIM" and transfer control to it. We have no further information on SLIM, which was probably something developed and used locally by Shell Research.
    • If you enter a zero digit, the assembler will clear main memory and from tape unit 2 load the program just assembled. It will then rewind unit 0 and read 15 blocks as described above.

    To run the assembled program from the deck punched by the second movement, there is a loader program detailed in Section XI of the Part I manual for the five-per-card format punched by the assembler.

    Detailed Operating Instructions

    To run the assembler in the retro-205 emulator, perform the following steps. See [12] for detailed instructions on operating the Cardatron and card equipment and [13] for instructions on operating the tape drives.
    1. On the Supervisory Panel, make sure the LOCK/NORMAL and CONTINUOUS/STEP switches are both in the down position.
    2. Load magnetic tape unit 10 (same as unit 0) with the load tape image for the assembler. You can use the tape image in [6]. Place the unit in REMOTE status.
    3. Load magnetic tape units 1 and 2 each with blank tapes and place them in REMOTE status. 
    4. On the Control Console, make sure the OUTPUT switch is set to the PAGE (Flexowriter) position.
    5. On the Control Console, make sure the INPUT switch is set to the KEYBOARD position.
    6. On the Cardatron Control Unit, click the GENERAL CLEAR and then INPUT SETUP buttons in that order. The ORDER field of the C register will show 44 for a card-read instruction.
    7. On card reader unit 1:
      • Make sure FORMAT SELECT is "By Col" and FORMAT COL is set to 1.
      • Load the bootstrap card image into the reader. You can use the image in [5].
      • Load the card deck for the program to be assembled after the bootstrap card.
      • Click the reader's START button. The orange lights will flash and stop with RLO, FLO, FS4 and FS2 lit, indicating Read Lockout, Format Lockout, and format band 6 selected.
    8. On the Control Console, click the CONT (Continue) button. The tape on unit 0 should spin and load Movement 1. The reader should start reading cards, and tape unit 1 will move as the card images and partially-assembled instructions are written to it.
    9. At the end of the first movement, tape unit 1 will rewind and tape unit 0 will spin to load Movemenent 2.
    10. During Movement 2, tape units 1 and 2 will move as the partially-assembled instructions are read from unit 1 and finished instructions are written to unit 2. The program will be listed on the line printer and the object code will be output to the card punch
    11. At the end of Movement 2, tape units 1 and 2 will rewind. The Flexowriter will print the program checksum. followed by the word LOAD. The KEYBOARD annunciator on the Control Console with light. At this point you have three choices:
      • Halt the computer by pressing STOP on the Control Console.
      • Key the digit 0 on your keyboard to run the program just assembled. Make sure the Control Console window has the focus when you do this, otherwise the keystroke will not be recognized. The program will be loaded from magnetic tape unit 2. At the end, unit 2 will rewind and the Flexowriter will print the highest and lowest addresses loaded into memory. Tape unit 0 will then seek to lane 89, block 0 and read 15 blocks into address 3700 (presumably to load the SLIM operating system as discussed above). Finally, the program will attempt to read a card into address 6000.
      • Key any digit 1-9 on your keyboard. Likewise make sure the Control Console window has the focus first. This will skip loading the program just assembled and simply cause tape drive 0 to seek to block 0, read 15 blocks to address 3700, then attempt to read a card, as above.
    Stay tuned for Part 2 of this post, which will discuss the source record layout and programming features of the Shell Assembler.


    [1] "Knuth's EASY Assembler":

    [2] "Knuth's Algol-58 Compiler":

    [3] Shell Symbolic Assembly Program for the Burroughs 205, Part I, Burroughs Corporation, Bulletin 3038, March 1960:

    [4] Shell Symbolic Assembly Program for the Burroughs 205, Part II, Burroughs Corporation, Bulletin 3038, March 1960:

    [5] One-card bootstrap program to load and execute the Shell Assembler:

    [6] Loadable tape image of the Shell Assembler for the retro-205 emulator:

    [7] Movement 1 assembly listing from 2015-10-27, showing format band errors and other anomalies:

    [8] Latest commit of Shell Assembler files to the retro-205 repository:

    [9] Utility script to extract source and object code from the assembler transcription files:

    [10] Utility script to convert the output tapes from assembling both movements of the assembler into a loadable tape:

    [11] Assembly listing of Movement 2 of the assembler:

    [12] "Using the retro-205 Cardatron":

    [13] "Magnetic Tape for the retro-205 Emulator":

    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:
    1. It should be as close as possible to standard mathematical notation.
    2. It should be possible to use it to describe computing processes in publications.
    3. 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&
    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 (nFnB), 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:
    2X1=X + Y + 3.14.X + 7.98/Z + (X-Y).(X+Z)$
    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:




    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




                            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

                            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.
    1. On the Supervisory Panel, make sure the LOCK/NORMAL and CONTINUOUS/STEP switches are both in the down position.
    2. 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.
    3. On the Control Console, set the INPUT switch to the KEYBOARD position.
    4. On the Control Console, click the CLEAR button, then the STEP button. The KEYBOARD annunciator on the Console should light.
    5. 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.
    6. On the Control Console, click CLEAR again, then the CONT button. The KEYBOARD annunciator on the Console should light.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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:
    1.  On the Supervisory Panel, make sure the LOCK/NORMAL and CONTINUOUS/STEP switches are both in the down position.
    2. Load magnetic tape unit 5 with the loadable tape image of the compiler available from [8]. Place the unit in REMOTE status.
    3. Load magnetic tape unit 1 with a blank tape. Place the unit in REMOTE status.
    4. On the Control Console, set the INPUT switch to the KEYBOARD position.
    5. On the Control Console, click the CLEAR button, then the STEP button. The KEYBOARD annunciator on the Console should light.
    6. 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.
    7. On the Control Console, click CLEAR again, then the CONT button. The KEYBOARD annunciator on the Console should light.
    8. 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.
    9. 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.


    [1] "Preliminary Report - International Algebraic Language," A.J. Perlis, K.Samelson, Communications of the ACM, volume 1, number 12, December 1958, pp. 8-22:

    [2] "Revised Report on the Algorithm Language ALGOL 60," P. Naur, ed., Communications of the ACM, volume 6, number 1, January 1963, pp. 1-17:

    [3] "Knuth's EASY Assembler":

    [4] Knuth's Algol-58 compiler listing donated to the Computer History Museum:

    [5] Index to Knuth documents available at the Computer History Museum: http://archive.computerhistory.org/resources/text/Knuth_Don_X4100/PDF_index/KnuthDigitalArchive-Index.html

    [6] Tom Sawyer's Datatron 205 web site:

    [7] Tom Sawyer's transcription of the dump of the "Burroughs Algebraic Compiler" tape:

    [8] Loadable tape image of Tom Sawyer's compiler tape dump transcription:

    [9] Corrected transcription of Knuth's compiler listing [4] donated to the Computer History Museum:

    [10] Corrected card deck extracted from the transcription [9] of Knuth's compiler listing:

    [11] Listing of the Algol-58 compiler from assembly of the corrected card deck [10]:

    [12] Script to apply leading-zero suppressing to MEASY assembly listings:

    [13] Magnetic tape image of object code producted by MEASY from assembly of [10]:

    [14] "Magnetic Tape for the retro-205 Emulator":

    [15] "Using the retro-205 Caratron":

    [16] Small sample Algol-58 program prepared by Tom Sawyer:

    [17] Compile listing produced by the recovered compiler for [16] with object code annotations:

    [18] Sample Algol-58 program taken from Appendix C of the Burroughs Algebraic Compiler for the 205 Programmer's Manual:

    [19] Compile listing produced by the recovered compiler for [18]:

    [20] Compile listing produced by Tom Sawyer's compiler for [16]:

    [21] Compile listing produced by Tom Sawyer's compiler for [18]:

    [22] Comparison of object code for the recovered compiler and Tom Sawyer's transcription:

    [23] "Compiling Programs on Paul Kimpel's B205 Emulator":

    [24] "The Internals of Algol 205," Donald Knuth, ca. 1960:

    [25] The Burroughs Algebraic Compiler for the 205 Programmers Manual, Bulletin 3041, Burroughs Corporation, Pasadena, California, February 1961:

    [26] Object code card deck generated by compiling [16] with the recovered compiler: