THE FOLD / CO-OP / THE PUSH / THE CHURCH ROSSER
THE CHURCH ROSSER
any order, one answer
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
In the lambda calculus there is usually more than one thing you could reduce next, and no rule says which. The Church–Rosser theorem says it does not matter: if two different reduction orders both finish, they finish at the same term, up to renaming. This is why a functional program has a meaning independent of its evaluation strategy, and why a compiler may reorder work without being asked. What the theorem does not say is that every order finishes — and that gap is where real language design happens.
LIT verified live with a working reducer: five terms reduced under both leftmost-outermost and rightmost-innermost order reach identical normal forms — S K K → I in 4 steps either way, PLUS 2 3 → 5 in 6, MULT 3 4 → 12 in 9, (λx.x x)(λy.y) → I in 2. And on K A Ω the two orders come apart exactly as the theorem permits: normal order terminates at A, applicative order is still reducing at the 3,000-step cutoff.
LIT verified live with a working reducer: five terms reduced under both leftmost-outermost and rightmost-innermost order reach identical normal forms — S K K → I in 4 steps either way, PLUS 2 3 → 5 in 6, MULT 3 4 → 12 in 9, (λx.x x)(λy.y) → I in 2. And on K A Ω the two orders come apart exactly as the theorem permits: normal order terminates at A, applicative order is still reducing at the 3,000-step cutoff.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at THE PUSH: everyone reduces in whatever order they like and the merge is identical every time.
AVAN (AI) implemented capture-avoiding substitution with fresh-name generation rather than the naive version, because naive substitution silently produces wrong answers on exactly the terms that make this theorem interesting — the ones where a bound variable would be captured. A reducer that gets that wrong will still report “both strategies agree,” because both will be equally wrong, and the page would pass its own test while demonstrating nothing. The K A Ω case is included deliberately: it is the standing counterexample to the misreading that confluence guarantees termination, and it also explains why Haskell can return a value where a strict language diverges. Church and Rosser proved this in 1936.
AVAN (AI) implemented capture-avoiding substitution with fresh-name generation rather than the naive version, because naive substitution silently produces wrong answers on exactly the terms that make this theorem interesting — the ones where a bound variable would be captured. A reducer that gets that wrong will still report “both strategies agree,” because both will be equally wrong, and the page would pass its own test while demonstrating nothing. The K A Ω case is included deliberately: it is the standing counterexample to the misreading that confluence guarantees termination, and it also explains why Haskell can return a value where a strict language diverges. Church and Rosser proved this in 1936.
3 ONE DIMENSION
Five terms, two strategies, one destination each.
4 TWO DIMENSIONS · INTERACTIVE
Step a term down two different paths and watch them meet.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: two reduction paths diverging and rejoining.
AVAN’s addition (the inverse-companion): the forward reading is “order does not matter.” The inverse is that confluence is what makes the word “value” mean anything, and it had to be earned. Before it, a term does not have an answer — it has a set of possible futures, and calling any of them the result would be a choice. The theorem collapses that set to at most one point, and only then can a program be said to compute something rather than to do something. Read backwards, Church–Rosser is not a convenience for optimisers; it is the proof that there was a fact to optimise toward, and the Ω case is the reminder that the fact can still be out of reach.
LIT with a working reducer, five terms reduced under both leftmost-outermost and rightmost-innermost order reach identical normal forms - S K K -> I in 4 steps either way, PLUS 2 3 -> 5 in 6, MULT 3 4 -> 12 in 9, (lx.x x)(ly.y) -> I in 2; and on K A OMEGA the two orders come apart exactly as the theorem permits, normal order terminating at A while applicative order is still reducing at the 3,000-step cutoff
FIG CAPTURE-AVOIDING substitution with fresh-name generation was implemented rather than the naive version, because naive substitution silently produces wrong answers on exactly the terms that make this theorem interesting - the ones where a bound variable would be captured. A reducer that gets that wrong still reports 'both strategies agree', because both are equally wrong, and the page would pass its own test while demonstrating nothing. The K A OMEGA case is the standing counterexample to the misreading that confluence guarantees termination, and it explains why Haskell returns a value where a strict language diverges. Church and Rosser, 1936.
FIG CAPTURE-AVOIDING substitution with fresh-name generation was implemented rather than the naive version, because naive substitution silently produces wrong answers on exactly the terms that make this theorem interesting - the ones where a bound variable would be captured. A reducer that gets that wrong still reports 'both strategies agree', because both are equally wrong, and the page would pass its own test while demonstrating nothing. The K A OMEGA case is the standing counterexample to the misreading that confluence guarantees termination, and it explains why Haskell returns a value where a strict language diverges. Church and Rosser, 1936.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PUSH · David Lee Wise (ROOT0), with AVAN