Continuations

I’ve been working with continuations for the past few days. I haven’t had occasion to use them before, and must confess to finding them a little spooky. As a first impression I’d say that I like them, but find that, as with threads, buggy code that involves continuations can give rise to some truly bewildering behaviour.

Spooky

A continuation is basically a blob of code and/or data that represents all the future steps of a computation. On one level this isn’t too remarkable; most programming languages have some concept of a “main” function, and it’s easy to conceive of grabbing a pointer to this function, and calling that a “continuation” (albeit a very particular one). A program that can perform a similar operation at any point, however, is a little stranger.

Useful

The nice thing about continuations is that they make it easy for a program to schedule its own execution. In particular, a program can make its current continuation the callback associated with some asynchronous event. This technique allows you to trivially implement cooperative multitasking.

Bewildering

When continuations are used heavily (e.g. in a continuation-passing style program) they can become confusing. (For example, one has no meaningful call stack when debugging continuation code that’s been scheduled asynchronously.)

A continuation-passing style (CPS) program has its own special hazard. Calls to functions that are passed continuations should not be followed by any other instructions. There are several reasons for this:

• Instructions following the function call aren’t covered by the passed continuation; therefore, their existence violates the notion that the passed continuation represents “the rest of the computation”.
• Instructions following the function call will be executed at some unknown time relative to the instructions covered by the continuation. (In effect, you create two threads of execution when you pass a continuation to a function, and then execute more code on that function’s return.)
• If the code following the function call starts passing continuations around itself, you’ve really created a co-operatively multithreaded program, with execution switching back and forth between the threads based upon when each thread finds itself waiting for an event. This probably isn’t what you want.

Unfortunately, the “no code after a CPS call” rule isn’t particularly intuitive if you’re new to continuations. (This statement is particularly relevant if you’re porting non-CPS code.) Really unfortunately, violations of this rule, like thread bugs, don’t pop up immediately or consistently, or demonstrate much locality.

A Suggestion

I found it useful to put some “sanity checks” in my blocking functions. Since I was writing single threaded code, there should never be a process waiting for a blocking function when that function is executed.

For instance, here is a simple blocking function (and support code) that waits for user input, and returns a single character:

var bcurses = new function () {

	// Private State
	var buffer = [];

	// Private Functions
	function HandleKeyboard(ev)
	{
		buffer.push(ev.key().string);
		ev.stop();
	};

	// Functions
	this.initscr = function () {
		// Initialize the library
		disconnectAll(document, 'onkeydown');
		connect(document, 'onkeydown', HandleKeyboard);
	};

	this.getch = function (c) {
		(function test () {
			if (buffer.length)
				c(buffer.shift());
			else
				setTimeout(test, 50);
		})();
	};
}();

(This is JS code, based on MochiKit. It implements the bcurses namespace.)

To add a sanity check, we can recode it as:

var bcurses = new function () {

	// Private State
	var nwaits = 0;
	var buffer = [];

	// Private Functions
	function HandleKeyboard(ev)
	{
		buffer.push(ev.key().string);
		ev.stop();
	};

	// Functions
	this.initscr = function () {
		// Initialize the library
		disconnectAll(document, 'onkeydown');
		connect(document, 'onkeydown', HandleKeyboard);
	};

	this.getch = function (c) {
		if (nwaits)
			alert('Uh-Oh');
		nwaits++;
		(function test () {
			if (buffer.length)
			{
				nwaits -= 1;
				c(buffer.shift());
			}
			else
				setTimeout(test, 50);
		})();
	};
}();

This will fire off an (ugly) alert box if matters ever get so deranged that we have (effectively) two (or more) threads of execution. It’s better to notice that sort of thing early.