Continuations for Javascript

NOTE! There is nothing yet, just this README file.

What are continuations? What does continuation.js do?

A continuations reifies (i.e. makes explicitly formulated and addressable) a point in the execution of software. Almost all languages have means to manipulate the order of executing instructions, namely control structures like if statements, loops, return statements, etc. With setjump in C one can "return" out of several levels of nested function calls, but not jump freely from function to function: if the function in which setjmp() was called has returned, a jump is not possible. Continuations can jump back and therefore are strictly more powerful than setjump points.

Some languages offer first-class continuations, for example Scheme with call-with-current-continuation. They can be internally implemented with function frame stack capture and switching. For other languages continuations can be grafted on with continuation passing style, in which the functions are modified to pass an additional parameter k, the current continuation; the return expressions are modified inside-out to make the evaluation order explicit and finally k is invoked. With CPS the function never returns, so in non-tail-call languages a trampoline is additionally neccessary. A trampoline repeatedly invokes passed-in functions in a loop to avoid the nesting of their calls. With neither a trampoline nor tail call optimization stack overflow occurs very soon.

continuation.js offers a CPS transform. CPS transforms are difficult in the sense that they turn functions inside-out and produce unreadable code. But in Javascript they are easier than in C because Javascript knows closures.

continuation.js also provides a trampoline, because Javascript doesn't have tail-call optimization.

An example why continuations are useful: sleep

NOTE! I am not sure whether this really works. It is just an idea which I need to test first.

One of the things which baffles Javascript newbies is the lack of a sleep() function and the difficulty to implement it in a good way. php.js' usleep() uses a busy loop to sleep. A very bad idea. I suspect that it is possible to implement it with continuations and a jump to the idle loop (with a continuation of the idle loop).

function sleep(seconds) {
    var cc = new Continuation()
    if (!cc instanceof Continuation) return /* sleep() ended */
    setTimeout(cc, seconds * 1000)
    Continuation.idle() /* go to the idle loop */
}

where new Continuation() delivers a delimited continuation cc whic can be invoked like this cc() or passed to setTimeout like a function; and where cc instanceof Continuation is true if the continuation just has been created, i.e. a «goto» to the continuation has not yet happened and finally where Continuation.idle is a continuation for the idle loop.

We see we can (perhaps) implement the control structure "sleep" with the help of continuations only. This also shows why continuations are important for Node.js: continuations can encapsulate complicated asynchronous control structures.

How does continuation.js work?

There is a CPS transform function. It takes a function or its source code and applies a CPS transformation to it. There is also a trampoline and a function to emulate Scheme's call/cc, and also a few additional helper functions.

The CPS transform parses the function and walks the parse tree to replace the return expressions by their CPS transform: Do these steps:

1. Parse the function source code and produce a simplified parse tree (with nodes relevant to the CPS transform: function call arguments; and in return expressions either expressions expr, nested CPS function calls func or operators op).

2. Append the argument k to the function's arguments.

3. For all return statements post-order walk and build the transformed expressions incrementally using these rules:

   1. For an expression expr

      1. empty → CPS(k, expr)
      2. CPS(…, k) → CPS(…, function k(i++) { return CPS(k, expr) })
      3. CPS(k, …) doesn't occur

   2. For a nested CPS function call func

      1. empty → CPS(func, k)
      2. CPS(…, k) → CPS(…, function k(i++) { return CPS(func, i, k) })
      3. CPS(k, …) → CPS(func, …, k)

   3. For an operator op

      1. empty doesn't occur
      2. CPS(…, k) → ??? Todo
      3. CPS(k, …) → CPS(k, node-left op node-right)

   The CPS() function calls are thunk trampoline invocations: the first argument is the function to be called by the trampoline, the following arguments its arguments. k is either the first argument or the last or the last argument is a function invoking k directly or indirectly through the trampoline. This ensures the thunk closure chain in which each thunk is the current continuation exactly when the trampoline invokes the thunk.

4. Replace the return expression with the CPS transform incrementally built.

function sum(n) {
  if (n == 0) return 0
  return sum(n - 1) + n
}