Microthreads without Stackless?

[David Mertz, Ph.D.]

Bryan Olson <fakeaddress at nowhere.org> wrote in message news:
> I'm genuinely surprised to find we disagree on what constitutes
> coroutine or micro/weightless threads.  I really did read
> David's articles, and I thought I was with him on that.  The
> article he cited brings up the distinction "Coroutines And Semi-
> coroutines", and I think it implies that full co-routines are
> not limited to a single level.

Well, a couple things.  The article on (semi-)coroutines is really a
different topic than the one on "weightless threads."  They both take
advantage of Python generators.  And they both involve a scheduler. 
But there are differences between the techniques... and still greater
differences between the motivations that would prompt the use of each.

Unfortunately, Bryan started the discussion with a claim like
"weightless threads aren't *really* coroutines"... to which the answer
is "Duh!"

Weightless threads basically amount to "cooperative multitasking." 
Unlike in actual Stackless (or with "weighty" OS threads), the
weightless thread schedulers/technique depends every "thread"
(procedure) acting nice, and giving control back to the scheduler
without too much delay.  Some older OS's were written this way, FWIW,
but those had obvious problems.  "Procedure" is a somewhat neutral
term for "a collection of instructions"... which is what all these
things are at an abstract level.

But when a weightless thread gives control back to its parent (the
scheduler), it doesn't provide any advice on which procedure/thread
should get attention next.  If the scheduler is written sensibly,
every procedure that wants it gets some attention fairly soon.  My
article just showed a simple round-robin scheduler, but I mention that
it wouldn't be hard to add priorities to give some procedures more
attention than others.  Either way, the scheduler grants the CPU time
to the procedure (but each one is responsible for not hogging that
time once it gets it).

A coroutine is different.  It's just a GOTO, really, but one where
each procedure contains a memory of where it left off.  That is, the
procedure is resumable in its middle, rather than always starting
again at the top (as in a regular function).  Under my
coroutine/state-machine scheduler, each procedure explicitly states
where it wants to branch to.  Not an arbitrary line within an
arbitrary procedure; but simply to the "last line processed" in an
arbitrary procedure.

At the Python Cookbook site, Bernhard Mulder unfortunately posted a
recipe that he called "coroutines", when what it really does is
implement weightless threads.  The recipe itself is fine, but I hate
to see people mislead on the nomenclature:

  http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/300019

Now it's true that Python syntax -in itself- only implements
semi-coroutines.  That is, you can branch INTO any procedure you want,
but the branch OUT OF that procedure is still stack like... i.e. to
the caller only.  What my article points out (which a lot of people
did not realize when Python generators were new) is that
semi-coroutines are actually fully general.  That is, while it is not
built into the *syntax*, you can perfectly well implement full
coroutines using semi-coroutines and a little extra Python code (a
scheduler).

As both Bryan and some other folks upthread point out, *FLAT*
coroutines don't mix well directly with a callstack.  There are things
you can do that use both, but reasoning about your programs becomes
more difficult, and you probably need extra code.  But you REALLY
don't lose anything by moving an explicit callstack out of a
function/generator object, and into the overall flow of your program.

Here's a perfectly traditional function-based callstack:

  def grandma():
      mom()
  def mom():
      daughter()
  def daughter()
      return
  grandma()

And here's how the flow between *procedures* happens:

  grandma -> mom -> daughter -> mom -> grandma -> EXIT

Obviously, if each function did something other than return and call
each other, the program would be more exciting.

You can bring about the same flow using generators:

  from __future__ import generators
  def grandma():
      print "grandma start"
      MOM.next()
      print "grandma exit"
      yield None
  def mom():
      print "mom start"
      DAUGHTER.next()
      print "mom exit"
      yield None
  def daughter():
      print "daughter start"
      print "daughter exit"
      yield None
  GRANDMA, MOM, DAUGHTER = grandma(), mom(), daughter()
  GRANDMA.next()

You can see from the new debugging messages that the flow is identical
among procedures, as before.  But if some of these had multiple yields
(or yields in a loop) you could also call GEN.next() repeatedly to
resume context.

Now you can perfectly well get callstack-like flow using the
coroutines described in:

  http://gnosis.cx/publish/programming/charming_python_b5.html

The only change is that you always "yield to" a given procedures,
rather than either call it, or call its .next() method.  Of course,
lots of other flows are possible other than stack-like.  But you are
not prohibited from stack-like flow (example typed without testing,
forgive any minor typo):

  from __future__ import generators
  cargo = None
  def grandma():
      yield (MOM, cargo)
  def mom():
      yield (DAUGHTER, cargo)
      yield (GRANDMA, cargo)
  def daughter():
      yield (MOM, cargo)
  GRANDMA, MOM, DAUGHTER = grandma(), mom(), daughter()
  scheduler(GRANDMA)

Btw. This implies a slightly different version of the scheduler than
that in the article.  That is, rather than lookup jump targets by name
(as in the article), we might just jump based on an actual passed
generator object.  There are advantages and disadvantages to this
change.  It's harder to make the switches data driven (e.g. user
input, or based on database table lookup), but the code is simpler and
has one less indirection.  The scheduler might look something like:

  def scheduler(start):
      global cargo
      coroutine = start
      while 1:
          (coroutine, cargo) = coroutine.next()

If you want to pass real data around, you probably have to throw in
some more 'global cargo' lines up there and/or hold shared data in a
class instance or other mutable, global structure.

Yours, David...