PL history: lambda calculus through the 1970s

17 Sep 2026. This page is the 13 Sep synthesis of an external research run. The Mo it describes — brace syntax, effect rows, a Rust implementation, a package registry, an RFC process — was never Mo’s design. Mo’s decisions are the spec chapters under spec/design-v0/ and the decision-log. Read this page as landscape only.

Headline

Forty years of foundational work that still governs modern language design. The 1930s formal systems (lambda calculus, Turing machines) determined what a language could be; the 1950s produced the first high-level languages; the 1960s and 1970s created every paradigm we still argue about.

Three findings that shape everything

  • Every idea Mo will consider was invented before 1980. Type inference, garbage collection, first-class functions, algebraic data types, structured concurrency, capability-based security, homoiconicity, ownership — all originated in this window. What has changed is execution: implementation techniques, ecosystem practices, and the compute we can spend on verification.
  • The Curry–Howard correspondence is the deep secret. Types are propositions, programs are proofs. Every language that takes verification seriously (Lean, Rust with formal semantics, Idris, Dafny, F*) is drawing on this 1930s–60s theoretical stack.
  • Backwards compatibility eats languages. ALGOL 68 killed ALGOL. PL/I killed IBM’s mainframe language story. Wirth kept remaking Pascal → Modula → Oberon rather than accreting features — a discipline Mo should imitate.

Era 1: Theoretical foundations (1930s–1950s)

  • Lambda calculus (Church, 1930s) — function abstraction + application + variable substitution. Turing-complete without a machine model. Every functional language descends here (Wikipedia: Lambda calculus).
  • Turing machines (Turing, 1936) — the machine model. Church–Turing thesis: both formalisms compute the same thing.
  • Curry–Howard correspondence origins — Curry (1930s) and Howard (1969) formalize the isomorphism between logic and computation.
  • Von Neumann architecture (1945) — the substrate. Every imperative language is a notation for it.

Era 2: First high-level languages (1954–1962)

  • FORTRAN (Backus, 1954–57) — first widely used compiled language. Scientific computing.
  • LISP (McCarthy, 1958) — symbolic, list-based, homoiconic. See lisp.
  • COBOL (Hopper et al., 1959) — business computing, English-like syntax, still runs the world’s payroll.
  • ALGOL 60 — the reference language of the era. Block structure, recursion, formal syntax (BNF). Never dominant in industry; hugely influential in design.

Era 3: The 1960s and early 1970s paradigm explosion

  • ALGOL 68 — everything in one language. A cautionary tale in kitchen-sink design.
  • Simula 67 (Dahl & Nygaard) — classes and inheritance. Ancestor of every OO language.
  • BCPL → B → C — the systems-programming lineage that led to Unix. See c.
  • Pascal (Wirth, 1970) — teaching language, LL(1) parseable, disciplined.
  • PL/I (IBM) — attempted to unify FORTRAN + COBOL + ALGOL. Overreached spectacularly.
  • SNOBOL — string processing; ancestor of regex culture.

Era 4: The 1970s functional and OO branches

  • Smalltalk (Kay, Ingalls, Goldberg at PARC, 1972) — objects, messages, live image. See smalltalk.
  • Prolog (Colmerauer, Kowalski, 1972) — logic programming. Still used in constraint solvers and NLP.
  • Scheme (Sussman & Steele, 1975) — the minimalist Lisp. First-class continuations, tail calls.
  • ML (Milner, 1973) — type inference invented here to make LCF theorem-prover tactics safe. See ml.
  • Forth (Moore, 1970) — stack-based, extensible, still lives in bootloaders and space probes.

Cross-cutting themes

  • “GOTO Considered Harmful” (Dijkstra, 1968) — structured programming becomes orthodoxy.
  • The software crisis (NATO conference, 1968) — the profession admits it does not know how to build large systems.
  • Wirth’s Law — software gets slower faster than hardware gets faster. First articulated here, still true.
  • Compiler technology — lex/yacc, table-driven parsing, single-pass vs multi-pass debates.
  • Memory management — Lisp had GC in 1959; C shipped without one in 1972. The split has never healed.

What Mo takes from this era

  • Static typing with algebraic data types — the ML lineage, refined (d11-statically-typed, d22-rust-plus-refinements-types).
  • First-class functions and closures — from lambda calculus, made practical by Scheme.
  • Structured programming — no goto, block-scoped, disciplined control flow (d04-style-rules-become-laws).
  • Immutability as default — the LISP tradition, now widely accepted (d10-immutable-by-default).
  • Small, teachable core — the Wirth discipline. Mo aims for a spec small enough to hold in one head (or one agent context).

What Mo refuses

  • Inheritance-based OO — Simula’s legacy is the wrong abstraction for the AI era (d06-never-oop).
  • Kitchen-sink design — no ALGOL 68, no PL/I, no C++ growth curve.
  • Dynamic typing as default — LISP’s flexibility is an agent-hostile substrate.

Sources