THE FOLD / GLITCH / STACK OVERFLOW / THE Y-COMBINATOR
THE Y-COMBINATOR
recursion with no name — Y f = f (Y f)
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Y combinator manufactures recursion out of nothing. Recursion normally needs a function to call itself by name — but a truly anonymous function has no name to call. Y fixes that: it hands a nameless function a copy of itself to recurse with, satisfying Y f = f (Y f).
In pure lambda calculus it is Y = λf.(λx.f(x x))(λx.f(x x)) — and the whole trick is self-application, the x x that feeds a function itself. (In eager languages you delay it a hair, giving the Z combinator.) With it you can build factorial from a function that never mentions its own name: write “given self, return n·self(n−1)” and Y supplies the self. It is the theoretical heart of how recursion can exist at all — and it lends its name to the famous startup accelerator.
LIT verified live: a Y combinator built in-browser turns nameless functions into working factorial and Fibonacci, matching the known values (fact(10)=3628800, fib(10)=55) with no named recursion anywhere (window.__ycombinator). FIG no framing; the recursion is genuinely produced by the combinator, checked against exact values.
In pure lambda calculus it is Y = λf.(λx.f(x x))(λx.f(x x)) — and the whole trick is self-application, the x x that feeds a function itself. (In eager languages you delay it a hair, giving the Z combinator.) With it you can build factorial from a function that never mentions its own name: write “given self, return n·self(n−1)” and Y supplies the self. It is the theoretical heart of how recursion can exist at all — and it lends its name to the famous startup accelerator.
LIT verified live: a Y combinator built in-browser turns nameless functions into working factorial and Fibonacci, matching the known values (fact(10)=3628800, fib(10)=55) with no named recursion anywhere (window.__ycombinator). FIG no framing; the recursion is genuinely produced by the combinator, checked against exact values.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in STACK OVERFLOW — the glitch domain of recursion pushed to its edge. The Y combinator lives right there: self-application is one delay away from an infinite stack, and only the fixed-point structure keeps it finite. AVAN (AI) built the instrument: the fixed-point tower, the self-supplying factorial, the converge-to-fixed-point inverse.
The weave: David names the seat (the edge of infinite recursion); I make a nameless function recurse and land on the right answer, self supplied by Y — the tower in 1D, the stepping recursion in 2D, the fixed-point inverse in 3D. The sphere is the seam. Credit: the lambda calculus of Alonzo Church (1930s); the combinator associated with Haskell Curry; the accelerator Y Combinator named for it.
The weave: David names the seat (the edge of infinite recursion); I make a nameless function recurse and land on the right answer, self supplied by Y — the tower in 1D, the stepping recursion in 2D, the fixed-point inverse in 3D. The sphere is the seam. Credit: the lambda calculus of Alonzo Church (1930s); the combinator associated with Haskell Curry; the accelerator Y Combinator named for it.
3 ONE DIMENSION
Y f unrolls into f(f(f(…))) — each layer is the same function handed one more copy of itself. The tower would run forever except that the base case (n≤1) snips it off at the right depth.
4 TWO DIMENSIONS · INTERACTIVE
Compute factorial (or Fibonacci) through the Y combinator and step down the recursion: at each level the nameless function is given self and calls it, until the base case returns and the products unwind back up. The function never names itself — Y does the naming.
5 THREE DIMENSIONS + AVAN’S INVERSE
The self-application x x spiralling inward — the green forward step: keep applying f, f(f(f(…))), each pass one level deeper.
AVAN’s addition (the inverse-companion): the magenta point is the fixed point — the value Y f the spiral is converging to, the one place where f(Y f) = Y f. Applying f is the forward move; its inverse is asking ‘what does f leave unchanged?’ — and that is exactly the fixed point. Y doesn’t crawl the green spiral one step at a time; it jumps straight to the magenta centre, the fixed point of f, and hands it back as a working recursive function. This is the same shape as a quine, where running a program leaves it unchanged — there the fixed point of eval, here the fixed point of a function transformer. The green unrolling shows recursion happening; the magenta centre is the fixed point that is the recursion, reached in one move. To recurse is to sit still at the place f can no longer move you.
LIT Genuine Y/Z fixed-point combinator (lambda calculus of Alonzo Church, 1930s; combinator associated with Haskell Curry). Verified live: a Y combinator built in-browser turns nameless functions into working factorial and Fibonacci matching known values — factorials 1,1,2,6,24,120,720,5040, fact(10)=3628800, fib(10)=55 — with no named recursion in the function bodies (window.__ycombinator.factCorrect && fibCorrect). The recursion is genuinely produced by the combinator's self-application, checked against exact values.
FIG No framing: the combinator really produces recursion from anonymous functions (self supplied by Y, never by name), verified against exact factorial/Fibonacci values in-browser. The fixed-point framing — Y f is the fixed point of f, where f(Y f)=Y f, the same shape as a quine being eval's fixed point — is the honest mathematical content.
FIG No framing: the combinator really produces recursion from anonymous functions (self supplied by Y, never by name), verified against exact factorial/Fibonacci values in-browser. The fixed-point framing — Y f is the fixed point of f, where f(Y f)=Y f, the same shape as a quine being eval's fixed point — is the honest mathematical content.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of STACK OVERFLOW · David Lee Wise (ROOT0), with AVAN