🌐 ν•œκ΅­μ–΄λ‘œ 읽기

06 β€” Becoming Haskell

Where we are

Chapter 05 closes at 8018eec8 ("Add null"), 19:10:07 on 2023-06-02 β€” a working little language with monadic IO, a working IO.serialize/IO.deserialize pair, a three-module golden-file test harness wired into make test, and a first README.md. The module system that exists at that point is minimal: lib/Prelude.hs, lib/IO.hs, lib/List.hs, and lib/String.hs sit as four flat files, none of them carrying an export list, none of them importable with a qualifier or an as-alias, and every module's every top-level name floods into one shared unqualified symbol table β€” two imports defining the same name collide as a runtime "ambiguous" error, not something a programmer reaches for on purpose. do-notation still needs an explicit qualifier at every call site (IO.do, not do). There is no if, no list comprehensions, no operator sections. This chapter's first commit, 5f08e33b, lands seven seconds after 8018eec8 β€” the same sitting, not a new session.

What happened

The range 8018eec8..41d6a7e8 is 30 commits, and they land on four calendar days out of the six the range spans: one commit late on 2023-06-02 (a continuation of chapter 05's own evening), 22 commits in one sitting on 2023-06-03 (11:33 to 15:02, roughly three and a half hours β€” nothing on 06-04), 4 commits on 2023-06-05 (11:17 to 15:17, with a three-and-a-half-hour gap inside that day β€” nothing on 06-06), and 3 commits on 2023-06-07 (10:51 to 14:13). Then the log goes quiet: the next commit dated after 41d6a7e8 (2023-06-07 14:13:56) is 44004020 ("Small fixes."), 2023-07-01 15:41:40 β€” 24 days later, and, per this book's own overview, "[n]othing in this repo's history explains the 24-day gap β€” the log simply resumes." One more wrinkle, visible only in the commit graph, not the flat git log the overview's table reads from: 44004020 isn't actually a child of 41d6a7e8. Its own parent is 53d4bfdc (06-03 15:02:16, this chapter's next-to-last 06-03 commit) β€” a checkout that predates every commit from d5bac600 onward, missing if, list comprehensions, both file reorganizations, and the CHAR removal entirely. About six minutes after 44004020, a merge commit, d128fb6f ("Merge branch 'master' of github.com:augustss/MicroHs", also 2023-07-01), reconciles that stale branch with 41d6a7e8. Read as a graph rather than a date-sorted list, the honest picture is two checkouts that fell out of sync on 06-03 and were stitched back together on 07-01 β€” not a single line of work that simply paused for 24 days and resumed. That gap, and what resumes on the other side of it, is the next chapter's story, not this one's.

Inside the six working days that do have commits, three things happen at once: the module system grows qualification, aliasing, and required export lists; the file layout is reorganized twice to mirror Haskell's own directory conventions; and the surface syntax picks up if, operator sections, and list comprehensions. A fourth, smaller thread β€” scope checking moving into the desugarer, and Char losing its own runtime representation β€” is where the compiler's internals catch up with everything the other three threads asked of it.

The module system becomes Haskell-shaped

06-03 opens with two structural preludes before the module-system work proper starts. 35ef759d ("Refactor module desugaring.") replaces the bare (IdentModule, [LDef]) tuple chapter 03's b25d9fc8 used for a compiled module with a real Module type carrying its own export list and constructor-arity table (35ef759d:Desugar.hs line 11, quoted whole):

data Module = Module IdentModule [Export] [TypeDef] [LDef]

69437754 ("Use a map for final lookup"), fifteen minutes later, swaps Main.hs's final-linking lookup from a linear lookup over a list β€” one list scan per reference, into every earlier definition β€” to a Data.Map (69437754:Main.hs lines 21–23, quoted whole):

      defs :: M.Map Ident Exp
      defs = M.fromList [ (n, ref i) | ((n, _), i) <- zip ds' [0..] ]
      findIdent n = fromMaybe (error $ "undefined: " ++ show n) $ M.lookup n defs

Neither commit is user-visible; both are the kind of "clean the load- bearing plumbing before building more on it" move chapter 03 already named a rhythm.

Then, in quick succession: 155e9f5a ("Add 'qualified' to imports.") adds the qualified keyword, threading a Bool through ImportSpec so a qualified import's names only enter the symbol table under their dotted form, never bare (155e9f5a:Parse.hs lines 279–280, quoted whole):

  <|>            (pKeyword "import" *> (Import <$> pQua <*> pUIdent))
  where pQua = (True <$ pKeyword "qualified") <|< pure False

cfbf3c7d ("Implement 'as' in 'import' statement"), 28 minutes later, adds the alias itself β€” ImportSpec grows a third field, Maybe Ident, and pImportSpec becomes one self-contained parser instead of being spelled out inline in pDef (cfbf3c7d:Parse.hs lines 280–282, quoted whole):

pImportSpec :: P ImportSpec
pImportSpec = ImportSpec <$> pQua <*> pUIdent <*> optional (pKeyword "as" *> pUIdent)
  where pQua = (True <$ pKeyword "qualified") <|< pure False

Seven minutes after that, bd28b65c ("Avoid errors on multiple imports of the same module.") fixes a bug the previous two commits' own symbol- table plumbing exposes: when the same module is reachable by two import paths (directly, and transitively through another import), its qualified names were being inserted twice via (++), so the "ambiguous" check chapter 03 built (checkExpr's Just qis -> error "ambiguous: ") fired against a name that wasn't actually ambiguous β€” it just appeared in its own symbol-table bucket twice. The fix is switching the map-merge function from list concatenation to Data.List.union, which already dedupes (bd28b65c:Desugar.hs lines 39–44, quoted whole):

      allSyms :: SymTable
      allSyms = M.fromListWith union $ concatMap syms (imdl : mdls)
        where syms (is, Module mn qis _ _) = [ (v, [Var qi]) | (i, qi) <- qis, v <- qns is mn i ]
      allTypes :: TypeTable
      allTypes = M.fromListWith union $ concatMap types (imdl : mdls)
        where types (is, Module mn _ tds _) = [ (v, [td]) | td@(TypeDef _ cs) <- tds, (c, _) <- cs, v <- qns is mn c ]

Between cfbf3c7d and bd28b65c, two file-reorganization commits land (16c75970, 4f3b8f8d β€” covered below under "Files reorganize"), and then 7c23e672 ("Make 'do' qualifier optional.") lets do stand alone: EDo's qualifier becomes Maybe Ident instead of a required Ident, and an unqualified do looks up (>>=)/(>>) unqualified rather than demanding a module prefix at every call site β€” the change chapter 03's "Try it" exercise had to route around by hand is now built in, and Example.hs's own main drops its IO.do down to plain do in the same commit.

The last piece of the module-system thread is 1136f265 ("Require an export list."), 06-03 at 14:10:46. Before this commit module M where parses; after it, pModule demands a parenthesized export list between the module name and where, with only one kind of export item implemented β€” module M, a whole-module re-export, nothing selective (1136f265:Parse.hs lines 155–161, quoted whole):

pModule :: P EModule
pModule = EModule <$> (pKeyword "module" *> pUIdent) <*>
                      (pSym '(' *> many pExportSpec <* pSym ')') <*>
                      (pKeyword' "where" *> pBlock pDef)

pExportSpec :: P ExportSpec
pExportSpec = ExpModule <$> (pKeyword "module" *> pUIdent)

Running a module with no export list at all through the compiler (a build later in this chapter reproduces the exact transcript β€” see "Try it" Exercise 3) now fails to parse right after the module name, before where is even reached β€” module NoExport where gets rejected with expeced: '(' (the source's own spelling, kept verbatim below). The same commit updates every existing library and test module to the only form the new grammar accepts, module M(module M) where β€” a whole-module self-re-export, which is the sole way to write "export everything" until selective export lists exist. One of those mechanical edits ships with a real typo: tests/ListTest.hs gets module ListTest(Module ListTest) where β€” a capitalized Module that isn't the module keyword pExportSpec looks for, so it wouldn't have parsed. The very next commit, dba211e1 ("More tests"), three minutes later, fixes it to lowercase along with unrelated content changes to the same test β€” a small, honest reminder that a 30-commit, six-day sprint still ships the occasional bug it catches almost immediately.

Files reorganize, in commits of their own

Two separate reorganizations happen in this range, each split cleanly from any commit that changes behavior.

The first: 16c75970 ("Reorganize modules to be more like Haskell.") deletes the bodies of the flat lib/IO.hs and lib/List.hs (191 lines removed, 9 files touched, 13 insertions β€” mostly import-line updates in Desugar.hs and the test modules) and, 47 seconds later, 4f3b8f8d ("Moved files.") adds lib/Data/List.hs and lib/System/IO.hs back with that same content, now living under Haskell-shaped paths (178 lines, pure additions, two files). The pair of commits is a manual git mv β€” content deleted in one commit, recreated verbatim (module name and all) in the very next β€” rather than a single commit doing both at once.

The second reorganization is bigger and, read literally against the tree at each commit, leaves the project unbuildable for a stretch. 34c8965e ("Rearrange files."), 06-05 at 15:17:24, deletes Compile.hs, Desugar.hs, Exp.hs, Main.hs, Parse.hs, and ParserComb.hs outright β€” 975 lines of Haskell source gone, with no replacement for any of it anywhere in the same commit (the commit's --stat totals 980 deletions across 8 files; the other 5 are Makefile lines rewritten below) β€” while renaming eval.c to src/runtime/eval.c and repointing the Makefile at paths that, at that exact commit, don't exist (34c8965e:Makefile, quoted in full):

BIN=bin
.PHONY: all test time example

all:	$(BIN)/eval $(BIN)/uhs

$(BIN)/eval:	src/runtime/eval.c
	@mkdir -p bin
	gcc -Wall -O3 src/runtime/eval.c -o $(BIN)/eval

$(BIN)/uhs:	src/*/*.hs
	@mkdir -p bin
	ghc -Wall -O -isrc src/MicroHs/Main.hs -o $(BIN)/uhs

test:	$(BIN)/eval $(BIN)/uhs tests/*.hs
	cd tests; make test

time:	$(BIN)/eval $(BIN)/uhs tests/*.hs
	cd tests; make time

example:	$(BIN)/eval $(BIN)/uhs Example.hs
	$(BIN)/uhs -ilib Example && $(BIN)/eval

clean:
	rm -f src/*/*.hi src/*/*.o eval Main *.comb *.tmp *~ $(BIN)/*
	cd tests; make clean

git ls-tree -r 34c8965e --name-only confirms it directly: no file under src/MicroHs/ exists at this commit β€” the Makefile's own $(BIN)/uhs: src/*/*.hs rule has nothing to match. ac6f377c ("Make files a bit more like Haskell."), the next commit touching the tree, lands almost two days later (2023-06-07 10:51:20) and only edits lib/System/IO.hs and src/runtime/eval.c β€” the compiler sources stay missing. Only 2f89971e ("Move files."), 06-07 at 14:13:33, restores them, under src/MicroHs/*.hs and src/Text/ParserComb.hs, each file's own module line requalified to match its new path (module Compile becomes module MicroHs.Compile, and so on). But "Move files." under-describes its own diff, the same way ac6f377c (next paragraph) does, in two separate respects. First, diffing the restored files against the content 34c8965e deleted shows four of the six are indeed pure moves (module/import lines only) β€” but Desugar.hs and Exp.hs come back changed: Exp's Chr Char constructor is gone, Int Integer narrows to Int Int, and EChar c now desugars to Int (fromEnum c) β€” the compiler-side half of the CHAR removal, landing inside the "move" commit 23 seconds before 41d6a7e8 (below) deletes the runtime-side half. Second, the commit adds seven files, and the seventh, src/MicroHs/Translate.hs (78 lines), is not a moved file at all β€” it has no earlier counterpart anywhere in the project's history. It's the first draft of something new: a translator from the compiler's Exp combinator terms straight into native GHC values (trans :: Exp -> Any, built on unsafeCoerce, with a primOps table pairing each combinator name with an actual Haskell function β€” comb "S" (\ f g x -> f x (g x)), comb "Y" (let fix f = f (fix f) in fix), and so on) β€” that is, a way to run compiled programs inside GHC's own runtime instead of shipping them to eval.c (and the reason Exp's integers just became machine-width Int: Translate.hs's arithmetic table is typed Int -> Int -> Int). It's also visibly unfinished: line 52 of the committed file reads , comb "IO.h β€” an unterminated string literal, a file frozen mid-keystroke, which can't even lex. It doesn't break the build only because nothing imports it yet (2f89971e:src/MicroHs/Main.hs imports Parse/Exp/Compile, not Translate, and ghc -isrc only compiles what Main reaches). Where this thread goes is the next chapter's material; here it's a stowaway in a commit titled like pure housekeeping. Meanwhile the headline fact about the pair of commits stands: for roughly 47 hours, spanning the boundary between this chapter's 06-05 and 06-07 sessions, this repository's own history has no commit from which uhs can be built at all β€” a genuine gap in buildability, not an artifact of this book's worktree convention, and the reason this chapter's own "Try it" anchors before it (see below).

ac6f377c's own diff, landing inside that gap, is worth one aside: its title reads as pure cosmetic rename work, but the diff to lib/System/IO.hs adds real error handling β€” hGetChar and openFile now raise a proper error on EOF or a failed open instead of silently handing back a sentinel value β€” and the diff to src/runtime/eval.c fixes a genuine garbage-collector bug: scan's sweep was closing stdin/stdout/stderr as unreachable file handles whenever nothing else pointed at them from the program graph, which the commit corrects by excluding those three handles from the close-on-collect check. A commit named for tidying carries a real bug fix and a real behavior change alongside it β€” the same "commit titles don't fully describe their diffs" pattern chapter 05 flags for 3cdbb820.

Scope checking moves into desugaring

0cc677d5 ("Change desugaring to do scope checks. Add case error checks."), 06-03 at 12:30:50, is the biggest single-commit change in this thread. Before it, Compile.hs desugars a module first and then walks the already-desugared Exp tree in a separate pass, checkExpr (chapter 03's b25d9fc8), resolving each bare Var against a symbol table built from every imported module's exports. 0cc677d5 deletes that separate pass and folds its job straight into dsExpr, which now takes the symbol table (and a matching constructor-arity table) as an argument and resolves every EVar the moment it's desugared, not afterward (0cc677d5:Desugar.hs lines 53–57, quoted whole):

dsExpr syms _ (EVar i) =
  case M.lookup i syms of
    Nothing -> error $ "undefined: " ++ show i
    Just [qi] -> qi
    Just qis -> error $ "ambiguous: " ++ show i ++ ", " ++ show qis

The same commit adds the "case error checks" its message promises: a new reorderArms pass that, given a case's arms and the constructor table, checks a constructor case against the actual data declaration it belongs to β€” not just parses, but validates β€” and reorders the arms into declaration order so dsExpr's Scott-encoding case compiler (chapter 02's O/P-combinator trick) always sees them in the order the runtime expects (0cc677d5:Desugar.hs lines 92–108, quoted whole):

reorderArms :: TypeTable -> [(EPat, Expr)] -> [(EPat, Expr)]
reorderArms _ [] = error "case has no arms"
reorderArms _ as@[(PTuple _, _)] = as
reorderArms tys as@((PConstr con _, _) : _) =
  let arms = [(c, a) | a@(PConstr c _, _) <- as] in
  if length arms /= length as then error "bad tuple pattern" else
  case M.lookup con tys of
    Nothing -> error $ "undefined constructor: " ++ show con
    Just [TypeDef _ cs] -> map arm cs
      where arm (c, k) =
              case lookup c arms of
                Nothing -> error $ "constructor missing: " ++ show (c, con)
                Just a@(PConstr _ vs, _) ->
                  if length vs == k then a else error $ "bad contructor arity: " ++ show a
                _ -> undefined
    Just _tds -> error $ "ambiguous constructor: " ++ show con
reorderArms _ _ = undefined

Six distinct failure modes in one 16-line function: an empty case, a mixed tuple/constructor pattern set, an unknown constructor, a constructor present in the data declaration but missing from the case, an arm whose pattern binds the wrong number of fields for that constructor's declared arity (misspelled in the source as "contructor," kept verbatim above), and a constructor name that's ambiguous across two imported types. None of these were checked before this commit β€” a case with a typo'd constructor name, or the wrong number of bound variables, either crashed the C runtime with an unhelpful message or silently ran into undefined behavior; after 0cc677d5, all six are caught in the desugarer, at compile time, in Haskell, with a message naming what's wrong.

The Prelude splits into Data.*-style modules

3a9c0edb ("Split up Prelude") and 92960261 ("More stuff in Prelude"), 17 and 26 minutes after 1136f265, break the single lib/Prelude.hs into one file per concern and re-export all of them through Prelude. By the end of 92960261, the module map is (92960261:lib/Prelude.hs, quoted whole):

module Prelude(
  module Control.Error,
  module Data.Bool,
  module Data.Either,
  module Data.Function,
  module Data.Int,
  module Data.List,
  module Data.Maybe,
  module Data.Tuple,
  module System.IO,
  module Text.String
  ) where
import Control.Error
import Data.Bool
import Data.Either
import Data.Function
import Data.Int
import Data.List
import Data.Maybe
import Data.Tuple
import System.IO
import Text.String

Ten modules, all under hierarchical Data.*/Control.*/System.*/ Text.* prefixes, most at the exact paths where the same names live in real Haskell's base package β€” Data.Bool, Data.Either, Data.Maybe, Data.Tuple for the small ADTs and their functions; Data.Function for id/./ flip; Data.Int for arithmetic and the (soon-to-be-identity) chr/ord pair; Data.List for the list type itself and its functions; System.IO for handles and IO primitives; and two Haskell-flavored names that aren't actually base modules, Text.String for string formatting and Control.Error for error and undefined. None of this is a new feature β€” every name that moves keeps working exactly as it did in the flat file β€” but it's the module system finally being exercised at the scale it was built for: real code, split across real files, glued back together by real imports.

Surface syntax catches up

178f43d0 ("Better 'let' in 'do'") lets a do-block's let bind more than one name at once β€” Let Ident Expr becomes Let [EDef], and pStmt's let parses a whole pBlock pDef instead of one name = expr pair β€” closing a gap the previous commit's own comment had flagged ("could be better").

1a0ac4c6 ("Add operator sections."), nine minutes later, adds (e op) and (op e) as expressions β€” left and right sections. A left section, (e op) (e.g. (5 <)), fixes e as the operator's first argument, so it's just op e applied to whatever comes next β€” a plain App. A right section, (op e) (e.g. (< 5)), needs the next argument to land in the operator's first position instead, with e staying fixed in the second β€” exactly what C (chapter 03's argument-flipping combinator, C f x y = f y x) is for (1a0ac4c6:Desugar.hs lines 107–110, quoted whole):

dsExpr syms tys (ESectL e op) =
  App (dsExpr syms tys (EVar op)) (dsExpr syms tys e)
dsExpr syms tys (ESectR op e) =
  App2 CC (dsExpr syms tys (EVar op)) (dsExpr syms tys e)

with the parser side one alternative each in pAExpr (1a0ac4c6:Parse.hs lines 311–312, quoted whole):

  <|> (ESectL <$> (pSym '(' *> pExprArg) <*> (pOper <* pSym ')'))
  <|> (ESectR <$> (pSym '(' *> pOper) <*> (pExprArg <* pSym ')'))

Then a two-day break (06-03 evening to 06-05 morning). The session resumes with d5bac600 ("Some compatibility fixes.") β€” a small, unglamorous commit: Flags' path field is renamed to paths throughout Compile.hs/Main.hs, eval.c's printrec switches an INT format string from %ld to %lld, and both Makefile build rules grow @mkdir -p bin so a clean checkout's missing bin/ directory doesn't fail the build β€” the kind of small friction a second sitting turns up immediately. Eleven minutes later comes if β€” was there really no if at all before this range? A search across the entire project history for EIf (the constructor a working if would need) turns up nothing before 1baaf7b6 β€” the commit is genuinely the first time if/then/else become parseable syntax anywhere in this project's git history, not just this chapter's range. Before it, a conditional could only be written as case cond of { True -> a; False -> b }, and Example.hs's own fac uses exactly that form right up until this commit rewrites it to if n <= 0 then 1 else n * fac(n-1). 1baaf7b6 ("Add 'if'"), 06-05 at 11:28:53, adds three new keywords (if/then/else, alongside the existing list β€” 1baaf7b6:Parse.hs lines 201–203, quoted whole):

keywords :: [String]
keywords = ["case", "data", "do", "else", "if", "import",
  "in", "let", "module", "of", "primitive", "then", "where"]

and a desugaring that reuses the same case-on-Bool trick the rewritten Example.hs had been spelling out by hand β€” if compiles to an application of the (Scott-encoded) condition to its else- and then- branches, in that order (1baaf7b6:Desugar.hs lines 111–112, quoted whole):

dsExpr syms tys (EIf e1 e2 e3) =
  App2 (dsExpr syms tys e1) (dsExpr syms tys e3) (dsExpr syms tys e2)

Nineteen minutes later, 0eb369f9 ("Add list comprehensions.") adds [e | q1, q2, ...] as new pAExpr syntax, reusing the exact same EStmt type do-notation already parses (Bind, Then, Let) for its qualifiers, and desugars each of the three qualifier kinds by recursion on the rest of the comprehension (0eb369f9:Desugar.hs lines 113–119, quoted whole):

dsExpr syms tys (ECompr e []) = dsExpr syms tys (EList [e])
dsExpr syms tys (ECompr e (Bind i b : ss)) =
  App2 (Var "Data.List.concatMap") (dsExpr syms tys (ELam [i] (ECompr e ss))) (dsExpr syms tys b)
dsExpr syms tys (ECompr e (Then c : ss)) =
  dsExpr syms tys (EIf c (ECompr e ss) (EList []))
dsExpr syms tys (ECompr e (Let d : ss)) =
  dsExpr syms tys (ELet d (ECompr e ss))

Four rules, each one line: no qualifiers left ([]) is a singleton list; a generator (Bind i b) becomes concatMap (\i -> rest) b β€” the hard-coded name "Data.List.concatMap", not a re-desugared EVar lookup, so this rule depends on Data.List (or something re-exporting concatMap under that exact qualified name) being in scope wherever a comprehension is used; a guard (Then c) becomes if c then rest else [], reusing 1baaf7b6's just-added if; and a let qualifier becomes an ordinary let wrapping the rest. [x*x | x <- xs, x > 2] is, by this recipe, concatMap (\x -> if x > 2 then [x*x] else []) xs β€” textbook comprehension desugaring, built from pieces (concatMap, if, let) that all already existed by the time this commit needed them.

41d6a7e8: getting rid of CHAR

The chapter's last commit, 06-07 at 14:13:56, deletes the runtime's dedicated character representation outright β€” completing what 2f89971e, 23 seconds earlier, had already started on the compiler side by deleting Exp's Chr constructor (see "Files reorganize" above). Before it, eval.c β€” living at src/runtime/eval.c since 34c8965e's move β€” has a CHAR node tag distinct from INT, a 'c literal syntax in the runtime's own combinator-file parser, and two primitives, ORD/CHR, that convert between the two tags. 41d6a7e8 removes all of it β€” CHAR disappears from the tag enum (compare the two states directly; 41d6a7e8~1:src/runtime/eval.c line 18 still has it, 41d6a7e8:src/runtime/eval.c line 18 doesn't):

enum node_tag { FREE, IND, AP, INT, HDL, S, K, I, B, C, T, Y, SS, BB, CC, P, O,

β€” along with the '\'' literal parser case, the evalchar function, the printrec/eval/evalio cases for CHAR/ORD/CHR, and evalstring's call through evalchar (replaced with a plain evalint plus a 0 <= c <= 127 range check). On the Haskell side, chr/ord β€” previously primitive "chr"/primitive "ord", calling into the now-deleted runtime primitives β€” become plain identity functions, because a Char and its Int ordinal are now, at the runtime level, literally the same representation (41d6a7e8:lib/Data/Int.hs lines 27–28, quoted whole):

chr x = x
ord x = x

What dies is a whole node tag and its associated primitives β€” real simplification, not a rename β€” and what makes it safe to delete is that nothing above the runtime actually needed Char to be its own tag: strings were already lists of something being printed as characters (chapter 03's EStr-to-EList desugaring), and once the runtime treats that "something" as a plain integer end to end, chr/ord have nothing left to do.

Why it matters

None of the individual pieces in this chapter are large. Qualified imports are a Bool field. as is a Maybe Ident. A required export list is one new production in pModule with exactly one export-item form implemented. Operator sections are two lines of desugaring each. List comprehensions are four one-line desugaring rules that lean on concatMap and if rather than inventing new machinery. What's notable is less any single commit and more what the set, taken together, is aimed at: the module system, the Prelude's shape, and the surface syntax all move toward looking like real Haskell in the same six days, not because completeness was the goal, but because a specific, concrete target sits a few weeks out β€” getting this compiler to eventually compile a real Haskell program, and eventually, itself, once it's written in Haskell rather than in the tiny dialect the runtime speaks. (The self-hosting push is this book's next chapter's story.) Every feature this chapter adds is one that real Haskell code written the ordinary way would use without a second thought β€” if, list comprehensions, qualified imports to avoid Prelude clashes, export lists to control what a module exposes β€” and nothing here is speculative: there's still no fixity declaration mechanism, no user-defined operators, no type classes, no selective export (only whole-module re-export). YAGNI cuts both ways in this sprint: build what real code will need soon, and nothing else yet.

Notebook margin

  • "Update docs." commits land right after the user-visible change they document, not batched at the end of a session: 51a56220 ("Update docs.") follows 92960261 (the Prelude split finishing) five minutes later; 263d2f87 ("Update docs") follows 1a0ac4c6 (operator sections) three minutes later.
  • File moves get their own commits, mostly separate from commits that change behavior β€” twice in this range, at two different scales. 16c75970/4f3b8f8d split lib/IO.hs/lib/List.hs into lib/System/IO.hs/lib/Data/List.hs in a clean delete-then-recreate pair, 47 seconds apart. 34c8965e/2f89971e do the same for the compiler's own six top-level .hs files and ParserComb.hs, moving them under src/MicroHs//src/Text/ β€” except this time the "moved files" commit isn't the very next commit (it's two calendar days and one unrelated commit, ac6f377c, later, and the repository genuinely has no compiler source tree in between), and it isn't purely a move either: 2f89971e smuggles in the brand-new, half-finished Translate.hs alongside the six restored files (see "Files reorganize"). The discipline is real but not absolute β€” worth knowing before trusting any commit title over its diff.
  • The rhythm across the whole range is sprint-then-gap at two nested scales: within the six working days, commits cluster tightly (22 in one afternoon on 06-03) and then jump a day (06-04, 06-06 both idle); across the whole book so far, this chapter's close is followed by the 24-day silence the overview's own timeline table calls out before chapter 07 resumes on 07-01.

Try it

Anchor: 0eb369f9 ("Add list comprehensions."), 2023-06-05 11:48:09 β€” chosen deliberately from before 34c8965e's file move, so the compiler sources this chapter's Build note patches are still at the top level, the same layout chapters 02–05 already build from. (Checking out anything between 34c8965e and 2f89971e instead would leave you with no Compile.hs/Desugar.hs/Exp.hs/Main.hs/Parse.hs/ ParserComb.hs to build at all β€” see "Files reorganize," above.) Convention (see 00-overview.md):

git worktree add /tmp/mhs-0eb369f9 0eb369f9
cd /tmp/mhs-0eb369f9

Build note: this commit's Makefile still builds bin/uhs from *.hs at the top level and bin/eval from eval.c, same shape as chapter 05's anchor. Building as written hits the same two GHC-9.8/ mtl gaps chapters 02–05 hit, unchanged in this range:

mkdir -p bin
nix develop $MICROHS -c ghc Main.hs -o bin/uhs

fails first with ParserComb.hs's ap-not-in-scope error; add, after ParserComb.hs's existing import Control.Monad.State.Strict:

import Control.Monad(ap)

then with Compile.hs's when-not-in-scope error (five call sites this time, Compile.hs having grown since chapter 05's anchor β€” all five are the same error, only the first is shown):

Compile.hs:33:7: error: [GHC-88464]
    Variable not in scope: when :: Bool -> a5 -> StateT Cache IO a6
    Suggested fix:
      Perhaps use data constructor β€˜Then’ (imported from Parse)
   |
33 |       when (nm `elem` ws) $
   |       ^^^^

add, after Compile.hs's existing import Control.Monad.State.Strict:

import Control.Monad(when)

With both one-line patches, the build succeeds (harmless -Wx-partial warnings about head/tail omitted):

[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 bin/uhs

Build the runtime the same way (one harmless -Wformat warning about %lld vs. value_t omitted):

nix develop $MICROHS -c gcc -Wall -O3 eval.c -o bin/eval

Every bin/uhs invocation below needs -ilib to find Prelude and the other library modules under lib/.

Exercise 1: export list, qualified import, and shadowing made visible

M1 exports everything via the only export-list form this commit's parser accepts (module M(module M) where β€” see "What happened," 1136f265), and defines double:

cat > M1.hs <<'EOF'
module M1(module M1) where
import Prelude

double :: Int -> Int
double x = x + x
EOF

M2 imports M1 qualified and defines its own double, a name that would otherwise collide:

cat > M2.hs <<'EOF'
module M2(module M2) where
import Prelude
import qualified M1

double :: Int -> Int
double x = x * 3

main = do
  print (double 5)
  print (M1.double 5)
EOF
nix develop $MICROHS -c ./bin/uhs -ilib M2
nix develop $MICROHS -c ./bin/eval

15
10

double 5 resolves to M2's own definition (5 * 3 = 15); M1.double 5 reaches the qualified-only import explicitly (5 + 5 = 10). The qualified keyword is what makes this shadowing safe: M1's double never enters the unqualified symbol table at all (155e9f5a's qns rule β€” qualified imports contribute only the dotted name), so there's nothing for M2's own double to collide with. Confirm the collision is real by dropping qualified and rebuilding the same program under a new name:

cat > M2plain.hs <<'EOF'
module M2plain(module M2plain) where
import Prelude
import M1

double :: Int -> Int
double x = x * 3

main = do
  print (double 5)
  print (M1.double 5)
EOF
nix develop $MICROHS -c ./bin/uhs -ilib M2plain

uhs: ambiguous: "double", [Var "M1.double",Var "M2plain.double"]
CallStack (from HasCallStack):
  error, called at ./Desugar.hs:73:17 in main:Desugar

Same two modules, same two names, and the only thing that changed is one keyword β€” 0cc677d5's scope-checking EVar case (see "What happened") is what raises this, the instant the unqualified double is looked up in M2plain.main and finds two candidates instead of one.

Exercise 2: a guarded list comprehension, desugared

cat > Compr.hs <<'EOF'
module Compr(module Compr) where
import Prelude

main = do
  putStrLn $ showList showInt [ x*x | x <- [1,2,3,4,5], x > 2 ]
EOF
nix develop $MICROHS -c ./bin/uhs -v -ilib Compr

The -v dump (chapter 05's verbosity flag) prints every compiled definition; grepping for Compr.main finds the one line this exercise cares about:

Compr.main = ((Data.Function.$ System.IO.putStrLn) ((Text.String.showList Text.String.showInt) ((Data.List.concatMap (($S (($C (($C Data.Int.>) 2)) $K)) ((($C' $O) (($S Data.Int.*) $I)) $K))) (($O 1) (($O 2) (($O 3) (($O 4) (($O 5) $K))))))))

Data.List.concatMap sitting right there as a Var reference β€” not bracket-abstracted away, because it's a call to a library function, not an inlined lambda β€” is 0eb369f9's Bind rule made visible: [x*x | x <- [1..5], x > 2] compiles through concatMap (\x -> ...) [1,2,3,4,5] exactly as the diff's second rule says. To isolate what the guard itself contributes, compile the same comprehension with the guard removed and diff the two compiled forms:

cat > ComprNoGuard.hs <<'EOF'
module ComprNoGuard(module ComprNoGuard) where
import Prelude

main = do
  putStrLn $ showList showInt [ x*x | x <- [1,2,3,4,5] ]
EOF
nix develop $MICROHS -c ./bin/uhs -v -ilib ComprNoGuard

ComprNoGuard.main = ((Data.Function.$ System.IO.putStrLn) ((Text.String.showList Text.String.showInt) ((Data.List.concatMap ((($C' $O) (($S Data.Int.*) $I)) $K)) (($O 1) (($O 2) (($O 3) (($O 4) (($O 5) $K))))))))

The no-guard body, ((($C' $O) (($S Data.Int.*) $I)) $K) β€” the compiled \x -> [x*x] β€” appears byte-for-byte inside the guarded version too, wrapped in one extra layer, $S (($C (($C Data.Int.>) 2)) $K) (...). That extra layer is 0eb369f9's third rule, if x > 2 then [x*x] else [], compiled: the guard adds exactly one wrapping combinator around the same lambda the ungated comprehension already produces, nothing more. Run it to confirm the values:

nix develop $MICROHS -c ./bin/eval

[9,16,25]

3^2, 4^2, 5^2 β€” 1 and 2 are filtered out by the x > 2 guard, as expected.

Exercise 3: the required export list, rejected

cat > NoExport.hs <<'EOF'
module NoExport where
import Prelude

main = putStrLn "hi"
EOF
nix develop $MICROHS -c ./bin/uhs -ilib NoExport

uhs: "NoExport.hs": line 1, col 16:
   found: "where"
   expeced: white-space
   expeced: '('

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

Column 16 is formatFailed's 0-based offset for the 16 characters already consumed, "module NoExport " β€” the position where starts at in module NoExport where. pModule (1136f265:Parse.hs, quoted in "What happened") requires a ( right after the module name, and there isn't one. The filename prefix on the error ("NoExport.hs":) is itself a small feature from earlier the same day: 2d818f30 ("Better error message.") threads the source filename through ParserComb.hs's formatFailed, so a failure in any imported module β€” not just the one named on the command line β€” says which file it came from.

Clean up:

git worktree remove --force /tmp/mhs-0eb369f9