y-compiler

A minimal PoC in Go exploring how a compiler binary can reproduce its own source, without hardcoded string blueprints or quine-style escape methods.

How does self-hosting work?

Production compilers (rustc, go, clang) are self-hosted: the compiler is written in the language it compiles.
But how?
— Well, you can't compile the first binary without a binary that already exists. That's the bootstrapping paradox.

The standard resolution is a staged chain. Take Rust as an example:

• [0] The seed. The first rustc prototype was written in OCaml, not Rust.
• [2] The transition. The compiler source is rewritten in Rust. The OCaml binary compiles it, producing the first native rustc executable.
• [3] The loop closes. The native binary compiles itself. OCaml is no longer used.

From second stage onward, the invariant holds permanently:

compiler_binary + compiler_source => identical compiler_binary

What is this PoC about?

The classic way to demonstrate this concept is a quine, which is a program that prints its own source code. But quines rely on embedding a static string template internally and carefully escaping it through the parser, which is quite brittle. Change anything about the source structure and the embedded template breaks.

Hence, instead of storing the source inside itself in my PoC, the binary uses resolves its own location on disk at runtime, then streams that file directly to stdout. The filesystem is the blueprint.

The language spec is intentionally trivial. There is only one valid instruction: y. The compiler reads a .y source file, validates the instruction, and emits its own source to stdout.

Trusting Trust

Because a self-hosting compiler reproduces its own lineage, it introduces a profound security quirk known as the Thompson Hack, which is popularized by Ken Thompson's 1984 Turing Award lecture Reflections on Trusting Trust.

TL;DR

If a compiler binary is modified to inject a backdoor whenever it compiles itself, that backdoor propagates into every subsequent generation of the binary — even if the source code looks completely clean. You'd never find it by reading the source. The attack lives in the compiled artifact, not the text.

It means that for any self-hosting toolchain, the trust chain extends all the way back to whatever binary produced the first native executable.

Usage

go build -o y-compiler main.go
./y-compiler program.y > compiled_compiler.go

Verify the equivalence of both:

# unix
diff main.go compiled_compiler.go

# windows (pwsh)
fc.exe main.go compiled_compiler.go