// HACKER NEWS — CYBERSECURITY
Show HN: Combinators in Array Languages
Prior to this post, searching this site for “Y combinator” turned up nothing. The search engine was innocent: no post had ever covered it, despite the fact that the repos have carried working fixed-point combinators since August. This short post closes the gap.
Raymond Smullyan’s To Mock a Mockingbird names the combinators after songbirds, and the Sage is the fixed-point bird: for any function f, the Sage produces a value x with f(x) = x. Composition gives it for free:
That last line is the Y combinator in its classical form, and it satisfies exactly the recursive equation: Y f = f (Y f). Feed it a factorial “body” that takes its own recursion as an argument, and the Sage hands that body back to itself, fully armed — recursion without a name, no assignment, no def.
In sw-MLPL every bird is an ordinary def — no lambda syntax, no special machinery; the Smullyan name is the notation. The most common flock (this table is deliberately incomplete; demo-combinators houses the Dove, Eagle, Phoenix, Lark, Owl and the rest of the aviary):
There is a reason this post is short and the lesson is careful. sw-MLPL is an eager language. The classical Sage, applied to anything, diverges immediately: constructing (λx. f (x x)) (λx. f (x x)) demands x x before f is ever called, which demands x x, forever. demo-combinators/src/fixed_points.mlpl therefore defines the classical Sage as call(:u:bluebird, :u:mockingbird, :u:lark) and deliberately never forces it. docs/derived-combinators.md records this as a stopping point, not an oversight.
The fix is the one every strict language rediscovers: delay the self-application behind one layer of abstraction. In sw-MLPL the delay is a named partial — a unary function the evaluator will not call until given a value:
This is the Z combinator wearing a bird costume, and it runs. Lesson 17 builds factorial and fibonacci as fixed points of their builder functions — factorial(6) and fibonacci(8) return correct answers with no recursive name anywhere in scope.
The APL family sidesteps the problem twice. Anonymous self-reference is a language primitive: a Dyalog dfn calls itself with ∇ ({0=⍵:1 ⋄ ⍵×∇ ⍵-1} is factorial with no name), BQN blocks have 𝕊, q has .z.s — the fixed point is built into function semantics, and Y is never needed for practical recursion. And the array style dissolves most recursion entirely: J’s power-limit conjunction ^:_ applies a verb until its result stops changing (transitive closure is +./ .^:_ y), promoting fixpoint iteration to an operator. sw-MLPL has neither, which is exactly why the APL2-idioms plane — the homage to that lineage — is the file that had to reach for a fixed-point combinator in the first place.
No — sw-MLPL should stay eager — and the reasoning is short. Running the classical Sage requires lazy evaluation: Y f = f (Y f) terminates only if the inner Y f is not evaluated until someone actually needs it. Strictness is a feature of the APL lineage — predictable cost, a simple evaluator — and one bird is not a reason to trade it away. For practical recursion nothing is missing: named defs already self-reference by name, which is exactly how APL\360 and APL2 do it.
And APL2 itself has no lambdas. Anonymous functions are a Dyalog innovation (dfns), and every language that adopted them had to add a self-reference token to go with them — ∇ in Dyalog, 𝕊 in BQN, $: in J, .z.s in q — because a lambda does not solve recursion, it creates the problem APL never had. Named defs plus first-class function values is the APL2 design, on purpose. If anything ever gets added, the lineage-faithful direction is fixpoint iteration over arrays — J’s ^:_ or Dyalog’s ⍣≡, apply a verb until the result stops changing — not lambda syntax.