ALGOL: the language of academia

ALGOL introduced concepts that are an integral part of nearly every language since – but it never stood a chance against FORTRAN.

Unless you’ve studied computer science, you probably won’t have heard of ALGOL. It was designed by a committee of scientists, half from the US Association for Computing Machinery (ACM), and half from the German Gesellschaft für Angewandte Mathematik und Mechanik (GAMM). They met in Zurich in 1958, with the grand intention of designing a universal computing language. The preliminary post-meeting report called this language IAL (International Algebraic Language); it was officially renamed ALGOL about a year later. The first ALGOL 58 compiler was implemented by the end of 1958.

ALGOL 58 was fairly basic. It did introduce the basic idea of a compound statement: a block of statements, surrounded by begin…end, which can be treated as a single statement. This works particularly well with control structures such as loops and if/then structures. However, ALGOL 58 was soon superseded by ALGOL 60, which is the version of ALGOL we’ll look at here. It came from a design meeting in Paris in 1960, consisting of seven scientists from Europe and six from the USA, described by Alan Perlis as “exhausting, interminable, and exhilarating”.

Here are some of ALGOL’s characteristics:

• Block structure: the ability to create blocks of statements that control the scope of both variable assignments (local vs global) and control statements (if blocks, loops, functions, etc). This is a feature of pretty much all subsequent languages.
• Two methods of passing parameters to subroutines (functions): call by value (where all arguments are evaluated before being passed into the function) and call by name (where the arguments are evaluated in the function itself).
• If/then/else statements and an iteration control statement. FORTRAN did have some if statements and a do loop in 1957, and some machine languages had versions of it too. However, the ALGOL version was broader, less limited; FORTRAN’s was initially only arithmetic-based.
• Recursion: a program or function could call itself. (FORTRAN didn’t have this officially until 1977.) According to reports from the 1960 committee, recursion was to some extent snuck in the definition against the preferences of part of the committee.

Peter Naur, Turing Award winner (although he prefers Backus Normal Form to Backus-Naur Form). CC BY-SA 3.0

ALGOL had some initial popularity with research scientists, but less so commercially, due partly to the lack of I/O functions and partly to the fact that few of the big computer vendors were interested in it. IBM had been heavily pushing FORTRAN, and there were already a significant number of FORTRAN programs floating around for people to build on. ALGOL’s problems may also be a reflection of the fact that it was designed by academics, with no real effort made to make it easy to understand, although it is very clear if you are familiar with the necessary mathematical and logical concepts. (In comparison, FLOW-MATIC and later COBOL were designed to be accessible for non-scientific users.)

However, there were machines that ran ALGOL. Burroughs machines in particular were designed to run ALGOL well (in particular their own Extended ALGOL version), and there are still ALGOL-friendly machines running today. A couple of current ALGOL programmers, both using Unisys Clearpath mainframes, popped up on a Stack Overflow thread in 2012, so at least as of two years ago it was active in the wild.

ALGOL 68 was intended to be a successor to ALGOL 60, but in practice it was more like a complete rewrite. It is much more complex than ALGOL 60 (and was criticised by some of the design committee, including Edsger Dijkstra, for this). It is sufficiently different that it is treated as a separate language; “Algol” in general refers to versions of ALGOL 60.

The structure of a language is determined by its grammar: the set of rules describing what is permitted in the language. Backus-Naur form was developed in order to describe ALGOL 60, but also as a notation to describe any grammar for any language. Most of it was created by John Backus (who was responsible for the team who developed FORTRAN), but it was improved for ALGOL 60 by Peter Naur. Since then it is nearly always used to formally specify the rules for a language. Every rule is given like this:

name ::= expansion

This means that name can be expanded into, or replaced by, expansion (they are defined to be the same).

Here’s an example from the first version of BNF:

<number&rt; ::=<digit&rt; |<number&rt; <digit&rt; <digit&rt; ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

The | sign means ‘or’, so the first line means that any number is defined as an digit, or any number followed by a digit. The second line defines a ‘digit’. So this means that a number consists of any number of digits. Here’s another example from the K&R definition of C:

type_qualifier :== ‘const’ | ‘volatile’

This means that a type qualifier can be either const or volatile. (This is from C89; two more types now exist.)

Grammars are useful partly because they provide a formal definition of a language, so there’s no room for disagreement or ambiguity. This in turn makes it possible in many cases to mechanically build parsers and compilers. Extended BNF (which includes the ?, *, and + operators to represent different sorts of repeated value) is used to define even more different protocols and data formats.

Our Hello World program written and compiled. Note the “dummy statement” warning about that final semi-colon.

Running ALGOL and Hello World

To compile ALGOL 60 on a modern Linux machine, your best bet is the GNU project Marst, which is an Algol-to-C translator. You’ll need to get it from a GNU mirror (see its webpage – www.gnu.org/software/marst) as it doesn’t seem to be packaged for at least the Linux distributions I checked.

Once it’s downloaded and unpacked, you should be able to compile and install it from the unpacked directory with

./configure; make; make install

By default this installs things in /usr/local/ (check the configure options if you wish to change this). Edit your $PATH if Marst doesn’t find the executable. You may also need to edit $LD_LIBRARY_PATH if it is blank:

$ echo $LD_LIBRARY_PATH $ export LD_LIBRARY_PATH=/usr/local/lib $ echo $LD_LIBRARY_PATH /usr/local/lib

First up, as ever, Hello World:

comment This is a Hello World example; outstring(1, “Hello world!n”)

The begin and end lines do what you expect. comment treats all the following characters as a comment (across multiple lines if need be) until it encounters a semi-colon. In general, ALGOL statements end with a semi-colon, but the last one before the final end need not.

As mentioned above, the original ALGOL 60 spec did not include I/O functions. Various compilers solved this problem with their own library functions; outstring seems to have come from IBM, and was officially included in the modification of ALGOL 60 published in 1976. outstring uses an I/O channel, of which there are 16, to provide input and output. 0 is always stdin and 1 (as here) is always stdout. Others must be assigned to files.

To compile and run this code takes several steps, as you need to translate it into C, then compile the C with reference to the relevant libraries:

$ marst hello.alg -o hello.c $ gcc hello.c -lalgol -lm -o hello $ ./hello Hello world! $

Version 1 of the Archimedes program narrowing the range down. A neater way to do this might be to edit the values of a and b in a single procedure, without returning a value at all:

Mini program

Here’s another test program to get the idea of how things are structured:

integer N, M; N := 12; begin integer procedure oneton(N); value N; integer N; begin integer i; for i := 1 step 1 until N do begin outinteger (1, i); outstring (1, “n”); end loop; onetoten := (N * 2); end oneton; M := oneton(N); outinteger(1, M); end all;

You’ll get even more “unlabelled dummy statement” warnings this time, again due to ‘unnecessary’ semicolons. My experience was that trying to remove these warnings just meant more time spent bug-hunting every time I edited the code and the necessity of the semi-colons changed. Feel free to edit them out if you disagree.

Here’s some of the aspects of ALGOL you’ll see in the code:

• The first two lines (declaring global variables) can also be moved to just before the M := onetoten(N); line. However, the code fails to compile if you have those lines between the second begin and the procedure definition.
• Assignment is the := operator. Variables must have a type before they can have a value assigned to them.
• You need begin…end around the main body of the code as well as around the full program.
• Similarly, procedure code (operational code, after the variable declarations) needs a begin…end enclosure. This is what allows ALGOL to treat multiple statements as a single procedure (function) block.
• The line integer procedure oneton(N) defines a procedure which returns an integer, is called oneton, and takes a single parameter, N.
• The value keyword specifies that we are passing these parameters in by value; that is, they are evaluated and then passed into the procedure. (The other option is to pass by name, in which case they are evaluated within the procedure; see next section.) In either case, the parameter’s type (eg integer) must also be specified.
• The for loop syntax is straightforward, but for multiple lines, once again you need begin…end wrapping to create a block.
• To call, and get a return value from, a procedure, create a variable and assign the procedure to it.
• outinteger does the same thing for integers as outstring does for strings. (There’s also outreal.)
• Anything after end is treated as a comment. This means you can put labels on your end lines (eg end foo; to help you remember where you are in the code. I found this useful when bugfixing.

Finding pi

This next piece of code uses the method Archimedes developed of finding π, by drawing a polygon just around a circle, a polygon just inside the unit circle, and using these as an upper and lower bound on the circumference of the circle.

The bounds are expressed like this (2πr being the circumference of a circle, and an the side length of the n-sided polygon drawn outside the circle):

an > 2πr > bn

If you start with a unit circle r = 1, so a and b provide bounds for 2π .

To calculate a and b, we use an iterative formula, starting with a6 and b6 which represent hexagons drawn outside and inside a unit circle. These values are easy to calculate and come out at 4√3 and 6. The iterative formulae are:

a2n = (2anbn) / (an + bn) b2n = √ (a2nbn)

So we start with a hexagon (n = 6), and double the number of sides in each round, getting steadily closer and closer to a true circle.

Here’s a program that does the calculation:

begin real a, b, anext, bnext; a := 4 * sqrt(3); b := 6; begin real procedure archimedesa(a, b); value a, b; real a, b; begin archimedesa := (2 * a * b) / (a + b); end archimedesa; real procedure archimedesb(anext, b); value anext, b; real a, b; begin archimedesb := sqrt (anext * b); end archimedesb; integer i; for i := 1 step 1 until 10 do begin anext := archimedesa(a, b); bnext := archimedesb(anext, b); a := anext; b := bnext; outreal(1, (a / 2)); outstring(1, “ > pi > “); outreal(1, (b / 2)); outstring(1, “n”); end loop; end all;

As in the previous section, we declare our global variables first, and then start the main body of the code. There are two procedures, one to calculate the next value of a, and one doing the same for b, both of which return a real value. The for loop then repeats the iterative procedure 10 times, printing the results each time.

real a, b; a := 4 * sqrt(3); b := 6; begin procedure archimedes(a, b); real a, b; begin a := (2 * a * b) / (a + b); b := sqrt (a * b); end archimedes; procedure archprint; begin outreal(1, (a / 2)); outstring(1, “ > pi > “); outreal(1, (b / 2)); outstring(1, “n”); end archprint; integer i; for i := 1 step 1 until 10 do begin archimedes(a, b); archprint; end loop; end all;

This time, instead of calling by value (with the value keyword), we pass parameters into the archimedes procedure using call-by-name. This means that instead of evaluating a and b and passing the evaluation into the procedure, we pass the actual variables. This means that we can edit the variables within the procedure itself and these changes will propagate globally rather than just locally. (This is exactly the sort of side effect that functional programming seeks to avoid.)

The procedure archprint accesses the same global variables in a slightly different way; instead of being passed in, it simply uses the fact that they are global variables to access them by name.

Version 2: passing by name.

Afterword

ALGOL 60 truly feels like a giant step forwards for the time; a language that pioneered ideas that have become an intrinsic part of how we code. In many ways, however popular FORTRAN might have been, it took years for it to really catch up to ALGOL from a theoretical point of view. (Unfortunately, beauty and elegance are not always the most important factors when making a choice of coding language; being able to compile it has to come first, and availability of libraries is also important. Both of which factors ALGOL fell down on.)

It would be nice to know what would have happened to ALGOL if it had lasted as long as FORTRAN; but perhaps ALGOL 68 demonstrates that the purity of an academically-designed ‘universal language’, and the practicalities of writing code across many different machines, were always going to clash sooner or later.

Juliet Kemp is a scary polymath, and is the author of Apress’s Linux System Administration Recipes.