[Python-Dev] Fancy control flow

Tim Peters tim_one@email.msn.com
Tue, 6 Jul 1999 21:52:15 -0400

Responding to a msg of Guido's that shows up in the archives but didn't come
across the mail link (the proper authorities have been notified, and I'm
sure appropriate heads will roll at the appropriate pace <wink> ...).

> From guido@CNRI.Reston.VA.US Mon, 05 Jul 1999 08:06:03 -0400
> Date: Mon, 05 Jul 1999 08:06:03 -0400
> From: Guido van Rossum guido@CNRI.Reston.VA.US
> Subject: Fake threads (was [Python-Dev] ActiveState & fork & Perl)

[generators, coroutines, continuations]

> I still don't understand all of this (I have not much of an idea of
> what Christian's search for hidden registers is about and what kind of
> analysis he needs) but I think of continuations as requiring
> (theoretically) coping the current stack (to and from), while
> generators and coroutines just need their own piece of stack set aside.

A generator needs one frame, period (its own!).  "Modern" coroutines can get
more involved, mixing regular calls with coroutine transfers in arbitrary

About Christian's mysterious quest, we've been pursuing it offline.  By
"hidden registers" I think he means stuff on the eval stack that should
*not* be saved/restored as part of a continuation's state.  It's not clear
to me that this isn't the empty set.  The most debatable case I've seen is
the Python "for" loop, which hides an anonymous loop counter on the stack.

for i in seq:
    if func1(i):

This is more elaborate than necessary <wink>, but since it's the one we've
discussed offline I'll just stick with it.

Suppose func1 saves a continuation on the first iteration, and func2 invokes
that continuation on the fifth.  Does the resumed continuation "see" the
loop as being on its first iteration or as being on its fifth?

In favor of the latter is that the loop above "should be" equivalent to

hidden = 0
while 1:
        temp = seq[hidden]
    except IndexError:
    hidden = hidden + 1
    i = temp
    if func1(i):

since that's what "for" *does* in Python.  With the latter spelling, it's
clear that the continuation should see the loop as being on its fifth
iteration (continuations see changes in bindings, and making the loop
counter a named local exposes it to that rule).  But if the entire eval
stack is (conceptually) saved/restored, the loop counter is part of it, so
the continuation will see the loop counter at its old value.

I think it's arguable either way, and argued in favor of "fifth" initially.
Now I'm uncertain, but leaning toward "first".

> The difference between any of these and threads (fake or real) is that
> they pass control explicitly, while threads (typically) presume
> pre-emptive scheduling, i.e. they make independent parallel progress
> without explicit synchronization.


> (Hmm, how do you do this with fake threads?  Or are these only required
> to switch whenever you touch a mutex?)

I'd say they're only *required* to switch when one tries to acquire a mutex
that's already locked.  It would be nicer to switch them as ceval already
switches "real threads", that is give another one a shot every N bytecodes.

> I'm not sure if there's much of a difference between generators and
> coroutines -- it seems just the termination convention.

A generator is a semi-coroutine, but is the easier half <wink>.

> (Hmm... would/should a generator be able to raise an exception in its
> caller?

Definitely.  This is all perfectly clear for a generator -- it has a unique
& guaranteed still-active place to return *to*.  Years ago I tried to rename
them "resumable functions" to get across what a trivial variation of plain
functions they really are ...

> A coroutine?)

This one is muddier.  A (at line A1) transfers to B (at line B1), which
transfers at line B2 to A (at line A2), which at line A3 transfers to B (at
line B3), and B raises an exception at line B4.  The obvious thing to do is
to pass it on to line A3+1, but what if that doesn't catch it either?  We
got to A3 from A2 from B2 from B1, but B1 is long gone.

That's a real difference with generators:  resuming a generator is
stack-like, while a co-transfer is just moving control around a flat graph,
like pushing a pawn around a chessboard.

The coroutine implementation I posted 5 years ago almost punted on this one:
if any coroutine suffered an unhandled exception, all coroutines were killed
and an EarlyExit exception was raised in "the main coroutine" (the name
given to the thread of your code that created the coroutine objects to begin

Deserves more thought than that, though.

or-maybe-it-doesn't<wink>-ly y'rs  - tim