Continuations are the new threads
Friday, June 1st, 2007I've always thought that continuations are the right answer to many if no all the network-programming problems.
What are continuations?
A continuation represent the state of execution of a function: all the local variables and the instruction pointer (the last line executed).
(Update: At least: there can be many kind of continuations. Other than the local variables, it's possible to store the state of the entire thread/process/stack)
What are them used for?
You can interrupt the execution of a function and resume it later.
This can be useful to create "generators": iterators made simple.
A generator looks like this:
The function next return the next element in the arr array every time is called.
When you call the function you resume the continuation, so the execution will resume from the yield.
If you want to implement an iterator like that without generators you'll have to explicitly unroll the for loop.
The resulting code will be surely less readabe.
Like:
-
function next() {
-
if(this.current == null) this.current = 0;
-
this.current++;
-
if(this.current> arr.lenght) {
-
this.current = 0;
-
return null;
-
}
-
retrun arr[x];
This can get really worse for every non-trivial iterator (eg: tree traversal).
Another nice use of continuations is to generate cooperative threads.
They are different from standard threads because they can't be stopped, they should cooperatively stop.
For example you can do:
-
function process() {
-
sendConnectRequest();
-
yield;
-
if(!this.connected) return false;
-
sendLoginRequest();
-
yield;
-
sendMessage();
-
yield;
-
trace("msg received: " + this.response);
-
}
The process function return the control to the calling function every time it has to do an asynchronous operation.
Without continuations you'll have to do:
-
function process(onComplete) {
-
connect(function (connected) {
-
sendLoginRequest( function(logged) {
-
sendMessage( function (response) {
-
trace("msg received: " + response);
-
onComplete();
-
}
-
}
-
}
-
}
As you can see we have used closures in a Continuation Passing Style:
Every time you have to do an asynchronous operation, you'll have to pass a function (a callback) that will be called when the operation is done.
Without closures the code will look even worst, this is why recently there is a great buzz about closures in the java world.
But, what have in common continuations and threads?
A continuations-like style of programming (but without continuations) is possible only using threads.
However, threads are the heavier and most problematic way to handle the I/O waitings. (see: 10Kproblem)
You have not only to deal with concurrency problems with read/write variables, but you have to block an entire thread for every I/O operation.
A better way is to use asynchronous events, like in the last two example. But of the two, which one do you prefer?
If your answer is like mine, take a look to:
- Jetty servlet engine, it support a limited form of one shot continuations: the function is re-executed from the beginning, what is restored is only the HTTP connection state.
- RIFE continuations, it's a bytecode-level implementation in Java, these are real continuations
- NarrativeJS, a precompiler that create a simple form of continuations in Javascript: using the
->operator the execution can be resumed from that point. - Update: Torsten Curdt suggest Javaflow, a continuation implementation that seems really interesting, he offers some tutorials on his blog too
Jetty scratched only the surface of what is possible with continuations, while with RIFE it's possible to develop highly concurrent servers using cooperative sessions instead of threads (some >10000 connections instead of 1000). See: Mina Java-NIO library, Perl POE, Mina-Mule.
A server that uses continuations, will allow the simple and linear programming style of blocking-synchronous operations while using non-blocking ones. With a huge increment in performance.
In the client side, the most interesting is NarrativeJs, that use an approach that can be adapted to every language:
it unroll loops and transform all local variables in object variables to generate his quasi-continuations.
became:
-
function boo(){var njf1=njen(this,arguments);nj:while(1){switch(njf1.cp){case 0:
-
alert("start");njf1.pc(1,null,
-
sleep,[30]);case 1:with(njf1)if((rv1=f.apply(c,a))==NJSUS){return fh;}
-
alert("end");break nj;}}}
The code looks ugly but it is so to preserve line numbers.
With narrativeJs you can do complex animations in a simple, linear way:
-
waitForClick->(theButton);
-
animate->(theButton, "left", 200, 1000, 20);
-
-
theButton.innerHTML = "go left";
-
-
// move the button to the left (again note the blocking operations)
-
waitForClick->(theButton);
-
animate->(theButton, "left", 0, 1000, 20);
or:
-
document.getElementById("myElem").innerHTML = fetch->("http://www.url.com/");
Really interesting now that Flash and Ajax are pushing asynchronous operations to the masses.
Will we say goodbye to events, and maybe to threads as we know now?
