[Python-checkins] CVS: python/nondist/peps pep-0279.txt,1.5,1.6
Barry Warsaw
bwarsaw@users.sourceforge.net
Mon, 11 Mar 2002 09:33:52 -0800
Update of /cvsroot/python/python/nondist/peps
In directory usw-pr-cvs1:/tmp/cvs-serv28327
Modified Files:
pep-0279.txt
Log Message:
PEP 279 update from Raymond Hettinger
Index: pep-0279.txt
===================================================================
RCS file: /cvsroot/python/python/nondist/peps/pep-0279.txt,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** pep-0279.txt 4 Mar 2002 13:20:02 -0000 1.5
--- pep-0279.txt 11 Mar 2002 17:33:49 -0000 1.6
***************
*** 21,64 ****
Rationale
! Starting with xrange() and xreadlines(), Python has been evolving
! toward a model that provides lazy evaluation as an alternative
! when complete evaluation is not desired because of memory
! restrictions or availability of data.
!
! Starting with Python 2.2, a second evolutionary direction came in
! the form of iterators and generators. The iter() factory function
! and generators were provided as convenient means of creating
! iterators. Deep changes were made to use iterators as a unifying
! theme throughout Python. The unification came in the form of
establishing a common iterable interface for mappings, sequences,
! and file objects. In the case of mappings and file objects, lazy
! evaluation became the norm.
! The next steps in the evolution of generators are:
! 1. Add built-in functions which provide lazy alternatives to their
! complete evaluation counterparts and one other convenience
! function which was made possible once iterators and generators
! became available. The new functions are xzip, xmap, xfilter,
! and indexed.
! 2. Provide a generator alternative to list comprehensions [3]
! making generator creation as convenient as list creation.
! 3. Extend the syntax of the 'yield' keyword to enable generator
! parameter passing. The resulting increase in power simplifies
! the creation of consumer streams which have a complex execution
! state and/or variable state.
! 4. Add a generator method to enable exceptions to be passed to a
generator. Currently, there is no clean method for triggering
exceptions from outside the generator. Also, generator exception
passing helps mitigate the try/finally prohibition for generators.
All of the suggestions are designed to take advantage of the
existing implementation and require little additional effort to
incorporate. Each is backward compatible and requires no new
! keywords. These generator tools go into Python 2.3 when
generators become final and are not imported from __future__.
--- 21,81 ----
Rationale
! Python 2.2 introduced the concept of an iterable interface as proposed
! in PEP 234 [4]. The iter() factory function was provided as common
! calling convention and deep changes were made to use iterators as a
! unifying theme throughout Python. The unification came in the form of
establishing a common iterable interface for mappings, sequences,
! and file objects.
! Generators, as proposed in PEP 255 [1], were introduced as a means for
! making it easier to create iterators, especially ones with a complex
! internal execution or variable states. When I created new programs,
! generators were often the tool of choice for creating an iterator.
! However, when updating existing programs, I found that the tool had
! another use, one that improved program function as well as structure.
! Those programs exhibited a pattern of creating large lists and then
! looping over them. As data sizes increased, the programs encountered
! scalability limitations owing to excessive memory consumption (and
! malloc time) for the intermediate lists. Generators were found to be
! directly substitutable for the lists while eliminating the memory
! issues through lazy evaluation a.k.a. just in time manufacturing.
! Python itself encountered similar issues. As a result, xrange() and
! xreadlines() were introduced. And, in the case of file objects and
! mappings, lazy evaluation became the norm. Generators provide a tool
! to program memory conserving for-loops whenever complete evaluation is
! not desired because of memory restrictions or availability of data.
! The next steps in the evolution of generators are:
! 1. Add a new builtin function, indexed() which was made possible
! once iterators and generators became available. It provides
! all iterables with the same advantage that iteritem() affords
! to dictionaries -- a compact, readable, reliable index notation.
!
! 2. Establish a generator alternative to list comprehensions [3]
! to provide a simple way to convert a list comprehensions into
! generators whenever memory issues arise.
!
! 3. Add a generator method to enable exceptions to be passed to a
generator. Currently, there is no clean method for triggering
exceptions from outside the generator. Also, generator exception
passing helps mitigate the try/finally prohibition for generators.
+ 4. [Proposal 4 is now deferred until Python 2.4]
+ Extend the syntax of the 'yield' keyword to enable generator
+ parameter passing. The resulting increase in power simplifies
+ the creation of consumer streams which have a complex execution
+ state and/or variable state.
+
All of the suggestions are designed to take advantage of the
existing implementation and require little additional effort to
incorporate. Each is backward compatible and requires no new
! keywords. The first three generator tools go into Python 2.3 when
generators become final and are not imported from __future__.
+ The fourth proposal should be considered deferred and will be
+ proposed for Python 2.4 after the Python community has more
+ experience with generators.
***************
*** 67,149 ****
There is not currently a CPython implementation; however, a simulation
! module written in pure Python is available on SourceForge [8]. The
simulation covers every feature proposed in this PEP and is meant
to allow direct experimentation with the proposals.
! There is also a module [9] with working source code for all of the
examples used in this PEP. It serves as a test suite for the simulator
and it documents how each of the new features works in practice.
! Specification for new built-ins:
!
! def xfilter(pred, gen):
! '''
! xfilter(...)
! xfilter(function, sequence) -> list
!
! Return an iterator containing those items of sequence for
! which function is true. If function is None, return a list of
! items that are true.
! '''
! if pred is None:
! for i in gen:
! if i:
! yield i
! else:
! for i in gen:
! if pred(i):
! yield i
!
! def xmap(fun, *collections): ### Code from Python Cookbook [6]
! '''
! xmap(...)
! xmap(function, sequence[, sequence, ...]) -> list
!
! Return an iterator applying the function to the items of the
! argument collection(s). If more than one collection is given,
! the function is called with an argument list consisting of the
! corresponding item of each collection, substituting None for
! missing values when not all collections have the same length.
! If the function is None, return an iterator of the items of the
! collection (or an iterator of tuples if more than one collection).
! '''
! gens = map(iter, collections)
! values_left = [1]
! def values():
! # Emulate map behavior by padding sequences with None
! # when they run out of values.
! values_left[0] = 0
! for i in range(len(gens)):
! iterator = gens[i]
! if iterator is None:
! yield None
! else:
! try:
! yield iterator.next()
! values_left[0] = 1
! except StopIteration:
! gens[i] = None
! yield None
! while 1:
! args = tuple(values())
! if not values_left[0]:
! raise StopIteration
! yield fun(*args)
!
! def xzip(*collections):
! '''
! xzip(...)
! xzip(seq1 [, seq2 [...]]) -> [(seq1[0], seq2[0] ...), (...)]
!
! Return a iterator of tuples, where each tuple contains the
! i-th element from each of the argument sequences or iterable.
! The returned iterator is truncated in length to the length of
! the shortest argument collection.
! '''
! gens = map(iter, collections)
! while 1:
! yield tuple([g.next() for g in gens])
def indexed(collection, cnt=0, limit=None):
--- 84,105 ----
There is not currently a CPython implementation; however, a simulation
! module written in pure Python is available on SourceForge [7]. The
simulation covers every feature proposed in this PEP and is meant
to allow direct experimentation with the proposals.
! There is also a module [8] with working source code for all of the
examples used in this PEP. It serves as a test suite for the simulator
and it documents how each of the new features works in practice.
+ The authors and implementers of PEP 255 [1] were contacted to provide
+ their assessment of whether these enhancements were going to be
+ straight-forward to implement and require only minor modification
+ of the existing generator code. Neil felt the assertion was correct.
+ Ka-Ping thought so also. GvR said he could believe that it was true.
+ Tim did not have an opportunity to give an assessment.
+
! Specification for a new builtin:
def indexed(collection, cnt=0, limit=None):
***************
*** 160,164 ****
xrange, sequence, or iterable object. Also, those proposals were
presented and evaluated in the world prior to Python 2.2 which did
! not include generators. As a result, the generator-less version in
PEP 212 had the disadvantage of consuming memory with a giant list
of tuples. The generator version presented here is fast and light,
--- 116,120 ----
xrange, sequence, or iterable object. Also, those proposals were
presented and evaluated in the world prior to Python 2.2 which did
! not include generators. As a result, the non-generator version in
PEP 212 had the disadvantage of consuming memory with a giant list
of tuples. The generator version presented here is fast and light,
***************
*** 166,199 ****
in mid-stream.
!
! Note B: An alternate, simplified definition of indexed is:
!
! def indexed(collection, cnt=0, limit=sys.maxint):
! 'Generates an indexed series: (0,seqn[0]), (1,seqn[1]) ...'
! return xzip( xrange(cnt,limit), collection )
!
!
! Note C: As it stands, the Python code for xmap is slow. The actual
! implementation of the functions should be written in C for speed.
! The pure Python code listed above is meant only to specify how the
! functions would behave, in particular that they should as closely as
! possible emulate their non-lazy counterparts.
! Note D: Almost all of the PEP reviewers welcomed these functions but were
! divided as to whether they should be built-ins or in a separate module.
! The main argument for a separate module was to slow the rate of language
! inflation. The main argument for built-ins was that these functions are
! destined to be part of a core programming style, applicable to any object
! with an iterable interface. Just as zip() solves the problem of looping
! over multiple sequences, the indexed() function solves the loop counter
! problem. Likewise, the x-functions solve the problem of applying
! functional constructs without forcing the evaluation of an entire sequence.
! If only one built-in were allowed, then indexed() is the most important
general purpose tool, solving the broadest class of problems while
! improving program brevity, clarity and reliability.
Specification for Generator Comprehensions:
--- 122,172 ----
in mid-stream.
! There are other PEPs which touch on related issues: integer iterators,
! integer for-loops, and one for modifying the arguments to range and
! xrange. The indexed() proposal does not preclude the other proposals
! and it still meets an important need even if those are adopted -- the need
! to count items in any iterable. The other proposals give a means of
! producing an index but not the corresponding value. This is especially
! problematic if a sequence is given which doesn't support random access
! such as a file object, generator, or sequence defined with __getitem__.
! Note B: Almost all of the PEP reviewers welcomed the function but were
! divided as to whether there should be any builtins. The main argument
! for a separate module was to slow the rate of language inflation. The
! main argument for a builtin was that the function is destined to be
! part of a core programming style, applicable to any object with an
! iterable interface. Just as zip() solves the problem of looping
! over multiple sequences, the indexed() function solves the loop
! counter problem.
! If only one builtin is allowed, then indexed() is the most important
general purpose tool, solving the broadest class of problems while
! improving program brevity, clarity and reliability.
!
+ Commentary from GvR: filter and map should die and be subsumed into list
+ comprehensions, not grow more variants. I'd rather introduce builtins
+ that do iterator algebra (e.g. the iterzip that I've often used as
+ an example).
+
+ Commentary from Ka-Ping Yee: I'm also quite happy with everything you
+ proposed ... and the extra builtins (really 'indexed' in particular)
+ are things I have wanted for a long time.
+
+ Commentary from Neil Schemenauer: The new builtins sound okay. Guido
+ may be concerned with increasing the number of builtins too much. You
+ might be better off selling them as part of a module. If you use a
+ module then you can add lots of useful functions (Haskell has lots of
+ them that we could steal).
+ Author response: Prior to these comments, four builtins were proposed.
+ After the comments, xmap xfilter and xzip were withdrawn. The one
+ that remains is vital for the language and is proposed by itself.
+
+ I still secretly covet xzip() a.k.a. iterzip() but think that it will
+ happen on its own someday.
+
+
Specification for Generator Comprehensions:
***************
*** 225,229 ****
minus side, the brackets may falsely suggest that the whole
expression returns a list. Most of the feedback received to date
! indicates that brackets are helpful and not misleading.
Note B: List comprehensions expose their looping variable and
--- 198,211 ----
minus side, the brackets may falsely suggest that the whole
expression returns a list. Most of the feedback received to date
! indicates that brackets are helpful and not misleading. Unfortunately,
! the one dissent is from GvR.
!
! A key advantage of the generator comprehension syntax is that it
! makes it trivially easy to transform existing list comprehension
! code to a generator by adding yield. Likewise, it can be converted
! back to a list by deleting yield. This makes it easy to scale-up
! programs from small datasets to ones large enough to warrant
! just in time evaluation.
!
Note B: List comprehensions expose their looping variable and
***************
*** 247,252 ****
! Specification for Generator Parameter Passing:
1. Allow 'yield' to assign a value as in:
--- 229,341 ----
+ Commentary from GvR: Cute hack, but I think the use of the [] syntax
+ strongly suggests that it would return a list, not an iterator. I
+ also think that this is trying to turn Python into a functional
+ language, where most algorithms use lazy infinite sequences, and I
+ just don't think that's where its future lies.
+
+ Commentary from Ka-Ping Yee: I am very happy with the things you have
+ proposed in this PEP. I feel quite positive about generator
+ comprehensions and have no reservations. So a +1 on that.
! Commentary from Neil Schemenauer: I'm -0 on the generator list
! comprehensions. They don't seem to add much. You could easily use
! a nested generator to do the same thing. They smell like lambda.
!
! Author response: This may be before its time in that some people still
! don't like list comprehensions and half of this PEP's reviewers did
! not have any use for generators in any form. What I like best about
! generator comprehensions is that I can design using list
! comprehensions and then easily switch to a generator (by adding
! yield) in response to scalability requirements (when the list
! comprehension produces too large of an intermediate result).
!
!
!
! Specification for Generator Exception Passing:
!
! Add a .throw(exception) method to the generator interface:
!
! def logger():
! start = time.time()
! log = []
! try:
! while 1:0
! log.append( time.time() - start )
! yield log[-1]
! except WriteLog:
! return log
!
! g = logger()
! for i in [10,20,40,80,160]:
! testsuite(i)
! g.next()
! g.throw(WriteLog)
!
! There is no existing work-around for triggering an exception
! inside a generator. This is a true deficiency. It is the only
! case in Python where active code cannot be excepted to or through.
!
! Generator exception passing also helps address an intrinsic limitation
! on generators, the prohibition against their using try/finally to
! trigger clean-up code [1]. Without .throw(), the current work-around
! forces the resolution or clean-up code to be moved outside the generator.
!
!
! Note A: The name of the throw method was selected for several
! reasons. Raise is a keyword and so cannot be used as a method
! name. Unlike raise which immediately raises an exception from the
! current execution point, throw will first return to the generator
! and then raise the exception. The word throw is suggestive of
! putting the exception in another location. The word throw is
! already associated with exceptions in other languages.
!
! Alternative method names were considered: resolve(), signal(),
! genraise(), raiseinto(), and flush(). None of these seem to fit
! as well as throw().
!
!
! Note B: The throw syntax should exactly match raise's syntax:
!
! throw([expression, [expression, [expression]]])
!
! Accordingly, it should be implemented to handle all of the following:
!
! raise string g.throw(string)
! raise string, data g.throw(string,data)
! raise class, instance g.throw(class,instance)
! raise instance g.throw(instance)
! raise g.throw()
!
!
! Commentary from GvR: I'm not convinced that the cleanup problem that
! this is trying to solve exists in practice. I've never felt the need
! to put yield inside a try/except. I think the PEP doesn't make enough
! of a case that this is useful.
!
! Commentary from Ka-Ping Yee: I agree that the exception issue needs to
! be resolved and [that] you have suggested a fine solution.
!
! Commentary from Neil Schemenauer: The exception passing idea is one I
! hadn't thought of before and looks interesting. If we enable the
! passing of values back, then we should add this feature too.
!
! Author response: If the sole use of generators is to simplify writing
! iterators for lazy producers, then the odds of needing generator
! exception passing are very slim. If, on the other hand, generators
! are used to write lazy consumers, create coroutines, generate output
! streams, or simply for their marvelous capability for restarting a
! previously frozen state, THEN the need to raise exceptions will
! come up almost every time.
!
! I'm no judge of what is truly Pythonic, but am still astonished
! that there can exist blocks of code that can't be excepted to or
! through, that the try/finally combination is blocked, and that the
! only work-around is to rewrite as a class and move the exception
! code out of the function or method being excepted.
!
!
!
! Specification for Generator Parameter Passing [Deferred Proposal]
1. Allow 'yield' to assign a value as in:
***************
*** 326,330 ****
ostream.next(firstdat) # Analogous to file.write(dat)
ostream.next(seconddat)
! ostream.throw(FlushStream) # This feature proposed below
--- 415,419 ----
ostream.next(firstdat) # Analogous to file.write(dat)
ostream.next(seconddat)
! ostream.throw(FlushStream) # This feature proposed above
***************
*** 332,336 ****
Loop over the picture files in a directory, shrink them
! one at a time to thumbnail size using PIL [7], and send them to a
lazy consumer. That consumer is responsible for creating a large
blank image, accepting thumbnails one at a time and placing them
--- 421,425 ----
Loop over the picture files in a directory, shrink them
! one at a time to thumbnail size using PIL [6], and send them to a
lazy consumer. That consumer is responsible for creating a large
blank image, accepting thumbnails one at a time and placing them
***************
*** 351,462 ****
! Specification for Generator Exception Passing:
!
! Add a .throw(exception) method to the generator interface:
!
! def mygen():
! try:
! while 1:
! x = yield None
! print x
! except FlushStream:
! print 'Done'
!
! g = mygen()
! g.next(5)
! g.throw(FlushStream)
! There is no existing work-around for triggering an exception
! inside a generator. This is a true deficiency. It is the only
! case in Python where active code cannot be excepted to or through.
! Even if the .next(arg) proposal is not adopted, we should add the
! .throw() method.
! Generator exception passing also helps address an intrinsic limitation
! on generators, the prohibition against their using try/finally to
! trigger clean-up code [1]. Without .throw(), the current work-around
! forces the resolution or clean-up code to be moved outside the generator.
!
- Note A: The name of the throw method was selected for several
- reasons. Raise is a keyword and so cannot be used as a method
- name. Unlike raise which immediately raises an exception from the
- current execution point, throw will first return to the generator
- and then raise the exception. The word throw is suggestive of
- putting the exception in another location. The word throw is
- already associated with exceptions in other languages.
- Alternative method names were considered: resolve(), signal(),
- genraise(), raiseinto(), and flush(). None of these seem to fit
- as well as throw().
! Note B: The throw syntax should exactly match raise's syntax:
!
! throw([expression, [expression, [expression]]])
!
! Accordingly, it should be implemented to handle all of the following:
! raise string g.throw(string)
! raise string, data g.throw(string,data)
! raise class, instance g.throw(class,instance)
! raise instance g.throw(instance)
! raise g.throw()
!
!
! Discussion of Restartability:
!
! Inside for-loops, generators are not substitutable for lists unless they
! are accessed only once. A second access only works for restartable
! objects like lists, dicts, objects defined with __getitem__, and
! xrange objects. Generators are not the only objects which are not
! restartable. Other examples of non-restartable sequences include file
! objects, xreadlines objects, and the result of iter(callable,sentinel).
!
! Since the proposed built-in functions return generators, they are also
! non-restartable. As a result, 'xmap' is not substitutable for 'map' in
! the following example:
!
! alphabet = map(chr, xrange(ord('a'), ord('z')+1))
! twoletterwords = [a+b for a in alphabet for b in alphabet]
!
! Since generator comprehensions also return generators, they are not
! restartable. Consequently, they are not substitutable for list
! comprehensions in the following example:
!
! digits = [str(i) for i in xrange(10)]
! alphadig = [a+d for a in 'abcdefg' for d in digits]
!
! To achieve substitutabity, generator comprehensions and x-functions
! can be implemented in a way that supports restarts. PEP 234 [4]
! explicitly states that restarts are to be supported through repeated
! calls to iter(). With that guidance, it is easy to add restartability
! to generator comprehensions using a simple wrapper class around the
! generator function and modifying the implementation above to return:
!
! g = Restartable(__temp) # instead of g = __temp()
!
! Restartable is a simple (12 line) class which calls the generator function
! to create a new, re-wound generator whenever iter() requests a restart.
! Calls to .next() are simply forwarded to the generator. The Python source
! code for the Restartable class can found in the PEP 279 simulator [8].
! An actual implementation in C can achieve re-startability directly and
! would not need the slow class wrapper used in the pure Python simulation.
!
! The XLazy library [10] shows how restarts can be implemented for xmap,
! xfilter, and xzip.
!
! The upside of adding restart capability is that more list comprehensions
! can be made lazy and save memory by adding 'yield'. Likewise,
! more expressions that use map, filter, and zip can be made lazy just by
! adding 'x'.
! A possible downside is that x-functions have no control over whether their
! inputs are themselves restartable. With non-restartable inputs like
! generators or files, an x-function restart will not produce a meaningful
! result.
References
--- 440,490 ----
+ Commentary from GvR: We discussed this at length when we were hashing
+ out generators and coroutines, and found that there's always a problem
+ with this: the argument to the first next() call has to be thrown away,
+ because it doesn't correspond to a yield statement. This looks ugly
+ (note that the example code has a dummy call to next() to get the
+ generator going). But there may be useful examples that can only be
+ programmed (elegantly) with this feature, so I'm reserving judgment.
+ I can believe that it's easy to implement.
! Commentary from Ka-Ping Yee: I also think there is a lot of power to be
! gained from generator argument passing.
! Commentary from Neil Schemenauer: I like the idea of being able to pass
! values back into a generator. I originally pitched this idea to Guido
! but in the end we decided against it (at least for the initial
! implementation). There was a few issues to work out but I can't seem
! to remember what they were. My feeling is that we need to wait until
! the Python community has more experience with generators before adding
! this feature. Maybe for 2.4 but not for 2.3. In the mean time you
! can work around this limitation by making your generator a method.
! Values can be passed back by mutating the instance.
! Author response: Okay, consider this part of the proposal deferred
! until 2.4.
+ Restartability
! [Discussion of restartability deleted]
! Commentary from GvR: The PEP then goes on to discuss restartable
! iterators. I think this is an evil idea obtained from reading too
! much about C++ STL iterators. It should definitely be a separate
! PEP if the author wants me to take this seriously.
! Commentary from Ka-Ping Yee: I have less of an opinion on restartability
! since i have not yet had to really run into that issue. It seems
! reasonable that it might be good idea, though perhaps YAGNI will apply
! here until I experience the need for it first-hand.
+ Author response: Over thirty reviewers responded, only one was interested
+ in restartability on the theory that it made life easier for beginners
+ and that it made lazy evaluation more substitutable for full
+ evaluation. I was never sold on it myself. Consider it retracted.
+
References
***************
*** 477,496 ****
http://gnosis.cx/publish/programming/charming_python_b5.txt
! [6] The code fragment for xmap() was found at:
! http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66448
!
! [7] PIL, the Python Imaging Library can be found at:
http://www.pythonware.com/products/pil/
! [8] A pure Python simulation of every feature in this PEP is at:
http://sourceforge.net/tracker/download.php?group_id=5470&atid=305470&file_id=17348&aid=513752
! [9] The full, working source code for each of the examples in this PEP
along with other examples and tests is at:
http://sourceforge.net/tracker/download.php?group_id=5470&atid=305470&file_id=17412&aid=513756
! [10] Oren Tirosh's XLazy library with re-startable x-functions is at:
! http://www.tothink.com/python/dataflow/
!
Copyright
--- 505,519 ----
http://gnosis.cx/publish/programming/charming_python_b5.txt
! [6] PIL, the Python Imaging Library can be found at:
http://www.pythonware.com/products/pil/
! [7] A pure Python simulation of every feature in this PEP is at:
http://sourceforge.net/tracker/download.php?group_id=5470&atid=305470&file_id=17348&aid=513752
! [8] The full, working source code for each of the examples in this PEP
along with other examples and tests is at:
http://sourceforge.net/tracker/download.php?group_id=5470&atid=305470&file_id=17412&aid=513756
!
Copyright