470,648 Members | 1,396 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,648 developers. It's quick & easy.

genexp surprise (wart?)

I tried to code the Sieve of Erastosthenes with generators:

def sieve_all(n = 100):
# yield all primes up to n
stream = iter(xrange(2, n))
while True:
p = stream.next()
yield p
# filter out all multiples of p from stream
stream = (q for q in stream if q%p != 0)

# print primes up to 100
print list(sieve_all(100))

but it didn't work. I had to replace

stream = (q for q in stream if q%p != 0)

with

def s1(p):
return (q for q in stream if q%p != 0)
stream = s1(p)

or alternatively

stream = (lambda p,stream: \
(q for q in stream if q%p != 0)) (p, stream)

I had thought that genexps worked like that automatically, i.e. the
stuff inside the genexp was in its own scope. If it's not real
obvious what's happening instead, that's a sign that the current
behavior is a wart. (The problem is that p in my first genexp comes
from the outer scope, and changes as the sieve iterates through the
stream)

Oh well.
May 26 '06 #1
7 1169
Paul Rubin wrote:
I tried to code the Sieve of Erastosthenes with generators:

def sieve_all(n = 100):
# yield all primes up to n
stream = iter(xrange(2, n))
while True:
p = stream.next()
yield p
# filter out all multiples of p from stream
stream = (q for q in stream if q%p != 0)

# print primes up to 100
print list(sieve_all(100))

but it didn't work. I had to replace

stream = (q for q in stream if q%p != 0)

with

def s1(p):
return (q for q in stream if q%p != 0)
stream = s1(p)

or alternatively

stream = (lambda p,stream: \
(q for q in stream if q%p != 0)) (p, stream)

You do realize that you're creating a new level of generator nesting
with each iteration of the while loop, right? You will quickly hit the
maximum recursion limit. Try generating the first 1000 primes.

I had thought that genexps worked like that automatically, i.e. the
stuff inside the genexp was in its own scope. If it's not real
obvious what's happening instead, that's a sign that the current
behavior is a wart. (The problem is that p in my first genexp comes
from the outer scope, and changes as the sieve iterates through the
stream)

I don't see how it's a wart. p is accessed (i.e., not set) by the
genexp. Consistent with the function scoping rules in...
http://www.python.org/doc/faq/progra...bles-in-python
....Python treats p in the genexp as a non-local variable.

--Ben

May 26 '06 #2
"Ben Cartwright" <be****@gmail.com> writes:
You do realize that you're creating a new level of generator nesting
with each iteration of the while loop, right? You will quickly hit the
maximum recursion limit. Try generating the first 1000 primes.
Yes, I know about the generator nesting, that was the point. The
Sieve of Eraswhatsisname takes linear space by definition. It's
usually done with an array but this version uses nested generators
instead. I didn't bother to test whether they counted against the
recursion limit, so it's informative to know that they do.
I don't see how it's a wart. p is accessed (i.e., not set) by the
genexp. Consistent with the function scoping rules in...
http://www.python.org/doc/faq/progra...bles-in-python
...Python treats p in the genexp as a non-local variable.


Yeah, it's just counterintuitive is all. I guess the natural way to
express this would have been with tail recursion instead of a while
loop.
May 26 '06 #3
The generator is in its own scope. For proof, try accessing q outside
the generator.

There are two possibilities. The first is that you don't know what
closures are and are complaining that python has them. That would be
amusingly ironic, but I'm guessing you do know (if you don't, google
"make_adder" and be enlightened)

The second is that you don't like the late-binding behavior of
generator expressions. PEP 289 has this to say:
After much discussion, it was decided that the first (outermost)
for-expression should be evaluated immediately and that the remaining
expressions be evaluated when the generator is executed.
and:
After exploring many possibilities, a consensus emerged that [...] [for]
more complex applications, full generator definitions are always superior
in terms of being obvious about scope, lifetime, and binding


And as an illustration of that last point, consider:

def sieve_all(n = 100):
# generate all primes up to n

def filter_multiples(input, m):
for q in input:
if q % m != 0:
yield q

stream = iter(xrange(2, n))
while True:
p = stream.next()
yield p
# this is now a redundant comment.
# filter out all multiples of p from stream
stream = filter_multiples(stream, p)
p

May 26 '06 #4
Paul Rubin <http://ph****@NOSPAM.invalid> writes:
Yeah, it's just counterintuitive is all. I guess the natural way to
express this would have been with tail recursion instead of a while
loop.


FWIW, here's a listcomp version:

def s2(n=100):
stream = range(2,n)
while stream:
p = stream[0]
yield p
stream = [s for s in stream if s%p != 0]

print list(s2(100))

This should have the same space consumption and approx. running time
as the classic sieve. The genexp version actually used O(n/log(n))
space instead of linear space, I think.
May 26 '06 #5
Paul Rubin wrote:
I tried to code the Sieve of Erastosthenes with generators:

def sieve_all(n = 100):
# yield all primes up to n
stream = iter(xrange(2, n))
while True:
p = stream.next()
yield p
# filter out all multiples of p from stream
stream = (q for q in stream if q%p != 0)

# print primes up to 100
print list(sieve_all(100))

but it didn't work.


This is a known issue with the scope rules in loops which has bitten
many (including
myself; there is a long thread involving me and Jacek Generowitz
debating this at
death, you may find it if you google the newsgroup).

I would be curious to know if your code would work the way you expect
in Haskell
(I know it would for 'for' loop, dunno about 'while' loops, I am
completely ignorant
in Haskell).

Michele Simionato

May 26 '06 #6
"Paul Du Bois" <pa*********@gmail.com> writes:
The second is that you don't like the late-binding behavior of
generator expressions. PEP 289 has this to say:
After much discussion, it was decided that the first (outermost)
for-expression should be evaluated immediately and that the remaining
expressions be evaluated when the generator is executed.


Thanks. That PEP is informative. It shows that I stumbled into
something that other people found confusing too, and that alternatives
were considered that turned out not to be better.
May 26 '06 #7
Paul Rubin wrote:
"Paul Du Bois" <pa*********@gmail.com> writes:
The second is that you don't like the late-binding behavior of
generator expressions. PEP 289 has this to say:
After much discussion, it was decided that the first (outermost)
for-expression should be evaluated immediately and that the remaining
expressions be evaluated when the generator is executed.


Thanks. That PEP is informative. It shows that I stumbled into
something that other people found confusing too, and that alternatives
were considered that turned out not to be better.


The net effect of the bad version seems to be that you're
not getting a new generator from
stream = (q for q in stream if q%p != 0)
(* disassembly shown below.)

Disassembly seems to show the program getting a pre-compiled
generator expression code block, and binding the new value
of p to it, then getting iter(stream), which is stream. As
Paul Du Bois says, the outer loop is fixed, but the
subsequent if-expression is liable to change.

So 3 passes because 3%2 != 0
4 passes because 4%3 != 0
5 passes because 5%4 != 0
and so on.
Interesting.

* Disassembly of stream = ...:

6 47 LOAD_CLOSURE 0 (p)
50 LOAD_CONST 2 (<code object
<generator expression> at 009D65E0, file "try_eratos.py",
line 6>)
53 MAKE_CLOSURE 0
56 LOAD_FAST 1 (stream)
59 GET_ITER
60 CALL_FUNCTION 1
63 STORE_FAST 1 (stream)
May 26 '06 #8

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

2 posts views Thread by rw | last post: by
2 posts views Thread by Bryan | last post: by
reply views Thread by Boris Borcic | last post: by
3 posts views Thread by Rakesh Parekh | last post: by
16 posts views Thread by Sathyaish | last post: by
4 posts views Thread by Giovanni Bajo | last post: by
10 posts views Thread by codefire | last post: by
4 posts views Thread by Paul Rubin | last post: by
1 post views Thread by Korara | last post: by
reply views Thread by warner | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.