Unexpected behavior with iterators

Question

I tried to implement the sieve of Eratosthenes with iterators (because I wanted to get more into functional programming with python). Sadly some unexpected behaviour occurred. You can see it here in this video: https://i.stack.imgur.com/woEu5.jpg

Here is my code:

def sieve_primes(stop=10):
    L = (x for x in range(2, stop+1))
    while True:
        prime = next(L)
        L = filter(lambda x: x % prime != 0 or x == prime, L)
        #L, M = itertools.tee(L)
        #print(list(M))
        yield prime

It works (spits out an iterator object with the desired primes) when the two commented lines are uncommented. Otherwise, it just iterates over every number.

I'm looking forward to your answers :) Thanks!

I suspect you're seeing an issue with the scope `prime` is bound in. Try `lambda x, prime=prime:` in your lambda definition — Patrick Haugh, Feb 13 '20 at 21:49
@PatrickHaugh Great, It worked! Can you explain me what the bug was? I don't really understand what I changed. Thank you in advance! — ixam07, Feb 13 '20 at 21:52
Why do you do `while True: prime = next(L)` instead of just `for prime in L:`? Why do you turn the `range` into a generator? BTW welcome to Stack Overflow! Check out the [tour]. — wjandrea, Feb 13 '20 at 22:04
@wjandrea The `while True` was just supposed the be a temporary solution. I know that I made things more complicated as they should be, but I really wanted to test out my understanding of iterators. I still struggle why my code did not work before, is it some "nasty" kind of closure which sabotaged me? — ixam07, Feb 13 '20 at 22:13
@wjandrea Since they're redefining `L` every loop, they can't do `for prime in L`. That would create an iterator over the original `L` that wouldn't be updated to reflect the various filters — Patrick Haugh, Feb 13 '20 at 22:14
@ixam07 See this similar question, it has some more detailed answers, though they don't address why `tee` is changing your output: https://stackoverflow.com/questions/19837486/python-lambda-in-a-loop — Patrick Haugh, Feb 13 '20 at 22:15

score 1 · Answer 1 · answered Feb 13 '20 at 22:12

1

You're using the variable prime in your lambda, which is a reference that you are inheriting from the enclosing scope. When your code evaluates the lambda, it will use whatever value is bound to that reference in the scope the reference is inherited from. When you're not using tee and evaluating the list, all the lambda functions are identical, and are using the same value for prime.

tee works by just storing the results in a list and giving them to you from that list when you ask again later, so for each value of prime it actually applies the filter to all of the values from L

You can fix this by binding prime in the scope of the lambda by passing it as an argument with a default value. This saves that value as part of the function object, and the reference prime is then a local reference to that stored value.

answered Feb 13 '20 at 22:12

Patrick Haugh

59,226
13
88
96

1

Okay, I think I got it! This actually reminds me of an example in the "You don't know JS" book series, where `for (var i=1; i<=5; i++) { setTimeout( function timer(){ console.log( i ); }, i*1000 ); }` prints "6", five times, instead of the expected "1 2 3 4 5". Thank you for your explanation! It reminded me of forgotten concepts :D – ixam07 Feb 13 '20 at 22:30
@Patrick Haugh You are correct about lambda *it will use whatever value is bound to that reference* but not correct here *all the lambda functions are identical, and are using the same value for prime*. The problem is more than just lambda but it's a combination of lambda and lazy evaluation of filter. – Ch3steR Feb 13 '20 at 23:42
@Ch3steR In what way is it incorrect? All of the lambda functions share the same definition, and will produce identical results for all inputs, won't they? – Patrick Haugh Feb 13 '20 at 23:44
@PatrickHaugh I thought same until I now. I tested it various conditions. Your correct about lambda's use whatever value is bound to that reference. `prime` is actually changing in each iteration. I'm posting detailed answer iteration by iteration analysis.May take some time. – Ch3steR Feb 13 '20 at 23:47
@Ch3steR To be clear, I'm saying that the multiple lambda functions that are created are all the same, and that they all change every iteration of the loop. So instead of a unique lambda function for each of the Pi(x) primes less than x, we have Pi(x) lambda functions being used as filters that are all the same, though `prime` itself changes every iteration. – Patrick Haugh Feb 13 '20 at 23:52
@PatrickHaugh Posted the answer. Hoping it adds some more clarity to future reads after reading your answer. – Ch3steR Feb 14 '20 at 00:31

Ch3steR · Accepted Answer · 2020-02-19T04:01:15.830

def sieve_primes(stop=10):
    L = (x for x in range(2, stop+1))
    while True:
        prime = next(L)
        L = filter(lambda x: x % prime != 0 or x == prime, L)
        yield prime

What exactly is happening in your code is given below iteration by iteration. For convenience in I represent L as L1 in 1st iteration, L as L2 in 2nd iteration, so on.

In 1st iteration prime=next(L) which is 2 (as expected). L1=filter(lambda x: x % prime != 0 or x == prime, L) (Values of L are calculated lazily i.e values calculated only on demand. yield prime will yield 2 expected.
In 2nd iteration prime=next(L1). Here comes the tricky part. L1 is filter object whose values are calculated only on demand. So, in 2nd iteration when prime=next(L1) is executed only one value is calculated from L. Now the lambda uses prime as 2 and calculates one value which is 3 (3%2!=0) which is now prime. L2=filter(lambda x: x % prime != 0 or x == prime, L1) (Values of L2 are calculated lazily i.e values calculated only on demand. Now you yield prime will yield 3.
In 3rd iteration prime=next(L2). Now things get little complicated. To get one value from L2 you need to calculate one value of L1 and to calculate one value L1 you need to calculate one values L. If you remember correctly L will now yield 4 which will now be used by L1 to produce one value. But the latest reference to prime is 3. 4%3!=0 is evaluated to True. So, L1 yields 4. So, calculate the value to be yielded by L2 4%3!=0 is evaluated to True so prime=next(L2) is 4.

Apply same logic for further iterations you will find 5,6,7,8,9... will be yielded in further iterations.

score 0 · Answer 3 · answered Feb 13 '20 at 22:01

0

How about the following? You're usually better off using generator expressions than map/filter/reduce.

#!/usr/bin/env python3


def sieve_primes(stop=100):
    primes = []
    for candidate in range(2, stop+1):
        if not any(candidate % prime == 0 for prime in primes):
            primes.append(candidate)
            yield candidate


for prime in sieve_primes():
    print(prime)

answered Feb 13 '20 at 22:01

dstromberg

6,954
1
26
27

BTW, you can get a 2x speedup by using range(2, stop+1, 2) and adding 2 to the primes list at creation time. – dstromberg Feb 13 '20 at 22:04

Unexpected behavior with iterators

3 Answers3