[Python-ideas] Cofunctions - A New Protocol

[Greg Ewing]

A Coroutine Protocol
====================

Here are some thoughts on the design of a new protocol to support lightweight
threads using a mechanism similar to, but distinct from, generators and
yield-from. Separating the two protocols will make it much easier to support
suspendable generators, something that is not possible using the cofunction
mechanism as currently specified in PEP 3152.

The protocol to be described is similar in many ways to the generator
protocol, and in what follows, analogies will be drawn between the two protocols
where it may aid understanding.


API
---

This section describes the outward appearance of the coroutine mechanism to
the programmer.

A coroutine is created using the following constructor:

::

     coroutine(f, *args, **kwds)

where ``f`` is an object obeying the "coroutine protocol" to be described
below. Syntactic support will be provided for creating such an object using
a special form of Python function definition, analogous to a generator.

The result is a "coroutine object" having the following methods:

``resume(value = None)``

     Resumes execution of the coroutine at the point where it was last
     suspended. The value, if any, is passed into the coroutine and
     becomes the return value of the operation that caused the suspension.
     The coroutine executes until its next suspension point, at which
     time the ``resume`` call returns with the value passed into the
     suspension operation.

     (Note: This is analogous to calling next() or send() on a generator-iterator.
     Suspension of a coroutine is analogous to a generator executing a
     ``yield`` operation.)

     If the coroutine has been freshly created, the passed-in value is
     ignored and the coroutine executes up to its first suspension point.

     If the top level of the coroutine finishes execution without
     encountering any further suspension points, a ``CoReturn`` exception
     is raised. This exception has a ``value`` attribute containing the
     return value from the coroutine.

     (Note: ``CoReturn`` is analogous to the ``StopIteration`` exception
     raised by an exhausted iterator or generator.)

``throw(exception)``

     Causes the given exception to be raised in the coroutine at its
     current suspension point.

``close()``

     Requests that the coroutine shut down and clean itself up. This is
     achieved by throwing in a ``CoExit`` exception (analogous to 
``GeneratorExit``).

It is expected that programmers will not write code that deals directly with
coroutine objects very often; rather, some kind of driver or scheduler will be
used that takes care of making ``resume()`` calls and handling ``CoReturn``
exceptions.


Cofunctions
-----------

There will be a special form of Python function called a "cofunction", defined
using the new keyword ``codef`` in place of ``def``. A cofunction provides a
convenient way of creating an object obeying the coroutine protocol. (This is
similar to how a generator provides a convenient way of creating an object
obeying the iterator protocol).

Suspension of a cofunction is achieved using the expression

::

     ``coyield`` [value]

This is analogous to a ``yield`` expression in a generator, and like ``yield``,
it can both provide and receive a value. However, unlike ``yield``, it is *not*
restricted to communicating with the immediate caller. It communicates directly
with the ``resume`` method of the coroutine, however deep the nesting of calls
is between the ``resume`` call and the ``coyield``.

There are some restrictions, however:

* A ``coyield`` is only allowed in the body of a cofunction (a function defined
with ``codef``), not in any other context.

* A cofunction can only be called from the body of another cofunction, not in
any other context.

Exceptions are raised if any of these restrictions are violated.

As a consequence, there must be an unbroken chain of cofunctions (or other objects
obeying the cofunction protocol, see below) making up the call stack from the
``resume`` method down to the suspension point. A cofunction may call an ordinary
function, but that function or anything called by it will not be able to suspend
the coroutine.

Note that the class of "ordinary functions" includes most functions and methods
written in C. However, it is possible for an object implemented in C to participate
in a coroutine stack by implementing the coroutine protocol below explicitly.


Coroutine Protocol
------------------

As well as the coroutine object, the coroutine protocol involves three other kinds
of objects, "cocallable objects", "coframe objects" and "coiterator objects".

A cocallable object has the following method:

``__cocall__(*args, **kwds)``

     Initiates a suspendable computation. Returns a coframe object.

     (This is analogous to the __iter__ method of an iterable object.)

     May return NotImplemented to signal that the object does not support the
     coroutine protocol. This enables wrapper objects such as bound methods to
     reflect whether or not the wrapped object supports the coroutine protocol.

A coframe object has the following methods:

``__resume__(costack, value)``

     There are two purposes for which this method is called: to continue
     execution from a suspension point, and to pass in the return value resulting
     from a nested call to another cocallable object.

     In both cases, the ``resume`` method is expected to continue execution until
     the next suspension point, and return the value produced by it. If the
     computation finishes before reaching another suspension point,
     ``CoReturn(retval)`` must be raised, where ``retval`` is the return value of
     the computation.

     (This method is analogous to the __send__ method of a generator-iterator.
     With a value of None, it is analogous to the __next__ method of an iterator.)

     The currently-executing coroutine object is passed in as the ``costack``
     parameter. The ``__resume__`` method can make a nested call to another 
cocallable
     object ``sub`` by performing:

         ``return costack.call(sub, *args, **kwds)``

     No further calls to this coframe will be made until ``obj`` finishes. When
     it does, the ``__resume__`` method of this coframe  is called with the
     return value from ``sub``.

     It is the responsibility of the coframe object to keep track of whether the
     previous call to its ``__resume__`` method resulted in a suspension or a nested
     call, and make use of the ``value`` parameter accordingly.

``__throw__(costack, exception)``

     Called to throw an exception into the computation. The coframe may choose to
     absorb the exception and continue executing, in which case ``__throw__`` should
     return the value produced by the next exception point or raise ``CoReturn`` as
     for ``__resume__``. Alternatively it may allow the same or a different 
exception
     to propagate out.

     Implementation of this method is optional. If it is not present, the behaviour
     is as if a trivial ``__throw__`` method were present that simply re-raises the
     exception.

A coiterator is an iterator that permits iteration to be carried out in a 
suspendable
manner. A coiterator object has the following method:

``__conext__()``

     Returns a coframe for computing the next item from the iteration. This is the
     coroutine equivalent of an iterator's ``__next__`` method, and behaves 
accordingly:
     its ``__resume__`` method must return an item by raising ``CoReturn(item)``. To
     finish the iteration, it raises ``StopIteration`` as usual.

To support coiteration, whenever a "next" operation is invoked by a cofunction
(whether implicitly by means of a for-loop or explicitly by calling ``next()``)
a ``__conext__`` method is first looked for, and if found, the operation is
carried out suspendably. Otherwise a normal call is made to the ``__next__``
method.


Formal Semantics
----------------

The semantics of the coroutine object are defined by the following Python 
implementation.

::

     class coroutine(object):

         #  Public methods

         def __init__(self, main, *args, **kwds):
             self._stack = []
             self._push(_cocall(main, *args, **kwds))

         def resume(self, value = None):
             return self._run(value, None)

         def throw(self, exc):
             return self._run(None, exc)

         def close(self):
             try:
                 self.throw(CoExit)
             except (CoExit, CoReturn):
                 pass

         def call(self, subroutine, *args, **kwds):
             meth = getattr(subroutine, '__cocall__', None)
             if meth is not None:
                 frame = meth(*args, **kwds)
                 if frame is not NotImplemented:
                     self._push(frame)
                     return self._run(None, None)
             return CoReturn(subroutine(*args, **kwds))

         #  Private methods

         def _run(self, value, exc):
             while True:
                 try:
                     frame = self._top()
                     if exc is None:
                         return frame.__resume__(self, value)
                     else:
                         meth = getattr(frame, '__throw__', None)
                         if meth is not None:
                             return meth(self, exc)
                         else:
                             raise exc
                 except BaseException as exc:
                     if self._pop():
                         if isinstance(exc, CoReturn):
                             value = exc.value
                             exc = None
                     else:
                         raise

         def _push(self, frame):
             self._stack.append(frame)

         def _pop(self):
             if len(self._stack) > 0:
                 del self._stack[-1]
                 return True
             else:
                 return False

         def _top(self):
             return self._stack[-1]

-- 
Greg