[GvR]
... 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?
Paul Wilson (the GC guy) has a very nice-- but incomplete --intro to Scheme and its implementation: ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_toc.html You can pick up a lot from that fast. Is Steven (Majewski) on this list? He doped most of this out years ago.
Here's a start of my own understanding (brief because I'm on a 28.8k connection which makes my ordinary typing habits in Emacs very painful).
1. All program state is somehow contained in a single execution stack. This includes globals (which are simply name bindings in the botton stack frame).
Better to think of name resolution following lexical links. Lexical closures with indefinite extent are common in Scheme, so much so that name resolution is (at least conceptually) best viewed as distinct from execution stacks. Here's a key: continuations are entirely about capturing control flow state, and nothing about capturing binding or data state. Indeed, mutating bindings and/or non-local data are the ways distinct invocations of a continuation communicate with each other, and for this reason true functional languages generally don't support continuations of the call/cc flavor.
It also includes a code pointer for each stack frame indicating where the function corresponding to that stack frame is executing (this is the return address if there is a newer stack frame, or the current instruction for the newest frame).
Yes, although the return address is one piece of information in the current frame's continuation object -- continuations are used internally for "regular calls" too. When a function returns, it passes control thru its continuation object. That process restores-- from the continuation object --what the caller needs to know (in concept: a pointer to *its* continuation object, its PC, its name-resolution chain pointer, and its local eval stack). Another key point: a continuation object is immutable.
2. A continuation does something equivalent to making a copy of the entire execution stack. This can probably be done lazily. There are probably lots of details.
The point of the above is to get across that for Scheme-calling-Scheme, creating a continuation object copies just a small, fixed number of pointers (the current continuation pointer, the current name-resolution chain pointer, the PC), plus the local eval stack. This is for a "stackless" interpreter that heap-allocates name-mapping and execution-frame and continuation objects. Half the literature is devoted to optimizing one or more of those away in special cases (e.g., for continuations provably "up-level", using a stack + setjmp/longjmp instead).
I also expect that Scheme's semantic model is different than Python here -- e.g. does it matter whether deep or shallow copies are made? I.e. are there mutable *objects* in Scheme? (I know there are mutable and immutable *name bindings* -- I think.)
Same as Python here; Scheme isn't a functional language; has mutable bindings and mutable objects; any copies needed should be shallow, since it's "a feature" that invoking a continuation doesn't restore bindings or object values (see above re communication).
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.
Right, except "stack" is the wrong mental model in the presence of continuations; it's a general rooted graph (A calls B, B saves a continuation pointing back to A, B goes on to call A, A saves a continuation pointing back to B, etc). If the explicitly saved continuations are never *invoked*, control will eventually pop back to the root of the graph, so in that sense there's *a* stack implicit at any given moment.
4. Coroutines (which I *do* understand) are probably done by swapping between two (or more) continuations.
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.
There's much less copying going on in Scheme-to-Scheme than you might think; other than that, right on.
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.)
"Scheme" has become a generic term covering dozens of implementations with varying semantics, and a quick tour of the web suggests that cross-language Schemes generally put severe restrictions on continuations across language boundaries. Most popular seems to be to outlaw them by decree.
Continuations involving only Python stack frames might be supported, if we can agree on the the sharing / copying semantics. This is where I don't know enough see questions at #2 above).
I'd like to go back to examples of what they'd be used for <wink> -- but fully fleshed out. In the absence of Scheme's ubiquitous lexical closures and "lambdaness" and syntax-extension facilities, I'm unsure they're going to work out reasonably in Python practice; it's not enough that they can be very useful in Scheme, and Sam is highly motivated to go to extremes here. give-me-a-womb-and-i-still-won't-give-birth-ly y'rs - tim