[Python-ideas] Cofunctions - Back to Basics

[Nick Coghlan]

On Fri, Oct 28, 2011 at 5:33 AM, Paul Moore <p.f.moore at gmail.com> wrote:
> On 27 October 2011 20:15, Arnaud Delobelle <arnodel at gmail.com> wrote:
>
>>> That article states that Python has coroutines as of 2.5 -- that's
>>> incorrect, isn't it?
>>
>> Generator functions + trampoline = coroutines
>
> If I understand, the cofunctions of this thread aren't coroutines as
> such, they are something intended to make writing coroutines easier in
> some way. My problem is that it's not at all obvious how they help.
> That's partly because the generator+trampoline idiom, although
> possible, is not at all common so that there's little in the way of
> examples, and even less in the way of common understanding, of how the
> idiom works and what problems there are putting it into practice.

I highly recommend reading the article Mark Shannon linked earlier in
the thread. I confess I didn't finish the whole thing, but even the
first half of it made me realise *why* coroutine programming in Python
(sans Stackless or greenlet) is such a pain: *every* frame on the
coroutine stack has to be a generator frame in order to support
suspending the generator.

When a generator calls into an ordinary function, suspension is not
possible until control has returned to the main generator frame. What
this means is that, for example, if you want to use generators to
implement asynchronous I/O, every layer between your top level
generator and the asynchronous I/O request *also* has to be a
generator, or the suspension doesn't work properly (control will be
returned to the innermost function frame, when you really want it to
get all the way back to the scheduler).

PEP 380 (i.e. "yield from") makes it easier to *create* those stacks
of generator frames, but it doesn't make the need for them to go away.
Proceeding further down that path (as PEP 3152 does) would essentially
partitioning Python programming into two distinct subsets: 'ordinary'
programming (where you can freely mix generators and ordinary function
frames) and 'generator coroutine' programming (where it *has* to be
generators all the way down to get suspension to work).

In some ways, this is the situation we have now, where people using
Twisted and other explicitly asynchronous libraries have to be
continuously aware of the risk of inadvertently calling functions that
might block. There's no way to write I/O functions that internally say
"if I'm in a coroutine, suspend with an asynchronous I/O request,
otherwise perform the I/O request synchronously".

Frankly, now that I understand the problem more clearly, attempting to
attack it by making it easier to create stacks consisting entirely of
generator frames strikes me as a terrible idea. Far better to find a
way to have a dynamic "non-local" yield construct that yields from the
*outermost* generator frame in the stack, regardless of whether the
current frame is a generator or not.

Ideally, we would like to make it possible to write code like this:

    def coroutine_friendly_io(*args, **kwds):
        if in_coroutine():
            return coyield AsychronousRequest(async_op, *args, **kwds)
        else:
            return sync_op(*args, **kwds)

If you look at the greenlet docs
(http://packages.python.org/greenlet/) after reading the article on
Lua's coroutines, you'll realise that greenlet implements *symmetric*
coroutines - you have to explicitly state which greenlet you are
switching to. You can then implement asymmetric coroutines on top of
that by always switching to a specific scheduler thread.

A more likely model for Python code would be Lua's *asymmetric*
coroutines. With these, you couldn't switch to another arbitrary
coroutine. Instead, the only thing you could do is suspend yourself
and return control to the frame that originally invoked the coroutine.

Some hypothetical stacks may help make this clearer:

Suspending nested generators with 'yield from':

  scheduler()
    --> result = outer_gen.next()
        --> yield from inner_gen()
            --> yield 42

After the yield is executed, our stack looks like this:

    outer_func()

The generator stack is gone - it was borrowing the thread's main
stack, so suspending unwound it. Instead, each generator *object* is
holding a reference to a suspended frame, so they're all kept alive by
the following reference chain:

   outer_func's frame (running) -> outer_gen -> outer_gen's frame
(suspended) -> inner_gen -> inner_gen's frame (suspended)

There's no object involved that has the ability to keep a *stack* of
frame's alive, so as soon as you get an ordinary function on the stack
inside the generator, you can't suspend any more.

Now, suppose we had greenlet style symmetric coroutines. You might do
something like this:

  scheduler_greenlet()  # (Could use the implicit main greenlet, but I
think this makes the example clearer)
      --> result = outer_greenlet.switch() # The
scheduler_greenlet.switch() call below returns here

  outer_greenlet() # Separate stack, not using the thread's main frame stack
      --> inner_func() # Can have ordinary function frames on the stack
          --> scheduler_greenlet.switch(42) # Suspends this greenlet

Finally, Lua style asymmetric coroutines might look like this:

  outer_func()
      --> result = outer_codef.next()  # The "coyield" below comes back here

  outer_codef() # Separate stack, not using the thread's main frame stack
      --> inner_func() # Just an ordinary function call
          --> coyield 42  # Actually suspends the whole coroutine

To achieve 'natural' coroutine programming, a Lua style asymmetric
coroutine approach looks the most promising to me.

Cheers,
Nick.

-- 
Nick Coghlan   |   ncoghlan at gmail.com   |   Brisbane, Australia