Guido van Rossum writes:
Perhaps it would help to explain what a continuation actually does with the run-time environment, instead of giving examples of how to use them and what the result it?
This helped me a lot, and is the angle used in "Essentials of Programming Languages": Usually when folks refer to a 'stack', they're refering to an *implementation* of the stack data type: really an optimization that assumes an upper bound on stack size, and that things will only be pushed and popped in order. If you were to implement a language's variable and execution stacks with actual data structures (linked lists), then it's easy to see what's needed: the head of the list represents the current state. As functions exit, they pop things off the list. The reason I brought this up (during a lull!) was that Python is already paying all of the cost of heap-allocated frames, and it didn't seem to me too much of a leap from there.
1. All program state is somehow contained in a single execution stack. Yup.
2. A continuation does something equivalent to making a copy of the entire execution stack. Yup. I.e. are there mutable *objects* in Scheme? (I know there are mutable and immutable *name bindings* -- I think.)
Yes, Scheme is pro-functional... but it has arrays, i/o, and set-cdr!, all the things that make it 'impure'. I think shallow copies are what's expected. In the examples I have, the continuation is kept in a 'register', and call/cc merely packages it up with a little function wrapper. You are allowed to stomp all over lexical variables with "set!".
3. Calling a continuation probably makes the saved copy of the execution stack the current execution state; I presume there's also a way to pass an extra argument. Yup. 4. Coroutines (which I *do* understand) are probably done by swapping between two (or more) continuations. Yup. Here's an example in Scheme:
http://www.nightmare.com/stuff/samefringe.scm Somewhere I have an example of coroutines being used for parsing, very elegant. Something like one coroutine does lexing, and passes tokens one-by-one to the next level, which passes parsed expressions to a compiler, or whatever. Kinda like pipes.
5. Other control constructs can be done by various manipulations of continuations. I presume that in many situations the saved continuation becomes the main control locus permanently, and the (previously) current stack is simply garbage-collected. Of course the lazy copy makes this efficient.
Yes... I think backtracking would be an example of this. You're doing a search on a large space (say a chess game). After a certain point you want to try a previous fork, to see if it's promising, but you don't want to throw away your current work. Save it, then unwind back to the previous fork, try that option out... if it turns out to be better then toss the original.
If this all is close enough to the truth, I think that continuations involving C stack frames are definitely out -- as Tim Peters mentioned, you don't know what the stuff on the C stack of extensions refers to. (My guess would be that Scheme implementations assume that any pointers on the C stack point to Scheme objects, so that C stack frames can be copied and conservative GC can be used -- this will never happen in Python.)
I think you're probably right here - usually there are heavy restrictions on what kind of data can pass through the C interface. But I know of at least one Scheme (mzscheme/PLT) that uses conservative gc and has c/c++ interfaces. [... dig dig ...]