PEP 255: Simple Generators

[Tim Peters]

[Denys Duchier]
> Think for example of a tree traversal algorithm that is parametrized
> by a procedure to be applied to each node.  My reading of the PEP does
> not allow a procedure to be passed in that `yields' the node.

The PEP gives two examples (one recursive, one not, but the distinction is
internal implementation detail) of inorder node generators for a specific
kind of binary tree.

    def generic_processor(traversable_thing, function_to_apply):
        for node in traversable_thing:
            function_to_apply(node)

works fine, and isn't limited to trees -- traversable_thing can be any
iterable object.  Call via, e.g. (using the PEP example's names)

    generic_processor(t, some_leaf_function)

where t is an instance of the PEP's Tree class.

If you mean instead that you want to be able to pass a procedure to the tree
traverser itself, fine, but then there's no real attraction to generators at
all.

> While possibly aberrant, let me suggest a higher-order programming
> approach that would not even require a new keyword but merely a new
> primitive which I'll call `generator'.  This primitive takes a unary
> procedure as argument and returns an iterator.  The unary procedure
> takes itself a `yield' procedure as argument.

You do know that most calculus students drop out at "for every epsilon > 0
there exists a delta such that for every x where ..." <wink>.

> Here is the fib example of the PEP written with my proposal:
>
> 	def fib(yield):
> 	  a, b = 0, 1
> 	  while 1:
> 	    yield(b)
> 	    a, b = b, a+b
>
> 	g=generator(fib)

I'm guessing at what all these pieces mean, but the final clue is missing:
what do I do with g?  Like, for example,

    for value in g:
        print value

?  If so, how is Jython supposed to implement this?  As the PEP says,
"yield" is a keyword in large part because the Jython implementors can't
alter the JVM, and they believe they need to know all potential suspension
points at compile-time (implementing this stuff on top of Java threads
instead is not a practical option).

I would also miss the ability to pass arguments to generators in a natural
way (I know I can fake it by mucking with lexical closures to make the
function actually passed "look like" a one-argument function, but that's a
strain in Python too).

> It's straightforward (in an implementation) to check that the yield
> procedure which is invoked actually corresponds to the generator that
> is currently executing.  If that's not the case, an exception should
> be raised.
>
> This proposal has the advantage that the boundary of the generator is
> fixed late, namely at the time the `generator' primitive is invoked.
> It also support full compositionality.

I'm not sure what you mean by that, but if it implies that you want, e.g.,
to be able to, within fib, pass yield on to a *called* function bif(yield),
and also yield values from within bif, then we need the Stackless Python
machinery to support that.  PEP 255 is strictly a "one-frame gimmick":  a
255 generator need only remember the state of a single frame, and can only
yield to the generator's immediate invoker.  Since the PVM is currently
written in C using recursion, anything more general than that creates severe
implementation difficulties.

> ...
> which I would write as follows:
>
> def zipgen(g,h):
>   def result(yield):
>     g(yield)
>     h(yield)
>   return result

We can't support that, for reasons sketched in the preceding paragraph:
when the guts of g decide to yield, we have a (recursive) C stack frame,
inside the PVM, "stuck in the middle" between the invocation of "result" and
the invocation of g.  In order for "result"'s invoker to regain control, the
C stack has to be popped.  Icon (or at least one implementation I used for
several years) manages to do this via platform-specific assembler to do
cactus-stack-like context switches fooling the platform C implementation,
and Stackless Python does it via eliminating C recursion from the PVM's eval
loop (it supports full-blown continuations).

The "Simple" in "Simple Generators" sidesteps all of that by supporting only
generator->immediate_caller yields; but, as the recursive "inorder" PEP
example shows, that's less a limitation than it may first appear (and Icon
has the same limitation; the "cactus-stack-like" stuff is required only for
Icon co-expressions, which are consequently not supported on all platforms).