John Backus and FORTRAN

Zusammenfassung

In 1957, a team at IBM led by John Backus released a compiler that many mathematicians thought impossible: a program that translated algebraic formulas into efficient machine code. FORTRAN proved that human-readable language could produce programs as fast as hand-coded assembly — and in doing so, created the template for every compiled high-level language that followed. Twenty years later, Backus gave a Turing Award lecture arguing that FORTRAN and its successors were all variants of the same fundamentally limited model. He was right, and almost no one listened.

The IBM 701 and the Speedcode Experiment

John Warner Backus was born in Philadelphia on December 3, 1924. He was an unremarkable student who spent a semester studying medicine before discovering mathematics. He joined IBM in 1950 as a programmer on the IBM 701 — IBM’s first commercial scientific computer — and quickly became one of the company’s most productive technical people.

The immediate problem was productivity. Programming the 701 required writing machine code or assembly — explicit instructions for moving data between registers, memory, and arithmetic units. A competent programmer could produce perhaps ten to twenty debugged instructions per day. Scientific calculations that mathematicians could specify in a few lines of algebra required hundreds or thousands of assembly instructions. The bottleneck was not the machine; it was the translation from mathematical notation to machine notation.

Backus wrote a small interpreter called Speedcode for the 701 that allowed programmers to write formulas in a notation closer to mathematics. Speedcode programs ran significantly slower than hand-coded assembly — the interpreter overhead was substantial — but programmers could write them much faster. The lesson Backus drew was different from the lesson most people drew: the overhead was a compiler problem, not an inherent cost of high-level notation.

FORTRAN: The Bet That Compilers Could Compete

In 1953, Backus proposed to IBM management a project to develop a compiled language for scientific computation. The pitch was direct: FORTRAN (FORmula TRANslation) would allow programmers to write algebraic expressions and have them translated automatically into efficient machine code. The resulting code would be competitive with hand-coded assembly.

The proposal was met with skepticism. Professional programmers considered the claim implausible. A compiler, translating without human judgment, could not be expected to generate the carefully optimized register assignments that experienced programmers produced by hand. If the compiled code was significantly slower than assembly, no serious scientific user would adopt it.

Backus’s team — thirteen programmers over four years — proved the skeptics wrong. FORTRAN I shipped in April 1957 for the IBM 704. The compiler generated code that was, in practice, within a factor of two of expert hand-coded assembly for typical scientific programs, and often faster because it applied register allocation optimizations consistently where tired programmers made mistakes.

      C EARLY FORTRAN (1957)
      DIMENSION A(10), B(10), C(10)
      DO 10 I = 1, 10
          C(I) = A(I) + B(I)
   10 CONTINUE

The adoption was rapid. Within eighteen months, more than half of all programming on IBM 704 installations was done in FORTRAN. The reduction in programming time was so large that it changed what scientists could realistically attempt.

BNF: A Notation for Languages

Backus’s second major contribution came in 1959 in a context entirely different from compiler engineering. He was assigned to represent the American programming language community at a meeting to design an international scientific language — what would become ALGOL 58 and then ALGOL 60.

To describe the syntax of the new language precisely — in a way that left no ambiguity — Backus invented a formal notation for grammars. BNF, now known as Backus-Naur Form (the Danish computer scientist Peter Naur refined and promoted it for the ALGOL 60 report), used simple recursive rules to define the structure of valid programs:

<digit>      ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<integer>    ::= <digit> | <integer> <digit>
<expression> ::= <integer> | <expression> + <expression>

BNF became the universal notation for language syntax and compiler construction. Every programming language reference manual, every parser generator (yacc, ANTLR, bison), every formal grammar specification uses a notation derived from Backus’s 1959 invention. It is arguably his most durable contribution — used daily by language designers and compiler writers who have never heard his name.

The Turing Award Lecture: A Critique of His Own Creation

In 1977, Backus received the Turing Award — computing’s highest honor — and used his acceptance lecture to argue that everything he had built was a dead end.

His lecture, “Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs,” was a systematic critique of what he called von Neumann languages: all the major programming languages of 1977, including FORTRAN, COBOL, Pascal, PL/I, and Algol. These languages, Backus argued, shared the fundamental limitation of being organized around the idea of assigning values to named locations in memory — variables. This model was not a natural consequence of mathematics or computation; it was an artifact of the von Neumann architecture, which communicated between CPU and memory by shuffling values through a bottleneck one word at a time. Programming languages had inherited the bottleneck and built it into their semantics.

Backus proposed FP (Functional Programming), a language organized not around variables and assignment but around function composition. Programs were constructed by combining functions using a small set of algebraic combining forms. The resulting programs had properties that could be reasoned about mathematically — the algebra of programs — in a way that variable-based programs could not.

The Bottleneck Metaphor

Backus used a vivid metaphor: programmers using von Neumann languages are like people who can only carry one shopping item at a time across a busy street, because the store and the house can only communicate through a one-item slot. The Von Neumann bottleneck — the single bus between CPU and memory — imposed a serial, word-at-a-time model of computation, and languages had made that model permanent by building variables and assignment into their foundations.

Dead End: FP and the Road Not Taken

The FP language was never widely adopted. Backus had built it as a demonstration of principles, not a practical tool, and it showed: FP programs were difficult to write and the language lacked the libraries, tooling, and community of practice that made FORTRAN and its successors productive environments.

More fundamentally, the industry Backus was addressing had committed billions of dollars and decades of institutional investment to the von Neumann model. FORTRAN II, III, IV, 66, 77, 90, 95, 2003, 2008, 2018 — the language he had built to prove compilers were possible was still being standardized long after his lecture. The critique was absorbed theoretically — functional programming research flourished in the 1980s and 1990s, and the features Backus identified as essential (higher-order functions, immutability, algebraic reasoning) eventually appeared in mainstream languages — but as additions to variable-based languages rather than replacements.

The fuller story of functional programming’s influence on the industry is traced in The Rise of Functional Programming. The first generation of high-level languages that FORTRAN initiated is covered in The Rise of High-Level Languages.