May 12, 2003

What's the point of continuations and CPS?

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)

Generally, it seems like CPS is a win. Once you've decided to have closures, you've paid most of the necessary cost for CPS.

But I don't understand your first argument -- that the caller's job is much easier if there were a single instruction for creating a continuation. Couldn't you also have a single instruction for "saving the context", without explicitly saying that it is a continuation that gets passed as an argument, and stored in the callee's lexical frame?

It seems like the _real_ value of CPS is in the compiler, which can analyze the use of continuations in order to optimize things like tail recursion. But once it did its analysis, it wouldn't have to spit out actual CPS instructions -- they would just be data structures used during flow analysis.

There also seems to be a value in continuations in the VM -- it makes the implementation of exceptions and other weird constructs pretty easy. But VM-implemented continuations don't automatically imply CPS.

Let me know what I have wrong -- all of this is kind of new to me..

Posted by: Steven at May 18, 2003 12:28 PM

Closures aren't really where CPS is a big win, it's continuations where they win. The mechanisms you need for closures only get you part of the way there, though it is an important part.

You are right when you point out that there doesn't have to be any difference in the bytecode between the CPS and normal styles--when I wrote this piece I was only starting to work over to CPS, and I'd not given much thought to the old scheme, nor its issues. A single op to create a calling context is a sensible thing as well.

FWIW, while I didn't make this clear, I consider CPS first and foremost a VM/compiler trick, one that gets hidden from the user unless they try really, really hard to get to it. (And I'm not sure I'd want to expose it even then, though I can see good reasons to do so)

Posted by: Dan at May 18, 2003 05:40 PM

I'm looking to build a simple parser, and I was going to do it in C, but perhaps (since it is a toy project), I could do it in parrot. Do you have a simple code example in parrot showing how continuations actually work?

Posted by: Bings at April 22, 2004 03:40 PM

I'm looking to build a simple parser, and I was going to do it in C, but perhaps (since it is a toy project), I could do it in parrot. Do you have a simple code example in parrot showing how continuations actually work?

Posted by: Bings at April 22, 2004 03:40 PM