🌐 한국어로 읽기

04 — Talking to the world

Where we are

Chapter 03 leaves a language with let, infix operators, tuples, lists, strings, modules, and do-notation — including an IO module, IO.uhs, created by 95ff6a34 alongside Prelude.uhs and List.uhs. IO.uhs at that commit is nothing but a list of primitive declarations (95ff6a34:IO.uhs, quoted whole):

module IO where

(>>=)     = primitive "IO.>>="
(>>)      = primitive "IO.>>"
return    = primitive "IO.return"
readFile  = primitive "IO.readFile"
writeFile = primitive "IO.writeFile"
putChar   = primitive "IO.putChar"
getChar   = primitive "IO.getChar"

and because chapter 03's 693dc6ce made do-notation dispatch on whatever module supplies (>>=)/(>>) rather than on any built-in notion of "the IO monad", IO.do { putChar 'h'; putChar 'i' } parses, desugars, and compiles cleanly through every stage that exists so far — there is no type checker yet (chapter 03's e96d04be establishes that a :: signature is parsed and thrown away) to notice or care that IO is special. But compiling is not running. eval.c, unchanged since chapter 02, is still the old character-dispatch parser and reducer: its primitive table is a hardcoded switch over single characters ('+', '-', '*', '/', '%', '=', '!', '<', '>', '?') with no entry, and no mechanism for an entry, that could ever recognize a multi-character name like IO.>>=. Verified directly: building 834fd9ba (the range's first commit — still before monadic IO lands, see below) with the same one-line ap/when patches chapter 03's Build note uses, and running

module TestIO where
import Prelude
import IO

main = IO.do
  putChar 'h'
  putChar 'i'

compiles to a .comb file that literally contains the text IO.>>=, IO.putChar, and so on as bare, unprefixed identifiers (Prim, at this point, prints as its own raw string — the $-prefix convention that lets the runtime recognize a primitive reference doesn't exist yet either), and running that file crashes immediately:

$ nix develop $MICROHS -c ./eval out.comb
ERR: parse ')'

So "where we are" is precise: IO syntax, an IO module, and generic do-notation that happens to work with it are all already in place. The runtime underneath all of it is fictional — every IO primitive is a name with no meaning below the compiler. This chapter's first commit is the one that gives it a meaning.

What happened

3246e2a6: monadic IO, and what an IO value actually is

"Implement monadic IO." lands the evening of 2023-06-01, about four hours and forty minutes after 95ff6a34 closed chapter 03 — not an empty gap: 834fd9ba "Small improvements" and e2f3cf57 "More stuff" land earlier the same day (12:09 and 12:32), both unnarrated warm-ups that extend IO.uhs — one more primitive declaration (print) plus a first batch of derived helpers (mapM, mapM_, putStr, putStrLn) built on the existing primitives — still with no runtime behind any IO.* name. Two things happen in the same commit, and it's worth keeping them separate: eval.c gains a general mechanism for named primitives (not IO-specific), and on top of that mechanism, IO gets its first real implementation.

The general mechanism: the old NODEPTR combS, combK, ... roster of individually-named global variables is replaced by one table, an array of {name, tag, node} triples, quoted with elisions (3246e2a6:eval.c, lines 168–210):

struct {
  char *name;
  enum node_tag tag;
  NODEPTR node;
} primops[] = {
  /* combinators */
  { "S", S },
  { "K", K },
  ...
  { "O", O },
  /* primops */
  { "+", ADD },
  ...
  { "ord", ORD },
  { "IO.>>=", IO_BIND },
  { "IO.>>", IO_THEN },
  { "IO.return", IO_RETURN },
  { "IO.readFile", IO_READFILE },
  { "IO.writeFile", IO_WRITEFILE },
  { "IO.getChar", IO_GETCHAR },
  { "IO.putChar", IO_PUTCHAR },
  { "IO.print", IO_PRINT },
};

and the .comb-file parser's '+'/'-'/'?'/etc. single-character cases are replaced by one '$' case that reads an arbitrary name and looks it up (3246e2a6:eval.c, lines 365–381, quoted whole):

  case '$':
    /* A primitive, keep getting char's until end */
    for (int j = 0;;) {
      c = getc(f);
      if (c == ' ' || c == ')') {
        ungetc(c, f);
        buf[j] = 0;
        break;
      }
      buf[j++] = c;
    }
    for (int j = 0; j < sizeof primops / sizeof primops[0]; j++) {
      if (strcmp(primops[j].name, buf) == 0)
        return primops[j].node;
    }
    fprintf(stderr, "bad primop %s\n", buf);
    ERR("no primop");

Every combinator and primitive, IO or not, now goes through this one path — the $-prefix convention this chapter's transcripts show everywhere ($K, $IO.>>=, $chr, ...) is this commit's doing, and it is the piece of infrastructure that makes IO.>>= parseable at all, independent of what IO.>>= then does.

What it does is eight new enum node_tag values (3246e2a6:eval.c, lines 18–21, quoted whole):

enum node_tag { FREE, IND, AP, INT, CHAR, S, K, I, B, C, T, Y, SS, BB, CC, P, O,
                ADD, SUB, MUL, QUOT, REM, SUBR, EQ, NE, LT, LE, GT, GE, ERROR, CHR, ORD,
                IO_BIND, IO_THEN, IO_RETURN, IO_READFILE, IO_WRITEFILE, IO_GETCHAR, IO_PUTCHAR, IO_PRINT
};

An IO a value, at this commit and every later one in this chapter, is not a distinct runtime type — it is an ordinary graph node whose tag happens to be one of these eight. To the normal reduction loop, eval(), these tags are opaque, already-a-value tags exactly like INT or CHAR — the whole handling is one RET with no reduction rule (3246e2a6:eval.c, lines 769–777, quoted whole):

    case IO_BIND:
    case IO_THEN:
    case IO_RETURN:
    case IO_READFILE:
    case IO_WRITEFILE:
    case IO_GETCHAR:
    case IO_PUTCHAR:
    case IO_PRINT:
      RET;

Meaning lives entirely in a second interpreter, evalio, that main calls once on the whole program instead of the old evali+print pattern. evalio walks the same kind of graph eval does, but its switch gives these eight tags actual behavior — sequencing is spelled out directly as C control flow (3246e2a6:eval.c, lines 817–830):

    case IO_BIND:
      CHECKIO(2);
      GCCHECK(1);
      x = evalio(ARG(TOP(1)));  /* first argument, unwrapped */
      f = ARG(TOP(2));          /* second argument, the continuation */
      n = new_ap(f, x);
      POP(3);
      goto top;
    case IO_THEN:
      CHECKIO(2);
      (void)evalio(ARG(TOP(1))); /* first argument, unwrapped, ignored */
      n = ARG(TOP(2));          /* second argument, the continuation */
      POP(3);
      goto top;

IO_BIND (>>=) recursively runs its left computation to get an unwrapped result, applies the continuation to it, and loops (goto top) on whatever that produces — a genuine trampoline, not a recursive descent, so a long do-chain doesn't grow the C stack. IO_THEN (>>) is the same shape with the left result discarded. On the Haskell/compiler side there is no analogous "IO type" either: EDo's desugaring (chapter 03's 693dc6ce:Desugar.hs) turns M.do { x <- e; rest } into App2 (Var "M.>>=") e (Lam x rest) for any M, and by the time that reaches Exp.hs it's an ordinary Prim/Var node indistinguishable at the term level from + or error. "This is IO" is a fact known only to evalio's switch, nowhere else in the system — the same architecture that already ran nfib.

The same commit adds one more piece: a Let statement inside a do-block (M.do { let x = e; rest }), desugaring to a plain, non-recursive application, no different from chapter 03's expression-level let at that point (3246e2a6:Desugar.hs, line 54, quoted with its two neighbors for context):

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))
dsExpr (EDo n (Let  i e : ss)) = App  (Lam i $ dsExpr (EDo n ss)) (dsExpr e)

That line never changes for the rest of this chapter's range, even after fe22efbd (below) makes expression-level let unconditionally recursive — a let written inside a do-block stays simple, non-recursive sugar for a lambda application all the way through 8c5fbb1a. Two lets, spelled the same way, with different desugaring rules depending on which syntactic position they're in; nothing in this range unifies them.

And one honest gap, shipped anyway: IO_READFILE and IO_WRITEFILE are declared in the primop table, parseable, printable — and their evalio bodies are stubs (3246e2a6:eval.c, lines 836–841, quoted whole):

    case IO_READFILE:
      CHECKIO(1);
      ERR("IO_READFILE");
    case IO_WRITEFILE:
      CHECKIO(2);
      ERR("IO_WRITEFILE");

Console IO — getChar/putChar, hardcoded to stdin/stdout — works immediately in this commit. File IO is declared and left to crash on first use. 4c4229ec ("Fix bugs and improve.") and 7bb30b64 ("Minor improvements.") land later the same evening — 4c4229ec generalizes ELam to multi-argument lambdas and adds fix = primitive "Y" as a named Prelude function (a second, explicit route to the Y tag, alongside whatever let itself does — used immediately by List.uhs's new map/filter/foldr, each written as fix (\ rec arg -> ...) because plain recursive let doesn't exist as a language feature yet) — but neither commit touches IO_READFILE/IO_WRITEFILE. They stay broken until the next morning.

c5564e64: redo IO to allow files

Timestamps matter here: 3246e2a6 commits at 16:41 on 2023-06-01; c5564e64 commits at 09:38 the next day, 2023-06-02 — about seventeen hours, not "two days," and it's the very next work session, not a later return to old business. "Redo IO to allow files" isn't a bug fix to something that used to work; it's the first attempt to actually implement the two primitives that shipped as ERR() stubs.

The problem the flat-primitive design runs into: IO.readFile/ IO.writeFile as declared have no place to put an open file — there is no runtime representation for "a file that's been opened but not yet fully read or closed." c5564e64 adds one: a new node tag, HDL, whose payload is a raw C FILE * (c5564e64:eval.c, the union gains a FILE *file field addressed as HANDLE(p)), joining INT/CHAR as one more already-a-value tag the ordinary reducer just returns. Every IO primitive that used to assume stdin/stdout now takes an explicit handle argument — IO.getChar/IO.putChar/IO.print become hGetChar/hPutChar/hPrint, opening a file produces one of these handle nodes, and putChar/getChar/print survive as thin wrappers applying the h-prefixed primitive to a built-in stdin/stdout node (c5564e64:IO.uhs, quoted):

openFile :: FilePath -> IOMode -> IO Handle
openFile p m =
  let
    n = case m of
          ReadMode -> 0
          WriteMode -> 1
          AppendMode -> 2
          ReadWriteMode -> 3
  in  (primitive "IO.open") p n

putChar :: Char -> IO ()
putChar = hPutChar stdout

writeFile :: FilePath -> String -> IO ()
writeFile p s = IO.do
  h <- openFile p WriteMode
  hPutStr h s
  hClose h

writeFile is no longer a primitive at all — it's openFile + hPutStr (itself mapM_ (hPutChar h)) + hClose, three primitives composed in the Prelude rather than one primitive doing everything. IO_OPEN's C side needs a C string to hand to fopen, and the runtime has no string type — a String is a Scott-encoded cons-list of Char nodes, chapter 03's d91b9812/ddb1bb29 machinery, meaningful only by convention. c5564e64 adds evalstring, a new helper that walks that convention by hand, forcing each cons cell and copying its character into a fixed 10000-byte C buffer, with its own comment admitting the compromise (c5564e64:eval.c, quoted whole):

/* XXX this is cheating, should use continuations */
char *
evalstring(NODEPTR n)
{
  size_t sz = 10000;
  char *p, *name = malloc(sz);

  if (!name)
    ERR("evalstring malloc");
  for (p = name;;) {
    if (p >= name + sz)
      ERR("evalstring too long");
    n = evali(n);
    if (TAG(n) == K)
      break;
    else if (TAG(n) == AP && TAG(FUN(n)) == AP && TAG(FUN(FUN(n))) == O) {
      *p++ = evalchar(ARG(FUN(n)));
      n = ARG(n);
    } else {
      ERR("evalstring not Nil/Cons");
    }
  }
  *p = 0;
  return name;
}

A file path longer than 10000 characters is an ERR, not handled gracefully — a real, present limitation, left as-is. This is design-by-rewrite in miniature: the first cut declared a shape for file IO (readFile, writeFile, two primitives) without a representation underneath it, discovered that on first real use the next morning, and replaced the shape itself — handles as first-class values, every console/file operation parameterized over one — rather than patching around the gap. (readFile itself doesn't reappear until a3355632, "More functions.", later the same day, built from openFile + a new hGetContents that reads until IO.getChar returns a CHAR node holding -1 — getc's own EOF sentinel, stored and compared with nothing more than an Int equality check, ord c == negate 1; there is no distinct end-of-file representation anywhere in this system.)

fe22efbd: recursive let, and where the "was it recursive" question actually gets answered

Chapter 03's 5ccb1b2a desugars let as strictly sequential, non-recursive lambda application, with the comment "For now, just sequential bindings." fe22efbd ("Make let bindings recursive, and optimise the non-recursive case") makes good on that "for now" — every let-bound name, without exception, is now visible to its own right-hand side, via the fixed-point combinator (aux/y-combinator-and-recursion.md). The desugaring changes by inserting one Y per binding (fe22efbd:Desugar.hs, line 41):

      def (i, d) a = App (Lam i a) (App (Comb "Y") (Lam i d))

let i = d in a becomes (\i -> a) (Y (\i -> d)) — every binding, whether or not d actually mentions i. This is the aux doc's mechanism (Y f = f (Y f), one self-looped graph cell, case Y in eval.c) applied uniformly, which means a non-recursive let — the overwhelming common case — pays for a Y cell it doesn't need, unless something notices. The same commit adds exactly one more rule to Exp.hs's improveT, the post-compilation cleanup pass (fe22efbd:Exp.hs, lines 159–165, quoted whole):

improveT :: Exp -> Exp
improveT (App f a) =
  case (improveT f, improveT a) of
    (CK,                     CI) -> CT
    (CY,               App CK e) -> e
    (e1,                     e2) -> App e1 e2
improveT e = e

The interesting part is how "was d recursive" gets answered here — not by a free-variable scan over the surface syntax before desugaring, but for free, after the fact, from bracket abstraction's own smart constructors. Bracket-abstracting \i -> d when d doesn't mention i bottoms out in abstract's catch-all case, App CK d — and cS's existing rule from chapter 02 (cS (App CK e1) (App CK e2) = cK (App e1 e2)) means any closed subterm collapses to a single top-level K wrapper regardless of its internal shape. So a non-recursive binding's compiled form is always, mechanically, Y (K d') for some d' — and Y (K e) = K e (Y (K e)) = e by Y's own defining equation, one step, no cycle needed. improveT's new line recognizes exactly that shape and replaces it with e directly, so the runtime never builds the self-looped cell for a binding that never needed one — the recursive/ non-recursive distinction is discovered, not declared.

967b92c0: more data types, same combinators

967b92c0 ("More data types.") adds Maybe and Either to Prelude.uhs, plus showMaybe/showEither/showBool to String.uhs — and touches nothing else. (git show 967b92c0 --stat confirms: two .uhs files, zero lines of eval.c, Desugar.hs, or Exp.hs.) That's possible because the mechanism a data declaration compiles to hasn't changed since chapter 02, and this commit is a clean instance of it. Desugar.hs's handling, unchanged at this commit (967b92c0:Desugar.hs, lines 17–22, quoted whole):

dsDef (Data _ cs) = zipWith dsConstr [0..] cs
  where
    fs = [f i | (i, _) <- zip [0..] cs]
    dsConstr i (c, ts) = (c, lams xs $ lams fs $ apps (Var (f i)) (map Var xs))
      where xs = ["$x" ++ show (j::Int) | (j, _) <- zip [0..] ts]
    f i = "$f" ++ show (i::Int)

Each constructor at declaration-index i, with fields ts, compiles to a function of its own field values (xs) followed by one continuation per constructor of the type (fs, one $f0, $f1, ... per entry in cs) — which, once all of that is supplied, applies its own continuation, f i, to its own fields and ignores every other continuation entirely. data Maybe a = Nothing | Just a compiles Nothing to \$f0 $f1 -> $f0 and Just to \x $f0 $f1 -> $f1 x — a value of the type doesn't carry a tag to inspect; it is a dispatcher, waiting to be handed as many continuations as the type has constructors and calling exactly one of them. This is Scott encoding, the same trick chapter 02 used for hand-built tuple/list constructors and chapter 03's 8939d55b/d91b9812 reused for the tuple and list syntax — 967b92c0 is the first commit in this chapter's range to apply it to genuinely new user-facing sum types, and it costs nothing below Desugar.hs because the mechanism was already fully general. ECase's desugaring is the dual of this: it applies the scrutinee to its case arms' bodies, as continuations, in the order the arms are textually written — a fact dsDef's constructor-index numbering depends on silently matching (see Try It, Exercise 1, for what happens when it doesn't).

d2956ee8: optimizing Y better, and closing the aux doc's promise

fe22efbd's improveT rule catches Y (K e) — but only when that exact shape survives, structurally intact, all the way to the top of a fully bracket-abstracted term, because improveT is a separate pass that runs once, after compile finishes, pattern-matching on the finished term (compileOpt = improveT . compile). A let sitting inside an enclosing lambda — which is nearly every let in practice, a top-level function with even one parameter already being one lambda — doesn't reach improveT in that shape. The outer lambda's own bracket abstraction absorbs the inner Y (K e) and restructures it through cS/cB on the way to producing the outer function, and by the time that's finished, the term is B Y (B K e), not App CY (App CK e) — a shape improveT's one rule never matches, so the Y cell ships to the runtime unoptimized.

d2956ee8 ("Optimize Y better.") fixes this by moving the recognition into bracket abstraction's own machinery, so it fires bottom-up, during compilation, before the restructuring happens — one new line in cB, the smart constructor for the B combinator (d2956ee8:Exp.hs, lines 99–104, quoted whole):

cB :: Exp -> Exp -> Exp
cB CC          (App CC CI)    = CP -- Pair
cB (App CB CK) CP             = CO -- Cons
cB CY          (App2 CB CK e) = e  -- B Y (B K e) = e
cB CI          e              = e  -- B I e = e
cB e1          e2             = App2 CB e1 e2

Verified directly: compiling the identical program

module YOpt where
import Prelude
import IO

f :: Int -> Int
f x =
  let
    y = x + 1
   in y + y

main = print (f 10)

at 967b92c0 (before this optimization) and at d2956ee8 (after) gives two different compiled bodies for f:

967b92c0:  YOpt.f = B (S Prelude.+ I) (B Y (B K (Prelude.+ 1)))
d2956ee8:  YOpt.f = B (S Prelude.+ I) (Prelude.+ 1)

The Y is gone entirely in the second — not shrunk, eliminated — and both versions still run to the same answer, 22, with the d2956ee8 build doing it in fewer reductions (340 against 351 for the identical computation, both measured with ./eval's reduction counter). The non-recursive let inside f's body no longer costs a self-looped graph cell at runtime, regardless of how deeply it's nested under other lambdas — which is exactly what the aux doc, closing with "commit d2956ee8 ... revisits this implementation. What it changes is out of scope here; chapter 04 covers it.", promised. The same commit also migrates List.uhs's map/filter/foldr and IO.uhs's mapM_ from the explicit fix (\ rec arg -> ...) idiom 4c4229ec/c5564e64 had been using to plain let rec = ... in rec — the library code starts using the language feature the optimization just made free, in the same commit that made it free.

b1e84cf7 and 8c5fbb1a: serialization and deserialization

Main.hs's writeFile "out.comb" $ toStringP res (chapter 02/03's mechanism, unchanged) and eval.c's print/pp (used to echo a program before and after reduction) both already exist. IO.print (later renamed IO.serialize) is nothing more than wiring that same print function up as a runtime IO primitive — dump any live graph value, not just the whole compiled program at start-up, to a file handle, using the identical textual format ($name primitive references, :N/_N sharing labels). That wiring already existed before this chapter's range (IO.print/hPrint, c5564e64); what's new is making it survive contact with values that contain handles, and adding the reverse direction.

b1e84cf7 ("Handle serialization of standard handles.") fixes a narrow gap: before it, any HDL node reaching print's switch was an outright error (1a2f7b7a:eval.c, line 468: case HDL: ERR("Cannot serialize handles");). b1e84cf7 recognizes exactly the three well-known handles by C pointer identity and prints them as named primitives instead (b1e84cf7:eval.c, lines 483–492, quoted whole):

  case HDL:
    if (HANDLE(n) == stdin)
      fprintf(f, "$IO.stdin");
    else if (HANDLE(n) == stdout)
      fprintf(f, "$IO.stdout");
    else if (HANDLE(n) == stderr)
      fprintf(f, "$IO.stderr");
    else
      ERR("Cannot serialize handles");
    break;

Any freshly openFiled handle is still unserializable — the commit title says "standard handles," not "handles," and the code matches it exactly.

8c5fbb1a ("Add deserialization.") adds the reverse primitive, IO.deserialize, by calling parse() — the very function that reads the compiled .comb program at start-up — directly, on a live file handle, mid-run (8c5fbb1a:eval.c, lines 965–970, quoted whole):

    case IO_DESERIALIZE:
      CHECKIO(1);
      hdl = evalhandle(ARG(TOP(1)));
      gc();                     /* parser runs without GC */
      n = parse(hdl);
      RETIO(n);

What "serialize a running program's graph" means concretely, then, is: the exact same reader that bootstraps a program from its .comb file is reachable as a primitive from inside a running program, pointed at an arbitrary handle instead of the startup file. A value written with IO.serialize and read back with IO.deserialize round-trips through the same :N/_N label syntax chapter 02 established for whole-program linking — which, as Try It below shows directly, is also how a genuinely cyclic value survives the trip: :N/_N isn't just an optimization for repeated subterms, it's the only way this text format can express a graph that loops back on itself at all.

But parse()'s :/_ cases both read and write through one global, NODEPTR *shared, and that global is allocated, zeroed, and then freed — once, at start-up, by the function that reads the compiled program (8c5fbb1a:eval.c, lines 447–456, quoted whole):

NODEPTR
parse_top(FILE *f)
{
  shared = malloc(heap_size * sizeof(NODEPTR));
  for(int i = 0; i < heap_size; i++)
    shared[i] = NIL;
  NODEPTR n = parse(f);
  free(shared);
  return n;
}

IO_DESERIALIZE calls parse() directly, not parse_top() — it never reallocates shared, so it's dereferencing memory that was freed before main ever started running evalio. Deserializing a value with no :/_ labels at all (nothing shared, nothing cyclic) never touches shared[] and works fine; deserializing anything that does use a label — including every cyclic value, unavoidably — is a use-after-free. Verified directly (Try It, Exercise 3): it segfaults, consistently, every time.

Three more commits land the same day and are chapter 05's story, not this one's: ef082bbe/8c66d4dd/c0fb9a91 add independent -v verbosity flags to both uhs (the compiler) and eval (the runtime), and b0915dcf moves the library .uhs modules into a lib/ subdirectory and adds a -i<dir> module search path — both show up mechanically in Try It below (eval needs -v to print its reduction-count trailer at all now; uhs needs -ilib to find Prelude/List/IO/String), without being this chapter's subject.

Why it matters

Every extension in this chapter lands on the architecture chapters 01–03 already built, without changing that architecture's shape. An IO a is not a new kind of runtime value — it's a graph node with one of eight new tags, opaque to the ordinary reducer, meaningful only to a second small interpreter (evalio) layered on top of the same graph. A Maybe/Either value is not a new kind of runtime value either — it's the same Scott-encoding trick chapter 02 already generalized for tuples and lists, applied to two more sum types with zero lines of eval.c changed (967b92c0's diff is Prelude.uhs and String.uhs, nothing else). "More combinators, plus (for IO specifically) one more small interpreter that gives some of those combinators meaning" absorbs both features without touching the core loop eval() that's been running since chapter 01's ccb31388.

Redoing IO seventeen hours after shipping it is what design-by-rewrite looks like when it's working as intended: the first cut declared file IO as two primitives (readFile, writeFile) it hadn't yet figured out how to back with a real representation, shipped it anyway with ERR() stubs rather than pretending it worked, and the very next session — once files were actually needed — replaced the shape of the design (flat primitives with an implicit stdin/stdout) with one that had a place to put an open file (HDL nodes, every primitive taking an explicit handle) rather than patching the old shape into working. And d2956ee8's optimization is the same lesson at smaller scale: fe22efbd shipped a correct but naive recursive let (Y around every binding, no exceptions) with one narrow-scope cleanup already in place; d2956ee8, in the same sitting that generalized the cleanup, immediately went and rewrote List.uhs/IO.uhs's own fix (\ rec -> ...) idioms to plain recursive let — proof, in the same commit, that the newly-cheap feature was trusted enough to replace the manual workaround it was cheap enough to obsolete.

Notebook margin

• 4c4229ec ("Fix bugs and improve.") and 7bb30b64 ("Minor improvements.") land the same evening as 3246e2a6, about forty-four minutes and about an hour later respectively — ELam generalized to multi-argument lambdas, fix = primitive "Y" added as a named function, print/pp refactored to share a printrec helper. Neither touches the IO_READFILE/IO_WRITEFILE stubs; those wait for the next morning's c5564e64.
• 8b39ba55 ("Remove junk.") deletes Lam.hs outright — all 233 lines of it, the entire hand-embedded-Haskell prototype dating to ccb31388 (touched only lightly since, by two commits, 6485a341 and a9178695) that aux/y-combinator-and-recursion.md and chapters 01–02 walked through, superseded since chapter 03's 95ff6a34/b25d9fc8 gave the parser-driven Main.hs a real Prelude to replace it with. It's its own commit, not bundled with any feature — cleanup gets to be first-class work, done once there's enough of it to be worth doing.
• do-block let (3246e2a6) and expression let (5ccb1b2a, fe22efbd) are spelled identically but desugar differently for the rest of this chapter's range: only the expression form goes through fe22efbd's unconditional Y-wrap-then-optimize; a let written inside M.do { ... } stays the original, simple, non-recursive lambda application all the way through 8c5fbb1a. Nothing in this range unifies the two.
• a3355632's readFile has no distinct end-of-file value — hGetChar hands back whatever raw getc() returned, including -1 at EOF, packed into an ordinary CHAR node, and hGetContents stops when ord c == negate 1. The C convention leaks straight through.

Try it

Anchor: 8c5fbb1a ("Add deserialization."). Convention (see 00-overview.md):

git worktree add /tmp/mhs-8c5fbb1a 8c5fbb1a
cd /tmp/mhs-8c5fbb1a

Build note: this commit's Makefile finally has a Main: target (ghc Main.hs -o Main, added by 3246e2a6), but it's still a bare ghc invocation and hits the same GHC-9.8/mtl issues chapters 02 and 03's Build notes cover, so build by hand with -o uhs to keep the binary name consistent with earlier chapters:

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

fails first with ParserComb.hs's ap-not-in-scope error (same as chapters 02/03); 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 (same as chapter 03); 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):

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

Build the runtime the same way chapters 02/03 do:

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

Two more things are new to this commit's range and matter for every command below. b0915dcf moved Prelude.uhs/List.uhs/IO.uhs/ String.uhs into a lib/ subdirectory and added a -i<dir> module search path (Compile.hs's path field) — every ./uhs invocation below passes -ilib so import Prelude/import IO/etc. resolve. And ef082bbe/8c66d4dd/c0fb9a91 gated eval's own diagnostic trailer (node size=..., N reductions, M GCs) behind a -v flag that didn't exist in chapters 02/03 — by default ./eval now prints only the program's own output, nothing else; pass -v (as ./eval -v out.comb) to see reduction counts.

Exercise 1: read a file, transform it, print the result

printf 'hello world\nfrom a file\n' > greeting.txt

cat > Shout.uhs <<'EOF'
module Shout where
import Prelude
import List
import IO

upc :: Char -> Char
upc c =
  case (ord c >= ord 'a') && (ord c <= ord 'z') of
    True  -> chr (ord c - 32)
    False -> c

main = IO.do
  s <- readFile "greeting.txt"
  putStr (map upc s)
EOF
nix develop $MICROHS -c ./uhs -ilib Shout
nix develop $MICROHS -c ./eval out.comb

hello world�from a file�

Not what was wanted, and not a typo above — a genuine dead end. upc's case writes its arms True first, False second, but Prelude.uhs declares data Bool = False | True, making False the constructor at index 0 and True the constructor at index 1. Per "What happened" above (967b92c0), dsExpr (ECase e as) = apps (dsExpr e) (map dsArm as) applies the scrutinee to its arms' compiled bodies positionally, in the order they're written — nothing checks that written order against declaration order. Writing True first means the first continuation supplied is the one meant for True, but a Bool value returns its declaration-index-0 continuation (False's) first — so every character, whatever upc's condition actually evaluates to, runs the arm written first. Every space (ord ' ' = 32) got chr (32 - 32) = the NUL byte; every newline (ord '\n' = 10) got chr (10 - 32) = byte 0xEA — visibly wrong once printed, confirmed with od:

$ nix develop $MICROHS -c ./eval out.comb | od -An -tx1 | head -1
 68 65 6c 6c 6f 00 77 6f 72 6c 64 ea 66 72 6f 6d

Swap the arms to match Bool's actual declaration order — False first, True second — and rebuild:

cat > Shout.uhs <<'EOF'
module Shout where
import Prelude
import List
import IO

upc :: Char -> Char
upc c =
  case (ord c >= ord 'a') && (ord c <= ord 'z') of
    False -> c
    True  -> chr (ord c - 32)

main = IO.do
  s <- readFile "greeting.txt"
  putStr (map upc s)
EOF
nix develop $MICROHS -c ./uhs -ilib Shout
nix develop $MICROHS -c ./eval out.comb

HELLO WORLD
FROM A FILE

Exercise 2: read the sharing labels out of out.comb

Exercise 1's out.comb (the corrected version) is 2792 bytes, one line, 81 top-level definitions (Prelude, List, IO, and Shout linked together). Its opening (byte-exact, ... eliding everything after the fourth definition):

(($T :0 (($B $K) (($B $K) $K))) (($T :1 ($K (($B $K) $K))) (($T :2 ($K ($K $K))) (($T :3 ($K ($K $T))) (($T :4 $IO.>>=) ...

:0 through :3 and :4 ($IO.>>=) are top-level definitions in source-module-linking order — exactly chapter 02's 17587b2d label scheme, unchanged. A concrete back-reference, from further into the same file:

... (($T :16 (_7 _13)) (($T :17 (_8 _12)) (($T :18 (_9 _13)) ...

:16 (which turns out to be IO.putChar's stdout-bound wrapper, i.e. putChar) is defined as _7 _13 — a reference to definition 7 (IO.putChar) applied to a reference to definition 13 (IO.stdout), reusing their labels rather than repeating their bodies.

It's worth being precise about what kind of "sharing" this is, because this chapter also produces a different kind. Every one of these :N labels is assigned unconditionally, one per top-level definition, by Main.hs itself (def ((_, e), i) r = App2 CT (Lbl i (subst e)) r, iterating zip ds' [0..] over every definition whether or not anything else ever references it) — a static, positional scheme, decided at compile time from source order. Contrast that with what the runtime's own IO.serialize produces, which uses find_sharing's two-pass graph walk (mark on first visit, promote to shared on second) to label only nodes actually visited more than once while printing a live value — dynamically, from the graph's actual shape, nothing to do with source order. A plain list with no repeated substructure gets no labels at all:

cat > PlainSer.uhs <<'EOF'
module PlainSer where
import Prelude
import List
import IO

main = IO.do
  writeSerialized "plain.ser" [1, 2, 3]
  v <- readSerialized "plain.ser"
  print v
EOF
nix develop $MICROHS -c ./uhs -ilib PlainSer
nix develop $MICROHS -c ./eval out.comb
echo "exit: $?"
cat plain.ser

(($O 1) (($O 2) (($O 3) $K)))
exit: 0
(($O 1) (($O 2) (($O 3) $K)))

(the run exits cleanly, and both the runtime's own printed result and the file content are the same text, $O/$K all the way down, no :/_ anywhere.) Reusing the same let-bound list twice, so the traversal that writes it actually visits one node more than once, does produce a label:

cat > ShareDemo.uhs <<'EOF'
module ShareDemo where
import Prelude
import List
import IO

main = IO.do
  let
    xs = [1, 2, 3]
   in writeSerialized "share.ser" (xs, xs)
EOF
nix develop $MICROHS -c ./uhs -ilib ShareDemo
nix develop $MICROHS -c ./eval out.comb
cat share.ser

(($P :99474 (($O 1) (($O 2) (($O 3) $K)))) ($I _99474))

One label, :99474 (a heap-cell index, hence the large arbitrary number — nothing like the small sequential :0/:1/... Main.hs assigns), marking the list xs the first time the pair's traversal reaches it; _99474 the second time, because both halves of (xs, xs) are the same heap cell (one let-bound thunk, used twice), not two equal-looking copies.

Exercise 3: tie a knot

take exists as of 72d4d093 (List.uhs), so a cyclic list can be observed through a finite prefix:

cat > Knot.uhs <<'EOF'
module Knot where
import Prelude
import List
import String
import IO

main = IO.do
  let
    xs = 1 : xs
   in putStrLn (showList showInt (take 5 xs))
EOF
nix develop $MICROHS -c ./uhs -ilib Knot
nix develop $MICROHS -c ./eval out.comb

[1,1,1,1,1]

fe22efbd's unconditional Y-wrap applies to any let, not just function definitions — xs = 1 : xs builds a genuinely self-looped graph cell the same way nfib's Y does in aux/y-combinator-and-recursion.md, and take 5 walks five steps into it and stops, never noticing the list has no end. Serializing xs directly (not through take, the whole infinite structure) shows the cycle in the label syntax itself:

cat > KnotSer.uhs <<'EOF'
module KnotSer where
import Prelude
import List
import IO

main = IO.do
  let
    xs = 1 : xs
   in writeSerialized "knot.ser" xs
EOF
nix develop $MICROHS -c ./uhs -ilib KnotSer
nix develop $MICROHS -c ./eval out.comb
cat knot.ser

:99731 (($O 1) _99731)

This terminates — find_sharing's mark-based traversal handles a cyclic graph the same way eval.c's garbage collector always has, stopping at nodes it's already visited rather than following AP pointers forever — and the result says exactly what the graph is: definition :99731 is the cons cell (O 1 _99731), and _99731 inside it refers back to the very node being defined. Not two equal cons cells; one cell, pointing at itself.

Reading it back is where this commit's range runs out of runway. Deserializing this exact file segfaults:

cat > KnotRead.uhs <<'EOF'
module KnotRead where
import Prelude
import List
import String
import IO

main = IO.do
  ys <- readSerialized "knot.ser"
  putStrLn (showList showInt (take 5 ys))
EOF
nix develop $MICROHS -c ./uhs -ilib KnotRead
nix develop $MICROHS -c ./eval out.comb
echo "exit: $?"

exit: 139

(139 = 128 + SIGSEGV.) Per "What happened" above, this isn't specific to cycles — it's any use of the :/_ label syntax at all. IO_DESERIALIZE calls parse() directly, and parse()'s :/_ cases read and write the global shared pointer that parse_top() allocated once, at start-up, and already free()d before evalio ever ran. Confirmed by trying the non-cyclic share.ser from Exercise 2 the same way — one shared node, no cycle, same crash:

cat > ShareRead.uhs <<'EOF'
module ShareRead where
import Prelude
import List
import IO

main = IO.do
  v <- readSerialized "share.ser"
  print v
EOF
nix develop $MICROHS -c ./uhs -ilib ShareRead
nix develop $MICROHS -c ./eval out.comb
echo "exit: $?"

exit: 139

versus the earlier, un-shared [1,2,3] value from writeSerialized (no :/_ in its file at all — see Exercise 2), which deserializes without incident. At 8c5fbb1a, IO.serialize can write a genuine cycle to a file and IO.deserialize exists as a primitive — but reading anything that actually needs the label mechanism back crashes the runtime, every time, reproducibly. That is the real, current state of this feature at this commit, not a hypothetical.

Clean up:

git worktree remove --force /tmp/mhs-8c5fbb1a