Skip to content

ALGOL: The Language That Taught Programming How to Teach Itself

Abstract

ALGOL (the ALGOrithmic Language) was designed by an international committee in 1958 and revised in 1960; the 1960 version set the template that most later programming languages followed. 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 or through intermediaries. 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, developed by John Backus’s team at IBM. By 1959, COBOL was in development, targeting business data processing. Both worked, but for the international scientific and academic computing community they had one problem: they were American and proprietary.

FORTRAN was IBM’s language, built for IBM hardware and changed according to IBM’s commercial priorities. COBOL was a US Department of Defense initiative, developed largely by American contractors. European researchers were building programs in a language they did not control and could not modify.

The European side had started early: after a meeting of GAMM in Darmstadt in October 1955 that discussed programming languages, a GAMM subcommittee with Friedrich Bauer, Klaus Samelson, and Heinz Rutishauser set out to define one. In June 1957, the ACM set up an ad hoc committee of its own. GAMM wrote to ACM president John Carr in October 1957 proposing a joint effort, and in April 1958 Bauer presented the GAMM proposal to the ACM committee in Philadelphia. The American ACM (Association for Computing Machinery) and the European GAMM (Gesellschaft für Angewandte Mathematik und Mechanik) agreed on a joint committee to design an international algorithmic language that would belong to the mathematical community rather than to any company or government.

The committee convened in Zurich in May 1958. Four Americans (from the ACM) and four Europeans (from GAMM), including John Backus (IBM), Alan Perlis (Carnegie Tech), Friedrich Bauer (Munich), and Hermann Bottenbruch (Darmstadt), alongside Charles Katz, Joseph Wegstein, Heinz Rutishauser, and Klaus Samelson, met at ETH Zurich from May 27 to June 2, 1958, and produced the IAL (International Algebraic Language), renamed ALGOL the following year (Perlis found IAL “unspeakable” and pompous). By the end of 1958, the Zuse Z22 at the University of Mainz had an ALGOL 58 compiler, and from spring 1959 Peter Naur edited the ALGOL Bulletin for the discussion that followed. The initial design had a cleaner syntax than FORTRAN and a stronger type system, and it introduced the compound statement, though only for control flow: blocks that tied begin/end to the scope of local declarations came with ALGOL 60.

Peter Naur and Backus-Naur Form

ALGOL 58 had one serious flaw: 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, thirteen people from seven countries in Paris from January 11 to 16, 1960 (IBM paid the hotel), produced ALGOL 60. The Report on the Algorithmic Language ALGOL 60, edited by Peter Naur of Denmark and published that May (a Revised Report followed in 1963), was a document of unusual clarity, fourteen pages plus two of index. The first compiler for it ran on August 24, 1960 on the Electrologica X1 of the Mathematical Centre in Amsterdam, written by Edsger Dijkstra and Jaap Zonneveld, who had vowed not to shave until it worked; afterward Zonneveld shaved off his beard and Dijkstra kept his. The Centre’s computing department had been run since January 1, 1947 by Adriaan van Wijngaarden, a mechanical engineer from Delft who had hired Dijkstra in 1952 and was one of the thirteen in Paris; he became director of the Centre in 1961 and held the post for twenty years. 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. Rules like <if clause> ::= if <Boolean expression> then and <if statement> ::= <if clause> <unconditional statement> specified exactly what an if-statement was in terms of its parts, each of which was in turn defined by other rules. A few pages of BNF rules described the entire syntax without 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. Variants of it are still used in language specifications, compiler textbooks, and parser generators. 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. <unsigned integer> ::= <digit> | <unsigned integer><digit> says that an unsigned integer is either a single digit or an unsigned 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.

The ALGOL 60 Language

ALGOL 60 introduced several features new to practical programming languages that 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 did not allow recursion. ALGOL did. A factorial function that called itself, or a tree traversal that recursed into subtrees, 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. This could surprise the unwary, but it allowed some compact idioms. Jensen’s Device, which passed an expression such as a[i] together with its index variable i by name so that one summation procedure could sum any formula, 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, ALGOL programs that did I/O relied on non-standard vendor extensions, which limited portability. FORTRAN remained dominant for scientific computing. COBOL dominated business computing. ALGOL existed primarily in research and academic settings.

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.

Dennis Ritchie built C (1972) at Bell Labs on BCPL and B. Both descended from CPL, which drew on ALGOL. C kept ALGOL’s block structure and lexical scoping, added pointer arithmetic, and gave up type safety to give systems programmers more freedom.

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 SETL and ALGOL 68. JavaScript is syntactically C-derived. The block structure, lexical scoping, and recursive procedures of ALGOL 60 are now common to nearly every mainstream language.

ALGOL 68 and the Committee Disaster

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

ALGOL 68 introduced orthogonal design principles, operator overloading, parallel processing constructs, and a very general type system. The language could express things ALGOL 60 could not, and its formal definition, written in Adriaan van Wijngaarden’s two-level grammar, was complete.

The problem was complexity. ALGOL 68 was so difficult to understand (even for experts) that the language report was practically unreadable. Peter Naur and Niklaus Wirth resigned from the working group shortly after the May 1968 Zurich meeting where a late draft was discussed. WG 2.1 adopted the design anyway at a stormy Munich meeting in December 1968, and a Minority Report, based on a draft by Edsger Dijkstra, was signed by Dijkstra and seven other members, among them C.A.R. Hoare, Brian Randell, and Mike Woodger; the Minority Report appeared in the ALGOL Bulletin in March 1970 and concluded that “as a tool for the reliable creation of sophisticated programs, the language was a failure.”

ALGOL 68 was implemented: the first working compiler, ALGOL 68-R, came from the Royal Radar Establishment at Malvern in July 1970, followed by others including a Leningrad compiler and ALGOL 68C at Cambridge. It kept a small, loyal user community but never achieved significant adoption. The contrast between ALGOL 60’s simplicity and ALGOL 68’s complexity became a standard lesson in language design about piling up features.

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.

Hoare, whose Quicksort was first published in 1961 as an ALGOL 60 procedure (CACM Algorithm 64), 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.”

The language it described saw active use for perhaps fifteen years. The notation it introduced (BNF) and the concepts it established (block structure, lexical scope, formal language specification) are still in use more than sixty years later.

Alan Perlis, a leading figure on the original Zurich committee and founding head of the computer science department at Carnegie Tech, received the first ACM Turing Award in 1966. His citation was, simply, “for his influence in the area of advanced computer programming techniques and compiler construction.” The citation is generally read as a reference to his ALGOL work.

📚 Sources