[Python-Dev] Generator details

Tim Peters tim_one@email.msn.com
Thu, 8 Jul 1999 02:45:51 -0400

I'm out of time for tonight so will just address the first one:

[Guido van Rossum]
> I have a few questions/suggestions about generators.
> Tim writes that a suspended generator has exactly one stack frame.
> I'm not sure I like that.  The Demo/thread/Generator.py version has no
> such restriction; anything that has a reference to the generator can
> put() the next value.  Is the restriction really necessary?

It can simplify the implementation, and (not coincidentally <wink>) the
user's mental model of how they work.

> I can see a good use for a recursive generator, e.g. one that generates
> a tree traversal:

Definitely; in fact, recursive generators are particularly useful in both
traversals and enumeration of combinatorial objects (permutations, subsets,
and so on).

>     def inorder(node):
>         if node.left: inorder(node.left)
>         suspend node
>         if node.right: inorder(node.right)
> If I understand Tim, this could not work because there's more than one
> stack frame involved.

That's right.  It would be written like this instead:

def inorder(node):
    if node.left:
        suspend inorder(node.left)
    suspend node
    if node.right:
        suspend inorder(node.right)

Now there may be many instances of the "inorder" generator active (as many
as the tree is deep), but each one returns directly to its caller, and all
but the bottom-most one is "the caller" wrt the generator it invokes.  This
implies that "suspend expr" treats expr like a generator in much the same
way that "for x in expr" does (or may ...).  I realize there's some
muddiness in that.

> On the other hand, he seems to suggest that something like this *is*
> allowed when using "modern" coroutines.

Yes, and then your original version can be made to work, delivering its
results directly to the ultimate consumer instead of (in effect) crawling up
the stack each time there's a result.

> Am I missing something?

Only that I've been pushing generators for almost a decade, and have always
pushed the simplest possible version that's sufficient for my needs.
However, every time I've made a micron's progress in selling this notion,
it's been hijacked by someone else pushing continuations.  So I keep pushing
the simplest possible version of generators ("resumable function"), in the
hopes that someday somebody will remember they don't need to turn Python
inside out to get just that much <wink>.

[much worth discussion skipped for now]
> ...
> (I'm still baffled by continuations.

Actually not, I think!

> The question whether the for saved and restored loop should find itself
> in the 1st or 5th iteration surprises me.  Doesn't this cleanly map into
> some Scheme code that tells us what to do?  Or is it unclear because
> Scheme does all loops through recursion?

Bingo:  Scheme has no loops.  I can model Python's "for" in Scheme in such a
way that the continuation sees the 1st iteration, or the 5th, but neither
way is obviously right -- or wrong (they both reproduce Python's behavior in
the *absence* of continuations!).

> I presume that if you save the continuation of the 1st iteration and
> restore it in the 5th, you'd find yourself in the back 1st iteration?
> But this is another thread.)

The short course here is just that any way I've tried to model Python's
"for" in *Python* shares the property of the "while 1:" way I posted:  the
continuation sees the 5th iteration.  And some hours I think it probably
should <wink>, since the bindings of all the locals it sees will be
consistent with the 5th iteration's values but not the 1st's.

could-live-with-it-either-way-but-"correct"-is-debatable-ly y'rs  - tim