Why do Trampolines work?

Question

I've been doing some functional JavaScript. I had thought that Tail-Call Optimization had been implemented, but as it turns out I was wrong. Thus, I've had to teach myself Trampolining. After a bit of reading here and elsewhere, I was able to get the basics down and constructed my first trampoline:

/*not the fanciest, it's just meant to
reenforce that I know what I'm doing.*/

function loopy(x){
    if (x<10000000){ 
        return function(){
            return loopy(x+1)
        }
    }else{
        return x;
    }
};

function trampoline(foo){
    while(foo && typeof foo === 'function'){
        foo = foo();
    }
    return foo;
/*I've seen trampolines without this,
mine wouldn't return anything unless
I had it though. Just goes to show I
only half know what I'm doing.*/
};

alert(trampoline(loopy(0)));

My biggest issue, is I don't know why this works. I get the idea of rerunning the function in a while loop instead of using a recursive loop. Except, technically my base function already has a recursive loop. I'm not running the base loopy function, but I am running the function inside of it. What's stopping foo = foo() from causing a stack overflow? And isn't foo = foo() technically mutating, or am I missing something? Perhaps it's just a necessary evil. Or some syntax I'm missing.

Is there even a way to understand it? Or is it just some hack that somehow works? I've been able to make my way through everything else, but this one has me befuzzled.

Answer 1

The reason your brain is rebelling against the function loopy() is that it is of an inconsistent type:

function loopy(x){
    if (x<10000000){ 
        return function(){ // On this line it returns a function...
            // (This is not part of loopy(), this is the function we are returning.)
            return loopy(x+1)
        }
    }else{
        return x; // ...but on this line it returns an integer!
    }
};

Quite a lot of languages don't even let you do things like this, or at least demand a lot more typing to explain just how this is supposed to make any kind of sense. Because it really doesn't. Functions and integers are totally different kinds of objects.

So let's go through that while loop, carefully:

while(foo && typeof foo === 'function'){
    foo = foo();
}

Initially, foo is equal to loopy(0). What is loopy(0)? Well, it's less than 10000000, so we get function(){return loopy(1)}. That's a truthy value, and it's a function, so the loop keeps going.

Now we come to foo = foo(). foo() is the same as loopy(1). Since 1 is still less than 10000000, that returns function(){return loopy(2)}, which we then assign to foo.

foo is still a function, so we keep going... until eventually foo is equal to function(){return loopy(10000000)}. That's a function, so we do foo = foo() one more time, but this time, when we call loopy(10000000), x is not less than 10000000 so we just get x back. Since 10000000 is also not a function, this ends the while loop as well.

Answer 2

Kevin succinctly points out how this particular code snippet works (along with why it's quite incomprehensible), but I wanted to add some information about how trampolines in general work.

Without tail-call optimization (TCO), every function call adds a stack frame to the current execution stack. Suppose we have a function to print out a countdown of numbers:

function countdown(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    countdown(n - 1);
  }
}

If we call countdown(3), let's analyze how the call stack would look without TCO.

> countdown(3);
// stack: countdown(3)
Launch in 3
// stack: countdown(3), countdown(2)
Launch in 2
// stack: countdown(3), countdown(2), countdown(1)
Launch in 1
// stack: countdown(3), countdown(2), countdown(1), countdown(0)
Blastoff!
// returns, stack: countdown(3), countdown(2), countdown(1)
// returns, stack: countdown(3), countdown(2)
// returns, stack: countdown(3)
// returns, stack is empty

With TCO, each recursive call to countdown is in tail position (there's nothing left to do other than return the result of the call) so no stack frame is allocated. Without TCO, the stack blows up for even slightly large n.

Trampolining gets around this restriction by inserting a wrapper around the countdown function. Then, countdown doesn't perform recursive calls and instead immediately returns a function to call. Here's an example implementation:

function trampoline(firstHop) {
  nextHop = firstHop();
  while (nextHop) {
    nextHop = nextHop()
  }
}

function countdown(n) {
  trampoline(() => countdownHop(n));
}

function countdownHop(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    return () => countdownHop(n-1);
  }
}

To get a better sense of how this works, let's look at the call stack:

> countdown(3);
// stack: countdown(3)
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(3)
Launch in 3
// return next hop from countdownHop(3)
// stack: countdown(3), trampoline
// trampoline sees hop returned another hop function, calls it
// stack: countdown(3), trampoline, countdownHop(2)
Launch in 2
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(1)
Launch in 1
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(0)
Blastoff!
// stack: countdown(3), trampoline
// stack: countdown(3)
// stack is empty

At each step the countdownHop function abandons direct control of what happens next, instead returning a function to call that describes what it would like to happen next. The trampoline function then takes this and calls it, then calls whatever function that returns, and so on until there is no "next step". This is called trampolining because the flow of control "bounces" between each recursive call and the trampoline implementation, instead of the function directly recurring. By abandoning control over who makes the recursive call, the trampoline function can ensure the stack doesn't get too large. Side note: this implementation of trampoline omits returning values for simplicity.

It can be tricky to know whether this is a good idea. Performance can suffer due to each step allocating a new closure. Clever optimizations can make this viable, but you never know. Trampolining is mostly useful for getting around hard recursion limits, for instance when a language implementation sets a maximum call stack size.

Answer 3

Maybe it becomes easier to understand if the trampoline is implemented with a dedicated return type (instead of abusing a function):

class Result {}
// poor man's case classes
class Recurse extends Result {
    constructor(a) { this.arg = a; }
}
class Return extends Result {
    constructor(v) { this.value = v; }
}

function loopy(x) {
    if (x<10000000)
        return new Recurse(x+1);
    else
        return new Return(x);
}

function trampoline(fn, x) {
    while (true) {
        const res = fn(x);
        if (res instanceof Recurse)
            x = res.arg;
        else if (res instanceof Return)
            return res.value;
    }
}

alert(trampoline(loopy, 0));

Contrast this to your version of trampoline, where the recursion case is when the function returns another function, and the base case is when it returns something else.

What's stopping foo = foo() from causing a stack overflow?

It does not call itself any more. Instead, it returns a result (in my implementation, literally a Result) that conveys whether to continue the recursion or whether to break out.

And isn't foo = foo() technically mutating, or am I missing something? Perhaps it's just a necessary evil.

Yes, this is exactly the necessary evil of the loop. One could write trampoline without mutation as well, but it would require recursion again:

function trampoline(fn, x) {
    const res = fn(x);
    if (res instanceof Recurse)
        return trampoline(fn, res.arg);
    else if (res instanceof Return)
        return res.value;
}

Still, it shows the idea of what the trampoline function does even better.

The point of trampoling is abstracting out the tail-recursive call from the function that wants to use recursion into a return value, and doing the actual recursion in only one place - the trampoline function, which then can be optimised in a single place to use a loop.