Trampoline function operation principle

Question

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}
function sum(x, y) {
  if (y > 0) {
  //   return sum(x + 1, y - 1);  Maximum call stack size exceeded
  return sum.bind(null, x + 1, y - 1); //100001
  } else {
    return x;
  }
}
sum(1, 100000) //Maximum call stack size exceeded
let value= trampoline(sum(1, 100000))
console.log(value)

Why use trampoline functions without stack overflow
Why does the sum function in a trampoline function require bind

@MaheerAli The maximum call stack size depends on the JS runtime. — nicholaswmin, Mar 23 '19 at 10:14
@MaheerAli, on chrome it throws the error, on egde, it shows the result. — Nina Scholz, Mar 23 '19 at 10:14

score 1 · Answer 1 · answered Mar 23 '19 at 10:21

1.Why use trampoline functions without stack overflow

Maximum call stack is thrown when a function calls itself more than limit. In trampoline there is a while loop not recursion.so it works fine.

2.Why does the sum function in a trampoline function require bind

You can do that without using bind(). Bind is used because it returns a new function. If you use a wrapper function still it works fine

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}
function sum(x, y) {
  if (y > 0) {
  //   return sum(x + 1, y - 1);  Maximum call stack size exceeded
  return () => sum(x + 1, y - 1); 
  } else {
    return x;
  }
}
sum(1, 100000) //Maximum call stack size exceeded
let value= trampoline(sum(1, 100000))
console.log(value)

You may ask why we need to use wrapper function. Because if we don't use the wrapper function and simply do

return sum(x + 1, y - 1);

It will cause recursion. When we you wrapper function or bind() a new function is returned but not called so recursion occurs and it throws error.

it still uses recursion, but with a stack and this does not explain what is going on. — Nina Scholz, Mar 23 '19 at 10:30
maybe this https://stackoverflow.com/a/489860/1447675 highlights the problem a bit. — Nina Scholz, Mar 23 '19 at 10:37

georg · Answer 2 · 2019-03-23T22:25:44.333

Let's simplify your example a bit:

function sum_tramp(x, y) {
    if (y > 0)
        return () => sum_tramp(x + 1, y - 1);
    else
        return x;
}

function sum_rec(x, y) {
    if (y > 0)
        return sum_rec(x + 1, y - 1);
    else
        return x;
}

x = sum_tramp(1, 1e6)
while (x instanceof Function)
    x = x();
console.log(x)


x = sum_rec(1, 1e6) //Maximum call stack size exceeded
console.log(x)

Naive recursion (sum_rec) requires all values to be computed before it can return anything, so to compute 6+4, it has to compute 7+3 which requires 8+2 etc. The function doesn't exit until all subsequent calls are complete and its arguments are sitting on the stack until then.

A trampoline returns a computation, that is, instructions how to compute the value instead of the value itself. Since the computation is already known, the function exits immediately and doesn't fill up the stack. In the main program, we check if the returned value is a computation, and if yes, simply invoke it again. So, when computing 6+4, we receive instructions how to compute 7+3. We carry out these instructions, and get instructions how to compute 8+2. Then, we carry them out... and so on, until we end up with a non-function return value.

As noted in the comments, some browsers already implement tail call optimizations, which makes trampolines unnecessary (but still worth knowing about).

Trampoline function operation principle

2 Answers2