2006-09-27
Futures and Promises in Javascript
The Alice programming language has some nice concurrency features to facilitate dataflow programming. Futures and Promises allow performing computations and having threads block waiting for the results of those computations in an safe, predictable manner.
There have been discussions in the Narrative Javascript group about how to implement this sort of functionality on the browser client side. Given client side threads, it's fairly easy to implement. I'd done some work previously on implementing client side threads with Narrative Javascript but to try out these ideas I took a slightly different approach. Narrative Javascript changed the internals recently and I couldn't use the manually written CPS transformed functions like my previous threading implementation. This time I reimplemented things using the 'notifier' functionality that it has been replaced with.
For simple threading, instead of writing a scheduler I that has a queue of continuations to resume I just pass everything on to Javascript's 'setTimeout' function:
function Process() {
this.pid = pid_count++;
this.mailbox = new Queue();
this.blocked = false;
}
Process.prototype.resumeAfter = function(func, ms) {
var p = this;
setTimeout(function() { self = p; func(); self = false; }, ms)
}
Process.prototype.resume = function(func) {
this.resumeAfter(func, 10);
}
function concede() {
var n = NjsRuntime.createNotifier();
self.resume(n)
n.wait->()
}
function sleep(ms) {
var n = NjsRuntime.createNotifier();
self.resumeAfter(n, ms)
n.wait->()
}
function spawn(func) {
var n = NjsRuntime.createNotifier();
var p = new Process();
p.resume(function() { func(); n(); });
n.wait->()
return p;
}
A 'future' is just a spawned thread that updates an object when it is complete. A process can block waiting for the result of the future. For this quick example I poll the object to see if it has completed, and give up a timeslice using 'concede' if it hasn't. In an actual framework I'd rewrite this to not poll, but instead to be notified when it is complete - I just wanted to prove the concept first:
function future(func) {
var f = {}
f.finished = false
spawn->(function() { f.result = func->(); f.finished = true; })
return f;
}
function value(f) {
while(!f.finished) {
concede->();
}
return f.result;
}
An example of how this can be used using a 'fib' calculation:
function fib(n) {
concede->()
if(n==0) {
return 1;
}
else if(n==1) {
return 1;
}
else {
return fib->(n-1)+fib->(n-2);
}
}
function test() {
var f1 = future->(function() { return fib->(5); })
var f2 = future->(function() { return fib->(6); })
print(value->(f1) + value->(f2))
}
Two threads are spawned as futures and then the results are used and printed. 'print' is a simple function to display the results in a div on the html page. If the threads have not completed then the process blocks until they are and the results provided.
Promises are implemented in a very similar manner:
function promise() {
var p = {}
p.finished = false;
return p;
}
function fulfill(p, value) {
p.result = value;
p.finished = true;
}
function test2() {
var p = promise();
spawn->(function() { var v = value->(p); print("Thread 1 complete: " + v); });
spawn->(function() { var v = value->(p); print("Thread 2 complete: " + v); });
spawn->(function() { var v = value->(p); print("Thread 3 complete: " + v); });
fulfill(p, 42)
}
Here I spawn three processes waiting on a single promise variable. When that promise is fulfilled the three threads resume and display the values.
You might notice that the process object has a 'mailbox' - this is for Erlang style message passing which I've also implemented. Here's how the lightweight message passing code looks:
function test3() {
var p1 = spawn->(function() {
var m = receive->();
print(m[1]);
send->(m[0], "From p1!")
})
var p2 = spawn->(function() {
send->(p1, [ self, "From p2" ]);
print("p2 sent to p1");
var m = receive->();
print(m);
})
I think this implementation of threading using Narrative Javascript is a bit cleaner than my last implementation since it passes off most of the work to the browser's setTimeout function - and there's less code which is always good. It also uses the standard Narrative Javascript API rather than taking advantage of the internal structure of the generated code.
I'm rewriting the promise and future code not to use polling and tidying it up and I'll make the code and a live example available here over the next few days.
