Iterables, Iterators and Generators

Ian Ward

Ottawa Python Authors Group, 24 January 2013

https://github.com/wardi/iterables-iterators-generators (or http://bit.ly/itergen )

A Gentle Introduction

The first few examples are from Ned Bachelder's Python Iteration Talk http://bit.ly/pyiter

Coming from another language you might find it natural to create a counter and increment it to iterate over a list in Python

In [1]:
my_list = [17, 23, 47, 51, 101, 173, 999, 1001]

i = 0
while i < len(my_list):
    v = my_list[i]
    print v
    i += 1
17
23
47
51
101
173
999
1001

You might also have been told about range() which almost lets you write a C-style for loop

In [2]:
for i in range(len(my_list)):
    v = my_list[i]
    print v
17
23
47
51
101
173
999
1001

But neither of the above are natural ways of iterating in python. We do this instead:

In [3]:
for v in my_list:
    print v
17
23
47
51
101
173
999
1001

Many types of objects may be iterated over this way. Iterating over strings produces single characters:

In [4]:
for v in "Hello":
    print v
H
e
l
l
o

Iterating over a dict produces its keys (in no particular order):

In [5]:
d = {
    'a': 1,
    'b': 2,
    'c': 3,
    }

for v in d:
    print v
# Note the strange order!
a
c
b

Iterating over a file object produces lines from that file, including the line termination:

In [6]:
f = open("suzuki.txt")
for line in f:
    print ">", line
> On education

> "Education has failed in a very serious way to convey the most important lesson science can teach: skepticism."

> "An educational system isn't worth a great deal if it teaches young people how to make a living but doesn't teach them how to make a life."

Objects that can be iterated over in python are called "Iterables", and a for loop isn't the only thing that accepts iterables.

The list constructor takes any iterable. We can use this to make a list of the keys in a dict:

In [7]:
list(d)
Out[7]:
['a', 'c', 'b']

Or the characters in a string:

In [8]:
list("Hello")
Out[8]:
['H', 'e', 'l', 'l', 'o']

List comprehensions take iterables.

In [9]:
ascii = [ord(x) for x in "Hello"]
ascii
Out[9]:
[72, 101, 108, 108, 111]

The sum() function takes any iterable that produces numbers.

In [10]:
sum(ascii)
Out[10]:
500

The str.join() method takes any iterable that produces strings.

In [11]:
"-".join(d)
Out[11]:
'a-c-b'

Iterables can produce any python object. The re.finditer() function returns an iterable that produces re.match objects.

In [12]:
import re
suzuki = open("suzuki.txt").read()
for match in re.finditer(r'\bs\w+', suzuki):
    print match.group(0)
serious
science
skepticism
system

A "classic" iterable class

Very old versions of Python supported iteration through the __getitem__() method, and this is still supported.

In [13]:
class Lucky(object):
    def __getitem__(self, index):
        if index > 3:
            raise IndexError
        return 7

Lucky is a class that will return 7 for any index less than or equal to 3:

In [14]:
lucky = Lucky()

lucky[0]
Out[14]:
7

And raise an IndexError for larger indexes:

In [15]:
lucky[6]
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
/home/ian/git/iterables-iterators-generators/<ipython-input-15-5c0a87559915> in <module>()
----> 1 lucky[6]

/home/ian/git/iterables-iterators-generators/<ipython-input-13-bd578dbfbead> in __getitem__(self, index)
      2     def __getitem__(self, index):
      3         if index > 3:
----> 4             raise IndexError
      5         return 7

IndexError: 

This is a perfectly well-behaved python iterable. We can loop over it:

In [16]:
for number in lucky:
    print number
7
7
7
7

Or pass it to functions that take iterables:

In [17]:
list(lucky)
Out[17]:
[7, 7, 7, 7]

Even the in operator works with it:

In [18]:
7 in lucky
Out[18]:
True

But writing this sort of class it difficult. You need to be able to return a value for any index passed to __getitem__() but most of the time you really only want to produce items in order from first to last.

Enter "Iterators".

Iterators

The naming is confusingly similar here, but it's important to understand the difference between iterables and iterators.

Iterators are iterables with some kind of 'position' state and a .next() method. The .next() method may be called to produce the next item and update the internal state.

Iterables are objects that produce an iterator when they are passed to the iter() builtin.

Iterators are Iterables with .next()

Calling iter() on our "classic" iterable object produces a plain iterator instance

In [19]:
i = iter(lucky)
i
Out[19]:
<iterator at 0x288cc10>

This plain iterator has a counter and the original object as its internal state. Calling .next() advances the counter and calls our "classic" iterable's .__getitem__() method.

In [20]:
print i.next()
print i.next()
print i.next()
print i.next()
7
7
7
7

When we get to the end however, our IndexError exception is turned into a StopIteration exception. This is the iterator protocol: when .next() raises StopIteration there are no more items to be produced.

In [21]:
print i.next() # raises StopIteration, *not* IndexError
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
/home/ian/git/iterables-iterators-generators/<ipython-input-21-b3e04e043095> in <module>()
----> 1 print i.next() # raises StopIteration, *not* IndexError

StopIteration: 

Remember that an iterator is an iterable, so it can be passed to anything that takes an iterable.

Be careful, though. Iterators may only be iterated over once, since they are updating their internal state as they go. If we try to iterate twice, the second time will produce no more items:

In [22]:
i = iter(lucky)
print list(i)
print list(i)
[7, 7, 7, 7]
[]

Calling on iter() on an iterable will produce a different iterator object each time.

In [24]:
i is iter(lucky)
Out[24]:
False

Also, like other iterables, calling iter() on an iterator works, but it behaves differently!

Calling iter() on an iterator typically returns the exact same iterator. If you think about it, that's all that can be done because you can't rewind or duplicate an iterator in the general case.

In [23]:
i is iter(i)
Out[23]:
True

Iterators come in all shapes and sizes.

xrange() has a rangeiterator:

In [25]:
iter(xrange(20))
Out[25]:
<rangeiterator at 0x2896900>

dict has a dictionary-keyiterator:

In [26]:
iter({'a': 1, 'b': 2})
Out[26]:
<dictionary-keyiterator at 0x2894aa0>

list doesn't even use the plain iterator type, and instead uses its own more efficient listiterator:

In [27]:
iter([4, 5, 6])
Out[27]:
<listiterator at 0x28973d0>

And some have names that provide no clue what they iterate over:

In [28]:
re.finditer(r'\bs\w+', "some text with swords")
Out[28]:
<callable-iterator at 0x28971d0>

A better iterable class

You can choose the iterator that will be returned by iter() by defining your own .__iter__() method:

In [29]:
class Countdown(object):
    def __iter__(self): # must return an iterator!
        return iter([5, 4, 3, 2, 1, 'launch'])

The for loop and other places that take iterables internally use iter(), which calls our new .__iter__() method to create an iterator:

In [30]:
for n in Countdown():
    print n
5
4
3
2
1
launch

Iterators the hard way

The example above is fine if we want to reuse an existing iterator (like the listiterator above), but what if we want to write a new iterator?

We know the protocol, so one approach is to just implement it:

In [31]:
class CountdownIterator(object):
    def __init__(self):
        self._remaining = [5, 4, 3, 2, 1, 'launch']
        
    def __iter__(self):
        return self
    
    def next(self):
        if not self._remaining:
            raise StopIteration
        return self._remaining.pop(0)

Our internal 'position' state is a list of items we pop one at a time when .next() is called. We implement .__iter__() in the normal way for an iterator: "return self". We raise StopIteration when we have nothing left to produce.

This works as expected, but it's rather a lot of code for a simple result.

In [32]:
for n in CountdownIterator():
    print n
5
4
3
2
1
launch

Generators

A generator function is a simpler way to create an iterator.

Generator functions let you use local variables and the position of the program counter as state for a generator object. A new generator object is created and returned each time you call a generator function. The generator object is an iterator.

Generators are Iterators created with a generator function or expression

Here is a generator function that only uses the program counter for state:

In [33]:
def countdown_generator():
    yield 5
    yield 4
    yield 3
    yield 2
    yield 1
    yield 'launch'

When we call the generator function it does nothing except create a new generator object. None of the code in the generator function has been executed yet.

In [34]:
countdown_generator()
Out[34]:
<generator object countdown_generator at 0x289d0f0>

As the generator object is iterated over execution starts, following the generator function definition until the next yield statement.

When it reaches the yield statement execution is paused (the program counter is stored) and the value on the right of the yield statement is produced as a value from the generator object. Execution is resumed from the stored program counter position when iteration continues.

When the generator function reaches the end, the generator raises a StopIteration exception just like a normal iterator. And it behaves just like a normal iterator:

In [35]:
for n in countdown_generator():
    print n
5
4
3
2
1
launch

Now we have a much more concise way of defining our own iterator for an iterable class. The .__iter__() method of our class can be written as a generator function:

In [36]:
class Countdown(object):
    def __iter__(self):
        for n in [5, 4, 3, 2, 1, 'launch']:
            yield n
In [37]:
for n in Countdown():
    print n
5
4
3
2
1
launch

But, enough about classes. Let's dig further into how these generators work.

Recall that execution of the code in a generator function does not proceed until the generator object returned is iterated over. That lets us put things in a generator that might be expensive, knowing that we will only have to pay that cost when we actually ask it to produce the next item.

This generator causes a for loop to slow down between iterations. First waiting 5 seconds, then counting down from "5" to "1" with 1 seconds intervals in between:

In [38]:
import time

def slow_generator():
    time.sleep(5)
    yield 5
    time.sleep(1)
    yield 4
    time.sleep(1)
    yield 3
    time.sleep(1)
    yield 2
    time.sleep(1)
    yield 1
    time.sleep(1)

print "starting"
for n in slow_generator():
    print n
print "done"
starting
5
4
3
2
1
done

Another way of writing this code is to turn the generator inside-out.

Instead of sleeping inside the generator we can yield the amount of time we want to sleep. And instead of yield-ing the countdown we can use a function passed in to display values to the user.

In [39]:
##
def countdown_generator(fn):
    yield 5
    fn(5)
    yield 1
    fn(4)
    yield 1
    fn(3)
    yield 1
    fn(2)
    yield 1
    fn(1)
    yield 1

A show() function takes the place of the print inside the loop, and the time.sleep() call is done by the code iterating over the generator. This puts the code driving the generator in charge of how (or if) it sleeps for the given time.

In [40]:
def show(n):
    print n

print "starting"
for s in countdown_generator(show):
    time.sleep(s)
print "done"
starting
5
4
3
2
1
done

Generators as coroutines

While a generator object is an iterator, it can also be used for much more.

When paused at a yield statement generator objects can receive data by using .send() instead of .next().

When we use yield as an expression or assign it to a variable, the value passed to .send() is available inside the generator.

In [41]:
def knock_knock():
    name = yield "Who's there?"
    yield "%s who?" % name
    yield "That's not funny at all"

We have to switch to manually calling .next() on our generator object, because a for loop or function that takes an iterable won't be able to call .send() when we need to.

In [42]:
k = knock_knock()
k.next()
Out[42]:
"Who's there?"

At this point execution is paused at the first yield. The assignment to the variable name hasn't happened yet. But when we .send() a value execution continues:

In [43]:
k.send("David")
Out[43]:
'David who?'

And in the generator object we are at the second yield with "David" assigned to name.

If we send something to a yield that isn't being used as an expression, the value we send will be ignored:

In [44]:
k.send("David the environmentalist")
Out[44]:
"That's not funny at all"

But execution continues the same as if we called .next().

This is the end of part 1.

In part 2 we will build a simple interactive network game with 90% of the code written as generators. I will show how breaking down asynchronous code into generators can make it easy to test, easy to reuse, and (with some practice) easy to understand.


Generators in Depth

Generators' ability to accept as well as produce data is useful for many purposes. The interface to generator objects is limited, unlike instances of classes we create, but generators enable a very powerful programming style.

Here is a "running average" calculator implemented as a generator. As shown in the previous section the generator state (total, count) is stored in local variables.

Notice the extra parenthesis around the first yield expression. This is required any time yield doesn't appear immediately to the right of an assignment operator.

In [1]:
##
def running_avg():
    "coroutine that accepts numbers and yields their running average"
    total = float((yield))
    count = 1
    while True:
        i = yield total / count
        count += 1
        total += i

This type of generator is driven by input to .send(). However, the code inside a generator must execute up to the first yield expression before it can accept any value from the caller. That means that the caller always has to call .next() (or .send(None)) once after creating a generator object before sending it data.

If you try to send a value first instead, Python has a helpful error for you.

In [2]:
r = running_avg()
r.send(10)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-8c08c6a44ff3> in <module>()
      1 r = running_avg()
----> 2 r.send(10)

TypeError: can't send non-None value to a just-started generator

So let's call .next() to advance the program counter to the first yield expression, then start passing values we would like averaged.

In [3]:
r.next()
r.send(10)
Out[3]:
10.0
In [4]:
r.send(5)
Out[4]:
7.5
In [5]:
r.send(0)
Out[5]:
5.0
In [6]:
r.send(0)
Out[6]:
3.75

A convenient decorator

The flow is always the same when working with generators.

  1. a generator object is created by the caller
  2. the caller starts the generator
  3. the generator passes data to the caller (or signals the end of the sequence)
  4. the caller passes data to the generator
  5. repeat from (3)

For generators that are driven by input to .send() no data is transferred in the first 3 steps above.

This is a decorator that arranges for .next() to be called once immediately after a generator is created. This will turn a generator function into a function that returns a generator immediately ready to receive data (step 4).

In [51]:
##
def advance_generator_once(original_fn):
    "decorator to advance a generator once immediately after it is created"
    def actual_call(*args, **kwargs):
        gen = original_fn(*args, **kwargs)
        assert gen.next() is None
        return gen
    return actual_call

We apply our decorator to running_avg().

In [ ]:
##
running_avg = advance_generator_once(running_avg)

And now we don't need to call .next() every time we create a new running average generator.

In [52]:
r = running_avg()
r.send(42)
Out[52]:
42.0

Coroutine development is protocol development

As shown, one of the ways to pass a message to a generator is with .send(). This interface allows you to pass a single object to a generator. For this object we can pass tuples, dicts or anything else we choose.

You decide the protocol for your generator by documenting the types and values of objects you will send from caller to generator and yield from generator to caller.

Tuples are perfect for a generator that needs two objects each time, e.g. a player number and a key press.

This is a Rock-Paper-Scissors game where each player's play is passed in separately, and once both players have played the result of the game is yielded. Players can change their mind choose a different play if the other player hasn't chosen yet. Games will continue indefinitately.

This generator uses a common pattern of storing the result that will be yielded in a local variable so that there are fewer yield statements in the generator function. Having fewer yield statements makes it easier to understand where it is possible for execution to be paused within the generator function.

The outer while loop runs once for each full game. The inner while loop collects input from the users until the game result can be decided.

In [53]:
##
@advance_generator_once
def rock_paper_scissors():
    """
    coroutine for playing rock-paper-scissors

    yields: 'invalid key': invalid input was sent
            ('win', player, choice0, choice1): when a player wins
            ('tie', None, choice0, choice1): when there is a tie
            None: when waiting for more input

    accepts to .send(): (player, key):
        player is 0 or 1, key is a character in 'rps'
    """
    valid = 'rps'
    wins = 'rs', 'sp', 'pr'
    result = None

    while True:
        chosen = [None, None]
        while None in chosen:
            player, play = yield result
            result = None
            if play in valid:
                chosen[player] = play
            else:
                result = 'invalid key'
        
        if chosen[0] + chosen[1] in wins:
            result = ('win', 0) + tuple(chosen)
        elif chosen[1] + chosen[0] in wins:
            result = ('win', 1) + tuple(chosen)
        else:
            result = ('tie', None) + tuple(chosen)

We play this game by passing (player number, play) tuples to .send()

In [54]:
rps = rock_paper_scissors()
rps.send((0, 'r'))
rps.send((1, 'p'))
Out[54]:
('win', 1, 'r', 'p')
In [55]:
rps.send((1, 's'))
rps.send((1, 'p'))
rps.send((1, 'z'))
Out[55]:
'invalid key'
In [56]:
rps.send((0, 's'))
Out[56]:
('win', 0, 's', 'p')
In [57]:
rps.send((0, 'r'))
rps.send((1, 'r'))
Out[57]:
('tie', None, 'r', 'r')

Make the caller wait

It makes sense to design your generator protocols so that any waiting has to be done by the caller. This includes waiting for user input, IO completion and timers. The rock, paper scissors example above and all the examples to follow are designed this way.

The benefit of waiting in the caller is that other processing (and other generators) can be "running" at the same time without needing multiple processes or threads.

Generators with try: finally:

try: finally: blocks in normal Python code are great for managing an external resources. try: finally: blocks work just fine in generators too, you can use them to ensure a resource aquired inside a generator is properly cleaned up no matter how the generator is used. The generator could run to completion, raise an exception or simply be garbage collected after the last reference to it is removed and the finally: block will always be executed.

This generator sets the terminal attached to fd into "cbreak" mode when it is created and then restores the original terminal setting on exit. cbreak mode allows reading each key the user types as they are typed, instead of waiting for a full line of text.

Note that the first yield statement is inside the try: block, guaranteeing that the finally: block will be executed eventually. The first yield statement yields None (which is what is expected by the advance_generator_once decorator). The advance_generator_once decorator makes sure .next() is immediately called on this generator after creation, so the terminal is always set to cbreak mode after the caller calls cbreak_keys().

The finally: block in this generator is useful in normal operation and for debugging. When the program exits the terminal will be restored to normal mode. If the terminal is left in cbreak mode tracebacks shown will be sprayed across the screen in a hard-to-read manner, and the user's shell prompt won't echo input normally.

In [58]:
##
import os
import termios
import tty

@advance_generator_once
def cbreak_keys(fd):
    "enter cbreak mode and yield keys as they arrive"
    termios_settings = termios.tcgetattr(fd)
    tty.setcbreak(fd)
    try:
        yield # initialize step
        while True:
            yield os.read(fd, 1)
    finally:
        termios.tcsetattr(fd, termios.TCSADRAIN, termios_settings)

Testing this generator involves creating a "psuedo-tty" for the generator to connect to, then simulating user input on that pseudo-tty. In this test we read just 5 characters because reading any more would block.

In [59]:
import pty
import itertools

master, slave = pty.openpty()
old_settings = termios.tcgetattr(master)
os.write(slave, "hello")

c = cbreak_keys(master)
for i in range(5):
    print c.next(),
h e l l o

We still hold a reference to the generator, so our pseudo-tty is still in cbreak mode.

In [60]:
old_settings == termios.tcgetattr(master)
Out[60]:
False

We could remove the reference, or we can be more explicit by calling the generator's .close() method. The .close() method causes a GeneratorExit exception to be raised within the generator.

When the caller uses the .close() method it expects the generator to exit. If the generator yields a value instead, .close() raises a RuntimeError. Generators must exit normally or raise an exception when a GeneratorExit is raised.

In [61]:
c.close()
old_settings == termios.tcgetattr(master)
Out[61]:
True

Sockets are another type of external resource that needs to be properly managed.

When using sockets it's polite to shut down the socket so the other side knows you're done sending. It's also a very good idea to close the socket to free up the file descriptor allocated by the operating system.

This generator reads individual characters from a socket and on exit politely tries to shutdown the socket, and next ensures that the socket is closed.

In [62]:
##
import socket

@advance_generator_once
def socket_read_and_close(sock):
    "yields strings from sock and ensures sock.shutdown() is called"
    try:
        b = None
        while b != '':
            yield b
            b = sock.recv(1)
    finally:
        try:
            sock.shutdown(socket.SHUT_RDWR)
        except socket.error:
            pass
        sock.close()

Testing socket code takes quite a few lines of boilerplate. We have to find a free port, set up a server socket and then accept a client connection as another socket object.

We send some text and immediately disconnect the "client" to verify that our generator exits cleanly after reading all the data on the "server" side.

In [63]:
import socket
server = socket.socket()
server.bind(('', 0))
server.listen(0)
host, port = server.getsockname()

client = socket.socket()
client.connect(('localhost', port))
s, remote = server.accept()

client.send("world")
client.shutdown(socket.SHUT_RDWR)

for c in socket_read_and_close(s):
    print c,
w o r l d

The socket object has been closed, so if we try to wrap another generator around it we expect to get an error.

In [64]:
socket_read_and_close(s).next()
---------------------------------------------------------------------------
error                                     Traceback (most recent call last)
/home/ian/git/iterables-iterators-generators/<ipython-input-64-012fa39a25b8> in <module>()
----> 1 socket_read_and_close(s).next()

/home/ian/git/iterables-iterators-generators/<ipython-input-62-8840110348a1> in socket_read_and_close(sock)
      9         while b != '':
     10             yield b
---> 11             b = sock.recv(1)
     12     finally:
     13         try:

/usr/lib/python2.7/socket.pyc in _dummy(*args)
    168     __slots__ = []
    169     def _dummy(*args):
--> 170         raise error(EBADF, 'Bad file descriptor')
    171     # All _delegate_methods must also be initialized here.

    172     send = recv = recv_into = sendto = recvfrom = recvfrom_into = _dummy

error: [Errno 9] Bad file descriptor

State machine generators

Generators are great for representing state machines.

Telnet is a protocol for allowing untrusted, insecure connections from remote hosts. It's one option for plain terminal connections, and almost every operating system comes with a client.

For reading user input however, telnet has a bunch of control sequences that we need to filter out. Fortunately filtering out the control sequences with a little state machine is easy.

Starting in telnet normal mode all bytes except 255 are user input. A 255 byte enters command mode, which is followed by either one command byte and one parameter byte, or a 250 command byte and any number of subnegotiation bytes ending with a 240. On the transitions we mark True for user data and False for part of a control sequence.

Telnet command filter

The generator that implements this state machine isn't much longer than the diagram that describes it. The states "normal", "command", "parameter" and "subnegotiation" are represented as yield statements. The transitions are normal python flow statements while: if: and continue.

The pattern of storing the result in a local variable actual_input is used here for the "normal" state because some transitions to the normal state yield True and others yield False.

In [65]:
##
@advance_generator_once
def telnet_filter():
    """
    coroutine accepting characters and yielding True when the character
    passed is actual input or False when it is part of a telnet command.
    """
    actual_input = None
    while True:
        key = yield actual_input # normal
        if key != chr(255):
            actual_input = True
            continue
            
        key = yield False # command
        if key == chr(255):
            actual_input = True
            continue
            
        actual_input = False
        if key == chr(250):
            while key != chr(240):
                key = yield False # subnegotiation
        else:
            yield False # parameter

This generator yields True and False values for each byte sent to it. To test it we print the characters sent where the generator yielded True. This is a capture of a control sequences sent from a modern telnet client with the 6 characters "signal" mixed between the control sequences.

In [66]:
keep = telnet_filter()
chatter = ('\xff\xfd\x03si\xff\xfb"gn\xff\xfa"\x03\x01\x00\x00\x03b'
           '\x03\x04\x02\x0f\x05\x00\x00\x07b\x1c\x08\x02\x04\tB\x1a'
           '\n\x02\x7f\x0b\x02\x15\x0f\x02\x11\x10\x02\x13\x11\x02'
           '\xff\xff\x12\x02\xff\xff\xff\xf0al\xff\xfd\x01')
for c in chatter:
    if keep.send(c):
        print c,
s i g n a l

Combining generators

It's easy to combine simple generators for more advanced functionality. We can combine our socket_read_and_close() generator with some new telnet negotiation and our telnet_filter() generator to make a new "clean" character-by-character telnet input generator. This generator will yield only the user input from a telnet connection.

Be careful of when combining generators, though. If a "child" generator raises a StopIteration exception when you call its .next() method that exception will propagate normally in the "parent" generator, causing it to exit as well. This can lead to some hard to find bugs, so always think about what you want to happen when your child raises StopIteration. If you want to handle StopIteration you can catch it like any other exception, or you can use the default parameter of the next() builtin function when advancing the child generator.

In this case we do want the new telnet_keys() parent generator to stop when the socket_read_and_close() child generator does, so we let its StopIteration exception carry through.

In [67]:
##
@advance_generator_once
def telnet_keys(sock):
    "yields next key or None if key was a filtered out telnet command"
    # negotiate character-by-character, disable echo
    sock.send('\xff\xfd\x22\xff\xfb\x01')
    keep = telnet_filter()
    s = socket_read_and_close(sock)
    yield
    while True:
        # allow StopIteration to carry through:
        c = s.next()
        if keep.send(c):
            yield c
        else:
            yield None

High-level decision making with generators

Rock, paper, scissors isn't much fun when played single player in the Python read-eval-print-loop.

We should be able to play it with single keystrokes on the console. Opponents (guests) should be able to connect to play against us. Once they connect we should play a few games before we choose a winner. We need to handle a guest disconnecting before all the games have been played. Also, if the guest waits too long to make a move they should be disconnected so someone else can play. Finally, we should have reporting of how well we've done against all the guests that have connected.

For the game itself we can lay out the states and transitions. There are only really two states: "waiting" for a guest to connect and "play" while we're playing. "Moved" and "win" below are just steps in deciding whether we end up in the "play" or "waiting" state.

There are many transitions with different effects. When guest enters a play we should disable the timeout that will disconnect them. When a player has moved, play may continue because one player still needs to move or because the game was a tie. When a game ends with one player winning play will continue until a full round has been played when the guest will be disconnected.

game_machine states

This generator is responsible for providing prompts and feedback to both players, including game results. It accepts and processes input from both players and notifies players when their input is invalid. It also asks the caller to disconnect the opponent once enough games have been played by yielding 'waiting'. Finally this generator manages control of the opponent timeout by yielding 'reset timeout' when the timer should be (re)started and 'disable timeout' when the opponent has entered a valid play.

The caller is responsible for receiving input from the users, sending output to the users and informing the generator when the opponent connects, disconnects or has timed out. The disconnect and timeout conditions are somewhat exceptional so they have been implemented with the use of the generator's .throw() method.

Exceptions passed to a generator's .throw() method are raised within the generator from the current yield statement, just like how the .close() method raises GeneratorExit. Exceptions may then be handled by the generator with try: except: blocks. Here we handle the exceptions by printing a message and returning to the outer while: loop (the "waiting" state).

In [68]:
##
class Timeout(Exception):
    pass

class Disconnect(Exception):
    pass

def game_machine(game_factory, output, best_of=9):
    """
    coroutine that manages and provides comminication for two-player games,
    best of N

    :param game_factory: a function that returns a game generator object
    :param output: a function that sends output to one or both players
    :param best_of: max games to play per guest (an odd number)

    yields: 'waiting' : waiting for a guest (disconnect any existing guest)
            'play': playing a game, accepting input
            'disable timeout': disable the guest timout, accepting input
            'reset timeout': reset and start guest timeout, accepting input

    accepts to .send():
        ('join', guest_name): Guest guest_name joined
        ('key', (player_num, key)): Input from player player_num (0 or 1)

    accepts to .throw(): Disconnect: the guest disconnected
                         Timeout: the guest timout fired
    """
    ravg = running_avg()
    while True:
        event, value = yield 'waiting'
        if event != 'join':
            continue
        game = game_factory()
        wins = [0, 0]
        output("Player connected: {0}".format(value), player=0)
        output("Welcome to the game", player=1)

        try:
            response = 'reset timeout'
            while True:
                event, value = yield response
                response = 'play'
                if event != 'key':
                    continue
                    
                player, key = value
                result = game.send((player, key))
                if result == 'invalid key':
                    output("Invalid key", player=player)
                    continue
                elif player == 1:
                    response = 'disable timeout'
                if not result:
                    continue
                    
                outcome, player, play0, play1 = result
                output("Player 0: {0}, Player 1: {1}".format(play0, play1))
                if outcome == 'win':
                    wins[player] += 1
                    output("Player {0} wins!".format(player))
                    output("Wins: {0} - {1}".format(*wins))
                    output("Overall: {0:5.2f}%".format(
                        (1 - ravg.send(player)) * 100), player=0)
                    
                if any(count > best_of / 2 for count in wins):
                    output("Thank you for playing!")
                    break
                response = 'reset timeout'
                
        except Disconnect:
            output("Opponent disconnected.", player=0)

        except Timeout:
            output("Timed out. Good-bye")

To test this generator we need a simple output function with a default value for the player parameter.

In [69]:
def say(t, player='all'):
    print player, ">", t

g = game_machine(rock_paper_scissors, say)
g.next()
Out[69]:
'waiting'
In [70]:
g.send(('join', 'Ernie'))
0 > Player connected: Ernie
1 > Welcome to the game
Out[70]:
'reset timeout'
In [71]:
g.send(('key', (0, 'r')))
Out[71]:
'play'
In [72]:
g.send(('key', (1, 's')))
all > Player 0: r, Player 1: s
all > Player 0 wins!
all > Wins: 1 - 0
0 > Overall: 100.00%
Out[72]:
'reset timeout'
In [73]:
g.throw(Disconnect())
0 > Opponent disconnected.
Out[73]:
'waiting'
In [74]:
g.send(('join', 'Bert'))
0 > Player connected: Bert
1 > Welcome to the game
Out[74]:
'reset timeout'
In [75]:
g.send(('key', (1, 'x')))
1 > Invalid key
Out[75]:
'play'
In [76]:
g.send(('key', (1, 'p')))
Out[76]:
'disable timeout'
In [77]:
g.send(('key', (0, 'r')))
all > Player 0: r, Player 1: p
all > Player 1 wins!
all > Wins: 0 - 1
0 > Overall: 50.00%
Out[77]:
'reset timeout'
In [78]:
for player, key in [(0, 's'), (1, 'p')] * 5:
    r = g.send(('key', (player, key)))
r
all > Player 0: s, Player 1: p
all > Player 0 wins!
all > Wins: 1 - 1
0 > Overall: 66.67%
all > Player 0: s, Player 1: p
all > Player 0 wins!
all > Wins: 2 - 1
0 > Overall: 75.00%
all > Player 0: s, Player 1: p
all > Player 0 wins!
all > Wins: 3 - 1
0 > Overall: 80.00%
all > Player 0: s, Player 1: p
all > Player 0 wins!
all > Wins: 4 - 1
0 > Overall: 83.33%
all > Player 0: s, Player 1: p
all > Player 0 wins!
all > Wins: 5 - 1
0 > Overall: 85.71%
all > Thank you for playing!
Out[78]:
'waiting'

Driving an event loop with a generator

Now we need to pull all the peices together in a way that a select.select() loop can run the whole thing.

This generator accepts input on the console for player 0 with cbreak_keys(), and listens on a TCP port for player 1 (the guest) to connect. When player 1 connects it accepts input on that socket as a telnet connection with telnet_keys(). Input from both players is forwarded to game_machine(). When game_machine() asks for the timer to be reset this generator creates a countdown_generator() that will be used to give player 1 a countdown as their time is running out.

The caller is expected to be running select.select() in a loop. select.select() expects a list of file descriptors that might have data waiting and optionally a timeout value. The file descriptors passed will either be the console and server socket when player 1 is not connected, or the console and the client socket when player 1 is connected. The timeout will be set if there is a countdown in progress. select.select() yields a list of the file descriptors that are readable, or an empty list if the timeout was reached.

In [79]:
##
import socket
import sys
import time

def console_telnet_game_loop(game_factory, countdown_factory, best_of=9,
                             stdin=None, port=12333, now=None):
    """
    Coroutine that manages IO from console and incoming telnet connections
    (one client at a time), and tracks a timeout for the telnet clients.
    Console and telnet client act as player 0 and 1 of a game_machine.

    :param game_factory: passed to game_machine()
    :param coutdown_factory: function returning a countdown generator
    :param best_of: passed to game_machine()
    :param stdin: file object to use for player 0, default: sys.stdin
    :param port: telnet port to listen on for player 1
    :param now: function to use to get the current time in seconds,
                default: time.time

    yields args for select.select(*args)

    accepts to .send() the fd lists returned from select.select()
    """
    if stdin is None:
        stdin = sys.stdin
    if now is None:
        now = time.time
        
    server = socket.socket()
    server.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    server.bind(('', port))
    server.listen(0)
    print "Listening for telnet connections on port", port
    
    client = None
    client_reader = None
    timeout = None
    countdown = None
    local_fd = stdin.fileno()
    local_user = cbreak_keys(local_fd)
    
    def output(txt, player='all'):
        if player != 1:
            print txt
        if player != 0 and client:
            client.send(txt + '\r\n')

    g = game_machine(game_factory, output, best_of)
    state = g.next()
    
    while True:
        if state == 'waiting' and client:
            client = client_reader = timeout = None
        if state == 'reset timeout':
            countdown = countdown_factory(lambda n: output(str(n), player=1))
            timeout = time.time() + countdown.next()
            state = 'play'
        if state == 'disable timeout':
            countdown = timeout = None
        
        telnet_fd = client.fileno() if client else server.fileno()
        timeout_seconds = max(0, timeout - now()) if timeout else None
        
        readable, _, _ = yield [local_fd, telnet_fd], [], [], timeout_seconds
        
        if not readable: # no files to read == timeout, advance countdown
            try:
                timeout = now() + countdown.next()
            except StopIteration:
                state = g.throw(Timeout())
                timeout = None
            continue
        if local_fd in readable: # local user input
            state = g.send(('key', (0, local_user.next())))
            readable.remove(local_fd)
            continue
        if client: # client input
            try:
                key = client_reader.next()
            except StopIteration:
                state = g.throw(Disconnect())
            else:
                if key: # might be None if telnet commands were filtered
                    state = g.send(('key', (1, key)))
            continue
        # accept a new client connection
        client, addr = server.accept()
        client_reader = telnet_keys(client)
        client_reader.next()
        state = g.send(('join', str(addr)))

The big picture

Overview diagram

The last peice we need is a main() funtion to drive our generators. All the waiting for IO and timers is done here, controlled from the generators above.

This design lets us easily switch to different event loop or async library. We could also run many of these games or many different tasks on the same event loop.

In [ ]:
##
import select

def main():
    loop = console_telnet_game_loop(rock_paper_scissors, countdown_generator)
    fd_lists = None
    while True:
        select_args = loop.send(fd_lists)
        fd_lists = select.select(*select_args)

if __name__ == "__main__":
    main()

We end up with about 300 lines of code, including docstrings and more than 90% of that code is generators.

You may download it from https://raw.github.com/wardi/iterables-iterators-generators/master/rps_server.py

This code is a complete interactive game server. It supports character-by-character input with one player on the console and one connected by telnet. It detects players disconnecting and has a timer and countdown for disconnecting idle players. It also collects and reports game statistics.

This code contains no classes other than the simple Timeout and Disconnect exceptions. Message passing is accomplished with tuples, strings and integers.

All of the code is easy to test. The limited nature of the generator interface encourages us to break up code into small, simple, testable parts.

This code is 100% asynchronous with no threads, callback chains, queues, locking or monkey patching required.

Summary

Iterables

  • may create an iterator with iter(x)

    • implement .__getitem__(), which raises IndexError after the last element
    • or implement .__iter__()

Iterators

  • are iterables, where iter(x) typically returns x
  • maintain some kind of "position" state
  • implement .next(), which raises StopIteration after the last element

Generators

  • are iterators
  • come with .next(), .send(value), .close() and .throw(exception) methods for free!
  • "position" state includes local variables and program counter
  • PEP 380: delegation with "yield from" available in Python 3.3+
  • CAUTION: StopIteration exceptions will cause trouble: consider next(x, default) builtin

See also