April 01, 2003

Continuations and VMs, part 2

If you haven't yet, read past this entry to the next one discussing continuations, then come back. Don't worry, I'll wait.

Now that you've done that, let's talk about where continuations make things interesting for VM implementation.

Since continuations are closures, that means that allocating variables on the stack is somewhat problematic--it's effectively impossible with a true, one-chunk, contiguous stack. It can be done if the system is using a linked call frame system rather than a stack, if the frames are garbage collected and there's proper copy-on-write magic added in the right spots, but it's generally easier to just go with a full lexical scratchpad deal.

Call stacks in general are a bit of an issue with continuations, since we may need to put them back in place at some point. Systems like .NET and the JVM use a single contiguous chunk of memory for their stack. As we talked about earlier, that makes calling and returning from subs faster. But to take a continuation with a system like this means stopping and making a full copy of the stack, since we may have to put it back later. With a call frame system, if there are only backlinks all you need to do is grab a handle to the current frame and you're set. Either way you need a garbage collection system of some sort to clean up after the stack chunks.

The need to copy the stack is the big killer here. Ignoring everything else, the need to snapshot the stack immediately kills any possibility of using the system control primitives with .NET and the JVM, since you just aren't allowed to do that. (You could, if you were clever, write an extension to either with the C interface they have, but that immediately makes your code platform and interpreter dependent, not to mention unsafe. And really, really dodgy, since this is one of those things you're just Not Supposed To Do) If you can't use the system control primitives it means you need to do it by hand, which is very expensive. It also makes jumping across 'real' code (that is, code that runs normally on the JVM or .NET, rather than with your new wacky control primitives) dicey, since a continuation can't be passed across the 'real' code.

FWIW, that's a problem with Parrot as well--continuations can't pass across a parrot->C->parrot boundary, since we can't restore the C stack. That's less of an issue, though, since that sort of transition's not as likely, as code generally stays on one side or the other of the C fence, and so there won't often be reasons to pass continuations across it.

Languages that just take complete control of a system don't generally have this problem as you never leave them, but that's a matter for a different day.

Posted by Dan at April 1, 2003 05:49 PM | TrackBack (3)

If a problem exists that continuations can't pass across a parrot->C->parrot boundary, does that mean that there are cases where exception handling won't work?

Posted by: Dale Martenson at April 3, 2003 11:30 AM

Nope. There's always a default exception handler for any interpreter entry, so if you go parrot->C->parrot and throw an exception in the inner parrot invocation, it'll just abort out and return an error to the C code, which can then do what it needs to, possibly aborting itself and passing an exception up the chain.

This could be a problem if we had restartable exceptions by default, which I'd do with continuations, but we don't, so it's not an issue. (Though it could be if someone went and built a restartable exception class)

Posted by: Dan at April 3, 2003 01:36 PM

> FWIW, that's a problem with Parrot as well--continuations can't pass across a parrot->C->parrot boundary, since we can't restore the C stack.

Actually, it's easy to do that in C using longjmp, which does exactly that. POSIX even supports getcontext/setcontext functions that do a bit more bu t are useful for this.

The biggest problem is creating a new stack for C - there are quite portable solutions available for this.

As a proof-of-ceoncept, the Coroutine and Continuations package for perl5 is able to save/restore C stacks.

If parrot will not support this, I wonder how toolkits like Tk or Gtk+ will ever be implemented for perl6, as they require callbacks (and indepdnent C stacks in case of continuation switches).

Posted by: Marc Lehmann at July 29, 2004 08:41 PM