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

[Guido van Rossum]

[Tim]
> "stateful iterative process" is a helpful characterization of where these
> guys can be useful!  State captured in variables is the obvious one, but
> simply "where you are" in a mass of nested loops and conditionals is also
> "state" -- and a kind of state especially clumsy to encode as data state
> instead (ever rewrite a hairy recursive routine to use iteration with an
> explicit stack?  it's a transformation that can be mechanized, but the
> result is usually ugly & often hard to understand).

This is another key description of continuations (maybe not quite
worth a hug :).  The continuation captures exactly all state that is
represented by "position in the program" and no state that is
represented by variables.

But there are many hairy details.  In antiquated assembly, there might 
not be a call stack, and a continuation could be represented by a
single value: the program counter.  But now we have a call stack, a
value stack, a block stack (in Python) and who knows what else.

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 regular Python, the frame stack also contains local variables.
These are explicitly exempted from being saved by a continuation.  I
don't know how Christian does this, but I presume he uses the
dictionary which can be shared between frames.)

Let's see...  Say we have this function:

def f(x):
    try:
        return 1 + (-x)
    finally:
        print "boo"

The bytecode (simplified) looks like:

    SETUP_FINALLY	(L1)
    LOAD_CONST		(1)
    LOAD_FAST		(x)
    UNARY_NEGATIVE
    BINARY_ADD
    RETURN_VALUE

L1: LOAD_CONST		("boo")
    PRINT_ITEM
    PRINT_NEWLINE
    END_FINALLY

Now suppose that the unary minus operator saves its continuation
(e.g. because x was a type with a __neg__ method).  At this point
there is an entry on the block stack pointing to L1 as the try-finally
block, and the value stack has the value 1 pushed on it.

Clearly if that saved continuation is ever invoked (called?  used?
activated?  What do you call what you do to a continuation?) it should 
substitute whatever value was passed into the continuation for the
result of the unary minus, and the program should continue by pushing
it on top of the value stack, adding it to 1, and returning the
result, executing the block of code at L1 on the way out.  So clearly
when the continuation is used, 1 should be on the value stack and L1
should be on trh block stack.

Assuming that the unary minus function initially returns just fine,
the value stack and the block stack of the frame will be popped.  So I 
conclude that saving a continuation must save at least the value and
block stack of the frame being saved.

Is it safe not to save the frame and block stacks of frames further
down on the call stack?  I don't think so -- these are all destroyed
when frames are popped off the call stack (even if the frame is kept
alive, its value and block stack are always empty when the function
has returned).

So I hope that Christian has code that saves the frame and block
stacks!  (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.)

How does Scheme do this?  I don't know if it has something like the
block stack, but surely it has a value stack!

Still mystified,

--Guido van Rossum (home page: http://www.python.org/~guido/)