(or call-with-current-continuation for JavaScript programmers)

Being the terrible JavaScript developer that I am, I’ve come across a term that Node.JS developers apparently love to mention: continuation-passing style. Now, what the hell is continuation-passing style? If we look at the Wikipedia article, we’re presented with lines and lines of Scheme, which is great if you understand Scheme.

But I don’t understand Scheme!

In that case, let’s look at how this term is used in conjunction with Node.JS (please note I don’t condone the use of Node.JS, ever):

var myQuery = function(next) {
    db.query("some query here", function(err, res) {
        if (err) next(err);
        else next(null, res);
    });
};

This should be familiar to most people — we just make a function that takes a callback and, inside the function, run an asynchronous query then invoke the callback when we have the result. Now, if you look closely, the next function fulfills both the duties of the return and throw statements — next with the first parameter filled throws an error, and next with the second parameter filled returns a result. So, at a more abstract level, we can say that the next function continues the flow of execution — a continuation! If this isn’t immediately evident to you, don’t worry! We can simplify the example a little by just renaming next to return (pretend it’s valid, okay?) and removing its ability to throw:

var myQuery = function(return) {
    db.query("some query here", function(res) {
        return(res);
    });
}

Aha! We can nest more callbacks inside each other to make the continuation of program flow more evident:

var myQuery = function(return) {
    db.query("some query here", function(a) {
        db.query("some other query here " + a, function(b) {
            return(b);
        });
    });
}

As we nest functions inside each other, the flow gets passed from outer functions, through the callback functions (which are in fact explicit continuations!) into inner functions, where it eventually calls the return function (which is the continuation that was originally passed in).

Callbacks are continuations.

Okay, so what’s so cool about continuations?

With continuation-passing style, functions never return. They just keep calling more functions (aside: in JavaScript, this will eventually exhaust the call stack, but in languages like Scheme where we have tail-call elimination we don’t have those stack frames so we don’t run that risk). As such, simple operations like x + y aren’t actually in continuation-passing style since they return to the caller, which continuation-passing style has no notion of.

We can define a few magic functions that fulfill continuation-passing style:

var add_cps = function(x, y, next) {
    next(x + y);
};

var sub_cps = function(x, y, next) {
    next(x - y);
};

If we wanted to write console.log(x + 3 - 4) in continuation-passing style, we would do:

add_cps(x, 3, function(y) {
    sub_cps(y, 4, function(res) {
        console.log(res);
    });
});

Rather convoluted, I know, but this demonstrates how we can actually grab the state of program execution between any operation:

var cc;

add_cps(x, 3, function(y) {
    cc = function(next) {
        sub_cps(y, 4, next);
    };

    cc(function(res) {
        console.log(res);
    });
});

The function cc has captured the values of x and y from where it’s defined, so we can actually invoke cc over and over again to jump back to just before sub_cps. In imperative programming terms, cc is a label and invoking cc causes a goto back to cc — so, as we can see, cc is a continuation.

If you have closures, you have continuations.

Then what’s call-with-current-continuation?

call-with-current-continuation is a Scheme primitive that enables you to capture a continuation at a given point of computation — which we’ve already done with cc = .... That was easy, wasn’t it? What we can do with cc, though, is awesome.

var scope = {};

var set_cps = function(k, v, next) {
    scope[k] = v;
    next();
}

var get_cps = function(k, next) {
    next(scope[k]);
}

var cc;

set_cps('i', 0, function() {
    cc = function(next) {
        get_cps('i', function(i) {
            add_cps(i, 1, function(j) {
                set_cps('i', j, function() {
                    // this should be in CPS, but it would be too tedious
                    console.log(i);

                    // this should also be in CPS
                    if (i < 10) {
                        cc();
                    }
                });
            });
        });
    };
    cc();
});

Hooray, we’ve created a loop with continuations! But since JavaScript has no native support for call-with-current-continuation, it looks like absolute ass (no different from the usual Node.JS, right guys?).

Continuations can be used to make loops.

In conclusion

Continuations are a fascinating artifact of computer science. They’re basically gotos, but more powerful in that they capture the scope they’re created in and are created dynamically.

For some interesting further reading:

• call-with-current-continuation in Scheme
• callcc in Ruby