Cedric (it's amazing who you can find linking to you via Technorati) noted, twice, that while he understands continuations and CPS, he doesn't much see the point. And that brings up a good question--what is the point? What does it buy you?
Well, with exposed continuations, it's reasonably simple. If a language has them, you can put together any sort of control flow mechanism you want. Feel like having a perl-style
foreach that iterates over a list of variables and don't have one? Build it. And for the language implementor they're pretty nice too, as once you get them done you don't actually have to implement any other form of control structure, just convince the compiler to emit the right variant of continuation use under the hood. (Of course, it's not necessarily the most efficient way to build things, but it does get you going quickly, especially if you're not that fond of building language engines)
Doing CPS, though, can make implementation a lot easier, at least for some languages.
Now, let's be up front--using CPS for a really low level language like C or C++ would be counterproductive, and that's fine. Don't use it there, as it'd be kind of stupid. (Not that you couldn't, mind, just that there'd be little point given the thrusts of the languages) There are places, though, where going with CPS makes things easier, less error-prone, and potentially more flexible for backwards/forwards-compatibility.
Consider, for a moment, Parrot. This is a VM designed to run Perl, Python, Ruby, and suchlike languages. We have lexical variables, which means we have to swap lexical scopes in and out as we make function calls. We have lexically scoped nested global namespaces, which once again need to be swapped in and out as we make function calls. We've got dynamically loaded opcode functions and, more importantly, scoped opcode function tables. (Which means that two different pieces of bytecode may both use opcode # 1034, but it means something different in each piece. Long story, makes sense, ask later) We may well have scoped interrupt levels, though probably not. We also have quite a few stacks.
All that stuff needs to be saved and restored. We do caller-save, so the code making the function call will have to save off the important state. The called function isn't off the hook--it still needs to track the stacks, of which we have quite a few, and make sure that there's nothing extra on them.
Or... do we?
That's where CPS comes in, and makes things just a whole heck of a lot easier. At least for parrot.1 Consider all the saving and restoring. Compilers have to emit that code. Not, in itself, a big deal, but still, it's code that needs to be spat out. More importantly, consider the possibility for future expansion. What if we do decide to have lexically scoped filehandle filters, say. (Why? I dunno. Work with me here) If we use CPS, and more importantly if we have a single instruction to build the continuation object, then we're essentially future-proof(ish)--it doesn't matter that we're running old bytecode that doesn't know anything about lexical filehandle filters, the engine does and the CPS thingie builder will Do The Right Thing.
It also makes life in the subroutine easier. Since the stacks need restoring, that means we need to track how deep we are and pop off the extra, or have some sort of "mark for later undo" function. If we just do continuations it's part of the call--we're already passed in the mark we're interested in. (And, going CPS means we're probably not being very stackish, more going with a frame system, except for the control stack that needs to track runtime exception establishment. Which is, in itself, a bit of a pain with continuations, but that's a separate issue)
So, the annoying stuff is boiled down to two seemingly harmless instructions--makecontinuation and invokecontinuation. Makes emitting code (both by hand and machine) easier, condenses the code stream, and generally makes things more clean from the outside. Yeah, there are continuations, but they're well-contained.
The one big downside is that it might make python emulation more difficult, but I think we can work on that one. Pie is, after all, involved.
The short answer to "Does this mean much to me" is "No, not unless you're writing an interpreter engine, or generating code targeting one that uses CPS." Which is fine. It's nice to have things you don't have to bother with. :)
1 That is, assuming we do CPS, which we don't right now. Though that may well change.Posted by Dan at May 12, 2003 12:21 AM | TrackBack (0)