Follow Techotopia on Twitter

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

How To Guides
Virtualization
General System Admin
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
1

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

2

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.

3

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.

4

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.

5

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

6

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.

7

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