Lab 13: Coroutines
Due at 11:59pm on 08/04/2016.
Starter Files
Download lab13.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
Submission
By the end of this lab, you should have submitted the lab with
python3 ok --submit
. You may submit more than once before the
deadline; only the final submission will be graded.
- Questions 1, 2, and 3 must be completed in order to receive credit for this lab. Starter code for Question 3 is in lab13.py.
- Questions 4 through 10 are optional. It is recommended that you complete these problems on your own time. Starter code for these questions is in lab13_extra.py
Helpful Hints
OK has a new feature for the "What would Python display?" questions. As you go through the question's prompts OK may give you a hint based on your wrong answers. Our hope is these hints will help remind you of something important or push you in the right direction to getting the correct answer. For example:
Foo > Suite 1 > Case 1
(cases remaining: 1)
What would Python display? If you get stuck, try it out in the Python
interpreter!
>>> not False or False
? False
-- Helpful Hint --
What about the | not |?
------------------
-- Not quite. Try again! --
?
Topics
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
Generators
A generator function returns a special type of iterator called a
generator object. Generator functions have yield
statements within the
body of the function. Calling a generator function makes it return a generator
object rather than executing the body of the function.
The reason we say a generator object is a special type of iterator is that it has all the properties of an iterator, meaning that:
- Calling the
__iter__
method makes a generator object return itself without modifying its current state. - Calling the
__next__
method makes a generator object compute and return the next object in its sequence. If the sequence is exhausted,StopIteration
is raised. - Typically, a generator should not restart unless it's defined that way. But
calling the generator function returns a brand new generator object (like
calling
__iter__
on an iterable object).
However, they do have some fundamental differences:
- An iterator is a class with
__next__
and__iter__
explicitly defined, but a generator can be written as a mere function with ayield
in it. __next__
in an iterator usesreturn
, but a generator usesyield
.A generator "remembers" its state for the next
__next__
call. Therefore,the first
__next__
call works like this:- Enter the function, run until the line with
yield
. - Return the value in the
yield
statement, but remember the state of the function for future__next__
calls.
- Enter the function, run until the line with
And subsequent
__next__
calls work like this:- Re-enter the function, start at the line after
yield
, and run until the nextyield
statement. - Return the value in the
yield
statement, but remember the state of the function for future__next__
calls.
- Re-enter the function, start at the line after
When a generator runs to the end of the function, it raises StopIteration
.
Coroutines
Coroutines are generator objects that both produce and consume values. Values
are consumed by using the yield
expression, which is like the yield
statement except it is on the right hand side of an assignment statement.
Coroutines naturally enforce modularity in our code by splitting up complex
functionality into smaller parts that are easier to write, maintain, and
understand. They are also useful for the paradigm of event-driven programming,
where an event loop handles particular events, such as user input, and uses
callback functions to process those events.
Coroutines can be controlled by using the send
and close
methods.
send
resumes the coroutine and passes a value to it. Therefore, calling__next__
is equivalent to callingsend
withNone
.close
stops the coroutine and raises aGeneratorExit
exception within the coroutine. However, this exception is not propagated out of the coroutine. If we try to usesend
or__next__
on a coroutine that has been closed, aStopIteration
is raised.
An example of a coroutine is below:
def routine():
count = 0
while count < 2:
print("What color is the sky?")
ans = (yield)
if ans == "blue":
count += 1
print("Correct!")
else:
print("Try again!")
>>> r = routine()
>>> next(r)
What color is the sky?
>>> r.send("black")
Try again!
What color is the sky?
>>> r.send("blue")
Correct!
What color is the sky?
>>> next(r)
Try again!
What color is the sky?
>>> r.send("blue")
Correct!
StopIteration
One application of coroutines occurs in sequence processing. When working with data streams, a common technique is to set up a pipeline, where each stage of the pipeline is a coroutine. Data coming through the stream is sent through this pipeline to produce the final result.
- Functions at the beginning of the pipeline only send values (and thus are not coroutines) and are called producers.
- Coroutines in the middle of the pipeline both send and receive values and are called filters.
- Coroutines at the end of the pipeline only receive values and are called consumers.
Required Questions
What Would Python Display?
Question 1: WWPD: Generators
Use OK to test your knowledge with the following What would Python Display questions:
python3 ok -q generators -u
def generator():
print("Starting here")
i = 0
while i < 6:
print("Before yield")
yield i
print("After yield")
i += 1
>>> g = generator()
>>> g # what type of object is this?
______<generator object>
>>> g == iter(g) # equivalent of g.__iter__()
______True
>>> next(g) # equivalent of g.__next__()
______Starting here
Before yield
0
>>> next(g)
______After yield
Before yield
1
>>> next(g)
______After yield
Before yield
2
def generator():
print("Starting")
i = 2
while i < 6:
print("foo", i)
yield i
i += 1
print("bar")
yield i*2
i += 2
>>> h = generator()
>>> iter(h) == h
______True
>>> next(h)
______Starting
foo 2
2
>>> next(h)
______bar
6
>>> next(h)
______foo 5
5
Trace through the code and make sure you know where and why each statement is printed.
You might remember from when we studied iterators that iterator classes that
don't define a __next__
method cannot run in a for
loop. However, with
generators we can get around this.
class IterGen:
def __init__(self):
self.start = 5
def __iter__(self):
while self.start < 10:
self.start += 1
yield self.start
for i in IterGen():
print(i)
Why does this iterable work without defining a __next__
method?
The for
loop only expects the object returned by __iter__
to have a
__next__
method. The __iter__
method is a generator function because of the
yield
statement in the body. Therefore, when __iter__
is called, it returns
a generator object, which you can call __next__
on.
Question 2: WWPD: Coroutines
Use OK to test your knowledge with the following What would Python Display questions:
python3 ok -q coroutines -u
def search(pattern):
print("Looking for", pattern)
while True:
line = (yield)
if pattern in line:
print(line)
else:
print("Nope!")
>>> s = search('cs61a') # what type of object is this?
>>> next(s)
______Looking for cs61a
>>> s.send('cs61b is the best class!')
______Nope!
>>> s.send('I love cs61a')
______I love cs61a
>>> s.close()
>>> s.send('cs61a rocks.') # what is raised if the coroutine has been closed?
______StopIteration
def truthy():
print("Starting...")
num_truths = 0
while num_truths < 3:
print("Give me a truth!")
truth = (yield)
if truth:
num_truths += 1
print("Nice truth.")
else:
print("Liar!")
>>> t = truthy()
>>> next(t)
______Starting...
Give me a truth!
>>> t.send(True)
______Nice truth.
Give me a truth!
>>> t.send([])
______Liar!
Give me a truth!
>>> t.send(4)
______Nice truth.
Give me a truth!
>>> next(t)
______Liar!
Give me a truth!
>>> t.send([1, 2, 3]) # we break out of the loop
______Nice truth.
StopIteration
Trace through the code and make sure you know where and why each statement is printed.
Coding Practice
Question 3: Hailstone
Write a generator that outputs the hailstone sequence from homework 1.
Here's a quick reminder of how the hailstone sequence is defined:
- Pick a positive integer
n
as the start. - If
n
is even, divide it by 2. - If
n
is odd, multiply it by 3 and add 1. - Continue this process until
n
is 1.
def hailstone(n):
"""
>>> for num in hailstone(10):
... print(num)
...
10
5
16
8
4
2
1
"""
"*** YOUR CODE HERE ***"
i = n
while i > 1:
yield i
if i % 2 == 0:
i //= 2
else:
i = i * 3 + 1
yield i
Use OK to test your code:
python3 ok -q hailstone
Optional Questions
Generators
Question 4: Countdown
Write both a generator function and an iterator that counts down to 0.
def countdown(n):
"""
>>> for number in countdown(5):
... print(number)
...
5
4
3
2
1
0
"""
"*** YOUR CODE HERE ***"
while n >= 0:
yield n
n = n - 1
Use OK to test your code:
python3 ok -q countdown
class Countdown:
"""
>>> for number in Countdown(5):
... print(number)
...
5
4
3
2
1
0
"""
def __init__(self, cur):
self.cur = cur
def __iter__(self):
"*** YOUR CODE HERE ***"
while self.cur >= 0:
yield self.cur
self.cur -= 1
Is it possible to not have a __next__
method in the Countdown
class?
Use OK to test your code:
python3 ok -q Countdown
Question 5: Scale
Implement the generator function scale(s, k)
, which yields elements of the
given iterable s
, scaled by k
.
def scale(s, k):
"""Yield elements of the iterable s scaled by a number k.
>>> s = scale([1, 5, 2], 5)
>>> type(s)
<class 'generator'>
>>> list(s)
[5, 25, 10]
>>> m = scale(naturals(), 2)
>>> [next(m) for _ in range(5)]
[2, 4, 6, 8, 10]
"""
"*** YOUR CODE HERE ***"
for elem in s:
yield elem * k
Use OK to test your code:
python3 ok -q scale
Question 6: Merge
Implement merge(s0, s1)
, which takes two iterables s0
and s1
whose
elements are ordered. merge
yields elements from s0
and s1
in sorted
order, eliminating repetition. You may assume s0
and s1
themselves do not
contain repeats. You may also assume s0
and s1
represent infinite
sequences; that is, their iterators never raise StopIteration
.
See the doctests for example behavior.
def merge(s0, s1):
"""Yield the elements of strictly increasing iterables s0 and s1, removing
repeats. Assume that s0 and s1 have no repeats. You can also assume that s0
and s1 represent infinite sequences.
>>> twos = scale(naturals(), 2)
>>> threes = scale(naturals(), 3)
>>> m = merge(twos, threes)
>>> type(m)
<class 'generator'>
>>> [next(m) for _ in range(10)]
[2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
"""
i0, i1 = iter(s0), iter(s1)
e0, e1 = next(i0), next(i1)
"*** YOUR CODE HERE ***"
while True:
yield min(e0, e1)
if e0 < e1:
e0 = next(i0)
elif e1 < e0:
e1 = next(i1)
else:
e0, e1 = next(i0), next(i1)
Use OK to test your code:
python3 ok -q merge
Question 7: Pairs (generator)
Write a generator function pairs
that takes a list and yields all the
possible pairs of elements from that list.
def pairs(lst):
"""
>>> type(pairs([3, 4, 5]))
<class 'generator'>
>>> for x, y in pairs([3, 4, 5]):
... print(x, y)
...
3 3
3 4
3 5
4 3
4 4
4 5
5 3
5 4
5 5
"""
"*** YOUR CODE HERE ***"
for i in lst:
for j in lst:
yield i, j
Use OK to test your code:
python3 ok -q pairs
Question 8: Pairs (iterator)
Now write an iterator that does the same thing. You are only allowed to use a linear amount of space - so computing a list of all of the possible pairs is not a valid answer. Notice how much harder it is - this is why generators are useful.
class PairsIterator:
"""
>>> for x, y in PairsIterator([3, 4, 5]):
... print(x, y)
...
3 3
3 4
3 5
4 3
4 4
4 5
5 3
5 4
5 5
"""
def __init__(self, lst):
"*** YOUR CODE HERE ***"
self.lst = lst
self.i = 0
self.j = 0
def __next__(self):
"*** YOUR CODE HERE ***"
if self.i == len(self.lst):
raise StopIteration
result = (self.lst[self.i], self.lst[self.j])
if self.j == len(self.lst) - 1:
self.i += 1
self.j = 0
else:
self.j += 1
return result
def __iter__(self):
"*** YOUR CODE HERE ***"
return self
Use OK to test your code:
python3 ok -q PairsIterator
Question 9: Remainder Generator
- This question is a repeat from Lab 13.
Like functions,
generators can also be higher-order. For this
problem, we will be writing remainders_generator
, which yields a
series of generator objects.
remainders_generator
takes in an integer m
, and yields m
different
generators. The first generator is a generator of multiples of m
, i.e. numbers
where the remainder is 0. The second, a generator of natural numbers with
remainder 1 when divided by m
. The last generator yield natural numbers with
remainder m - 1
when divided by m
.
def remainders_generator(m):
"""
Takes in an integer m, and yields m different remainder groups
of m.
>>> remainders_mod_four = remainders_generator(4)
>>> for rem_group in remainders_mod_four:
... for _ in range(3):
... print(next(rem_group))
0
4
8
1
5
9
2
6
10
3
7
11
"""
"*** YOUR CODE HERE ***"
def remainder_group(rem):
start = rem
while True:
yield start
start += m
for rem in range(m):
yield remainder_group(rem)
Note that if you have implemented this correctly, each of the
generators yielded by remainder_generator
will be infinite - you
can keep calling next
on them forever without running into a
StopIteration
exception.
Hint: Consider defining an inner generator function. What arguments should it take in? Where should you call it?
Use OK to test your code:
python3 ok -q remainders_generator
Coroutines
Question 10: Restaurant (coroutines)
One common use of coroutines is to build multi-stage pipelines that pass data items between modular components. In this question, we will write a pipeline to model a restaurant and its customers.
There are three stages to the restaurant pipeline. Suppliers source ingredients and send them to Chefs. Chefs receive ingredients and assemble them into the dishes requested by their customers. Customers receive dishes and eat them!
We've implemented suppliers and customers for you already—let's take a look at
their code. supplier
takes a list of ingredients and a chef
coroutine to
supply, passes the ingredients one by one to the chef, and then closes the chef
coroutine. It handles the StopIteration
exception, which occurs if the chef
exits early:
def supplier(ingredients, chef):
for ingredient in ingredients:
try:
chef.send(ingredient)
except StopIteration as e:
print(e)
break
chef.close()
The customer
coroutine takes no arguments. It waits to be sent a dish, then
prints a message and enjoys the food! If the coroutine is closed before the
customer has eaten, it prints a complaint:
def customer():
served = False
while True:
try:
dish = yield
print('Yum! Customer got a {}!'.format(dish))
served = True
except GeneratorExit:
if not served:
print('Customer never got served.')
raise
Your job is to implement chef
. Chef takes two arguments, a dictionary mapping
customer
coroutines to dish names, and a dictionary mapping dish names to
ingredient lists. The chef
coroutine should:
- Receive ingredients from its supplier, using a
yield
expression. After receiving each ingredient, check to see if enough ingredients have been received to serve a customer:
- A customer may be served if all of the ingredients in their desired dish have been received.
- Ingredients never run out, so the same ingredient can be used to serve multiple customers.
- Customers should be served only once.
- If the chef coroutine is closed, it should print
'Chef went home.'
before exiting. - If the chef coroutine receives ingredients after all customers have been
served, it should raise
StopIteration('No one left to serve!')
to indicate that its work is complete.
def chef(customers, dishes):
"""
>>> cust = customer()
>>> next(cust)
>>> c = chef({cust: 'hotdog'}, {'hotdog': ['bun', 'hotdog']})
>>> next(c)
>>> supplier(['bun', 'hotdog'], c)
Yum! Customer got a hotdog!
Chef went home.
>>> cust = customer()
>>> next(cust)
>>> c = chef({cust: 'hotdog'}, {'hotdog': ['bun', 'hotdog']})
>>> next(c)
>>> supplier(['bun'], c)
Chef went home.
Customer never got served.
>>> cust = customer()
>>> next(cust)
>>> c = chef({cust: 'hotdog'}, {'hotdog': ['bun', 'hotdog']})
>>> next(c)
>>> supplier(['bun', 'hotdog', 'mustard'], c)
Yum! Customer got a hotdog!
No one left to serve!
"""
"*** YOUR CODE HERE ***"
remaining_customers = dict(customers)
ingredients = set()
while True:
try:
ingredient = yield
except GeneratorExit:
print('Chef went home.')
for customer in customers:
customer.close()
raise
ingredients.add(ingredient)
if not remaining_customers:
raise StopIteration('No one left to serve!')
for customer, dish_name in dict(remaining_customers).items():
if not set(dishes[dish_name]) - ingredients:
customer.send(dish_name)
del remaining_customers[customer]
Use OK to test your code:
python3 ok -q chef