Revisiting Generators and Subgenerators


W

Winston

Here's my proposal again, but hopefully with better formatting so you
can read it easier.


-Winston
-----------------

Proposal for a new Generator Syntax in Python 3K--
A Baton object for generators to allow subfunction to yield, and to
make
them symetric.

Abstract
--------
Generators can be used to make coroutines. But they require
the programmer to take special care in how he writes his
generator. In particular, only the generator function may
yield a value. We propose a modification to generators in
Python 3 where a "Baton" object is given to both sides of a
generator. Both sides use the baton object to pass execution
to the other side, and also to pass values to the other side.

The advantages of a baton object over the current scheme are:
(1) the generator function can pass the baton to a
subfunction, solving the needs of PEP 380, (2) after creation
both sides of the generator function are symetric--they both
can call yield(), send(), next(). They do the same thing.
This means programming with generators is the same as
programming with normal functions. No special contortions are
needed to pass values back up to a yield command at the top.

Motivation
----------
Generators make certain programming tasks easier, such as (a)
an iterator which is of infinite length, (b) using a
"trampoline function" they can emulate coroutines and
cooperative multitasking, (c) they can be used to make both
sides of a producer-consumer pattern easy to write--both
sides can appear to be the caller.

On the down side, generators as they currently are
implemented in Python 3.1 require the programmer to take
special care in how he writes his generator. In particular,
only the generator function may yield a value--subfunctions
called by the generator function may not yield a value.

Here are two use-cases in which generators are commonly
used, but where the current limitation causes less readable
code:

1) a long generator function which the programmer wants to
split into several functions. The subfunctions should be able
to yield a result. Currently the subfunctions have to pass
values up to the main generator and have it yield the results
back. Similarly subfunctions cannot receive values that the
caller sends with generator.send()

2) generators are great for cooperative multitasking. A
common use-case is agent simulators where many small
"tasklets" need to run and then pass execution over to other
tasklets. Video games are a common scenario, as is SimPy.
Without cooperative multitasking, each tasklet must be
contorted to run in a small piece and then return. Generators
help this, but a more complicated algorithm which is best
decomposed into several functions must be contorted because
the subfuctions cannot yield or recive data from the
generator.send().

Here is also a nice description of how coroutines make
programs easier to read and write:
http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

Proposal
--------
If there is a way to make a sub-function of a generator yield
and receive data from generator.send(), then the two problems
above are solved.

For example, this declares a generator. The first parameter
of the generator is the "context" which represents the other
side of the execution frame.

a Baton object represents a passing of the execution from one
line of code to another. A program creates a Baton like so:

generator f( baton ):
# compute something
baton.yield( result )
# compute something
baton.yield( result )

baton = f()
while True:
print( baton.yield() )


A generator function, denoted with they keyword "generator"
instead of "def" will return a "baton". Generators have the
following methods:
__call__( args... ) --
This creates a Baton object which is passed back to
the caller, i.e. the code that executed the Baton()
command. Once the baton starts working, the two sides
are symetric. So we will call the first frame, frame
A and the code inside 'function' frame B. Frame is is
returned a baton object. As soon as frame A calls
baton.yield(), frame B begins, i.e. 'function' starts
to run. function is passed the baton as its first
argument, and any additional arguments are also
passed in. When frame B yields, any value that it
yields will be returned to frame A as the result of
it's yield().

Batons have the following methods:
yield( arg=None ) -- This method will save the current
execution state, restore the other execution state,
and start running the other function from where it
last left off, or from the beginning if this is the
first time. If the optional 'arg' is given, then the
other side will be "returned" this value from it's
last yield(). Note that like generators, the first
call to yield may not pass an argument.
next() -- This method is the same as yield(None). next()
allows the baton to be an iterator.
__iter__() -- A baton is an iterator so this just returns
the baton back. But it is needed to allow use of
batons in "for" statements.
start() -- This starts the frame B function running. It
may only be called on a new baton. It starts the
baton running in frame B, and returns the Baton
object to the caller in frame A. Any value from the
first yield is lost.

baton = Baton( f ).start()
It is equivalent to:
baton = Baton( f ) # Create the baton
baton.yield() # Begin executing in frame B



Examples
--------

Simple Generator:
generator doubler( baton, sequence ):
for a in sequence:
print( a )
baton.yield( a+a )

baton = doubler( [3,8,2] )
# For statement calls baton.__iter__, and then baton.next()
for j in baton:
print j

Complicated Generator broken into parts:

generator Complicated( baton, sequence ):
'''A generator function, but there are no yield
statements in this function--they are in
subfunctions.'''
a = sequence.next()
if is_special(a):
parse_special( baton, a, sequence)
else:
parse_regular( baton, a, sequence )

def parse_special( baton, first, rest ):
# process first
baton.yield()
b = rest.next()
parse_special( baton, b, rest )

def parse_regular( baton, first, rest ):
# more stuff
baton.yield()

baton = Complicated( iter('some data here') )
baton.yield()


Cooperative Multitasker:

class Creature( object ):
def __init__(self, world):
self.world = world

generator start( self, baton ):
'''Designated entry point for tasklets'''
# Baton saved for later. Used in other
# methods like escape()
self.baton = baton
self.run()

def run(self):
pass # override me in your subclass

def escape(self):
# set direction and velocity away
# from baton creatures
self.baton.yield()

def chase(self):
while True:
# set direction and velocity TOWARDS
# nearest creature
self.baton.yield()
# if near enough, try to pounce
self.baton.yield()


class Vegetarian( Tasklet ):
def run(self):
if self.world.is_creature_visible():
self.escape()
else:
# do nothing
self.baton.yield()

class Carnivore( Tasklet ):
def run(self):
if self.world.is_creature_visible():
self.chase()
else:
# do nothing
self.baton.yield()

w = SimulationWorld()
v = Vegetarian( w ).start()
c = Carnivore( w ).start()
while True:
v.yield()
c.yield()


Benefits
--------

This new syntax for a generator provides all the benefits of
the old generator, including use like a coroutine.
Additionally, it makes both sides of the generator almost
symetric, i.e. they both "yield" or "send" to the other. And
since the baton objects are passed around, subfunctions can
yield back to the other execution frame. This fixes problems
such as PEP 380.

My ideas for syntax above are not fixed, the important
concept here is that the two sides of the generator functions
will have a "baton" to represent the other side. The baton
can be passed to sub-functions, and values can be sent, via
the baton, to the other side.

This new syntax for a generator will break all existing
programs. But we happen to be at the start of Python 3K where
new paradaigms are
being examined.

Alternative Syntax
------------------

yield, next, and send are redundant
------------------------------------
With old style generators, g.next() and g.send( 1 ) are
conceptually the same as "yield" and "yield 1" inside the
generator. They both pass execution to the other side, and
the second form passes a value. Yet they currently have
different syntax. Once we have a baton object, we can get rid
of one of these forms. g.next() is needed to support
iterators. How about we keep baton.next() and baton.send( 1
). We get rid of yield completely.

Use keyword to invoke a generator rather than declare
------------------------------------------------------------
Perhaps instead of a "generator" keyword to denote the
generator function, a "fork" keyword should be used to begin
the second execution frame. For example:

def f( baton ):
# compute something
baton.send( result )
# compute something
baton.send( result )

baton = fork f()
while True:
print( baton.next() )

or maybe the "yield" keyword can be used here:

def f( baton ):
# compute something
baton.send( result )
# compute something
baton.send( result )

baton = yield f
while True:
print( baton.next() )
 
Ad

Advertisements

C

Cameron Simpson

| Here's my proposal again, but hopefully with better formatting so you
| can read it easier.

Having quickly read the Abstract and Motivation, why is this any better
than a pair of threads and a pair of Queue objects? (Aside from
co-routines being more lightweight in terms of machine resources?)

On the flipside, given that generators were recently augumented to
support coroutines I can see your motivation within that framework.

Cheers,
--
Cameron Simpson <[email protected]> DoD#743
http://www.cskk.ezoshosting.com/cs/

C makes it easy for you to shoot yourself in the foot. C++ makes that
harder, but when you do, it blows away your whole leg.
- Bjarne Stroustrup
 
W

Winston Wolff

Coroutines achieve very similar things to threads, but avoid problems resulting from the pre-emptive nature of threads. Specifically, a coroutine indicates where it will yield to the other coroutine. This avoids lots of problems related to synchronization. Also the lightweight aspect is apparently important for some simulations when they have many thousands of agents to simulate--this number of threads becomes a problem.

-Winston

Winston Wolff
Stratolab - Games for Learning
tel: (646) 827-2242
web: www.stratolab.com
 
P

Patrick Maupin

(a bunch of stuff about coroutines)

There have been proposals in the past for more full-featured
generators, that would work as general purpose coroutines. Among
other things, there were issues with exception propagation, and the
design was deliberately simplified to what we have today. Before
proposing anything in this area you should carefully read PEPs 288,
325, and 342, and all the discussion about those PEPs in the python-
dev archives.

After reading all that, and still being convinced that you have the
greatest thing since sliced bread (and that you REALLY understand all
the concerns about exceptions and other things), you need to update
your document to address all the concerns raised in the discussions on
those PEPs, put on your asbestos suit (modern asbestos-free
replacements never work as advertised), and then re-post your
document.

Personally, I am very interested in co-routines, but I have very
little time right now, and am not at all interested in reading a
proposal from somebody who doesn't know the full history of how
generators got to be the way they are (the lack of coroutines is not
an accidental oversight). I suspect I am not alone in this opinion,
so there is probably some interest in a realistic proposal, but
perhaps also some skepticism about whether a realistic proposal can
actually be engineered...

Best regards and good luck!
Pat
 
S

Stefan Behnel

Patrick Maupin, 26.03.2010 04:30:
... and then re-post your document.

.... preferably to the python-ideas mailing list. Although it seems to me
that this is something that could be explored as a library first - which
usually means that people will tell you exactly that on python-ideas and
ask you to come back with an implementation that has proven to be useful in
practice.

Stefan
 
S

Steve Holden

Winston wrote:
[...]
This new syntax for a generator will break all existing
programs. But we happen to be at the start of Python 3K where
new paradaigms are
being examined.

However good your idea may be, I suspect this one sentence will kill it.

We are no longer "at the start of Py3k", we are moving towards the third
release, and there is already a substantial body of code and literature
embodying the current syntax.

So you would need to reformulate your proposals to incorporate backward
compatibility.

regards
Steve
 
Ad

Advertisements

S

Sebastien Binet

Here's my proposal again, but hopefully with better formatting so you
can read it easier.

-Winston
-----------------

Proposal for a new Generator Syntax in Python 3K--
A Baton object for generators to allow subfunction to yield, and to
make
them symetric.

isn't a Baton what CSP calls a channel ?

there is this interesting PyCSP library (which implements channels
over greenlets, os-processes (via multiprocessing) or python threads)
http://code.google.com/p/pycsp

cheers,
sebastien.
 
W

Winston

isn't a Baton what CSP calls a channel ?

there is this interesting PyCSP library (which implements channels
over greenlets, os-processes (via multiprocessing) or python threads)http://code.google.com/p/pycsp

cheers,
sebastien.

Thanks for the link. After reading about Greenlets, it seems my Baton
is a Greenlet. It is not passed in to the new greenlet as I wrote
above, but both sides use it to pass execution to the other, and to
send a value on switching.

I'm glad my thinking is matching other people's thinking. Now I have
to search for a greenlet written for Jython.

And thanks to others for their thoughts on this subject.

-Winston
 
Ad

Advertisements

C

Cameron Simpson

| > A Baton object for generators to allow subfunction to yield, and to
| > make them symetric.
|
| isn't a Baton what CSP calls a channel ?

I was thinking about this (roughly) in the shower this morning before
seeing this message.

One difference is that a Channel or zero-storage Queue lets the putter
continue execution after the put (or at least the other side's get). A
co-routine won't proceed until later, no? So a co-routine setup will do
lazier computation than a similar threaded setup.

Cheers,
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top