20 October 2005

Continuations in Unfriendly Environments

I'm sure many people already have seen the paper (and probably attended the conference), but have a look at this paper from Greg Pettyjohn, John Clements, Joe Marshall, Shriram Krishnamurthi, and Matthias Felleisen! It describes a technique that can be used to implement continuations in unfriendly environments where stack inspection is not available (i.e. portable ANSI C, JVM, .NET, etc.) The great thing about the technique (as opposed to, say, the CPS conversion in Chicken) is that most functions can still use the standard calling conventions and runtime stack of the host language or environment.

Here's my (probably weak) understanding of how it works: when a continuation is captured a chain of exceptions gets propagated up the stack. At each "stop" on the way up the stack, an exception handler cons-es up a closure which will continue the function whose frame is active at that point. When the exception reaches the top level of the stack, the frames are packaged up as the continuation. Activating the continuation simply calls the closures in order to resume the saved computation where it left off. All the implementation needs to provide is some way to unwind the stack, stopping at each frame along the way. In C, it would be a longjmp/setjmp; in Java it would be catch/throw; in .NET catch/throw.

There is an example with more code (and less math) here, too.

No comments: