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

[Tim Peters]

[Gordon]
> I beg enlightenment from someone more familiar with these
> high-falutin' concepts. Would the following characterization be
> accurate?
>
> All these beasts (continuations, coroutines, generators) involve the
> idea of "resumable", but:
>
>  A generator's state is wholly self-contained
>  A coroutines's state is not necessarily self-contained but it is
> stable
>  Continuations may have volatile state.
>
> Is this right, wrong, necessary, sufficient...??
>
> goto-beginning-to-look-attractive-ly y'rs

"goto" is deliciously ironic, for a reason to become clear <wink>.

Here's my biased short course.

NOW

First, I have the feeling most people would panic if we simply described
Python's current subroutine mechanism under a new name <0.9 wink>.  I'll
risk that.  When Python makes a call, it allocates a frame object.  Attached
to the frame is the info everyone takes for granted so thinks is "simple &
obvious" <wink>.  Chiefly,

    "the locals" (name -> object bindings)
    a little evaluation stack for holding temps and dynamic
        block-nesting info
    the offset to the current bytecode instruction, relative to the
        start of the code object's fixed (immutable) bytecode vector

When a subroutine returns, it decrefs the frame and then the frame typically
goes away; if it returns because of an exception, though, traceback objects
may keep the frame alive.

GENERATORS

Generators add two new abstract operations, "suspend" and "resume".  When a
generator suspends, it's exactly like a return today except we simply
decline to decref the frame.  That's it!  The locals, and where we are in
the computation, aren't thrown away.  A "resume" then consists of
*re*starting the frame at its next bytecode instruction, with the retained
frame's locals and eval stack just as they were.

Some generator properties:

+ In implementation terms a trivial variation on what Python currently does.

+ They're asymmetric:  "suspend" is something only a generator can do, and
"resume" something only its caller can do (this does not preclude a
generator from being "the caller" wrt to some other generator, though, and
indeed that's very useful in practice).

+ A generator always returns control directly to its caller, at the point
the caller invoked the generator.  And upon resumption, a generator always
picks up where it left off.

+ Because a generator remembers where it is and what its locals are, its
state and "what to do next" don't have to be encoded in global data
structures then decoded from scratch upon entry.  That is, whenever you
build a little (or large!) state machine to figure out "what to do next"
from a collection of persistent flags and state vrbls, chances are good
there's a simple algorithm dying to break free of that clutter <wink>.

COROUTINES

Coroutines add only one new abstract operation, "transfer".  They're fully
symmetric so can get away with only one.  "transfer" names a coroutine to
transfer to, and gives a value to deliver to it (there are variations, but
this one is common & most useful).  When A transfers to B, it acts like a
generator "suspend" wrt A and like a generator "resume" wrt B.  So A
remembers where it is, and what its locals etc are, and B gets restarted
from the point *it* last transfered to someone else.

Coroutines grew up in simulation languages because they're an achingly
natural way to model independent objects that interact with feedback.  There
each object (which may itself be a complex system of other stuff) is written
as an infinite loop, transferring control to other objects when it has
something to tell them, and transferred to by other objects when they have
something to tell it.

A Unix pipeline "A | B | C | D" doesn't exploit the full power but is
suggestive.  A may be written as

while 1:
    x = compute my next output
    B.transfer(x)     # resume B with my output

B as

while 1:
    x = A.transfer()  # resume A to get my input
    y = compute something from x and my own history
    C.transfer(y)     # resume C with my output

C as

while 1:
    x = B.transfer()  # resume B to get my input
    y = compute something from x and my own history
    D.transfer(y)     # resume D with my output

and D as

while 1:
    x = C.transfer()  # resume C to get my input
    y = compute something from x and my own history
    print y

If e.g. C collapses pairs of values from B, it can be written instead as

while 1:
    # get a pair of B's
    x = B.transfer()
    y = B.transfer()
    z = f(x, y, whatever)
    D.transfer(z)     # resume D with my output

It's a local modification to C:  B doesn't know and shouldn't need to know.
This keeps complex algorithms manageable as things evolve.

Initialization and shutdown can be delicate, but once the pipe is set up it
doesn't even matter which of {A, B, C, D} first gets control!  You can view
A as pushing results through the pipe, or D as pulling them, or whatever.
In reality they're all equal partners.

Why these are so much harder to implement than generators:  "transfer"
*names* who next gets control, while generators always return to their
(unnamed) caller.  So a generator simply "pops the stack" when it suspends,
while coroutine flow need not  be (and typically isn't) stack-like.

In Python this is currently a coroutine-killer, because the C stack gets
intertwined.  So if coroutine A merely calls (in the regular sense) function
F, and F tries to transfer to coroutine B, the info needed to resume A
includes the chunk of the C stack between A and F.  And that's why the
Python coroutine implementation I referenced earlier uses threads under the
covers (where capturing pieces of the C stack isn't a problem).

Early versions of coroutines didn't allow for this, though!  At first
coroutines could only transfer *directly* to other coroutines, and as soon
as a coroutine made "a regular call" transfers were prohibited until the
call returned (unless the called function kicked off a brand new collection
of coroutines, which could then transfer among themselves -- making the
distinction leads to convoluted rules, so modern practice is to generalize
from the start).

Then the current state of each coroutine was contained in a single frame,
and it's really no harder to implement than generators.  Knuth seems to have
this restricted flavor of coroutine in mind when he describes generator
behavior as "semi-coroutine".

CONTINUATIONS

Given the pedagogical structure so far, you're primed to view continuations
as an enhancement of coroutines.  And that's exactly what will get you
nowhere <wink>.  Continuations aren't more elaborate than coroutines,
they're simpler.  Indeed, they're simpler than generators, and even simpler
than "a regular call"!  That's what makes them so confusing at first:
they're a different *basis* for *all* call-like behavior.  Generators and
coroutines are variations on what you already know; continuations challenge
your fundamental view of the universe.

Legend has it they were discovered when theorists were trying to find a
solid reason for why goto statements suck:  the growth of "denotational
semantics" (DS) boomed at the same time "structured programming" took off.
The former is a solid & fruitful approach to formally specifying the
semantics of programming languages, built on the lambda calculus (and so
dear to the Lisp/Scheme community -- this all ties together, of course
<wink>).

The early hope was that goto statements would prove to present intractable
problems for formal specification, and then "that's why they suck:  we can't
even sort them out on paper, let alone in practice".

But in one of God's cleverer tricks on the programming world <tee hee>, the
semantics of goto turned out to be trivial:  at a branch point, you can go
one of two ways.  Represent one of those ways by a function f that computes
what happens if you branch one way, and the other way by a function g.  Then
an if+goto simply picks one of f or g as "the continuation" of the program,
depending on whether the "if" condition is true or false.  And a plain goto
simply replaces the current continuation with a different one (representing
what happens at the branch target) unconditionally.  So goto turned out to
be simpler (from the DS view) than even an assignment stmt!

I've often suspected theorists were *surprised* (and maybe appalled <0.7
wink>) when the language folks went on to *implement* the continuation idea.
Don't really know, but suppose it doesn't matter anyway.  The fact is we're
stuck with them now <wink>.

In theory a continuation is a function that computes "the rest of the
program", or "its future".  And it really is like a supercharged goto!  It's
the formal DS basis for all control flow, from goto stmts to exception
handling, subsuming vanilla call flow, recursion, generators, coroutines,
backtracking, and even loops along the way.

To a certain frame of mind (like Sam's, and Christian is temporarily under
his evil influence <wink>), this relentless uniformity & consistency of
approach is very appealing.  Guido tends to like his implementations to
mirror his surface semantics, though, and if he has ten constructs they're
likely to be implemented ten ways.  View that as a preview of future battles
that have barely been hinted at so far <0.3 wink>.

Anyway, in implementation terms a continuation "is like" what a coroutine
would be if you could capture its resumption state at any point (even
without the coroutine's knowledge!) and assign that state to a vrbl.  So we
could say it adds an abstract operation "capture", which essentially
captures the program counter, call stack, and local (in Python terms) "block
stack" at its point of invocation, and packages all that into a first-class
"continuation object".  IOW, a building block on top of which a generator's
suspend, and the suspend half of a coroutine transfer, can be built.  In a
pure vision, there's no difference at all between a regular return and the
"resume" half of a coroutine transfer:  both amount to no more than picking
some continuation to evaluate next.

A continuation can be captured anywhere (even in the middle of an
expression), and any continuation can be invoked at will from anywhere else.
Note that "invoking a continuation" is *not* like "a call", though:  it's
abandoning the current continuation, *replacing* it with another one.  In
formal DS this isn't formally true (it's still "a call" -- a function
application), but in practice it's a call that never returns to its caller
so the implementation takes a shortcut.

Like a goto, this is as low-level as it gets, and even hard-core
continuation fans don't use them directly except as a means to implement
better-behaved abstractions.

As to whether continuations have "volatile state", I'm not sure what that
was asking.  If a given continuation is invoked more than once (which is
something that's deliberately done when e.g. implementing backtracking
searches), then changes made to the locals by the first invocation are
visible to the second (& so on), so maybe <wink> the answer is "yes".  It's
more accurate to think of a continuation as being immutable, though:  it
holds a reference to the structure that implements name bindings, but does
not copy (save or restore) the bindings.

Quick example, given:

(define continuation 0)

(define (test)
  (let ((i 0))
    (call/cc (lambda (k)
               (set! continuation k)))
    (set! i (+ i 1))
    i))

That's like the Python:

def test():
    i = 0
    global continuation
    continuation = magic to resume at the start of the next line
    i = i + 1
    return i

Then (this is interactive output from a Scheme shell):

> (test) ; Python "test()"
1
> (continuation) ; Python "continuation()"
2
> (continuation)
3
> (define thisguy continuation) ; Python "thisguy = continuation"
> (test)
1
> (continuation)
2
> (thisguy)
4
>

too-simple-to-be-obvious?-ly y'rs  - tim