Subroutines and Coroutines
In the section called “Generator Semantics” we noted that a
for
statement and the associated generator are peers.
Technically, two functions with this peer relationship are called
coroutines. This is in contrast to ordinary functions, where one is
subordinate to the other; when a function is evaludatated, it is a
subroutine.
The function evaluation we've been using since Chapter 9, Functions
shows the standard subroutine relationship. The
function's evaluation is entirely subordinate to the statement that
evaluated the function. Consider the following snippet of code
for i in range(10):
print math.sqrt( float( i ) )
We have a
print
statement which evaluates the
math.sqrt
function. The evaluation of the
math.sqrt
function is entirely subordinate to the
statement. Each evaluation is math.sqrt
is
distinct, with no memory of any previous evaluation of the function. We
sometimes describe functions like this as
idempotent: we get the same result every time
because there's no memory or history.
A generator, however, can define a different kind of relationship
called coroutine instead of subroutine. Evaluation of a couroutine is
not subordinate to the statement, but a peer with the statement. We can
use this to create functions with "memory." Couroutines are functions
which have an internal state.
To define a stateful coroutine, we will use the more general form
of the
yield
statement and we'll use
send
instead of next
.
The
yield
statement we looked at in the section called “Defining a Generator” was triggered by a
for
statement calling the generator's next
method.
Each time the
for
statement evaluated the
next
method, the generator resumed execution at
the
yield
statement. The value provided by the
yield
statement was the value returned by the
next
function. The relationship is assymetric
becuase the generator provides values with no interaction or
control.
It turns out that the
yield
statement is really
a special kind of operator. The
yield
operator yields
a value that will be made available through the
next
or send
function.
Additionally, the send
function can provide a
value which is returned by the
yield
operator. There
are two simultaneous data transfers: the
yield
value
is the result returned by the send
function;
the values provided by the send
function and
the results returned by the
yield
operator.
Example 18.2. coroutine.py
def search(aList,key):
probeG= probe(len(aList))
try:
index= probeG.next()
while aList[index] != key:
print "search for", key, ":", index
index= probeG.send( cmp(aList[index],key) )
probeG.close()
return index
except StopIteration:
return 1
def probe( size ):
lo, hi = 0, size
oldMid, mid = 0, (lo+hi)//2
while oldMid != mid:
compare= (yield mid)
if compare < 0: lo= mid
else: hi= mid
oldMid, mid = mid, (lo+hi)//2

The search function examines a sorted list to locate the
entry with a given key.


We initiate the generator, probe ,
providing the overall size of the list. We save the return value
in probeG . The return value from an initial
call to a generator function is an internal generator object
which has a number of methods (next, send, close and throw.)
When we use simple generators in a
for
statement, this happens silently and automatically.


We evaluate probeG 's
next method, which yields the first
value from the generator. This is a position in the list that
we'll probe to see if the requested key is at that
position.


If we didn't find the requested key, we send the
comparison result to the generator via the generator's
send method. This will cause the
generator to yield a new probe value. The probe function's
yield
operator will receive either 1 or +1
from this send method.


We handle the StopIteration
exception; this may be raised if our probe
function has run out of values to yield to search.


The probe function contains a
yield
operation, so it is a generator. It is
initialized with the size of a list that will be searched. The
variables lo and hi define
a subset of the list which is being probed. Initially, it's the
whole list. Values sent in from the coroutine,
search , will define which half of the list
will be considered as the new subset list.


We yield the previously computed middle of the list. The
result of the
yield
operator will be the
comparison result. A negative number means that the probed value
was too low, and we need to examine the upper half of the
subset. A positive number means we should examine the lower half
of the subset. A new middle position is computed; this will be
yielded next time the coroutine makes a request.

Linear Search and Binary Search. Note that we've partitioned the algorithm into two elements: the
key comparison portion (in searc), and the sequence of probe values.
We've provided a binary search version of probe. We can also provide a
linear search version of probe. With a few name changes we can create
a search function which works with a sorted list or an unsorted
list.
The probe function can be renamed to either "sorted", because
that's the kind of data it requires, or "binary" because that's the
algorithm it embodies.
The following function can be called "unsorted" or "linear",
depending on your preference for describing the data it works with or
the algorithm.
def unsorted( size ):
for pos in range(size):
compare= (yield pos)
if compare == 1: break # went too far
We prefer "sorted" and "unsorted" as the coroutine names. We can
define a version of search that we woukld use as follows:
search( sorted, someList, akey )
search( unsorted, someOtherList, aKey )
This relies on providing one of the two probe functions to the
search function.