How to write a Y-combinator implementation in javascript that does not exceed maximum stack size

Question

TL;DR:

Why applying a javascript implementation of a factorial function with a lazy Y combinator fails with "Maximum call stack size exceeded"?

Here is the code:

// LAZY_Y = λf.(λx.f(λy.xxy))(λx.f(λy.xxy))
const LAZY_Y = (f) => ((x) => f((y) => x(x)(y)))((x) => f((y) => x(x)(y)));
// λf.λn.IF (ISZERO n) ONE (MULTIPLY n f(PREDECESSOR n))
const ALMOST_FACTORIAL = (f) => (n) =>
 IF(ISZERO(n))(ONE)(MULTIPLY(n)(f(PREDECESSOR(n))));
const FACTORIAL = LAZY_Y(ALMOST_FACTORIAL);
const res = FACTORIAL(ONE); // Maximum call stack size exceeded

Long version of the question giving more context:

I am trying to learn and understand lambda calculus as a software engineer. That's why I am validating my understanding by implementing (and running) every concept and structure in javascript. Everything has been going smoothly so far until I reached the Y-combinator.

I have been following this very-well written article https://mvanier.livejournal.com/2897.html on the Y-combinator, which uses Scheme for the actual implementation of the concepts in code.

There the author first defines a Y (not a combinator yet) that is itself recursive:

(define Y
 (lambda (f)
 (f (Y f))))

or my implementation in js:

const RECURSIVE_Y = (f) => f(RECURSIVE_Y(f));

As explained, using this to define a recursive function (e.g. factorial) would work in a lazy-evaluated language, but not in a strict one. And that makes perfect sense, as the very definition of a recursive function would be an endless series of nested functions:

(Y f)
= (f (Y f))
= (f (f (Y f)))
= (f (f (f (Y f)))) ...

Then, the article continues with a definition of Y (not a combinator) that should work fine with strict languages:

(define Y
 (lambda (f)
 (f (lambda (x) ((Y f) x)))))

or, again, in js:

const LAZY_RECURSIVE_Y = (f) => f((x) => LAZY_RECURSIVE_Y(f)(x))

This is where the issue is: while the definition of FACTORIAL itself now does not create an infinite loop, the actual application of it still does:

const FACTORIAL = LAZY_RECURSIVE_Y(ALMOST_FACTORIAL);
const res = FACTORIAL(ONE); // Maximum call stack size exceeded

What am I missing here? I tried to implement the actual Y combinator and it's lazy version, just in case those recursive functions are not really equivalent:

// Y = λf.(λx.f(xx))(λx.f(xx))
const Y = (f) => ((x) => f(x(x)))((x) => f(x(x)));
// LAZY_Y = λf.(λx.f(λy.xxy))(λx.f(λy.xxy))
const LAZY_Y = (f) => ((x) => f((y) => x(x)(y)))((x) => f((y) => x(x)(y)));

but still, they fail the exact same way.

What is even weirder is that defining an almost_factorial that uses regular javascript does work with LAZY_RECURSIVE_Y:

const non_lambda_almost_factorial = (f) => (n) => n === 0 ? 1 : n * f(n - 1);
const FACTORIAL = LAZY_RECURSIVE_Y(non_lambda_almost_factorial);
const res = FACTORIAL(4); // this works

But on the other hand, manually defining "factorials-that-work-up-until-number-x" does work with my OG, Lambda almost-factorial definition:

const FACTORIAL0 = ALMOST_FACTORIAL(IDENTITY);
const FACTORIAL1 = ALMOST_FACTORIAL(FACTORIAL0);
const FACTORIAL2 = ALMOST_FACTORIAL(FACTORIAL1);
const FACTORIAL3 = ALMOST_FACTORIAL(FACTORIAL2);
FACTORIAL3(THREE); // this works

I have created a codesandbox here where you can see all the definitions, including those of TRUE, FALSE, IF, ISZERO, churchNumerals, MULTIPLY and PREDECESSOR, although they have been tested separately and work as expected:

What is wrong in my understanding of either the way a Y-combinator works and what it does or of how to implement it in JS?

Answer 1

I want to document my resolution here in case anyone ever goes down the same rabbit hole as me.

As it turns out, the issue is with the lambda IF expression in a strict language. In hindsight, this should have been obvious based on the fact that the non_lambda_almost_factorial worked, while the lambda one didn't.

The lambda IF I used was

// IF = λp.λa.λb.pab
export const IF = (p) => (a) => (b) => p(a)(b);

This is fine if a and b are functions (like ONE in the TRUE branch in ALMOST_FACTORIAL), but a problem arises if they are function applications (like the MULTIPLY(...)(...) in the FALSE branch):

// λf.λn.IF (ISZERO n) ONE (MULTIPLY n f(PREDECESSOR n))
const ALMOST_FACTORIAL = (f) => (n) =>
 IF(ISZERO(n))(ONE)(MULTIPLY(n)(f(PREDECESSOR(n))));

If a function in any of the branch is applied, its code will always run, no matter the predicate of the IF. This is why the application of FACTORIAL was always causing an infinite loop, even if applied to ZERO. The solution is to use thunks every time an IF is used and then apply the correct branch at the end:

const ALMOST_FACTORIAL = (f) => (n) =>
 IF(ISZERO(n))(() => ONE)(() => MULTIPLY(n)(f(PREDECESSOR(n))))();