[Python-Dev] Re: Graph exploration with generators

[David Eppstein]

On 8/20/03 10:53 AM -0400 Kevin Jacobs <jacobs at penguin.theopalgroup.com> 
wrote:
> 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.

If you are implying (when you say "all N-1 of those yields can be elided" 
that recursive chains of "yield *" can be handled in such a way that each 
generated item is passed through the whole chain in constant time, then you 
are mistaken.

I can prove a nonconstant lower bound via a simulation of union-find, and 
the best amortized upper bound I know is logarithmic.  Ewing's technique, 
that I referred to in a previous message, should do better in practice but 
not in the worst case.

The problem is that, if a generator X calls "yield *" on a generator Y, we 
can not safely assume that all of Y's output goes to X.  X can be suspended 
and in the meantime someone else can request values from Y.
-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science