The Bootstrapping Process in Detail

The Seed Compiler (Stage 0)

• Purpose: Create a minimal, working compiler for the new language (Language X) using an existing language (Language Y).
• Constraints:
  • The seed compiler only needs to support a subset of Language X (enough to compile the full compiler later).
  • It may generate inefficient code or lack optimisations - its primary goal is correctness.
• Example:
  • The first C compiler (circa 1970) was written in assembly.
  • The first Go compiler (2009) was written in C.

Rewriting the Compiler in Language X (Stage 1)

• Developers write a new, improved compiler entirely in Language X.
• This compiler must handle the full feature set of Language X, including optimisations.
• Key Challenge:
  • The seed compiler (written in Language Y) must be capable of compiling this new compiler.

Bootstrap Compilation (Stage 2)

• Use the seed compiler (Language Y) to compile the new compiler (Language X).
• The result is a self-hosted compiler (written in Language X) that can compile its own source code.

Self-Hosting and Iteration

• Future updates to the compiler are written in Language X and compiled using the bootstrapped compiler.
• This creates a feedback loop where the language evolves using its own tools.

Real-World Examples

C Language

• Seed: The original Unix C compiler (1970s) was written in PDP-11 assembly.
• Bootstrap: Once the C compiler could compile C code, later versions were written in C itself.

Rust

• Seed: The first Rust compiler (rustc) was written in OCaml (2010).
• Bootstrap: Once Rust was mature enough, rustc was rewritten in Rust. Today, the Rust compiler compiles itself.

Go

• Seed: The Go compiler (gc) was initially written in C (2009).
• Bootstrap: Go 1.5 (2015) introduced a compiler written in Go, compiled using the existing C-based compiler.

Java

• Seed: The first Java compiler (1995) was written in C.
• Bootstrap: Modern Java compilers (like javac) are written in Java.

Key Challenges in Bootstrapping

The Chicken-and-Egg Problem

• How do you compile the first version of the compiler written in Language X if no compiler exists for it?
• Solution: The seed compiler (written in Language Y) bridges this gap.

Trusting Trust Attack

• A security concept raised by Ken Thompson's 1984 lecture Reflections on Trusting Trust.
• A compromised seed compiler could inject malicious code during bootstrapping, perpetuating vulnerabilities in all future compilers.

Cross-Platform Bootstrapping

• Compiling a compiler for a different architecture (e.g., compiling an ARM compiler on x86).
• Solution: Use a cross-compiler in the seed stage to generate code for the target platform.

Evolving Language Features

• Adding new syntax or optimisations to Language X requires the bootstrapped compiler to understand those features.
• Developers often use phased updates to avoid breaking the compiler.

Advantages of Bootstrapping

1. Self-Sufficiency: No dependency on external tools for future development.
2. Dogfooding: Using the language to build its own tools reveals flaws and drives improvements.
3. Performance: Optimizations in the language can directly benefit the compiler itself.
4. Credibility: Demonstrates the language is mature enough to handle complex tasks.

Modern Bootstrapping Techniques

• Incremental Bootstrapping:
  • Compilers like TypeScript or Kotlin are written in their own language but rely on existing ecosystems (e.g., TypeScript compiles to JavaScript first).
• Multiple Backends:
  • Compilers like GCC or LLVM support multiple architectures, requiring careful bootstrapping for each target.
• Bootstrap-Specific Tools:
  • Tools like re2c (lexer generator) or yacc (parser generator) help automate parts of compiler development.

The Bootstrap Process Visualized

1. Stage 0 (Seed):
   Language X Compiler (written in C) → compiles → Basic Language X Program
2. Stage 1 (Self-Hosting):
   Language X Compiler (written in X) → compiled by Stage 0 → New Compiler Binary
3. Stage 2 (Self-Compilation):
   Language X Compiler (written in X) → compiles itself → Improved Compiler Binary