What is Compiler Bootstrapping?
The chicken-and-egg problem
A compiler is just a program, and like any program in a compiled language it has to be compiled before it can run. So how do you compile the very first compiler for a brand-new language, when no compiler for that language exists yet? This is the bootstrapping problem, and every self-hosting language has had to solve it.
The answer is to break the circular dependency once, at the beginning, using a language that already works. The first compiler, the stage 0 or "seed" compiler, is written in an existing language such as C, OCaml, or assembly. It only needs to be good enough to compile the second compiler, which is written in the new language itself. From then on, the language can compile itself and the seed can be retired.
The three bootstrap stages
A typical self-hosting build runs in three stages, and the last two are the proof that bootstrapping succeeded:
- Stage 0 (seed): An existing compiler, often a previous release of the same compiler downloaded as a binary, or a one-time compiler written in another language.
- Stage 1: Use stage 0 to compile the current compiler source (written in the new language). The result is a working compiler, but it was produced by the older stage-0 compiler, so it may not yet contain the newest optimizations.
- Stage 2: Use the stage-1 compiler to compile the same source again. Now the compiler has compiled itself. Building a stage 3 and checking that it is byte-for-byte identical to stage 2 is a common correctness test: if a compiler compiled by itself produces the same compiler again, the toolchain is internally consistent.
Bootstrap chain diagram
Why languages bootstrap
Self-hosting is a milestone of maturity. It proves the language is expressive and complete enough to build a large, performance-sensitive systems program, a compiler. It also lets the compiler team write the compiler in the language they are designing, so every improvement to the language immediately benefits the tool that builds it. Finally, it removes the long-term dependency on a foreign implementation language.
Real bootstrap chains from the dataset
The Language Lineage dataset records the historical implementation language for each toolchain via bootstrap_written_in edges. Here are two chains in detail:
Rust via OCaml
Rust began as Graydon Hoare's personal project in 2006. The first compiler, rustboot, was written in OCaml. OCaml's algebraic types and pattern matching were well-suited to the experimental type-system work Rust required. Mozilla sponsored the project in 2009, and the team gradually rewrote rustboot in Rust. By 2011, rustc could compile itself: the OCaml dependency was gone. Each rustc release since then has been compiled by the previous stable release. The mrustc project (written in C++) provides an alternative seed that can compile an early rustc without trusting a prior Rust binary.
Go via C at version 1.5
Go's original toolchain was written in C. The Go team at Google designed the language starting in 2007 and open-sourced it in November 2009, with a Plan 9-style C compiler as the implementation. In 2013, Russ Cox ran an automated translation of the C compiler sources to Go, producing a Go-syntax compiler that was still structurally C. That translated compiler was refined and shipped as the default compiler in Go 1.5 (August 2015), removing the C toolchain requirement entirely. From Go 1.5 onward, the build tool only needs a previous Go binary as seed.
Other examples: Haskell's GHC is written in Haskell with a C runtime. GCC is bootstrapped from an earlier C/C++ compiler through exactly the stage 0/1/2 process. TypeScript's tsc is written in TypeScript and compiles itself.
See every bootstrap relationship in the dataset for the full list, each with a source and confidence score.
Glossary
- Bootstrapping
- The process of using a minimal working compiler to compile a more capable compiler, repeating until a language can compile its own full implementation.
- Self-hosting
- A compiler is self-hosting when the compiler's own source code can be compiled by that same compiler. Self-hosting is the end-state that bootstrapping achieves.
- Cross-compilation
- Compiling a program on one platform (the host) so that it runs on a different platform (the target). Cross-compilation is often used to bootstrap a compiler for a new CPU architecture from an existing one.
- Trusting Trust
- Ken Thompson's 1984 observation that a malicious compiler can be made to inject hidden code into programs it compiles, including into copies of itself, in a way that cannot be detected by reading source code. The attack propagates through any binary-distributed compiler chain.
Frequently asked questions
Is Rust's compiler written in Rust?
Yes. rustc, the official Rust compiler, is written in Rust and has been self-hosting since 2011. The first Rust compiler was written in OCaml.
Is Go's compiler written in Go?
Yes, since Go 1.5 (August 2015). The original Go compiler was written in C. A mechanical translation produced a Go-syntax version, which became the self-hosted gc compiler shipped in Go 1.5.
What language was the first Rust compiler written in?
OCaml. The initial rustboot compiler was written in OCaml because of its expressive type system. It was replaced by a self-hosted rustc by 2011.
What is the difference between self-hosting and bootstrapping?
Bootstrapping is the process; self-hosting is the result. You bootstrap a compiler by progressively compiling it with earlier versions until it can compile itself. A self-hosting compiler is one that has successfully reached that state.