Before there were programming languages

Inference rules · Gentzen, 1935. Writing a logical argument as rules, with the assumptions above a line and the conclusion they justify below. The rules this book uses to define evaluation take their shape from this format, worked out in logic before there were programs to run.
Syntax and semantics · Notation reference

The λ-calculus · Church, 1936. A model of computation built from nothing but functions: definition, application, substitution. It predates electronic computers entirely, and yet every language with first-class functions is a descendant.
First-class functions

Symbolic notation for machine orders · Britten and Booth, Coding for A.R.C., 1947. Write a letter for an operation instead of a number, and let a program work out the bits — among the earliest documented cases of bookkeeping handed from the programmer to the machine. On the EDSAC the same idea was designed into the instruction encoding: an operation’s bit pattern was the teleprinter code of its letter.
From machine code to high-level languages

Relocation, and the subroutine library · Wheeler’s Initial Orders 2 for the EDSAC, September 1949; Wilkes, Wheeler, and Gill, 1951. Adjust a routine’s addresses as it is loaded, and the routine stops caring where it lands — which is what lets code be written once and kept in a catalogue. The forerunner of the assembler, in 42 orders.
From machine code to high-level languages

1950s — abstraction arrives

“Automatic programming” · Hopper’s A-0, 1952. A program that assembles a program, argued for on the economics of programmer time. The early automatic-programming systems ran five to ten times slower than hand-coding, which is why the argument had to be had at all.
From machine code to high-level languages

Fortran · Backus and team, 1954–1957. The first widely used high-level language, and the first serious argument that a compiler could generate code good enough that humans need not write assembly. It shipped with an optimizing compiler because nothing less would have been accepted and widely used.
From machine code to high-level languages

Lisp · McCarthy, 1958. Programs as data, functions as values, garbage collection, recursion as the primary control structure. Also the origin of dynamic scope — largely an artifact of how the first interpreter resolved variables, later understood as a bug rather than a design.
First-class functions · Static vs. dynamic scope

Algol 60 · international committee, 1960. Block structure, nested scope, and the BNF grammar notation used to define it — the moment syntax itself became something you specify formally rather than describe in prose. Also the moment a language became a document, defined by a committee report before any compiler for it existed. Algol 58 came first and was likewise settled by committee ahead of any implementation, and its begin/end grouped statements without declaring names; however, the block and formal syntax definition were introduced in Algol 60.
From machine code to high-level languages · Syntax and semantics · Environments and let

1960s–70s — structure, objects, and types

Simula 67 · Dahl and Nygaard. Classes, objects, and inheritance, invented to simulate real-world systems — objects were a modelling idea before they were a software-engineering one.
Structs with methods · Traits vs. inheritance

“Go To Statement Considered Harmful” · Dijkstra, 1968. The argument that unrestricted jumps make programs impossible to reason about, and the case for structured control flow.
Conditionals and loops

Type inference · Hindley 1969, Milner 1978, Damas–Milner 1982. You need not write types down for a checker to know them; the principal type can be computed.
Function types and polymorphism

Pascal · Wirth, 1970. Static typing as a discipline for ordinary programmers, and a generation of students taught that the compiler catches your mistakes.
Why types?

C · Ritchie, 1972. Written so that an operating system need not be coded in assembler, and classed among the high-level languages of its day; it is now routinely called low-level. What constitutes a high-level language moved, while little about C itself changed.
From machine code to high-level languages

de Bruijn indices · 1972. Replace variable names with their binding distance, and shadowing and renaming problems disappear. A choice about representation, made below the level of the language itself — the surface syntax need not change at all.
Environment representations and lookup

Prolog · Colmerauer and Roussel 1972; Kowalski’s “logic as a programming language” 1974. State what holds, let the machine search for what follows.
Declarative programming · Unification

Smalltalk · Kay, Ingalls, and colleagues, 1972–1980. Everything is an object, computation is message-passing, and the language is inseparable from its live environment.
Dispatch and encapsulation

CLU · Liskov and colleagues, 1974–1977. Abstract data types with enforced encapsulation, plus early iterators and exception handling — much of what “modularity” now means.
Sum and product types · Error handling

Scheme · Steele and Sussman, 1975. Lexical scope done right, closures as first-class values, and proper tail calls. The repair of Lisp’s dynamic-scope accident, and the direct ancestor of the scope semantics this book builds.
Closures · Static vs. dynamic scope

ML · Milner and colleagues, from 1973. Type inference, algebraic data types, pattern matching, and the slogan this book’s Part VI is organized around: well-typed programs don’t go wrong.
Soundness, informally · Pattern matching

1980s — semantics, logic, and fixpoints

Hope · Burstall, MacQueen, Sannella, 1980. Algebraic data types and pattern matching as a language’s primary way of building and taking apart data.
Sum and product types

Operational semantics · Plotkin’s structural operational semantics (1981) and Kahn’s big-step “natural semantics” (1987). The notation this book uses to specify every feature before building it.
Syntax and semantics · Program semantics · Notation reference

Datalog · named in the early 1980s. Prolog’s declarative core minus function symbols, which guarantees termination — exactly the choice this book’s relational sublanguage makes.
Declarative programming

Semi-naïve evaluation · Bancilhon and others, mid-1980s. Compute a least fixpoint without re-deriving what you already know: only consider facts new in the previous round.
Evaluating relations: the least fixpoint

Linear logic · Girard, 1987. A logic where assumptions are consumed when used. Decades later this becomes the theory behind ownership and borrowing.
Appendix A · Why types?

1990s–2000s — the modern settlement

Haskell · committee, from 1990. Purity and laziness taken seriously enough to find out what they actually cost.
Programming functionally · Evaluating function calls

Java · 1995. Static types, garbage collection, and single inheritance with interfaces for the mainstream — and, in time, the standard exhibit for the costs of classical inheritance.
Traits vs. inheritance

Gradual typing · Siek and Taha, 2006. A principled account of how typed and untyped code can coexist in one program, and what the boundary between them must cost.
Dynamic and gradual typing

2010s — composition over hierarchy

Go · 2009, and Rust · 1.0 in 2015. Both reject classical inheritance in favour of composition plus interfaces/traits. Rust additionally makes ownership a checked, substructural discipline — linear logic arriving in a production language.
Traits vs. inheritance · Appendix A

TypeScript · 2012. Gradual typing at industrial scale, layered onto a language never designed for it.
Dynamic and gradual typing

Ideas without a single date

Cost semantics · abstract cost models that count reduction steps rather than seconds, making “how expensive is this program?” a question about the semantics instead of the hardware.
Cost semantics

Dynamic scope’s deliberate survivors · exception handlers, thread-local variables, Emacs Lisp’s defvar, and effect handlers all resolve at the call site on purpose. Dynamic scope failed as a language-wide default while remaining the right semantics in the small.
Static vs. dynamic scope