On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions

## 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.

 Published under the terms of the Open Publication License Design by Interspire