The ALGOL 60 Report — Defining a Language by Its Grammar

Thirteen representatives from Denmark, England, France, Germany, Holland, Switzerland and the United States met in Paris from 11 to 16 January 1960. The Report on the Algorithmic Language ALGOL 60, edited by Peter Naur, appeared in Communications of the ACM that May (volume 3, number 5, pages 299–314).

What the report left behind was less a programming language than a template for how a programming language is defined.

From ALGOL 58 to ALGOL 60

Its predecessor was the preliminary report drafted at the 1958 Zurich conference, published twice: as ACM's Preliminary report — International Algebraic Language (1958) and as the Numerische Mathematik version edited by A. J. Perlis and K. Samelson (1959). It is usually called ALGOL 58, or IAL.

Implementation conferences followed in Europe, and the ALGOL Bulletin, which Naur edited from Regnecentralen in Copenhagen, became the forum. Misunderstandings that surfaced at the June 1959 ICIP conference in Paris led to a decision to hold an international meeting in January 1960 to settle a final report. Seven European and seven American representatives were selected. One of the Americans, William Turanski, was killed by an automobile shortly before the conference; the report is dedicated to his memory, and thirteen people met in Paris.

Naur had written a completely new draft from the preliminary report and the preparatory meetings' recommendations before the conference opened, and the conference adopted it as the basis for its work, then argued item by item. The report describes its own process in one line: "The present report represents the union of the Committee's concepts and the intersection of its agreements."

Three levels of language

The report begins by splitting the language into three:

The definition, the human-readable notation and the machine-readable notation are separated from the first page. The now-routine attitude that a specification is a distinct object from any of its implementations is written into the structure here.

Metalinguistic formulae — later BNF

Section 1 of the report opens flatly: "The syntax will be described with the aid of metalinguistic formulae." It then defines the notation itself. Sequences of characters enclosed in angle brackets are metalinguistic variables whose values are sequences of symbols; ::= and | (the latter meaning or) are metalinguistic connectives; any mark that is neither a variable nor a connective denotes itself; juxtaposition denotes juxtaposition of the sequences.

The whole of the language is then written out in that notation:

<basic symbol> ::= <letter>|<digit>|<logical value>|<delimiter>
<digit> ::= 0|1|2|3|4|5|6|7|8|9

A footnote names the source: J. W. Backus, The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM conference, ICIP Paris, June 1959. John Backus had built the notation to describe ALGOL 58; Naur reworked it for ALGOL 60.

The name took four more years to settle. In the December 1964 Communications of the ACM, Donald Knuth published a short letter proposing that "Backus Normal Form" be dropped in favour of Backus Naur Form, for three reasons: it credits both Backus and Naur, it preserves the familiar abbreviation BNF, and it stops calling a Form a Normal Form. His technical point was that any context-free language admits infinitely many BNF grammars, so the notation is not a normal form in the mathematical sense at all. The proposal stuck.

Write a language's syntax as a set of formal rules rather than as prose. That single move opened the way to parsing theory and to compiler generators. Grammars shipping alongside JSON, HTTP and Rust today are downstream of this report's habit.

Blocks and scope

The other centre of the report is the block. Section 4.1.3 states the principle in one sentence: "Every block automatically introduces a new level of nomenclature."

The rules follow from it. An identifier occurring within a block may be declared local to it, which means (a) the entity that identifier denotes inside the block has no existence outside it, and (b) any entity the same identifier denotes outside is completely inaccessible inside. Identifiers used but not declared in a block are non-local: they denote the same entity inside the block and in the level immediately outside. Since a block may itself contain blocks, local and non-local are understood recursively.

That is lexical scope. Name collisions are settled by a rule of the language rather than by convention or a naming discipline. Mark a declaration own and its value survives leaving and re-entering the block — the static variable, in its original form.

And a procedure can call itself. Recursion went into the specification very late in the conference, reportedly against the wishes of some of the committee.

Thin commerce, enormous influence

ALGOL 60 did not take the market. Its users were mostly research computer scientists in the United States and Europe, and the reasons for the thin commercial uptake are not mysterious: the report defines no input or output, and the large computer vendors were not interested. I/O procedures were not folded in until IFIP Working Group 2.1 produced the Modified Report in 1975.

What ALGOL 60 did become was the standard notation for publishing algorithms. The first implementation was written in August 1960 by Edsger W. Dijkstra and Jaap A. Zonneveld for the Electrologica X1. CPL, PL/I, Simula, BCPL, B, Pascal and C are all, in varying degrees, its descendants.

Who actually said it

The most quoted remark about ALGOL 60 runs: "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."

It is not Perlis's line. C. A. R. Hoare wrote it in the annotated reading list at the end of Hints on Programming Language Design, Stanford Artificial Intelligence Laboratory Memo AIM-224 (STAN-CS-73-403), December 1973, in the entry for the ALGOL 60 report itself. In the same entry he singles out the report's introduction of all the main program-structuring concepts, the simplicity and clarity of its description, its refusal to abbreviate syntax names, and its inclusion of examples in every section. Perlis was one of the thirteen; he was not the author of this sentence.