
[Guido wonders about continuations -- must be a bad night for sleep <wink>] Paul Wilson's book-in-progress has a (large) page of HTML that you can digest quickly and that will clear up many mysteries: ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_142.html Scheme may be the most-often implemented language on Earth (ask 100 Schemers what they use Scheme for, persist until you get the truth, and 81 will eventually tell you that mostly they putz around writing their own Scheme interpreter <0.51 wink>); so there are a *lot* of approaches out there. Wilson describes a simple approach for a compiler. A key to understanding it is that continuations aren't "special" in Scheme: they're the norm. Even plain old calls are set up by saving the caller's continuation, then handing control to the callee. In Wilson's approach, "the eval stack" is a globally shared stack, but at any given moment contains only the eval temps relevant to the function currently executing. In preparation for a call, the caller saves away its state in "a continuation", a record which includes: the current program counter a pointer to the continuation record it inherited a pointer to the structure supporting name resolution (locals & beyond) the current eval stack, which gets drained (emptied) at this point There isn't anything akin to Python's block stack (everything reduces to closures, lambdas and continuations). Note: the continuation is immutable; once constructed, it's never changed. Then the callees' arguments are pushed on the eval stack, a pointer to the continuation as saved above is stored in "the continuation register", and control is transferred to the callee. Then a function return is exactly the same operation as "invoking a continuation": whatever is in the continuation register at the time of the return/invoke is dereferenced, and the PC, continuation register, env pointer and eval stack values are copied out of the continuation record. The return value is passed back in another "virtual register", and pushed onto the eval stack first thing after the guts of the continuation are restored. So this copies the eval stack all the time, at every call and every return/invoke. Kind of. This is partly why "tail calls" are such a big deal in Scheme: a tail call need not (*must* not, in std Scheme) create a new continuation. The target of a tail call simply inherits the continuation pointer inherited by its caller. Of course many Scheme implementations optimize beyond this.
I'm trying to understand whether we can get away with saving just a pointer to a frame, whether we need to copy the frame, or whether we need to copy the entire frame stack.
In the absence of tail calls, the approach above saves the stack on every call and restores it on every return, so there's no "extra" copying needed when capturing, or invoking, a continuation (cold comfort, I agree <wink>). About Christian's code, we'd better let it speak for itself -- I'm not clear on the details of what he's doing today. Generalities:
... So I hope that Christian has code that saves the frame and block stacks!
Yes, but nothing gets copied until a continuation gets captured, and at the start of that I believe only one frame gets cloned.
(It would be fun to try and optimize this by doing it lazily, so that frames which haven't returned yet aren't copied yet.)
He's aware of that <wink>.
How does Scheme do this? I don't know if it has something like the block stack, but surely it has a value stack!
Stacks and registers and such aren't part of the language spec, but, you bet -- however it may be spelled in a given implementation, "a value stack" is there. BTW, many optimizing Schemes define a weaker form of continuation too (call/ec, for "escaping continuation"). Skipping the mumbo jumbo definition <0.9 wink>, you can only invoke one of those if its target is on the path back from the invoker to the root of the call tree (climb up tree like Cheetah, not leap across branches like Tarzan). This amounts to a setjmp/longjmp in C -- and may be implemented that way! i-say-do-it-right-or-not-at-all<wink>-ly y'rs - tim