yield_all needed in Python

[Douglas Alan]

While writing a generator, I was just thinking how Python needs a
"yield_all" statement. With the help of Google, I found a
pre-existing discussion on this from a while back in the Lightweight
Languages mailing list. I'll repost it here in order to improve the
chances of this enhancement actually happening someday. The original
poster from the LL mailing list seems mostly concerned with
algorithmic efficiency, while I'm concerned more about making my
programs shorter and easier to read. The ensuing discussion on the LL
list talks about how yield_all would be somewhat difficult to
implement if you want to get the efficiency gain desired, but I don't
think it would be very difficult to implement if that goal weren't
required, and the goal were limited to just the expressive elegance:

A Problem with Python's 'yield'

* To: LL1 Mailing List <address@hidden >
* Subject: A Problem with Python's 'yield'
* From: Eric Kidd <address@hidden >
* Date: 27 May 2003 11:15:20 -0400
* Organization:
* Sender: address@hidden

I'm going to pick on Python here, but only because the example code will
be short and sweet. :-) I believe several other implementations of
generators have the same problem.

Python's generator system, used naively, turns an O(N) tree traversal
into an O(N log N) tree traversal:

class Tree:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

def in_order(self):
if self.left is not None:
for v in self.left.in_or der():
yield v
yield self.value
if self.right is not None:
for v in self.right.in_o rder():
yield v

t=Tree(2, Tree(1), Tree(3))
for v in yield_bug.t.in_ order():
print v

This prints:
1
2
3

Unfortunately, this snippet calls 'yield' 5 times, because the leaf
values must be yielded twice on their way back up the tree.

We can shorten the code--and make it run in O(N) time--by adding a new
keyword to replace the "for v in ...: yield v" pattern:

def in_order(self):
if self.left is not None:
yield_all self.left.in_or der():
yield self.value
if self.right is not None:
yield_all self.right.in_o rder():

Interestingly enough, this allows you define notions such as
"tail-recursive generation", and apply the usual bag of
recursion-optimization techniques.

Cheers,
Eric

|>oug

[Andrew Dalke]

Re: yield_all needed in Python

On Mon, 28 Feb 2005 18:25:51 -0500, Douglas Alan wrote:[color=blue]
> While writing a generator, I was just thinking how Python needs a
> "yield_all" statement. With the help of Google, I found a pre-existing
> discussion on this from a while back in the Lightweight Languages
> mailing list. I'll repost it here in order to improve the chances of
> this enhancement actually happening someday.[/color]

You should also have looked for the responses to that. Tim Peter's
response is available from

http://aspn.activestate.com/ASPN/Mail/Message/624273

as linked from

http://aspn.activestate.com/ASPN/Mail/Message/python-dev/758572

Here is the most relevant parts.

I'm not bothered -- this comes with the territory. If/when
full-fledged coroutines make it in too, people worried about that can
use them instead. Curious fact: I *was* worried about the worst-case
time aspects of "simple generators" in Icon years ago, but in practice
never ever got burned by it. And rewriting stuff to use Icon
co-expressions instead invariably resulted in messier code that ran
significantly slower in virtually all cases, except for the ones I
*contrived* to prove the O() difference.

BTW, Python almost never worries about worst-case behavior, and people
using Python dicts instead of, e.g., balanced trees, get to carry their
shame home with them hours earlier each day <wink> .

Andrew
dalke@dalkescie ntific.com

[Terry Reedy]

Re: yield_all needed in Python


"Douglas Alan" <nessus@mit.edu > wrote in message
news:lck6osnu68 .fsf@gaffa.mit. edu...[color=blue]
> We can shorten the code--and make it run in O(N) time--by adding a
> new
> keyword to replace the "for v in ...: yield v" pattern:[/color]

Maybe. Until you define the semantics of yield_all and at least outline an
implementation, I am not convinced of 'run in o(n) time'. There was once a
several-post discussion of a related idea of having yield somehow,
magically, skip intermediate generators that only yielded value on up,
without tranformation. But it was never clear how to do this practically
without negatively impacting all generators. Cetainly, if <yield_all
iterator> == <for i in iterator: yield i>, I don't see how anything is
gained except for a few keystrokes. If <yield_all iterator> == <yield
list(i for i in iterator)> then the replacement is a semantic change.
[color=blue]
> def in_order(self):
> if self.left is not None:
> yield_all self.left.in_or der():
> yield self.value
> if self.right is not None:
> yield_all self.right.in_o rder():[/color]

If and when I write a text-based double-recursion to iteration transformer,
a pseudokeyword might be be an idea for indicating that stacked yields are
identify functions and therefore bypassable.

Terry J. Reedy

[Steve Holden]

Re: yield_all needed in Python

Terry Reedy wrote:[color=blue]
> "Douglas Alan" <nessus@mit.edu > wrote in message
> news:lck6osnu68 .fsf@gaffa.mit. edu...
>[color=green]
>> We can shorten the code--and make it run in O(N) time--by adding a
>>new
>> keyword to replace the "for v in ...: yield v" pattern:[/color]
>
>
> Maybe. Until you define the semantics of yield_all and at least outline an
> implementation, I am not convinced of 'run in o(n) time'. There was once a
> several-post discussion of a related idea of having yield somehow,
> magically, skip intermediate generators that only yielded value on up,
> without tranformation. But it was never clear how to do this practically
> without negatively impacting all generators. Cetainly, if <yield_all
> iterator> == <for i in iterator: yield i>, I don't see how anything is
> gained except for a few keystrokes. If <yield_all iterator> == <yield
> list(i for i in iterator)> then the replacement is a semantic change.
>[/color]
La plus ca change, la plus c'est la meme chose (I trust native French
speakers will excuse the laziness that led to the absence of accent).

This is very reminiscent of discussions several years ago about tail
recursion and how it would be a great thing to optimise the edge cases.
Of course we didn't have generators then, so we couldn't complain about
*their* inefficiencies then.[color=blue]
>[color=green]
>> def in_order(self):
>> if self.left is not None:
>> yield_all self.left.in_or der():
>> yield self.value
>> if self.right is not None:
>> yield_all self.right.in_o rder():[/color]
>
>
> If and when I write a text-based double-recursion to iteration transformer,
> a pseudokeyword might be be an idea for indicating that stacked yields are
> identify functions and therefore bypassable.
>[/color]
The key words in the above being "use" and "case", I suspect.

python:-always-something-new-to-bitch-about-ly y'rs - steve

[Antoon Pardon]

Re: yield_all needed in Python

Op 2005-03-01, Steve Holden schreef <steve@holdenwe b.com>:[color=blue]
> Terry Reedy wrote:[color=green]
>> "Douglas Alan" <nessus@mit.edu > wrote in message
>> news:lck6osnu68 .fsf@gaffa.mit. edu...
>>[color=darkred]
>>> We can shorten the code--and make it run in O(N) time--by adding a
>>>new
>>> keyword to replace the "for v in ...: yield v" pattern:[/color]
>>
>>
>> Maybe. Until you define the semantics of yield_all and at least outline an
>> implementation, I am not convinced of 'run in o(n) time'. There was once a
>> several-post discussion of a related idea of having yield somehow,
>> magically, skip intermediate generators that only yielded value on up,
>> without tranformation. But it was never clear how to do this practically
>> without negatively impacting all generators. Cetainly, if <yield_all
>> iterator> == <for i in iterator: yield i>, I don't see how anything is
>> gained except for a few keystrokes. If <yield_all iterator> == <yield
>> list(i for i in iterator)> then the replacement is a semantic change.
>>[/color]
> La plus ca change, la plus c'est la meme chose (I trust native French
> speakers will excuse the laziness that led to the absence of accent).[/color]


Small diversion:

You weren't lazy enough because you added words. The idiom AFAIK is:

Plus ça change, plus ça reste la même chose.

You shouldn't add the "la", I think that came from translating
too literally, adding an article to a comparative in french
turns it into a superlative. So instead of writing:

The more it changes, the more is stays the same

You wrote something like:

Most it changes, most it is the same thing.

--
Antoon Pardon

[Douglas Alan]

Re: yield_all needed in Python

Andrew Dalke <dalke@dalkesci entific.com> writes:
[color=blue]
> On Mon, 28 Feb 2005 18:25:51 -0500, Douglas Alan wrote:[/color]
[color=blue][color=green]
>> While writing a generator, I was just thinking how Python needs a
>> "yield_all" statement. With the help of Google, I found a
>> pre-existing discussion on this from a while back in the
>> Lightweight Languages mailing list. I'll repost it here in order
>> to improve the chances of this enhancement actually happening
>> someday.[/color][/color]
[color=blue]
> You should also have looked for the responses to that. Tim Peter's
> response is available from[/color]
[color=blue]
> http://aspn.activestate.com/ASPN/Mail/Message/624273[/color]

[...]
[color=blue]
> Here is the most relevant parts.[/color]

[...]
[color=blue]
> BTW, Python almost never worries about worst-case behavior, and people
> using Python dicts instead of, e.g., balanced trees, get to carry their
> shame home with them hours earlier each day <wink> .[/color]

If you'll reread what I wrote, you'll see that I'm not concerned with
performance, but rather my concern is that I want the syntactic sugar.
I'm tired of writing code that looks like

def foogen(arg1):

def foogen1(arg2):
# Some code here

# Some code here
for e in foogen1(arg3): yield e
# Some code here
for e in foogen1(arg4): yield e
# Some code here
for e in foogen1(arg5): yield e
# Some code here
for e in foogen1(arg6): yield e

when it would be much prettier and easier to read if it looked like:

def foogen(arg1):

def foogen1(arg2):
# Some code here

# Some code here
yield_all foogen1(arg3)
# Some code here
yield_all foogen1(arg4)
# Some code here
yield_all foogen1(arg5)
# Some code here
yield_all foogen1(arg6)

|>oug

[Douglas Alan]

Re: yield_all needed in Python

"Terry Reedy" <tjreedy@udel.e du> writes:
[color=blue]
> Cetainly, if <yield_all
> iterator> == <for i in iterator: yield i>, I don't see how anything
> is gained except for a few keystrokes.[/color]

What's gained is making one's code more readable and maintainable,
which is the one of the primary reasons that I use Python.

|>oug

[Duncan Booth]

Re: yield_all needed in Python

Douglas Alan wrote:
[color=blue]
> "Terry Reedy" <tjreedy@udel.e du> writes:
>[color=green]
>> Cetainly, if <yield_all
>> iterator> == <for i in iterator: yield i>, I don't see how anything
>> is gained except for a few keystrokes.[/color]
>
> What's gained is making one's code more readable and maintainable,
> which is the one of the primary reasons that I use Python.[/color]

On of the reasons why Python is readable is that the core language is
comparatively small. Adding a new reserved word simply to save a few
characters is a difficult choice, and each case has to be judged on its
merits, but it seems to me that in this case the extra syntax is a burden
that would have to be learned by all Python programmers with very little
benefit.

Remember that many generators will want to do slightly more than just yield
from another iterator, and the for loop allows you to put in additional
processing easily whereas 'yield_all' has very limited application e.g.

for tok in tokenstream():
if tok.type != COMMENT:
yield tok

I just scanned a random collection of my Python files: out of 50 yield
statements I found only 3 which could be rewritten using yield_all.

[Douglas Alan]

Re: yield_all needed in Python

Duncan Booth <duncan.booth@i nvalid.invalid> writes:
[color=blue]
> Douglas Alan wrote:[/color]
[color=blue][color=green]
>> "Terry Reedy" <tjreedy@udel.e du> writes:[/color][/color]
[color=blue][color=green][color=darkred]
>>> Cetainly, if <yield_all
>>> iterator> == <for i in iterator: yield i>, I don't see how anything
>>> is gained except for a few keystrokes.[/color][/color][/color]
[color=blue][color=green]
>> What's gained is making one's code more readable and maintainable,
>> which is the one of the primary reasons that I use Python.[/color][/color]
[color=blue]
> On of the reasons why Python is readable is that the core language is
> comparatively small.[/color]

It's not that small anymore. What it *is* is relatively conceptually
simple and readily comprehensible (i.e. "lightweigh t"), unlike
languages like C++ and Perl.
[color=blue]
> Adding a new reserved word simply to save a few
> characters[/color]

It's not to "save a few characters". It's to make it immediately
clear what is happening.
[color=blue]
> is a difficult choice, and each case has to be judged on its merits,
> but it seems to me that in this case the extra syntax is a burden
> that would have to be learned by all Python programmers with very
> little benefit.[/color]

The amount of effort to learn what "yield_all" does compared to the
amount of effort to understand generators in general is so miniscule,
as to be negligible. Besides, by this argument, the standard library
should be kept as small as possible too, since people have to learn
all that stuff in order to understand someone else's code.
[color=blue]
> Remember that many generators will want to do slightly more than just yield
> from another iterator, and the for loop allows you to put in additional
> processing easily whereas 'yield_all' has very limited application e.g.[/color]
[color=blue]
> for tok in tokenstream():
> if tok.type != COMMENT:
> yield tok[/color]
[color=blue]
> I just scanned a random collection of my Python files: out of 50 yield
> statements I found only 3 which could be rewritten using yield_all.[/color]

For me, it's a matter of providing the ability to implement
subroutines elegantly within generators. Without yield_all, it is not
elegent at all to use subroutines to do some of the yielding, since
the calls to the subroutines are complex, verbose statements, rather
than simple ones.

I vote for the ability to have elegant, readable subroutining,
regardless of how much you in particular would use it.

|>oug

[Skip Montanaro]

Re: yield_all needed in Python


Doug> def foogen(arg1):

Doug> def foogen1(arg2):
Doug> # Some code here

Doug> # Some code here
Doug> yield_all foogen1(arg3)
Doug> # Some code here
Doug> yield_all foogen1(arg4)
Doug> # Some code here
Doug> yield_all foogen1(arg5)
Doug> # Some code here
Doug> yield_all foogen1(arg6)

If this idea advances I'd rather see extra syntactic sugar introduced to
complement the current yield statement instead of adding a new keyword.
It's a bit clumsy to come up with something that will work syntactically
since the next token following the yield keyword can be any identifier.
You'd thus need another keyword there. Something like:

def foogen(arg1):

def foogen1(arg2):
# Some code here

# Some code here
yield from foogen1(arg3)
# Some code here
yield from foogen1(arg4)
# Some code here
yield from foogen1(arg5)
# Some code here
yield from foogen1(arg6)

It would be nicer if that was

yield all from <something>

but since "all" is a valid identifier that might break existing code, though
maybe the presence of the following "from" can be used to distinguish
these two cases:

yield <expr>

yield all from <expr>

Skip

[Jeremy Bowers]

Re: yield_all needed in Python

On Tue, 01 Mar 2005 12:42:51 -0600, Skip Montanaro wrote:[color=blue]
> yield <expr>[/color]

yield *<expr>

(Mu-hu-ha-ha-ha!)

[Francis Girard]

Re: yield_all needed in Python

Hi,

You absolutely and definitively have my vote.

When I first learned the generators , I was even wondering if there was
something wrong in what I do when faced with the sub-generators problem you
describe. I was wondering "why am I doing this extra for-loop ? Is there
something wrong ? Can I return the sub-iterator itself and let the final
upper loop do the job ? But no, I absolutely have to 'yield'. What then ?"

Therefore, the suggestion you make, or something similar, would have actually
ease my learning, at least for me.

Regards,

Francis Girard

Le mardi 1 Mars 2005 19:22, Douglas Alan a écrit :[color=blue]
> For me, it's a matter of providing the ability to implement
> subroutines elegantly within generators.  Without yield_all, it is not
> elegent at all to use subroutines to do some of the yielding, since
> the calls to the subroutines are complex, verbose statements, rather
> than simple ones.[/color]

[Mike C. Fletcher]

Re: yield_all needed in Python

Skip Montanaro wrote:
....
[color=blue]
>If this idea advances I'd rather see extra syntactic sugar introduced to
>complement the current yield statement instead of adding a new keyword.
>It's a bit clumsy to come up with something that will work syntactically
>since the next token following the yield keyword can be any identifier.
>You'd thus need another keyword there. Something like:
>
>[/color]
I'd agree on *not* introducing a new keyword. I run into this issue
every once in a while, but new keywords for minor syntactic sugar seems
a bit much.
[color=blue]
> # Some code here
> yield from foogen1(arg3)
>
>[/color]
....
[color=blue]
>It would be nicer if that was
>
> yield all from <something>
>
>[/color]
I don't really like the need to look past that (potentially long)
expression to see the effect of the operation. I don't mind the yield
from syntax, it nicely encapsulates the learning of "generators " so that
when you see yield up front you know something generatish is going on.

I'd be fine with:

for yield on foogen1(arg3)

or

for yield from foogen1(arg3)

which goes more toward the idea of being syntactic sugar for a for loop
that yields each value that is produced. Of course, what happens with:

[ for yield from foogen1(arg3) ]

would then have to be defined... that might make it too complex an
change. Oh well.

Have fun all,
Mike

_______________ _______________ _______________ ___
Mike C. Fletcher
Designer, VR Plumber, Coder

http://www.vrplumber.com

http://blog.vrplumber.com

PyCon is coming...

[Steven Bethard]

Re: yield_all needed in Python

Mike C. Fletcher wrote:[color=blue]
> ... it nicely encapsulates the learning of "generators " so that
> when you see yield up front you know something generatish is going on.[/color]

+1 for "generatish " as VOTW (Vocabulation of the Week). =)

STeVe

[David Eppstein]

Re: yield_all needed in Python

In article <lcacpnxp8s.fsf @gaffa.mit.edu> ,
Douglas Alan <nessus@mit.edu > wrote:
[color=blue][color=green]
> > Cetainly, if <yield_all
> > iterator> == <for i in iterator: yield i>, I don't see how anything
> > is gained except for a few keystrokes.[/color]
>
> What's gained is making one's code more readable and maintainable,
> which is the one of the primary reasons that I use Python.[/color]

I don't see a lot of difference in readability and maintainability
between the two versions. And if yield_all is going to expand into the
loop, anyway, I'd prefer to make that obvious by using the for-loop
version, rather than using a keyword and pretending that passing the
iterators on has no overhead.

If we're talking about machinery behind the scenes to shortcut chains of
yield_all's, so that the time to pass items up through the chain is
smaller than it would be in the for-loop case, I'd think that would be a
better reason for a keyword, because it's not something that can be done
very easily without one in the current language. I don't know how to
make such shortcutting machinery faster than logarithmic in the worst
case (taking into account the possibility that multiple generators could
have yield_all's to the same iterator) but I think it could be made
nearly constant time in most situations. On the other hand, I'm not
convinced that this would be needed frequently enough to warrant the
complexity of trying to optimize it.

--
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/