Source

python-peps / pep-3141.txt

Full commit
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
PEP: 3141
Title: A Type Hierarchy for Numbers
Version: $Revision$
Last-Modified: $Date$
Author: Jeffrey Yasskin <jyasskin@google.com>
Status: Final
Type: Standards Track
Content-Type: text/x-rst
Created: 23-Apr-2007
Post-History: 25-Apr-2007, 16-May-2007, 02-Aug-2007


Abstract
========

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 :> Integral`` where ``A :> B``
means "A is a supertype of B". The hierarchy is inspired by Scheme's
numeric tower [#schemetower]_.

Rationale
=========

Functions that take numbers as arguments should be able to determine
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 ``Integrals``, and the functions in the ``math`` module require
their arguments to be ``Real``.

Specification
=============

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.

The type checks in the standard library should use these classes
instead of the concrete built-ins.


Numeric Classes
---------------

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. ::

    class Number(metaclass=ABCMeta): pass


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.

        In short, those are: conversion to complex, bool(), .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):
            """Return a builtin complex instance."""

        def __bool__(self):
            """True if self != 0."""
            return self != 0

        @abstractproperty
        def real(self):
            """Retrieve the real component of this number.

            This should subclass Real.
            """
            raise NotImplementedError

        @abstractproperty
        def imag(self):
            """Retrieve the real component of this number.

            This should subclass Real.
            """
            raise NotImplementedError

        @abstractmethod
        def __add__(self, other):
            raise NotImplementedError

        @abstractmethod
        def __radd__(self, other):
            raise NotImplementedError

        @abstractmethod
        def __neg__(self):
            raise NotImplementedError

        def __pos__(self):
            """Coerces self to whatever class defines the method."""
            raise NotImplementedError

        def __sub__(self, other):
            return self + -other

        def __rsub__(self, other):
            return -self + other

        @abstractmethod
        def __mul__(self, other):
            raise NotImplementedError

        @abstractmethod
        def __rmul__(self, other):
            raise NotImplementedError

        @abstractmethod
        def __div__(self, other):
            """a/b; should promote to float or complex when necessary."""
            raise NotImplementedError

        @abstractmethod
        def __rdiv__(self, other):
            raise NotImplementedError

        @abstractmethod
        def __pow__(self, exponent):
            """a**b; should promote to float or complex when necessary."""
            raise NotImplementedError

        @abstractmethod
        def __rpow__(self, base):
            raise NotImplementedError

        @abstractmethod
        def __abs__(self):
            """Returns the Real distance from 0."""
            raise NotImplementedError

        @abstractmethod
        def conjugate(self):
            """(x+y*i).conjugate() returns (x-y*i)."""
            raise NotImplementedError

        @abstractmethod
        def __eq__(self, other):
            raise NotImplementedError

        # __ne__ is inherited from object and negates whatever __eq__ does.


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 except for NaNs (which this PEP basically ignores). ::

    class Real(Complex):
        """To Complex, Real adds the operations that work on real numbers.

        In short, those are: conversion to float, trunc(), math.floor(),
        math.ceil(), round(), divmod(), //, %, <, <=, >, and >=.

        Real also provides defaults for some of the derived operations.
        """

        # XXX What to do about the __int__ implementation that's
        # currently present on float?  Get rid of it?

        @abstractmethod
        def __float__(self):
            """Any Real can be converted to a native float object."""
            raise NotImplementedError

        @abstractmethod
        def __trunc__(self):
            """Truncates self to an Integral.

            Returns an Integral i such that:
              * i>=0 iff self>0;
              * abs(i) <= abs(self);
              * for any Integral j satisfying the first two conditions,
                abs(i) >= abs(j) [i.e. i has "maximal" abs among those].
            i.e. "truncate towards 0".
            """
            raise NotImplementedError

        @abstractmethod
        def __floor__(self):
            """Finds the greatest Integral <= self."""
            raise NotImplementedError

        @abstractmethod
        def __ceil__(self):
            """Finds the least Integral >= self."""
            raise NotImplementedError

        @abstractmethod
        def __round__(self, ndigits:Integral=None):
            """Rounds self to ndigits decimal places, defaulting to 0.

            If ndigits is omitted or None, returns an Integral,
            otherwise returns a Real, preferably of the same type as
            self. Types may choose which direction to round half. For
            example, float rounds half toward even.

            """
            raise NotImplementedError

        def __divmod__(self, other):
            """The pair (self // other, self % other).

            Sometimes this can be computed faster than the pair of
            operations.
            """
            return (self // other, self % other)

        def __rdivmod__(self, other):
            """The pair (self // other, self % other).

            Sometimes this can be computed faster than the pair of
            operations.
            """
            return (other // self, other % self)

        @abstractmethod
        def __floordiv__(self, other):
            """The floor() of self/other. Integral."""
            raise NotImplementedError

        @abstractmethod
        def __rfloordiv__(self, other):
            """The floor() of other/self."""
            raise NotImplementedError

        @abstractmethod
        def __mod__(self, other):
            """self % other

            See
            http://mail.python.org/pipermail/python-3000/2006-May/001735.html
            and consider using "self/other - trunc(self/other)"
            instead if you're worried about round-off errors.
            """
            raise NotImplementedError

        @abstractmethod
        def __rmod__(self, other):
            """other % self"""
            raise NotImplementedError

        @abstractmethod
        def __lt__(self, other):
            """< on Reals defines a total ordering, except perhaps for NaN."""
            raise NotImplementedError

        @abstractmethod
        def __le__(self, other): 
            raise NotImplementedError

        # __gt__ and __ge__ are automatically done by reversing the arguments.
        # (But __le__ is not computed as the opposite of __gt__!)

        # Concrete implementations of Complex abstract methods.
        # Subclasses may override these, but don't have to.

        def __complex__(self):
            return complex(float(self))

        @property
        def real(self):
            return +self

        @property
        def imag(self):
            return 0

        def conjugate(self):
            """Conjugate is a no-op for Reals."""
            return +self


We should clean up Demo/classes/Rat.py and promote it into
rational.py in the standard library. Then it will implement the
Rational ABC. ::

    class Rational(Real, Exact):
        """.numerator and .denominator should be in lowest terms."""

        @abstractproperty
        def numerator(self):
            raise NotImplementedError

        @abstractproperty
        def denominator(self):
            raise NotImplementedError

        # Concrete implementation of Real's conversion to float.
        # (This invokes Integer.__div__().)

        def __float__(self):
            return self.numerator / self.denominator


And finally integers::

    class Integral(Rational):
        """Integral adds a conversion to int and the bit-string operations."""

        @abstractmethod
        def __int__(self):
            raise NotImplementedError

        def __index__(self):
            """__index__() exists because float has __int__()."""
            return int(self)

        def __lshift__(self, other):
            return int(self) << int(other)

        def __rlshift__(self, other):
            return int(other) << int(self)

        def __rshift__(self, other):
            return int(self) >> int(other)

        def __rrshift__(self, other):
            return int(other) >> int(self)

        def __and__(self, other):
            return int(self) & int(other)

        def __rand__(self, other):
            return int(other) & int(self)

        def __xor__(self, other):
            return int(self) ^ int(other)

        def __rxor__(self, other):
            return int(other) ^ int(self)

        def __or__(self, other):
            return int(self) | int(other)

        def __ror__(self, other):
            return int(other) | int(self)

        def __invert__(self):
            return ~int(self)

        # Concrete implementations of Rational and Real abstract methods.
        def __float__(self):
            """float(self) == float(int(self))"""
            return float(int(self))

        @property
        def numerator(self):
            """Integers are their own numerators."""
            return +self

        @property
        def denominator(self):
            """Integers have a denominator of 1."""
            return 1


Changes to operations and __magic__ methods
-------------------------------------------

To support more precise narrowing from float to int (and more
generally, from Real to Integral), we propose the following new
__magic__ methods, to be called from the corresponding library
functions. All of these return Integrals rather than Reals.

1. ``__trunc__(self)``, called from a new builtin ``trunc(x)``, which
   returns the Integral closest to ``x`` between 0 and ``x``.

2. ``__floor__(self)``, called from ``math.floor(x)``, which returns
   the greatest Integral ``<= x``.

3. ``__ceil__(self)``, called from ``math.ceil(x)``, which returns the
   least Integral ``>= x``.

4. ``__round__(self)``, called from ``round(x)``, which returns the
   Integral closest to ``x``, rounding half as the type chooses.
   ``float`` will change in 3.0 to round half toward even. There is
   also a 2-argument version, ``__round__(self, ndigits)``, called
   from ``round(x, ndigits)``, which should return a Real.

In 2.6, ``math.floor``, ``math.ceil``, and ``round`` will continue to
return floats.

The ``int()`` conversion implemented by ``float`` is equivalent to
``trunc()``.  In general, the ``int()`` conversion should try
``__int__()`` first and if it is not found, try ``__trunc__()``.

``complex.__{divmod,mod,floordiv,int,float}__`` also go away. It would
be nice to provide a nice error message to help confused porters, but
not appearing in ``help(complex)`` is more important.


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):
	    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
~~~~~~~~~~~~~~~~~~~~~~~~

There are, of course, more possible ABCs for numbers, and this would
be a poor hierarchy if it precluded the possibility of adding
those. You can add ``MyFoo`` between ``Complex`` and ``Real`` with::

    class MyFoo(Complex): ...
    MyFoo.register(Real)

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
=====================

The initial version of this PEP defined an algebraic hierarchy
inspired by a Haskell Numeric Prelude [#numericprelude]_ including
MonoidUnderPlus, AdditiveGroup, Ring, and Field, and mentioned several
other possible algebraic types before getting to the numbers. We had
expected this to be useful to people using vectors and matrices, but
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 we 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.


The Decimal Type
================

After consultation with its authors it has been decided that the
``Decimal`` type should not at this time be made part of the numeric
tower.


References
==========

.. [#pep3119] Introducing Abstract Base Classes
   (http://www.python.org/dev/peps/pep-3119/)

.. [#classtree] Possible Python 3K Class Tree?, wiki page by Bill Janssen
   (http://wiki.python.org/moin/AbstractBaseClasses)

.. [#numericprelude] NumericPrelude: An experimental alternative hierarchy
   of numeric type classes
   (http://darcs.haskell.org/numericprelude/docs/html/index.html)

.. [#schemetower] The Scheme numerical tower
   (http://www.swiss.ai.mit.edu/ftpdir/scheme-reports/r5rs-html/r5rs_8.html#SEC50)


Acknowledgements
================

Thanks to Neal 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, 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
=========

This document has been placed in the public domain.



..
   Local Variables:
   mode: indented-text
   indent-tabs-mode: nil
   sentence-end-double-space: t
   fill-column: 70
   coding: utf-8
   End: