How to understand trampoline in JavaScript?

Here is the code:

function repeat(operation, num) {
  return function() {
    if (num <= 0) return
    operation()
    return repeat(operation, --num)
  }
}

function trampoline(fn) {
  while(fn && typeof fn === 'function') {
    fn = fn()
  }
}

module.exports = function(operation, num) {
  trampoline(function() {
    return repeat(operation, num)
  })
}

I have read that the trampoline is used to deal with overflow problems, so the function would not just keep calling itself and cause the stack to fill up.

But how does this snippet function? Especially the trampoline function? What did it exactly do by while and how did it accomplish its goal?

Solution 1:

The trampoline is just a technique to optimize recursion and prevent stack-overflow exceptions in languages that don't support tail call optimization like Javascript ES5 implementation and C#. However, ES6 will probably have support for tail call optimization.

The problem with regular recursion is that every recursive call adds a stack frame to the call stack, which you can visualize as a pyramid of calls. Here is a visualization of calling a factorial function recursively:

(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0)))) 
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

Here is a visualization of the stack where each vertical dash is a stack frame:

         ---|---
      ---|     |---
   ---|            |--- 
---                    ---

The problem is that the stack has limited size, and stacking up these stack frames can overflow the stack. Depending on the stack size, a calculation of a larger factorial would overflow the stack. That is why regular recursion in C#, Javascript etc. could be considered dangerous.

An optimal execution model would be something like a trampoline instead of a pyramid, where each recursive call is executed in place, and does not stack up on the call stack. That execution in languages supporting tail call optimization could look like:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

You can visualize the stack like a bouncing trampoline:

   ---|---   ---|---   ---|---
---      ---       ---       

This is clearly better since the stack has always only one frame, and from the visualization you can also see why it is called a trampoline. This prevents the stack from overflowing.

Since we don't have the luxury of tail call optimization in Javascript, we need to figure out a way to turn regular recursion into an optimized version that will execute in trampoline-fashion.

One obvious way is to get rid of recursion, and rewrite the code to be iterative.

When that is not possible we need a bit more complex code where instead of executing directly the recursive steps, we will utilize higher order functions to return a wrapper function instead of executing the recursive step directly, and let another function control the execution.

In your example, the repeat function wraps the regular recursive call with a function, and it returns that function instead of executing the recursive call:

function repeat(operation, num) {
    return function() {
       if (num <= 0) return
       operation()
       return repeat(operation, --num)
    }
}

The returned function is the next step of recursive execution and the trampoline is a mechanism to execute these steps in a controlled and iterative fashion in the while loop:

function trampoline(fn) {
    while(fn && typeof fn === 'function') {
        fn = fn()
    }
}

So the sole purpose of the trampoline function is to control the execution in an iterative way, and that ensures the stack to have only a single stack frame on the stack at any given time.

Using a trampoline is obviously less performant than simple recursion, since you are "blocking" the normal recursive flow, but it is much safer.

http://en.wikipedia.org/wiki/Tail_call

http://en.wikipedia.org/wiki/Trampoline_%28computing%29

Solution 2:

The while loop will keep running until the condition is falsy.

fn && typeof fn === 'function' will be falsy either if fn itself is falsy, or if fn is anything other than a function.

The first half is actually redundant, since falsy values are also not functions.

Solution 3:

The other replies describe how a trampoline works. The given implementation has two drawbacks though, one of which is even harmful:

• The trampoline protocol depends only on functions. What if the result of the recursive operation is a function as well?
• You have to apply the recursive function with the trampoline function throughout your calling code. This is an implementation detail that should be hidden.

Essentially, the trampoline technique deals with lazy evaluation in an eagerly evaluated language. Here is an approach that avoids the drawbacks mentioned above:

// a tag to uniquely identify thunks (zero-argument functions)

const $thunk = Symbol.for("thunk");

//  eagerly evaluate a lazy function until the final result

const eager = f => (...args) => {
  let g = f(...args);
  while (g && g[$thunk]) g = g();
  return g;
};

// lift a normal binary function into the lazy context

const lazy2 = f => (x, y) => {
  const thunk = () => f(x, y);
  return (thunk[$thunk] = true, thunk);
};

// the stack-safe iterative function in recursive style

const repeat = n => f => x => {
  const aux = lazy2((n, x) => n === 0 ? x : aux(n - 1, f(x)));
  return eager(aux) (n, x);
};

const inc = x => x + 1;

// and run...

console.log(repeat(1e6) (inc) (0)); // 1000000

The lazy evaluation takes place locally inside repeat. Hence your calling code doesn't need to worry about it.