Python Enhancement Proposals

Python »
PEP Index »
PEP 334

PEP 334 – Simple Coroutines via SuspendIteration

Author:: Clark C. Evans <cce at clarkevans.com>
Status:

Abstract

Asynchronous application frameworks such as Twisted[1] and Peak[2], are based on a cooperative multitasking via event queues ordeferred execution. While this approach to application developmentdoes not involve threads and thus avoids a whole class of problems[3], it creates a different sort of programming challenge. When anI/O operation would block, a user request must suspend so that otherrequests can proceed. The concept of a coroutine[4] promises tohelp the application developer grapple with this state managementdifficulty.

This PEP proposes a limited approach to coroutines based on anextension to theiterator protocol. Currently, an iterator mayraise a StopIteration exception to indicate that it is done producingvalues. This proposal adds another exception to this protocol,SuspendIteration, which indicates that the given iterator may havemore values to produce, but is unable to do so at this time.

Rationale

There are two current approaches to bringing co-routines to Python.Christian Tismer’s Stackless[6] involves a ground-up restructuringof Python’s execution model by hacking the ‘C’ stack. While thisapproach works, its operation is hard to describe and keep portable. Arelated approach is to compile Python code to Parrot[7], aregister-based virtual machine, which has coroutines. Unfortunately,neither of these solutions is portable with IronPython (CLR) or Jython(JavaVM).

It is thought that a more limited approach, based on iterators, couldprovide a coroutine facility to application programmers and still beportable across runtimes.

Iterators keep their state in local variables that are not on the“C” stack. Iterators can be viewed as classes, with state stored inmember variables that are persistent across calls to its next()method.
While an uncaught exception may terminate a function’s execution, anuncaught exception need not invalidate an iterator. The proposedexception, SuspendIteration, uses this feature. In other words,just because one call to next() results in an exception does notnecessarily need to imply that the iterator itself is no longercapable of producing values.

There are four places where this new exception impacts:

ThePEP 255 simple generator mechanism could be extended to safely‘catch’ this SuspendIteration exception, stuff away its currentstate, and pass the exception on to the caller.
Various iterator filters[9] in the standard library, such asitertools.izip should be made aware of this exception so that it cantransparently propagate SuspendIteration.
Iterators generated from I/O operations, such as a file or socketreader, could be modified to have a non-blocking variety. Thisoption would raise a subclass of SuspendIteration if the requestedoperation would block.
The asyncore library could be updated to provide a basic ‘runner’that pulls from an iterator; if the SuspendIteration exception iscaught, then it moves on to the next iterator in its runlist[10].External frameworks like Twisted would provide alternativeimplementations, perhaps based on FreeBSD’s kqueue or Linux’s epoll.

While these may seem dramatic changes, it is a very small amount ofwork compared with the utility provided by continuations.

Semantics

This section will explain, at a high level, how the introduction ofthis new SuspendIteration exception would behave.

Simple Iterators

The current functionality of iterators is best seen with a simpleexample which produces two values ‘one’ and ‘two’.

classStates:def__iter__(self):self._next=self.state_onereturnselfdefnext(self):returnself._next()defstate_one(self):self._next=self.state_tworeturn"one"defstate_two(self):self._next=self.state_stopreturn"two"defstate_stop(self):raiseStopIterationprintlist(States())

An equivalent iteration could, of course, be created by thefollowing generator:

defStates():yield'one'yield'two'printlist(States())

Introducing SuspendIteration

Suppose that between producing ‘one’ and ‘two’, the generator abovecould block on a socket read. In this case, we would want to raiseSuspendIteration to signal that the iterator is not done producing,but is unable to provide a value at the current moment.

fromrandomimportrandintfromtimeimportsleepclassSuspendIteration(Exception):passclassNonBlockingResource:"""Randomly unable to produce the second value"""def__iter__(self):self._next=self.state_onereturnselfdefnext(self):returnself._next()defstate_one(self):self._next=self.state_suspendreturn"one"defstate_suspend(self):rand=randint(1,10)if2==rand:self._next=self.state_tworeturnself.state_two()raiseSuspendIteration()defstate_two(self):self._next=self.state_stopreturn"two"defstate_stop(self):raiseStopIterationdefsleeplist(iterator,timeout=.1):"""    Do other things (e.g. sleep) while resource is    unable to provide the next value    """it=iter(iterator)retval=[]whileTrue:try:retval.append(it.next())exceptSuspendIteration:sleep(timeout)continueexceptStopIteration:breakreturnretvalprintsleeplist(NonBlockingResource())

In a real-world situation, the NonBlockingResource would be a fileiterator, socket handle, or other I/O based producer. The sleeplistwould instead be an async reactor, such as those found in asyncore orTwisted. The non-blocking resource could, of course, be written as agenerator:

defNonBlockingResource():yield"one"whileTrue:rand=randint(1,10)if2==rand:breakraiseSuspendIteration()yield"two"

It is not necessary to add a keyword, ‘suspend’, since most realcontent generators will not be in application code, they will be inlow-level I/O based operations. Since most programmers need not beexposed to the SuspendIteration() mechanism, a keyword is not needed.

Application Iterators

The previous example is rather contrived, a more ‘real-world’ examplewould be a web page generator which yields HTML content, and pullsfrom a database. Note that this is an example of neither the‘producer’ nor the ‘consumer’, but rather of a filter.

defListAlbums(cursor):cursor.execute("SELECT title, artist FROM album")yield'<html><body><table><tr><td>Title</td><td>Artist</td></tr>'for(title,artist)incursor:yield'<tr><td>%s</td><td>%s</td></tr>'%(title,artist)yield'</table></body></html>'

The problem, of course, is that the database may block for some timebefore any rows are returned, and that during execution, rows may bereturned in blocks of 10 or 100 at a time. Ideally, if the databaseblocks for the next set of rows, another user connection could beserviced. Note the complete absence of SuspendIterator in the abovecode. If done correctly, application developers would be able tofocus on functionality rather than concurrency issues.

The iterator created by the above generator should do the magicnecessary to maintain state, yet pass the exception through to alower-level async framework. Here is an example of what thecorresponding iterator would look like if coded up as a class:

classListAlbums:def__init__(self,cursor):self.cursor=cursordef__iter__(self):self.cursor.execute("SELECT title, artist FROM album")self._iter=iter(self._cursor)self._next=self.state_headreturnselfdefnext(self):returnself._next()defstate_head(self):self._next=self.state_cursorreturn"<html><body><table><tr><td>\                Title</td><td>Artist</td></tr>"defstate_tail(self):self._next=self.state_stopreturn"</table></body></html>"defstate_cursor(self):try:(title,artist)=self._iter.next()return'<tr><td>%s</td><td>%s</td></tr>'%(title,artist)exceptStopIteration:self._next=self.state_tailreturnself.next()exceptSuspendIteration:# just pass-throughraisedefstate_stop(self):raiseStopIteration

Complicating Factors

While the above example is straightforward, things are a bit morecomplicated if the intermediate generator ‘condenses’ values, that is,it pulls in two or more values for each value it produces. Forexample,

defpair(iterLeft,iterRight):rhs=iter(iterRight)lhs=iter(iterLeft)whileTrue:yield(rhs.next(),lhs.next())

In this case, the corresponding iterator behavior has to be a bit moresubtle to handle the case of either the right or left iterator raisingSuspendIteration. It seems to be a matter of decomposing thegenerator to recognize intermediate states where a SuspendIteratorexception from the producing context could happen.

classpair:def__init__(self,iterLeft,iterRight):self.iterLeft=iterLeftself.iterRight=iterRightdef__iter__(self):self.rhs=iter(iterRight)self.lhs=iter(iterLeft)self._temp_rhs=Noneself._temp_lhs=Noneself._next=self.state_rhsreturnselfdefnext(self):returnself._next()defstate_rhs(self):self._temp_rhs=self.rhs.next()self._next=self.state_lhsreturnself.next()defstate_lhs(self):self._temp_lhs=self.lhs.next()self._next=self.state_pairreturnself.next()defstate_pair(self):self._next=self.state_rhsreturn(self._temp_rhs,self._temp_lhs)

This proposal assumes that a corresponding iterator written usingthis class-based method is possible for existing generators. Thechallenge seems to be the identification of distinct states withinthe generator where suspension could occur.

Resource Cleanup

The current generator mechanism has a strange interaction withexceptions where a ‘yield’ statement is not allowed within atry/finally block. The SuspendIterator exception provides anothersimilar issue. The impacts of this issue are not clear. However itmay be that re-writing the generator into a state machine, as theprevious section did, could resolve this issue allowing for thesituation to be no-worse than, and perhaps even removing theyield/finally situation. More investigation is needed in this area.

API and Limitations

This proposal only covers ‘suspending’ a chain of iterators, and doesnot cover (of course) suspending general functions, methods, or “C”extension function. While there could be no direct support forcreating generators in “C” code, native “C” iterators which complywith the SuspendIterator semantics are certainly possible.