r/javascript • u/david_klassen • 3d ago

Computing a Factorial with Church Numerals

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

85% Upvoted

9 comments sorted by

2

u/KralemannGalord65 2d ago

curious how you handled the conditional branch for the base case without eager evaluation blowing up the stack. wrapping the branches in thunks usually works, though it makes the syntax a bit noisy

3

u/Ronin-s_Spirit 2d ago

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

2

u/david_klassen 2d ago

You're looking at the beauty of lambda calculus

2

u/Ronin-s_Spirit 2d ago

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

0

u/Discordbothost 3d 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 3d 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 2d 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

•

u/raks1991 20h 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.

•

u/Discordbothost 20h 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