Python generator expression recursion

This is a question about Python internals. The following code is taken from this video about laziness in python:

def nats(n):
    yield n
    yield from nats(n + 1)


def sieve(s):
    n = next(s)
    yield n
    yield from sieve(i for i in s if i % n != 0)

s = sieve(nats(2))
print(next(s), next(s), next(s), next(s), next(s)) # Primes: 2, 3, 5, 7, 11...

The sieve function generates prime numbers lazily (read this for the original concept). Conceptually, we add filters to the “sieve”, so every number (say, 10) is tested against all the previously found prime numbers (so 2, 3, 5 and 7) until the next prime is found, i.e. 11. 11 is then added to the “list” of filters, and so on.

This part (i for i in s if i % n != 0) is a generator expression (or “comprehension”).

My question relates to the mechanism with which Python uses to “nest” these generator expressions. For example, let’s use two possible passes through the expression:

The first time we go through it, we take nats (for natural numbers) and add the 2 filter to it.

The second time, we take our generator which already “goes through” nats and the 2 filter, and add the 3 filter to it. We are yielding from [3,2,nats], which yields from [2,nats], which yields from [nats]. The point is, clearly some preservation of a context of variables is necessary for each layer pass, as each layer “sees” a different n for example.

But what exactly is Python doing here? Here are a few options I thought were possible:

1. Is it adding a stack frame for each nested generator call?
2. Does it just need to create a closure object?
3. Maybe python “compresses” the generator into one generator analogous to this expression: i % 2 != 0 and i % 3 != 0 and i % 4 !=0?

Or maybe I’m missing something fundamental about what is happening here?

Answer

clearly some preservation of a context of variables is necessary for each layer pass, as each layer “sees” a different n for example.

Yes, this is not specific to generators, but to any function call: if that function calls a function (possibly itself), then its local variables are preserved in a stack frame, and the new function execution context gets its own set of local variables.

Is it adding a stack frame for each nested generator call?

Yes. So in the case of sieve, each execution context of sieve has its own n and s variables.

In the expression that sieve passes to the recursive call, it is creating a new, more restrictive, iterator from the existing one it got as argument. We could work backwards to see what the complete iterator looks like.

The first recursive call, can be expanded to:

yield from sieve(i for i in 
                   (i for i in nat(3))   # this is roughly `s`
                 if i % 2 != 0)

I write nat(3) instead of nat(2) because the value 2 was already consumed from that iterator.

That recursive call will then yield 3, and make the next recursive call:

yield from sieve(i for i in 
                   i for i in                 # }
                     (i for i in nat(3))      # } this is roughly `s` 
                   if i % 2 != 0 and i != 3)  # }
                 if i % 3 != 0)

Again, I add and i != 3 because 3 was already consumed with a separate next(s) call.

…and so it continues.

Practical limitations

As you can imagine, this is very memory consuming. At each recursive call, the call stack usage increases, and each iterator in the nested construction of iterators is a variable s in one of the execution contexts of sieve, and must do its job.

Although this looks elegant from a theoretical perspective, it is not practical in a real implementation: the number of primes you can generate before bumping into a “maximum recursion depth exceeded” kind of error will be disappointingly little. When running it on repl.it the last prime generated before the error was 3559.