Revisiting Generators and Subgenerators
Winston
simulation in Jython and I need cooperative multitasking. PEP 380 hits
on my problem, but does not quite solve it for me. I have the
following proposal as an alternative to PEP380. I don't know if this
is the right way for me to introduce my idea, but below is my writeup.
Any thoughts?
------------------------
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 j in baton: # For statement calls baton.__iter__, and then
baton.next()
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
------------------
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.
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() )
Winston
can read it easier.
-Winston
-----------------
common use-case is agent simulators where many small
Examples
--------
# For statement calls baton.__iter__, and then baton.next()
for j in baton:
print j
Cooperative Multitasker:
# 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
Benefits
--------
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
------------------------------------------------------------
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 <c...@zip.com.au> 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
Winston Wolff
-Winston
Winston Wolff
Stratolab - Games for Learning
tel: (646) 827-2242
web: www.stratolab.com
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
Stefan Behnel
> ... 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
Steve Holden
[...]
> 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
--
Steve Holden +1 571 484 6266 +1 800 494 3119
See PyCon Talks from Atlanta 2010 http://pycon.blip.tv/
Holden Web LLC http://www.holdenweb.com/
UPCOMING EVENTS: http://holdenweb.eventbrite.com/
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.
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.
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
Cameron Simpson
| On Mar 25, 10:39 pm, Winston <winst...@stratolab.com> wrote:
| > 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,
--
Cameron Simpson <c...@zip.com.au> DoD#743
http://www.cskk.ezoshosting.com/cs/
Principles have no real force except when one is well fed. - Mark Twain