Python's Old Iteration Protocol

Iteration In Python

(If you're familiar with the current state of Python iteration, feel free to skip ahead to The Old Iteration Protocol.)

Iteration is the ability to operate on the members of a collection [1] individually, one after the other. It is commonly used in for loops.

>>> collection = [1, 2, 3]
>>> for member in collection:
...     print(member)
1
2
3

There's a lot going on behind the scenes there, which makes it harder to discuss the concepts involved in iteration. To bring those concepts into focus, let's pull back the curtain and look at what's actually going on. We can do this by noting that a for loop could be considered syntactic sugar for an equivalent while loop.

>>> collection = [1, 2, 3]
>>> iterator = iter(collection)
>>> while True:
...    try:
...        member = next(iterator)
...    except StopIteration:
...       break
...    else:
...       print(member)
1
2
3

In this example, we want to iterate over the value of the variable collection. Python provides two built-in functions that help us.

The first function is iter, which takes a collection (also known as an iterable) and returns an iterator (conveniently stashed in the variable named iterator). An iterator is an object that keeps track of the state of the iteration, i.e., what members have been seen and what members are still to come.

The second built-in function is next which takes an iterator and returns its next member. When the iterator is out of members, next will raise the StopIteration exception.

A for loop, then, just knows to call iter at the beginning, next as needed, and catch StopIteration at the end.

Iterables and Iterators

Recall that being iterable means that when passed to iter we get back an iterator. The types Iterable and Iterator formally define what this post has been describing in words. Many built-in types are iterable (and thus Iterable), including lists, tuples, sets, and dictionaries.

>>> from collections.abc import Iterable
>>> from collections.abc import Iterator
>>> isinstance([], Iterable)
True
>>> isinstance(iter([]), Iterator)
True
>>> iter([])
<list_iterator object at 0x1042244a8>

>>> isinstance((), Iterable)
True
>>> isinstance(iter(()), Iterator)
True
>>> iter(())
<tuple_iterator object at 0x1042244a8>

>>> isinstance(set(), Iterable)
True
>>> isinstance(iter(set()), Iterator)
True
>>> iter(set())
<set_iterator object at 0x10422ed38>

>>> isinstance({}, Iterable)
True
>>> isinstance(iter({}), Iterator)
True
>>> iter({})
<dict_keyiterator object at 0x104221278>

>>> class MyIterable(object):
...     def __init__(self, count):
...        self.count = count
...     def __iter__(self): # This makes this object Iterable
...         return MyIterator(self.count)
...
>>> class MyIterator(object):
...     def __init__(self, count):
...        self.count = count
...        self.value = 0
...     def __next__(self):
...         if self.value >= self.count:
...            raise StopIteration()
...         self.value += 1
...         return self.value
...     def __iter__(self):
...         return self
...
>>> collection = MyIterable(3)
>>> isinstance(collection, Iterable)
True
>>> for i in collection:
...     print(i)
...
1
2
3

>>> iterator = iter([])
>>> iterator
<list_iterator object at 0x1042244a8>
>>> iter(iterator)
<list_iterator object at 0x1042244a8>
>>> iter(iterator) is iterator
True

>>> iterator = iter([1, 2, 3])
>>> for member in iterator:
...    print(member)
1
2
3

>>> iterable = MyIterable(3)
>>> 1 in iterable
True
>>> 1 in iterable
True
>>> iterator = iter(iterable)
>>> 1 in iterator
True
>>> 1 in iterator
False

The Old Iteration Protocol

The above describes the way iteration in Python works now. But it wasn't always this way. If you've been following along with the links to the Python documentation, you saw that __contains__ referenced "the old sequence iteration protocol." The Iterable class referenced some other way to iterate besides __iter__, and the documentation on iterable types stated that sequence types are always iterable without saying why or how.

It all goes back to Python 2.2, when iter was first introduced, along with the special methods __iter__ and __next__ [2]. Prior to that, the only thing that for knew how to iterate was sequences like lists. for member in sequence: print(member) would have looked something like this as a while loop.

sequence = [1, 2, 3]
_i = 0
while 1: # `True` wasn't a built-in yet
    try:
      member = sequence[i]
    except IndexError:
      break
    else:
      print(member)
    _i += 1

In other words, for was implemented by calling __getitem__ with ever-increasing integers until it "ran off the end" and the sequence raised IndexError.

This was suboptimal. For one thing, dictionaries couldn't be iterated with a for loop—their keys (usually) weren't sequential increasing integers, and misses raise KeyError instead of IndexError. For another thing, if you had a custom type you wanted to make iterable—such as a set which wasn't standard until Python 2.4—you had to also make it subscriptable, which may not make any sense (sets aren't ordered).

Python's BDFL [3] and others recognized the shortcomings, wrote PEP 234 to give us iterables and iterators, and the rest is history.

>>> class MySequence:
...     def __getitem__(self, i):
...         if i > 3:
...             raise IndexError()
...         return str(i)
...
>>> for member in MySequence():
...    print(member)
...
0
1
2
3

>>> isinstance(MySequence(), Iterable)
False
>>> iter(MySequenc())
<iterator object at 0x10e1e7790>

>>> import bisect
>>> class ContainerOfSortedStrings(object):
...   def __init__(self):
...      self._strings = []
...   def __setitem__(self, key, value):
...      assert isinstance(key, str) and isinstance(value, str)
...      bisect.insort_left(self._strings, (key, value))
...   def __getitem__(self, key):
...      return self._strings[bisect.bisect_left(self._strings, (key,))]

>>> cs = ContainerOfSortedStrings()
>>> cs['key'] = 'value'
>>> cs['key']
('key', 'value')
>>> for member in cs: print(member)
Traceback (most recent call last)
TypeError: '<' not supported between instances of 'str' and 'int'

>>> class OldStyle:
...     pass
...
>>> container = [1, 2, 3]
>>> old_style = OldStyle()
>>> old_style.__getitem__ = container.__getitem__
>>> for i in old_style:
...     print(i)
...
1
2
3