Functional programming in JavaScript (5)

Please take a look at other posts about functional programming in JavaScript:

1. Part 1 - what functional programming is about
2. Part 2 - functional pipelines
3. Part 3 - the Y combinator
4. Part 4 - monads
5. Part 5 - the Trampoline

Another interesting technique that is commonly used in functional programming is the Trampoline. Is a hybrid way of avoiding stack overflows that possibly occur during deep recursive computations.

Functional environments that support Tail Call Optimizations can possibly go deep into recursion. But in V8's JavaScript, stack depth is limited by memory. Since each stack frame consumes a portion of this memory and the stack memory limit is around 1M, depending on how many actual arguments your stack calls have, you can possibly execute about 10000 simple recursive calls. In case of heavy calls (with multiple arguments), this goes down quickly.

Consider this example:

function naiveFac(n) {
  return n <= 1 ? 1 : n * naiveFac(n - 1);
}
console.log( naiveFac(5) );
console.log( naiveFac(10000) );

On my current V8 (node 24), the former computes 120 correctly, the latter throws:

Uncaught RangeError RangeError: Maximum call stack size exceeded
    at naiveFac (c:\Temp\uni\weppo\w7\app.js:2:3)

And this is where the Trampoline can be used.

But first, let's refactor this to the Accumulator Passing Style we've already covered:

function naiveFac2(n) {
   return (function factStep(n, accumulator = 1) {
      return n <= 1
         ? accumulator
         : factStep(n-1, n*accumulator);
      })(n);
}
console.log( naiveFac2(5) );
console.log( naiveFac2(10000) );

It still fails for 10000 but the important refactorization is already there.

Now, consider the Trampoline:

function trampoline(fn) {
  while (typeof fn === 'function') {
    fn = fn();
  }
  return fn;
}

First, note that it's imperative, it uses while. And yes, it's not pure, not quite functional but it does the job in a hybrid world of JavaScript. Then, note what it does. It gets a function, executes it and if the return value of the function is another function, it executes it again. And again, until something else than a function is returned. Do you get the idea? Our recursive function, instead just calling itself, will now return a function that calls it but the Trampoline will execute this new function. It avoids recursion but also requires this specific approach that involves the accumulator.

We can now go back to the original issue and refactor it to use the Trampoline:

function trampolineFac(n) {
   function factStep(n, accumulator = 1n) {
      return n <= 1n 
        ? accumulator
        : () => factStep(n-1n, n*accumulator);
   }
   return trampoline( () => factStep(BigInt(n)) );
}

console.log(trampolineFac(5));  
console.log(trampolineFac(10000)); 

Note that it requires some subtle tweaks to actually support BigInts as the result is a huge number. But, hey, it works! The recursion limit is gone!