Fake threads (was [Python-Dev] ActiveState & fork & Perl)

[Tim Peters]

[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