Skip to content

John Backus and FORTRAN

Abstract

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.

John Backus
John Backus. Image: PIerre.Lescanne, CC BY-SA 4.0, via Wikimedia Commons.

The IBM 701 and the Speedcode Experiment

John Warner Backus was born in Philadelphia on December 3, 1924. He was expelled from the University of Virginia after less than a year of chemistry, was drafted into the Army, dropped out of medical school in New York after nine months, trained as a radio technician, and only then found mathematics, taking a bachelor’s (1949) and a master’s (1950) at Columbia. He joined IBM in New York in 1950, worked first on the SSEC, a relay and vacuum-tube calculator, and then on the IBM 701, IBM’s first commercial scientific computer.

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. 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.

In 1953 Backus wrote Speedcoding, an interpreter for the 701 that let programmers work with floating-point numbers as if the machine had floating-point hardware. Speedcoding 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 late 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, which began work in early 1954 with about ten people and later included the mathematician Lois Haibt, proved the skeptics wrong. A preliminary report on the language followed in November 1954 and the Reference Manual in October 1956, but the compiler took until early 1957: the team presented the “FORTRAN Automatic Coding System” at a conference in Los Angeles in February 1957, and FORTRAN I shipped in April 1957 for the IBM 704. FORTRAN II with subroutines followed in 1958, FORTRAN IV in 1962. Its optimizer, which analysed loops and index registers, produced code that came close to what good programmers wrote by hand, which was the point of the whole project.

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. In 1958, after a year and a half of use, Backus reported that over half the instructions being written for some sixty 704 installations were thought to be produced by FORTRAN, and that it cut the cost of programming and debugging by about four to one. 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 out of committee work. He was one of the American delegates at the 1958 Zurich meeting that designed an international scientific language, ALGOL 58, which led to ALGOL 60.

To describe the syntax of that language precisely, Backus devised a formal notation for grammars and presented it at the UNESCO conference on information processing in Paris in June 1959. 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 and used his lecture, published in 1978, to argue that the languages descended from FORTRAN had reached 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

Backus coined the term in the lecture. A von Neumann computer, he wrote, has a CPU, a store, “and a connecting tube that can transmit a single word between the CPU and the store… I propose to call this tube the von Neumann bottleneck.” His complaint was that languages had copied the tube: “Surely there must be a less primitive way of making big changes in the store than by pushing vast numbers of words back and forth through the von Neumann bottleneck.” Conventional languages, in his words, had a “primitive word-at-a-time style of programming inherited from their common ancestor, the von Neumann computer.”

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, 2023: 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.

๐Ÿ“š Sources