Bootstrapping a Compiler

The question is genuinely puzzling the first time. A compiler for a language is often written in that language: rustc is Rust, the Go compiler is Go, Clang is C++, and a C compiler is very commonly C. So the source cannot be compiled without a compiler for the language it is written in, which does not exist yet.

The resolution is that the first one is written in something else. You implement a small compiler for a *subset* of the language, in whatever is available — assembly, C, another high-level language — and it only has to be good enough to compile the real compiler's source. Then you compile the real compiler with it, and from that point on you have a compiler for the language and never need the first one again.

The crucial relaxation is "subset". Stage 0 does not implement the language; it implements enough of it to compile one specific program. If the compiler's own source avoids generics, or exceptions, or the fancy pattern matching, stage 0 need not know about any of them. It also need not optimize, produce good errors, or be fast. It has one user and one input.

The first C compiler is the canonical case and it is documented in Dennis Ritchie's own account. It began as a translator written in B, itself a descendant of BCPL, and grew incrementally: each version of the compiler was written in the subset of C that the previous version already supported. Adding a feature meant first teaching the compiler to compile it, then using it. Ritchie describes bootstrapping the character escape \n this way — the compiler had to be taught the escape before its own source could use it, so the first version encoded it numerically.

rustc bootstrapped from OCaml. The original Rust compiler was written in OCaml, and once it could compile enough Rust, the compiler was rewritten in Rust and the OCaml one retired. Today rustc is built by downloading a previous released rustc — the "beta" compiler — which is stage 0. That means the chain does not go back to OCaml at build time; it goes back to a binary Rust's infrastructure produced, which is a very different trust proposition and is exactly what [[trusting-trust]] is about.

Go was written in C and then translated. Through Go 1.4 the compiler and runtime were C programs; for Go 1.5 the team ran an automated translation of that C source into Go and then developed the result as Go, so the modern chain bootstraps from a previous Go release. The 1.4 C compiler remains the historical root, and Go maintains an explicit documented bootstrap path from it.

And GCC is built in three stages every time, as a matter of routine, precisely to run the identity check the previous section named. That is standard practice rather than a special event, which is what makes it a useful verification rather than a ceremony.

There is a practical wrinkle in the modern chains that is easy to miss. Rust and Go both bootstrap from a *previous binary release* rather than from their historical stage 0. That is efficient and it means the trust chain at build time is: this compiler is trustworthy because the last one was, which was trustworthy because the one before it was, going back to a binary somebody produced years ago and which nobody can now rebuild from scratch on current hardware.

For a distribution that wants to build everything from source, this is a genuine problem: a binary you did not build is a dependency you cannot audit. It is why Debian, Guix and others care about bootstrappability as an explicit property, and why the Bootstrappable Builds project exists — an effort to reduce the unauditable seed to something a human could inspect, starting from a few hundred bytes of hex and building upward through progressively larger compilers.

The honest position is that this is unsolved for most modern toolchains and improving for a few. It is worth knowing about because it reframes what a bootstrap chain is for: not merely a historical curiosity about how the first compiler existed, but a live question about what you are actually trusting when you run a build today.