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.

17 October 2005

Exciting and Depressing

Ever have something happen that's terribly exciting, as long as you don't think about it too much? I just had a mental breakthrough with my integrators: I realized a way to think about what's going on that makes everything perfectly clear. Then I implemented this in about 174 lines of Bigloo code. "That's great!" you say. I agree completely. Unfortunately, if I can't quite remain lost in the moment, I think of two mildly depressing things:
  1. Why didn't I think of this sooner? I've spent the last few months playing around with these things, and then I figure out that pretty much everything I was doing before was wrong in the space of two days---and it's (in retrospect) obvious!
  2. Someone else has to have had this thought! I'm almost scared to do a literature search tomorrow (time for bed now)---I'm sure I'll find half a dozen papers describing this technique and explaining why it's not better than what everyone else has been doing, etc (worst case) or that other people have had this thought and it's got promise for future implementations (much better, but still a bit of a bummer).

However, I'm still terribly excited! 174 lines!! It's so simple!!! This is great!!!!

13 October 2005

Shared State in PLT Scheme's Swindle

I just spent about six hours debugging a version of my integrator that runs in PLT Scheme (got tired of not having the class creation options available at runtime in Bigloo) because of a shared state problem. If you define a Swindle class with the slot option :initvalue <value> then <value> is only evaluated once; every object of this class shares the same value. Not good if you want to have mutable state! The thing to use is :initializer <thunk>. I wish there was an :initform slot option, like in the real CLOS.