Author: guido.van.rossum Date: Tue Jul 31 21:19:57 2007 New Revision: 56634 Modified: peps/trunk/pep-3141.txt Log: New version by Jeffrey Yasskin. Modified: peps/trunk/pep-3141.txt ============================================================================== --- peps/trunk/pep-3141.txt (original) +++ peps/trunk/pep-3141.txt Tue Jul 31 21:19:57 2007 @@ -7,7 +7,7 @@ Type: Standards Track Content-Type: text/x-rst Created: 23-Apr-2007 -Post-History: 25-Apr-2007, 16-May-2007 +Post-History: 25-Apr-2007, 16-May-2007, xx-Aug-2007 Abstract @@ -15,7 +15,7 @@ This proposal defines a hierarchy of Abstract Base Classes (ABCs) (PEP 3119) to represent number-like classes. It proposes a hierarchy of -``Number :> Complex :> Real :> Rational :> Integer`` where ``A :> B`` +``Number :> Complex :> Real :> Rational :> Integral`` where ``A :> B`` means "A is a supertype of B", and a pair of ``Exact``/``Inexact`` classes to capture the difference between ``floats`` and ``ints``. These types are significantly inspired by Scheme's numeric @@ -28,41 +28,16 @@ the properties of those numbers, and if and when overloading based on types is added to the language, should be overloadable based on the types of the arguments. For example, slicing requires its arguments to -be ``Integers``, and the functions in the ``math`` module require +be ``Integrals``, and the functions in the ``math`` module require their arguments to be ``Real``. Specification ============= -This PEP specifies a set of Abstract Base Classes with default -implementations. If the reader prefers to think in terms of Roles (PEP -3133), the default implementations for (for example) the Real ABC -would be moved to a RealDefault class, with Real keeping just the -method declarations. - -Although this PEP uses terminology from PEP 3119, the hierarchy is -intended to be meaningful for any systematic method of defining sets -of classes, including Interfaces. I'm also using the extra notation -from PEP 3107 (Function Annotations) to specify some types. - - -Exact vs. Inexact Classes -------------------------- - -Floating point values may not exactly obey several of the properties -you would expect. For example, it is possible for ``(X + -X) + 3 == -3``, but ``X + (-X + 3) == 0``. On the range of values that most -functions deal with this isn't a problem, but it is something to be -aware of. - -Therefore, I define ``Exact`` and ``Inexact`` ABCs to mark whether -types have this problem. Every instance of ``Integer`` and -``Rational`` should be Exact, but ``Reals`` and ``Complexes`` may or -may not be. (Do we really only need one of these, and the other is -defined as ``not`` the first?):: - - class Exact(metaclass=MetaABC): pass - class Inexact(metaclass=MetaABC): pass +This PEP specifies a set of Abstract Base Classes, and suggests a +general strategy for implementing some of the methods. It uses +terminology from PEP 3119, but the hierarchy is intended to be +meaningful for any systematic method of defining sets of classes. Numeric Classes @@ -70,23 +45,21 @@ We begin with a Number class to make it easy for people to be fuzzy about what kind of number they expect. This class only helps with -overloading; it doesn't provide any operations. **Open question:** -Should it specify ``__add__``, ``__sub__``, ``__neg__``, ``__mul__``, -and ``__abs__`` like Haskell's ``Num`` class?:: +overloading; it doesn't provide any operations. class Number(metaclass=MetaABC): pass Some types (primarily ``float``) define "Not a Number" (NaN) values that return false for any comparison, including equality with -themselves, and are maintained through operations. Because this -doesn't work well with the Reals (which are otherwise totally ordered -by ``<``), Guido suggested we might put NaN in its own type. It is -conceivable that this can still be represented by C doubles but be -included in a different ABC at runtime. **Open issue:** Is this a good -idea?:: +themselves, and are maintained through operations. That is, ``nan + x +-> nan`` and ``nan == nan -> False`` Because this doesn't work well +with the Reals (which are otherwise totally ordered by ``<``), Guido +suggested we might put NaN in its own type. It is conceivable that +this can still be represented by C doubles but be included in a +different ABC at runtime. **Open issue:** Is this a good idea?:: - class NotANumber(Number): + class UndefinedNumber(Number): """Implement IEEE 754 semantics.""" def __lt__(self, other): return false def __eq__(self, other): return false @@ -94,162 +67,130 @@ def __add__(self, other): return self def __radd__(self, other): return self ... + # Should we demand a conversion to float? + +Most implementations of complex numbers will be hashable, but if you +need to rely on that, you'll have to check it explicitly: mutable +numbers are supported by this hierarchy. :: + + class Complex(Number): + """Complex defines the operations that work on the builtin complex type. -Complex numbers are immutable and hashable. Implementors should be -careful that they make equal numbers equal and hash them to the same -values. This may be subtle if there are two different extensions of -the real numbers:: - - class Complex(Hashable, Number): - """A ``Complex`` should define the operations that work on the - Python ``complex`` type. If it is given heterogenous - arguments, it may fall back on this class's definition of the - operations.addition, subtraction, negation, and - multiplication. These operators should never return a - TypeError as long as both arguments are instances of Complex - (or even just implement __complex__). + In short, those are: a conversion to complex, .real, .imag, +, + -, *, /, abs(), .conjugate, ==, and !=. + + If it is given heterogenous arguments, and doesn't have + special knowledge about them, it should fall back to the + builtin complex type as described below. """ @abstractmethod def __complex__(self): - """This operation gives the arithmetic operations a fallback. - """ - return complex(self.real, self.imag) + """Return a builtin complex instance.""" + + @abstractmethod @property def real(self): - return complex(self).real + """Retrieve the real component of this number, which should subclass Real.""" + raise NotImplementedError + @abstractmethod @property def imag(self): - return complex(self).imag - -I define the reversed operations here so that they serve as the final -fallback for operations involving instances of Complex. **Open -issue:** Should Complex's operations check for ``isinstance(other, -Complex)``? Duck typing seems to imply that we should just try -__complex__ and succeed if it works, but stronger typing might be -justified for the operators. TODO: analyze the combinations of normal -and reversed operations with real and virtual subclasses of Complex:: + """Retrieve the real component of this number, which should subclass Real.""" + raise NotImplementedError - def __radd__(self, other): - """Should this catch any type errors and return - NotImplemented instead?""" - return complex(other) + complex(self) - def __rsub__(self, other): - return complex(other) - complex(self) + @abstractmethod + def __add__(self, other): + raise NotImplementedError + @abstractmethod + def __sub__(self, other): + raise NotImplementedError + @abstractmethod def __neg__(self): - return -complex(self) - def __rmul__(self, other): - return complex(other) * complex(self) - def __rdiv__(self, other): - return complex(other) / complex(self) + raise NotImplementedError + @abstractmethod + def __mul__(self, other): + raise NotImplementedError + @abstractmethod + def __div__(self, other): + raise NotImplementedError + @abstractmethod def __abs__(self): - return abs(complex(self)) + """Returns the Real distance from 0.""" + raise NotImplementedError + @abstractmethod def conjugate(self): - return complex(self).conjugate() + """(x+y*i).conjugate() returns (x-y*i).""" + raise NotImplementedError - def __hash__(self): - """Two "equal" values of different complex types should - hash in the same way.""" - return hash(complex(self)) + @abstractmethod + def __eq__(self, other): + raise NotImplementedError + def __ne__(self, other): + return not (self == other) The ``Real`` ABC indicates that the value is on the real line, and supports the operations of the ``float`` builtin. Real numbers are -totally ordered. (NaNs were handled above.):: +totally ordered. (NaNs were handled above).:: + + class Real(Complex): + """To Complex, Real adds the operations that work on real numbers. + + In short, those are: a conversion to float, trunc(), divmod, + %, <, <=, >, and >=. - class Real(Complex, metaclass=TotallyOrderedABC): + Real also provides defaults for the derived operations. + """ @abstractmethod def __float__(self): """Any Real can be converted to a native float object.""" - raise NotImplementedError - def __complex__(self): - """Which gives us an easy way to define the conversion to - complex.""" - return complex(float(self)) - @property - def real(self): return self - @property - def imag(self): return 0 - - def __radd__(self, other): - if isinstance(other, Real): - return float(other) + float(self) - else: - return super(Real, self).__radd__(other) - def __rsub__(self, other): - if isinstance(other, Real): - return float(other) - float(self) - else: - return super(Real, self).__rsub__(other) - def __neg__(self): - return -float(self) - def __rmul__(self, other): - if isinstance(other, Real): - return float(other) * float(self) - else: - return super(Real, self).__rmul__(other) - def __rdiv__(self, other): - if isinstance(other, Real): - return float(other) / float(self) - else: - return super(Real, self).__rdiv__(other) - def __rdivmod__(self, other): - """Implementing divmod() for your type is sufficient to - get floordiv and mod too. - """ - if isinstance(other, Real): - return divmod(float(other), float(self)) - else: - return super(Real, self).__rdivmod__(other) - def __rfloordiv__(self, other): - return divmod(other, self)[0] - def __rmod__(self, other): - return divmod(other, self)[1] - + raise NotImplementedError + + @abstractmethod def __trunc__(self): - """Do we want properfraction, floor, ceiling, and round?""" - return trunc(float(self)) - - def __abs__(self): - return abs(float(self)) + """Returns an Integral of the same sign as self whose abs is <= self's abs.""" + raise NotImplementedError -There is no way to define only the reversed comparison operators, so -these operations take precedence over any defined in the other -type. :( :: + def __divmod__(self, other): + """The pair (self // other, self % other).""" + return (self // other, self % other) + @abstractmethod + def __floordiv__(self, other): + """The floor() of self/other.""" + raise NotImplementedError + @abstractmethod + def __mod__(self, other): + """.""" + raise NotImplementedError + @abstractmethod def __lt__(self, other): - """The comparison operators in Python seem to be more - strict about their input types than other functions. I'm - guessing here that we want types to be incompatible even - if they define a __float__ operation, unless they also - declare themselves to be Real numbers. - """ - if isinstance(other, Real): - return float(self) < float(other) - else: - return NotImplemented - - def __le__(self, other): + raise NotImplementedError + def __le__(self, other): + # Assume that if other is Real, it defines an ordering + # consistent with this class, or returns NotImplemented. if isinstance(other, Real): - return float(self) <= float(other) - else: - return NotImplemented + return not (other < self) + + # Concrete implementations of Complex abstract methods. + def __complex__(self): + return complex(float(self)) + @property + def real(self): + return self + @property + def imag(self): + return 0 - def __eq__(self, other): - if isinstance(other, Real): - return float(self) == float(other) - else: - return NotImplemented - There is no built-in rational type, but it's straightforward to write, -so we provide an ABC for it:: +so we provide an ABC for it. *Open issue*: Add Demo/classes/Rat.py to +the stdlib?:: class Rational(Real, Exact): - """rational.numerator and rational.denominator should be in - lowest terms. - """ + """.numerator and .denominator should be in lowest terms.""" @abstractmethod @property def numerator(self): @@ -259,49 +200,80 @@ def denominator(self): raise NotImplementedError + # Concrete implementation of Real's conversion to float. def __float__(self): return self.numerator / self.denominator - class Integer(Rational): - @abstractmethod - def __int__(self): - raise NotImplementedError - def __float__(self): - return float(int(self)) +And finally integers:: + + class Integral(Rational): + """Integral adds a conversion to int and the bit-string operations.""" + @abstractmethod + def __int__(self): + raise NotImplementedError + + @abstractmethod + def __lshift__(self, other): + raise NotImplementedError + @abstractmethod + def __rshift__(self, other): + raise NotImplementedError + @abstractmethod + def __and__(self, other): + raise NotImplementedError + @abstractmethod + def __xor__(self, other): + raise NotImplementedError + @abstractmethod + def __or__(self, other): + raise NotImplementedError + + # Concrete implementations of Rational and Real abstract methods. + def __float__(self): + return float(int(self)) @property - def numerator(self): return self + def numerator(self): + return self @property - def denominator(self): return 1 + def denominator(self): + return 1 - def __ror__(self, other): - return int(other) | int(self) - def __rxor__(self, other): - return int(other) ^ int(self) - def __rand__(self, other): - return int(other) & int(self) - def __rlshift__(self, other): - return int(other) << int(self) - def __rrshift__(self, other): - return int(other) >> int(self) - def __invert__(self): - return ~int(self) - def __radd__(self, other): - """All of the Real methods need to be overridden here too - in order to get a more exact type for their results. - """ - if isinstance(other, Integer): - return int(other) + int(self) - else: - return super(Integer, self).__radd__(other) - ... + + +Exact vs. Inexact Classes +------------------------- + +Floating point values may not exactly obey several of the properties +you would expect. For example, it is possible for ``(X + -X) + 3 == +3``, but ``X + (-X + 3) == 0``. On the range of values that most +functions deal with this isn't a problem, but it is something to be +aware of. + +Therefore, I define ``Exact`` and ``Inexact`` ABCs to mark whether +types have this problem. Every instance of ``Integral`` and +``Rational`` should be Exact, but ``Reals`` and ``Complexes`` may or +may not be. (Do we really only need one of these, and the other is +defined as ``not`` the first?):: + + class Exact(Number): pass + class Inexact(Number): pass + + +Notes for type implementors +--------------------------- + +Implementors should be careful to make equal numbers equal and +hash them to the same values. This may be subtle if there are two +different extensions of the real numbers. For example, a complex type +could reasonably implement hash() as follows:: def __hash__(self): - """Surprisingly, hash() needs to be overridden too, since - there are integers that float can't represent.""" - return hash(int(self)) + return hash(complex(self)) +but should be careful of any values that fall outside of the built in +complex's range or precision. Adding More Numeric ABCs ------------------------ @@ -313,7 +285,61 @@ class MyFoo(Complex): ... MyFoo.register(Real) -TODO(jyasskin): Check this. +Implementing the arithmetic operations +-------------------------------------- + +We want to implement the arithmetic operations so that mixed-mode +operations either call an implementation whose author knew about the +types of both arguments, or convert both to the nearest built in type +and do the operation there. For subtypes of Integral, this means that +__add__ and __radd__ should be defined as:: + + class MyIntegral(Integral): + def __add__(self, other): + if isinstance(other, MyIntegral): + return do_my_adding_stuff(self, other) + elif isinstance(other, OtherTypeIKnowAbout): + return do_my_other_adding_stuff(self, other) + else: + return NotImplemented + def __radd__(self, other): + if isinstance(other, MyIntegral): + return do_my_adding_stuff(other, self) + elif isinstance(other, OtherTypeIKnowAbout): + return do_my_other_adding_stuff(other, self) + elif isinstance(other, Integral): + return int(other) + int(self) + elif isinstance(other, Real): + return float(other) + float(self) + elif isinstance(other, Complex): + return complex(other) + complex(self) + else: + return NotImplemented + + +There are 5 different cases for a mixed-type operation on subclasses +of Complex. I'll refer to all of the above code that doesn't refer to +MyIntegral and OtherTypeIKnowAbout as "boilerplate". ``a`` will be an +instance of ``A``, which is a subtype of ``Complex`` (``a : A <: +Complex``), and ``b : B <: Complex``. I'll consider ``a + b``: + + 1. If A defines an __add__ which accepts b, all is well. + 2. If A falls back to the boilerplate code, and it were to return + a value from __add__, we'd miss the possibility that B defines + a more intelligent __radd__, so the boilerplate should return + NotImplemented from __add__. (Or A may not implement __add__ at + all.) + 3. Then B's __radd__ gets a chance. If it accepts a, all is well. + 4. If it falls back to the boilerplate, there are no more possible + methods to try, so this is where the default implementation + should live. + 5. If B <: A, Python tries B.__radd__ before A.__add__. This is + ok, because it was implemented with knowledge of A, so it can + handle those instances before delegating to Complex. + +If ``A<:Complex`` and ``B<:Real`` without sharing any other knowledge, +then the appropriate shared operation is the one involving the built +in complex, and both __radd__s land there, so ``a+b == b+a``. Rejected Alternatives @@ -324,12 +350,18 @@ MonoidUnderPlus, AdditiveGroup, Ring, and Field, and mentioned several other possible algebraic types before getting to the numbers. I had expected this to be useful to people using vectors and matrices, but -the NumPy community really wasn't interested. The numbers then had a -much more branching structure to include things like the Gaussian -Integers and Z/nZ, which could be Complex but wouldn't necessarily -support things like division. The community decided that this was too -much complication for Python, so the proposal has been scaled back to -resemble the Scheme numeric tower much more closely. +the NumPy community really wasn't interested, and we ran into the +issue that even if ``x`` is an instance of ``X <: MonoidUnderPlus`` +and ``y`` is an instance of ``Y <: MonoidUnderPlus``, ``x + y`` may +still not make sense. + +Then I gave the numbers a much more branching structure to include +things like the Gaussian Integers and Z/nZ, which could be Complex but +wouldn't necessarily support things like division. The community +decided that this was too much complication for Python, so I've now +scaled back the proposal to resemble the Scheme numeric tower much +more closely. + References ========== @@ -337,10 +369,7 @@ .. [#pep3119] Introducing Abstract Base Classes (http://www.python.org/dev/peps/pep-3119/) -.. [#pep3107] Function Annotations - (http://www.python.org/dev/peps/pep-3107/) - -.. [3] Possible Python 3K Class Tree?, wiki page created by Bill Janssen +.. [#classtree] Possible Python 3K Class Tree?, wiki page created by Bill Janssen (http://wiki.python.org/moin/AbstractBaseClasses) .. [#numericprelude] NumericPrelude: An experimental alternative hierarchy of numeric type classes @@ -355,9 +384,10 @@ Thanks to Neil Norwitz for encouraging me to write this PEP in the first place, to Travis Oliphant for pointing out that the numpy people -didn't really care about the algebraic concepts, and to Guido van -Rossum, Collin Winter, and lots of other people on the mailing list -for refining the concept. +didn't really care about the algebraic concepts, to Alan Isaac for +reminding me that Scheme had already done this, and to Guido van +Rossum and lots of other people on the mailing list for refining the +concept. Copyright =========