A History of Programming Languages: Theoretical Foundations Through the 1970s
A source-cited survey for a language designer. Covers the mathematical foundations laid in the 1930s, the birth of high-level languages in the 1950s, and the explosion of paradigms in the 1960s and 1970s that still defines the field.
Table of Contents
- Era 1 — Theoretical Foundations (1930s–1950s)
- Lambda calculus
- Turing machines and the Church–Turing thesis
- Combinatory logic and SKI
- Curry–Howard origins
- Post’s rewriting systems
- Von Neumann architecture
- Assembly languages and macro assemblers
- Autocodes at Manchester and Cambridge
- Era 2 — The First High-Level Languages (1954–1962)
- FORTRAN, LISP, COBOL, ALGOL 58/60, IPL, FLOW-MATIC, APT
- Era 3 — Type Systems, Structured Programming, and the ALGOL Legacy (1960s–1970s)
- ALGOL 68, Simula 67, PL/I, BCPL/B/C, Pascal/Modula/Oberon, SNOBOL, LOGO, Smalltalk, “GOTO Considered Harmful”, software crisis, Prolog, Scheme, ML, Forth
- Cross-cutting themes
- Compiler technology, memory management, second-system effect, Wirth’s Law, early type theory
Era 1 — Theoretical Foundations (1930s–1950s)
Lambda calculus (Alonzo Church, 1930s)
Lambda calculus is a formal system for expressing computation via function abstraction, application, and variable substitution; the untyped version is Turing-complete and can simulate any Turing machine and vice versa (Wikipedia: Lambda calculus). It was introduced by the American mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics (Wikipedia: Lambda calculus). Church’s original 1932/1933 system was shown to be logically inconsistent when Stephen Kleene and J. B. Rosser derived the Kleene–Rosser paradox in 1935; Church then isolated and published in 1936 the fragment that concerned only computation — the untyped lambda calculus — and in 1940 introduced a weaker but logically consistent system, the simply typed lambda calculus (Wikipedia: Lambda calculus).
Syntactically, a lambda term is either a variable, an abstraction λx.M (a function of parameter x with body M), or an application M N; the sole computational rule is β-reduction, which substitutes an argument for the bound parameter in the body (Wikipedia: Lambda calculus). The system’s power comes from what it omits — it has no data types, no primitive numbers, no I/O, no assignment; numbers, booleans, pairs, and recursion are all encoded as functions (the Church numerals, Church booleans, the Y combinator), demonstrating that first-class functions plus name binding suffice for all computable functions (Wikipedia: Lambda calculus).
Church used lambda calculus in 1936 to give the first negative answer to Hilbert’s Entscheidungsproblem, proving that no algorithm can decide the equivalence of two arbitrary lambda expressions (Wikipedia: Lambda calculus). This result — obtained months before Turing independently proved the analogous undecidability with Turing machines — established lambda calculus as one of the two founding models of computation (Wikipedia: Alonzo Church).
The simply typed lambda calculus (STLC) that Church published in 1940 assigns each term a type built from base types and the function-type constructor → (Wikipedia: Simply typed lambda calculus). STLC has strong normalization — every well-typed term reduces to a normal form — so it is not Turing-complete, but it forms the kernel of every statically typed functional language and, via the Curry–Howard correspondence, the proof theory of intuitionistic propositional logic (Wikipedia: Simply typed lambda calculus).
Why this matters for a language designer. Every modern language that supports first-class functions, higher-order functions, lexical closures, or type inference inherits its semantics from work Church did before there were computers. Scheme, ML, Haskell, F#, OCaml, Scala, and (via a longer route) JavaScript’s arrow functions, Python’s lambda, C#‘s LINQ, and Rust’s closures all descend, directly or indirectly, from Church’s calculus (Wikipedia: Lambda calculus).
Turing machines and the Church–Turing thesis
Alan Turing introduced his abstract machine model in the 1936 paper “On Computable Numbers, with an Application to the Entscheidungsproblem”, showing that a machine with a finite state control and an infinite tape can compute exactly the functions Church had characterized with lambda calculus (Wikipedia: Turing machine). Turing’s proof of the undecidability of the halting problem, and his construction of the universal Turing machine that can simulate any other, appeared in the same paper (Wikipedia: Turing machine).
The Church–Turing thesis is the empirical/mathematical claim that any function computable by an “effective method” — that is, by any algorithmic procedure a human clerk with paper and pencil could carry out — is computable by a Turing machine, and equivalently by lambda calculus, general recursive functions, or Post canonical systems (Stanford Encyclopedia of Philosophy: The Church–Turing Thesis). The equivalence between lambda calculus and Turing machines was proved by Turing in his 1937 paper “Computability and λ-definability”, which unified two apparently very different characterizations of the computable functions (Stanford Encyclopedia of Philosophy: The Church–Turing Thesis).
For programming languages, the Church–Turing thesis has one enormous consequence: any two Turing-complete languages compute the same class of functions, so choice of language becomes a matter of expressiveness, ergonomics, safety, and performance — not of computational power (Stanford Encyclopedia of Philosophy: The Church–Turing Thesis).
A subtler consequence — and one every language designer eventually collides with — is that Turing completeness is cheap. Any language rich enough to describe general recursion (fixed-point operators, while-loops with unbounded conditions, arbitrary function calls) is already Turing-complete, which means it can express any computable function and any non-terminating computation. Preserving decidability of interesting semantic properties (halting, type checking, program equivalence) therefore requires removing expressiveness, not adding features. Every totally functional language (Coq, Agda, Dhall), every strongly normalizing type system, and every terminating-by-construction DSL is a response to this observation (Stanford Encyclopedia of Philosophy: The Church–Turing Thesis).
Turing was educated at Cambridge and Princeton, working under Church for his 1938 PhD; during the Second World War he broke German naval Enigma at Bletchley Park, and after the war he wrote the specification for the ACE (Automatic Computing Engine) at the National Physical Laboratory, one of the earliest stored-program computer designs (Wikipedia: Alan Turing). Turing’s ACE proposal and von Neumann’s EDVAC draft were essentially concurrent responses to the same design question, and together they shaped the imperative language semantics that dominated the field for the next four decades (Wikipedia: Alan Turing; Wikipedia: Von Neumann architecture).
Combinatory logic — Schönfinkel and Curry
Combinatory logic was invented by Moses Schönfinkel in a 1920 lecture (published in 1924) and independently re-discovered and greatly extended by Haskell Curry from 1927 onward (Wikipedia: Moses Schönfinkel; Wikipedia: Combinatory logic). Schönfinkel’s insight — which we now call currying — was that every function of several arguments can be reduced to a chain of unary functions (Wikipedia: Moses Schönfinkel).
The SKI combinator calculus is a variable-free reformulation of the untyped lambda calculus using just three primitive operators (Wikipedia: SKI combinator calculus):
- I x = x (identity)
- K x y = x (constant)
- S x y z = x z (y z) (generalized application)
Every lambda term can be mechanically translated into an SKI expression, and Turing showed that SKK computes the identity and the combinators together are Turing-complete (Wikipedia: SKI combinator calculus; Wikipedia: Combinatory logic). Because SKI terms contain no bound variables, they were used for a decade in the 1980s as an implementation strategy for lazy functional languages — David Turner’s SASL and Miranda were compiled to combinators, with a G-machine or supercombinator abstraction machine as runtime (Wikipedia: Combinatory logic).
Haskell Brooks Curry (1900–1982), one of the founders of the mathematical field of combinatory logic, spent most of his career at the Pennsylvania State University and Amsterdam; the programming languages Haskell, Brook, and Curry are all named after him, and both currying and the Curry–Howard correspondence carry his name (Wikipedia: Haskell Curry).
Curry–Howard correspondence (origins)
The Curry–Howard correspondence — the “propositions-as-types, proofs-as-programs” isomorphism — has roots in Curry’s 1934 observation that types of the combinators K and S are precisely the axioms of intuitionistic implicational logic (the axioms A → (B → A) and (A → (B → C)) → ((A → B) → (A → C))) (Wikipedia: Curry–Howard correspondence). Curry made the connection more precise in the 1950s together with Feys, and William Alvin Howard extended it to the full simply typed lambda calculus and Gentzen’s natural deduction in an influential unpublished 1969 manuscript that circulated widely before appearing in print in a 1980 Festschrift for Curry (Wikipedia: Curry–Howard correspondence).
Howard’s observation was that STLC types correspond one-for-one to propositions of intuitionistic logic, β-reduction corresponds to proof normalization (cut elimination), and a program of type A is a constructive proof of proposition A (Wikipedia: Curry–Howard correspondence). Extensions of the correspondence led directly to Per Martin-Löf’s dependent type theory (1971 onward), the Calculus of Constructions (Coquand and Huet, 1985), and modern proof assistants like Coq, Agda, Lean, and Idris (Wikipedia: Curry–Howard correspondence).
Emil Post’s rewriting systems
Emil Leon Post (1897–1954) was a Polish-American mathematician who, in his 1920 PhD thesis, proved the completeness and consistency of the propositional calculus of Whitehead and Russell’s Principia Mathematica and introduced truth tables (Wikipedia: Emil Leon Post). Post also invented, in the 1920s, a formalism now called the Post canonical system — a string-rewriting formalism that generates a set of strings from axioms by a fixed set of production rules, and which is Turing-complete (Wikipedia: Post canonical system).
Post’s simplest version — the Post production system — is exactly the substitution rule that shows up in every grammar-based tool: α x β → γ x δ, where lowercase letters are strings and x is a metavariable (Wikipedia: Post canonical system). Chomsky’s phrase-structure grammars, BNF, term-rewriting systems, macro-expansion, and the pattern-based rewrite engines of Prolog and Mathematica all trace to Post (Wikipedia: Post canonical system; Wikipedia: Emil Leon Post). Post also independently arrived at a variant of the Turing-machine model (the Post machine) in 1936, in a paper submitted just before Turing’s (Wikipedia: Emil Leon Post).
Von Neumann architecture and its shadow on language design
The stored-program computer — memory holding both instructions and data, a central processing unit that fetches, decodes, and executes one instruction at a time — was described in John von Neumann’s 1945 First Draft of a Report on the EDVAC and is now called the von Neumann architecture (Wikipedia: Von Neumann architecture). The design consists of a processing unit with an arithmetic-logic unit and processor registers, a control unit with an instruction register and program counter, a memory that stores data and instructions, external mass storage, and input/output (Wikipedia: Von Neumann architecture).
The single memory holding both code and data — as opposed to the “Harvard architecture” that separates them — is what enables self-modifying code, dynamic loading, compilers that write out executables, JITs, and generally the interchangeability of program and data that makes systems like Lisp and Smalltalk possible (Wikipedia: Von Neumann architecture).
For imperative language design the consequences are pervasive: the program counter becomes control flow (goto, if, while); registers become variables; load/store becomes assignment; the call stack (a later addition, not in EDVAC) becomes procedure invocation; and the assumption that instructions execute one-after-another underlies the semantic gap that would later be attacked by dataflow, functional, and logic languages (Wikipedia: Von Neumann architecture). John Backus famously polemicized against this “von Neumann bottleneck” in his 1977 Turing Award lecture “Can Programming Be Liberated from the von Neumann Style?” — the same Backus who had, twenty years earlier, designed FORTRAN as a thin veneer over exactly that machine model (Wikipedia: John Backus).
Assembly languages and macro assemblers
The first assembler is generally credited to Kathleen and Andrew Booth for the ARC2 in the late 1940s; the term “assembler” appears in Wilkes, Wheeler, and Gill’s 1951 book The Preparation of Programs for an Electronic Digital Computer, which described symbolic labels, subroutine libraries, and re-locatable subroutine calls on the Cambridge EDSAC (Wikipedia: Assembly language). An assembler is a one-to-one translator from symbolic mnemonics (ADD, MOV, JMP) to machine code, resolving labels for jump targets and (in later versions) computing relative addresses so that programs can be loaded at different memory locations (Wikipedia: Assembly language).
A macro assembler adds macros — parameterized templates that the assembler expands into a sequence of instructions — allowing programmers to build higher-level abstractions on top of the raw instruction set (Wikipedia: Assembly language; Wikipedia: Macro (computer science)). Macros were the first widely used mechanism for user-defined syntactic extension; the sophistication of the IBM/360 macro facility (with conditional assembly, macro-time computation, and nested expansion) was such that entire structured-programming preprocessors were written as macros (Wikipedia: Macro (computer science)). Lisp’s defmacro, the C preprocessor, Rust’s macro_rules!, and Scheme’s syntax-rules are all descendants of ideas first worked out in 1950s-era macro assemblers (Wikipedia: Macro (computer science)).
Autocodes at Manchester and Cambridge
“Autocode” was the generic 1950s British term for what would soon be called a high-level programming language. The first was written by Alick Glennie at Manchester in 1952 for the Ferranti Mark 1, taking algebraic expressions as input and producing machine code as output — the first “compiler in the modern sense” (Wikipedia: History of compiler construction; Autocodes — J. W. Perry, University of Edinburgh). Glennie’s autocode was, however, so close to the underlying machine that it made few converts (Wikipedia: Autocode).
The Mark 1 Autocode developed by R. A. “Tony” Brooker in 1954 was much more successful: it hid machine registers, offered floating-point arithmetic directly, and became widely used on the Ferranti Mercury and later machines; Brooker’s Mercury Autocode (1957) and Atlas Autocode (early 1960s) refined the design and influenced the ALGOL family (Autocodes — J. W. Perry, University of Edinburgh; Wikipedia: Autocode). The Cambridge Autocode, developed by David Hartley at the Cambridge Mathematical Laboratory for the EDSAC 2 (published 1961) and later for TITAN, was also widely used, particularly for scientific work (Autocodes — J. W. Perry, University of Edinburgh).
The autocodes are important both as engineering precursors of FORTRAN and ALGOL and as a warning: they were largely institution-specific, they did not survive their host machines, and their community was too small to maintain them. They illustrate what happens to a language without a portable implementation and a broad user base — a lesson that FORTRAN, LISP, and COBOL would each solve in different ways.
Era 2 — The First High-Level Languages (1954–1962)
FORTRAN (1957) — John Backus and the first optimizing compiler
FORTRAN — from FORmula TRANslation — was designed by a group at IBM led by John Backus between 1954 and 1957 for the IBM 704 scientific computer; the first FORTRAN compiler was released in April 1957 (Wikipedia: Fortran; IBM: Fortran). The motivating problem was economic: by the mid-1950s the cost of programming a computer had begun to rival the cost of the hardware itself, and hand-writing machine code for scientific calculations was so laborious that computer time was often idle for want of programs (FORTRAN Session — J. Backus, HOPL-I; IBM: John Backus).
Backus later summarized the aim of the project as being “to enable the programmer to specify a numerical procedure using a concise language like that of mathematics and obtain automatically from this specification an efficient 704 program to carry out the procedure” — with the emphasis on “efficient” (FORTRAN Session — J. Backus, HOPL-I). This distinguished FORTRAN from earlier “automatic programming” systems, which had a reputation for producing code so slow that users refused to switch from assembler (FORTRAN Session — J. Backus, HOPL-I).
The first commercial optimizing compiler. The FORTRAN team spent roughly 18 person-years on the compiler; it is widely regarded as the first commercially available compiler in the modern sense, and its optimizer — with sophisticated register allocation, common-subexpression elimination, and loop optimizations — was so good that FORTRAN produced object code competitive with hand-written assembler (Wikipedia: History of compiler construction; IBM: Fortran). This is the reason FORTRAN succeeded where earlier autocodes had not: the quality of the generated code convinced skeptical scientific programmers that they could give up assembler without losing performance (FORTRAN Session — J. Backus, HOPL-I).
Design decisions. FORTRAN was designed around fixed-format punched cards (columns 1–5 for labels, column 6 for continuation, 7–72 for statements) and column-position-sensitive syntax; it supported integer and floating-point arithmetic, one- and multi-dimensional arrays, three-way arithmetic IF, DO loops with integer counters, subroutines with FORTRAN’s call-by-reference convention, and a COMMON block for shared global data (Wikipedia: Fortran). Variables beginning with I, J, K, L, M, N were integers by default; all others were real — the origin of the “implicit typing” convention still occasionally seen today (Wikipedia: Fortran). There was originally no recursion, no dynamic memory allocation, and no local variables in the modern sense — all variables were statically allocated, and stack frames did not exist (Wikipedia: Fortran).
Adoption and influence. FORTRAN spread quickly through the scientific computing community and became the dominant language for numerical work — a position it has never fully surrendered; FORTRAN 77, Fortran 90/95, Fortran 2003/08/18/23 are all direct descendants (Wikipedia: Fortran). Backus received the 1977 ACM Turing Award “for profound, influential, and lasting contributions to the design of practical high-level programming systems, notably through his work on FORTRAN” (IBM: John Backus). By any measure, FORTRAN is the most successful programming language ever made — not because of its design, but because it was the first language whose compiler proved a high-level language could match assembly performance.
What was later criticized. FORTRAN’s global data through COMMON blocks, arithmetic IF, computed GOTO, three-way branches, EQUIVALENCE aliasing, and column-oriented syntax became emblematic of the “spaghetti code” era; Dijkstra and the structured-programming movement targeted many of these features directly (Wikipedia: Fortran). Backus himself, in his 1977 Turing lecture, described FORTRAN as a von Neumann language whose fundamental idiom — “one word at a time through the tube” — was itself the bottleneck (Wikipedia: John Backus).
LISP (1958) — John McCarthy and the birth of symbolic computation
LISP was designed by John McCarthy at MIT in 1958–1959 as a language for artificial-intelligence work on the IBM 704 (History of Lisp — John McCarthy, 1979; Wikipedia: Lisp (programming language)). McCarthy summarized the founding ideas in his 1979 History of Lisp: computing with symbolic expressions rather than numbers; representation of symbolic expressions by list structure in memory; a small set of selector/constructor functions; function composition; conditional expressions; λ-expressions for naming functions; the representation of LISP programs as LISP data; the LISP function eval that serves both as the language’s definition and as its interpreter; and garbage collection (History of Lisp — John McCarthy, 1979).
Motivating problem. McCarthy wanted an “algebraic list processing language for artificial-intelligence work” and had been exposed to Newell, Simon, and Shaw’s IPL — the first list-processing language — at the Dartmouth Summer Research Project on Artificial Intelligence in 1956 (History of Lisp — John McCarthy, 1979). McCarthy found IPL awkward — its form was based on a JOHNNIAC loader that happened to be at Rand — and preferred the FORTRAN idea of writing programs algebraically (History of Lisp — John McCarthy, 1979).
S-expressions and homoiconicity. LISP’s uniform data structure is the cons cell — a two-slot record — from which all lists and trees are built (Wikipedia: Lisp). The external representation is the S-expression: an atom, or a parenthesized list of S-expressions (Wikipedia: S-expression). Because programs and data share this representation, a LISP program is a piece of LISP data, and a LISP program can construct, inspect, and evaluate other LISP programs at runtime; this property — later called homoiconicity — is the source of LISP’s macro system and its use as an “extensible” language (Wikipedia: S-expression). M-expressions (a more Algol-like syntax) were originally planned as the external form, with S-expressions used only as an internal representation, but the M-expression compiler was never finished and programmers grew attached to S-expressions (Wikipedia: Lisp).
The meta-circular evaluator. McCarthy’s 1960 paper “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I” defined LISP semantically by giving eval and apply — a LISP interpreter written in LISP itself, in about a page (Wikipedia: Meta-circular evaluator; History of Lisp — John McCarthy, 1979). Alan Kay described reading this evaluator as being like seeing “Maxwell’s equations of software” — a compact, self-describing formal system (Wikipedia: Meta-circular evaluator). Steve Russell then observed that if this LISP function could be hand-translated into machine code, they would have a LISP interpreter — which he then did, producing the first working LISP implementation (History of Lisp — John McCarthy, 1979; Wikipedia: Lisp).
Garbage collection — invented for LISP. The list-structure model required some mechanism to reclaim inaccessible cells; McCarthy considered reference counting but rejected it (a variant was later used by G. E. Collins on the CDC 1604 in 1960), and instead chose to defer reclamation until free memory was exhausted, then trace from program roots to mark all live cells and rebuild the free list from the unmarked ones (History of Lisp — John McCarthy, 1979). This is the mark-and-sweep garbage collector, first implemented in LISP 1 around 1959–1960; it is the direct ancestor of every tracing collector in Java, C#, Python, Go, Ruby, and Haskell (History of Lisp — John McCarthy, 1979; Origins of Garbage Collection — Harvard CS252, 2016). McCarthy’s own account of the first public GC demo — the collector, previously untriggered, was suddenly called during a demonstration and printed “THE GARBAGE COLLECTOR HAS BEEN CALLED. SOME INTERESTING STATISTICS ARE AS FOLLOWS:” for the remainder of the demo, incapacitating both lecturer and audience with laughter — is one of the field’s classic anecdotes (History of Lisp — John McCarthy, 1979).
Ecosystem and dialects. LISP fragmented very early. MacLisp at MIT (1960s–70s), BBN Lisp / Interlisp (Bolt, Beranek & Newman + Xerox PARC), Standard Lisp, ZetaLisp (the “Lisp machine” dialect), and eventually Common Lisp (standardized 1984, ANSI 1994) formed one branch; Scheme (Sussman & Steele 1975, treated below) formed another; Clojure (2007) and Racket (2010s) are modern descendants (Wikipedia: Lisp). LISP was the language of the AI Lab at MIT, of Stanford AI Lab (SAIL), of BBN, and of the Xerox PARC AI group; it powered SHRDLU, Macsyma, ACL2, AutoCAD’s macro language, Emacs’s extension language, and Yahoo! Store (Wikipedia: Lisp). LISP 1.5 (MIT, 1962), described in the LISP 1.5 Programmer’s Manual by McCarthy, Abrahams, Edwards, Hart, and Levin, was the reference version through the 1960s and defined the syntax, eval/apply, defun, prog, property lists, and the basic library that most later dialects preserved (History of Lisp — McCarthy, 1979).
Specialized hardware. Because LISP’s list-processing and garbage collection stressed the memory subsystems of general-purpose machines, the AI Labs at MIT and Stanford developed dedicated LISP machines in the late 1970s (CADR, Symbolics 3600, LMI Lambda, TI Explorer). These had tagged memory (every word carries a type tag), hardware-assisted garbage collection, and microcoded LISP instructions; they enabled the first industrial-scale AI applications in the 1980s but were driven out of the market by general-purpose workstations running LISP at competitive speeds by the early 1990s (Wikipedia: Lisp).
What was criticized. LISP’s parenthesized syntax became a cultural signature — and a shibboleth. Numeric performance was traditionally poor (McCarthy’s own 1979 history lists “ultra-slow numerical computation” among LISP’s biggest weaknesses in the early 1960s) (History of Lisp — John McCarthy, 1979). Dynamic scoping in early LISPs led to the “upward FUNARG problem” — closures over local variables did not work correctly across function returns — which was a large motivation for Scheme’s later insistence on lexical scoping (Wikipedia: Lisp; Wikipedia: History of the Scheme programming language).
COBOL (1959) — Grace Hopper, CODASYL, and business computing
COBOL — the COmmon Business-Oriented Language — was designed in 1959 by the Conference on Data Systems Languages (CODASYL), a consortium sponsored by the U.S. Department of Defense; the initial CODASYL Short Range Committee met at the Pentagon on 28–29 May 1959, exactly one year after the Zurich ALGOL 58 meeting (Wikipedia: COBOL; Wikipedia: CODASYL). The motivation was the Defense Department’s concern that it could not run the same business-data-processing programs on different manufacturers’ computers — FORTRAN, the only mainstream language at the time, lacked the file-oriented and record-oriented features needed for business work (Wikipedia: COBOL).
Grace Hopper’s role. Grace Murray Hopper (1906–1992) was a Navy Rear Admiral and one of the pioneers of computer programming (Wikipedia: Grace Hopper). At Eckert–Mauchly (later Sperry Rand) she wrote the A-0 System in 1952 — sometimes called the first compiler, though it was closer to a loader/linker — and by 1959 she led the release of FLOW-MATIC, the first English-like data-processing language, on the UNIVAC I; FLOW-MATIC was the direct model that CODASYL used for COBOL (Wikipedia: Grace Hopper; Wikipedia: FLOW-MATIC; Wikipedia: A-0 System). Hopper is often called “the grandmother of COBOL”; she did not sit on the design committee but her earlier work and personal influence were decisive in orienting the design toward an English-like syntax (Wikipedia: Grace Hopper; Wikipedia: COBOL).
Design decisions. COBOL divides every program into four Divisions: IDENTIFICATION, ENVIRONMENT, DATA, and PROCEDURE. It offers verbose, prose-like syntax (ADD 1 TO X, MOVE Y TO Z, PERFORM PARA-100 UNTIL COUNT = 10); a hierarchical record data model (01 CUSTOMER. 02 NAME PIC X(30). 02 ADDRESS. 03 STREET PIC X(20). …); fixed-length numeric types with a PICTURE clause specifying number of digits and formatting; and native file I/O with sequential, relative, and indexed access (Wikipedia: COBOL). The design intent was that a business analyst could read COBOL code without programming training — an intent captured in the marketing phrase “self-documenting” (Wikipedia: COBOL).
Implementation and adoption. COBOL was standardized in 1968 (ANSI X3.23) and has been revised repeatedly (COBOL-74, COBOL-85, COBOL 2002 with object-oriented extensions, and later revisions to ISO/IEC 1989) (Wikipedia: COBOL). Vendor pressure from DoD forced every mainframe manufacturer to provide a COBOL compiler; a demonstration in December 1960 famously ran a COBOL program, unchanged, on both a UNIVAC II and an RCA 501 — the first known cross-platform high-level language demonstration (Wikipedia: History of compiler construction).
Lasting influence and criticism. COBOL is estimated to run on more mainframe transactions per day than any other language, and much of the world’s banking, insurance, and payroll infrastructure was written in it in the 1970s–1990s (Wikipedia: COBOL). Dijkstra’s 1975 quip — “The use of COBOL cripples the mind; its teaching should, therefore, be regarded as a criminal offense” — captured the aesthetic view of many academic computer scientists (Wikipedia: COBOL). COBOL was very verbose (a typical program is 3× the line count of an equivalent Pascal program), lacked local scope in its original form, and originally had no support for recursion or dynamic memory — these deficiencies were addressed in later revisions (Wikipedia: COBOL).
ALGOL 58 and ALGOL 60 — the algorithmic language and the birth of BNF
ALGOL 58 (originally IAL — International Algebraic Language) was designed at a joint meeting in Zurich in May–June 1958 by an ACM committee (Backus, Perlis, Bauer, Rutishauser, Samelson, and others) intending a single algorithmic language for publication of algorithms in journals like Communications of the ACM (Wikipedia: ALGOL 58; Wikipedia: ALGOL). ALGOL 58 introduced code blocks delimited by begin and end, compound statements, and a distinction between a “publication language” for print and a “hardware representation” for input to compilers (Wikipedia: ALGOL 58; Wikipedia: ALGOL 60).
ALGOL 60 — the Revised Report on the Algorithmic Language ALGOL 60, edited by Peter Naur and published in the Communications of the ACM Vol. 3 No. 5 in May 1960 — was the product of a follow-on committee (Backus, Bauer, Green, Katz, McCarthy, Naur, Perlis, Rutishauser, Samelson, van Wijngaarden, Vauquois, Wegstein, Woodger) (Wikipedia: ALGOL 60). The Report was influential far out of proportion to ALGOL 60’s actual industrial deployment: C. A. R. Hoare later called it “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” (Wikipedia: ALGOL 60).
Key design innovations of ALGOL 60:
- Block structure with lexical scope — the first widely used language with nested blocks where variable declarations obey static scope; nested procedures, and closures-of-a-limited-kind, follow directly (Wikipedia: ALGOL 60).
- Recursive procedures — procedures could invoke themselves, requiring a runtime stack; this ruled out some FORTRAN-style static allocation (Wikipedia: ALGOL 60).
- Call-by-value and call-by-name parameter passing — call-by-name is essentially β-substitution and is the ancestor of lazy evaluation and thunks; the classic Jensen’s device exploits it (Wikipedia: ALGOL 60).
- Dynamic arrays — array bounds could be computed at runtime, allocated on the stack when a block is entered (Wikipedia: ALGOL 60).
- Structured control —
if…then…else…,forloops with step and while forms, and no arithmeticIF(Wikipedia: ALGOL 60). - Static, strong typing (Wikipedia: ALGOL 60).
BNF — Backus–Naur Form. ALGOL 58’s syntax had been described in prose, which led to disagreements between implementers about what was legal. John Backus, in a paper at the 1959 UNESCO conference, proposed a formal notation — a Post-style production system with the metasymbols ::=, |, and angle-bracket nonterminals — to describe the syntax of ALGOL 58 (About BNF notation — University of Geneva; Wikipedia: Backus–Naur form). Peter Naur, editor of the ALGOL 60 Report, adopted Backus’s notation, made small changes, and used it to define ALGOL 60’s syntax; the notation is thus known as Backus–Naur Form (About BNF notation — University of Geneva; Wikipedia: Backus–Naur form). Donald Knuth argued the “N” should stand for “Naur” rather than “Naur form” and the name stuck; every context-free-grammar notation used since — EBNF, ABNF, PEG, ANTLR grammars, Yacc/Bison syntax — is a direct descendant (Wikipedia: Backus–Naur form).
Implementation. The first ALGOL 58 compiler was completed at the end of 1958 by Friedrich L. Bauer, Hermann Bottenbruch, Heinz Rutishauser, and Klaus Samelson for the Z22 computer (Wikipedia: History of compiler construction). ALGOL 60 was implemented in Europe more than in America; notable compilers include Dijkstra and Zonneveld’s X1 ALGOL 60 (1960, the first fully working ALGOL 60 compiler), the Elliott Algol compiler by C. A. R. Hoare, Naur’s own Dansk-Regnecentralen compiler for the GIER, and Wirth and Hoare’s ALGOL W (a subset extended with records and pointers) (Wikipedia: ALGOL 60; Wikipedia: ALGOL).
Adoption and legacy. ALGOL 60 never achieved wide industrial use — IBM’s commitment to FORTRAN and the difficulty of implementing call-by-name and dynamic arrays on 1960s machines kept it academic — but essentially every subsequent imperative language descends from it: CPL, BCPL, B, C, Pascal, PL/I, Simula, Ada, Modula, Oberon, Java, C#, and Go all trace their block structure and lexical scoping to ALGOL 60 (Wikipedia: ALGOL 60). Peter Naur received the 2005 ACM Turing Award for the ALGOL 60 Report; C. A. R. Hoare received his 1980 Turing Award in part for ALGOL 60 implementation work (Wikipedia: ALGOL 60).
IPL — the actual first list-processing language
Information Processing Language (IPL) was developed by Allen Newell, Cliff Shaw, and Herbert Simon at RAND Corporation and Carnegie Tech starting in 1954, and used to write the first artificial-intelligence programs — Logic Theorist (1956) and General Problem Solver (1957) — years before LISP existed (Wikipedia: Information Processing Language). IPL introduced the linked list, list-manipulation primitives, symbolic atoms, property lists, and a runtime that supported recursion via an explicit stack (Wikipedia: Information Processing Language). IPL’s syntax, however, was essentially a symbolic assembler for the JOHNNIAC computer, with numeric codes for operations — a design that McCarthy explicitly rejected in favor of “algebraic” (FORTRAN-like) syntax when he designed LISP (History of Lisp — John McCarthy, 1979; Wikipedia: Information Processing Language). IPL was used through the 1960s within the AI community but never spread; LISP absorbed its ideas and improved the syntax and semantics beyond recognition (Wikipedia: Information Processing Language).
FLOW-MATIC — the immediate ancestor of COBOL
FLOW-MATIC, originally called B-0 (Business Language version 0), was developed for the UNIVAC I at Remington Rand under Grace Hopper’s direction between 1955 and 1959; the compiler was publicly available in early 1958 and substantially complete in 1959 (Wikipedia: FLOW-MATIC). Hopper’s motivation, in her own words, was that business-data-processing customers “were uncomfortable with mathematical notation… They said, ‘Throw those symbols out—I do not know what they mean, I have not time to learn symbols’” (Wikipedia: FLOW-MATIC). FLOW-MATIC allowed statements like INPUT INVENTORY FILE-A PRICE FILE-B ; OUTPUT PRICED-INV FILE-C UNPRICED-INV FILE-D ; HSP D — English keywords, file identifiers, and separate DATA and PROCEDURE divisions (Wikipedia: FLOW-MATIC). The COBOL committee took FLOW-MATIC as its starting point almost verbatim; the DIVISION/SECTION/PARAGRAPH structure and PICTURE-based data definitions of COBOL are recognizable inheritances (Wikipedia: FLOW-MATIC; Wikipedia: COBOL).
APT — Automatically Programmed Tool
APT was developed by Douglas T. Ross and colleagues at the MIT Servomechanisms Laboratory beginning in 1956; it is a domain-specific language for describing the paths that numerical-control (NC) machine tools should follow — a milling machine’s cutter path is described geometrically in APT (points, lines, circles, surfaces, feed rates, tool changes) and the compiler generates the punched-paper-tape control code the mill’s controller executes (Wikipedia: APT (programming language); Wikipedia: Douglas T. Ross). APT is important as one of the earliest domain-specific languages, as an early demonstration that compiler technology applies far beyond general-purpose computation, and as the direct ancestor of every CAM/CNC language in use today (Wikipedia: APT (programming language)). It was demonstrated publicly on the “MIT Science Reporter” television broadcast in 1959, “Automatically Programmed Tools” — an early attempt at popularizing computer-aided manufacturing (Wikipedia: Douglas T. Ross).
Era 3 — Type Systems, Structured Programming, and the ALGOL Legacy (1960s–1970s)
ALGOL 68 — ambition, complexity, and the fracture of the ALGOL community
ALGOL 68, formally the Report on the Algorithmic Language ALGOL 68, was designed by IFIP Working Group 2.1 between roughly 1962 and 1968; the editor was Adriaan van Wijngaarden of the Centrum Wiskunde & Informatica in Amsterdam, and the language was published in December 1968 (Wikipedia: ALGOL 68). Its design brief was to define a successor to ALGOL 60 that would fix its deficiencies and add features needed for systems programming, string processing, complex numbers, and parallel processing (Wikipedia: ALGOL 68).
Language features. ALGOL 68 introduced an ambitious set of features that were novel in a mainstream language: user-defined types (struct, union), pointer types (called ref), a full expression-oriented language (every construct returns a value, so x := if p then a else b fi is legal), operator overloading, user-defined operators with programmer-chosen priorities, a case statement, parallel-execution primitives (par clause with semaphores), collateral clauses, and a coherent “orthogonal” design in which types could be combined systematically (Wikipedia: ALGOL 68).
Van Wijngaarden grammars. The syntax of ALGOL 68 was specified in a novel two-level grammar (or “W-grammar”) invented for the purpose: a context-free “metagrammar” generates the infinite context-free grammar that in turn generates ALGOL 68 programs, allowing ALGOL 68’s context-sensitive syntax (e.g. that identifiers must be declared before use, that function arguments must have the right types) to be defined formally (Wikipedia: ALGOL 68). The technique was mathematically elegant but rendered the Report notoriously difficult to read (Wikipedia: ALGOL 68).
The IFIP schism. The report was approved narrowly, and a minority of Working Group 2.1 — including C. A. R. Hoare, Edsger Dijkstra, Niklaus Wirth, and Peter Naur — issued a formal Minority Report in December 1968 protesting the design’s complexity and the difficulty of implementing it (Wikipedia: ALGOL 68). Wirth had already left the working group and produced ALGOL W as an alternative “cleaned-up ALGOL 60”; when ALGOL W was rejected in favor of the ALGOL 68 direction, Wirth went home and designed Pascal (Recollections about the Development of Pascal — N. Wirth; Wikipedia: ALGOL 68).
Hoare’s judgment on ALGOL 68, delivered in his 1980 Turing lecture: “The first version of any language should be small; the second version of any language should be smaller still. Our ALGOL 60 Report was 17 pages. Our ALGOL 68 Report was 236 pages” (Wikipedia: ALGOL 68). The community’s schism between ALGOL 68 and Pascal effectively ended ALGOL as a movement — after 1970, the imperative-language stream flowed through Pascal-Modula-Oberon on one side and BCPL-B-C on the other (Wikipedia: ALGOL 68).
Implementation and adoption. ALGOL 68 was implemented — most notably by C. H. Lindsey’s “ALGOL 68S” and by the Royal Signals and Radar Establishment’s ALGOL 68R — and had a small but devoted following particularly in continental Europe and the UK military; but it never achieved wide industrial adoption (Wikipedia: ALGOL 68). Ada (1980) inherited several ALGOL 68 features (tasks, exceptions, generic units) but not its syntax (Wikipedia: ALGOL 68).
Why it matters for a designer. ALGOL 68 is the textbook case of the second-system effect (see cross-cutting themes below): a design team, flushed with the success of ALGOL 60, tried to fold every good idea circulating in the community into a single monolithic language, and produced something too complex to implement quickly, too complex to teach, and too complex to specify precisely without inventing a new grammar formalism (Wikipedia: Second-system effect; Wikipedia: ALGOL 68).
Simula 67 — the birth of objects
Simula I (1962) and Simula 67 (1967) were designed by Ole-Johan Dahl and Kristen Nygaard at the Norwegian Computing Center in Oslo (Wikipedia: Simula; The Birth of Object Orientation — Dahl, HOPL Norsk). Nygaard had been running Monte Carlo simulations for Norwegian Defense in the 1950s and wanted a language in which the entities being simulated — ships in a fjord, molecules in a reactor, customers in a queue — could be represented directly as language-level constructs; Dahl was recruited as the language designer and compiler implementer (The Birth of Object Orientation — Dahl; ETHW: Milestones — Object-Oriented Programming, 1961–1967).
Simula I (1962–1965) was implemented as an ALGOL 60 extension for the UNIVAC 1107 and provided processes — records with associated code and their own execution state, capable of being suspended and resumed via coroutines — for discrete-event simulation (The Birth of Object Orientation — Dahl).
Simula 67 generalized the notion of “process” into the notion of class, added inheritance (with the class C1 class C2 prefix notation for what we would now call class C2 extends C1), and offered virtual procedures for what we would now call dynamic dispatch (Wikipedia: Simula; The Birth of Object Orientation — Dahl). This is the point at which “objects” as a language-level abstraction — encapsulated state and behavior, with subclasses that specialize base classes — first appeared in a mainstream language; Dahl and Nygaard received the 2001 ACM Turing Award and the 2001 IEEE John von Neumann Medal for this work (Wikipedia: Ole-Johan Dahl; Wikipedia: Kristen Nygaard).
Implementation. Simula 67 was compiled to native code on several machines; the runtime included a garbage collector (necessary because objects were heap-allocated and had non-nested lifetimes), a coroutine scheduler, and a class-based type check at method call sites (Wikipedia: Simula).
Adoption and influence. Simula was widely used in Scandinavia, in the discrete-event-simulation community, and — critically — was taught to and profoundly influenced Alan Kay (The Early History of Smalltalk — Kay) and Bjarne Stroustrup (who took the ideas of Simula’s classes back to Bell Labs and built the first C++ prototype, “C with Classes”, explicitly modeled on Simula 67) (ETHW: Object-Oriented Programming Milestone). Every class-based OO language — C++, Java, Python, C#, Ruby, Swift, Kotlin, Scala — inherits from Simula 67 by a straight line (Wikipedia: Simula).
PL/I — IBM’s “kitchen sink”
PL/I — originally NPL (New Programming Language), renamed to avoid confusion with Britain’s National Physical Laboratory — was designed by IBM starting in 1964 to be a single, unified language for both scientific and business computing, replacing FORTRAN, COBOL, and (in IBM’s ambition) ALGOL for the new System/360 line (Wikipedia: PL/I; The Early History and Characteristics of PL/I — IBM Research). The initial design was done by a joint IBM–SHARE (user-group) committee in 1963–1964, aiming to give scientific programmers COBOL’s record I/O, business programmers FORTRAN’s expression evaluation, and everyone ALGOL’s block structure and control flow (Wikipedia: PL/I).
Design decisions. PL/I incorporated essentially every feature its designers had seen: complex numbers, decimal fixed-point and floating-point arithmetic with programmer-controlled precision, string handling with pattern matching, records (structures), pointers, dynamic and static storage, tasks with events and priorities, condition handling (ON CONDITION), preprocessor macros, function overloading via implicit conversions, and cross-language calls (Wikipedia: PL/I). The type-conversion rules were extraordinarily permissive: IF I THEN… was legal for any numeric I; strings and numbers could be assigned to each other with silent conversion; array and structure assignments extended naturally (Wikipedia: PL/I).
Implementation. IBM’s PL/I F compiler (1966) was one of the largest software projects of the era; a subset called PL/C was built at Cornell in the late 1960s specifically for teaching, with far better diagnostics than the production compiler (Wikipedia: PL/I). Multics was largely written in PL/I — an early “systems programming” use of a high-level language — and Multics’s Early PL/I compiler was itself written in PL/I (Wikipedia: PL/I).
Adoption and criticism. PL/I never displaced FORTRAN or COBOL in their respective domains and was overtaken by C for systems programming in the 1970s. The most-cited critique is Edsger Dijkstra’s, from his 1972 Turing Award lecture: “Using PL/I must be like flying a plane with 7000 buttons, switches, and handles to manipulate in the cockpit. I absolutely fail to see how we can keep our growing programs firmly within our intellectual grip when by its sheer baroqueness the programming language — our basic tool, mind you! — already escapes our intellectual control” (Wikipedia: PL/I). PL/I remains, alongside ALGOL 68, the canonical example of design-by-committee complexity: nothing is missing from the language, and nothing hangs together (Wikipedia: PL/I).
BCPL → B → C — the Unix lineage
BCPL — Basic Combined Programming Language — was designed by Martin Richards at Cambridge in 1966 as a simplified typeless dialect of CPL (a joint Cambridge–London project that had grown too complex to implement) (Wikipedia: BCPL). BCPL’s radical simplification was to use a single data type — the machine word — with the meaning (integer, pointer, character) determined by the operators applied to it; this typelessness allowed a very small, portable, bootstrappable compiler (Wikipedia: BCPL). BCPL’s own compiler was designed for portability — the front end produced an intermediate representation called O-code which a back end translated to the target machine (Wikipedia: BCPL; The Development of the C Language — Ritchie).
B was written by Ken Thompson at Bell Labs in 1969, initially for the DEC PDP-7 running an early Unix, as a further simplification of BCPL fitted to the tight memory of the PDP-7 (Wikipedia: B (programming language); The Development of the C Language — Ritchie). B was also typeless — the fundamental data type was the word — and was interpreted first, then compiled (Wikipedia: B (programming language)).
C was designed by Dennis Ritchie at Bell Labs in 1971–1973 as a typed extension of B for the DEC PDP-11 — the PDP-11 had byte addressing, mixed byte and word operations, and different-size integers, all of which the typeless B could not describe naturally (The Development of the C Language — Ritchie; Wikipedia: C (programming language)). Ritchie added a small type system with int, char, float, double, arrays, structures, and pointers; he retained BCPL’s philosophy of exposing the machine’s representation directly, so pointer arithmetic and casts remained cheap and unchecked (The Development of the C Language — Ritchie).
The killer application. The Unix kernel was rewritten from PDP-11 assembly into C in 1973, making Unix the first widely used operating system written in a high-level language and demonstrating that C was suitable for the most demanding systems work (The Development of the C Language — Ritchie; Wikipedia: C (programming language)). Brian Kernighan and Ritchie’s 1978 book The C Programming Language — universally known as “K&R” — served as the de facto specification until ANSI C (C89) was standardized in 1989 (Wikipedia: C (programming language)).
Design decisions worth studying. C’s syntax follows ALGOL 60 (semicolons, braces for blocks, if…else, while, for) but its type system is a stripped-down Pascal, its memory model is BCPL’s, and its philosophy is “trust the programmer” — no bounds checking, no automatic memory management, weak type conversions, and a small standard library (The Development of the C Language — Ritchie). Ritchie summed up the language’s aesthetic in his HOPL-II paper: “C is quirky, flawed, and an enormous success” (The Development of the C Language — Ritchie).
Ecosystem and adoption. Once Unix was distributed to universities (from 1974) with C source, the language spread through the academic-Unix ecosystem, and by the 1980s had displaced Pascal in university systems courses, PL/I in scientific systems programming, and assembler almost everywhere (Wikipedia: C (programming language)). Every subsequent systems language — C++, Objective-C, Java (in syntax), C#, Go, Rust, Zig — cites C as a direct ancestor (Wikipedia: C (programming language)). Ritchie received the 1983 ACM Turing Award, shared with Ken Thompson, for Unix and C (The Development of the C Language — Ritchie).
What was later criticized. C’s semantics — undefined behavior on integer overflow, on out-of-bounds access, on use-after-free, on null-pointer dereference — has made it the source of most exploitable security vulnerabilities in modern software; the industry-wide push to memory-safe systems languages (Rust, Zig, Swift, Go) is essentially a reaction to C’s design (Wikipedia: C (programming language)).
Pascal (1970) — Wirth’s teaching language and structured programming
Pascal was designed by Niklaus Wirth at ETH Zürich in 1968–1970, motivated by two goals: (1) a language suitable for teaching programming as a systematic discipline based on Dijkstra’s structured-programming ideas; and (2) an implementation that could run reliably and efficiently on the machines then available at ETH (Recollections about the Development of Pascal — Wirth; Wikipedia: Pascal (programming language)). Wirth had spent 1963–1967 working on ALGOL W and been present at the ALGOL 68 committee meetings; when ALGOL 68 went in a direction he thought disastrous, he returned to Zürich and built Pascal to demonstrate his own alternative (Recollections about the Development of Pascal — Wirth).
Design philosophy. Wirth’s guiding principle throughout his career was simplicity: a language should be small enough for one person to hold in mind, its features orthogonal, its implementation direct, and its cost model transparent (Wikipedia: Niklaus Wirth; Recollections about the Development of Pascal — Wirth). Pascal’s language definition was 39 pages, versus ALGOL 68’s 236; Wirth would later insist that every language he designed be smaller than its predecessor (Wikipedia: Niklaus Wirth).
Design decisions. Pascal was a static, strongly typed ALGOL descendant, with block structure and lexical scope inherited directly from ALGOL 60. Its novel features were:
- User-defined types: enumeration types, subrange types (
1..10), records (product types), variant records (a limited sum type), sets, arrays with static bounds, and files (Wikipedia: Pascal). - Nested procedures and functions, with recursion and lexical scoping, as in ALGOL 60 (Wikipedia: Pascal).
- Pointers (
^T) withnewanddisposefor explicit heap allocation (Wikipedia: Pascal). - Structured control:
if…then…else,while,repeat…until,for,case; nogotowas required (but one was reluctantly included) (Wikipedia: Pascal). - A single-pass, recursive-descent compiler — Pascal was designed so that a hand-written recursive-descent parser could compile it in one pass, which is why (for example) all types must be declared at the top of a procedure before any statements (Wikipedia: Pascal; Recollections — Wirth).
Implementation — the P-code compiler. Wirth’s 1973 implementation, later called Pascal-P, compiled Pascal source to a portable stack-machine intermediate representation called P-code, which was then interpreted or translated on each target machine (Recollections — Wirth; Wikipedia: Pascal). Universities across the world ported the P-code interpreter to their hardware and thereby got a working Pascal, which is a large part of why Pascal became the dominant university teaching language of the 1970s and 80s (Wikipedia: Pascal). The P-code idea — a portable virtual machine as compilation target — is the same idea later used by UCSD Pascal, the JVM, the CLR, and WebAssembly (Wikipedia: Pascal).
Adoption. UCSD Pascal (from 1978) ran on the Apple II and other microcomputers, shipping with a P-code-compatible virtual machine and a full development environment on floppy disk — a form factor that made Pascal the first serious programming environment for hobbyist microcomputers (Wikipedia: Pascal). Borland’s Turbo Pascal (1983), written by Anders Hejlsberg, compiled directly to x86 machine code in a single pass with speeds measured in tens of thousands of lines per second on the original PC — orders of magnitude faster than the competing C compilers of the day — and priced at $49.95 when comparable tools cost thousands (Wikipedia: Pascal). Turbo Pascal made Pascal the dominant DOS programming environment of the mid-1980s and the introductory language of a generation of programmers. Object Pascal and Borland’s Delphi (1995) — Hejlsberg’s next design — carried the language forward into modern GUI application development, and Hejlsberg himself went on to design C# for Microsoft in 2000, taking many Pascal/Delphi ideas with him (Wikipedia: Pascal).
What was criticized. Brian Kernighan’s 1981 essay “Why Pascal is Not My Favorite Programming Language” enumerated the failures of Pascal as a systems programming language: the string type was a fixed-length array with the length as part of the type, so procedures could not accept strings of different lengths without special mechanisms; there was no separate compilation; arrays were part of their length type; the standard library was minimal; and I/O was awkward (Wikipedia: Pascal). Wirth had designed Pascal to teach programming, not to build production systems, and many of these limitations were direct consequences (Recollections — Wirth).
Modula, Modula-2, and Oberon — Wirth’s continuing evolution
Modula (1975) was Wirth’s first attempt at a language with modules — separately compilable units with explicit import/export interfaces — motivated by his need for a systems language for the Xerox-inspired Lilith personal workstation being built at ETH (History of Modula-2 and Oberon — Wirth, HOPL-3, 2005/2006; Wikipedia: Modula-2). Modula was small and experimental — concurrency primitives (process, signal, monitor in Hoare’s sense) were its main additions to Pascal — and not intended as a general-purpose language (History of Modula-2 and Oberon — Wirth).
Modula-2 (defining report 1979, textbook 1982) was the full-scale successor: modules as compilation units with cleanly separated DEFINITION and IMPLEMENTATION parts, procedure types (function pointers), low-level machine access via a special SYSTEM module, and coroutines instead of Modula’s processes (Wikipedia: Modula-2; History of Modula-2 and Oberon — Wirth). Modula-2 was influenced by Wirth’s 1976 sabbatical at Xerox PARC, where he saw the Mesa language and the Xerox Alto workstation (Wikipedia: Modula-2). Modula-2 was used as the systems language of the Lilith workstation, was ported widely, and had a passionate but limited community — it was ultimately outcompeted by C for portable systems work (Wikipedia: Modula-2).
Oberon (1988) was the sequel — Wirth’s admission that Modula-2 had itself grown too complex (History of Modula-2 and Oberon — Wirth). Oberon dropped several features (subranges, variant records, most enumerated types), added a form of single-inheritance object-orientation via type extension of records, and shipped as part of the Oberon operating system — a complete integrated system for personal workstations (History of Modula-2 and Oberon — Wirth). The Oberon System introduced automatic garbage collection to the Modula family and became the platform on which Wirth’s group did much of its research on compilers, editors, and network file systems into the 1990s (History of Modula-2 and Oberon — Wirth).
Wirth’s design trajectory — Pascal (1970) → Modula (1975) → Modula-2 (1979) → Oberon (1988) — is one of the few in the field where each successor is deliberately smaller than its predecessor; it is a working demonstration of the discipline that “the second system should be smaller” (History of Modula-2 and Oberon — Wirth; Wikipedia: Niklaus Wirth). Wirth received the 1984 ACM Turing Award for “developing a sequence of innovative computer languages, EULER, ALGOL-W, MODULA and PASCAL” (Wikipedia: Niklaus Wirth).
SNOBOL — string processing
SNOBOL — String-Oriented Symbolic Language — was developed at Bell Labs by David J. Farber, Ralph E. Griswold, and Ivan P. Polonsky from 1962 onward; SNOBOL4 (1967) was the mature, widely used version (Wikipedia: SNOBOL). SNOBOL was designed for symbolic manipulation — text processing, compiler prototyping, and computational linguistics — at a time when FORTRAN and ALGOL had essentially no string types (Wikipedia: SNOBOL).
Design decisions. SNOBOL’s central abstraction was the pattern: a first-class value describing a set of strings, with combinators for concatenation, alternation, and recursion, and pattern matching as a language-level primitive with automatic backtracking (Wikipedia: SNOBOL). SNOBOL4 also had dynamic typing (a value carries its own tag), associative arrays (called tables), first-class functions, and the ability to define new data types at runtime (Wikipedia: SNOBOL). Griswold implemented SNOBOL4 in a macro-based portable back end (SIL — SNOBOL Implementation Language), which allowed SNOBOL4 to be ported to a large fraction of the machines then in existence — a portability strategy similar to Pascal’s P-code (Wikipedia: SNOBOL).
Influence. SNOBOL4 was the direct ancestor of Griswold’s later Icon language (1977), and its pattern-matching model influenced regular-expression libraries, parser combinators, and the string-processing features of AWK, Perl, and Python (Wikipedia: SNOBOL). SNOBOL’s associative arrays predate PHP’s, Python’s, and JavaScript’s by decades (Wikipedia: SNOBOL).
LOGO — Papert, Feurzeig, and the teaching language
LOGO was designed at Bolt, Beranek & Newman (BBN) in 1967 by Wallace Feurzeig, Seymour Papert, and Cynthia Solomon as a programming language for children — specifically, as an educational instrument to embody Papert’s constructionist theory of learning derived from Jean Piaget (Wikipedia: Logo (programming language)). LOGO’s name comes from the Greek logos (“word”), reflecting its origins as a symbolic-computation language (Wikipedia: Logo).
Design. LOGO was semantically a dialect of LISP — dynamically typed, list-oriented, recursive, with functions as first-class values — but with a syntax based on natural English words and no parentheses on function calls (Wikipedia: Logo). The famous turtle graphics — a screen turtle that responds to FORWARD 100, RIGHT 90, PENUP, PENDOWN, letting a child draw geometric figures — was added around 1969–1971 as a way to make computation physically visible (Wikipedia: Logo). Papert’s book Mindstorms: Children, Computers, and Powerful Ideas (1980) argued LOGO into a global educational movement, and LOGO was used in millions of classrooms in the 1980s (Wikipedia: Logo).
Influence. LOGO’s model — a beginner-friendly graphical programming environment — is the direct ancestor of MIT’s Scratch, of Squeak/Etoys, of Alice, of Berkeley’s Snap!, and of the whole “beginner programming environment” genre (Wikipedia: Logo). Papert also co-designed the LEGO Mindstorms robotics kit, applying LOGO’s ideas to physical devices (Wikipedia: Logo).
Smalltalk 71 / 72 / 76 — the pure object system
Smalltalk was designed by Alan Kay’s Learning Research Group at Xerox PARC beginning in 1971, and passed through several major redesigns — Smalltalk-72, Smalltalk-74, Smalltalk-76, and finally Smalltalk-80 (the version released outside Xerox) (Wikipedia: Smalltalk; The Early History of Smalltalk — Kay, HOPL-II, 1993). Kay’s vision was of a Dynabook — a personal, portable computer usable by children as a medium for thought — and Smalltalk was the language that Dynabook software would be written in (The Early History of Smalltalk — Kay).
Design philosophy. Kay identified Smalltalk’s philosophical roots as biological: every object is a small, self-contained cell that maintains its own state and communicates with other objects only by sending messages (The Early History of Smalltalk — Kay). This is a stricter form of object-orientation than Simula 67: in Smalltalk, control flow (if…then…else, loops), collections, numeric operations, and even classes themselves are objects that respond to messages (Wikipedia: Smalltalk). The influences Kay explicitly cited as the “four great programming conceptions of the sixties” were Sketchpad, JOSS, LISP, and Simula (The Early History of Smalltalk — Kay).
Smalltalk-72 (implemented mainly by Dan Ingalls) introduced the syntax of message sends, image-based development (all state — code, classes, running processes — is a single serializable “image” file), and an integrated development environment with an editor, class browser, and debugger (Wikipedia: Smalltalk; The Early History of Smalltalk — Kay). Smalltalk-76 was the first version to include a full class-based inheritance hierarchy and a bytecode compiler; the runtime executed bytecodes on a virtual machine — an approach later inherited by the JVM (Wikipedia: Smalltalk; The Early History of Smalltalk — Kay). Smalltalk-80 (released 1980–1983) was the version documented in the “blue book” (Goldberg and Robson, Smalltalk-80: The Language and its Implementation, 1983) and licensed to Apple, HP, DEC, and others (Wikipedia: Smalltalk).
Implementation. The Smalltalk runtime was a bytecode virtual machine with an integrated generational garbage collector, a JIT-optimized inline cache for message dispatch, and an image — a single memory-mapped file holding the entire object graph, including running processes and windows (Wikipedia: Smalltalk; The Early History of Smalltalk — Kay). The image model meant Smalltalk had no distinction between “source code on disk” and “running program in memory”: you edited a live program in place, and saving simply wrote the image to disk (Wikipedia: Smalltalk).
Influence. Smalltalk’s model of pure OO with dynamic dispatch influenced Objective-C (which grafted Smalltalk-style messaging onto C), Ruby, Python’s method resolution, JavaScript’s prototype-based objects, and Erlang’s message-based actors (Wikipedia: Smalltalk). More broadly, the Xerox PARC user-interface work that surrounded Smalltalk — overlapping windows, the mouse, the WIMP GUI, WYSIWYG editing, the class browser, the debugger, the object inspector — became the model for the Macintosh (1984) and every desktop system since (The Early History of Smalltalk — Kay). Alan Kay received the 2003 ACM Turing Award for his work on Smalltalk (Wikipedia: Smalltalk).
What was criticized. Smalltalk’s runtime was heavy for 1970s–80s hardware; the image-based development model made version control and multi-programmer collaboration awkward; the dynamically typed message model produced runtime errors that would have been caught by a static type system. Every one of these trade-offs was made consciously in service of Kay’s vision of a personal-computer language, and Kay himself has said that “the actual Smalltalk is not what I had in mind” — the industry took the syntax and lost the philosophy (The Early History of Smalltalk — Kay).
”GOTO Considered Harmful” and the structured-programming debate
Edsger W. Dijkstra’s letter to the editor of the Communications of the ACM, published in March 1968 under the title (chosen by the editor Niklaus Wirth) “Go To Statement Considered Harmful”, argued that unrestricted goto should be abolished from higher-level programming languages because it makes programs difficult to reason about (Go To Statement Considered Harmful — Dijkstra, CACM 1968). Dijkstra’s technical argument was that the “conceptual distance” between the static program text and its dynamic execution grows unboundedly with the use of goto, because at any point during execution the state is described not just by the current instruction and the values of variables but also by the entire history of gotos taken (Go To Statement Considered Harmful — Dijkstra, CACM 1968). With only structured control (if…then…else, while, procedure call), the state can be described by variable values plus a single point in the program, which the programmer can name and reason about (Go To Statement Considered Harmful — Dijkstra, CACM 1968).
The letter kicked off the structured programming movement, which crystalized in the 1972 collection Structured Programming by Dahl, Dijkstra, and Hoare (Academic Press), in which Dijkstra contributed “Notes on Structured Programming,” Hoare contributed “Notes on Data Structuring,” and Dahl and Hoare contributed “Hierarchical Program Structures” (the essay that promoted class-based abstraction from Simula 67) (Wikipedia: Structured programming). Böhm and Jacopini’s 1966 result — that any program using arbitrary goto can be rewritten to use only while and if…then…else — provided the theoretical underpinning (Wikipedia: Structured programming).
By the mid-1970s the structured-programming argument had won: every new language (Pascal, C, Modula, Ada) offered structured control, and goto was retained (if at all) only for exceptional exits (Wikipedia: Structured programming). The debate was one of the first successful arguments that language-level restrictions could improve program quality — the direct ancestor of every subsequent language-level safety mechanism, from Pascal’s type checking to Rust’s borrow checker (Wikipedia: Structured programming).
Simula 67’s coroutines — a note on control abstractions
One feature of Simula 67 that deserves separate mention is its coroutines: procedures that can voluntarily suspend their execution (detach) and later be resumed (resume) at the point of suspension, with all local state intact (Wikipedia: Simula; The Birth of Object Orientation — Dahl). This is a strict generalization of the procedure-return model: a procedure has one entry point and (via return) one implicit exit point, while a coroutine has one entry point and many resume/suspend points (Wikipedia: Simula). Coroutines are the natural implementation model for discrete-event simulation (each simulated entity runs as a coroutine, suspending when it must wait for an event and resuming when the event fires), and Simula’s execution model is essentially a coroutine scheduler with a priority queue of events (The Birth of Object Orientation — Dahl).
The coroutine idea propagated through Modula-2 (Wirth adopted them directly as an alternative to threads), through Icon (Griswold’s successor to SNOBOL, whose generators are coroutines), and — after several decades of dormancy — into modern languages as Python’s yield-based generators (2001), C#‘s iterators, Lua’s coroutines, Kotlin’s suspending functions, and JavaScript’s async/await. Every language today that offers cooperative concurrency, lazy sequences, or async I/O owes its runtime model directly to Simula 67 (Wikipedia: Continuation).
The “software crisis”
The phrase software crisis was coined at the 1968 NATO Software Engineering Conference in Garmisch, Germany — a landmark conference organized by F. L. Bauer that also introduced the term “software engineering” (Wikipedia: Software crisis). The crisis in question was that the rapid growth in computer power was making possible software projects (large operating systems, business systems, and later real-time systems) far beyond what existing methods could deliver on schedule, on budget, and correctly; the failures were spectacular — IBM’s OS/360 (over budget, over time, and buggy) being the canonical example (Wikipedia: Software crisis; A Brief History of Software Engineering — Wirth).
Reactions were varied and are still with us:
- Structured programming (Dijkstra, Dahl, Hoare) — restrict language features to make correctness reasoning possible (Wikipedia: Structured programming).
- Program verification and formal methods (Hoare’s 1969 axiomatic semantics, Dijkstra’s A Discipline of Programming 1976) — prove programs correct against specifications (Wikipedia: Software crisis).
- Better languages — Pascal, Modula, Ada, and later ML, Eiffel, and Haskell all cite the software crisis as motivation (Wikipedia: Software crisis).
- Software engineering as a profession — process, methodology, testing, code review, configuration management (Wikipedia: Software crisis).
- Modularity and information hiding (Parnas’s 1972 “On the Criteria To Be Used in Decomposing Systems into Modules”) — architectural mitigation (Wikipedia: Software crisis).
Wirth’s 2008 IEEE Annals history “A Brief History of Software Engineering” traces this whole arc from an insider’s perspective (A Brief History of Software Engineering — Wirth).
Comparing the 1968 responses: ALGOL 68, Simula 67, Pascal, and structured programming
It is instructive to lay 1968’s programming-language events side by side. In one calendar year:
- ALGOL 68 was published in draft form (December 1968), a massive design that IFIP Working Group 2.1 approved narrowly amid protest (Wikipedia: ALGOL 68).
- Dijkstra’s “Go To Statement Considered Harmful” appeared in the March 1968 CACM (Go To Statement Considered Harmful — Dijkstra).
- The NATO Software Engineering Conference at Garmisch (October 1968) coined the terms “software crisis” and “software engineering” (Wikipedia: Software crisis).
- Simula 67 had just been standardized (May 1968 IFIP Common Base Language draft), introducing classes and inheritance (Wikipedia: Simula).
- Wirth’s Pascal design was being drafted at ETH, published formally in 1970 as a reaction to ALGOL 68 (Recollections on Pascal — Wirth).
Each of these was a response to the same underlying anxiety: the growing complexity of software was outpacing the tools available to write it. ALGOL 68 responded by making the language more powerful; Simula responded by introducing a new abstraction (the object); Dijkstra and Wirth responded by making the language more disciplined; the NATO conference responded by declaring software engineering a discipline. The subsequent 55 years of programming-language history have essentially rerun this same debate over and over, with different labels: expressiveness vs. discipline, dynamic vs. static, features vs. minimalism, powerful abstractions vs. simple mechanisms. A language designer in 2026 confronts the identical trade-offs, which is what makes 1968 the field’s foundational year.
Prolog (1972) — Colmerauer, Kowalski, and logic programming
Prolog — PROgrammation en LOGique — was created by Alain Colmerauer and Philippe Roussel at the University of Aix-Marseille in 1972, growing out of Colmerauer’s earlier project to allow deduction over French-language texts (Wikipedia: Prolog; The Birth of Prolog — Colmerauer & Roussel, 1992). The name was chosen by Roussel at his wife’s suggestion (Wikipedia: Prolog; The Birth of Prolog — Colmerauer & Roussel).
Motivating problem. Colmerauer had been working since 1970 on making a computer “understand” French-language questions and answer them by deduction over a knowledge base — a system he initially called the “Q-system” (The Birth of Prolog — Colmerauer & Roussel). The team recognized in Robert Kowalski’s 1971 work on SL-resolution — a refinement of Robinson’s 1965 resolution principle for first-order logic — a computational engine that could serve as the deduction machinery (The Birth of Prolog — Colmerauer & Roussel). Kowalski visited Marseille for a week in June 1971 and the collaboration led directly to Prolog: Colmerauer contributed the implementation and pragmatics, Kowalski the theoretical framework (The Birth of Prolog — Colmerauer & Roussel).
Language and execution model. A Prolog program is a collection of Horn clauses — logical implications of the form head :- body1, body2, …, bodyn, meaning head is true if all of body1…n are true (Wikipedia: Prolog). Execution is goal-directed SLD-resolution: given a query, Prolog unifies it with the head of some clause, then recursively tries to prove each body atom; if a branch fails, it backtracks and tries another clause (Wikipedia: Prolog). Unification — the algorithm that finds the most-general substitution making two terms equal — is the central runtime primitive (Wikipedia: Prolog).
The execution semantics are declarative — a Prolog program can (in principle) be read as a set of logical statements — but they are also procedural — the order of clauses and the order of goals in a clause determine what actually happens (Wikipedia: Prolog). Colmerauer’s Prolog 0 (1972) and Prolog I (1973) were the first implementations; the interpreter was hand-coded in FORTRAN on an IBM 360/44 (The Birth of Prolog — Colmerauer & Roussel).
Implementation. David H. D. Warren’s 1977 Edinburgh Prolog compiler and the later Warren Abstract Machine (WAM) — a specialized abstract machine for Prolog with registers, unification hardware, and choice-point stacks — became the standard implementation model and made Prolog performance-competitive with LISP for symbolic work (Wikipedia: Prolog). The ISO standardized Prolog in ISO/IEC 13211-1:1995 (Wikipedia: Prolog).
Adoption and influence. Prolog became the standard language for computational linguistics, expert systems, and (famously) Japan’s Fifth-Generation Computer Systems project (1982–1992) — a national attempt to build parallel Prolog-executing computers as the platform for AI (Wikipedia: Prolog). While the Fifth-Generation project did not achieve its ambitions, Prolog influenced (among others) Erlang (which was originally implemented in Prolog), Mercury, Datalog (used in modern static-analysis tools like Semmle/CodeQL and Rust’s borrow checker), and the pattern-matching syntax of ML-family languages (Wikipedia: Prolog).
What was criticized. Prolog’s pure declarative semantics is compromised by the cut operator (!), by side-effecting predicates (assert, retract), by the reliance on clause and goal order, and by the non-first-order-logical negation as failure — all of which mean that Prolog programs are best understood operationally, not declaratively (Wikipedia: Prolog). Prolog’s performance on non-symbolic workloads is poor, and the language struggles with numerical computation (Wikipedia: Prolog).
Kowalski’s separate contribution. Robert Kowalski, at Edinburgh and later Imperial College, published in 1974 the paper “Predicate Logic as Programming Language” that gave the theoretical framing — “algorithm = logic + control” — that separated Prolog’s declarative content (Horn clauses as logical statements) from its procedural content (the SLD resolution strategy used to execute them) (The Birth of Prolog — Colmerauer & Roussel). This framing became the intellectual foundation of the entire logic programming subfield, which extends well beyond Prolog into deductive databases (Datalog), constraint logic programming (CLP, Prolog III/IV), and modern answer-set programming (The Birth of Prolog — Colmerauer & Roussel).
Scheme (1975) — Sussman, Steele, and lexical Lisp
Scheme was designed by Guy L. Steele Jr. and Gerald Jay Sussman at the MIT Artificial Intelligence Laboratory in 1975, initially as a small experiment to test Carl Hewitt’s actor model of computation (Wikipedia: History of the Scheme programming language; The Lambda Papers — Steele & Sussman, MIT AI Memos). Steele and Sussman discovered that actors and Lisp procedures — if the procedures had lexical scoping and were first-class values — were essentially the same thing, and Scheme grew out of this discovery (Wikipedia: History of the Scheme programming language).
Two crucial design decisions.
-
Lexical scoping — a variable in a Scheme expression refers to the binding in the innermost enclosing lexical block, exactly as in ALGOL 60. Previous Lisps (MacLisp, InterLisp) used dynamic scoping, where a variable refers to the innermost binding on the runtime call stack; this made closures over local variables incorrect (the “FUNARG problem”), so higher-order functional programming was awkward (Wikipedia: History of the Scheme programming language; Wikipedia: Lisp). Scheme’s insistence on lexical scoping meant that closures worked, which meant that functional programming worked, which meant Scheme was a Lisp in which the lambda calculus lived properly (The Lambda Papers — Steele & Sussman).
-
First-class continuations — Scheme provides
call-with-current-continuation(call/cc), which reifies the current continuation (the “rest of the computation”) as a first-class function that can be stored, invoked, and re-entered (Wikipedia: Continuation; Wikipedia: History of the Scheme programming language). This one primitive is sufficient to implement exceptions, generators, coroutines, backtracking, and cooperative threads at the library level (Wikipedia: Continuation).
Minimalism. Scheme’s initial specification (Steele and Sussman, “Scheme: An Interpreter for Extended Lambda Calculus,” MIT AI Memo 349, 1975) was on the order of ten pages (The Lambda Papers — Steele & Sussman). The R5RS standard (1998) was 50 pages; R6RS (2007) was much larger and controversial; R7RS-small (2013) returned to Scheme’s original minimalism (Wikipedia: History of the Scheme programming language).
The “Lambda Papers”. From 1975 through the early 1980s Steele and Sussman produced a series of papers with names like “Lambda: The Ultimate Imperative”, “Lambda: The Ultimate Declarative”, “Lambda: The Ultimate GOTO”, and “The Art of the Interpreter, or the Modularity Complex”; collectively known as the Lambda Papers, they laid out how tail calls, continuations, closures, and macros make lambda calculus a viable computer science foundation for the whole of programming, not just for functional programs (The Lambda Papers — Steele & Sussman; Wikipedia: History of the Scheme programming language).
Implementation innovations. Steele’s masters thesis “RABBIT: A Compiler for SCHEME” (1978) demonstrated that a Scheme compiler could be written in continuation-passing style (CPS) — a transformation of programs in which every function takes an explicit continuation argument — and generate code competitive with hand-written assembly (RABBIT: A Compiler for SCHEME — Steele, 1978). CPS is now standard in almost every optimizing functional compiler (RABBIT: A Compiler for SCHEME — Steele, 1978).
Influence. Scheme was the language of Abelson and Sussman’s Structure and Interpretation of Computer Programs (1985) — for two decades the introductory programming course at MIT and one of the most influential textbooks in the field (Wikipedia: History of the Scheme programming language). Scheme’s design directly influenced Common Lisp, Clojure, Racket, JavaScript (whose original Brendan Eich brief was “make Scheme for the browser”), Julia’s macro system, and every modern functional language (Wikipedia: History of the Scheme programming language).
ML (1973) — Milner, LCF, and Hindley–Milner type inference
ML — Meta Language — was designed by Robin Milner at Edinburgh in 1972–1973 as the meta-language of the LCF theorem prover (“Logic for Computable Functions”), a system for interactive proof of properties of programs built around Dana Scott’s logic of the same name (Wikipedia: ML (programming language); History of Standard ML — Robert Harper, CMU). Milner needed a language in which users could write tactics — programs that manipulate proof terms and construct new proofs from old ones — with static guarantees that a valid tactic would produce only valid proofs (Wikipedia: ML (programming language)).
Two key design decisions.
-
A polymorphic type system with type inference (Hindley–Milner) — types are inferred automatically without programmer annotations; the type system is expressive enough to give functions polymorphic types like
α list → int(length of a list of any element type) but restricted enough that inference always terminates and produces a unique most-general type (the “principal type scheme”) (Wikipedia: Hindley–Milner type system). The type system is named for Roger Hindley (who proved the “principal type” theorem in a 1969 paper on combinatory logic) and Milner (who independently re-discovered and generalized the result in 1978 for ML) (Wikipedia: Hindley–Milner type system; Milner, “A Theory of Type Polymorphism in Programming,” 1978 — as summarized in the Hindley-Milner Wikipedia article). -
Algebraic data types with pattern matching — types like
datatype 'a list = Nil | Cons of 'a * 'a listand pattern-matching function definitions (fun length Nil = 0 | length (Cons(x,xs)) = 1 + length xs) let programmers define and consume tagged unions concisely, with the compiler statically checking that all cases are handled (Wikipedia: ML).
The LCF type discipline was also sound: Milner’s key theorem — colloquially “well-typed programs cannot go wrong” — was that a program of type bool at runtime returns a boolean, never a runtime type error (Wikipedia: Hindley–Milner type system). This is the foundation for every subsequent typed functional language.
Implementation. The original ML was implemented as an embedded language of Cambridge LCF; it ran under Franz Lisp and later under specialized runtimes (Wikipedia: ML). Standard ML (definition 1990, revised 1997 as “SML ‘97”) was the first attempt to give ML a rigorous formal definition — Robin Milner, Mads Tofte, and Robert Harper’s The Definition of Standard ML (MIT Press, 1990/1997) is one of the few production programming languages defined by a completely formal operational semantics (Wikipedia: ML; History of Standard ML — Harper). SML/NJ (Standard ML of New Jersey, 1988 onward) and the Moscow ML, Poly/ML, and MLton compilers followed (History of Standard ML — Harper).
Influence. ML is the direct ancestor of OCaml (Xavier Leroy et al., 1996), F# (Don Syme, 2005), and Haskell (1990, adding lazy evaluation and monadic effects) (Wikipedia: ML). Hindley–Milner inference and algebraic data types have propagated into Scala, Rust, Swift, Kotlin, TypeScript, and Elm (Wikipedia: Hindley–Milner type system). Milner received the 1991 ACM Turing Award for LCF, ML, and CCS (his calculus of communicating systems) (Wikipedia: ML).
Forth (1970) — Charles Moore’s concatenative minimalism
Forth was designed by Charles H. Moore starting around 1968, with the mature language appearing in 1970 at the National Radio Astronomy Observatory in the software controlling their radio telescopes (Wikipedia: Forth (programming language); Wikipedia: Charles H. Moore). Moore’s motivation was extreme resource constraint: the language, its compiler, its interpreter, its debugger, and the user’s programs all had to fit into tens of kilobytes on minicomputers, and the resulting programs had to be small, fast, and easy to modify in the field (Wikipedia: Forth; Wikipedia: Charles H. Moore).
Design decisions. Forth is a stack-based language: operands are pushed on an operand stack, and operators consume operands from the top of the stack and push results back. 2 3 + . pushes 2, pushes 3, adds them (leaving 5 on the stack), and prints (Wikipedia: Forth). It is concatenative: juxtaposing two “words” (Forth’s term for functions) means composing them, so f g applied to a stack is g(f(stack)) (Wikipedia: Forth).
Every Forth program is a dictionary of user-defined words. The core language is tiny — perhaps thirty primitives — and everything else, including the compiler, is defined in Forth (Wikipedia: Forth). Forth’s : (colon-word definition) makes it trivial to define new syntax and new control structures; there is no distinction between the compiler, the interpreter, and the standard library (Wikipedia: Forth).
Implementation. A Forth system typically consists of a small (kilobyte-scale) inner interpreter that walks threaded code — a list of addresses of subroutines to be executed — and a text interpreter that reads the source, looks up each word in the dictionary, and either executes it (in interpret mode) or compiles a call to it (in compile mode) into the current definition (Wikipedia: Forth). Direct-threaded, indirect-threaded, and subroutine-threaded code are alternative low-level implementations of the same idea (Wikipedia: Forth).
Adoption. Forth dominated embedded-systems programming from the mid-1970s through the mid-1980s (radio telescopes, industrial control, arcade games including Space Invaders), was used in Sun’s OpenBoot / Open Firmware (the boot ROM standard used by Sun, IBM AIX, Apple PowerPC Macs, and the OLPC XO), and remains in use for firmware and embedded systems today (Wikipedia: Forth).
Influence. Forth’s concatenative, stack-based model influenced PostScript (Adobe, 1982), the JVM bytecode (which is stack-based), the .NET CLR bytecode, and modern concatenative languages like Factor and Joy (Wikipedia: Forth). Forth’s philosophy — that the programmer should be able to redefine anything, including the compiler — makes it a spiritual cousin of Lisp, and its extreme minimalism is a working demonstration that Wirth’s “smaller is better” argument can be taken far further than Wirth himself took it (Wikipedia: Forth).
Cross-cutting themes
Compiler technology through the 1970s
Recursive descent parsers — top-down parsers where each nonterminal in the grammar is implemented as a mutually-recursive procedure — have been used since the 1960s and remain the dominant hand-coded parsing technique today, in production compilers for C (GCC, Clang), C++, C#, Go, Rust, and TypeScript (Wikipedia: Recursive descent parser). The technique works cleanly on the class of LL(k) grammars (top-down parseable with k tokens of lookahead) and produces the fastest and most maintainable parsers when the grammar can be arranged into LL(1) form (Wikipedia: Recursive descent parser). Pascal was explicitly designed to be LL(1)-parseable by recursive descent, which is why (for instance) types must be declared before use and forward-reference constructs are so restrictive (Wikipedia: Pascal).
LR parsing was invented by Donald Knuth in 1965 in the paper “On the Translation of Languages from Left to Right” — a bottom-up parsing technique that shifts input tokens onto a stack and, when the top of the stack matches the right-hand side of some grammar rule, reduces it to the corresponding left-hand side nonterminal (Wikipedia: LR parser). Knuth proved that LR(k) parsers were the most general-purpose deterministic parsers possible, and that any language that could be described by an LR(k) grammar could also be described by an LR(1) grammar (Wikipedia: LR parser). The canonical LR parsers described by Knuth had impractically large parse tables for 1960s memory, so LR parsing did not become practical until Frank DeRemer’s 1969 invention of the SLR (Simple LR) and LALR (Look-Ahead LR) subsets, which produced much smaller tables (Wikipedia: LR parser).
The YACC (Yet Another Compiler-Compiler) parser generator, written by Stephen C. Johnson at Bell Labs in 1970, produced LALR(1) parsers from BNF-like grammar specifications and became the tool of choice for compiler front-ends throughout the 1970s and 80s; Bison is its GNU successor and remains widely used (Wikipedia: History of compiler construction; Wikipedia: LR parser).
Symbol tables — data structures mapping identifiers to their declaration information (type, scope, storage class) — have been part of compilers since the first FORTRAN, and their design has been extensively studied; the classic 1970s compiler used a hash table per scope with a scope stack, or a single global symbol table with scope-numbered entries (Wikipedia: History of compiler construction).
Code generation in the 1970s ranged from FORTRAN-style direct emission of target machine code to intermediate-representation-based approaches like Pascal’s P-code and Wirth’s approach in the ETH compilers, and eventually to the register allocation, instruction selection, and peephole optimization techniques codified in Aho, Sethi, and Ullman’s 1977 textbook Principles of Compiler Design (the original “dragon book”) (Wikipedia: History of compiler construction).
Memory management evolution
The three memory-management regimes in play by 1970 were:
- Manual, static allocation — FORTRAN’s approach: every variable is a fixed slot in memory, all storage is decided at compile time. Works fine for FORTRAN’s original scientific workload; catastrophic for anything else (Wikipedia: Fortran).
- Stack-based allocation — ALGOL 60’s contribution: when a block is entered, its local variables are pushed on a runtime stack; when the block exits, they are popped. Enables recursion and cheap local storage but does not accommodate data whose lifetime exceeds the block that created it (Wikipedia: ALGOL 60).
- Heap allocation with garbage collection — LISP’s contribution: allocate objects on a heap, and periodically trace from roots to find live objects and reclaim the rest (History of Lisp — McCarthy, 1979; Origins of Garbage Collection — Harvard CS252).
Mark-and-sweep (McCarthy, ca. 1959) was the first algorithm: pause the mutator, traverse the object graph marking every reachable cell, then sweep the whole heap linearly, adding unmarked cells to the free list (History of Lisp — McCarthy, 1979; Origins of Garbage Collection — Harvard CS252).
Reference counting (Collins, 1960 on the CDC 1604) — each object carries a count of references to it; when the count reaches zero, the object is freed. Simple, incremental, but doesn’t collect cycles and requires atomic increments/decrements in a concurrent setting (History of Lisp — McCarthy, 1979; Origins of Garbage Collection — Harvard CS252).
Cheney’s algorithm — described in C. J. Cheney’s 1970 ACM paper — was a major advance: a copying collector that partitions the heap into two equal semi-spaces, and during collection traces live objects from the from-space to the to-space, breadth-first, using the to-space itself as the traversal queue — no auxiliary stack required (Wikipedia: Cheney’s algorithm). At the end of collection, the entire from-space is discarded in one operation, and the roles of the two spaces swap (Wikipedia: Cheney’s algorithm). Cheney’s algorithm compacts the heap (eliminating fragmentation), has runtime proportional to the live set (not the whole heap), and uses only a constant amount of extra memory beyond the two semi-spaces (Wikipedia: Cheney’s algorithm). Every generational and concurrent collector shipping in modern JVMs, CLRs, V8, and Go runtimes uses Cheney’s algorithm (or a close variant) for young-generation collection (Wikipedia: Cheney’s algorithm).
The second-system effect
Fred Brooks coined the phrase second-system effect in his 1975 book The Mythical Man-Month, describing IBM’s transition from the relatively simple operating systems of the IBM 700/7000 series to the over-ambitious OS/360 for the IBM System/360 family (announced 1964) (Wikipedia: Second-system effect). Brooks’s formulation: an architect’s first system is often “spare and clean” because the designer is still learning and is cautious about generalizations; the second is “the most dangerous” because the designer, now confident, is tempted to incorporate every previously deferred improvement, optional feature, and generalization, producing a successor that is harder to build, understand, and evolve (Wikipedia: Second-system effect).
The 1960s–70s programming-language canon of the second-system effect includes:
- ALGOL 68, second-system to ALGOL 60 — orthogonal type system, two-level grammar, coroutines, operator overloading, all in one package (Wikipedia: ALGOL 68).
- PL/I, IBM’s second-system attempt to replace FORTRAN, COBOL, and (implicitly) ALGOL — Dijkstra’s “flying a plane with 7000 buttons” jibe (Wikipedia: PL/I).
- Multics, second-system to CTSS — vast, ambitious, over-budget, and a running joke by the time it shipped; Unix (Ken Thompson’s uniplexed information and computing service) was explicitly Multics’s simpler, spartan reaction (Wikipedia: History of compiler construction).
The design lesson — repeatedly emphasized by Wirth, Hoare, and Dijkstra — is that a language designer’s second system should be smaller than the first, not larger. Wirth’s Pascal-Modula-Oberon trajectory is the working demonstration; C’s minimalism relative to PL/I is another; Scheme’s minimalism relative to Common Lisp is a third (History of Modula-2 and Oberon — Wirth).
Wirth’s Law and the tension between simplicity and expressiveness
Wirth’s Law — “software is getting slower more rapidly than hardware is becoming faster” — was formulated by Niklaus Wirth in his 1995 Computer article “A Plea for Lean Software”, drawing on an earlier observation of Martin Reiser’s (Wikipedia: Wirth’s law). Wirth traced two causes: rapidly growing hardware performance (which removes the pressure to keep software lean) and customer ignorance of the distinction between essential and nice-to-have features (Wikipedia: Wirth’s law).
For a language designer, Wirth’s Law is a design principle: the language, its compiler, and its runtime should be as small as they can be for the problem they solve, because they will grow anyway and any complexity added at the start compounds through the language’s life (Wikipedia: Wirth’s law; Wikipedia: Niklaus Wirth).
The counter-argument — that a language must have enough expressiveness to support the abstractions its users need, else those users will bolt on their own ill-designed extensions (macros, DSLs, code generators) — is equally old. The tension between simplicity and expressiveness is the axis on which the field’s design debates play out: ALGOL 68 vs Pascal, PL/I vs C, Common Lisp vs Scheme, C++ vs C, Perl vs Python, Scala vs Kotlin. Each pair chooses a different point on the same axis, and each choice is a bet about which class of user the language is really for.
Early type theory: Russell/Whitehead, Church, Curry
Russell and Whitehead’s Principia Mathematica (three volumes, 1910/1912/1913, with a second edition in 1927) introduced ramified type theory as the technical device Russell used to resolve his own paradox in Frege’s naive set theory (Wikipedia: Principia Mathematica). Russell’s types are a hierarchy — individuals at level 0, properties of individuals at level 1, properties of properties at level 2, and so on — with the syntactic rule that a property can only be applied to entities strictly below it in the hierarchy, so x ∈ x is not even well-formed (Wikipedia: Principia Mathematica).
Church’s simple types (1940) rebuilt the same idea on a functional foundation: base types (ι, ο) plus a function-type constructor A → B, with every lambda term assigned a unique type derivable from its structure (Wikipedia: Simply typed lambda calculus). Where Russell’s types were ramified (indexed by order and by level), Church’s were flat and structural, and thus much easier to work with — Church’s system is the direct mathematical ancestor of every modern static type system (Wikipedia: Simply typed lambda calculus).
Curry types are Curry’s implicit or à la Curry formulation of the simple type system: terms are the untyped lambda terms, and typing is a separate judgment (Γ ⊢ M : A) rather than a decoration of the term itself, so a given term can be assigned many types (or none) (Wikipedia: Simply typed lambda calculus; Wikipedia: Hindley–Milner type system). Roger Hindley’s 1969 paper “The Principal Type-Scheme of an Object in Combinatory Logic” proved that if a Curry-typed term is typable at all, there is a unique most general type — the principal type — from which all other types can be obtained by substitution (Wikipedia: Hindley–Milner type system). Milner’s 1978 paper “A Theory of Type Polymorphism in Programming” independently re-derived the result for ML and gave the algorithm now called Algorithm W for type inference (Wikipedia: Hindley–Milner type system).
The two traditions — Church’s explicit types on the terms themselves (“Church-style”), and Curry’s implicit types inferred from the terms (“Curry-style”) — are still the two poles of contemporary type-system design. Java, C#, C++, and Rust are Church-style: every variable declaration specifies its type. Haskell, OCaml, and Standard ML are Curry-style: types are inferred, and annotations are (mostly) documentation (Wikipedia: Hindley–Milner type system).
Coda — what a language designer should take from this era
Reading the archival papers of Backus, McCarthy, Hopper, Wirth, Ritchie, Dahl and Nygaard, Colmerauer, Kay, Milner, and Steele-and-Sussman reveals a small set of recurring patterns that shaped every language that followed.
- A language succeeds because its implementation is good. FORTRAN succeeded because its compiler produced fast code (FORTRAN Session — Backus); C succeeded because it was portable enough that Unix could go anywhere it went (Ritchie, The Development of the C Language); Pascal succeeded because the P-code implementation let any university port it in a week (Wirth, Recollections). Ambitious language designs die when they cannot be implemented well enough for their intended users (Wikipedia: ALGOL 68).
- Simplicity is a feature that has to be defended. ALGOL 68, PL/I, and Common Lisp all show what happens when a committee tries to include every feature its members like (Wikipedia: ALGOL 68; Wikipedia: PL/I). Scheme, Pascal, and C each derive much of their historical importance from the discipline of what they left out (History of the Scheme programming language).
- Type systems are a form of documentation the machine reads. Church’s 1940 STLC, Curry’s implicit types, Hindley’s principal types, and Milner’s Algorithm W between them prove that a well-designed static type system can catch entire categories of errors before the program ever runs, without imposing much cost on the programmer (Wikipedia: Hindley–Milner type system).
- Memory management is a runtime choice with pervasive language consequences. LISP and Simula have garbage collection; FORTRAN, C, and Pascal do not. This one choice determines whether closures work naturally, whether object lifetimes need to be manually tracked, and whether the language can support functional programming idioms without leaks (History of Lisp — McCarthy; Wikipedia: Cheney’s algorithm).
- Every paradigm exists in reaction to a real problem. OO exists because Nygaard needed to simulate real-world entities (The Birth of Object Orientation — Dahl). Logic programming exists because Colmerauer wanted to do natural-language deduction (The Birth of Prolog — Colmerauer & Roussel). ML exists because Milner needed a metalanguage for a proof assistant (Wikipedia: ML). Structured programming exists because Dijkstra was tired of programs no one could reason about (Go To Statement Considered Harmful — Dijkstra). A new paradigm without a real motivating problem is a solution in search of a language.
- The best histories are written by the designers. The single most valuable source in this whole survey is not any Wikipedia page but the HOPL (History of Programming Languages) conference papers by the languages’ original authors: Backus on FORTRAN, McCarthy on LISP, Wirth on Pascal and Modula and Oberon, Ritchie on C, Kay on Smalltalk, Dahl on Simula, Colmerauer and Roussel on Prolog, Steele and Sussman on Scheme, Milner on ML. Reading them directly is worth more than any secondary summary — they show what the designers actually thought they were doing, and, in every case, what they wish they had done differently (FORTRAN Session — Backus; History of Lisp — McCarthy; Recollections on Pascal — Wirth; Development of C — Ritchie; Early History of Smalltalk — Kay; The Birth of Prolog — Colmerauer & Roussel; Lambda Papers — Steele & Sussman).
End of report.