chapter 01 left two files and a text format between them: Lam.hs compiles one hand-built Exp value — eNfib, computing nfib 35 — down to combinators, and eval.c runs the result. There is still no parser. Every example the system can run is Haskell source, but it's Haskell source written as a literal Exp value inside Lam.hs itself, not text the compiler reads. Commit 21168890 ("Clean more") is the last commit before this chapter's range, and it changes one line of the Makefile. Nothing about the hardcoded-program shape has moved yet.

What happened

Warm-up: 2023-05-26

Three commits land the Friday after the seed, all still inside the old two-file world (Lam.hs/eval.c), none of them touching the parser that hasn't been written yet:

54806439 ("Use file handle for printing.") turns eval.c's pretty/ pp functions from hardcoded printf/putchar calls into print(FILE *f, ...)/pp(FILE *f, ...) that take an explicit stream. main still calls pp(stdout, n) both times, so nothing about the program's visible output changes — but the function can now be pointed at any file handle, which is what makes b0c33a8f, 34 minutes later, able to add a label-parsing path that reads from the same kind of handle it prints to.

6485a341 ("Move some improvements earlier.") reorders Lam.hs's optimizer without changing its rule set: the "flip arguments to commutative ops" rewrites ((CC, Prim "+") -> Prim "+" and friends) move out of improveT's case list and into improveC's, ahead of improveC's own catch-all. Both passes still exist (improve = improveT . improveC), but a term now gets flip-normalized during the first traversal instead of having to wait for the second — more opportunities for the S'/C' rules just above them in improveC to fire on an already-flipped operand in one pass instead of two. The commit message names the intent ("move ... earlier"), not this mechanism; that's a pattern this chapter keeps running into (see "Notebook margin").

b0c33a8f ("Print and parse sharing/cycles.") is the one warm-up commit worth quoting, because the format it introduces is what chapter 02's own compiler output uses from a9178695 onward: a way to print a DAG or a cycle — not just a tree — as flat text. The parser side (b0c33a8f:eval.c, lines 295–306):

  case '_' :
    l = (int)parse_int(f);  /* The label */
    if (shared[l] == NIL) ERR("shared == NIL");
    return shared[l];
  case ':' :
    l = (int)parse_int(f);  /* The label */
    if (!gobble(f, ' ')) ERR("parse ' '");
    if (shared[l] != NIL) ERR("shared != NIL");
    shared[l] = alloc_node(IND); /* Must have a placeholder for cycles */
    r = parse(f);
    INDIR(shared[l]) = r;
    return r;

:N <expr> defines shared node N (an indirection placeholder is allocated before <expr> is parsed, specifically so a cyclic reference inside <expr> back to N has something to point at); _N refers back to it. The print side marks any node visited twice during a pre-pass (find_sharing) as SHARED, then on the real print pass emits :N the first time a SHARED node is reached and just _N every time after (b0c33a8f:eval.c, lines 327–333):

  if (MARK(n) == PRINTED) {
    fprintf(f, "_%d", LABEL(n));
    return;
  } else if (MARK(n) == SHARED) {
    fprintf(f, ":%d ", LABEL(n));
    MARK(n) = PRINTED;
  }

Nothing in this commit's own test data actually shares a node yet — it's groundwork. Four days later, 17587b2d's "hack" is the first thing that puts this label format to real use.

`a9178695`: "Make a real compiler." (2023-05-29, 16:14)

The pivot. Six new files, 561 lines, git show a9178695 --stat:

 Desugar.hs    |  31 +++++++++
 Exp.hs        | 141 ++++++++++++++++++++++++++++++++++++++++
 Lam.hs        |   6 ++
 Main.hs       |  14 ++++
 Parse.hs      | 204 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ParserComb.hs | 165 +++++++++++++++++++++++++++++++++++++++++++++++

ParserComb.hs and Parse.hs are a parser-combinator library and the grammar built on it — aux/parser-combinators.md covers both in detail. What matters here is what they accept and what changes downstream. The surface language at this commit is small: a module (module Name where plus a block of definitions), function definitions (f x y = expr), data declarations (data T = C1 t1 t2 | C2), and expressions built from variable/constructor names, integer literals, application, \x. expr lambdas, case expr of with constructor-pattern arms, and parenthesized subexpressions — one representative production (a9178695:Parse.hs, lines 147–150):

pDef :: P Def
pDef =
      Data <$> (pKeyword "data" *> pLHS pUIdent <* pSymbol "=") <*> esepBy1 ((,) <$> pUIdent <*> many pAType) (pSymbol "|")
  <|> Fcn <$> (pLHS pLIdent <* pSymbol "=") <*> pExpr

Exp.hs is, almost line for line, Lam.hs's own Exp type and compile/abstract/improve/reduce pipeline (aux/bracket-abstraction.md covers the original) copied into its own module — Lam.hs keeps its copy unmodified and stays the engine behind make test; Exp.hs becomes the engine behind the new parser-driven path. The two diverge from this commit on. Desugar.hs bridges Parse.hs's Expr/Def/Module AST to Exp.hs's Exp: a plain case-to-application rewrite for expressions (a9178695:Desugar.hs, lines 25–31, quoted whole)—

dsExpr :: Expr -> Exp
dsExpr (EVar i) = Var i
dsExpr (EApp f a) = App (dsExpr f) (dsExpr a)
dsExpr (ELam x e) = Lam x (dsExpr e)
dsExpr (EInt i) = Int i
dsExpr (ECase e as) = apps (dsExpr e) (map dsArm as)
  where dsArm ((_, xs), r) = lams xs $ dsExpr r

— and, more interestingly, a data-declaration desugaring that turns each constructor into a plain function taking its own fields followed by one continuation argument per constructor and picking its own (a9178695:Desugar.hs, lines 16–22): dsDef (Data _ cs) = zipWith dsConstr [0..] cs builds, for constructor i out of n, a function of shape \x1 x2 ... $f0 $f1 ... $f(n-1) -> $fi x1 x2 ... — a Scott encoding, case analysis compiled straight to application with no separate pattern-match machinery in the runtime at all. main changes from printing one hardcoded term to this (a9178695:Main.hs, quoted whole):

import System.Environment(getArgs)
import Parse
import Desugar
import Exp

main :: IO ()
main = do
  [fn] <- getArgs
  mdl <- parseDie pTop fn <$> readFile fn
  let ds = desugar mdl
      ds' = [ (i, improve $ compile e) | (i, e) <- ds ]
  mapM_ (\ (i, e) -> putStrLn $  i ++ " = " ++ toString e) ds
  mapM_ (\ (i, e) -> putStrLn $  i ++ " = " ++ toString e) ds'

One command-line argument, a file name, no more; the program is read (readFile fn), parsed (parseDie pTop fn), desugared, and each top-level definition is compiled and improved independently — this version doesn't yet try to link the definitions into one runnable program; it just prints, per name, the naive and the optimized combinator form. There's no writeFile yet, and no notion of which definition is the entry point. That gap is exactly what 17587b2d addresses five commits later.

648aeef0 ("Add another node representation.", 13 minutes after a9178695) and 71729105 ("Add pair and cons.", 19 seconds after that) follow the same afternoon; both are described below with the commits they belong with thematically.

`648aeef0`: a third node layout for `eval.c`

Chapter 01's eval.c ran one node representation, NODE_NAIVE — a C struct with real pointers, selected by #define NODE_NAIVE at the top of the file — but the file already carried a second, uncompiled-into option in the same #if/#elif chain, NODE_SPLIT (ccb31388:eval.c, lines 5–8: the same comment block quoted below, minus its NODE_INDEX line, which doesn't exist yet). This commit adds a third live option, NODE_INDEX, and flips the active #define to it (648aeef0:eval.c, lines 5–10):

/* Node representation:
 * NODE_NAIVE   all fields in a struct, regular pointers
 * NODE_INDEX   use 32 bit indices instead of pointers
 * NODE_SPLIT   split flags, funs, and args
 */
#define NODE_INDEX

NODE_INDEX replaces the two 8-byte pointers inside each cell (FUN/ ARG) with 32-bit array indices into one cells array (648aeef0:eval.c, lines 51–67, the union body elided — same shape as NODE_NAIVE's):

#elif defined(NODE_INDEX)
/* Naive node representation with minimal unions */
typedef u_int32_t NODEPTR;
typedef struct node {
  enum node_mark mark;
  enum node_tag tag;
  union {
    ...
  } u;
} node;
#define NIL (-1)
#define HEAPREF(i) (i)
#define MARK(p) cells[p].mark

This is a real, measured effect, not a hypothetical one: chapter 01's ccb31388 build reports node size=24, heap size=100000 for NODE_NAIVE; building this chapter's b56ba28b (which keeps NODE_INDEX active) and running the exact same nfib 35 program through the unmodified Lam.hs pipeline reports node size=16 — a third smaller, with the reduction count and GC count both unchanged (1045124618 reductions, 1944 GCs, identical in both — see "Try it" below for the transcript). Three representation choices now live side by side in the same #if chain, NODE_NAIVE and NODE_SPLIT both still compiling, just not selected — representation experiments happen as edits to one #define, on the mainline, not as a branch that gets merged later.

`9cf1e937` + `b4e44ded`: "New optimiser." (2023-05-30, 12:46–12:47)

The next session, the day after, starts with the same commit message twice, forty seconds apart. Read literally, the first one doesn't build: 9cf1e937's entire diff is one line added to Exp.hs, toStringP (Lbl i e) = ":" ++ show i ++ " " ++ toStringP e — a pretty-printer case for a constructor, Lbl, that this commit's Exp type doesn't declare yet (Lbl isn't added to data Exp until b4e44ded). Building Exp.hs at exactly 9cf1e937 and nowhere else in the range confirms it:

Exp.hs:129:37: error: [GHC-58481] parse error on input ‘=’
    |
129 | redOne (App4 (Comb "O") x1 x2 f1 f2 = Just $ App2 f2 x1 x2

— not even the error you'd expect from the missing Lbl constructor; a plain unbalanced-parenthesis typo, inherited unfixed from 71729105 ("Add pair and cons.", the previous afternoon), is enough on its own to stop the file from compiling at all. b4e44ded, the second "New optimiser." commit, both fixes that syntax error and does the real rewrite: the old two-pass compile (naive bracket abstraction) then improve = improveT . improveC (a separate cleanup pass) is replaced by one pass whose abstraction step calls smart constructors — cS/cC/cB/cS'/cC' — that apply the same rewrite rules inline, while building the term, instead of afterward (b4e44ded:Exp.hs, lines 73–100):

abstract :: Ident -> Exp -> Exp
abstract x e@(Var y) | x == y = CI
abstract x (App f a) = cS (abstract x f) (abstract x a)
abstract x (Lam y e) = abstract x $ abstract y e
abstract x e = cK e

cK :: Exp -> Exp
--cK CI = CT
cK e  = App CK e

cS :: Exp -> Exp -> Exp
cS (App CK e1)     (App CK e2) = cK (App e1 e2)    -- S (K e1) (K e2) = K (e1 e2)
cS (App CK e1)     CI          = e1                -- S (K e1) I      = e1
cS (App CK e1)     e2          = cB e1 e2          -- S (K e1) e2     = B e1 e2
cS e1              (App CK e2) = cC e1 e2          -- S e1     (K e2) = C e1 e2
cS (App2 CB e1 e2) e3          = cS' e1 e2 e3      -- S (B e1 e2) e3  = S' e1 e2 e3
cS e1 e2                       = App2 CS e1 e2

cC :: Exp -> Exp -> Exp
cC (App2 CB e1 e2) e3          = cC' e1 e2 e3      -- C (B e1 e2) e3  = C' e1 e2 e3
--cC (Prim op)       e2 | Just op' <- lookup op flipOps = App (Prim op') e2 -- C op e = flip-op e
cC (Var op)        e2 | Just op' <- lookup op flipOps = App (Var op') e2 -- C op e = flip-op e
cC e1              e2          = App2 CC e1 e2

cB :: Exp -> Exp -> Exp
cB CC          (App CC CI) = CP -- Pair
cB (App CB CK) CP          = CO -- Cons
cB e1          e2          = App2 CB e1 e2

The old improveC/improve block is left in the file, commented out ({- ... -}) rather than deleted, in the same "keep exploratory code, just stop running it" habit chapter 01 noted at commit 1. Machine-verified, not just read: with compileOpt = improveT . compile, compiling \x. \y. \f. f x y (the pairing function) at a9178695 needs the separate improve pass to collapse to the P combinator —

compile epair            = S (K C) (S (S (K C) (K I)) I)
improve (compile epair)  = P

— while at b4e44ded, compile alone already produces P, no second pass required:

compile epair    = P
compileOpt epair = P

Same input, same final answer, one fewer traversal to get there — the "New optimiser." title describes the intent; reading the diff is the only way to see that it means fusing the cleanup pass into abstraction, not adding new rules (the rule set — Pair/Cons included — is close to a straight port of what improveC already had; cB's Pair/Cons cases are literally the two rules 71729105 had commented out the day before, now live again).

`17587b2d`: "Hack around a problem." (2023-05-30, 12:47:15, 13 seconds later)

a9178695's main compiled each top-level definition independently and printed each one on its own — it never combined them into a single runnable term, and had no idea which one was the entry point. That's the problem. The fix (17587b2d:Main.hs, quoted whole):

import Data.Maybe
import System.Environment(getArgs)
import Parse
import Desugar
import Exp

primOps :: [(Ident, Exp)]
primOps =
  [ ("error", Prim "?")
  , ("+",     Prim "+")
  , ("-",     Prim "-")
  , ("-'",    Prim "-'")
  , ("*",     Prim "*")
  , ("quot",  Prim "/")
  , ("rem",   Prim "%")
  , ("<",     Prim "<")
  , ("<=",    Prim "<=")
  , (">",     Prim ">")
  , (">=",    Prim ">=")
  , ("==",    Prim "==")
  , ("/=",    Prim "!=")
  ]

main :: IO ()
main = do
  [fn] <- getArgs
  mdl <- parseDie pTop fn <$> readFile fn
  let ds = desugar mdl
      ds' = [ (n, compileOpt e) | (n, e) <- ds ]
      defs :: [(Ident, Exp)]
      defs = [ (n, ref i) | ((n, _), i) <- zip ds' [0..] ] ++ primOps
      find n = fromMaybe (error $ "undefined: " ++ show n) $ lookup n defs
      emain = find "main"
      res = foldr def emain (zip ds' [0..])
      def :: ((Ident, Exp), Int) -> Exp -> Exp
      def ((n, e), i) r = App2 CT (Lbl i (subst e)) r
      subst (Var n) = find n
      subst (App f a) = App (subst f) (subst a)
      subst e = e
      ref i = Var $ "_" ++ show i
--  mapM_ (\ (i, e) -> putStrLn $  i ++ " = " ++ toString e) ds
  mapM_ (\ (i, e) -> putStrLn $  i ++ " = " ++ toString e) ds'
  putStrLn $ toStringP res
  writeFile "out.comb" $ toStringP res

Every top-level definition n gets an integer index i (source-file order, zip ds' [0..]); every free variable reference to a top-level name inside any other definition's body is textually replaced (subst) by Var "_i" — a reference into b0c33a8f's label format, not a real bound variable. The whole program becomes nested T (Lbl i body_i) rest applications (T x y = y — T here is used purely to sequence a definition's text into the output; its value is discarded, its label is what matters), ending in a reference to whichever index main got. There is no dependency analysis, no forward-declaration handling beyond what the label format's own placeholder-before-parsing trick (b0c33a8f) buys for free, and an unresolved name doesn't fail to parse — it fails at find, with error $ "undefined: " ++ show n, a Haskell exception, not a diagnostic from the parser. It is exactly what the commit message says it is: a hack, applied to the actual problem (turning N independent compiled definitions into one closed, runnable graph) rather than a general solution to it (linking, dependency ordering, a real module system) — and it's honestly labeled as such in the commit log, not dressed up as a design decision. "Try it" exercise 1 below runs into this hack's exact limits.

`4030f721` and `b56ba28b`: parsing and combinators keep growing

4030f721 ("Parse more") adds one new expression form — a parenthesized operator, (+), usable anywhere a normal identifier is — in twelve added lines, all ordinary combinator code built from pieces aux/parser-combinators.md section 3 already covers; that doc walks the diff in full (section 5). b56ba28b ("More combinators.") is the eval.c side of b4e44ded's revived Pair/Cons rules: the P/O combinators get a tag in enum node_tag, a global combP/combO node, parser cases ('P'/'O'), a printer case, and runtime reduction rules (b56ba28b:eval.c, lines 599–620, quoted whole):

    case P:                     /* P x y f = f x y */
      CHECK(3);
      GCCHECK(1);
      x = ARG(TOP(1));
      y = ARG(TOP(2));
      f = ARG(TOP(3));
      POP(3);
      n = TOP(0);
      FUN(n) = new_ap(f, x);
      ARG(n) = y;
      GOTO ap;
    case O:                     /* P x y g f = f x y */
      CHECK(4);
      GCCHECK(1);
      x = ARG(TOP(1));
      y = ARG(TOP(2));
      f = ARG(TOP(4));
      POP(4);
      n = TOP(0);
      FUN(n) = new_ap(f, x);
      ARG(n) = y;
      GOTO ap;

P is pair's own combinator, three arguments in, applies the third to the first two; O is cons, four arguments, applies the fourth to the first two (the third — a "nil" continuation — is skipped over, which is what cons-vs-nil case analysis needs). Even the comment above case O: still says P x y g f = f x y — copy-pasted from the case above it and never updated to say O. This commit closes out the range: after b56ba28b, the language a source file can express has grown from nothing to modules, functions, data declarations, case expressions, and integers, and the runtime understands two new combinators it didn't a day earlier.

Why it matters

Four days after a compiler that could only run one hand-built term, a9178695 gives it a real front door: source text in, by way of an actual parser, not Haskell values assembled by hand in main. That's the headline. But the more durable habit visible across these eleven commits is what happens after the headline commit: the node representation changes (648aeef0), the optimizer gets rewritten from a two-pass design to a one-pass one and breaks compiling on the first attempt (9cf1e937/b4e44ded, forty seconds apart), and the missing "combine N definitions into one program" piece gets bolted on as an admitted hack (17587b2d) — five commits, 9cf1e937 through b56ba28b, span a total of 98 seconds of commit timestamps (12:46:22 to 12:48:00), which is not how long any of that code took to write; it's how long it took to commit work that had already been done. Rewriting two-day-old code — the optimizer, twice — costs nothing here, because nothing outside this project depends on it yet. That's a luxury a toy has and a shipped compiler doesn't, and this range uses it freely.

Notebook margin

Commit messages state intent, not mechanism. "Make a real compiler." doesn't say it adds a parser-combinator library, a desugarer, and a second copy of the bracket-abstraction pipeline in six new files; "New optimiser." (twice, 40 seconds apart) doesn't say the first of the two doesn't compile, or that the real change is fusing a cleanup pass into abstraction rather than adding new rules.
Representation experiments happen as commits on the mainline, not branches: 648aeef0 adds NODE_INDEX as a third option in eval.c's existing #if/#elif chain and flips one #define to activate it; NODE_NAIVE (chapter 01's representation) stays in the file, compiling, just not selected.
A hack, applied and honestly labeled: 17587b2d is the commit message before you even open the diff. What it hacks around — turning independently-compiled top-level definitions into one runnable, entry-point-aware graph — is a real problem this range never gives a general solution to.

Try it

Anchor: b56ba28b. Convention (see 00-overview.md):

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

This still runs the old Lam.hs/nfib.comb pipeline — the Makefile's test target was never updated in this range to build the new Main.hs/Parse.hs path at all (git show b56ba28b:Makefile is byte-identical to 6485a341's). Expect the same nfib 35 computation as chapter 01, on the new NODE_INDEX representation:

./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=16, heap size=100000
1045124618 reductions, 1944 GCs

Same answer, same reduction count and GC count as ccb31388's node size=24 build in chapter 01 — the representation change is invisible to the computation, only to memory per node.

Build note: the new parser-driven path (Main.hs) has no Makefile target at this commit and needs one line added to build at all with this project's flake toolchain (GHC 9.8.4, mtl 2.3.1). Building it as written fails:
nix develop $MICROHS -c ghc Main.hs -o uhs
ParserComb.hs:52:11: error: [GHC-88464]
    Variable not in scope:
      ap :: Prsr s (a -> b) -> Prsr s a -> Prsr s b
    Suggested fix: Perhaps use ‘map’ (imported from Data.List)
   |
52 |   (<*>) = ap
   |           ^^
ap (used in ParserComb.hs's Applicative instance, aux/parser-combinators.md section 2) isn't brought into scope by any of ParserComb.hs's own imports on this GHC/ mtl combination — it needs Control.Monad explicitly. Add one line after the existing import Control.Monad.State.Strict in ParserComb.hs:
import Control.Monad(ap)
Then the build succeeds:
nix develop $MICROHS -c ghc Main.hs -o uhs
[1 of 6] Compiling ParserComb       ( ParserComb.hs, ParserComb.o )
[2 of 6] Compiling Parse            ( Parse.hs, Parse.o )
[3 of 6] Compiling Exp              ( Exp.hs, Exp.o )
[4 of 6] Compiling Desugar          ( Desugar.hs, Desugar.o )
[5 of 6] Compiling Main             ( Main.hs, Main.o )
[6 of 6] Linking uhs
(A GHC warning about partial tail at Parse.hs:203 — the same kind of partiality chapter 01 noted in Lam.hs — appears too; harmless here, omitted above.) Apply this one-line patch before the exercises below.

Exercise 1: a tiny program in the accepted syntax

cat > pair.hs <<'EOF'
module Pair where
f x = x
main = f 3
EOF
./uhs pair.hs

f = I
main = f 3
((T :0 I) ((T :1 (_0 3)) _1))

The first two lines are ds' (each definition's compiled, optimized form — f x = x collapses to the identity combinator I, exactly the (\x. x) = I case aux/bracket-abstraction.md section 1 covers). The third line is 17587b2d's linked program, written to out.comb as well as stdout. Run it:

nix develop $MICROHS -c ./eval out.comb

3
node size=16, heap size=100000
14 reductions, 0 GCs

3, as expected. Worth trying, and worth knowing about 17587b2d's hack before you rely on it: swap the declaration order in pair.hs — main = f 3 before f x = x — and rebuild:

cat > fwd.hs <<'EOF'
module Fwd where
main = f 3
f x = x
EOF
./uhs fwd.hs
nix develop $MICROHS -c ./eval out.comb

ERR: shared == NIL

Labels are assigned in source order (zip ds' [0..]), so main — first in this file — is now label 0, referencing f — label 1 — by _1, before :1 has appeared in the printed text at all. b0c33a8f's parser is a single left-to-right pass with no forward-declaration support; a label has to be defined before it's referenced in the text, not just before it's needed. 17587b2d's "hack" inherits this constraint silently — nothing catches or reports it above the C-level ERR. (Put f back before main before continuing, or just use pair.hs again.)

Exercise 2: trigger a parse error

cat > bad.hs <<'EOF'
module Bad where
main = )
EOF
./uhs bad.hs

Actual behavior: an uncaught Haskell exception, all to stderr, exit code 1 (parseDie, a9178695:Parse.hs line 85: Left err -> error err):

uhs: line 2, col 7:
   found: ")"
   expeced: = white-space
   expeced: lower case
   expeced: upper case
   expeced: int digit
   expeced: '('
   expeced: \ symbol
   expeced: case letter, digit
   expeced: case <empty>

CallStack (from HasCallStack):
  error, called at ./Parse.hs:85:17 in main:Parse

Read literally: expeced is misspelled in the actual source (formatFailed, a9178695:ParserComb.hs line 109: pr e = " expeced: " ++ e) — not a transcription error here, the running binary really prints it that way. The list is every alternative tried and failed at the point of furthest progress (column 7, right after main = ), merged via <?>'s labeling and LastFail's longest. "case <empty>" traces to a specific, verifiable spot: pExpr's third alternative, pCase, starts with pKeyword "case" (a9178695:Parse.hs, lines 98–102, quoted whole):

pKeyword kw = (skipWhite $ do
  s <- pIdentRest
  guard (kw == s)
  pure ()
  ) <?> kw

On ), pIdentRest reads zero characters () isn't a letter or digit), so s = "", guard ("case" == "") is guard False, which is Alternative's empty (guard is Control.Monad's, not ParserComb.hs's own), and <?> "case" prepends "case" to empty's own "<empty>" message — unwords ["case", "<empty>"]. An honest byproduct of a two-day-old error-reporting pass (empty's literal placeholder text leaking into a real error message) rather than a deliberately designed one.

Exercise 3: the optimizer, before and after

9cf1e937~1..9cf1e937 (the literal endpoints of the first "New optimiser." commit) is not buildable — confirmed above in "What happened": 9cf1e937 alone fails with a parse error inherited from 71729105's typo, before the Lbl-not-in-scope problem its own diff would otherwise cause even gets a chance to surface. Neither this pair nor 71729105/9cf1e937/b4e44ded in any combination gives two buildable Main.hs binaries either side of the rewrite: b4e44ded's own Exp.hs builds, but the Main.hs sitting alongside it at that commit still calls the old, now-removed improve function and fails with Variable not in scope: improve.

Build note: substituting the nearest pair of commits where the relevant code (Exp.hs's compile/improve/compileOpt) both parses and typechecks on its own — a9178695 (before the rewrite; the original two-pass improveC/improveT) and b4e44ded (after; the fused smart-constructor version) — and comparing via ghci/ghc -e directly on Exp.hs, the same way aux/bracket-abstraction.md section 2 does, rather than through the full Main.hs pipeline (which needs the ap patch above at every commit in the range and isn't the part that actually changed).

git worktree add /tmp/mhs-a9178695 a9178695
cd /tmp/mhs-a9178695

Apply the same one-line ParserComb.hs fix as above (import Control.Monad(ap), needed here too since Exp.hs imports Parse, which imports ParserComb), then:

nix develop $MICROHS -c ghc -e 'let epair = Lam "x" (Lam "y" (Lam "f" (App2 (Var "f") (Var "x") (Var "y")))) in putStrLn (toString (compile epair)) >> putStrLn (toString (improve (compile epair)))' Exp.hs

S (K C) (S (S (K C) (K I)) I)
P

epair is \x. \y. \f. f x y — the pairing function, the exact form the Pair rule matches. Naive compile alone doesn't collapse it; a separate improve call is required to reach P. Second worktree:

git worktree add /tmp/mhs-b4e44ded b4e44ded
cd /tmp/mhs-b4e44ded

Same one-line fix, then:

nix develop $MICROHS -c ghc -e 'let epair = Lam "x" (Lam "y" (Lam "f" (App2 (Var "f") (Var "x") (Var "y")))) in putStrLn (toString (compile epair)) >> putStrLn (toString (compileOpt epair))' Exp.hs

P
P

compile alone already produces P — the abstraction step and the optimization are now one pass, not two, exactly as "What happened" describes from reading the diff; running it on the same input both sides of the rewrite confirms the diff's meaning rather than just its shape.

Clean up all three worktrees when done:

git worktree remove --force /tmp/mhs-b56ba28b
git worktree remove --force /tmp/mhs-a9178695
git worktree remove --force /tmp/mhs-b4e44ded

Learning from MicroHs

02 — A real compiler

Where we are

What happened

Warm-up: 2023-05-26

`a9178695`: "Make a real compiler." (2023-05-29, 16:14)

`648aeef0`: a third node layout for `eval.c`

`9cf1e937` + `b4e44ded`: "New optimiser." (2023-05-30, 12:46–12:47)

`17587b2d`: "Hack around a problem." (2023-05-30, 12:47:15, 13 seconds later)

`4030f721` and `b56ba28b`: parsing and combinators keep growing

Why it matters

Notebook margin

Try it

Exercise 1: a tiny program in the accepted syntax

Exercise 2: trigger a parse error

Exercise 3: the optimizer, before and after

Learning from MicroHs

a9178695: "Make a real compiler." (2023-05-29, 16:14)

648aeef0: a third node layout for eval.c

9cf1e937 + b4e44ded: "New optimiser." (2023-05-30, 12:46–12:47)

17587b2d: "Hack around a problem." (2023-05-30, 12:47:15, 13 seconds later)

4030f721 and b56ba28b: parsing and combinators keep growing

`a9178695`: "Make a real compiler." (2023-05-29, 16:14)

`648aeef0`: a third node layout for `eval.c`

`9cf1e937` + `b4e44ded`: "New optimiser." (2023-05-30, 12:46–12:47)

`17587b2d`: "Hack around a problem." (2023-05-30, 12:47:15, 13 seconds later)

`4030f721` and `b56ba28b`: parsing and combinators keep growing