Bootstrapping compiler

Programs are written by humans in a well-readable programming language. A processor understands none of this; it only knows machine instructions made of zeros and ones. A compiler is a program that carries out this translation. But it is itself also just a program and must therefore likewise be written in some language. One speaks of bootstrapping when the compiler for a language is written in that very same language. The compiler thus translates itself — which at first sounds like an impossible circle.

Why languages want to translate themselves

The most important reason is a practical test. Anyone designing a new programming language wants to know whether it is suitable for large, serious software. A compiler is exactly such a program: extensive, complex, and unforgiving of poor designs. If a language is not even good enough to write its own compiler, that is a bad sign.

There is also a very practical point. The developers of a compiler are at the same time its most intensive users. They feel every weakness of the language daily in their own project. Errors and cumbersome constructs thus stand out quickly and are quickly fixed. This principle is also known as eating your own dog food.

Finally, bootstrapping makes the project independent. A compiler that permanently needs a foreign language depends on that language’s tools and its continued existence. One that translates itself ultimately only needs itself. Languages such as Go, Rust, and C have taken exactly this path.

The way out of the chicken-and-egg problem

The apparent circle can be broken with a trick. First, one writes a small, simple compiler in an already existing language, often in C. This first compiler is unrefined and can only handle part of the new language. But it is sufficient to translate an initial version of the actual compiler. This starting aid is called stage 0 or the bootstrap compiler.

Then comes the actual step. The full compiler is written in the new language itself. The bootstrap compiler translates this source code into a runnable program. Now, for the first time, a compiler for the new language exists that is written in the new language. From this point on, the bootstrap compiler is no longer needed and can be discarded.

A comparison helps: to set up a workshop, one needs tools. So one first borrows someone else’s tools. With these, one manufactures one’s own, better tools. Afterward, the borrowed ones are returned and only the own tools are used from then on. This is exactly how it works with bootstrapping. From then on, further development proceeds in stages: version 5 of the compiler is translated with version 4, version 6 with version 5, and so on.

From the Linux kernel to the trust problem

The topic becomes especially visible when installing software from source code. Anyone who builds a Linux distribution from scratch almost immediately encounters the bootstrap chain of the C compiler GCC. The Rust compiler, too, first downloads an older, finished version of itself when building. Major languages bring their own origin story with them.

In security discussions, bootstrapping regularly appears as a risk. The computer scientist Ken Thompson described a famous attack in 1984. A manipulated compiler can insert malicious code into programs without anything of it appearing in the source code. Because it translates itself, it passes the manipulation on to all subsequent versions. The source code looks completely clean in the process.

That is why there are now projects aiming to make the entire chain traceable. They start with a tiny, manually verifiable program and build modern compilers from it step by step. Reproducible builds is the term that comes up in this context in trade news. A related but distinct concept is the interpreter: it executes programs directly instead of translating them completely beforehand.