6

The program below [Python 3.4] is a simple Eratosthenes sieve:

from itertools import *
def excl(ns,pr):
    return (i for i in ns if i%pr)
def sieve(ns):
    while True:
        pr=next(ns)
        yield pr
        ns=excl(ns,pr)
        # ns=(i for i in ns if i%pr)
r=list(islice(sieve(count(2)),10))

which produces [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]. OK. Uncommenting the line which inlines excl(), and commenting the call, gives [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]. Why?

Is it related to troubles expected when modyfing a sequence inside a loop which iterates over it?

Thank you for any hint.

Jerzy Karczmarczuk
  • 81
  • 2

1 Answers1

2

Your problem is that the pr referred to by the generator expression is the same pr that you modify in the next iteration of your while loop, so every number that is not divisible by the previous 'prime' number is treated as 'prime'. Which itself modifies pr and so in. In the excl function, the pr that you refer to is the one passed as an argument, which never changes.

pppery
  • 3,731
  • 22
  • 33
  • 46
  • I am not sure that I understand this answer. The prime pr doesn't change in excl (nor in the gen.expression), it changes within the loop, and this context is identical for the inlined and 'call' version. BTW I removed an erroneous remark about filter(). – Jerzy Karczmarczuk Oct 17 '15 at 20:57
  • @JerzyKarczmarczuk According to [PEP 227](https://www.python.org/dev/peps/pep-0227/), if a name is used within a code block(nested function), but it is not bound there and is not declared global, the use is treated **as a reference to** the nearest enclosing function region. As it applies to your case, the generator expression is a function under the hood, and it does not define the variable `pr`, so its `pr` is a **reference** to the `pr` in the enclosing function (`sieve`). Which means that when the `pr` in `sieve` changes, so does the `pr` in the generator expression. – pppery Oct 17 '15 at 21:09