🌐 한국어로 읽기

Background for chapter 07.

Bootstrapping a compiler

"Self-hosting" means a compiler that can compile its own source code. It sounds circular, and the first time through it is: before any version of uhs exists, nothing can compile uhs's own sources — they're just Haskell text sitting on disk. MicroHs breaks the circle the ordinary way every self-hosting compiler does: use a different, already-working implementation of (a large-enough subset of) the same language to build the first working copy, then let that first copy take over. In this project the "different implementation" is GHC, already sitting in the nix develop shell every chapter of this book builds from.

The ladder, as it stands after chapter 07

By the time chapter 08 wires up dedicated make targets for it, the bootstrap ladder has three rungs, and the Makefile names them directly (456ce17c:Makefile lines 66–69, quoted whole):

bootcombtest:	$(BIN)/uhs uhs.comb
	$(BIN)/uhs -ilib -isrc -omain-uhs.comb  MicroHs.Main
	$(BIN)/eval -H10000000 -K1000000 -ruhs.comb --  -ilib -isrc -omain-comb.comb MicroHs.Main
	cmp main-uhs.comb main-comb.comb

Read as a ladder:

1. GHC compiles the compiler. $(BIN)/uhs — an ordinary native binary — is built by GHC from src/MicroHs/Main.hs and everything it imports (456ce17c:Makefile line 23: $(GHCE) -package mtl -isrc -Wall -O src/MicroHs/Main.hs -main-is MicroHs.Main -o $(BIN)/uhs). Nothing self-referential here yet — it's the same "GHC builds a Haskell program" every earlier chapter's Try-it already does.
2. bin/uhs compiles the same source. The uhs.comb rule (456ce17c:Makefile lines 80–81) runs $(BIN)/uhs -ilib -isrc -ouhs.comb MicroHs.Main — the GHC-built compiler reads its own src/MicroHs/*.hs sources and emits uhs.comb, a combinator file in the same textual format every chapter's own .comb output has used since chapter 02. This is the first genuinely self-hosting step: the compiler is compiling itself, just not running as itself yet.
3. bin/eval runs uhs.comb, which compiles the source a second time. bootcombtest's middle line hands uhs.comb to the C runtime ($(BIN)/eval ... -ruhs.comb -- ... MicroHs.Main) — the runtime interprets the combinator file chapter 02 built the very first version of, and what it's interpreting is the compiler itself. That interpreted compiler then compiles MicroHs.Main from source again, writing main-comb.comb. Meanwhile the first line of the same target, $(BIN)/uhs -ilib -isrc -omain-uhs.comb MicroHs.Main, has the original GHC-built binary compile the identical source to main-uhs.comb, independently.
4. Compare. cmp main-uhs.comb main-comb.comb — plain byte equality, no special-casing.

A second, parallel check exists alongside this one, built from the "local lib" infrastructure this chapter's own July 1st commits add (see chapter 07's "What happened"): bootboottest (456ce17c:Makefile lines 61–64, quoted whole):

bootboottest:	$(BIN)/uhs $(BIN)/bootuhs
	$(BIN)/uhs     -ilib -isrc -omain-uhs.comb  MicroHs.Main
	$(BIN)/bootuhs -ilib -isrc -omain-boot.comb MicroHs.Main
	cmp main-uhs.comb main-boot.comb

$(BIN)/bootuhs is a second native binary — still built by GHC, but compiled module-by-module against MicroHs's own hand-rolled lib/ sources (through the ghc/ primitives shim, -XNoImplicitPrelude, and the convertY.sh preprocessor described below) instead of against GHC's own base package. bootboottest checks that this alternate, library-swapped GHC build agrees with the ordinary one — a different axis of "does this still mean the same thing," orthogonal to running the combinator file through the interpreter.

Why byte-identical output is the oracle

Neither test asks "does the output look right." Both just cmp two files. That's deliberate, and it's the only oracle that scales here: a compiler bug — say, a case arm handled in the wrong order, or an operator compiled with the wrong associativity — doesn't have to crash anything to be a bug. It can produce a .comb file that runs fine but computes a different value from what the other build of the same compiler, compiling the same source, produces. Left uncaught, that kind of bug would happily compile itself into every future build. Byte-for-byte comparison at each rung turns "the compiler is subtly wrong" into "these two files differ" — a diff cmp reports immediately, instead of a bug that only surfaces if someone happens to write a test that exercises the exact miscompiled path. Chapter 07's whole grind — everything short of actually running bootcombtest for real, which is chapter 08's story — is the work of getting the compiler's own source into a state where rung 2 above (bin/uhs compiling itself) even produces a uhs.comb that parses and runs at all.

The constraint: uhs may only use uhs

For the ladder above to prove anything, the compiler's own source has to be legal input to both GHC and, eventually, itself. That's a much narrower dialect than ordinary Haskell — no type classes (grep -rn "class \|instance " across src/MicroHs/ and src/Text/ParserComb.hs in this chapter's own Try-it turns up nothing live, and neither does the same search over lib/), no deriving, no fixity declarations. Chapter 07 is largely the diet this constraint forces, three examples of it made concrete:

• Int, not Integer. a721e046 ("Use Int instead of Integer") narrows EInt's payload from Integer to Int throughout src/MicroHs/Parse.hs/Desugar.hs — uhs's own Exp type had already committed to machine-width Int back in chapter 06's Translate.hs (its arithmetic table is typed Int -> Int -> Int), and the front end catches up to match.
• A hand-rolled Map, because Data.Map needs an Ord instance and uhs has no instances at all: f113210f adds src/MicroHs/Map.hs, 33 lines, admitting its own limits in a comment right next to the type (f113210f:src/MicroHs/Map.hs line 5): -- This is a pretty bad implementation. Every lookup and merge function takes its equality test as an explicit argument (lookup :: (k -> k -> Bool) -> k -> Map k v -> Maybe v) instead of reaching for (==) through a type-class constraint.
• No fixity mechanism, so uhs's own parser resolves every operator's precedence from one hand-written ladder of pLeftAssoc/ pRightAssoc/pNonAssoc calls in pExpr (f113210f:src/MicroHs/Parse.hs lines 450–462) rather than reading infixl/infixr declarations — there are none to read; a project-wide search for infix in src/MicroHs/Parse.hs across this chapter's whole commit range comes up empty. The --Yinfixr 2 ||-style comments that do show up in lib/*.hs in this range (chapter 07's "What happened" quotes one) are for GHC's benefit on the "local lib" build path below, not uhs's own parser.

The --X/--Y trick

The same source files have to satisfy two different compilers with two different needs — GHC wants real hiding clauses, real fixity declarations, real deriving; uhs doesn't understand any of them and would choke if it tried. The fix is textual: write the GHC-only syntax as an ordinary comment with a two-character marker prefix, and let a GHC preprocessor (-F -pgmF, a stage that rewrites source before compilation) strip the marker right before GHC parses the file. uhs itself never runs this preprocessor, so it just sees an ordinary comment and skips it. Both scripts are two lines (b71e0e90:convert.sh, split into 67715b16:convertX.sh and bea8283d:convertY.sh; quoted here as they read once both exist, f113210f:convertX.sh and f113210f:convertY.sh, each whole):

#!/bin/sh
( echo "{-# LINE 1 \"$1\" #-}" ; sed -e 's/--X//' $2 ) > $3

#!/bin/sh
( echo "{-# LINE 1 \"$1\" #-}" ; sed -e 's/--Y//' $2 ) > $3

convertX.sh feeds the $(BIN)/uhs build itself (GHCE, rung 1 above): a line like import Prelude --Xhiding (Monad(..), ...) becomes, once GHC sees it, import Prelude hiding (Monad(..), ...) — needed because uhs's source hand-rolls its own >>=/pure/<*> as plain top-level functions (see chapter 07) and GHC's real Prelude would otherwise fight it for those names. convertY.sh feeds the "local lib" build (GHCC, the machinery bootboottest's $(BIN)/bootuhs depends on): a line like --Yinfixr 2 || in lib/Data/Bool.hs becomes a real infixr 2 || declaration, needed because that build compiles lib/'s hand-rolled (||) under GHC's own expression grammar, which does care about declared fixity even though uhs's own parser doesn't. Same source, two markers, two audiences.

One more name for this

This two-rung self-check — compiler output matching compiler output, one level removed — is the same shape of trust question Ken Thompson's 1983 Turing-award lecture "Reflections on Trusting Trust" (published in CACM in 1984) raises: a cmp that passes proves the two builds agree with each other, not that either one is correct, so a bug (or something worse) baked into the very first GHC-built bin/uhs could in principle survive every later bootstrap unnoticed.