[Python-checkins] python/nondist/peps pep-0326.txt, 1.1, 1.2 pep-0000.txt, 1.261, 1.262

Tue Jan 6 10:34:51 EST 2004

Update of /cvsroot/python/python/nondist/peps
In directory sc8-pr-cvs1:/tmp/cvs-serv24252
Modified Files:
	pep-0326.txt pep-0000.txt 
Log Message:
updates from Josiah Carlson, edited
Index: pep-0326.txt
===================================================================
RCS file: /cvsroot/python/python/nondist/peps/pep-0326.txt,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** pep-0326.txt	4 Jan 2004 17:30:47 -0000	1.1
--- pep-0326.txt	6 Jan 2004 15:34:49 -0000	1.2
***************
*** 1,7 ****
 PEP: 326
! Title: A Case for All
 Version: $Revision$
 Last-Modified: $Date$
! Author: Josiah Carlson <jcarlson at uci.edu>
 Status: Draft
 Type: Standards Track
--- 1,8 ----
 PEP: 326
! Title: A Case for Top and Bottom Values
 Version: $Revision$
 Last-Modified: $Date$
! Author: Josiah Carlson <jcarlson at uci.edu>,
! Terry Reedy <tjreedy at udel.edu>
 Status: Draft
 Type: Standards Track
***************
*** 9,13 ****
 Created: 20-Dec-2003
 Python-Version: 2.4
! Post-History: 20-Dec-2003, 03-Jan-2004

--- 10,14 ----
 Created: 20-Dec-2003
 Python-Version: 2.4
! Post-History: 20-Dec-2003, 03-Jan-2004, 05-Jan-2004

***************
*** 15,25 ****
 ========

! This PEP proposes a new named constant or built-in: ``All``.

! Users of Python have had the constant None, which represents a lack of
! value, for quite some time (possibly from the beginning, this is
! unknown to the author at the current time). The author believes that
! ``All`` should be introduced in order to represent a functionally
! infinite value, with similar behavior corresponding to None.

--- 16,28 ----
 ========

! This PEP proposes two new attributes to the ``cmp`` built-in that
! represent a top and bottom [4]_ value: ``high`` and ``low`` (or a pair
! of similarly named attributes [5]_).

! As suggested by their names, ``cmp.high`` and ``cmp.low`` would
! compare higher or lower than any other object (respectively). Such
! behavior results in easier to understand code and fewer special cases
! in which a temporary minimum or maximum is required, and an actual
! minimum or maximum numeric value is not limited.

***************
*** 27,70 ****
 =========

! While None can be used as an absolute minimum that any value can
! attain [1]_, there does not exist an equivalent absolute maximum. For
! example::
! 
! >>> print min(None, -2**1000)
! None

! All comparisons including None and another object results in None 
! being the smaller of the two. 

! However, there does not exist a value such that the comparison of any
! other object results in the constant being the larger of the two.
! What is commonly done to deal with such cases, is to set a value in a
! script that is larger than the author ever expects the input to reach,
! and hope that it isn't reached.

 Guido has brought up [2]_ the fact that there exists two constants
! that can be used in the interim: sys.maxint and floating point
! positive infinity (1e309 will evaluate to positive infinity).
! However, each has their drawbacks. On most architectures sys.maxint
! is arbitrarily small (2**31-1 or 2**63-1), and can be easily eclipsed
! by large 'long' integers or floating point numbers. Furthermore,
! comparing long integers larger than the largest floating point number
! representable against any float will result in an exception being
! raised::

! >>> cmp(1.0, 10**309)
! Traceback (most recent call last):
! File "<stdin>", line 1, in ?
! OverflowError: long int too large to convert to float

! Even when large integers are compared against positive infinity::

! >>> cmp(1e309, 10**309)
! Traceback (most recent call last):
! File "<stdin>", line 1, in ?
! OverflowError: long int too large to convert to float

! Introducing an ``All`` built-in that works as described does not take
! much effort. A sample Python implementation is included.

--- 30,76 ----
 =========

! While ``None`` can be used as an absolute minimum that any value can
! attain [1]_, this may be depreciated [5]_ in Python 3.0, and shouldn't
! be relied upon.

! As a replacement for ``None`` being used as an absolute minimum, as
! well as the introduction of an absolute maximum, attaching ``low`` and
! ``high`` to ``cmp`` addresses concerns for namespace pollution and
! serves to make both self-documenting.

! What is commonly done to deal with absolute minimum or maximum values,
! is to set a value that is larger than the script author ever expects
! the input to reach, and hope that it isn't reached.

 Guido has brought up [2]_ the fact that there exists two constants
! that can be used in the interim for maximum values: sys.maxint and
! floating point positive infinity (1e309 will evaluate to positive
! infinity). However, each has their drawbacks.

! - On most architectures sys.maxint is arbitrarily small (2**31-1 or
! 2**63-1) and can be easily eclipsed by large 'long' integers or
! floating point numbers.

! - Comparing long integers larger than the largest floating point
! number representable against any float will result in an exception
! being raised::

! >>> cmp(1.0, 10**309)
! Traceback (most recent call last):
! File "<stdin>", line 1, in ?
! OverflowError: long int too large to convert to float

! Even when large integers are compared against positive infinity::
! 
! >>> cmp(1e309, 10**309)
! Traceback (most recent call last):
! File "<stdin>", line 1, in ?
! OverflowError: long int too large to convert to float
! 
! - These same drawbacks exist when numbers are small.
! 
! Introducing ``high`` and ``low`` attributes to ``cmp`` that work as
! described does not take much effort. A sample Python `reference
! implementation`_ of both attributes is included.

***************
*** 72,81 ****
 ==========

 There are hundreds of algorithms that begin by initializing some set
! of values to a logical (or numeric) infinity. Python lacks a positive
! infinity that works consistently or really is the largest value that
! can be attained. By adding the ``All`` constant (or built-in), Python
! would have a real maximum value, and such algorithms can become
! clearer due to the reduction of special cases.

 Take for example, finding the minimum in a sequence::
--- 78,91 ----
 ==========

+ ``cmp.high`` Examples
+ ---------------------
+ 
 There are hundreds of algorithms that begin by initializing some set
! of values to a logical (or numeric) infinity or negative infinity.
! Python lacks either infinity that works consistently or really is the
! most extreme value that can be attained. By adding the ``cmp.high``
! and ``cmp.low`` attributes, Python would have a real maximum and
! minimum value, and such algorithms can become clearer due to the
! reduction of special cases.

 Take for example, finding the minimum in a sequence::
***************
*** 92,95 ****
--- 102,107 ----
 return cur

+ ::
+ 
 def findmin_None(seq):
 cur = None
***************
*** 100,110 ****
 return cur
 return cur
! 
! def findmin_All(seq):
! cur = All
 for obj in seq:
 cur = min(obj, cur)
 return cur

 Guido brought up the idea of just negating everything and comparing
 [2]_. Certainly this does work when using numbers, but it does not
--- 112,129 ----
 return cur
 return cur
! 
! ::
! 
! def findmin_high(seq):
! cur = cmp.high
 for obj in seq:
 cur = min(obj, cur)
 return cur

+ Please note that there are an arbitrarily large number of ways to find
+ the minimum (or maximum) of a sequence, these seek to show a simple
+ example where using ``cmp.high`` makes the algorithm easier to
+ understand and results in simplification of code.
+ 
 Guido brought up the idea of just negating everything and comparing
 [2]_. Certainly this does work when using numbers, but it does not
***************
*** 112,119 ****
 being less readable. ::

! #we have All available
 a = min(a, b)

! #we don't have All available
 if a is not None:
 if b is None:
--- 131,138 ----
 being less readable. ::

! #we have cmp.high available
 a = min(a, b)

! #we don't have cmp.high available
 if a is not None:
 if b is None:
***************
*** 122,132 ****
 a = -max(-a, -b)

! Implementation
! ==============

 ::

! class _AllType(object):

 def __cmp__(self, other):
--- 141,321 ----
 a = -max(-a, -b)

+ As another example, in Dijkstra's shortest path algorithm on a graph
+ with weighted edges (all positive).

! 1. Set distances to every node in the graph to infinity.
! 2. Set the distance to the start node to zero.
! 3. Set visited to be an empty mapping.
! 4. While shortest distance of a node that has not been visited is less
! than infinity and the destination has not been visited.
! 
! a. Get the node with the shortest distance.
! b. Visit the node.
! c. Update neighbor distances and parent pointers if necessary for
! neighbors that have not been visited.
! 
! 5. If the destination has been visited, step back through parent
! pointers to find the reverse of the path to be taken.
! 
! To be complete, below are two versions of the algorithm, one using a
! table (a bit more understandable) and one using a heap (much faster)::
! 
! def DijkstraSP_table(graph, S, T):
! #runs in O(N^2) time using a table
! #find the shortest path
! table = {}
! for node in graph.iterkeys():
! #(visited, distance, node, parent)
! table[node] = (0, cmp.high, node, None)
! table[S] = (0, 0, S, None)
! cur = min(table.values())
! while (not cur[0]) and cur[1] < cmp.high:
! (visited, distance, node, parent) = cur
! table[node] = (1, distance, node, parent)
! for cdist, child in graph[node]:
! ndist = distance+cdist
! if not table[child][0] and ndist < table[child][1]:
! table[child] = (0, ndist, child, node)
! cur = min(table.values())
! #backtrace through results
! if not table[T][0]:
! return None
! cur = T
! path = [T]
! while table[cur][3] is not None:
! path.append(table[cur][3])
! cur = path[-1]
! path.reverse()
! return path

 ::

! def DijkstraSP_heap(graph, S, T):
! #runs in O(NlgN) time using a minheap
! #find the shortest path
! import heapq
! Q = [(cmp.high, i, None) for i in graph.iterkeys()]
! heapq.heappush(Q, (0, S, None))
! V = {}
! while Q[0][0] < cmp.high and T not in V:
! dist, node, parent = heapq.heappop(Q)
! if node in V:
! continue
! V[node] = (dist, parent)
! for next, dest in graph[node]:
! heapq.heappush(Q, (next+dist, dest, node))
! #backtrace through results
! if T not in V:
! return None
! cur = T
! path = [T]
! while V[cur][1] is not None:
! path.append(V[cur][1])
! cur = path[-1]
! path.reverse()
! return path
! 
! Readers should note that replacing ``cmp.high`` in the above code with
! an arbitrarily large number does not guarantee that the actual
! distance to a node will never exceed that number. Well, with one
! caveat: one could certainly sum up the weights of every edge in the
! graph, and set the 'arbitrarily large number' to that total. However,
! doing so does not make the algorithm any easier to understand and has
! potential problems with various numeric overflows.
! 
! 
! A ``cmp.low`` Example
! ---------------------
! 
! An example of usage for ``cmp.low`` is an algorithm that solves the
! following problem [7]_:
! 
! Suppose you are given a directed graph, representing a
! communication network. The vertices are the nodes in the network,
! and each edge is a communication channel. Each edge ``(u, v)`` has
! an associated value ``r(u, v)``, with ``0 <= r(u, v) <= 1``, which
! represents the reliability of the channel from ``u`` to ``v``
! (i.e., the probability that the channel from ``u`` to ``v`` will
! **not** fail). Assume that the reliability probabilities of the
! channels are independent. (This implies that the reliability of
! any path is the product of the reliability of the edges along the
! path.) Now suppose you are given two nodes in the graph, ``A``
! and ``B``.
! 
! Such an algorithm is a 7 line modification to the DijkstraSP_table
! algorithm given above::
! 
! #only showing the changed to lines with the proper indentation
! table[node] = (0, cmp.low, node, None)
! table[S] = (0, 1, S, None)
! cur = max(table.values())
! while (not cur[0]) and cur[1] > cmp.low:
! ndist = distance*cdist
! if not table[child][0] and ndist > table[child][1]:
! cur = max(table.values())
! 
! Or a 6 line modification to the DijkstraSP_heap algorithm given above
! (if we assume that ``maxheapq`` exists and does what it is supposed
! to)::
! 
! #only showing the changed to lines with the proper indentation
! import maxheapq
! Q = [(cmp.low, i, None) for i in graph.iterkeys()]
! maxheapq.heappush(Q, (1, S, None))
! while Q[0][0] > cmp.low and T not in V:
! dist, node, parent = maxheapq.heappop(Q)
! maxheapq.heappush(Q, (next*dist, dest, node))
! 
! Note that there is an equivalent way of translating the graph to
! produce something that can be passed unchanged into the original
! Dijkstra shortest path algorithm.
! 
! Further usage examples of both ``cmp.high`` and ``cmp.low`` are
! available in the realm of graph algorithms.
! 
! 
! Independent Implementations?
! ----------------------------
! 
! Independent implementations of the top/bottom concept by users
! desiring such functionality are not likely to be compatible, and
! certainly will be inconsistent. The following examples seek to show
! how inconsistent they can be.
! 
! - Let us pretend we have created proper separate implementations of
! Myhigh, Mylow, Yourhigh and Yourlow with the same code as given in
! the sample implementation (with some minor renaming)::
! 
! >>> lst = [Yourlow, Mylow, Mylow, Yourlow, Myhigh, Yourlow,
! Myhigh, Yourhigh, Myhigh]
! >>> lst.sort()
! >>> lst
! [Yourlow, Yourlow, Mylow, Mylow, Yourlow, Myhigh, Myhigh,
! Yourhigh, Myhigh]
! 
! Notice that while all the "low"s are before the "high"s, there is no
! guarantee that all instances of Yourlow will come before Mylow, the
! reverse, or the equivalent Myhigh and Yourhigh.
! 
! - The problem is evident even when using the heapq module::
! 
! >>> lst = [Yourlow, Mylow, Mylow, Yourlow, Myhigh, Yourlow,
! Myhigh, Yourhigh, Myhigh]
! >>> heapq.heapify(lst) #not needed, but it can't hurt
! >>> while lst: print heapq.heappop(lst),
! ...
! Yourlow Mylow Yourlow Yourlow Mylow Myhigh Myhigh Yourhigh Myhigh
! 
! - Furthermore, the findmin_high code and both versions of Dijkstra
! could result in incorrect output by passing in secondary versions of
! high.
! 
! 
! Reference Implementation
! ========================
! 
! ::
! 
! class _HighType(object):

 def __cmp__(self, other):
***************
*** 136,163 ****

 def __repr__(self):
! return 'All'

! import sys
! sys.modules['__builtin__'].All = _AllType()

! Results of Test Run in Python 2.3.3::

! >>> max(All, 2**65536)
! All
! >>> min(All, 2**65536)
 20035299304068464649790...
 (lines removed for brevity)
 ...72339445587895905719156736L
! >>> max(All, None)
! All
! >>> min(All, None)
! >>> print min(All, None)
! None
! >>> bool(All)
! True
! >>> not None
! 1
! >>> not All
! 0

--- 325,359 ----

 def __repr__(self):
! return 'cmp.high'

! class _LowType(object):

! def __cmp__(self, other):
! if isinstance(other, self.__class__):
! return 0
! return -1

! def __repr__(self):
! return 'cmp.low'
! 
! # please note that the following code doesn't
! # work due to built-ins being read-only
! cmp.high = _HighType()
! cmp.low = _LowType()
! 
! Results of Test Run if we could set cmp.high and cmp.low::
! 
! >>> max(cmp.high, 2**65536)
! cmp.high
! >>> min(cmp.high, 2**65536)
 20035299304068464649790...
 (lines removed for brevity)
 ...72339445587895905719156736L
! >>> min(cmp.low, -2**65536)
! cmp.low
! >>> max(cmp.low, -2**65536)
! -2003529930406846464979...
! (lines removed for brevity)
! ...072339445587895905719156736L

***************
*** 165,171 ****
 ===========

! ``All`` seemed to be an awkward object to various Python developers on
! the python-dev mailing list. The author hopes that with this updated
! PEP, developers will no longer find ``All`` awkward.

--- 361,424 ----
 ===========

! - Previously, ``Some`` and ``All`` were names for the idea that
! ``cmp.high`` now represents. They have been subsumed by
! ``cmp.high`` due to the relative ambiguity of ``Some`` and ``All``.
! 
! - Terry Reedy [5]_ and others have offered alternate names for the
! ``high/low`` objects: ``ObjHi/ObjLo``, ``NoneHi/NoneLo``,
! ``Highest/Lowest``, ``Infinity/NegativeInfinity``, ``hi/lo`` and
! ``High/Low``.
! 
! - Terry Reedy has also offered possible default behaviors of ``min``
! and ``max`` on empty lists using these values. Some have voiced
! that changing the behavior of min and max are not desirable due to
! the amount of code that actively uses min and max, which may rely on
! min and max raising exceptions on empty lists.
! 
! - Choosing ``high`` and ``low`` to be the attributes of ``cmp`` is
! arbitrary, but meaningful. Other meaningful parent locations
! include, but are not limited to: ``math``, ``int`` and ``number``
! (if such a numeric superclass existed). ``sys`` probably does not
! make sense, as such maximum and minimum values are not platform
! dependent.
! 
! - The base class of the high and low objects do not necessarily have
! to be ``object``. ``object``, ``NoneType`` or even a new class
! called ``cmp.extreme`` have been suggested.
! 
! - Various built-in names such as ``All`` and ``Some`` have been
! rejected by many users. Based on comments, it seems that regardless
! of name, any new built-in would be rejected. [6]_
! 
! - Should ``-cmp.high == cmp.low``? This seems to make logical sense.
! 
! - Certainly ``bool(cmp.high) == True``, but should ``bool(cmp.low)``
! be ``True`` or ``False``? Due to ``bool(1) == bool(-1) == True``,
! it seems to follow that ``bool(cmp.high) == bool(cmp.low) == True``.
! 
! - Whatever name the concepts of a top and bottom value come to have,
! the question of whether or not math can be done on them may or may
! not make sense. If math were not allowed, it brings up a potential
! ambiguity that while ``-cmp.high == cmp.low``, ``-1 * cmp.high``
! would produce an exception.
! 
! 
! Most-Preferred Options
! ======================
! 
! Through a non-rigorous method, the following behavior of the objects
! seem to be preferred by those who are generally in favor of this PEP
! in python-dev.
! 
! - ``high`` and ``low`` objects should be attached to the ``cmp``
! built-in as ``cmp.high`` and ``cmp.low`` (or ``cmp.High/cmp.Low``).
! 
! - ``-cmp.high == cmp.low`` and equivalently ``-cmp.low == cmp.high``.
! 
! - ``bool(cmp.high) == bool(cmp.low) == True``
! 
! - The base type seems to be a cosmetic issue and has not resulted in
! any real preference other than ``cmp.extreme`` making the most
! sense.

***************
*** 182,204 ****
 (http://mail.python.org/pipermail/python-dev/2003-December/041337.html)

 Changes
 =======

! Added this section.

! Renamed ``Some`` to ``All``: Some was an arbitrary name that suffered
! from being unclear. [3]_

! Made ``All`` a subclass of object in order for it to become a new
! style class.

! Removed mathematical negation and casting to float in Open Issues.
! None is not a number and is not treated as one, ``All`` shouldn't be
! either.

! Added Motivation section.

! Changed markup to reStructuredText.

--- 435,490 ----
 (http://mail.python.org/pipermail/python-dev/2003-December/041337.html)

+ .. [4] RE: [Python-Dev] Got None. Maybe Some?, Peters, Tim
+ (http://mail.python.org/pipermail/python-dev/2003-December/041332.html)
+ 
+ .. [5] [Python-Dev] Re: PEP 326 now online, Reedy, Terry
+ (http://mail.python.org/pipermail/python-dev/2004-January/041685.html)
+ 
+ .. [6] [Python-Dev] PEP 326 now online, Chermside, Michael
+ (http://mail.python.org/pipermail/python-dev/2004-January/041704.html)
+ 
+ .. [7] Homework 6, Problem 7, Dillencourt, Michael
+ (link may not be valid in the future)
+ (http://www.ics.uci.edu/~dillenco/ics161/hw/hw6.pdf)
+ 

 Changes
 =======

! - Added this section.

! - Renamed ``Some`` to ``All``: "Some" was an arbitrary name that
! suffered from being unclear. [3]_

! - Made ``All`` a subclass of ``object`` in order for it to become a
! new-style class.

! - Removed mathematical negation and casting to float in Open Issues.
! ``None`` is not a number and is not treated as one, ``All``
! shouldn't be either.

! - Added Motivation_ section.

! - Changed markup to reStructuredText.
! 
! - Renamed ``All`` to ``cmp.hi`` to remove builtin requirement and to
! provide a better better name, as well as adding an equivalent
! future-proof bottom value ``cmp.lo``. [5]_
! 
! - Clarified Abstract_, Motivation_, `Reference Implementation`_ and
! `Open Issues`_ based on the simultaneous concepts of ``cmp.hi`` and
! ``cmp.lo``.
! 
! - Added two implementations of Dijkstra's Shortest Path algorithm that
! show where ``cmp.hi`` can be used to remove special cases.
! 
! - Renamed ``hi`` to ``high`` and ``lo`` to ``low`` to address concerns
! for non-native english speakers.
! 
! - Added an example of use for ``cmp.low`` to Motivation_.
! 
! - Added a couple `Open Issues`_ and clarified some others.
! 
! - Added `Most-Preferred Options`_ section.

***************
*** 214,217 ****
 indent-tabs-mode: nil
 sentence-end-double-space: t
! fill-column: 74
 End:
--- 500,503 ----
 indent-tabs-mode: nil
 sentence-end-double-space: t
! fill-column: 70
 End:
Index: pep-0000.txt
===================================================================
RCS file: /cvsroot/python/python/nondist/peps/pep-0000.txt,v
retrieving revision 1.261
retrieving revision 1.262
diff -C2 -d -r1.261 -r1.262
*** pep-0000.txt	4 Jan 2004 17:30:47 -0000	1.261
--- pep-0000.txt	6 Jan 2004 15:34:49 -0000	1.262
***************
*** 122,126 ****
 S 324 popen5 - New POSIX process module Astrand
 S 325 Resource-Release Support for Generators Pedroni
! S 326 A Case for All Carlson
 S 754 IEEE 754 Floating Point Special Values Warnes

--- 122,126 ----
 S 324 popen5 - New POSIX process module Astrand
 S 325 Resource-Release Support for Generators Pedroni
! S 326 A Case for Top and Bottom Values Carlson
 S 754 IEEE 754 Floating Point Special Values Warnes

***************
*** 345,349 ****
 S 324 popen5 - New POSIX process module Astrand
 S 325 Resource-Release Support for Generators Pedroni
! S 326 A Case for All Carlson
 SR 666 Reject Foolish Indentation Creighton
 S 754 IEEE 754 Floating Point Special Values Warnes
--- 345,349 ----
 S 324 popen5 - New POSIX process module Astrand
 S 325 Resource-Release Support for Generators Pedroni
! S 326 A Case for Top and Bottom Values Carlson
 SR 666 Reject Foolish Indentation Creighton
 S 754 IEEE 754 Floating Point Special Values Warnes