Iterators & generators (RE: Real Problems with Python)

[Tim Peters]

[Tim]
>    def traverse_post(self):
>        for child in self.left, self.right:
>            if child is not None:
>                suspend child.traverse_post()
>        suspend self.data

[Andrew Cooke]
> That finally hammered home to me just what continuations are all
> about.

What's illustrated above is "a generator", which is a semi-coroutine, or,
literally, just half of a coroutine.  continuations are one possible means
of implementing that, but are far more general.

> Does anyone have something similarly elegant that shows a coroutine?

cmdline pipes (like "cat somefile | sort | uniq -c | sort -nr") are usually
implemented via separate processes communicating via files, but are easy to
write in a language with coroutines within a single process (and within a
single thread!).

This really isn't a bad <wink> analogy:  no command in the pipe is either
master or slave -- they're all equal partners.  Each has its own state,
including its own "program counter", call stack, and local variables.  They
don't "call" each other, they *communicate info* to each other.  Under a
normal call, the callee *loses* its state as soon as it returns.  Under a
coroutine transfer, it's completely symmetric:  the transferor asks the
transferee to run for a while (either passing info to it, or desiring info
from it), and the transferee doesn't *return*, but merely transfers control
to some other coroutine.  Nobody loses state.  And each transfer to a
coroutine C resumes C in exactly the state it was in at the time C
transfered to some other coroutine.  There's only one "thread" of control,
but control is not constrained to "stack like" resumptions:  any coroutine
can transfer to any other at any time (btw, the pipeline example doesn't
illustrate that particular point).

Knuth properly complains that it's very hard to give a simple example of
general coroutines.  He ends up writing a pretty hairy elevator simulation
to illustrate it.  In fact, coroutines most often pop up in languages
designed for writing event simulations (like Simula-67, which is a wonderful
early one that also anticipated much of modern OO machinery!).

> ...
> Also, comp.lang.lisp is currently dissing continuations.

That's because some Lisp people are fighting with some Scheme people.  It's
their version of using whitespace for indentation <wink>.

> Would that be because the alternative is to pass the code that
> will process the node into the iterator as a (first class) function?
> Obviously, in this case, yes, but is that true in general (are
> there examples where continuations or coroutines make something
> possible that really is tricky to do in other ways)?

This gets really involved really fast, and without a precise model of
computation to build on, discussing relative power is a trap.  *Generally*
speaking, coroutines can be implemented via continuations, but not vice
versa (continuations are more powerful); but continuations and threads can
each be implemented via the other (but have vastly different pragmatics,
which is why Christian worked so hard on Stackless); so if threads are more
familiar, rephrase your question to ask whether having threads can make some
things much easier to do.  "Of course", and the same for continuations.  Raw
threads and raw continuations are exceedingly difficult to use correctly,
though, so Python offers the higher-level threading.py to make thread life
easier, and continuations in Scheme are usually used "under the covers" to
implement an easier-to-use abstraction (like coroutines, or backtracking
search, or ...).

that's-the-ten-cent-answer-and-worth-almost-half-ly y'rs  - tim