03 — Growing the language

Where we are

chapter 02 leaves a compiler that reads a small lambda language from files: modules, function definitions, data declarations, case expressions, integer literals, application, and \x. expr lambdas, all parsed by the ParserComb.hs/Parse.hs combinator library (aux/parser-combinators.md), desugared by Desugar.hs to Exp.hs's tiny combinator core, and run by eval.c. Every top-level definition is linked into one program by 17587b2d's admitted hack: source order becomes a label number, and a name used before its own label has been printed crashes the C runtime with ERR: shared == NIL. This chapter's range, b56ba28b..95ff6a34, is twelve commits — nine landing in one sitting on 2023-05-30, the other three the next working session, 2023-06-01 — that turn that minimal language into something with let, infix operators, tuples, lists, characters, strings, module imports, and do-notation.

What happened

`5ccb1b2a`: comments, let, and error

Three unrelated features in one commit, each small enough that "unrelated things land together when they're this cheap" is itself worth noticing. Comments are handled before the parser ever sees the text, not inside it: parseDie now runs removeComments file on the whole source string first (5ccb1b2a:Parse.hs line 84), and removeComments is a line-oriented pass that blanks anything from -- to end of line while leaving the inside of "..." string literals alone (5ccb1b2a:Parse.hs, lines 90–98, quoted whole):

removeComments :: String -> String
removeComments = unlines . map remCom . lines
  where remCom ('-':'-':_) = ""
        remCom ('"':cs) = str cs
        remCom (c:cs) = c : remCom cs
        remCom "" = ""
        str ('"':cs) = remCom cs
        str ('\\':_:cs) = str cs
        str (_:cs) = str cs
        str "" = ""

(String literals aren't parseable syntax yet — that's ddb1bb29, seven commits later — but comment-stripping already has to route around a quoted -- so it doesn't eat the rest of the line.) let is a new expression form, ELet [Def] Expr, and it desugars to nested, non-recursive application of lambdas — "just sequential bindings", the comment above the case says (5ccb1b2a:Desugar.hs line 33, quoted with its comment):

-- For now, just sequential bindings.
dsExpr (ELet ds e) =
  let ds' = concatMap dsDef ds
      e' = dsExpr e
      def (i, d) e = App (Lam i e) d
  in  foldr def e' ds'

let x = a; y = b in e becomes (\x -> (\y -> e) b) a — each binding compiles to one more App (Lam ...) wrapped around what's inside it, in source order, with no letrec-style self-reference or mutual recursion support at all (a later chapter's problem). error is not a new syntax form — it's a new eval.c primitive, reached the same way + or < is, except it forces its argument, prints it to stderr, and exits (5ccb1b2a:eval.c, lines 661–667, quoted whole):

    case ERROR:
      x = ARG(TOP(1));
      x = evali(x);
      fprintf(stderr, "error: ");
      print(stderr, x);
      fprintf(stderr, "\n");
      exit(1);

`3aa12deb`: infix operators, and how fixity actually works here

Before this commit, pExpr only knew pExprApp (plain application), pLam, pCase, and pLet — no expression could contain a binary operator like + or == except by writing it as a parenthesized prefix identifier, (+) x y. 3aa12deb adds a new alternative, pExprOp, and this is the whole fixity mechanism at this commit, quoted whole (3aa12deb:Parse.hs, lines 203–212):

pExprOp :: P Expr
pExprOp = pA
  where
    pA = pRightAssoc (pOpers ["$"]) pB
    pB = pRightAssoc (pOpers ["||"]) pC
    pC = pRightAssoc (pOpers ["&&"]) pD
    pD = pNonAssoc (pOpers ["==", "/=", "<", "<=", ">", ">="]) pE
    pE = pLeftAssoc (pOpers ["+", "-"]) pF
    pF = pLeftAssoc (pOpers ["*", "quot", "rem"]) pG
    pG = pExprApp

There is no fixity declaration anywhere in the language, no table read from source, nothing a user program can influence. Precedence is literally the position of a parser in this fixed chain — pA is looser-binding than pB, which is looser than pC, and so on down to pG, which is plain function application, tightest of all. Associativity is which of three combinator functions wraps a given level: pRightAssoc, pNonAssoc, or pLeftAssoc, each parsing one occurrence of its own operand parser, then either recursing on itself (right-associative), taking exactly one more operand with no further chaining (non-associative — two == in a row is a parse error at this level), or folding left over a flat list of (op, operand) pairs (left-associative) — pLeftAssoc, quoted whole (3aa12deb:Parse.hs, lines 235–239):

pLeftAssoc :: P String -> P Expr -> P Expr
pLeftAssoc pOp p = do
  e1 <- p
  es <- emany ((,) <$> pOp <*> p)
  pure $ foldl (\ x (op, y) -> appOp op x y) e1 es

Fourteen operator tokens total get a home across these six levels ($, ||, &&, the six comparisons, +/-, */quot/rem), and every operator not on one of these six lists simply isn't a valid infix operator yet — writing a ++ b at this commit is a parse error, ++ doesn't appear until e96d04be inserts a new level for it (and :) between the comparison level and +/-. It is crude — precedence is baked into the parser's own call graph, adding an operator at a new precedence means inserting a new mutually-recursive pN function into the chain and renumbering nothing else, which is exactly what e96d04be does thirteen minutes later (p0 through p10, eleven numbered stages instead of six lettered ones, ->, :, ++, and . added). But it works, and it's the entire mechanism: no operator table, no user-extensible fixity, just a hand-written ladder of parsers.

`e96d04be`: type signatures, parsed and thrown away

The same commit that widens the operator ladder also adds f :: T as parseable syntax — and nothing else. The new Def case, Sign Ident Type (e96d04be:Parse.hs line 19), is built the same way every other alternative in pDef is (e96d04be:Parse.hs line 178):

  <|> Sign <$> (pLIdent <* pSymbol "::") <*> pType

pType, notably, isn't a separate grammar at all — it's pExpr under a different name (e96d04be:Parse.hs, lines 183–184, quoted whole):

pType :: P Type
pType = pExpr

A type signature is parsed as if it were an ordinary expression — Type is a type synonym for Expr — because there's no distinct type-syntax grammar to reuse yet, and the infix chain e96d04be just widened happens to already include -> at its loosest level (p0), which is what a T -> T signature needs to parse at all. And then the desugarer drops it on the floor, one line, the entire handling (e96d04be:Desugar.hs line 24):

dsDef (Sign _ _) = []

dsDef returns a list of compiled definitions for each Def; a Sign contributes zero of them. This is "parse and ignore": accept the syntax now, so source files that write type signatures don't fail to parse, without committing to any meaning for it yet. The meaning arrives months later — chapter 09 covers the type checker that finally reads what Sign is carrying instead of discarding it — but from e96d04be onward, every commit in between is free to write and ship code with type signatures in it that do nothing at all.

The shape of a feature commit: tuples, lists, strings

Three commits in a row show the same recipe at work — a new Expr constructor, a pAExpr alternative that builds it, and a dsExpr case that rewrites it to something the existing combinator core already understands.

Tuples (8939d55b) parse as a comma-separated list inside parentheses and desugar to a Scott-encoded continuation-passing function — the same trick chapter 02's a9178695:Desugar.hs used for data constructors, this time built by hand for the built-in tuple form (8939d55b:Parse.hs, lines 197–200, quoted whole):

eTuple :: [Expr] -> Expr
eTuple [] = ELam "_x" (EVar "_x")    -- encoding of ()
eTuple [e] = e
eTuple es = ELam "_f" $ foldl EApp (EVar "_f") es

A pair (a, b) becomes \f -> f a b — a value that is its own eliminator, waiting for a continuation. This shape is common enough that the same commit teaches the bracket-abstraction smart constructors to recognize it and collapse it straight to the P (pair) combinator chapter 02's b56ba28b added to eval.c, rather than build it out of S/K/C at the call site (8939d55b:Exp.hs line 95, one new line in cC):

cC (App2 CC CI e1) e2          = App2 CP e1 e2

List syntax (d91b9812) is even smaller — one parser alternative for [e1, e2, ...], and a two-line desugaring straight to nested cons/nil using b56ba28b's O combinator and the existing K (d91b9812:Desugar.hs lines 39–40, quoted whole):

dsExpr (EList es) =
  foldr (App2 CO) CK $ map dsExpr es

[1,2,3] becomes O 1 (O 2 (O 3 K)). No new runtime primitive: O's own reduction rule (redOne (App4 (Comb "O") x1 x2 f1 f2) = Just $ App2 f2 x1 x2, chapter 02's b56ba28b:Exp.hs line 184) needs two continuations, a nil-branch and a cons-branch, applied in that order — K a b = a is exactly the function that, given those two continuations, always picks the first (the nil-branch), which is why CK alone is a valid empty list: a Scott-encoded [] is a value that ignores its cons-continuation and returns its nil-continuation, and K does precisely that once partially applied to nothing else.

String literals (ddb1bb29) don't even need their own desugaring rule at the list level — a string is defined as a list of characters and handed straight to the list-desugaring case that already exists (ddb1bb29:Desugar.hs line 47, quoted whole):

dsExpr (EStr cs) = dsExpr $ EList $ map EChar cs

Two commits earlier, 60cd285c had already done the one piece of real work in this trio: character literals do need a new runtime primitive, because a Char isn't representable as anything already in eval.c — a new CHAR node tag joins enum node_tag right after INT (60cd285c:eval.c line 18), the parser gains a case '\'' that reads one raw byte off the stream into a CHAR node (60cd285c:eval.c lines 321–325), and eval's reduction loop treats CHAR the same inert way it already treats INT — a case CHAR: arm whose whole body is RET;, the same as INT's arm right above it, no reduction rule, just "this is already a value" (60cd285c:eval.c lines 508–511). Once that groundwork exists, EStr is free: strings are lists of Chrs, and both EList's desugaring and O/K's runtime behavior are already in place to carry them.

4e4c5252 ("Refactor.", between the list-syntax and character-literal commits) is not a feature: it's the moment case-pattern parsing, which had grown ad hoc pLHS pUIdent/tuple/[]/:-infix branches bolted on piece by piece as tuples and lists were added, gets pulled into one Pat type (PConstr Ident [Ident] | PTuple [Ident]) with dsExpr's ECase arm rewritten to match it. Nothing about what parses changes; what changes is that the four ad hoc pattern shapes now share one representation instead of four separately-threaded tuples. This is the first instance of a rhythm the rest of the chapter keeps repeating: feature, feature, refactor — clean up the accumulated mess only after enough of it has accumulated to be worth cleaning, not before.

`b25d9fc8`: importing modules

This is the biggest commit in the range — a new file, Compile.hs, 91 lines — and what "module" means here is more substantial than "parse and ignore": a module is a file, <Name>.uhs, whose own declared module name must match the file name it was loaded from (b25d9fc8:Compile.hs lines 40–45, quoted whole):

compileModule :: IdentModule -> StateT Cache IO CModule
compileModule nm = do
  let fn = nm ++ ".uhs"
  mdl@(Module nm' defs) <- parseDie pTop fn <$> liftIO (readFile fn)
  when (nm /= nm') $
    error $ "module name does not agree with file name: " ++ show nm

import M (a new Def case, one keyword away from data/import's neighbors in pDef) triggers compileModuleCached on M, which checks a Map of already-compiled modules before doing any work, and tracks a working list of modules currently mid-compile so that importing a module that (transitively) imports itself is a hard error rather than an infinite loop (b25d9fc8:Compile.hs lines 24–38) — genuine cycle detection, not a crude stopgap. Every top-level name a module defines ends up visible under two spellings in that module's own symbol table: unqualified (i) and dotted (mn ++ "." ++ i) — both point at the same qualified Var (b25d9fc8:Compile.hs line 53, quoted whole):

    syms (mn, ds) = [ (s, [Var qi]) | (i, _) <- ds, let qi = mn ++ "." ++ i, s <- [i, qi] ]

which is why two imported modules defining the same unqualified name is an ambiguity error at reference time (checkExpr's Just qis -> error $ "ambiguous: " ++ ..., unchanged from 17587b2d) rather than something caught at import time. There's a smaller fix bundled into the same commit that quietly closes a gap chapter 02's "Try it" ran straight into: 17587b2d's label format required a definition's :N to appear in the printed text before any _N reference to it, so a main that textually preceded the function it called crashed the C runtime with ERR: shared == NIL. b25d9fc8:eval.c makes both the _ and : cases allocate the indirection placeholder unconditionally, whichever one is seen first, instead of the _ case demanding the placeholder already exist (b25d9fc8:eval.c, lines 336–343, quoted whole):

  case '_' :
    l = (int)parse_int(f);  /* The label */
    if (shared[l] == NIL) {
      /* Not yet defined, so make it an indirection */
      shared[l] = alloc_node(IND);
      INDIR(shared[l]) = NIL;
    }
    return shared[l];

Forward references within one linked program now just work — not because the linking hack from 17587b2d got redesigned, but because the label format underneath it grew the one piece of order-independence it was missing.

`ff4622e8` and `693dc6ce`: another refactor, then do-notation

ff4622e8 ("Refactor ident parsing.") is the second instance of the feature-feature-refactor rhythm: identifiers, which had been three separately-defined parsers (lowercase, uppercase, and an ad hoc character set for "rest of identifier"), get unified around one pWord/pIdent pair and a new pQIdent that threads .-separated segments together — M.name, a qualified reference, is now representable at all, which 693dc6ce, twenty-two seconds later, immediately needs. do-notation doesn't dispatch on a Monad type class — there isn't one yet — it dispatches on an explicit qualifier written at the call site: pDo parses <Uident>.do { ... }, and that identifier is threaded through every desugared bind as the prefix of the operator name it calls (ff4622e8:Parse.hs, lines 359–372, quoted whole):

pDo :: P Expr
pDo = EDo <$> pQualDo <*> pBlock pStmt

pStmt :: P Stmt
pStmt =
      (Bind <$> (pLIdent <* pSymbol "<-") <*> pExpr )
  <|> (Then <$> pExpr)

pQualDo :: P String
pQualDo = do
  s <- pUIdent
  _ <- char '.'
  pKeyword' "do"
  pure s

The desugaring, all of 693dc6ce:Desugar.hs's new lines (49–53, quoted whole):

dsExpr (EDo _ []) = error "empty do"
dsExpr (EDo _ [Bind _ _]) = error "do without final expression"
dsExpr (EDo _ [Then e]) = dsExpr e
dsExpr (EDo n (Bind i e : ss)) = App2 (Var (n ++ ".>>=")) (dsExpr e) (Lam i $ dsExpr (EDo n ss))
dsExpr (EDo n (Then   e : ss)) = App2 (Var (n ++ ".>>"))  (dsExpr e)         (dsExpr (EDo n ss))

M.do { x <- e; rest } becomes (M.>>=) e (\x -> rest'), where rest' is rest recursively desugared the same way (still as an M.do block if more than one statement remains); M.do { e; rest } becomes (M.>>) e rest' the same way — textbook do desugaring, except that M.>>= and M.>> are not resolved through any type-class machinery at all, just looked up in the symbol table like any other qualified name. Whatever module defines (>>=) and (>>), its own name is the qualifier that unlocks do-notation for it — at this commit that's IO, wired in as two more entries in Compile.hs's still-hardcoded primOps list (693dc6ce:Compile.hs lines 78–79: ("IO.>>=", Prim "IO.>>="), ("IO.>>", Prim "IO.>>")), but nothing in pQualDo or dsExpr's EDo cases is specific to IO — any module that defines its own (>>=)/(>>) gets its own usable do block for free, IO monad or not ("Try it" exercise 1 uses exactly this to run do-notation without touching IO at all).

`95ff6a34`: `primitive`, and decoupling the compiler from the runtime

Every runtime primitive up to this commit is a hardcoded entry in Compile.hs's primOps list — one Haskell-source line per primitive, maintained by hand, growing every time a new operator needs a runtime counterpart. 95ff6a34 deletes that list outright and replaces it with a new expression form that lets any module spell out its own primitive bindings: primitive "tag" is new parseable syntax (95ff6a34:Parse.hs line 291, one alternative added to pAExpr):

  <|> (EPrim <$> (pKeyword "primitive" *> pString))

and it desugars, unsurprisingly given how mechanical the mapping is, to exactly the Exp.hs constructor its old table used to build by hand (95ff6a34:Desugar.hs line 54, quoted whole):

dsExpr (EPrim s) = Prim s

Three new source files land in the same commit — Prelude.uhs, IO.uhs, and List.uhs (a List data declaration plus map, unrelated to primitive). Prelude.uhs and IO.uhs are, line after line, nothing but top-level bindings whose right-hand side is primitive "..." — (+) = primitive "+", error = primitive "?", (>>=) = primitive "IO.>>=", readFile = primitive "IO.readFile", and so on. What used to require editing Compile.hs (a compiler-internal, Haskell-source file) to add a runtime primitive now requires only writing one line in a .uhs module (an ordinary program source file) — the string inside primitive "..." is the only thing that has to match what eval.c actually understands, and the compiler itself no longer needs to know the runtime's combinator vocabulary at all. Exp.hs's flipOps table (used by the bracket-abstraction smart constructor cC to recognize "flip this comparison instead of building a C combinator around it") gets its entries requalified to "Prelude.+", "Prelude.<", and so on in the same commit (95ff6a34:Exp.hs lines 115–124) — a small, honest side effect of the primitive names now living inside a real module instead of a hardcoded list of bare strings.

Why it matters

Look at what each of these commits actually costs. dsDef (Sign _ _) = [] is one line. dsExpr (EStr cs) = dsExpr $ EList $ map EChar cs is one line and doesn't even introduce a new case in the runtime — it just routes through a desugaring that already exists. dsExpr (EList es) = foldr (App2 CO) CK $ map dsExpr es needs no new combinator either, because O and K were already sitting in eval.c from chapter 02. That's the payoff of compiling everything down to a handful of SKI-style combinators before it ever reaches the runtime: most new surface syntax is free at the back end — it's just a new way to build a term the combinator core already knows how to run. The exceptions are instructive precisely because they're rare: character literals needed a real new runtime primitive (a CHAR node tag, a parser case, a GC- visible representation in eval.c), and that's the one feature in this chapter that took more than a few lines in two Haskell files. Everything else — let, tuples, lists, strings, type signatures, do-notation — is parser lines plus desugarer lines, no runtime change at all.

"Parse and ignore" is the same economy applied to time instead of code. e96d04be doesn't need to decide what a type signature means to let programmers write f :: Int -> Int above f's definition — accepting the syntax and discarding it costs one line and buys months: every commit between here and chapter 09 is free to use signatures as documentation, or not use them at all, without the type checker existing yet to enforce or even read them. Momentum matters more than completeness at this stage of the project, and both habits — desugar to a tiny core, accept syntax before you've decided its semantics — are how a language grows fast without every commit becoming a small research project.

Notebook margin

Feature per commit, chronologically: let+comments+error, infix operators, type signatures (ignored), tuples, list syntax, character literals, string literals, module imports, do-notation, primitive. Two commits in the range aren't features at all — 4e4c5252 and ff4622e8 are refactors, and both land only after enough ad hoc special-casing has piled up to be worth unifying (pattern-parsing after tuples and lists both bolted their own cases on; identifier- parsing right before qualified names become load-bearing for do). Refactors are interleaved with feature work, not batched into their own commit or their own day.
The day's count: nine of this chapter's twelve commits — 5ccb1b2a through b25d9fc8 — land on 2023-05-30, the same day chapter 02 closes with b56ba28b. The remaining three — ff4622e8, 693dc6ce, 95ff6a34 — land on 2023-06-01, the next working session.
A hardcoded fixity ladder is still a fixity mechanism: 3aa12deb's pA/pB/.../pG chain has no operator table and no user-facing fixity declarations, but it correctly parses 1 + 2 * 3 as 1 + (2 * 3) because * sits one level tighter than + in the chain — the entire precedence table is which function calls which, nothing more abstract than that.

Try it

Anchor: 693dc6ce ("Add do desugaring."). Convention (see 00-overview.md):

git worktree add /tmp/mhs-693dc6ce 693dc6ce
cd /tmp/mhs-693dc6ce

Like chapter 02's b56ba28b, this commit's Makefile has no target for the parser-driven compiler (Main.hs) — only the old Lam.hs/eval.c test target exists. Building Main.hs by hand hits the exact same GHC-9.8/mtl issue chapter 02's Build note covers, plus one more that's new to this chapter's range because it's the first commit in the range where the new file the note is about, Compile.hs, exists at all.

Build note: building as written —
nix develop $MICROHS -c ghc Main.hs -o uhs
fails first with chapter 02's ap-not-in-scope error in ParserComb.hs (Variable not in scope: ap :: Prsr s (a -> b) -> Prsr s a -> Prsr s b, ParserComb.hs:52:11) — apply the same one-line fix chapter 02 uses, adding it after ParserComb.hs's existing import Control.Monad.State.Strict:
import Control.Monad(ap)
With that fix, the build gets further and hits a second, same-shaped problem in the module b25d9fc8 added, Compile.hs:
Compile.hs:30:7: error: [GHC-88464]
    Variable not in scope: when :: Bool -> a2 -> StateT Cache IO a3
    Suggested fix:
      Perhaps use data constructor ‘Then’ (imported from Parse)
   |
30 |       when (nm `elem` ws) $
   |       ^^^^
(a second, identically-shaped error follows at Compile.hs:44:3, the function's other when call — omitted above.) when (used twice in Compile.hs, both to raise an error on a bad condition) isn't brought into scope by Compile.hs's own import Control.Monad.State.Strict on this GHC/mtl combination either — the same root cause as the ap problem, a different symbol, a different file. Add one line after Compile.hs's existing import Control.Monad.State.Strict:
import Control.Monad(when)
Then the build succeeds (harmless -Wx-partial warnings about head/ tail, the same kind chapter 02 noted, omitted below):
nix develop $MICROHS -c ghc Main.hs -o uhs
[1 of 7] Compiling ParserComb       ( ParserComb.hs, ParserComb.o )
[2 of 7] Compiling Parse            ( Parse.hs, Parse.o )
[3 of 7] Compiling Exp              ( Exp.hs, Exp.o )
[4 of 7] Compiling Desugar          ( Desugar.hs, Desugar.o )
[5 of 7] Compiling Compile          ( Compile.hs, Compile.o )
[6 of 7] Compiling Main             ( Main.hs, Main.o )
[7 of 7] Linking uhs
One more piece is needed before the runtime can execute anything the new compiler produces: eval.c itself, which the Makefile's eval target already knows how to build —
nix develop $MICROHS -c gcc -Wall -O3 eval.c -o eval
Apply both one-line patches and build eval before the exercises below.

Also note, since Compile.hs landed in b25d9fc8: a source file is loaded by module name, not by file argument — Compile.hs's compileModule reads <name>.uhs, not whatever path you pass on the command line, and ./uhs Foo (not ./uhs Foo.uhs) is how the new Main.hs invokes it ([mn] <- getArgs; ds <- compile mn, 693dc6ce:Main.hs).

Exercise 1: let, a list, and do-notation, without touching IO

do-notation at this commit doesn't require the IO module or any built-in monad — M.do just needs a module M with its own (>>=) and (>>) in scope, per "What happened" above. Write one small self-contained module that supplies a trivial (>>=)/(>>) pair and then uses them via do:

cat > Demo.uhs <<'EOF'
module Demo where

(>>=) x f = f x
(>>) x y = y

main = Demo.do
  y <- 10
  let
    xs = [1, 2, 3]
   in case xs of
    [] -> 0
    (:) a as -> a + y
EOF
nix develop $MICROHS -c ./uhs Demo

importing "Demo"
importing done "Demo"
Demo.>>= = C I
Demo.>> = T
Demo.main = Demo.>>= 10 (C' (P 0) (B (B K) (C +)) (O 1 (O 2 (O 3 K))))
((T :0 (C I)) ((T :1 T) ((T :2 ((_0 10) (((C' (P 0)) ((B (B K)) (C +))) ((O 1) ((O 2) ((O 3) K)))))) _2)))

Run the linked program:

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

((T :99996 (C I)) ((T T) ((T :99989 ((_99996 10) (((C' (P 0)) ((B (B K)) (C +))) ((O 1) ((O 2) ((O 3) K)))))) _99989)))
11
node size=16, heap size=100000
56 reductions, 0 GCs

eval.c's main calls pp(stdout, n) twice, once right after parsing and once after reduction (693dc6ce:eval.c lines 704 and 706 — unchanged since chapter 02's 54806439) — the first line above is the parsed-but-unreduced term, printed through pp's own independent sharing-detection pass (hence label numbers like :99996 that don't match the file's own :0/:1/:2), and the second line is the answer after evali runs: 11. y is bound to 10 by the do-block's Bind, xs is the list [1,2,3], the case on xs matches the (:) a as arm with a = 1, and a + y = 11. Two dead ends worth knowing about on the way here, both genuine limits of this commit's parser, not typos in the example above:

let x = 5 in x on one line does not parse:
```
cat > T1.uhs <<'EOF'
module T1 where

main = let x = 5 in x
EOF
nix develop $MICROHS -c ./uhs T1
```
```
importing "T1"
uhs: line 3, col 11:
   found: "x"
   expeced: let ' '
   ...
```
the block let opens (via pBlock's softLC) always takes its indentation from the next physical line, never the rest of the current one, so the bound variables have to start on a new, indented line.
in has to be indented to a column strictly between the enclosing do-block's column and the let-block's own column (here: do starts its statements at column 2, let's own block is at column 4, so in sits at column 3). Indent in to column 2 or less and the layout algorithm's dedent-on-whitespace rule (pWhite, Parse.hs) closes the let block correctly but then also reads the same dedent as the start of a new do-statement, injecting a ; in front of in and breaking the parse. A case with only the (:) arm and no [] arm also silently fails to reduce — chapter 02's O combinator takes two continuations (nil-branch, then cons-branch) in that order, and a one-arm case under-applies it, leaving the result stuck as a partial application instead of a number (confirmed by running the one-arm version through eval and getting an unreduced term back, not an error).

Exercise 2: read the desugared do-chain out of `out.comb`

Exercise 1's out.comb is 106 bytes, small enough to read whole:

((T :0 (C I)) ((T :1 T) ((T :2 ((_0 10) (((C' (P 0)) ((B (B K)) (C +))) ((O 1) ((O 2) ((O 3) K)))))) _2)))

:0, :1, :2 are the three top-level definitions in source order — Demo.>>=, Demo.>>, Demo.main — each compiled to a combinator term and linked by 17587b2d's label scheme (chapter 02). :0's term is C I — (>>=) x f = f x compiled by bracket abstraction, since C f x y = f y x, so C I x y = I y x = y x = f x with f and x renamed to match. :2, Demo.main's term, is where the do-desugaring from 693dc6ce:Desugar.hs is directly visible: (_0 10) (...) is _0 (Demo.>>=, i.e. the bind operator) applied to 10 (the desugared Bind "y" (EInt 10)) applied to a lambda-turned-combinator continuation — exactly the shape dsExpr (EDo n (Bind i e : ss)) = App2 (Var (n ++ ".>>=")) (dsExpr e) (Lam i $ dsExpr (EDo n ss)) produces, with n = "Demo", i = "y", e = EInt 10, and ss the case-expression that becomes the continuation's body. The continuation itself, (C' (P 0) (B (B K) (C +))) (O 1 (O 2 (O 3 K))), is the compiled case-on-a-list from Exercise 1's dead-end note: O 1 (O 2 (O 3 K)) is [1,2,3] (d91b9812:Desugar.hs's EList desugaring — see "What happened"), and (P 0)/(B (B K) (C +)) are the compiled [] -> 0 and (:) a as -> a + y arms in that order, the two continuations O's reduction rule expects.

Exercise 3: extend the parser — underscores in integer literals

pInt at this commit accepts one or more digits and nothing else (693dc6ce:Parse.hs line 204, quoted whole):

pInt :: P Integer
pInt = (read <$> (skipWhite $ esome $ satisfy "digit" isDigit)) <?> "int"

Confirm that a Haskell-style digit-group separator doesn't parse today:

cat > Under.uhs <<'EOF'
module Under where

main = 1_000
EOF
nix develop $MICROHS -c ./uhs Under

importing "Under"
uhs: line 3, col 8:
   found: "_000"
   expeced: int digit
   ...

(pInt reads 1 and stops at the first non-digit; pExprApp then looks for another atomic expression to apply 1 to and _000 isn't one — it doesn't start with a letter, so it isn't an identifier either.) Edit pInt (Parse.hs, the same one line quoted above) to accept _ as a digit-group separator, requiring a leading digit and filtering underscores out before read:

Before (Parse.hs line 204):

pInt = (read <$> (skipWhite $ esome $ satisfy "digit" isDigit)) <?> "int"

After:

pInt = (read . filter (/= '_') <$> (skipWhite $ (:) <$> satisfy "digit" isDigit <*> emany (satisfy "digit" isDigit <|> char '_'))) <?> "int"

Rebuild and rerun:

nix develop $MICROHS -c ghc Main.hs -o uhs
nix develop $MICROHS -c ./uhs Under

[2 of 7] Compiling Parse            ( Parse.hs, Parse.o ) [Source file changed]
[7 of 7] Linking uhs [Objects changed]
importing "Under"
importing done "Under"
Under.main = 1000
((T :0 1000) _0)

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

((T 1000) 1000)
1000
node size=16, heap size=100000
6 reductions, 0 GCs

(the first line is pp's pre-reduction echo, same as Exercise 1's transcript above; the second, 1000, is the reduced answer.) 1_000 now parses as the integer 1000 and runs to 1000; a plain main = 42 (no underscore) still compiles and runs to 42 unchanged — confirmed by rerunning it through the patched uhs the same way:

cat > Reg.uhs <<'EOF'
module Reg where

main = 42
EOF
nix develop $MICROHS -c ./uhs Reg
nix develop $MICROHS -c ./eval out.comb

((T 42) 42)
42
node size=16, heap size=100000
6 reductions, 0 GCs

Clean up:

git worktree remove --force /tmp/mhs-693dc6ce

Learning from MicroHs

5ccb1b2a: comments, let, and error

3aa12deb: infix operators, and how fixity actually works here

e96d04be: type signatures, parsed and thrown away

b25d9fc8: importing modules