The ALGOL Compiler

The Elliott 803 had an excellent compiler for the then new ALGOL 60 programming language. ALGOL 60 was one of the first "block structured" languages and was hugely influential on just about everything that has come since. For more information on ALGOL 60 itself try Wikipedia http://en.wikipedia.org/wiki/ALGOL.

These notes contain the following sections:

• Elliott ALGOL Notes
• Running ALGOL Programs
• Sample Programs
• Contributed Programs

Elliott ALGOL Notes

The Elliott ALGOL compiler was an almost complete implementation of ALGOL 60, however there were a few limitations and some changes from the defined reference language. In no particular order:

• The limited telecode character set meant that all keywords and variables had to be in uppercase only and many of the special symbols used in ALGOL were not available. The unavailable symbols were replaced with various symbol and letter sequences, for example:

  GR		for		>
  DIV		for		÷
  NOTEQ		for		≠
  **		for		↑	... and several others
  Three particularly important (but slightly odd) substitutions are:
  ' (apostrophe)		for		; (semicolon)
  £ (GB pound sign)		for		‘ (open string quote)
  ? (question mark)		for		’ (close string quote)

• All ALGOL programs must start with a title followed by an apostrophe.
• The final END keyword must be followed by an apostrophe.
• All identifiers are distinguished only by their first 6 characters.
• All labels used must be declared in a SWITCH statement
• In a block, all variable declarations must come before any procedure declarations
• There were special PRINT and READ statements to perform I/O to and from the tape punches, tape readers and output teletype.
• ... and several others

As an example here's a simple program in the ALGOL reference notation and in the Elliott format:

 begin integer i;  real x;  
       real array y[1:12];
      
       i := 1;  x := 0;
   s1: y[i] := sin((x/180 x 3.14159);
       comment No I/O functions are defined in ALGOL;
       i := i + 1;  x := x + 30;
       if i ≤ 12 then go to s1;      
 end

 CALCULATE SOME SINE VALUES'
 BEGIN INTEGER I'  REAL X'  
       REAL ARRAY Y(1:12)'
       SWITCH SS := S1'
       I := 1'  X := 0'
   S1: Y(I) := SIN(X/180 * 3.14159)'
       PRINT X, SAMELINE, £ SIN(X)=?, Y(I)'
       I := I + 1'  X := X + 30'
       IF I LESSEQ 12 THEN GOTO S1'
 END'

Running ALGOL Programs

To run ALGOL programs on the Elliott 803 you must first load the ALGOL compiler. The compiler was supplied as two large reels of paper tape - tape 1 was the compiler itself and tape 2 was a set of run-time routines used by both the compiler and the executing program. Getting everything to fit in 8K of store was something of a miracle and large programs would often need to overwrite some of the compiler space when they ran, requiring the compiler tapes to be loaded again before the next program could be run. Loading, and particularly re-winding, those large reels of tape was a slow and rather tiresome process - this is something that is much quicker and simpler using the simulator!

Short programs, such as the included samples, were normally run in a "compile, load and go" mode. Once the compiler was loaded, a program source tape was put in the reader and compiled in-store, when compiled it was run and its output was printed to the output teletype. As long as the compiler was not overwritten, further programs could then be compiled and run without the need to reload the compiler tapes.

Loading the Compiler

Use this sequence of operations to load the ALGOL compiler.

1. Place the ALGOL compiler tape 1 in the reader.
   The tape is found in the directory tapes/algol and is called a104-1.tape (A104 was the name of the ALGOL library tapes).
2. Use the console to execute a jump to location 0 to run the initial instructions to load the tape.
3. Wait for the tape to finish loading. You should see it being written to the core store window and you will hear a fairly constant rumbling noise as the tape loads. When complete, the busy light will go out on the reader and a high pitch tone (of around 1kHz) known as a System Wait will be heard.
   Note: When running in real time it will take around 2 minutes 25 seconds to load this tape - it may be sensible to switch out of real time mode while loading the compiler tapes.
4. Place the ALGOL compiler tape 2 in the reader.
   The tape is found in the directory tapes/algol and is called a104-2.tape
5. On the word generator section of the operator console, change the state of the top left-most button (the "Function 1" 40 button) and the second tape should load. (To change the state of the button: if it is already pressed - as it probably will be - release it by pressing the red release key at the far left; if it is already released press it down.)
6. Wait for the tape to finish loading. Again a fairly steady rumbling noise will be heard as the tape loads.
   Note: When running in real time it will take about 1 minute 10 seconds to load this tape.

At this point the system is ready to compile a program. It will be in the System Wait state with a high pitch tone coming from the speaker.

Using a Preloaded Machine Image

As an alternative to loading the two compiler tapes each time they are required it is possible to either start the simulator using a machine image parameter or use the Load... button on the simulation control window to restore a machine image containing a pre-loaded compiler. A pre-loaded compiler image can be found in samples/machines/algol.803.

If the pre-loaded image is used you will need to execute a 40 7 instruction to begin compiling a new program.

Compiling and Running a Program

When the compiler has been loaded it is ready to compile and run programs.

1. Place a program source tape into the reader.
   Pick one of the sample ALGOL programs or choose one of your own.
2. Again change the state of the top left-most button (the "Function 1" 40 button) on the word generator.
   The program source will be read and compiled and a set of fairly random noises will be generated as the tape is processed and compilation takes place. When the first phase of compilation is complete the program title will be printed on the teletype and a short time later, when the second phase is complete a message about the amount of FREE STORE will be printed.

   The program is now in what is known as a Data Wait indicated by a two-tone siren sound coming from the speaker. If the program requires additional data tapes they should be loaded into the readers at this point.

3. This time change the state of the "Function 2" left-most 40 button and the program should run.
   The sample programs will all produce some output on the teletype.
4. When finished an END OF PROGRAM message will be produced on the teletype.

If all went well the system is now back in a System Wait (high pitch tone) ready to compile and run another program. You can repeat from step (1) above.

If things didn't quite go to plan you may need to press the Reset key on the operator console to get control back. You may then execute a jump (i.e. a 40 instruction to one of several locations to continue. The two most useful are probably:

• 40 6 to re-run the last compiled program.
• 40 7 to reset to step (1) above to compile and run a new program.

If things go very wrong the simplest action is to Reset and to reload the whole ALGOL system starting again from Loading the Compiler.

For full details of the compiler (and there is a lot more detail) you can refer to Bill Purvis' scans of the 803 ALGOL Library Program A104 reference manual.

Sample Programs

Hello World

This is a very simple ALGOL "hello world" program. It just prints a short message to the output teletype.

The source code for this program uses only characters from the standard Elliott telecode character set, so it looks exactly like a genuine 803 ALGOL program, with the slight exception that it uses the # (number sign) in place of the £ (GB pound sign), as the GB pound sign can cause problems with PC character encodings. Note that it is all in uppercase and has apostrophes (rather than semicolons) as statement separators and uses the # and ? characters as string quotes. The PUNCH(3) command on the PRINT statement directs the output to the teletype (rather than a tape punch which would otherwise be the default).

Trigonometric Table

This program prints out a table of sine and cosine values for some angles between 0 and 360 degrees.

The source code for the program makes use of the extended mapping from Java system characters to telecode characters provided by the simulator to provide better looking source code. In particular both upper- and lowercase characters can be used (though they are treated identically), semicolons can be used as statement separators (rather than apostrophes) and square brackets can be used for array subscripts. The code also uses the number sign (#) instead of the GB pound sign (£) for the open string quote, for easier use on non UK keyboards.

QuickSort

This program creates a array of small random integers then sorts them into ascending order using the recursive Quicksort algorithm.

The source code for the program also makes use of the extended mapping from Java system characters to telecode characters provided by the simulator to provide better looking source code.

A few comments on the code:

The QuickSort program is a particularly nice example, since the Quicksort algorithm was invented by Tony Hoare and it was the same Tony Hoare who was responsible for much of the implementation of the Elliott 803 ALGOL compiler.

Original QuickSort

This is a variation on the previous Quicksort program but it is coded using the exact algorithms originally published in the Communications of the ACM, Volume 4, Issue 7 from July 1961. These algorithms (number 63 "Partition" and number 64 "Quicksort" from page 321) were published as ALGOL 60 programs, so have simply been copied from the original journal (and re-formatted a little to help with readability).

In addtion this one is written using only Elliott telecode characters, so looks exactly as an original 803 ALGOL source program would look.

Sine and Cosine Plot

This program demonstrates a simple use of the graph plotter to draw approximate sine and cosine functions. The mechanism used to draw lines on the plotter is deliberately done in a very simple manner, but it seems perfectly adequate for this application.

The ELLIOTT() statements are used to insert specific machine code instructions to drive the plotter. The plotter had paper that was 11 inches wide and a pen that could be moved in steps of 1/100 inch in any of 8 directions using special machine instructions:

72 7184		Raise the pen
72 7200		Lower the pen
72 7169		Move one step EAST
72 7170		Move one step WEST
72 7172		Move one step NORTH
72 7176		Move one step SOUTH
72 7173		Move one step NORTH-EAST
72 7174		Move one step NORTH-WEST
72 7177		Move one step SOUTH-EAST
72 7178		Move one step SOUTH-WEST

The Elliott ALGOL compiler included a pre-compiled Plotter Package that would normally be used to drive the plotter. This provided a set of procedures that could be used to set the origin, scale output, draw lines and various other options - including directing the output of PRINT statements to the plotter to add text and labels to graphs. The sample program however does not use the plotter package, mostly because I simply can't remember exactly how it all worked!

Note that the plotFn() procedure in this sample exploits the ALGOL 60 parameter convention of call by name and makes use of a technique known as Jensen's Device to provide the function whose output is to be plotted.

Contributed Programs

These are some rather more complex example ALGOL programs that have been kindly contributed by Bob Firth. Both these programs do a lot of intensive calculation and both will run very much faster if the CPU and Core Store windows are minimized and the Real time option is deselected.

Large Factorials

This will calculate factorials of large integers (e.g. 1000!). The value to be calculated should be provided on a tape placed into reader 2.

Calculation of PI

This will calculate the value of PI to many decimal places (e.g. 1000). The number of places required should be provided on a tape placed into reader 2.