pythonclosurespython-internalssieve-of-eratosthenesgenerator-expression# Python generator expression recursion

### Practical limitations

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:

- Is it adding a stack frame for each nested generator call?
- Does it just need to create a closure object?
- 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?

Solution

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.

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.

- AttributeError: install_layout when attempting to install a package in a virtual environment
- Python list comprehension - want to avoid repeated evaluation
- Hash algorithm for dynamic growing/streaming data?
- matplotlib - making labels for violin plots
- Python How to I check if last element has been reached in iterator tool chain?
- Polars and the Lazy API: How to drop columns that contain only null values?
- Why are my Mean, Var, and Std outputs from NumPy different from what the online grader expects?
- Correlation dataframe convertion from results from pl.corr
- Polars DataFrame transformation
- Discord rate limiting while only sending 1 request per minute
- Check if column contains (/,-,_, *or~) and split in another column - Pandas
- How to draw a rectangle at (x,y) in a PyQt GraphicsView?
- how to calculate correlation between ten columns with polars
- How to set class attribute with await in __init__
- Detect hindi encoding, response received from Facebook API in Python
- Is it possible to write a horizontal if statement with a multi-line body?
- Max length of items in list
- Cannot subclass multiprocessing Queue in Python 3.5
- How can I get notified of updates to Python packages in a unified way?
- Using python AST to traverse code and extract return statements
- merge groups of columns in a polars dataframe to single columns
- Group Pandas DataFrame by Continuous Date Ranges
- Flask login @login_required not working
- Odoo: one2many and many2one? KeyError:'___'
- merge some columns in a Polars dataframe and duplicate the others
- Python: Create table from string mixed with separators using FOR loops
- How do I type hint a method with the type of the enclosing class?
- How can I verify an emails DKIM signature in Python?
- Writing a class that accepts a callback in Python?
- Python Paramiko channel.exec_command not returning output intermittently