Implementing threads in javascript

Neil Mix implemented a cool solution to do threading in javascript. It achieves a specific kind of multi-threading, with voluntary yielding and interleaved execution, which is different than what C++, Java or C# offer (preemptive multi-threading).

The idea is that the code for each "thread" needs to voluntarily interrupt its processing flow to let another thread execute for a while. When a thread suspends its execution, its state is saved. When the thread is later awoken, it continues its processing from where it stopped.

To understand Neil's library, you first need to learn how to use generators. Generators are a new construct in javascript 1.7 (available in Firefox 2.0) which let your write a piece of code returning a sequence of results, pausing its execution for each result and restarting from its paused state to compute the next result.

Normally, a function that receives execution control keeps it until it returns. But with generators, the execution control can be given up in the middle of the routine and later restored.
One way to look at it is that the code in the generator is dependent on the caller to call repeatedly to activate each "segment" of the processing.

Some sample code will help you grop generators (taken from Brendan Eich's quick description of generators):

• "yield" in a function makes a generator:

function count(n : int) {
   for (let i = 0; i < n; i++)
     yield i;
}

• A generator function returns an iterator, which exposes a method called "next":

var gen = count(10);
gen.next(); // returns 0;
. . .;
gen.next(); // returns 9
gen.next(); // throws StopIteration

• Iterators also support "send" and "throw" methods:

gen.send(value); // passes value back to yield
gen.throw(exception); // throws exception from yield

As you can see, generators offer much of what's needed to let our "threads" relinquish control, pause and restart, at least if our threads are single functions.
But if you need to have sub-functions called as part of the thread, generators fall short. As Neil puts it: "generators are unable to yield across multiple frames in the callstack".

This is where his library comes in. It lets you write generators which call sub-generators, and it saves the state of an entire thread, when it gets paused, as a stack of paused generators.
The framework takes care of adding a new stack frame when a generator returns a sub-generator, lets the sub-generator segments get executed, and passes the value or exception returned by the sub-generator back to the calling frame (see gen.send(value) function above).
This is called trampolining generators.

Here's a code example for a thread, when using the library. Note that "sleep" "waitForInput" and "animateUI" are themselves generators (ie. they use the "yield" keyword).

Obviously, making use of this multi-threading technique comes with a peculiar coding style, where you have to indicate explicit yield points. This approach does however avoid some of the more complex concurrency problems (atomic operations on shared state).

It is good to see how the limits of javascript getting challenged with every incremental feature added to the language. And even though I haven't used this approach and I don't know if I'm going to use it any time soon, the technique is fascinating and definitely great mental exercise.
The library code is pretty small, about 150 lines of code, and is worth reading to get a better sense of the trampoline design.