Trampolines in Javascript and the Quest for Fewer Nested Callbacks

The problem of Javascript coders often having to deal with more than the desired number of nested callback functions have never really went away. My complaint has been stated not long ago. Lately, with the raise of node.js, the complaints seemed to have gotten louder, or just more numerous. At JSConf EU 2010, there were no fewer than 5 talks addressing this issue, each in their own unique way. 

Generators

One thing that was brought up over and over again in Kyle's thread is generators. My take is this: generators have existed in Spidermonkey ever since Firefox 2, so if you are open to new language features, generators have already been around the block, we just have to get it into the standard, at which point I believe node.js - and just Javascript programmers in general - can really benefit. I have long been using generators in Python, so I know that they are very powerful. All of this motivated me to go deeper and see how far it can go in the Quest for Fewer Nested Callbacks.

First, the Punchline!

Let's see the punchline now because it may take a while before we can get through all the steps necessary to arrive at it: with the help of generators and a bit of support code, this(code taken directly from Kyle's post)

setTimeout(function(){
   xhr("/something.ajax?greeting", function(greeting) {
      xhr("/else.ajax?who&greeting="+greeting, function(who) {
         console.log(greeting+" "+who);
      });
   });
}, 1000);

can be written as

yield sleep(1000)
var greeting = yield xhr('/something.ajax?greeting')
var who = yield xhr('/else.ajax?who&greeting=' + greeting)
console.log(greeting + ' ' + who)

The supporting function

function xhr(url, callback) {
   var x = new XMLHttpRequest();
   x.onreadystatechange = function(){
      if (x.readyState == 4) {
         callback(x.responseText);
      }
   };
   x.open("GET",url);
   x.send();
}

almost remains unchanged, all it needs is to be wrapped like so

function _xhr(url, callback) {
   var x = new XMLHttpRequest();
   x.onreadystatechange = function(){
      if (x.readyState == 4) {
         callback(x.responseText);
      }
   };
   x.open("GET",url);
   x.send();
}function xhr(url){   _xhr(url, (yield Continuation))   yield Suspend}

and, sleep() is implemented as

function sleep(ms){
    setTimeout((yield Continuation), ms)
    yield Suspend
}

Are you intrigued? Read on, then.

Gentle Introduction to Generators

What are generators? How do they work? How can I use them?

Let's start with "How can I use them?". You have to be running Firefox 2 or above, or alternatively you can download Spidermonkey by itself.

For my code samples I'll assume you are using Firefox.

Next, you have to use type="application/javascript;version=1.7" in your script tag. I guess Mozilla was sheepish about this feature when they released it, given that it introduced a new keyword.

So, a hello world example for generators would be:

<script type="application/javascript;version=1.7">
// This is a generator function
function naturalNumbers(){
    var i = 0
    while (true){
        yield i++
    }
}
var N = naturalNumbers() // N is now a generator
console.log(N.next()) // prints 0
console.log(N.next()) // prints 1
console.log(N.next()) // prints 2
// and so forth
</script>

First things first, a generator function is not the same as a function. Repeat after me: a generator function is not a function. Within a generator function, you have yield statements; within a function, you have return statements - you cannot have both.

The generator object has a few methods, here we are only demonstrating next() - which executes the code within the generator function until a yield statement is reached, and returns the value being yielded. If you call next() on it again, it will continue from where it left off, and once again execute till the next yield is reached. In our natural numbers example, since we are yielding the counter within an infinite loop, we can keep calling next() on the generator object to get the next number forever...

Receiving Values

It turns out that in addition to yielding values, the yield statement can also receive values(proud of myself that I avoided using the word "return" in this sentence).

For a yield statement to receive a value, the holder of the generator must call the send() method with a value instead of the next() function

function makePrinter(){
    while(true){
        var message = (yield)
        console.log(message)
    }
}
var printer = makePrinter()
printer.next() // You may not send a value to a newly created generator
printer.send('Hello')
printer.send('I am sending this message')
printer.send('into the generator')
printer.send('and it be received and get printed')

Here we created a printer generator whose job is only to print the objects that it receives from the yields. You can't send in a value for the first invocation of the generator because it hasn't had a chance to yield yet, but after that, you can send as many as you want, since it yields infinite times.

As you can see, we are switching back and forth between two separate threads of execution(but not Threads ;).

Trampolining

Now that you understand generators, the next step is to put it together to get rid of our nested callbacks. To do that, we need to know a technique called trampolining. Neil Mix's article has some brilliant code that shows you how to do it in Javascript, but it was David Beazley's gentle example in Python that helped me understand what's going on.

Let me translate his code to Javascript, and put in some comments for ya

function add(x,y){
    yield x + y             // yield the result of addition
}
function main(){
    var r = yield add(2,2)      // yield the result of add(2,2): a generator
    console.log(r)
    yield
}
function run(){
    var m = main()
    var sub = m.next()      // start the code execution in main()
                             // sub is now generator from calling add()
    var result = sub.next() // start execution of sub
                             // result now has the value of 2 + 2: 4
    m.send(result)           // send back to generator
}
run()

The main feature of trampolining is that a value yielded by a generator is yet another generator, such is the case on this line

var r = yield add(2,2)      // yield the result of add(2,2): a generator

In this example the thread of execution is bouncing between 3 different contexts, namely the run() function and the add() and main() generator functions. We started within run(), bounced to main(), then back to run(), then to add(), then back to run(), then back to main() again, and then finally exiting in run() again.

Here's a picture so we can visualize what's happening

But, right now the run() function is inflexible. We can generalize it to handle arbitrary levels of nested generator execution - with a stack

function run(gen){
    // is object a generator?
    function isGenerator(obj){
        return String(obj) === '[object Generator]'
    }
    // last element of array
    function last(arr){
        return arr[arr.length - 1]
    }
    var stack = []
    var retval = gen
    try{
        while (true){
            if (isGenerator(retval)){   // if a generator
                stack.push(retval)      // push it onto the stack
                retval = undefined
            }else{
                stack.pop().close()     // if we got a normal value
                                        // pop the stack and
            }
            gen = last(stack)           // get the generator at top of the stack
            if (!gen) break
            retval = gen.send(retval)   // send retval to the generator
                                        // if retval is undefined, it acts just
                                        // like next()
        }
    }catch(e if e === StopIteration){
        console.log('Program ended.')
    }
}

We have a stack which starts out containing the generator from which we are starting execution - gen. Then, we keep on executing the generator at the top of the stack. If the received value is also a generator, we push it onto the stack and keep going; if we receive a normal value, then we pop the generator off the stack and, on the next iteration of the loop - send the value to previous generator one level down in the stack.

To call the new and improved the run() function you pass it the entry level generator like so

run(main())

Let's take the same example again, but executing with the generic run() function instead. This time, let's visualize it as a stack. First we start with main() at the bottom

next,

var r = yield add(2,2)

add(2, 2) is pushed onto the stack, because it is a generator. The parameters x and y are both assigned to 2 inside the scope and also go on the stack.

add() then executes and 

yield x + y

yields a numerical value: 4. Because, this is not a generator, we pop() the stack, then send the 4 back to main()

var r = yield add(2,2)

where 4 is assigned to r. 

main() then prints the value via console.log and then

yield

again, which ends the execution.

Wait, I've Seen That Before!

This... stack, it looks almost like... an execution stack! The interpreter maintains a stack when it's executing code and handling the execution of function calls - and we've just reimplemented it using generators.

To see it another way, the only difference between the trampoline style code and normal functional code is the use of the yield statements. If you take out the yields - and substitute return when appropriate, you'd have

function add(x,y){
    return x + y
}
function main(){
    var r = add(2,2)      // yield the result of add(2,2): a generator
    console.log(r)    return
}

Now that we have a generalized run() function that handles the stack generically, we can handle recursion

// the Fibonacci sequence using recursion - don't try this at home!
function fib(n){
    if (n == 1 || n == 2)
        yield 1
    else
        yield (yield fib(n-1)) + (yield fib(n-2))
}
function main(){
    console.log(yield fib(10))
}

This actually works!

Wrapping Asynchronous Execution

Okay, that's all fine and good, but we still haven't address the problem of making asynchronous code less onerous. In order to tackle that problem, we need to do a little bit more.

By keeping a stack of all of the generators we have in progress, we can restart them back at any time. However, we need to be able to suspend the execution of a generator if we are waiting for an asynchronous response. We also need to pass a function as the callback handler for the async function call, only by which can we know when to resume execution of the thread.

The solution is demonstrated by the implementation of sleep()

function sleep(millis) {
    setTimeout((yield Continuation), millis)
    yield Suspend
}

Continuation and Suspend are special constants - that we created - used as signals to run().

Here's how this works:

(yield Continuation)

will receive a function as a callback handler to setTimeout. Let's call this function the continuation.

yield Suspend

will suspend the execution of this generator, and therefore also suspending this thread of execution until the continuation has been called by setTimeout(). When the continuation eventually gets called, it will resume execution of this generator, which starts back up again after the line

yield Suspend

Our new run() function that handles all of this looks like

function run(gen){
    function isGenerator(obj){
        return String(obj) === '[object Generator]'
    }
    function last(arr){
        return arr[arr.length - 1]
    }
    function startBouncing(retval){
        try{
            while (true){
                if (isGenerator(retval)){
                    stack.push(retval)
                    retval = undefined
                }else if (retval === Suspend){
                    break                       // to suspend execution:
                                                // just break out of this
                                                // while-loop.
                                                // we can later resume
                                                // by re-starting another
                                                // while-loop by calling
                                                // startBouncing() again
                }else if (retval === Continuation){
                    retval = startBouncing      // send startBouncing
                                                // back as the callback
                                                // handler to the async
                                                // function call
                }else{
                    stack.pop().close()
                }
                gen = last(stack)
                if (!gen) break
                retval = gen.send(retval)
            }
        }catch(e if e === StopIteration){
            console.log('Program ended.')
        }
    }    
    var stack = []
    var retval
    startBouncing(gen)
}

We've refactored the while-loop inside of a function: startBouncing(). When we need to suspend, we just break out of the while-loop. When we need to resume, we just call startBouncing() to start the while-loop all over again. All the while we still have the stack in tact. The callback handler we send as the continuation is none other than the startBouncing() function. Notice that startBouncing() also takes a retval as argument. This enables us to send the first argument of the callback back to the generator, as the XHR example shows

function _xhr(url, callback){
    var xhr = new XMLHttpRequest()
    xhr.open('GET', url)
    xhr.onreadystatechange = function(){
        if (this.readyState == 4){
            // send the responseText as the first arg of the continuation
            callback(this.responseText)
        }
    }
    xhr.send()
}
function xhr(url){
    _xhr(url, (yield Continuation))
    yield Suspend
}

Because we are passing the responseText as the first argument to the callback(the continuation) - by our made up convention - it will be the value that's sent back to the caller of this generator function. So

var responseText = yield xhr('/something.ajax')

Just works!

Adding Back Exceptions

Async-style calls don't really throw any exceptions. That's because if there were problems with the request, you could only be notified asynchronously - the original execution has already past! However, now that we have something that looks like synchronous code again, we can put exceptions back into play. We will use the convention that if an instance of Error is passed as the first argument of the continuation, then we will throw it. Thus for our xhr function

function _xhr(url, callback){
    var xhr = new XMLHttpRequest()
    xhr.open('GET', url)
    xhr.onreadystatechange = function(){
        if (this.readyState == 4){
            if (this.status === 200)
                callback(this.responseText)
            else{
                var ex = new Error("XMLHttpRequest Error: " + 
                    this.statusText + ': ' + this.status)
                // pass in an error object to the continuable to throw it
                callback(ex)
            }
        }
    }
    xhr.send()
}

To throw an exception from within a generator you actually have to call the throw() method on the generator object. We just need to add an extra else-if inside of our big if statement inside of the while-loop in run()

else if (retval instanceof Error){
    stack.pop().close()
    last(stack).throw(retval)
}

Now we can get exceptions throw from the xhr() generator function

function main(){
    try{
        var result = yield xhr('/doesnotexist.ajax')
        console.log('blah')
    }catch(e){
        console.log('exception caught: ' + e)
    }
}

Conclusion

I think the trampolining technique is very compelling, perhaps even more compelling than the continuables in fab.js. The only thing we need is support for generators in more engines. As far as I know, Spidermonkey and Rhino are the only 2 that support it right now.

Source Code

You can download all of the code examples shown in this post.

References