06 · Languages & Compilers

This chapter is the floor where instructions stop being addressed to a machine and start being addressed to people — and where a program is written to be read.

What makes a text mean something to a machine?

When John Backus's group at IBM began work on FORTRAN, the job was estimated at six months. In his own history of the project, Backus records that the six-month figure "remained the interval-to-completion until it actually was completed over two years later, in April 1957." The delay is not the interesting part. What everyone expected the result to be is. Backus recalled that "it is difficult to convey ... the strength of the skepticism about 'automatic programming'" and about "its ability to produce efficient programs"; his team's stated goal was only to "produce programs almost as efficient as hand coded ones" (Backus, The History of FORTRAN I, II, and III). Almost. The premise of the field was that a machine could not read a human notation and produce good code, and that premise was not stupid. Nothing about meaning looks mechanical.

The first move that made it mechanical was to cut meaning in two. Syntax is the question of whether a text is well formed; semantics is the question of what it does. They are not even the same kind of question. Backus described the syntax of a proposed international algebraic language in 1959 using a notation of rules and alternatives; Peter Naur adapted it for the ALGOL 60 report, and Donald Knuth's 1964 letter to CACM proposed the name it still carries, Backus–Naur Form (Knuth, 1964). With a formal grammar, "is this a valid program" stops being a matter of judgment and becomes a decision a program can make. ALGOL 60 was the demonstration, and Tony Hoare's verdict is the most quoted line in 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" — from his 1973 keynote "Hints on Programming Language Design", not, as is usually claimed, his Turing lecture.

Semantics resisted the same treatment, and the compiler's answer was not to solve meaning but to descend it — one small, exact step at a time. A compiler is a tower inside the tower. Lexical analysis turns characters into words. Parsing turns words into a tree that reflects the grammar. Semantic analysis annotates that tree with what the names refer to and whether the operations are permitted. Then the tree becomes an intermediate representation belonging to no particular language and no particular machine; optimization rewrites it into a cheaper one with the same meaning; and code generation emits the instruction set of chapter 04. Each stage exists because it hands the next one a representation in which the next one's job is easy — which is this book's whole thesis, performed in miniature inside a single program. The intermediate representation earns its keep with arithmetic: without it, supporting n languages on m machines takes n × m compilers; with it, n + m.

What languages built on that machinery offer is a set of ways to name things — functions, types, modules, objects — each of which exists to let a reader ignore something. The most compressed illustration is LISP. In April 1960 John McCarthy published a paper defining computation over symbolic expressions, including a function called eval that described what it means to evaluate any expression in the language (Recursive Functions of Symbolic Expressions, CACM 3, no. 4). It was mathematics, meant for reading. Then Steve Russell hand-compiled eval into IBM 704 machine code (McCarthy, History of Lisp), and the definition of the language became an interpreter for the language. That is chapter 04's stored-program idea coming due: because a program is data, a description of a language is a program that runs it.

Types are the sharpest of the naming mechanisms, because a type is a promise a machine can check. Declaring that a function takes an integer and returns a string is a claim about every possible execution, verified before any execution happens — the only part of programming where you get a guarantee rather than a test result. The guarantee is narrow but real: when Gao, Bird and Barr took public JavaScript bugs, checked out the code just before each fix, added type annotations by hand, and asked whether a type checker would have complained, both Flow and TypeScript caught 15 percent of them (To Type or Not to Type, ICSE 2017). Read that carefully: it is not "15 percent of bugs are type errors," but 15 percent of bugs that had already survived testing, review, and release. Push the idea far enough and it stops being about bugs. The Curry–Howard correspondence, observed by Haskell Curry in the 1930s and stated by William Howard in a 1969 manuscript titled "The Formulae-as-Types Notion of Construction," says that types are propositions and programs are proofs of them. A type checker is a small automatic theorem prover most programmers use daily without noticing.

Which raises the question of why there are so many. The HOPL database, maintained since 1995, catalogued 8,945 of them as of August 2026. The proliferation is not waste. A language is a bet about which mistakes are worth preventing and which repetitions are worth naming, and those bets are genuinely different for an operating system kernel, a statistical model, and a web page. Alan Perlis put the useful test in his 1982 Epigrams on Programming: "A language that doesn't affect the way you think about programming, is not worth knowing." What has not survived is the 1957 fear. Compilers routinely beat competent hand-written assembly, and superoptimizers now beat compilers: STOKE, searching randomly from unoptimized code for equivalent rewrites, matched or outperformed the best output of production compilers (Schkufza, Sharma & Aiken, ASPLOS 2013). Backus's team asked for almost as good, and lost that bet in the most agreeable direction.

The people on this floor had a habit of turning on their own work. Backus received the Turing Award in 1977 and used the lecture to attack the model FORTRAN entrenched, titling it "Can Programming Be Liberated from the von Neumann Style?" — published in CACM the following August. Grace Hopper's A-0 system of 1951–52 is often called the first compiler; it functioned closer to a loader, and the more consequential work was FLOW-MATIC, whose English-like verbs passed almost intact into COBOL and put readable text into commercial programming for good. She retired from the US Navy in 1986 as a rear admiral, in the habit of handing visitors a length of wire just under a foot long — the distance light travels in a nanosecond — so that they would stop treating wasted time as free.

Connections

Below this chapter, 04 supplies the instruction set the back end emits into, and 05 the process abstraction a compiled program is loaded into. Chapter 01 sets the ceiling: because the halting problem is undecidable, no compiler can decide in general whether an optimization is safe in every case, which is why real optimizers are conservative by construction. Above, chapter 07 asks which of these naming mechanisms keep large systems changeable over years, and chapter 12 raises the possibility that the next notation people write in will not be a programming language at all.

Open questions

If a model can produce working code from an English description, what is a programming language for — specification, verification, or only review? Types demonstrably catch real defects, so why does a large part of the industry still decline them, and is the honest answer about evidence or about cost? And what would a language look like that was designed for programs to read rather than write?

Go deeper

• Alfred V. Aho, Monica S. Lam, Ravi Sethi & Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Addison-Wesley, 2006 — the "dragon book," still the standard treatment of the pipeline.
• John Backus, "The History of FORTRAN I, II, and III," ACM SIGPLAN Notices 13, no. 8 (1978) — a founder's account of proving his field's skeptics wrong.
• John McCarthy, "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I," Communications of the ACM 3, no. 4 (1960): 184–195 — a language defined, not implemented, and implemented anyway.