[Python-Dev] Re: Graph exploration with generators

[Kevin Jacobs]

On Mon, 18 Aug 2003, David Eppstein wrote:
> In article <3F419D09.5070709 at ieee.org>,
>  "Shane Holloway (IEEE)" <shane.holloway at ieee.org> wrote:
> 
> >    I assume this loss is due to restoring each context in the chain.  (I 
> >    would need help verifying this assumption.)
> > What I would like to propose is a "yield *" type statement, where "yield 
> > *collection" would have the equivalent 
> > functionality of "for item in collection: yield item".  The above example 
> > would then appear as follows:
> 
> It's been proposed before, with somewhat different syntax ("yield every" 
> instead of "yield *"): http://tinyurl.com/kfvc
> 
> The syntax alone doesn't help speed things up, but iirc Greg Ewing had 
> some good ideas for doing this efficiently.  I think the concensus was, 
> though, that generators are so new that we haven't had enough experience 
> to know what the best ways of using them are, so it would be premature 
> to settle on chaining them this way.

99% of the "problem" can be taken care of by adding a relatively simple
optimization to the interpreter.  It involves adding the necessary
book-keeping to propogate values yielded by a generator directly to the next
expression it is needed in, and conversely to return to the generator
directly when the next value is requested.  Say we have a depth-N tree, then
for each leaf node, the interpreter must pass a value up to N-1 levels of
generators.  If the values yielded are direct generator calls, then all N-1
of those yields can be elided.  This allows "yield *" to be written
efficiently as a simple C-function, that is equivalent to this Python
generator:

  def yield_star(iterable):
    for i in iterable:
      yield i

Interestingly enough, this same optimization can also be applied to return
expressions/values, and is related to tail-call optimizations done by
traditional compilers and functional-language interpreters.  It is also very
much related to continuation-passing-style (CPS) transformations, which for
Python generators, have very tractable semantics.

Regards,
-Kevin

-- 
--
Kevin Jacobs
The OPAL Group - Enterprise Systems Architect
Voice: (440) 871-6725 x 19         E-mail: jacobs at theopalgroup.com
Fax:   (440) 871-6722              WWW:    http://www.theopalgroup.com/