Gems in Scheme (part 2)

August 17th, 2009

1

In my last post I described some of the use of call-with-current continuation for non-local or other sorts of dynamic exits. These uses of call/cc are similar to exceptions in many other languages, or a catch/throw mechanism.

However, these mechanisms establish continuations which have only limited extent: once the call to catch returns, you can no longer throw to it. It was the genius of the early Scheme inventors to realize that this was an artificial restriction, and call/cc was born.

My last post described a hypothetical table data structure which comes with a procedure “each” that calls a procedure for each element in the table, just as the normal “for-each” procedure does with lists. There we considered how to use continuations to abort the iteration. The model of iteration that “each” used was familiar to Scheme programmers:

But sometimes a different style of iteration is desired, in which a cursor is first created, and then repeatedly invoked to return successive elements of the table. One such interface looks like this:

If tables are just lists, this is easy to implement:

Each call to make-cursor instantiates a new C (the cursor itself), and returns a procedure which simply walks C down the list and returns each successive car of the list.

But this required knowing that tables were lists. Suppose (as in the style of my last post) the interface we have been given has the iterator “each”, and we want to have a cursor-style implementation? Here is where call/cc fits in. What we will do is use call/cc to record the state of the “each” call in progress. We want a function which looks like this:

to RETURN, and then reset “iteration” to a procedure to do the next step.

See how this works? The first time, we call each, which calls our procedure, which saves away its continuation and returns the element. The next time, we call the saved continuation from the last time, which sets the new return procedure (again, notice that it’s the argument to iteration) which calls our procedure for the next element, which saves away its continuation and returns the element. Eventually each returns; at that point we just return #f, and leave “iteration” alone: each time we invoke it, “each” returns again, and we return #f.

So our make-cursor routine just looks like this:

Notice what’s happened. It’s well-known how to turn a cursor-style iteration into a for-each-style iteration:

But now we also have a way to turn a for-each-style iteration into a cursor-style iteration.

One way to think about this sort of make-cursor is that we have two separate threads of control; one which runs inside the each call, and the other which invokes the cursor. Each thread saves its state with call-with-current-continuation, and then invokes the saved state of the other thread.

Indeed, this use of call/cc in order to implement lightweight threads is so important that it will be the topic of the next post in this series.

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

Related Posts

• Gems in Scheme (Part 3)
• Gems in Scheme
• Stateless Tests in a Stateful Protocol

Author