Nothing. This is commit ccb31388, "First version," 2023-05-25 19:33:17 +0200 — the first commit in the repository. There is no prior state to assume; everything in this chapter is read straight out of one commit.

Four files land together: .gitignore, Lam.hs (227 lines of Haskell), Makefile (14 lines), and eval.c (539 lines of C) — 786 lines total (see 00-overview.md for the commit stat). What the code shows, without reading further intent into it than the code justifies: the author wants a compiler from a small Haskell-like language down to combinators, plus a runtime tiny enough to fit in one C file, and he wants the two halves working together by the end of the sitting. There is no parser, no type checker, no module system, no error handling worth the name — just enough machinery to compile one hardcoded lambda term and run it.

What happened

The commit is a two-file architecture, plus a third artifact — a text file — that sits between them.

`Lam.hs`: compiler, no parser

Lam.hs defines the Exp AST (Var, App, Lam, Int, Comb, Prim — see aux/lambda-calculus-and-ski.md for what each constructor is for), a bracket-abstraction compiler that turns Exp terms with Var/Lam into pure combinator terms (see aux/bracket-abstraction.md for the derivation), a Kiselyov-style improve pass that shrinks the combinator output, a pretty-printer, and — at the very bottom of the file — one hardcoded program, eNfib, computing nfib 35. There is no readFile, no getArgs parsing beyond what the Makefile supplies, no lexer or parser for the source language at all. Every example in this commit is Haskell source built directly as an Exp value, by hand, inside Lam.hs itself.

The whole pipeline is small enough to fit in the Makefile, quoted here in full (ccb31388:Makefile):

test:	eval nfib.comb
	./eval nfib.comb

eval:	eval.c
	gcc -O3 eval.c -o eval

nfib.comb:	Lam
	./Lam > nfib.comb

Lam:	Lam.hs
	ghc Lam.hs -o Lam

clean:
	rm -f *.hi *.o eval Lam

Read bottom to top and it's the whole story: ghc compiles Lam.hs into a Lam binary; running Lam and redirecting its stdout produces nfib.comb, a text file; gcc compiles eval.c into an eval binary; running eval on nfib.comb is the actual program. Two independent toolchains (GHC and a C compiler) meet at one text file.

The compiler itself is compile, dispatching to abstract on every Lam. Quoted whole (ccb31388:Lam.hs, lines 97–101 — compile above it is one line per constructor and is covered by aux/bracket-abstraction.md section 1):

abstract :: Ident -> Exp -> Exp
abstract x e@(Var y) | x == y = CI
abstract x (App f a) = App2 CS (abstract x f) (abstract x a)
abstract x (Lam y e) = abstract x $ improveC $ abstract y e
abstract x e = App CK e

Four equations, no recursion into a name table, no environment — by design; the aux doc walks through why. Lam.hs never grows past 227 lines in this commit, and most of that length is the pretty-printer, the improve/improveC/improveT rewrite rules (aux/bracket-abstraction.md section 3), the reference reducer reduce/redOne, and a small combinator-building DSL (ToLam, $$, comp) used to write eNfib in a readable style.

`eval.c`: the runtime

eval.c is a self-contained C program: a fixed-size cell heap, a switch on node tags implementing every combinator reduction rule, an explicit spine stack, and a real mark-and-scan garbage collector, with indirection nodes used for in-place update. None of that is summarized further here — aux/graph-reduction-and-laziness.md covers the cell representation, the spine walk, sharing, and the GC in detail with line citations, and aux/y-combinator-and-recursion.md covers how Y builds a genuinely cyclic graph for recursion. Both are verified against this exact commit; there's no reason to duplicate them here.

The `.comb` file: a text interface you can read

nfib.comb — the file Lam writes and eval reads — is plain text, one line, human-legible combinator syntax. Generated fresh in a worktree at this commit, it reads (whole file; it genuinely is one line):

((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 35)

That is not a compact binary blob — it's S/K/I/B/C/S'/C' and friends, parenthesized left-to-right, printed by pretty() in eval.c and parsed back by parse() in the same file (both discussed in the aux doc). Choosing a plain-text interchange format between two otherwise-unrelated programs is itself a decision worth noticing: it means you can cat the intermediate representation, diff two versions of it, or hand-write a test case, all without either compiler.

The commented-out block in `main`

main is not just the eNfib-and-print line that ships. ccb31388:Lam.hs, lines 8–30, is a {- ... -}-commented block sitting directly above the line that runs:

main :: IO ()
main = do
{-
  let c1 = compile e1
      c1' = improve c1
      r1' = reduce (App c1 (Var "k"))
      r1'' = reduce (App c1 (Int 5))
  pp e1
  pp c1
  ...
  pp $ improve $ compile $ App (Lam "x" (App2 (Var "x") (Int 10) (Int 2))) (Prim "-")
-}
  putStrLn $ toStringP $ eNfib `App` 35

That block is 21 lines of pp/let calls exercising e1, e2, e3 (three small hand-written test terms defined a few lines below main) — compile them, improve them, reduce them, print every intermediate result. It's not dead code in the sense of being obsolete; it's a REPL session that got pasted into main and then commented out rather than deleted, so it's still there, still correct, and still runnable — see the "Try it" section.

Commit 2: "Clean more"

21168890, authored (and committed) 30 seconds after ccb31388 — same day, same two timestamps a half-minute apart — changes exactly one line of the Makefile:

 clean:
-	rm -f *.hi *.o eval Lam
+	rm -f *.hi *.o eval Lam *.comb

That's the entire diff. make clean didn't remove the generated nfib.comb; thirty seconds after committing the first version, that got noticed and fixed. Nothing else in the commit changes.

The B' gap

One loose end ships in this commit and stays: eval.c declares a BB tag (printed as B'), the parser accepts B' syntax, and pretty() knows how to print it — but the eval switch has no case BB:, so a B' node reaching the runtime crashes with bad tag 12. It happens not to matter, because improveC never emits B' in this commit, even though Lam.hs's own redOne implements the rule correctly. See aux/lambda-calculus-and-ski.md section 5 for the verified crash and aux/bracket-abstraction.md section 4 for why compile/improve never trigger it.

Why it matters

Everything the rest of this book covers is one of these two files, or the format between them, growing up. The parser that arrives four days later (chapter 02) replaces the hand-built Exp values in main; the improved node representation and optimiser extend eval.c's tag switch and improve's rewrite rules; the later self-hosting push replaces Lam.hs itself, module by module, without ever changing the shape of the pipeline it's part of. The .comb-file handoff — compile to a text format, then run the text format with a separate program — is the same shape the bootstrap uses two months later, just with a much bigger compiler on one side. Starting with a hardcoded program instead of a parser is exactly what makes day one end with something that runs end-to-end: nfib 35, for real, computed by a graph-reduction machine that didn't exist that morning.

Notebook margin

Habits visible already, at commit 1 and 2:

Exploratory code is commented out, not deleted. The e1/e2/e3 scratch block in main stays in the file, fully functional, just not running by default.
"Clean more" lands 30 seconds after "First version" — the same session, immediately fixing a make clean oversight rather than batching cleanup for later.
The interface between the Haskell half and the C half is a text file you can read with your eyes, not a serialized binary format.
The commit ships with a known-crashing case (B') rather than waiting until every combinator is wired up end-to-end. It doesn't block shipping because it isn't reachable yet.

Try it

Convention used throughout this book: check out the commit into its own worktree.

git worktree add /tmp/mhs-ccb31388 ccb31388
cd /tmp/mhs-ccb31388
nix develop $MICROHS -c make test

($MICROHS is the absolute path to your clone, set once per the top-level README.md.) Expect a GHC compile with one benign warning, then the program output:

Lam.hs:211:13: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘head’
    ...
./eval nfib.comb
((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 35)
29860703
node size=24, heap size=100000
1045124618 reductions, 1944 GCs

29860703 is nfib 35. The warning is about Data.List.\\'s use of partial head at line 211 (a version of \\ used to pick a fresh variable name) — harmless here since the input lists it's subtracting from are always non-empty in this commit's usage, but a real partiality GHC is right to flag.

Exercise 1: run the commented-out experiment

Open Lam.hs and delete just the two comment markers: the {- on line 8 and the -} on line 30. Leave everything between them untouched. Then:

nix develop $MICROHS -c make Lam
nix develop $MICROHS -c ./Lam

This prints 16 lines — the block's own pp/putStrLn calls followed by the usual nfib term. The first three lines are compile/improve applied to e1 = \x. + x x:

(\x. + x x)
S (S (K +) I) I
S + I

— matching aux/bracket-abstraction.md section 2's hand-traced derivation of compile e1 and section 3's improve (compile e1) exactly, but now confirmed a second, independent way (the block computes them directly in main, not via ghci). Further down (line 14 of the run), pp $ improve $ compile e3 prints:

— the same answer aux/bracket-abstraction.md section 5 asks you to predict by hand before checking in ghci; here it's the same computation, done inline in the compiled Lam binary instead. (Put the {-/-} back before moving on — the next two exercises regenerate nfib.comb, and this block's extra output would land in that file too if left uncommented, since nfib.comb is just Lam's redirected stdout.)

Exercise 2: run a smaller `nfib`

Change line 31 from eNfib \App` 35toeNfib `App` 25. Before rebuilding, predict the answer from eNfib's own recurrence (quoted in [aux/y-combinator-and-recursion.md](aux/y-combinator-and-recursion.md) section 3): nfib n = 1ifn < 2, else nfib(n-1) + nfib(n-2) + 1`. Expanding it from the base case:

nfib: 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219,
      1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735,
      150049, 242785
       (n= 0  1  2  3  4   5   6   7   8    9   10   11   12   13   14
            15    16    17    18     19     20     21     22     23
              24      25)

So nfib 25 should be 242785. Rebuild and check:

nix develop $MICROHS -c make test

./eval nfib.comb
((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 25)
242785
node size=24, heap size=100000
8497488 reductions, 15 GCs

242785, as predicted — and, worth noting in passing, over two orders of magnitude fewer reductions than nfib 35 (8,497,488 vs. 1,045,124,618) for a function whose call count roughly follows the Fibonacci growth rate. Before the next exercise, change line 31 back to 35 and rebuild — editing Lam.hs alone does not regenerate the nfib.comb sitting on disk, which is still the 25 version:

nix develop $MICROHS -c make test

This should print the original ... 35) term and 29860703 again; nfib.comb is now back to its baseline content.

Exercise 3: break `improveC` and watch the term grow

improveC (ccb31388:Lam.hs, lines 106–117) has this case, one of six special-cased patterns before the catch-all:

    (App CS (App CK e1),     e2)        -> improve (App2 CB e1 e2)

This is the rule that introduces B — see aux/bracket-abstraction.md section 4 for why it exists. First, save the current (unbroken) nfib.comb so there's something to diff against later:

cp nfib.comb nfib.comb.orig

Then delete that one improveC line and rebuild:

nix develop $MICROHS -c make test

./eval nfib.comb
((Y ((C ((S (K C)) ((S (K (S (> 2)))) ((C ((S (K C)) ((S (K (S (K +)))) ((S ((S (K S)) ((S (K (S (K +)))) ((C ((S (K S)) K)) (-' 1))))) ((C ((S (K S)) K)) (-' 2)))))) 1)))) 1)) 35)
29860703
node size=24, heap size=100000
1373651156 reductions, 2542 GCs

Still 29860703 — removing one improve rule doesn't change what the program computes, only how big the compiled term is and how much work eval does to reduce it. Measured against the nfib.comb.orig saved just before the edit:

$ nix develop $MICROHS -c diff nfib.comb.orig nfib.comb
1c1
< ((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 35)
---
> ((Y ((C ((S (K C)) ((S (K (S (> 2)))) ((C ((S (K C)) ((S (K (S (K +)))) ((S ((S (K S)) ((S (K (S (K +)))) ((C ((S (K S)) K)) (-' 1))))) ((C ((S (K S)) K)) (-' 2)))))) 1)))) 1)) 35)

(diff isn't in this project's own Makefile, but it's on the PATH nix develop hands you, since the devShell isn't built in isolation from the host.) The one-line term grows from 102 bytes to 181 — every B the missing rule would have produced instead shows up as S (K _) _, spelled out. eval pays for that: 1,373,651,156 reductions against the original 1,045,124,618 (31% more), and 2,542 GCs against 1,944 (31% more) — one missing rewrite rule, and both the program text and the runtime cost grow by roughly a third, for a function whose observable behavior is unchanged.

Clean up when done:

git worktree remove --force /tmp/mhs-ccb31388

Learning from MicroHs

01 — The seed

Where we are