A machine that writes programs: the birth of compilers

Philadelphia, spring 1952. You work for Remington Rand, and your computer is a UNIVAC I: five thousand valves, a whole room, mercury delay-line memory. Programming it means writing by hand, on squared paper, a sequence of machine-code instructions, each with its own memory address. If halfway through you realise you need one more instruction, you have to shift every instruction after it and fix every address that refers to them. By hand. With an eraser.

On your desk you keep a notebook full of code you reuse all the time: sine, square root, printing a number. When you need them, you copy them into the new program and recompute the addresses. Every copy is a chance to get a digit wrong, and the computer won't tell you where.

In the same building works Grace Hopper, a mathematician and Navy reserve officer who came from the Harvard Mark I group. She has an idea your colleagues find almost offensive: if copying subroutines and fixing addresses is mechanical work, why not let the machine do it?

A-0: the computer that writes its own programs

The system Hopper builds between 1951 and 1952 is called A-0. Subroutines are stored on magnetic tape, each with a reference number. You write a program that says, in essence, "take subroutine 12 with these arguments, then 7, then 31", and A-0 finds them on the tape, lines them up, fixes the addresses and produces the complete program in machine code. In May 1952 Hopper presents it at an ACM meeting in Pittsburgh, in a paper titled The Education of a Computer.

Historians still argue whether A-0 is really a compiler: it's closer to what we'd call a linker, joining together pieces of code already written. But the underlying idea is what counts: a program that produces other programs. And your colleagues' reaction counts even more. The common view is that a computer can do arithmetic, not write programs. It will take a couple of years for the idea to be taken seriously.

Hopper doesn't stop. Her group moves on to A-2 and then to FLOW-MATIC, a language for business applications that uses English words instead of mathematical symbols. When, in 1959, a committee of companies and the US government designs COBOL, FLOW-MATIC is one of its main models.

A moth in the logbook

At lunch someone tells the moth story again, and you decide to check it. On 9 September 1947, at 15:45, the operators of Harvard's Mark II found a moth stuck in relay 70 of panel F. They taped it into the operations logbook with a note: First actual case of bug being found.

Two details always get lost in the retelling. First: engineers had been using the word bug for a defect for decades (Edison used it too), and the joke in the note is precisely that "actual". Second: according to the Smithsonian, which keeps the logbook today, it probably wasn't Hopper's notebook, nor was she the one who found the insect. She was part of the team, though, and told that story for the rest of her life, making it famous.

Meanwhile, in Zurich and Manchester

You're not the only person in the world with this problem, and neither is Hopper. In Manchester, in 1952, Alick Glennie writes a system called Autocode for the Mark 1 computer, translating a more readable notation into its notoriously cryptic machine code. Many consider it the first compiled language. Glennie doesn't distribute it, though, and almost nobody else uses it: years later Donald Knuth will call Glennie the "unsung hero" of this story.

And in Zurich, at the end of 1951, a young mathematician from Milan named Corrado Böhm defends a doctoral thesis at the Swiss Federal Institute of Technology in which he does something nobody had done: he defines a programming language, an abstract machine, and a compiler for that language written in the language itself. It's the first description of a compiler able to compile itself, an idea that will come back later in this story. Böhm went on to become one of the fathers of Italian theoretical computer science: the Böhm-Jacopini theorem of 1966 proves that any program can be written using only sequence, selection and iteration, and it's the theoretical basis of structured programming.

1954: the priesthood and FORTRAN

Two years later you change jobs and move to IBM, on the new 704. There you meet John Backus's group, working on a system to translate mathematical formulas into machine code: FORmula TRANslation, FORTRAN. On 10 November 1954 the group finishes a preliminary report with a sentence that makes you laugh: FORTRAN, it says, "should virtually eliminate coding and debugging".

You're not the only one laughing. The programmers of the time are, in the words Backus will use years later, a "priesthood": people proud of working around the quirks of the hardware and of squeezing a program into a few thousand words of memory. The "automatic programming" systems seen so far produced code five to ten times slower than hand-written code. And machine time was extremely expensive: nobody would accept wasting it.

Backus knows this, and makes a decision that will shape the history of compilers: the main goal isn't the language, it's the efficiency of the generated code. FORTRAN must produce programs almost as fast as those written by the best programmers, or nobody will use it. The group spends most of its time on optimisation: how to allocate registers, how to transform loops, how to avoid computing the same expression twice.

In April 1957 FORTRAN starts shipping to 704 customers. You try comparing its code with yours, instruction by instruction, sure you'll beat it. In many cases you don't. Coding and debugging haven't disappeared, as the report promised: they've moved up a floor. But a program that used to cost you weeks now costs you days.

What a compiler does, in thirty lines

Seventy years later, a modern compiler still does the same four things FORTRAN did. You can see them in miniature with a small compiler in Python, for a language that only knows assignments and arithmetic:

import re

def tokenize(src):                     # 1. lexical analysis: text → words
    return re.findall(r"\d+|[a-z]+|[-+*/()=]", src)

def parse(tokens):                     # 2. parsing: words → tree
    pos = 0
    def peek():
        return tokens[pos] if pos < len(tokens) else None
    def take():
        nonlocal pos
        pos += 1
        return tokens[pos - 1]
    def expr():                        # sums and differences
        node = term()
        while peek() in ("+", "-"):
            node = (take(), node, term())
        return node
    def term():                        # products and divisions bind tighter
        node = factor()
        while peek() in ("*", "/"):
            node = (take(), node, factor())
        return node
    def factor():                      # number, variable or parentheses
        t = take()
        if t == "(":
            node = expr(); take()
            return node
        return int(t) if t.isdigit() else t
    target = take(); take()            # "y" "="
    return ("=", target, expr())

def fold(n):                           # 3. optimisation: compute constants right away
    if not isinstance(n, tuple):
        return n
    op, a, b = n[0], fold(n[1]), fold(n[2])
    if op != "=" and isinstance(a, int) and isinstance(b, int):
        return {"+": a + b, "-": a - b, "*": a * b, "/": a // b}[op]
    return (op, a, b)

def gen(n, out):                       # 4. code generation (stack machine)
    if isinstance(n, int):
        out.append(f"PUSH  {n}")
    elif isinstance(n, str):
        out.append(f"LOAD  {n}")
    elif n[0] == "=":
        gen(n[2], out); out.append(f"STORE {n[1]}")
    else:
        gen(n[1], out); gen(n[2], out)
        out.append({"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV"}[n[0]])
    return out

ast = parse(tokenize("y = a * (2 + 3) + b"))
print("\n".join(gen(fold(ast), [])))

The result, step by step:

# tokens
['y', '=', 'a', '*', '(', '2', '+', '3', ')', '+', 'b']
# syntax tree: the multiplication sits "below" the sum
('=', 'y', ('+', ('*', 'a', ('+', 2, 3)), 'b'))
# after optimisation: 2 + 3 has become 5
('=', 'y', ('+', ('*', 'a', 5), 'b'))
# generated code
LOAD  a
PUSH  5
MUL
LOAD  b
ADD
STORE y

The heart of the work is going from text to tree: that's where the compiler "understands" that the multiplication comes before the sum, something a 1952 programmer had to remember alone, instruction by instruction. In 1960, to describe ALGOL's grammar, Backus and Peter Naur introduced a formal notation for writing rules like expr, term and factor: Backus-Naur Form, still used today in the specification of almost every language.

Backus's legacy: the optimiser

Backus's choice to bet everything on efficiency is still visible in every compiler today. Take a trivial C function:

int f(int x) { return x*8 + x*2; }

Compiled by gcc without optimisation (-O0), it becomes an almost literal translation, with the value passing through the stack:

f:  push  rbp
    mov   rbp, rsp
    mov   DWORD PTR -4[rbp], edi
    mov   edx, DWORD PTR -4[rbp]
    mov   eax, edx
    sal   eax, 2
    add   eax, edx
    add   eax, eax
    pop   rbp
    ret

With -O2 this is what's left:

f:  lea   eax, [rdi+rdi*4]    ; eax = x*5
    add   eax, eax            ; eax = x*10
    ret

The compiler worked out that x*8 + x*2 is x*10, and that multiplying by ten is faster with an addressing instruction (lea, which computes x + x*4) and a doubling. No multiplication, no memory access. It's exactly the kind of trick the 1954 "priesthood" was sure a machine would never find.

The chicken and the egg

Sooner or later everyone who studies compilers asks the same question: the C compiler is written in C. Who compiled the first one? The answer is called bootstrapping, and Böhm had already described it in 1951: you write a minimal first version in a simpler language (or in machine code), use it to compile a version written in the language itself, and from then on the compiler compiles its own later versions. You can see the last link of the chain on any Linux system, by reading who compiled your compiler:

$ readelf -p .comment $(command -v gcc)
String dump of section '.comment':
  [     0]  GCC: (Alpine 13.2.1_git20240309) 13.2.1 20240309

gcc compiled by gcc, which in turn was compiled by an earlier gcc, and so on backwards, for decades. And that's exactly where, in 1984, Ken Thompson put his finger on the wound. In the text of his Turing Award lecture, received with Dennis Ritchie for Unix, titled Reflections on Trusting Trust, Thompson describes an attack in three steps:

1. modify the compiler so that, when it compiles the login program, it inserts a backdoor;
2. also modify it so that, when it compiles itself, it inserts both of these changes into the new compiler;
3. compile the modified compiler, then put the original, clean source back.

From then on the backdoor exists in no source code at all, yet it reproduces itself at every recompilation, because it lives only in the compiler binary. Thompson's conclusion is that you can't trust code you didn't write entirely yourself, compiler included. Reading the source isn't enough.

For twenty years it looked like a problem without a solution. In 2005 David A. Wheeler proposed a method called diverse double-compiling, developed further in his 2009 doctoral thesis: you recompile the suspect compiler's source with a second, independent compiler, recompile it again with the result, and compare the final binary bit by bit with the original. If they match, the binary really corresponds to its source. And in 2023 the GNU Guix project completed a full-source bootstrap: the entire distribution, more than twenty-two thousand packages, is built starting from an initial program of 357 bytes, small enough for a person to read and verify. The notebook of hex codes is back, in other words. Only this time it's there for trust, not for work.

Monday 15 September 2025

Seventy-three years after your first UNIVAC program, the latest gcc is 15.2, released on 8 August. Dr Brambilla walks past your desk with his phone in hand: he's just read that with artificial intelligence "nobody will need to write code any more", and he wants to know how much it will save.

You show him the sentence from the 1954 FORTRAN report: should virtually eliminate coding and debugging. Brambilla reads it twice, nods happily and asks when this FORTRAN came out.

"In 1957," you tell him.

He thinks for a moment. "So why am I still paying you?"