Continuations: Arc vs Java

What's a continuation? Despite much googling on the topic, continuations remained opaque to me until I stumbled upon Sam Ruby's amazingly excellent Continuations for Curmudgeons. Please read that article instead of this, it will be much more useful.

Here's a really fast description of continuations in java terms. Imagine in java we had first-class functions (like javascript). In other words, we could say

Function p = myObject.toString // no parens!

// later ...
p(); // calls myObject.toString()

Now, let's jump a little further: imagine "return" is not just a keyword, but it is a special built-in function that is magically available in the body of every method, just like "this" and "super" are. And we have first-class functions. So, we can write

public String foo(int n) {
  this.cc = return;
  return("foo " + n); // "return" is a function
}


public void bar() {
  System.out.println("I have received " + foo(10));
  System.out.println("end of bar");
}

...

bar(); // displays "I have received foo 10", then "end of bar"
cc("haha!") // displays "I have received haha!", then "end of bar", forever

With the call to cc you are re-entering bar at the instruction immediately after the call to foo(), and not only that, when bar returns, it will return to whoever its caller was when it was invoked the first time, and so on all the way up the stack. Not only that, the stack prior to the call to cc is completely discarded and gc'd (unless, of course, there's a stored continuation somewhere pointing to that stack).

Being a java dude, this was a shocking revelation for me. Worse than goto, a total abomination, a devilish contortion of everything that is right and proper in design.

But I was undeterred. Sam Ruby's article gave me what I needed to implement continuations in rainbow, although it meant re-writing everything. Because java doesn't allow me just store "return", I need to explicitly handle a stack in java code, so that I can "return" to it at any point, just in case someone decides to store it in a continuation. If the stack is stored in this way, it is not subject to garbage collection, so the entire stack - local variables, parameters, the stacktrace - is preserved.

So when rainbow invokes an arc function, it creates a new continuation for the invoked function, and passes the new continuation the current continuation, so the new continuation knows where to return to when it's done.

This results in java code written in Continuation-Passing style, or CPS. CPS and continuations are separate concepts, but feel the same. Here is a quick CPS tutorial in Java. Normally we write this:

 int calculateSomething(int p, int q) {
   return p * q;
 }

 ...

 int x = calculateSomething(p, q);
 System.out.println("result is " + x);

Trivial, no? Here's the same thing in CPS:

 void calculateSomething(int p, int q, Continuation c) {
   c.receive(p * q);
 }

 ... 
 
 Continuation c = new Continuation() {
  public void receive(Object o) {
   System.out.println("result is " + o);
  }
 }

 calculateSomething(p, q, c);

The idea is that your methods must never return a value, they should instead pass the intended return value to a "Continuation" parameter destined to receive it. The responsibility of the Continuation object is to continue whatever was in progress. Here, the Continuation object calls System.out.println, something that was achieved in the second line of the original version. So why would you want to write in CPS? In Java: you wouldn't, it's a nightmare, unless you happen to be writing a Lisp interpreter.

One difference between CPS and true continuations is that a true continuation never returns: the caller's stack is discarded, and the stack in scope for the called continuation is resurrected. CPS in java is a total hack. In the example above, any code following "c.receive(p * q)" is meaningless. The call to receive must be the last statement executed in the method - it's replacing "return". Using CPS in java, it's easy either to forget to invoke receive, or to forget to return immediately afterwards.

A slight problem for rainbow is that CPS functions never return: the last instruction is a call to the previous continuation. So, normally, the java stack grows and grows. To avoid this, rainbow executes arc in a while(true) loop. Each function invocation simply stores a reference to the function to invoke along with a reference to the caller and the lexical context - and then returns. The java stack unwinds, the loop loops, and the waiting function gets executed.