ALGOL: The Language That Taught Programming How to Teach Itself

Zusammenfassung

ALGOL — the ALGOrithmic Language — was designed by an international committee in 1958 and revised in 1960 into a form so elegant and influential that it effectively defined what a programming language should look like for the next sixty years. It introduced block structure, recursive procedures, and a formal grammar for describing language syntax. ALGOL never achieved commercial dominance, lacking a standard I/O system and IBM’s backing. But nearly every major programming language since — Pascal, C, Java, Python — descends from it directly. For related language history, see John Backus and FORTRAN, Dennis Ritchie and the C Language, and The Rise of High-Level Languages.

The Problem with FORTRAN and COBOL

By 1957, FORTRAN existed — the first practical high-level programming language, John Backus’s masterpiece at IBM. By 1959, COBOL was in development, targeting business data processing. Both were significant achievements, and both had a fundamental problem from the perspective of the international scientific and academic computing community: they were American and proprietary.

FORTRAN was IBM’s language, designed for IBM hardware, distributed by IBM, and evolving according to IBM’s commercial priorities. COBOL was a US Department of Defense initiative, developed largely by American contractors. European researchers, increasingly dependent on computers for scientific computation, were building programs in a language they did not control and could not modify.

The solution, proposed simultaneously by the American ACM (Association for Computing Machinery) and the European GAMM (Gesellschaft für Angewandte Mathematik und Mechanik), was to design a truly international algorithmic language through a joint committee — a language that would belong to the mathematical community rather than to any company or government.

The committee convened in Zurich in May 1958. The eight Americans and eight Europeans — including John Backus (IBM), Alan Perlis (Carnegie Mellon), Friedrich Bauer (Munich), and Hermann Bottenbruch (Stuttgart) — met for a week and produced the IAL (International Algebraic Language), soon renamed ALGOL 58. The initial design was a significant achievement: a block-structured language with a cleaner syntax than FORTRAN, a stronger type system, and — for the first time — a formal definition rather than just an informal description.

Peter Naur and the Invention of Formal Grammar

ALGOL 58 was a start, but it had a critical deficiency: it was described in natural language, which left ambiguities in its interpretation. Different implementations made different choices where the specification was unclear, producing programs that behaved differently on different machines. The committee recognized that a programming language needed a more rigorous definition.

The second ALGOL committee meeting, in Paris in January 1960, produced the design that would define the language’s legacy. The Revised Report on the Algorithmic Language ALGOL 60, edited by Peter Naur of Denmark, was a document of extraordinary intellectual clarity. Naur’s key contribution was adopting and extending a notation developed by John Backus for describing language syntax: a system of rules that precisely specified what sequences of characters constituted valid programs.

This notation — now called Backus-Naur Form (BNF) — used a simple metalanguage to describe the grammar of ALGOL 60. A rule like <if statement> ::= if <Boolean expression> then <unconditional statement> specified exactly what an if-statement was in terms of its component parts, each of which was in turn defined by other rules. The entire language syntax could be described in a few pages of BNF rules, leaving no ambiguity.

BNF was not Backus’s original invention — similar formalisms had appeared in Chomsky’s work on formal grammars — but Backus’s practical notation, refined by Naur, became the standard tool for describing programming language syntax. It is still used today, in every language specification, every compiler textbook, every parser generator. The IETF uses it to define internet protocol message formats. JSON’s syntax is defined in a variant of BNF. The notation outlived the language it was invented to describe.

Backus-Naur Form in Practice

BNF notation uses ::= to mean “is defined as,” angle brackets for non-terminal symbols (things that need further definition), and pipe characters for alternatives. The rule <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 says that a digit is any of the numerals zero through nine. <integer> ::= <digit> | <integer><digit> says that an integer is either a single digit or an integer followed by a digit — a recursive definition that captures numbers of arbitrary length. This ability to use recursive definitions gave BNF the power to describe arbitrarily complex language structures concisely.

ALGOL 60: The Language Itself

ALGOL 60 introduced several features that were genuinely new to practical programming languages and have been standard ever since.

Block structure was perhaps the most fundamental. An ALGOL program was organized into blocks — sections of code delimited by begin and end keywords. Variables declared within a block were local to that block; they came into existence when the block was entered and ceased to exist when it exited. Nested blocks could access variables from enclosing blocks, but not vice versa. This was lexical scoping: the scope of a variable was determined by the structure of the program text, not by the runtime execution order.

Lexical scoping is so natural to modern programmers that it is difficult to appreciate what it replaced. FORTRAN had no block structure; variables were either local to a subroutine or global (COMMON blocks). The lack of nesting and scope meant that large programs were hard to decompose and easy to accidentally corrupt through shared variable names. ALGOL’s blocks made programs easier to reason about: you could look at a block and know exactly which variables it could affect.

Recursive procedures followed naturally from block structure. If a procedure was a block, and blocks could call other blocks, then a procedure could call itself. FORTRAN explicitly prohibited recursion. ALGOL embraced it. The ability to write a factorial function that called itself, or a tree traversal that recursed into subtrees, was not just a convenience — it aligned programming with mathematical induction and made a large class of algorithms expressible naturally.

Call-by-name and call-by-value were two distinct parameter-passing mechanisms, and ALGOL offered both. Call-by-value passed a copy of the argument, insulating the caller’s variable from modification. Call-by-name was more exotic: the argument expression was substituted textually into the procedure body and re-evaluated every time the parameter was accessed — a mechanism that could produce behavior surprising to the unwary but allowed certain elegant idioms. Jensen’s Device, a technique for using call-by-name to simulate array operations, became a standard example of ALGOL’s expressive power and its capacity for subtle bugs.

Free-format syntax meant that programs could be written with indentation and line breaks chosen for readability rather than mandated by column positions (as in FORTRAN) or fixed-field formats (as in COBOL). ALGOL programs looked like mathematics, which was intentional: the language was designed for scientists and mathematicians who thought in equations.

The Influence on Every Language That Followed

ALGOL never won the commercial language wars. IBM, which dominated the computer market of the 1960s, did not back it. The language defined no standard input/output operations, which was a practical problem but also a philosophical choice — I/O was hardware-specific and the designers wanted ALGOL to be hardware-independent. In practice, this meant that programs using ALGOL for I/O used non-standard vendor extensions, limiting portability. FORTRAN remained dominant for scientific computing. COBOL dominated business computing. ALGOL existed primarily in research and academic settings.

But the influence it exerted on subsequent language design is nearly impossible to overstate.

Pascal (1970), designed by Niklaus Wirth — who had been a member of the ALGOL working groups — was essentially a cleaned-up ALGOL with standard I/O and a strong type system, designed explicitly for teaching structured programming. Pascal dominated computer science education through the 1970s and 1980s.

C (1972), Dennis Ritchie’s language at Bell Labs, drew heavily from BCPL and B, both of which descended from CPL, which was influenced by ALGOL. C adopted ALGOL’s block structure and lexical scoping while adding pointer arithmetic and shedding type safety — a deliberate tradeoff for systems programming flexibility.

Simula (1967), developed by Ole-Johan Dahl and Kristen Nygaard in Norway, extended ALGOL 60 with classes and objects — the first object-oriented language, and the direct ancestor of Smalltalk, C++, Java, and every subsequent OO language.

Java (1995) descends from C++ which descends from C which descends from ALGOL. Python descends from ABC which was influenced by Pascal and ALGOL. JavaScript is syntactically C-derived. The block structure, lexical scoping, and recursive procedures of ALGOL 60 are the common heritage of the dominant programming paradigm.

ALGOL 68 and the Committee Disaster

The ALGOL design process also produced a cautionary tale about language design by committee. ALGOL 68, published in 1968, was the work of an expanded international committee that attempted to build a far more powerful and general language than ALGOL 60.

The ambition was admirable. ALGOL 68 introduced orthogonal design principles, operator overloading, parallel processing constructs, and a type system of extraordinary generality. The language could express things ALGOL 60 could not, and its formal definition was impeccably complete.

The problem was complexity. ALGOL 68 was so difficult to understand — even for experts — that the language report was practically unreadable. Edsger Dijkstra resigned from the design committee and published a devastating critique: “With respect to ALGOL 68, I have to say something that I find hard to say but that I feel compelled to say: I think that this is a language the development of which should be stopped.” C.A.R. Hoare was equally blunt, observing that the language combined features with mutual interactions so complex that no programmer could keep them in mind simultaneously.

ALGOL 68 was implemented (in Leningrad, of all places, where a complete compiler was built) and had a small but passionate user community. It never achieved significant adoption. The contrast between ALGOL 60’s elegant simplicity and ALGOL 68’s baroque complexity became a standard lesson in language design: a language’s power is not measured by how many features it has, but by how well its features work together.

The Revised Report as a Document

The Revised Report on the Algorithmic Language ALGOL 60, published in 1963 in the Communications of the ACM, is arguably the most influential single document in programming language history. It was small — about 17 pages — and described a complete programming language with precision and economy that has rarely been matched since.

Wirth, who had been involved in the ALGOL working groups, praised its clarity of design. Hoare, whose QUICKSORT algorithm was first published as an ALGOL program, wrote of ALGOL 60 in his 1973 essay “Hints on Programming Language Design”: “Here is a language so far ahead of its time that it was not only an improvement on its predecessors, but also on nearly all its successors.”

That the language it described was used for perhaps fifteen years, while the notation it introduced (BNF) and the concepts it established (block structure, lexical scope, formal language specification) have lasted sixty years and will last sixty more, is not a paradox. The impact of an idea is not measured by the commercial success of its first implementation.

Alan Perlis, who had chaired the original Zurich committee and went on to become CMU’s first computer science department head, received the first ACM Turing Award in 1966 — the award’s inaugural year. His citation was, simply, “for his influence in the area of advanced computer programming techniques and compiler construction.” ALGOL was the primary referent.