103

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.

  • 5
    Yes, but thats still recursion. loopy doesn't overflow because it doesn't call itself. – tkausl Oct 11 '16 at 4:54
  • 4
    "I had thought that TCO had been implemented, but as it turns out I was wrong." It has been at least in V8 in most scenaros. You can use it for instance in any recent version of Node by telling Node to enable it in V8: stackoverflow.com/a/30369729/157247 Chrome's had it (behind an "experimental" flag) since Chrome 51. – T.J. Crowder Oct 11 '16 at 9:31
  • 125
    The kinetic energy from the user is transformed to elastic potential energy as the trampoline sags, then back to kinetic energy as it rebounds. – immibis Oct 11 '16 at 9:56
  • 66
    @immibis, On behalf of everyone who came here without checking which Stack Exchange site this was, thank you. – user1717828 Oct 11 '16 at 15:30
  • 4
    @jpaugh did you mean "hopping"? ;-) – Hulk Oct 12 '16 at 15:43
88

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.

  • 1
    Comments are not for extended discussion; this conversation has been moved to chat. – yannis Oct 12 '16 at 9:41
  • It's really just a sum type. Sometimes known as a variant. Dynamic languages support them rather easily because every value is tagged, while more statically-typed languages will require you to specify the function returns a variant. Trampolines are easily possible in C++ or Haskell, for example. – GManNickG Oct 12 '16 at 20:54
  • 2
    @GManNickG: Yes, that's what I meant by "a lot more typing." In C you would have to declare a union, declare a struct which tags the union, pack and unpack the struct at either end, pack and unpack the union at either end, and (probably) figure out who owns the memory which the struct inhabits. C++ is very likely less code than that, but it's not conceptually any less complicated than C, and it's still more verbose than OP's Javascript. – Kevin Oct 12 '16 at 21:13
  • Sure, I'm not contesting that, I just think the emphasis you put on it being weird or not making sense is a bit strong. :) – GManNickG Oct 12 '16 at 21:18
173

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.

17

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.

  • foo = foo() is mutation in the sense of modifying local state, but I'd generally consider that reassignment as you aren't actually modifying the underlying function object, you're replacing it with the function (or value) it returns. – JAB Oct 11 '16 at 21:21
  • @JAB Yes, I didn't mean to imply mutating the value that foo contains, only the variable is modified. A while loop requires some mutable state if you want it to terminate, in this case the variable foo or x. – Bergi Oct 11 '16 at 22:05
  • I did something like this a while back in this answer to a Stack Overflow question about tail call optimization, trampolines, etc. – Joshua Taylor Oct 12 '16 at 18:24
  • 2
    Your version without mutation has converted a recursive call of fn into a recursive call to trampoline - I'm not sure that's an improvement. – Michael Anderson Oct 13 '16 at 1:01
  • 1
    @MichaelAnderson It's only meant to demonstrate the abstraction. Of course a recursive trampoline is not useful. – Bergi Oct 13 '16 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.