🌐 한국어로 읽기

Background for chapter 01.

The Y combinator and recursion

bracket-abstraction.md eliminates every Lam in a term. But nfib calls itself — how does a self-call survive translation into a language that, after compile, has no names left at all?

1. No names, no self-reference

abstract (see bracket-abstraction.md section

1. only knows how to eliminate a bound variable from a term that contains it. A recursive definition like nfib n = ... nfib ... isn't naturally expressible this way: nfib isn't a parameter of anything — it's the name being defined, referring to itself, inside its own body. Once compile has erased Var/Lam, there is no environment and no name table at runtime (see lambda-calculus-and-ski.md section 3) for a name to even refer through. Combinator terms are closed by construction; something else has to supply the self-reference.

2. Y f = f (Y f), and what the reduction actually builds

The standard trick is the fixed-point combinator Y: Y f is defined to behave exactly like f (Y f) — apply f to "the very recursive value we're building." Turn nfib's body into an ordinary (non-recursive) function that takes its own recursive callee as an extra argument, nfibF = \nfib n -> ..., and Y nfibF is a value equal to nfibF (Y nfibF) — feed nfibF a copy of itself to call.

ccb31388:eval.c's reduction rule for Y (lines 429–437):

    case Y:
      CHECK(1);
      f = ARG(TOP(1));
      POP(1);
      n = TOP(0);
      FUN(n) = f;
      ARG(n) = n;
      GOTO ap;
      break;

n here is TOP(0) — the outermost cell of the redex, i.e. the AP(Y, f) node for Y f itself (compare case S in graph-reduction-and-laziness.md section 2, same pattern: read the argument, then reuse the outer cell as the answer). The rewrite sets FUN(n) = f and, critically, ARG(n) = n — the node's own argument field is set to point at itself. This is not "call Y f again to get another copy of f (Y f)" — it is one cell, mutated in place, that is now literally AP(f, n) where n is the very node holding that AP. Follow ARG from n and you arrive back at n. The graph for Y f is genuinely cyclic: a single self-referencing application cell, built once, with no bound on how many times it can be "unfolded" because unfolding it just means re-entering the same cell.

GOTO ap restarts the spine walk from n, now f (Y f) — exactly the fixed-point equation, but as a graph identity rather than a rewrite that has to be repeated. If f's body demands its second argument again deeper inside (the recursive call site), it dereferences the same self-looped cell n and finds it — by then — either still the same AP(f, n) (if the recursion hasn't been forced further) or already reduced further along the same self-link. Either way, f itself was fetched once and is never copied; only the spine around the self-reference grows as reduction proceeds.

3. eNfib: the recursive definition, and where Y enters it

ccb31388:Lam.hs (lines 193–194):

fix :: Exp -> Exp
fix e = App CY e

fix is nothing but "wrap in Y" — CY is the Comb "Y" pattern synonym (ccb31388:Lam.hs, line 72: pattern CY = Comb "Y"), and App CY e is the term Y e. eNfib (line 225):

eNfib = fix $ comp $ \ nfib n -> iF (n .< 2) 1 (nfib $$ (n-1) + nfib $$ (n-2) + 1)

\nfib n -> ... is the non-recursive nfibF from section 2, written with Haskell's own lambda syntax and turned into an Exp by the ToLam machinery (comp = improve . compile . toLam, line 219 — see bracket-abstraction.md for compile/improve). nfib $$ (n-1) and nfib $$ (n-2) are the two recursive calls, both against the parameter nfib, not a self-reference by name. fix applies Y to the whole compiled function, so eNfib = Y nfibF — and every occurrence of nfib inside the body ends up, after compile, referring to whatever Y's self-looped cell (section 2) resolves to when demanded. That compiled term, printed by ./eval nfib.comb before reduction, has Y right where the derivation predicts — wrapping the whole recursive function, applied to 35:

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

(This is the same printed term bracket-abstraction.md section 4 already quotes as the running example of improve's output; the Y at the front is the part this doc is about.)

4. Recursion as sharing

Section 2's self-looped cell is the same in-place-update mechanism graph-reduction-and-laziness.md describes for ordinary combinators (S, K, I) — Y's reduction just uses it to point a cell at itself instead of at some other existing node. Every recursive call in a running nfib reuses the one f pointer case Y fetched at the start; nothing about f's code (its compiled combinator graph) is ever duplicated per call. Only the argument spine — the chain of pending n-1/n-2 applications — grows as recursion descends, and each of those is built and torn down by ordinary AP reduction, exactly as in the rest of the graph.

5. Verified: ./eval nfib.comb prints 29860703

$ cd /tmp/mhs-ccb31388 && nix develop $MICROHS -c make test
./eval nfib.comb
((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 35)
29860703
node size=24, heap size=100000
1045124618 reductions, 1944 GCs

29860703 is nfib 35 — matching every earlier task's known-good result for this commit. The run also confirms graph-reduction-and-laziness.md's claim that GC is real and exercised, not just present in the source: 1944 GCs actually fired over the course of this one computation.

6. What changes later

This Y — one self-looped cell, reduced by case Y exactly as shown above — is what the first commit does. It is not the last word: commit d2956ee8, "Optimize Y better." (2023-06-02), revisits this implementation. What it changes is out of scope here; chapter 04 covers it.