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 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 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 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 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 solution, proposed 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. 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 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, thirteen people from seven countries in Paris from 11 to 16 January 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 24 August 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; afterwards Zonneveld shaved off his beard and Dijkstra kept his. 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 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. 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 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 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, a mechanism that could produce behavior surprising to the unwary but allowed certain elegant 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, 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.

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 SETL and ALGOL 68. 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, 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