Dit artikel bespreekt de implementatie van de Y-combinator (de "Sage Bird") binnen de programmeertaal sw-MLPL. De kern van het probleem is dat sw-MLPL een eager (strict) evaluator gebruikt, waardoor de klassieke Y-combinator onmiddellijk divergeert door oneindige recursie.
Om dit op te lossen, introduceert de auteur de applicatieve Sage (de Z-combinator), die gebruikmaakt van named partials om de evaluatie te vertragen en zo een veilig vast punt te creëren. Het artikel vergelijkt deze benadering met de APL-stamboom (zoals Dyalog, BQN en J), waar recursie vaak wordt opgelost via ingebouwde primitieven of vaste-punt-iteratie over arrays, waardoor externe combinatoren minder noodzakelijk zijn.
De auteur pleit ervoor om sw-MLPL eager te houden voor voorspelbaarheid en biedt een concreet stappenplan om recursie zonder benoemde functies te implementeren via een body-functie en de applicatieve Sage.
Rabbit-hole #6: De Sage Bird — Y-combinatoren in een Eager Array-taal
Bronnen
- Run the birds live: mlpl.softwarewrighter.com — Load Demo… > Array / APL > Combinators (the birds)
- Het boek: To Mock a Mockingbird — Raymond Smullyans volière van combinator-vogels, in de vorm van puzzels.
- Sage, CLI-side:
sw-ml-study/demo-combinators — lessen 17 (fixedpoints), src/fixedpoints.mlpl, en de derived-combinators documentatie.
De vogel
In Raymond Smullyans To Mock a Mockingbird zijn de combinatoren vernoemd naar zangvogels. De Sage is de vogel van het vaste punt: voor elke functie $f$ produceert de Sage een waarde $x$ waarvoor geldt dat $f(x) = x$. Compositie levert dit gratis op:
Sage = B M L = Bluebird . Mockingbird . Lark = λf. (λx. f (x x)) (λx. f (x x))
Die laatste regel is de Y-combinator in zijn klassieke vorm en voldoet exact aan de recursieve vergelijking: $Y f = f (Y f)$. Als je er een "body" voor een faculteit aan voert die zijn eigen recursie als argument aanneemt, geeft de Sage die body terug aan zichzelf, volledig bewapend — recursie zonder naam, zonder toewijzing en zonder def.
De kern van de volière
In sw-MLPL is elke vogel een gewone def — geen lambda-syntaxis, geen speciale mechanismen; de naam van Smullyan is de notatie. De meest voorkomende groep is als volgt (deze tabel is bewust onvolledig; demo-combinators bevat ook de Dove, Eagle, Phoenix, Lark, Owl en de rest van de volière):
| Vogel | $\lambda$-term | Wat het doet | sw-MLPL |
|---|
| Identity | $\lambda x.x$ | geeft argument ongewijzigd terug | def u:I(x) { x } |
| Kestrel | $\lambda x y.x$ | constante: houdt $x$ vast, negeert $y$ — staging | def u:K(x, y) { x } |
| Thrush | $\lambda x y.y x$ | past de gewachte functie toe op de bewaarde waarde | def u:T(x, y) { call(y, x) } |
| Mockingbird | $\lambda x.x x$ | zelf-applicatie | def u:M(x) { call(x, x) } |
| Bluebird | $\lambda x y z.x (y z)$ | compositie | def u:B(x, y, z) { call(x, call(y, z)) } |
| Cardinal | $\lambda x y z.x z y$ | wisselt de laatste twee argumenten om | def u:C(x, y, z) { call(call(x, z), y) } |
| Warbler | $\lambda x y.x y y$ | duplicatie | def u:W(x, y) { call(call(x, y), y) } |
| Starling | $\lambda x y z.x z (y z)$ | de S van de S-K basis: alles afleidbaar uit S en K | def u:S(x, y, z) { call(call(x, z), call(y, z)) } |
| Sage | $\lambda f.(\lambda x.f (x x)) (\lambda x.f (x x))$ | het vaste punt — het onderwerp van dit artikel | call(:u:bluebird, :u:mockingbird, :u:lark) — gebouwd, nooit geforceerd; zie hieronder |
Het addertje onder het gras: eagerness
Er is een reden waarom dit artikel kort is en de les voorzichtig. sw-MLPL is een eager taal. De klassieke Sage divergeert onmiddellijk wanneer hij op iets wordt toegepast: het construeren van $(\lambda x. f (x x)) (\lambda x. f (x x))$ vereist $x x$ voordat $f$ überhaupt wordt aangeroepen, wat opnieuw $x x$ vereist, tot in het oneindige. Daarom definieert demo-combinators/src/fixed_points.mlpl de klassieke Sage als call(:u:bluebird, :u:mockingbird, :u:lark) en forceert deze bewust nooit. In docs/derived-combinators.md wordt dit genoteerd als een stoppunt, niet als een omissie.
De oplossing is degene die elke strict taal herontdekt: vertraag de zelf-applicatie achter één laag abstractie. In sw-MLPL is die vertraging een named partial — een unaire functie die de evaluator niet zal aanroepen totdat er een waarde wordt gegeven:
def u:applicative_sage(builder) {
"Return the eager-safe fixed point of builder.";
step = call(:u:z_step, builder);
call(step, step)
}
Dit is de Z-combinator in een vogelkostuum, en deze werkt. Les 17 bouwt faculteit en fibonacci als vaste punten van hun builder-functies — factorial(6) en fibonacci(8) geven de correcte antwoorden zonder dat er ergens in de scope een recursieve naam voorkomt.
Wat de APL-stamboom anders doet
De APL-familie omzeilt het probleem op twee manieren. Ten eerste is anonieme zelf-referentie een primitief van de taal: een Dyalog dfn roept zichzelf aan met $\nabla$ ({0=⍵:1 ⋄ ⍵×∇ ⍵-1} is faculteit zonder naam), BQN-blokken hebben $\mathbb{S}$, en q heeft .z.s. Het vaste punt is ingebouwd in de functiesemantiek, waardoor Y nooit nodig is voor praktische recursie.
Ten tweede lost de array-stijl de meeste recursie volledig op: de power-limit conjunction ^: van J past een verb toe totdat het resultaat stopt met veranderen (transitieve afsluiting is +./ .^: y), waardoor vastpunt-iteratie een operator wordt. sw-MLPL heeft geen van beide, wat precies de reden is waarom het APL2-idiomen vlak — het eerbetoon aan die stamboom — het bestand is dat als eerste een vaste-puntcombinator nodig had.
Moet sw-MLPL overstappen van eager naar lazy?
Nee — sw-MLPL moet eager blijven — en de redenering is kort. Het draaien van de klassieke Sage vereist lazy evaluation: $Y f = f (Y f)$ termineert alleen als de innerlijke $Y f$ niet wordt geëvalueerd totdat iemand deze daadwerkelijk nodig heeft. Strictness is een kenmerk van de APL-stamboom — voorspelbare kosten, een eenvoudige evaluator — en één vogel is geen reden om dat op te geven. Voor praktische recursie ontbreekt er niets: benoemde defs refereren al naar zichzelf via hun naam, wat precies is hoe APL\360 en APL2 het doen.
Bovendien heeft APL2 zelf geen lambda's. Anonieme functies zijn een innovatie van Dyalog (dfns), en elke taal die ze adopteerde, moest een zelf-referentie-token toevoegen — $\nabla$ in Dyalog, $\mathbb{S}$ in BQN, $: in J, .z.s in q — omdat een lambda recursie niet oplost, maar juist het probleem creëert dat APL nooit had. Benoemde defs plus first-class function values is het APL2-ontwerp, met opzet. Als er ooit iets wordt toegevoegd, dan is de richting die trouw is aan de stamboom vastpunt-iteratie over arrays — J's ^:_ of Dyalog's <0xE2><0x8D><0xA3>≡, het toepassen van een verb totdat het resultaat stopt met veranderen — en niet lambda-syntaxis.
Vandaag een Sage draaien, zonder iets te wijzigen
De klassieke vogel sterft omdat sw-MLPL elke envelop opent op het moment dat deze arriveert — hij eist $x x$ voordat hij vraagt waarom. Geef hem dus geen envelop, maar een telefoonnummer. Een named partial is een functiewaarde die wacht om aangeroepen te worden, en die ene tel wachten is precies de vertraging die het vaste punt nodig heeft. Drie stappen, die allemaal vandaag al worden ondersteund:
- Schrijf een body die zijn recursie als argument ontvangt. De body noemt zichzelf nooit; degene die hem aanroept levert de "ik" aan:
``sw-mlpl def u:fact_body(rec, n) { if gt(n, 1) { n * call(rec, n - 1) } else { 1 } } ``
- Knoop de verbinding met de applicatieve Sage. Kopieer
zrecur, zstep en applicativesage letterlijk uit src/fixedpoints.mlpl — of de eenregelige u:fix uit apl2-idioms.mlpl als een benoemde helper acceptabel is:
``sw-mlpl def u:applicativesage(builder) { step = call(:u:zstep, builder); call(step, step) } ``
- Roep het aan.
``sw-mlpl fact = u:applicativesage(:u:factbody) call(fact, 6) # 720, zonder recursieve naam in de scope ``
Les 17 voert exact dit uit — factorial(6) en fibonacci(8) — dus de infrastructuur is gecontroleerd voordat je erop vertrouwt. De body blijft puur, de mechaniek bestaat uit drie kleine defs, en de taal blijft strict.
Waar het te vinden is
demo-combinators/src/fixed_points.mlpl — de klassieke Sage (niet geforceerd) en de applicatieve Sage (geforceerd), met faculteit- en fibonacci-bodies.demo-combinators/lessons/17-sage-fixed-points.mlpl — de uitvoerbare les.sw-mlpl/docs/apl2-idioms.mlpl — u:fix, dezelfde knoop gelegd in het APL2-idiomen vlak, eindigend in call(call(:u:fix, :u:fact_body), 5).
Eén regel door een AI geschreven commentaar is in dat laatste bestand overgebleven, en die is correct: de startup-accelerator genaamd Y Combinator is naar dit principe vernoemd.
Rabbit-hole #6: De Sage Bird — Y-combinatoren in een Eager Array-taal
Bronnen
- Run the birds live: mlpl.softwarewrighter.com — Load Demo… > Array / APL > Combinators (the birds)
- Het boek: To Mock a Mockingbird — Raymond Smullyans volière van combinator-vogels, in de vorm van puzzels.
- Sage, CLI-side:
sw-ml-study/demo-combinators — lessen 17 (fixedpoints), src/fixedpoints.mlpl, en de derived-combinators documentatie.
De vogel
In Raymond Smullyans To Mock a Mockingbird zijn de combinatoren vernoemd naar zangvogels. De Sage is de vogel van het vaste punt: voor elke functie $f$ produceert de Sage een waarde $x$ waarvoor geldt dat $f(x) = x$. Compositie levert dit gratis op:
Sage = B M L = Bluebird . Mockingbird . Lark = λf. (λx. f (x x)) (λx. f (x x))
Die laatste regel is de Y-combinator in zijn klassieke vorm en voldoet exact aan de recursieve vergelijking: $Y f = f (Y f)$. Als je er een "body" voor een faculteit aan voert die zijn eigen recursie als argument aanneemt, geeft de Sage die body terug aan zichzelf, volledig bewapend — recursie zonder naam, zonder toewijzing en zonder def.
De kern van de volière
In sw-MLPL is elke vogel een gewone def — geen lambda-syntaxis, geen speciale mechanismen; de naam van Smullyan is de notatie. De meest voorkomende groep is als volgt (deze tabel is bewust onvolledig; demo-combinators bevat ook de Dove, Eagle, Phoenix, Lark, Owl en de rest van de volière):
| Vogel | $\lambda$-term | Wat het doet | sw-MLPL |
|---|
| Identity | $\lambda x.x$ | geeft argument ongewijzigd terug | def u:I(x) { x } |
| Kestrel | $\lambda x y.x$ | constante: houdt $x$ vast, negeert $y$ — staging | def u:K(x, y) { x } |
| Thrush | $\lambda x y.y x$ | past de gewachte functie toe op de bewaarde waarde | def u:T(x, y) { call(y, x) } |
| Mockingbird | $\lambda x.x x$ | zelf-applicatie | def u:M(x) { call(x, x) } |
| Bluebird | $\lambda x y z.x (y z)$ | compositie | def u:B(x, y, z) { call(x, call(y, z)) } |
| Cardinal | $\lambda x y z.x z y$ | wisselt de laatste twee argumenten om | def u:C(x, y, z) { call(call(x, z), y) } |
| Warbler | $\lambda x y.x y y$ | duplicatie | def u:W(x, y) { call(call(x, y), y) } |
| Starling | $\lambda x y z.x z (y z)$ | de S van de S-K basis: alles afleidbaar uit S en K | def u:S(x, y, z) { call(call(x, z), call(y, z)) } |
| Sage | $\lambda f.(\lambda x.f (x x)) (\lambda x.f (x x))$ | het vaste punt — het onderwerp van dit artikel | call(:u:bluebird, :u:mockingbird, :u:lark) — gebouwd, nooit geforceerd; zie hieronder |
Het addertje onder het gras: eagerness
Er is een reden waarom dit artikel kort is en de les voorzichtig. sw-MLPL is een eager taal. De klassieke Sage divergeert onmiddellijk wanneer hij op iets wordt toegepast: het construeren van $(\lambda x. f (x x)) (\lambda x. f (x x))$ vereist $x x$ voordat $f$ überhaupt wordt aangeroepen, wat opnieuw $x x$ vereist, tot in het oneindige. Daarom definieert demo-combinators/src/fixed_points.mlpl de klassieke Sage als call(:u:bluebird, :u:mockingbird, :u:lark) en forceert deze bewust nooit. In docs/derived-combinators.md wordt dit genoteerd als een stoppunt, niet als een omissie.
De oplossing is degene die elke strict taal herontdekt: vertraag de zelf-applicatie achter één laag abstractie. In sw-MLPL is die vertraging een named partial — een unaire functie die de evaluator niet zal aanroepen totdat er een waarde wordt gegeven:
def u:applicative_sage(builder) {
"Return the eager-safe fixed point of builder.";
step = call(:u:z_step, builder);
call(step, step)
}
Dit is de Z-combinator in een vogelkostuum, en deze werkt. Les 17 bouwt faculteit en fibonacci als vaste punten van hun builder-functies — factorial(6) en fibonacci(8) geven de correcte antwoorden zonder dat er ergens in de scope een recursieve naam voorkomt.
Wat de APL-stamboom anders doet
De APL-familie omzeilt het probleem op twee manieren. Ten eerste is anonieme zelf-referentie een primitief van de taal: een Dyalog dfn roept zichzelf aan met $\nabla$ ({0=⍵:1 ⋄ ⍵×∇ ⍵-1} is faculteit zonder naam), BQN-blokken hebben $\mathbb{S}$, en q heeft .z.s. Het vaste punt is ingebouwd in de functiesemantiek, waardoor Y nooit nodig is voor praktische recursie.
Ten tweede lost de array-stijl de meeste recursie volledig op: de power-limit conjunction ^: van J past een verb toe totdat het resultaat stopt met veranderen (transitieve afsluiting is +./ .^: y), waardoor vastpunt-iteratie een operator wordt. sw-MLPL heeft geen van beide, wat precies de reden is waarom het APL2-idiomen vlak — het eerbetoon aan die stamboom — het bestand is dat als eerste een vaste-puntcombinator nodig had.
Moet sw-MLPL overstappen van eager naar lazy?
Nee — sw-MLPL moet eager blijven — en de redenering is kort. Het draaien van de klassieke Sage vereist lazy evaluation: $Y f = f (Y f)$ termineert alleen als de innerlijke $Y f$ niet wordt geëvalueerd totdat iemand deze daadwerkelijk nodig heeft. Strictness is een kenmerk van de APL-stamboom — voorspelbare kosten, een eenvoudige evaluator — en één vogel is geen reden om dat op te geven. Voor praktische recursie ontbreekt er niets: benoemde defs refereren al naar zichzelf via hun naam, wat precies is hoe APL\360 en APL2 het doen.
Bovendien heeft APL2 zelf geen lambda's. Anonieme functies zijn een innovatie van Dyalog (dfns), en elke taal die ze adopteerde, moest een zelf-referentie-token toevoegen — $\nabla$ in Dyalog, $\mathbb{S}$ in BQN, $: in J, .z.s in q — omdat een lambda recursie niet oplost, maar juist het probleem creëert dat APL nooit had. Benoemde defs plus first-class function values is het APL2-ontwerp, met opzet. Als er ooit iets wordt toegevoegd, dan is de richting die trouw is aan de stamboom vastpunt-iteratie over arrays — J's ^:_ of Dyalog's <0xE2><0x8D><0xA3>≡, het toepassen van een verb totdat het resultaat stopt met veranderen — en niet lambda-syntaxis.
Vandaag een Sage draaien, zonder iets te wijzigen
De klassieke vogel sterft omdat sw-MLPL elke envelop opent op het moment dat deze arriveert — hij eist $x x$ voordat hij vraagt waarom. Geef hem dus geen envelop, maar een telefoonnummer. Een named partial is een functiewaarde die wacht om aangeroepen te worden, en die ene tel wachten is precies de vertraging die het vaste punt nodig heeft. Drie stappen, die allemaal vandaag al worden ondersteund:
- Schrijf een body die zijn recursie als argument ontvangt. De body noemt zichzelf nooit; degene die hem aanroept levert de "ik" aan:
``sw-mlpl def u:fact_body(rec, n) { if gt(n, 1) { n * call(rec, n - 1) } else { 1 } } ``
- Knoop de verbinding met de applicatieve Sage. Kopieer
zrecur, zstep en applicativesage letterlijk uit src/fixedpoints.mlpl — of de eenregelige u:fix uit apl2-idioms.mlpl als een benoemde helper acceptabel is:
``sw-mlpl def u:applicativesage(builder) { step = call(:u:zstep, builder); call(step, step) } ``
- Roep het aan.
``sw-mlpl fact = u:applicativesage(:u:factbody) call(fact, 6) # 720, zonder recursieve naam in de scope ``
Les 17 voert exact dit uit — factorial(6) en fibonacci(8) — dus de infrastructuur is gecontroleerd voordat je erop vertrouwt. De body blijft puur, de mechaniek bestaat uit drie kleine defs, en de taal blijft strict.
Waar het te vinden is
demo-combinators/src/fixed_points.mlpl — de klassieke Sage (niet geforceerd) en de applicatieve Sage (geforceerd), met faculteit- en fibonacci-bodies.demo-combinators/lessons/17-sage-fixed-points.mlpl — de uitvoerbare les.sw-mlpl/docs/apl2-idioms.mlpl — u:fix, dezelfde knoop gelegd in het APL2-idiomen vlak, eindigend in call(call(:u:fix, :u:fact_body), 5).
Eén regel door een AI geschreven commentaar is in dat laatste bestand overgebleven, en die is correct: de startup-accelerator genaamd Y Combinator is naar dit principe vernoemd.
Groetjes,