Bootstrapping and Self-Hosting

Here is a puzzle that sounds like it cannot possibly have an answer. The Go compiler is written in Go. The Rust compiler is written in Rust. But to compile the Rust compiler you need a working Rust compiler — which you were trying to build. To make the first hammer, what did you hit the metal with? A compiler that can compile its own source code is self-hosting, and the process of getting the first one into existence — pulling yourself up by your own bootstraps — is bootstrapping.

The chicken-and-egg only looks unbreakable. The trick is that the first version need not be written in the language itself, and need not be good. Once any working compiler for the language exists — however primitive, in whatever other language — it can compile the real, self-hosted compiler, and from then on the language sustains itself. To see the moves clearly we need a notation that tracks the three languages in play at every step. That notation is the T-diagram.

The T-diagram (tombstone diagram)

A compiler involves three languages, and confusing them is the source of every bootstrapping headache. The source language S is what it reads; the target language T is what it writes; and the implementation language I is what the compiler itself is written in. A T-diagram (or tombstone diagram, after its shape) draws all three at once: S at the top-left, T at the top-right, I in the stem.

Read it aloud as: "a compiler from S to T, written in I." The power of the notation is that T-diagrams compose: you may slot one compiler's stem into another's when the languages line up, and the geometry tells you exactly when a chain of tools will actually run.

The bootstrap dance

Suppose we are creating a new language L and want a self-hosting compiler that emits native machine code M and is itself written in L. We cannot run that compiler yet — nothing speaks L. The classic three-move sequence gets us there. Reveal it step by step.

The pattern is worth committing to memory. Move 1: write a compiler for a subset of L in some existing language X (say C) — small, ugly, but real. Compiling it with the existing X compiler gives a running L_0\!\to\!M tool. Move 2: now write the full compiler in L itself (using only the subset L_0 understands) and compile it with the tool from move 1 — producing a native, self-hosted compiler. Move 3: feed the full compiler's source through itself. If the output is a working compiler, the language now stands on its own, and X can be thrown away forever.

Why the last recompile matters: the fixed-point test

Move 3 is not ceremony. When the compiler compiles its own source, the binary it produces should be bit-for-bit identical to the compiler that produced it — a fixed point. This is the famous "three-stage bootstrap" used by GCC and LLVM as a correctness check.

// The three-stage bootstrap as a fixed-point check. // stage1: the new compiler, built by the OLD trusted compiler. // stage2: the new compiler, built by stage1 (so: new building new). // stage3: the new compiler, built by stage2 (new building new AGAIN). // If the compiler is deterministic and self-consistent, stage2 === stage3. function build(builderTag: string, sourceVersion: string): string { // A binary is a function of WHICH compiler built it and the source it built. // A correct, deterministic self-hosting compiler ignores the builder's identity // and depends only on the source version it compiles. return `bin(${sourceVersion})`; // builderTag deliberately not in the output } const oldCompiler = "bin(v9-old)"; const stage1 = build(oldCompiler, "v10"); // old builds new const stage2 = build(stage1, "v10"); // stage1 builds new const stage3 = build(stage2, "v10"); // stage2 builds new console.log(`stage1 = ${stage1}`); console.log(`stage2 = ${stage2}`); console.log(`stage3 = ${stage3}`); console.log(`stage2 === stage3 ? ${stage2 === stage3} <- must be TRUE`); console.log("If they differ, the compiler is non-deterministic or self-inconsistent: bug!");

The logic: stage 1 was built by the old compiler, so it might carry subtle differences (it was translated by different code). But stage 2 and stage 3 were both built by an already-new compiler from the same source, so a correct, deterministic compiler must produce identical binaries. A mismatch means a bug — non-determinism, or a compiler that doesn't faithfully reproduce itself. It is one of the most elegant self-tests in all of software.

Cross-compilation: bootstrapping onto new hardware

The same T-diagram machinery answers a second question: how do you get a compiler running on a brand-new chip that has no compiler yet? You cross-compile. On an existing host machine H, take your L\!\to\!M_{\text{new}} compiler but have it emit code for the new target M_{\text{new}} while still running on H. Compile the compiler with it, ship the resulting M_{\text{new}} binary to the new hardware, and it runs there natively — the new machine is now self-hosting, without ever having built a compiler locally. Every new CPU architecture in history was bootstrapped this way: the first program that ever ran on it was cross-compiled somewhere else.

By stepping outside the language. The first Fortran compiler (1957) was hand-written in assembly. The first C compiler grew out of B, which grew out of BCPL, which was compiled by earlier tools written in still-older languages — a chain that bottoms out, eventually, at machine code someone entered by hand, toggle switches and all. Every self-hosting language has this ancestry: somewhere back down the line, a human wrote the seed compiler in a different, already-runnable language. Bootstrapping is not circular; it is a spiral that touches down once, on solid ground, at the very start. After that first contact, the language lifts off and never needs the ladder again — which is exactly why languages proudly announce "the compiler is now written in itself" as a rite of passage.

The classic confusion is to think a self-hosting compiler somehow compiled its own first version — an impossible loop. It did not. Keep the three languages of the T-diagram straight and the paradox evaporates: the first compiler for language L has implementation language I \neq L (assembly, C, another language entirely). Only later versions have I = L, and each of those is compiled by the previous working binary, never by itself-before-it-exists.

So "the compiler is written in itself" describes a steady state, reached after the bootstrap — not the origin. At every single moment there was already a working tool doing the compiling; what changed is which language that tool was written in. Mistake the steady state for the beginning and you invent a paradox that history simply never had.

In his 1984 Turing Award lecture, Ken Thompson posed a chilling question: could you trust a compiler you did not write? He described planting a backdoor not in a program's source, but in the compiler — teach it to recognise when it is compiling, say, the login program, and silently insert a hidden password. Then go further: teach the compiler to recognise when it is compiling itself, and re-insert both hacks into the new compiler binary. Now delete the malicious source entirely. The backdoor lives on, invisibly, propagated through every future self-compilation. Inspect all the source you like — the source is clean — yet every compiler descended from that poisoned binary carries the attack.

Thompson's moral: "You can't trust code that you did not totally create yourself" — and since no one writes their own compiler, CPU microcode and silicon, trust ultimately rests on the whole toolchain, not the source alone. It is bootstrapping's shadow: the very self-reproduction that lets a language stand on its own also lets a lie reproduce itself forever. Modern work on reproducible builds and "diverse double-compiling" is the compiler community's answer to the ghost Thompson raised.