Javascript recursion without conditional

Question

I'm trying to 'implement' Church's encoding of lambda calculus in Javascript, but started having trouble when I wrote the factorial function:

const factorial = n => (iszero(n))(ONE)(multiply(n)(factorial(predecessor(n))));

iszero(n) acts as a conditional, and returns a function that executes it's first parameter if n is zero, or the second if it isn't.

Calling this function on any value results in a stack overflow.

I tried to simplify it to find out why:

//const ifelse = condition => a => b => condition ? a : b;
//const factorial = n => ifelse(n == 0)(1)(n * factorial(n - 1));
const ifelse = function(condition, a, b) {
    if (condition) {
        return a;
    } else {
        return b;
    }
}
const factorial = function(number) {
    return ifelse(number == 0, 1, number * factorial(number - 1));
}

calling factorial here also results in overflow, although if we reduce the ifelse function in factorial, it makes a perfectly functional factorial function that doesn't throw:

//const factorial = n => (n == 0) ? (1) : (n * factorial(n - 1));
const factorial = function(number) {
    if (number == 0) {
        return 1;
    } else {
        return number * factorial(number - 1);
    }
}

But I'm trying to use nothing but functions inside the factorial, so the ternary conditional operator is not acceptable (see the commented arrow notation).

Why is my factorial function resulting in a stack overflow when invoked on any value, and can this be avoided while still using only functions (no conditionals)?

EDIT: the definitions for the first piece of code:

const TRUE = x => y => x;
const FALSE = x => y => y;

const ZERO = f => x => x;
const ONE = f => x => f(x);

const pair = a => b => f => f(a)(b);

const first = p => p(TRUE);
const second = p => p(FALSE);

const iszero = n => n(x => FALSE)(TRUE);

const successor = n => f => x => f(n(f)(x));
const multiply = n1 => n2 => f => x => n1(n2(f))(x);
const predecessor = n => second(n(p => pair(successor(first(p)))(first(p)))(pair(ZERO)(ZERO)));

Wow this reads terrible. No wonder you get confused. Why do you write it like this, is there a specific reason? — Martijn
– Martijn, Commented Aug 3, 2018 at 7:45
I really don't know how to write it better, can you edit it or point out what's unclear? English isn't my first language so my writing comes off a bit weird. I added the second piece of code to avoid including the missing parts of the first one, cause there's a lot of them. — HL.
– HL., Commented Aug 3, 2018 at 7:51

Amadan · Accepted Answer · 2018-08-03 08:22:07Z

2

You are getting stack overflow because JavaScript is not a lazy-evaluated language. For example:

ifelse(false)(console.log("YES"))(console.log("NO"))
// => YES
//    NO

Both parameters are evaluated. The way to keep that from happening is to keep them as functions till you need them.

ifelse(false)(() => console.log("YES"))(() => console.log("NO"))()
// => NO

So in your second factorial definition, factorial(n - 1) is getting executed no matter what; ifelse is just there to let you select which of the two values to return. Obviously, factorial(0) will then call factorial(-1), which will continue right down to -infinity, as limited by memory.

Keeping them unevaluated:

factorial = n => ifelse(n == 0)(() => 1)(() => n * factorial(n - 1)())
factorial(1)()
# => 1
factorial(5)()
// => 120

I can't tell you what's wrong with your first set given that you don't have the definitions, but the cause is likely the same.

EDIT: Having seen the definitions... let me first add one of my own:

const display = n => n(x => x + 1)(0)

(The n(x => x + 1)(0) is a handy trick to convert Church numerals to normal numbers, so we can see what's happening. Debug tool only, so it shouldn't violate the purity of what you're doing.)

With our inspector at hand... the predecessor is not correct. See:

display(successor(predecessor(ONE)))
// => TypeError: f(...) is not a function
//        at f (repl:1:33)
//        at x (repl:1:36)

Try this (direct from your Wikipedia link):

const predecessor = n => f => x => n(g => h => h(g(f)))(u => x)(u => u)

With that in place, you get the correct result:

display(successor(predecessor(ONE)))
// => 1

Now, to turn to the factorial. Applying the same trick as above (wrapping the if and else branches into closures to keep them from premature evaluation):

const factorial = n => (iszero(n))(() => ONE)(() => multiply(n)(factorial(predecessor(n))()));

const FIVE = successor(successor(successor(successor(ONE))));
display(factorial(FIVE)())
// => 120

edited Aug 3, 2018 at 8:22

answered Aug 3, 2018 at 7:54

Amadan

200k23 gold badges252 silver badges321 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

HL. Over a year ago

Fascinating! And you're absolutely right, the issue with my predecessor is using a comma in pair(ZERO, ZERO), instead it should be pair(ZERO)(ZERO), I'll correct it in a moment. This pred method with pairs comes from this paper btw, i found it more intuitive than the Wikipedia method.But hey great answer thanks again!

Amadan Over a year ago

Oh, I should have noticed that. But yeah, wasn't really the point of the question so I didn't waste too much time on it, just copied a definition known to work. :P

CertainPerformance · Accepted Answer · 2018-08-03 07:54:58Z

1

The problem is that function arguments are evaluated completely before the function itself is run. So, for example, when

(n * factorial(n - 1))

is an argument list, that code there must resolve to a value before proceeding to call the function returned by

n => ifelse(n == 0)(1)

It doesn't first check your ifelse condition before evaluating - it tries to evaluate it no matter what. So, a stack overflow results, because it attempts to continually figure out the else result of n, then n - 1, then n - 2, ... n - 10, n - 11, and so on.

Pass b as a function instead, so that you can call it and evaluate the else to a value only if the condition ends up being false:

const ifelse = condition => a => b => condition ? a : b();
const factorial = n => ifelse(n == 0)(1)(() => n * factorial(n - 1));
//                                       ^^^^^
console.log(factorial(5));

answered Aug 3, 2018 at 7:54

CertainPerformance

373k55 gold badges354 silver badges359 bronze badges

2 Comments

ymutlu Over a year ago

This wont get SO for input 5 of course, try it with 40000.

CertainPerformance Over a year ago

The problem was his previous code was getting a SO even with low inputs.

Collectives™ on Stack Overflow

Javascript recursion without conditional

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related