Gems in Scheme (Part 3)

October 19th, 2009

0

In my last post I described the use of call-with-current-continuation to implement co-routines, thus inverting for-each-style iterations into cursor-style iterations. I noted that this looks very similar to using threads.

Indeed, continuations can be used to implement light-weight, cooperatively scheduled, threads extremely easily.

Imagine that we maintain a list of procedures, each of which represents computation-to-be-performed. It is convenient to be able to schedule work by simply adding it to this list. Then, when a given bit of computation finishes, we simply pull the next item from the list and execute it.

Note that the call to next-computation is a tail call, so we don’t build up a big stack of these things. Each computation is expected to complete by calling (yield) in turn. This is still incomplete; for example, it does not address how to idle the processor when there is no computation to be performed. But it expresses the basic idea.

So far this is not threads, but simply a convenient way to handle computations that need not interrelate. However, if we add a mechanism for these routines to block, we have created threads. For a routine to block, it needs to do three things. First, it needs to capture its current execution state in such a way that it can be restarted when the block completes. Second, it needs to save that execution state in such a way that it can be continued later. And third, it needs to stop executing—the processor needs to be handed over to something else. And, we need a way to wake up blocked threads.

Imagine we already have the list-of-procedures model of scheduling computation described above. This handles the third step of blocking, by simply calling yield above.

Lets suppose that each blocked thread is identified by a “tag”, and woken up when that tag is signaled. A blocked thread will be a cons of two elements: the tag, and a procedure which, when executed, will resume the thread where it blocked.

This makes clear how to handle the second part of blocking: recording the blocked state:

All that remains is how to generate the restart-proc. But that is easy: it’s just a simple invocation of call/cc. So we combine the three steps thus:

One minor detail remains. The saved continuation expects an argument, which is not being supplied when it’s executed. So we need to wrap it appropriately. That is, we must fix the above to say:

And that’s it. Note that the “stack management” aspect of threading is here managed exactly by the “stack copying” character of call/cc: one way to think of call/cc, is that it copies the entire execution stack and boxes it up inside a suitable object. (Of course, good Scheme systems have many clever techniques for avoiding the obvious overhead that would entail, but the semantics remain the same.)

We use procedures just like these here to manage the complex multi-threaded servers running our backend database and communication operations, with three extra features. First, we allow more than one tag, and match them with generic procedures instead of always using the same eq? procedure. And second, we have a facility for an “idle” computation which executes when nothing else needs to be done, and which issues an epoll_wait or select system call. Finally, we have a “timeout” tag which needs to interact correctly with the epoll_wait/select call. But those are simple icing on the cake; the fundamental work is just as it is seen here.

Counting extensive documentation comments, our call/cc version of lightweight threads is 283 lines of Scheme code in sixteen procedures.

Tagged with: call/cc, continuations, control-structures, threads

Related Posts

• Gems in Scheme (part 2)
• Gems in Scheme
• Stateless Tests in a Stateful Protocol

Author