[Python-Dev] coroutines and microthreads

[Guido van Rossum]

(I would cc this to the Stackless list as well, except that starship
mail is still down it seems.  I *am* posting to the python-coro list,
which seems to be appropriate here.  Will Ware, are you listening?)

Coroutines!
-----------

Inspired by Gordon McMillan's Stackless tutorial
(http://www.mcmillan-inc.com/stackless.html), I've been thinking more
about a coroutine API for Python.

I proposed one before (see the thread "uthread strawman" in
python-dev).  I've been thinking a bit more and am now revising my
proposal a bit.

I'll first give an example.  Tim Peters gave a standard example to
return the fringe of a list (checked in as Demo/threads/fcmp.py).

Using my proposed API this example could be rewritten a bit
cleaner, as follows:

    from coro import coroutine, suspend, EarlyExit  # Provisional module name

    def fringe(L):
	for x in L:
	    if type(x) is type(L):
		fringe(x)
	    else:
		suspend(x)

    def printinorder(L):
	c = coroutine(f, L)
	try:
	    while 1:
		print c(),
	except EarlyExit:
	    pass
	print

    x = [0, 1, [2, [3]], [4,5], [[[6]]]]
    printinorder(x) # prints "0 1 2 3 4 5 6"

This is about as simple as it gets.  It supports both generators (like
the example here) and coroutines (like Tim's Demo/threads/squasher.py
example).

Besides the APIs shown here (coroutine(), suspend(), and EarlyExit) I
propose a function current() which returns the current coroutine
object.  There should also be a way to kill a coroutine (or at least
to send an exception).  When a coroutine falls through at its end,
*some* other coroutine needs to be resumed.  

I believe this can be implemented with a much simplified stackless
approach, that doesn't cater towards continuations (but still borrows
a lot of wisdom from Christian's Stackless).  It can also be
implemented using threads, which should give some hope for getting the
same API supported in JPython, making it more attractive.  I am hoping
to create an implementation on top of Stackless, just to experiment
with the idiom.

Microthreads?
-------------

I'm much less clear about microthreads (uthreads).  Last time, I
thought this was a fancy name for coroutines.  It isn't!  Microthreads
are "almost real" threads, with round-robin scheduling.  What makes
them attractive to some is the fact that they don't use operating
system resources: there's no OS-level stack or kernel process table
entry associated with them.  This also accounts for their biggest
weakness: when a microthread is suspended for I/O, *all* microthreads
are suspended.  In limited contexts, such as a network server, this
can be solved by an approach similar to that in Gordon's
SelectDispatcher.  (It would be a titanic effort to do this for every
potentially blocking I/O operation, and it probably wouldn't work well
with C extensions.)

I'm not sure what applications require the round-robin scheduling
property of uthreads -- certainly Gordon's application would seem to
be doing just fine without it (I'm not sure if it is being scheduled
round-robin or not).

Proper round-robin scheduling for uthreads requires explicit switching
code in the Python interpreter.  Stackless provides this, at the same
place where in regular Python the global interpreter lock is released
and re-acquired to give other threads a chance to run.  Is this
needed?

--Guido van Rossum (home page: http://www.python.org/~guido/)