Iterators & generators (RE: Real Problems with Python)

[Tim Peters]

[Neel identifies Python's iteration protocol as a weakness;
 Tim recounts a bit of the history of trying to get Icon
 generators / Sather iterators into Python]

[Neel Krishnaswami]
> I have only a nodding acquaintance with Icon or Sather, but I've
> programmed in CLU, and really enjoyed it.

Bingo.  Sather's iterators were inspired by CLU's, but removed some
restrictions (e.g., IIRC CLU catered to only one iterator per loop, while
Sather can iterate over multiple objects-- each with its own iterator --in a
single loop).  Icon's generators came from a different view of the world,
seen there as exposing a key mechanism in pattern matching engines.

However people come at this, though, some flavor of semi-coroutine keeps
getting reinvented:  it's utterly natural for many kinds of
producer/consumer problems (of which iteration is one), and a sanity
lifesaver when the producer has data *and* control-flow state to keep track
of.  All doable with threads or continuations, but they're gross overkill
for the little that's actually required.

> I suspect that in large part this was because of the cleanness
> with which iteration could be expressed in it. Iteration is an
> awful big chunk of what programs *do*, and being able to say it
> cleanly made writing them easier.

Yup!  Here's a made-up example in pseudo-Python, for iterating over a binary
tree in postorder.  This borrows the Icon "suspend" construct, which acts
like a "resumable return" (in implementation terms, the stack frame isn't
thrown away, and "the next call" merely resumes it exactly where it left
off):

class BinTree:
   # with members .left and .right of type BinTree (& None means none),
   # and .data of an arbitrary type
   ...
   def traverse_post(self):
       for child in self.left, self.right:
           if child is not None:
               suspend child.traverse_post()
       suspend self.data

b = BinTree()
...
for leaf in b.traverse_post():
    process(leaf)

It's hard to imagine more straightforward code for this task, although easy
to imagine terser code (e.g., that whole thihg is an idiomatic one-liner in
Icon, but "everything's a generator" in Icon and so has gobs of initially
cryptic shortcuts & special syntactic support).

Much more on this flavor of semi-coroutine can be dug out of c.l.py
archives.  I've often called it "resumable functions" on c.l.py, in a mostly
futile attempt to get across how conceptually simple it is (it's impossible
to mention this without someone chiming in with "but you can do that with
continuations!", and after the first Scheme example of *that*, the whole
newsgroup flees in terror <0.5 wink>).

ever-notice-that-sicp-doesn't-mention-call/cc-even-once?-ly
    y'rs  - tim