Bootstrapping: how do you compile a compiler's own language?

The chicken-and-egg problem

Here's a genuinely strange fact: the GCC C++ compiler is itself written mostly in C++. So who compiled the first C++ compiler, if you needed a working C++ compiler to compile it in the first place?

This is the bootstrapping problem, and it's named after the physically impossible idea of "pulling yourself up by your own bootstraps." It sounds like a paradox, but it has a clean, practical solution that every real compiler toolchain actually uses. This lesson unpacks it with a simple diagram invented for exactly this purpose.

T-diagrams: drawing a translator as a puzzle piece

Before solving bootstrapping, we need a way to draw compilers, so we can reason about which pieces plug into which. A T-diagram (sometimes called a tombstone diagram, because of its shape) draws a compiler as a T-shaped puzzle piece:

        ┌─────────────┐
Source  │  Compiler   │  Target
Lang.   │             │  Lang.
────────┤             ├────────
   S    │             │    T
        └──────┬──────┘
               │ M
       Language it runs on

Read it as: "a compiler that translates source language S into target language T, and which itself is a program written to run on machine/language M." The three labels around the T fully describe one compiler.

For example, a normal C++ compiler that runs on and produces code for an x86 machine looks like:

        ┌─────────────┐
 C++    │             │  x86
────────┤   compiler  ├────────
        └──────┬──────┘
             x86

Plugging T-diagrams together

T-diagrams are useful because you can stack them, exactly like puzzle pieces, as long as the bottom label of one matches the language something above it needs to run on. If you have a C++-to-x86 compiler that itself needs to run on x86, and you have actual x86 hardware, you can literally just run it — the bottom of the T sits directly on the machine:

        ┌─────────────┐
 C++    │             │  x86
────────┤   compiler  ├────────
        └──────┬──────┘
       ┌────────────────┐
       │  x86 hardware   │
       └────────────────┘

This stacking picture is exactly how we'll solve bootstrapping: by chaining together several different compilers, each one covering a gap the previous one couldn't.

The three-step bootstrap

Say you've just designed a brand new language, "NewLang," and you've written a NewLang compiler — but you wrote that compiler's source code in NewLang itself, because you wanted to prove your language was good enough to write real software in (this is called self-hosting, and nearly every serious production language, including C++ itself, does this). The problem: you have no way to run NewLang source code yet, since the only NewLang compiler that exists is itself unrun NewLang source.

Step 1 — Write a quick, "throwaway" compiler in a language you can already run. Write a small, possibly slow or incomplete NewLang compiler using a language you already have working tools for — say, C++. This gives you a real, runnable program:

        ┌─────────────┐
NewLang │             │  x86
────────┤  compiler₀  ├────────
        └──────┬──────┘
             x86       (written in C++, already compiles to x86 with your existing C++ toolchain)

        ┌──────────────┐
NewLang │              │  NewLang
────────┤  compiler₀   ├─────────  (compiler₀ compiles NewLang source...)
        └──────┬───────┘
             x86

   feeding it this NewLang source file:  →   "real_compiler.newlang" (a NewLang-to-x86 compiler, written in NewLang)

   produces:
        ┌──────────────┐
NewLang │              │  x86
────────┤  compiler₁   ├────────
        └──────┬───────┘
             x86        (an x86 binary — this IS your real compiler, now runnable!)

Why bother self-hosting at all?

It might seem easier to just always compile NewLang using a permanent C++-based compiler. Self-hosting is preferred by real language designers for a few concrete reasons:

• It's the ultimate real-world test of the language. If your language can't comfortably express something as complex as a full compiler, that's a strong signal the language design has gaps.
• Improvements compound. Once self-hosted, a faster or smarter NewLang compiler feature immediately makes compiling itself faster too — a nice feedback loop.
• Independence. A self-hosted language no longer depends on any other language's toolchain existing or staying maintained.

A little math: bootstrapping is function composition, made concrete

Recall from the previous lesson that a compiler is a function from source text to target code. Bootstrapping is just composing three specific functions to eliminate a dependency:

Let $C_0$ be your throwaway compiler (written in C++, runs on x86, translates NewLang → x86). Let $R$ be your real compiler's source code, written in NewLang. Running $C_0$ on $R$ produces:

$C_1 = C_0(R)$

$C_1$ is now an x86 binary that itself performs the NewLang → x86 translation — but it was produced by $C_0$, not compiled by itself. To confirm correctness, we run $C_1$ on the same source $R$ again:

$C_2 = C_1(R)$

If $C_1$ and $C_2$ behave identically on any future input (a property called a fixed point), the bootstrap is verified: the language has successfully "taken over" compiling itself, and $C_0$ is no longer needed for anything.

Common mistakes

1. Thinking bootstrapping is only a historical curiosity. It's an active, ongoing practice — Rust's compiler is written in Rust, Go's compiler is written in Go, and both went through exactly this process.
2. Assuming self-hosted means "the language can never use other languages again." Self-hosted compilers often still call out to a C library or assembler under the hood for the lowest-level machine interaction; self-hosting is about the compiler's own logic, not total isolation.
3. Confusing bootstrapping with cross-compilation. Cross-compilation is producing code for a different machine than the one you're compiling on (both labeled clearly in a T-diagram's target vs. bottom label). Bootstrapping specifically concerns a compiler compiling a language it is itself written in.

Summary

Bootstrapping solves the apparent chicken-and-egg problem of self-hosted compilers by writing a quick throwaway compiler in an already-working language, using it to compile the real, self-hosted compiler's source exactly once, and then verifying the result by having the newly produced compiler compile itself again and checking the output matches. T-diagrams give a clean visual way to track exactly which language a given compiler is written in, what it translates, and what it needs to run on — a tool you'll find genuinely useful any time you reason about cross-compilers or toolchains later in your career.