[Python-checkins] r54986 - peps/trunk/pep-3119.txt
guido.van.rossum
python-checkins at python.org
Thu Apr 26 20:24:12 CEST 2007
Author: guido.van.rossum
Date: Thu Apr 26 20:24:07 2007
New Revision: 54986
Modified:
peps/trunk/pep-3119.txt
Log:
Deal with some open issues. Add some others. Will be posting soon.
Modified: peps/trunk/pep-3119.txt
==============================================================================
--- peps/trunk/pep-3119.txt (original)
+++ peps/trunk/pep-3119.txt Thu Apr 26 20:24:07 2007
@@ -7,7 +7,7 @@
Type: Standards Track
Content-Type: text/x-rst
Created: 18-Apr-2007
-Post-History: Not yet posted
+Post-History: 26-Apr-2007
Abstract
@@ -213,19 +213,18 @@
``PartiallyOrdered``
This ABC defines the 4 inequality operations ``<``, ``<=``, ``>=``,
``>``. (Note that ``==`` and ``!=`` are defined by ``object``.)
- Classes deriving from this ABC should satisfy weak invariants such
- as ``a < b < c`` implies ``a < c`` but don't require that for any
- two instances ``x`` and ``y`` exactly one of ``x < y``, ``x == y``
- or ``x >= y`` apply.
+ Classes deriving from this ABC should implement a partial order
+ as defined in mathematics. [9]_
``TotallyOrdered``
This ABC derives from ``PartiallyOrdered``. It adds no new
- operations but implies a promise of stronger invariants. **Open
- issues:** Should ``float`` derive from ``TotallyOrdered`` even
- though for ``NaN`` this isn't strictly correct?
+ operations but implies a promise of stronger invariants.
+ Classes deriving from this ABC should implement a total order
+ as defined in mathematics. [10]_
**Open issues:** Where should these live? The ``collections`` module
-doesn't seem right.
+doesn't seem right, but making them built-ins seems a slippery slope
+too.
One Trick Ponies
@@ -252,7 +251,7 @@
instances only, ``__hash__`` for those instances should raise a
``TypeError`` exception.
- Note: being an instance of this class does not imply that an
+ **Note:** being an instance of this class does not imply that an
object is immutable; e.g. a tuple containing a list as a member is
not immutable; its ``__hash__`` method raises ``TypeError``.
@@ -266,7 +265,7 @@
The base class for classes defining ``__next__``. This derives
from ``Iterable``. The abstract ``__next__`` method raises
``StopIteration``. The concrete ``__iter__`` method returns
- ``self``. (Note: this assumes PEP 3114 is implemented.)
+ ``self``.
``Sized``
The base class for classes defining ``__len__``. The ``__len__``
@@ -274,13 +273,7 @@
The abstract ``__len__`` method returns 0. **Invariant:** If a
class ``C`` derives from ``Sized`` as well as from ``Iterable``,
the invariant ``sum(1 for x in o) == len(o)`` should hold for any
- instance ``o`` of ``C``. **Open issues:** Is ``Sized`` the best
- name? Proposed alternatives already tentatively rejected:
- ``Finite`` (nobody understood it), ``Lengthy``, ``Sizeable`` (both
- too cute), ``Countable`` (the set of natural numbers is a
- countable set in math), ``Enumerable`` (sounds like a sysnonym for
- ``Iterable``), ``Dimension``, ``Extent`` (sound like numbers to
- me), ``Bounded`` (probably just as confusing as ``Fininte``).
+ instance ``o`` of ``C``.
``Container``
The base class for classes defining ``__contains__``. The
@@ -290,7 +283,7 @@
``Iterable``, then ``(x in o for x in o)`` should be a generator
yielding only True values for any instance ``o`` of ``C``.
- Note: strictly speaking, there are three variants of this method's
+ **Note:** strictly speaking, there are three variants of this method's
semantics. The first one is for sets and mappings, which is fast:
O(1) or O(log N). The second one is for membership checking on
sequences, which is slow: O(N). The third one is for subsequence
@@ -337,25 +330,31 @@
a set though! Sets have the additional invariant that each
element occurs only once (as can be determined by iteration), and
in addition sets define concrete operators that implement the
- inequality operations as subclass/superclass tests.
+ inequality operations as subclass/superclass tests. In general,
+ the invariants for finite sets in mathematics hold. [11]_
Sets with different implementations can be compared safely,
- efficiently and correctly. Because ``Set`` derives from
- ``Sized``, ``__eq__`` takes a shortcut and returns ``False``
- immediately if two sets of unequal length are compared.
- Similarly, ``__le__`` returns ``False`` immediately if the first
- set has more members than the second set. Note that set inclusion
- implements only a partial ordering; e.g. ``{1, 2}`` and ``{1, 3}``
- are not ordered (all three of ``<``, ``==`` and ``>`` return
- ``False`` for these arguments). Sets cannot be ordered relative
- to mappings or sequences, but they can be compared for equality
- (and then they always compare unequal).
+ (usually) efficiently and correctly using the mathematical
+ definitions of the subclass/superclass operations for finite sets.
+ The ordering operations have concrete implementations; subclasses
+ may override these for speed but should maintain the semantics.
+ Because ``Set`` derives from ``Sized``, ``__eq__`` may take a
+ shortcut and returns ``False`` immediately if two sets of unequal
+ length are compared. Similarly, ``__le__`` may return ``False``
+ immediately if the first set has more members than the second set.
+ Note that set inclusion implements only a partial ordering;
+ e.g. ``{1, 2}`` and ``{1, 3}`` are not ordered (all three of
+ ``<``, ``==`` and ``>`` return ``False`` for these arguments).
+ Sets cannot be ordered relative to mappings or sequences, but they
+ can be compared to those for equality (and then they always
+ compare unequal).
- Note: the ``issubset`` and ``issuperset`` methods found on the set
- type in Python 2 are not supported, as these are mostly just
+ **Note:** the ``issubset`` and ``issuperset`` methods found on the
+ set type in Python 2 are not supported, as these are mostly just
aliases for ``__le__`` and ``__ge__``.
- **Open issues:** Spell out the invariants and method definitions.
+ **Open issues:** should we define comparison of instances of
+ different concrete set types this way?
``ComposableSet``
This is a subclass of ``Set`` that defines abstract operators to
@@ -366,14 +365,22 @@
``NotImplementedError``; this is because any generic
implementation would have to create new instances but the ABCs
don't (and shouldn't, IMO) provide an API for creating new
- instances. **Invariants:** The implementations of these operators
- should ensure that the results match the mathematical definition
- of set composition.
-
- **Open issues:** Should I spell out the invariants? Should we
- define an API for creating new instances (e.g. a class method or a
- fixed constructor signature)? Should we just pick a concrete
- return type (e.g. ``set``)?
+ instances. The implementations of these operators should ensure
+ that the results match the mathematical definition of set
+ composition. [11]_
+
+ **Open issues:** Should ``__or__`` and friends be abstract or
+ concrete methods? Making them abstract means that every
+ ComposableSet implementation must reimplement all of them. But
+ making them concrete begs the question of the actual return type:
+ since the ABC doesn't (and IMO shouldn't) define the constructor
+ signature for subclasses, the concrete implementations in the ABC
+ don't have an API to construct a new instance given an iterable.
+ Perhaps the right choice is to have a static concrete factory
+ function ``fromiterable`` which takes an iterable and returns
+ a ``ComposableSet`` instance. Subclasses can override this and
+ benefit from the default implementations of ``__or__`` etc.; or
+ they can override ``__or__`` if they want to.
``HashableSet``
This is a subclass of both ``ComposableSet`` and ``Hashable``. It
@@ -385,8 +392,8 @@
values for different types of numbers and strings.)
**Open issues:** Spell out the hash algorithm. Should there be
- another ABC that derives from Set and Hashable (but not from
- Composable)?
+ another ABC that derives from Set and Hashable, but not from
+ Composable?
``MutableSet``
This is a subclass of ``ComposableSet`` implementing additional
@@ -421,7 +428,7 @@
``.clear()``
Concrete method that empties the set. The default
implementation repeatedly calls ``self.pop()`` until
- ``KeyError`` is caught. (Note: this is probably much slower
+ ``KeyError`` is caught. (**Note:** this is likely much slower
than simply creating a new set, even if an implementation
overrides it with a faster approach; but in some cases object
identity is important.)
@@ -467,21 +474,52 @@
raise ``KeyError``, and ``False`` if it does.
``Mapping``
- A subclass of ``BasicMapping``, ``iterable`` and ``Sized``. It
- defines concrete methods ``__eq__``, ``keys``, ``items``,
- ``values``. Iterating over a mapping should return all the valid
- keys (i.e. those keys for which ``.__getitem__()`` returns a
- value), once each, and nothing else. The lengh of a mapping
- should equal to the number of elements returned by iterating over
- the object until the end of the iterator is reached (this is
- implied by the invariant listed above for ``Sized``). Two
- mappings, even with different implementations, can be compared for
- equality, and are considered equal if and only iff their items
- compare equal when converted to sets. The ``keys``, ``items`` and
- ``values`` methods return views; ``keys`` and ``items`` return
- ``Set`` views, ``values`` returns a ``Container`` view. The
- following invariant should hold: m.items() == set(zip(m.keys(),
- m.values())).
+ A subclass of ``BasicMapping``, ``Iterable`` and ``Sized``. The
+ keys of a mapping naturally form a set. The (key, value) pairs
+ are also referred to as items. The items also form a set.
+ Methods:
+
+ ``__len__``
+ Abstract method returning the length of the key set.
+
+ ``__iter__``
+ Abstract method returning each key in the key set exactly once.
+
+ ``__eq__``
+ Concrete method for comparing mappings. Two mappings, even
+ with different implementations, can be compared for equality,
+ and are considered equal if and only iff their item sets are
+ equal. **Open issues:** should we define comparison of
+ instances of different concrete mapping types this way?
+
+ ``keys``
+ Concrete method returning the key set as a ``Set``. The
+ default concrete implementation returns a "view" on the key
+ set (meaning if the underlying mapping is modified, the view's
+ value changes correspondingly); subclasses are not required to
+ return a view but they should return a ``Set``.
+
+ ``items``
+ Concrete method returning the items as a ``Set``. The default
+ concrete implementation returns a "view" on the item set;
+ subclasses are not required to return a view but they should
+ return a ``Set``.
+
+ ``values``
+ Concrete method returning the values as a sized, iterable
+ container (not a set!). The default concrete implementation
+ returns a "view" on the values of the mapping; subclasses are
+ not required to return a view but they should return a sized,
+ iterable container.
+
+ The following invariant should hold for any mapping ``m``::
+
+ set(m.items()) == set(zip(m.keys(), m.values()))
+
+ i.e. iterating over the keys and the values in parallel should
+ return *corresponding* keys and values. **Open issues:** Should
+ this always be required? How about the stronger invariant using
+ ``list()`` instead of ``set()``?
``HashableMapping``
A subclass of ``Mapping`` and ``Hashable``. The values should be
@@ -492,11 +530,8 @@
A subclass of ``Mapping`` that also implements some standard
mutating methods. Abstract methods include ``__setitem__``,
``__delitem__``. Concrete methods include ``pop``, ``popitem``,
- ``clear``, ``update``. Note: ``setdefault`` is *not* included.
-
-**Open issues:**
-
-* We should say more about mapping view types.
+ ``clear``, ``update``. **Note:** ``setdefault`` is *not* included.
+ **Open issues:** Write out the specs for the methods.
Sequences
@@ -510,7 +545,7 @@
``Sequence``
A subclass of ``Iterable``, ``Sized``, ``Container``. It
- defines a new abstract method ``__getitem__`` that has a
+ defines a new abstract method ``__getitem__`` that has a somewhat
complicated signature: when called with an integer, it returns an
element of the sequence or raises ``IndexError``; when called with
a ``slice`` object, it returns another ``Sequence``. The concrete
@@ -535,10 +570,19 @@
well as slices), ``__delitem__`` (ditto), ``insert``, ``append``,
``reverse``. Concrete mutating methods: ``extend``, ``pop``,
``remove``. Concrete mutating operators: ``+=``, ``*=`` (these
- mutate the object in place). Note: this does not define
+ mutate the object in place). **Note:** this does not define
``sort()`` -- that is only required to exist on genuine ``list``
instances.
+**Open issues:** If all the elements of a sequence are totally
+ordered, the sequence itself can be totally ordered with respect to
+other sequences containing corresponding items of the same type.
+Should we reflect this by making ``Sequence`` derive from
+``TotallyOrdered``? Or ``Partiallyordered``? Also, we could easily
+define comparison of sequences of different types, so that e.g.
+``(1, 2, 3) == [1, 2, 3]`` and ``(1, 2) < [1, 2, 3]``. Should we?
+(It might imply ``["a", "b"] == "ab"`` and ``[1, 2] == b"\1\2"``.)
+
Strings
-------
@@ -686,10 +730,19 @@
.. [7] Unifying types and classes in Python 2.2, by GvR
(http://www.python.org/download/releases/2.2.3/descrintro/)
-.. [8] "Putting Metaclasses to Work: A New Dimension in Object-Oriented
- Programming", by Ira R. Forman and Scott H. Danforth
+.. [8] Putting Metaclasses to Work: A New Dimension in Object-Oriented
+ Programming, by Ira R. Forman and Scott H. Danforth
(http://www.amazon.com/gp/product/0201433052)
+.. [9] Partial order, in Wikipedia
+ (http://en.wikipedia.org/wiki/Partial_order)
+
+.. [10] Total order, in Wikipedia
+ (http://en.wikipedia.org/wiki/Total_order)
+
+.. [11] Finite set, in Wikipedia
+ (http://en.wikipedia.org/wiki/Finite_set)
+
Copyright
=========
More information about the Python-checkins
mailing list