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.