What is the trick behind generating Javascript code with continuations?

Question

I am looking for a way to add to Javascript a very specific form of non-preemptive multithreading. Mozilla's Javascript 1.7 supports native coroutines using yield, but I prefer not to use a browser-specific solution. I saw that there are several implementations of continuations or coroutines, based on transforming annotated Javascript code into plain Javascript. Some examples are StratifiedJS, Narrative Javascript, and jwacs.

I don't need a fully-featured framework for simulated Javascript asynchronous calls; I just need it for a very specific usage that I would like to implement. Therefore, the above libs are an overkill for me.

Can someone point me to the basic "trick" (or tricks) that such pre-processors use? Is there some special language hack that makes continuations possible in Javascript, at the cost of generating some extra code? Any relevant reference is welcomed.

Answer 1

It's continuation passing style.

Javascript is Lisp but wears as syntax the clothes of C.

Because Javascript is a functional language at its core, really crazy tricks are possible, like continuation passing style. But these tricks are headache-inducing.

In a summary, a continuation is the concept of what to do next -- made available as something which you can invoke, exactly like a function. I also sometimes view the continuation as a saved stack of call frames: You can save a stack of function calls as an execution state and return to or just "invoke" this state later.

Someone demonstrated that by transforming code into continuation passing style you can get the power of continuations. Wow! It is really impressive:

Just a source code transformation and whooosh you have the power of continuations.

Now, the problem with Javascript is its C syntax. It is difficult to do the source code transform with C syntax. It would be easier with Lisp syntax but still tedious and error-prone.

We are lucky that some really ingenious people did the hard work for us. This hard work entails the use of a Javascript parser, because what does this transform really mean? In a summary it means reordering the sequence of the operation such that what is really done first comes first.

f(g(a + x))

The addition a + x is done first, then the function call g() then f(). There are three sub-expressions. In the CPS transform the result of the sub-expressions are passed to a continuation. This involves the creation of many inner helper functions as temporary continuations. This can get complicated and tedious, as we will see below.

In http://en.wikipedia.org/wiki/Continuation-passing_style an example function

(define (pyth x y)
  (sqrt (+ (* x x) (* y y))))

is converted to

(define (pyth& x y k)
  (*& x x (lambda (x2)
      (*& y y (lambda (y2)
               (+& x2 y2 (lambda (x2py2)
                          (sqrt& x2py2 k))))))))

This corresponds to Javacript

function pyth(x, y) {
    return Math.sqrt(x * x + y * y);
}

but *, + and Math.sqrt() are not functions where a CPS would make sense.

But let assume for the sake of the example that *, + and Math.sqrt() are web services. This is important because Javascript web service invocations are asynchronous. Everybody who has worked with asynchronous invocations knows how complicated it can get to combine the results of them. With a preprocessing library or generators it gets easier to cope with asynchronous results.

So let's write the example in a different way:

function pyth(x, y) {
    return sqrt(add(mul(x, x), mul(y, y)));
}

then a CPS transform could look like this:

function pyth_cps(x, y, k) {
  mul_cps(x, x, function(x2) {
    mul_cps(y, y, function(y2) {
      add_cps(x2, y2, function(x2py2) {
        sqrt_cps(x2py2, k);
      })
    })
  });
}

We see that resulting code is torn inside-out and made positively unreadable. Each function is transformed. They all get a magic parameter k. That's the continuation. In javascript it is a function which gets the result of the operation. Somewhere deep down in the call stack k is invoked. In our example, in the CPS transform of sqrt() not shown here.

Also note that CPS transformed functions never return. They just call the continuation with the result of the calculation. This can lead to a stack exhaustion. All Javascript CPS transformers need to handle this. In Scheme this is not neccessary because all invocations are tail calls. A tail call doesn't need an additional invocation frame. In Javascript a trampoline or a similar technique is needed. Instead of invoking the continuation directly, invoke a helper and pass the result and the continuation to it. The helper runs in an endless loop always invoking and returning and avoids the stack exhaustion.

So, and why does this CPS give us the power of continuations? That is because a continuation is just something to be done next. If we always carry around this concept of something to be done next as an additional parameter k and always pass the result of the current expression to it, then we have realized this concept in code. However, as we have seen, this «always carrying around» is tedious to realize.

It's a steep price to pay, even if we let do source code preprocessor do the hard work. Why should we use continuations? It is possible to abstract control flow. Seaside, a web application framework, uses continuations to abstract away the browser's stateless request flow. User interaction can be modeled concisely - one does not think in requests anymore but in interaction flows. This is just one of the many examples of the power of the continuations. This power seems also odd and somewhat scary to many people.