What was wrong with Algol?

When I started my study at the Eindhoven University of Technology, most computing was done on a Burroughs B7900 mainframe, that used Burroughs Extended Algol as its system programming language. We were taught Pascal though, but older students still wrote programs in Algol, that had fewer restrictions than Pascal and had a complex data type (complex numbers) too.

Algol-60

Algol started originally in 1958, mostly as a language to publish algorithms in (for example in scientific papers). Algol-60 became the version that was most popular and that everyone thinks of when you refer to Algol.

Algol had block structures for IF-THEN-ELSE and FOR-loops (but no simple while loop) and it had procedures with local variables and parameters. These procedures could be recursive, as opposed to the ones in FORTRAN.

Algol-60 had a few limitations though:

• In had only three data types: INTEGER, REAL and BOOLEAN, plus arrays of these. There was no character data type and there were no records or pointers. There was something as a string data type, but the only thing you could do was pass literal strings around to a function that would print them. There was no way to manipulate character strings.
• It defined no standard I/O functions, so this was not portable in any way.
• Like Pascal, it offered no modularity. A program was a standalone entity. But the order in which you declared variables and procedures was less rigid than that of Pascal.
• The set of control structures was very limited, keeping the evil GOTO statement necessary.
• But the biggest drawback was the call-by-name convention. In most languages, such as Pascal, you either pass parameters to a procedure by value (it is an input parameter to the procedure) or by reference (the procedure is allowed to modify whatever variable you pass to it). In Algol-60 you had the choice between pass by value and pass by name. Pass by name meant that the expression passed as an actual parameter, had to be re-evaluated each time it was used inside the procedure. For simple variables this made no difference, but for an array element, the expression that specified the index could depend on variables that were modified inside the called procedure. This was inefficient to implement, requiring mini-subroutines for each of the pass-by-name parameters. These had to be provided by the caller, so the called procedure could call them back. It was also very hard to analyse programs that used it in a nontriviial way. You could do really clever things with it though. Call by name was more of an unintended ramification of a definition than the desired behaviour of the language.

Burroughs Extended Algol was a full-fledged system programming language with all the data types you would want. The mainframe operating system was written in it and the language was very much extended compared to Algol-60. And as far as I know, they left out pass by name and implemented pass by reference instead.

Algol-68

Algol-68 was very much different from Algol-60. You cannot meaningfully consider these mere versions of the same language.

For one thing, it ditched call-by-name and replaced it with pass-by-reference. It added many more data types:

• Characters and strings.
• structs and unions. The keywords struct and union were carried over to the C language, along with the keyword void, meaning no value.
• References (which were pointers). There was dynamic allocation on the heap too.
• Complex numbers
• Flexible arrays.
• semaphores, to be used with parallel statements.

It had a very versatile slicing syntax for arrays and (unlike Python), it also supported multi-dimensional arrays.

It had versatile control structures, including one for parallel execution, an extensive standard I/O library and special syntax for formatted I/O. And you could also overload operators, define entirely new operators and specify the priority of each operator. C++, Ada and Python also have operator overloading, but none of them allows you to change operator priorities.

But Algol-68 still had no modules and separate compilation. A program was still a single source text.

The syntax and semantics of Algol-68 were complex and very few implementations existed at the time. Full implementations were even rarer. At the university we had books about the language, but no working compiler. We only got an open-source implementation for Linux in 2005 with Algol-68 Genie https://jmvdveer.home.xs4all.nl/en.algol-68-genie.html

Some features of the language were hard to implement. The language required garbage collection for objects allocated on the heap and parallel execution was its own can of worms.

The biggest stumbling block, however, was the grammar of the language. Other languages are specified by context-free grammars, in particular in the Backus-Naur Form (https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form). These grammars are easy to comprehend and there are tools to help create parsers for them.

The drawback of context-free grammars is that they do not accurately specify what programs are legal. The context-free grammar specifies fore example that an expression can contain an identifier (variable name) consisting of letters and digits, starting with a letter, but it does not specify that a variable with that name must be declared earlier in the program.

The grammar of Algol-68 on the other hand, does specify exactly which programs are legal. The grammar contains two levels: at one level you specify what production rules you can create and at another level you specify what programs you can create using those production rules you just created. A context-free grammar has just one static set of production rules to create a program. Algol-68 has a customised set of production rules for every set of variables and procedures you declare.

Algol-68 is not particularly hard to comprehend per se, nor is it particularly hard to parse (compared with other complex languages like C++ and Ada), but comprehending the specification and using the two-level grammar to base a parser on, that is very hard indeed.

That stupid octal dump program in Unix, that’s the reason why in Bourne shell, the “do” loops are terminated with “done” instead of “od”. The “if”-statements are terminated with “fi” and “case” statements with “esac”. those keywords come directly from the Algol-68 control structures. “od” terminates loops in Algol-68, but that would conflict with the name of the octal dump program, so it was not practical to use that as a keyword in the shell.