Continuation Passing Style in JavaScript

One of the frequently unquestioned assumptions in modern programming languages is "what comes next". We just assume it's the line after the current line, or the first line of the function just called, or the line that follows where the function was called from.

Continuations are objects that say go to this point in the code, and there is no return, where next becomes explicit. They are not goto statements, they are objects that can be passed around and represented in structures. A common example is using continuations to model exceptions but with no requirement on a continuation to be somewhere "above" in the stack.

A continuation syntactically looks a bit like a function but with no going back there is no need for a stack frame. Function call without a new stack frame is a key concept in tail call recursion optimisation. Languages that support one often support the other.

But approximating the style can be useful even in a language which has no explicit support for them, for example JavaScript.

A JavaScript Recursive Descent Parser in Continuation Passing Style

To illustrate I've transformed this straight forward, hand crafted JavaScript, recursive descent expression parser to continuation passing style and along the way also into tail call recursive form. Both versions translate a token stream into tree, (useful for fully bracketed rendering, or evaluation with correct operator precedence).

The transformation means I can not rely on the return values of functions. Instead I can only go forward. I go forward by calling another function. So, the original version calls xpn, expects tokens to be mutated, passes the return value to term_tail along with the mutated tokens, and then returns that result.

 function term(tokens) {
    return term_tail(xpn(tokens), tokens);
  }

But translated it simply says to continue with xpn, then term_tail, and finally whatever c might be.

  function term(a, tokens, c) {
    continue_with([null, tokens], continuation(xpn, term_tail, c));
  }

And I start the whole process by saying at the end continue with done which prints the results. What will end up happening is the recursive tree will become a pipeline.

  continue_with([null, [10, '+', 11, '*', 12]], continuation(expr, done))

You can see I have a special function to prepare my continuation, and another to call them, we're deep in higher order programming territory here... But they're not deep magic, mostly they handle packing and unpacking arguments.

Because there is no coming back from the continuation all results have to accumulate forward in the parameters, and the continuation calls have to be the last thing done in the function, that bit is the translation to Tail Call Recursive form. Where the return of one function would have been used by another function call, that second function becomes a parameter to the first:

  fn2( fn1( 123 ))     // simple style
  fn1(123, fn2)         // continuation style

The last bit of cleverness is that you can insert other continuations in front of the input continuations. In effect, this algorithm works by taking the first function and the last function and squeezing all the other function calls in between.

  function xpn(a, tokens, c) {
    continue_with([null, tokens], continuation(factor, xpn_tail, c));
  }

So xpn is supposed to continue with c but has squeezed factor and xpn_tail in front.

Why Bother in General?

In a good functional programming language this style works without building up anything on the stack. And it's working without actively consuming tokens, allowing immutable data structures for the tokens. That means it can be very memory efficient, and also produces algorithms that are more suitable for parallelisation.

I also have a philosophical preference for being explicit about sequence when sequence is a real requirement, and practicing this style gives me another tool for being explicit about things that are often just assumed, (more on this soon).

As a general bonus tail call recursive functions can be trivially translated into loops which might be important if function call overhead is a problem for a given algorithm.

Why Bother in JavaScript?

The naive version in JavaScript, just modelling the continuation call with a simple function call, is probably a bad idea. It ends up taking all the branches of recursion and glueing them together in one long pipeline; a recipe for running out of stack space. But instead of simple function calls I've used setTimeout, so this potentially time consuming operation is now neatly broken up allowing the UI to remain responsive.

Because I'm managing the continuations calls explicitly, so I could trap all exceptions if that was important, just by changing the functions I use to build and call the continuations. Trapping exceptions this way is a great trick for concurrent programming because you can pass the exception handling continuations from thread to thread even though you're dealing with separate stacks, (you'd have to provide exception handlers as callbacks or additional continuations, a pattern I personally prefer anyway).

And as mentioned, I could translate all this to a loop, and do away with the function call overhead.