The Iteration Protocol & Lazy Evaluation

The iteration protocol is one of the most fundamental abstractions in Python. By decoupling underlying data storage from sequential traversal state, Python enables lazy evaluation: sequence elements are computed on demand rather than materialized in memory simultaneously.

This architecture allows Python applications to stream gigabytes of logs or infinite numeric series within an invariant $O(1)$ memory footprint.

Stream Memory FootprintComplexity

O(1)

Lazy iterators yield items one at a time, requiring constant memory regardless of stream length.

1. Formal Mathematical Specification of Iteration#

The iteration protocol formalizes the contract between an iterable collection and an active iterator cursor:

\text{Iterable Protocol}: I \xrightarrow{\text{\_\_iter\_\_()}} \text{Iter}

\text{Iterator Protocol}: \text{Iter} \xrightarrow{\text{\_\_next\_\_()}} v \in \mathcal{O} \quad \lor \quad \text{raise StopIteration}

Architecture Diagram

Rendering diagram...

Formally, an iterator is a state machine $(S, s_0, f)$ where:

$S$ is the internal iterator state set (e.g. current index or pointer offset).
$s_0 \in S$ is the initial state at instantiation.
$f: S \to (S \times \mathcal{O}) \cup \{\bot\}$ maps current state to updated state and yielded value $v$ , or terminal exhaustion state $\bot$ ( $\text{StopIteration}$ ).

2. C-API Implementation: `tp_iter` & `tp_iternext`#

At the C level, Python checks whether an object implements the iteration protocol by inspecting dedicated slots in its PyTypeObject:

Step 1: Acquiring the Iterator via `tp_iter`

When iter(obj) is called, CPython inspects obj->ob_type->tp_iter. If non-NULL, the interpreter invokes this function pointer to allocate and return a new iterator struct.

Step 2: Extracting Values via `tp_iternext`

When next(iterator) or the FOR_ITER bytecode executes, CPython invokes iterator->ob_type->tp_iternext(iterator) directly in C.

Step 3: Handling Value vs Exhaustion

If tp_iternext returns a non-NULL PyObject*, the pointer is pushed onto the frame stack.
If tp_iternext returns NULL, CPython inspects thread error state. If StopIteration was raised, the loop terminates cleanly; any other error propagates as an unhandled exception.

3. Implementing Custom Iterators#

An object is an iterable if it implements __iter__(). An object is an iterator if it implements both __iter__() (returning self) and __next__():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class PrimeNumberStream:
    """Infinite iterator yielding prime numbers on demand."""
    def __init__(self):
        self.candidate = 2

    def __iter__(self):
        # An iterator must return itself from __iter__
        return self

    def _is_prime(self, n: int) -> bool:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True

    def __next__(self) -> int:
        while True:
            current = self.candidate
            self.candidate += 1
            if self._is_prime(current):
                return current

# Lazy consumption: Constant memory!
primes = PrimeNumberStream()
first_five = [next(primes) for _ in range(5)]
print(f"First five primes: {first_five}")  # [2, 3, 5, 7, 11]

4. Lazy Evaluation vs Eager Materialization#

Compare the memory consumption of building a complete list versus using a generator iterator:

Architecture Diagram

Rendering diagram...

Composable Stream Pipelines

Standard library modules like itertools enable functional stream pipelines. Functions like itertools.islice, itertools.chain, and itertools.groupby process data lazily with zero intermediate list allocations.

5. Concept Verification#

Test your understanding of the iteration protocol:

Concept check

What are the formal requirements for an object to satisfy the Python Iterator Protocol?