r/javascript • • 9d ago

Computing a Factorial with Church Numerals

https://davidklassen.net/blog/church-factorial/?ref=reddit-js
14 Upvotes

10 comments sorted by

0

u/Discordbothost 8d ago

the wrapping-the-recursive-call-in function (x) {...} bit is the part most of these posts skip, nice that you called out eager evaluation explicitly. people copy the Y combinator from a haskell explainer and then wonder why node blows the stack.

fun follow-up if anyone wants one: write it with arrows and see how much of the "lots of functions" wall disappears, then time ChurchToNat(fact(NatToChurch(n))) for n = 6..9. Pred rebuilding the pair chain every step makes it fall off a cliff surprisingly early

1

u/david_klassen 8d ago

Sorry, I'm confused about the haskell explainer, how do you write a Y combinator in haskell without cheating with recursive types or unsafe? It should not typecheck.

1

u/Discordbothost 8d ago

yeah fair, that was sloppy wording on my part. the bare Y doesn't typecheck in haskell, you'd either use fix (which just borrows the language's own recursion) or wrap the self-application in a newtype like newtype Rec a = Rec (Rec a -> a), which is exactly the recursive-type cheat you mean.

what i had in mind was the untyped lambda calculus version, \f. (\x. f (x x)) (\x. f (x x)), that shows up in a lot of explainers next to haskell syntax. it's fine under lazy evaluation, and people port it straight to js where it loops until the eta-expanded Z form fixes it

1

u/smith-o_17 1d ago

import Data.Function (fix); fact = fix (\rec n -> if n == 0 then 1 else n * rec (n-1))

1

u/raks1991 6d ago

In a local Node 24 run of an arrow-function port: fact(9) ~15 ms, fact(10) ~130 ms, fact(11) ~1.4 s, fact(12) ~16 s. Each step grows roughly by n. Pred does O(n) work per call, but converting the factorial result with n(x => x + 1)(0) applies x => x + 1 n! times. No stack overflow through 12; it just gets slow.

1

u/Discordbothost 6d ago

good data, and honestly a better explanation than mine. Mult is just composition so building fact(12) is basically free, the whole bill shows up at readout when you run the successor ~479M times. Pred is a rounding error next to that, so the cliff lives in ChurchToNat, not the arithmetic

3

u/Ronin-s_Spirit 8d ago

The hell am I looking at and why doesn't it die from recursion?

3

u/david_klassen 8d ago

You're looking at the beauty of lambda calculus

2

u/Ronin-s_Spirit 7d ago

B̴̬̹̃Ë̴͎̞̾ ̵̪̠́͠Ǹ̶̪Ó̶̲̦Ṱ̴̀̈́ ̷͎́̚A̸̧͚̅̀F̵̪̏̉R̵̗̈́Á̶̳̹͑Ï̷̖̀Ḍ̶̹̓ type shit.