[Python-ideas] Proto-PEP on a 'yield from' statement

[Greg Ewing]

Comments are invited on the following proto-PEP.

PEP: XXX
Title: Syntax for Delegating to a Subgenerator
Version: $Revision$
Last-Modified: $Date$
Author: Gregory Ewing <greg.ewing at canterbury.ac.nz>
Status: Draft
Type: Standards Track
Content-Type: text/x-rst
Created: 13-Feb-2009
Python-Version: 2.7
Post-History:


Abstract
========

A syntax is proposed to allow a generator to easily delegate part
of its operations to another generator, with the subgenerator
yielding directly to the delegating generator's caller and receiving
values sent to the delegating generator using send(). Additionally,
the subgenerator is allowed to return with a value and the
value is made available to the delegating generator.

The new syntax also opens up some opportunities for optimisation
when one generator re-yields values produced by another.


Proposal
========

The following new expression syntax will be allowed in the body of
a generator:

::

     yield from <expr>

where <expr> is an expression evaluating to an iterator. The effect
is to run the iterator to exhaustion, with any values that it yields
being passed directly to the caller of the generator containing the
``yield from`` expression (the "delegating generator"), and any values
sent to the delegating generator using ``send()`` being sent directly to
the iterator. (If the iterator does not have a ``send()`` method, values
sent in are ignored.)

The value of the ``yield from`` expression is the first argument to the
``StopIteration`` exception raised by the iterator when it terminates.

Additionally, generators will be allowed to execute a ``return``
statement with a value, and that value will be passed as an argument
to the ``StopIteration`` exception.


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

The statement

::

     result = yield from iterator

is semantically equivalent to

::

     _i = iterator
     try:
         _v = _i.next()
         while 1:
             if hasattr(_i, 'send'):
                 _v = _i.send(_v)
             else:
                 _v = _i.next()
     except StopIteration, _e:
         _a = _e.args
         if len(_a) > 0:
             result = _a[0]
         else:
             result = None


Rationale
=========

A Python generator is a form of coroutine, but has the limitation
that it can only yield to its immediate caller. This means that a piece
of code containing a ``yield`` cannot be factored out and put into a
separate function in the same way as other code. Performing such a factoring
causes the called function to itself become a generator, and it is
necessary to explicitly iterate over this second generator and re-yield
any values that it produces.

If yielding of values is the only concern, this is not very arduous
and can be performed with a loop such as

::

     for v in g:
         yield v

However, if the subgenerator is to receive values sent to the outer
generator using ``send()``, it is considerably more complicated. As the
formal expansion presented above illustrates, the necessary code is very
longwinded, and it is tricky to handle all the corner cases correctly.
In this case, the advantages of a specialised syntax should be clear.

The particular syntax proposed has been chosen as suggestive of its
meaning, while not introducing any new keywords and clearly standing
out as being different from a plain ``yield``.

Furthermore, using a specialised syntax opens up possibilities for
optimisation when there is a long chain of generators. Such chains
can arise, for instance, when recursively traversing a tree structure.
The overhead of passing ``next()`` calls and yielded values down and
up the chain can cause what ought to be an O(n) operation to become
O(n\*\*2).

A possible strategy is to add a slot to generator objects to
hold a generator being delegated to. When a ``next()`` or ``send()``
call is made on the generator, this slot is checked first, and if
it is nonempty, the generator that it references is resumed instead.
If it raises StopIteration, the slot is cleared and the main generator
is resumed.

This would reduce the delegation overhead to a chain of C function
calls involving no Python code execution. A possible enhancement
would be to traverse the whole chain of generators in a loop
and directly resume the one at the end, although the handling of
StopIteration is more complicated then.


Alternative Proposals
=====================

Proposals along similar lines have been made before, some using the
syntax ``yield *`` instead of ``yield from``. While ``yield *`` is
more concise, it could be argued that it looks too similar to an
ordinary ``yield`` and the difference might be overlooked when
reading code.

To the author's knowledge, previous proposals have focused only
on yielding values, and thereby suffered from the criticism that
the two-line for-loop they replace is not sufficiently tiresome
to write to justify a new syntax. By dealing with sent values
as well as yielded ones, this proposal provides considerably more
benefit.


Copyright
=========

This document has been placed in the public domain.



..
    Local Variables:
    mode: indented-text
    indent-tabs-mode: nil
    sentence-end-double-space: t
    fill-column: 70
    coding: utf-8
    End:

-- 
Greg