Abstract

This PEP proposes several new features for comparisons:

• Allow separately overloading of <, >, <=, >=, ==, !=, both in classes and in C extensions.
• Allow any of those overloaded operators to return something else besides a Boolean result.

Motivation

The main motivation comes from NumPy, whose users agree that A<B should return an array of elementwise comparison outcomes; they currently have to spell this as less(A,B) because A<B can only return a Boolean result or raise an exception.

An additional motivation is that frequently, types don’t have a natural ordering, but still need to be compared for equality. Currently such a type must implement comparison and thus define an arbitrary ordering, just so that equality can be tested.

Also, for some object types an equality test can be implemented much more efficiently than an ordering test; for example, lists and dictionaries that differ in length are unequal, but the ordering requires inspecting some (potentially all) items.

Previous Work

Rich Comparisons have been proposed before; in particular by David Ascher, after experience with Numerical Python:

http://starship.python.net/crew/da/proposals/richcmp.html

It is also included below as an Appendix. Most of the material in this PEP is derived from David’s proposal.

Concerns

1. Backwards compatibility, both at the Python level (classes using __cmp__ need not be changed) and at the C level (extensions defining tp_comparea need not be changed, code using PyObject_Compare() must work even if the compared objects use the new rich comparison scheme).
2. When A<B returns a matrix of elementwise comparisons, an easy mistake to make is to use this expression in a Boolean context. Without special precautions, it would always be true. This use should raise an exception instead.
3. If a class overrides x==y but nothing else, should x!=y be computed as not(x==y), or fail? What about the similar relationship between < and >=, or between > and <=?
4. Similarly, should we allow x<y to be calculated from y>x? And x<=y from not(x>y)? And x==y from y==x, or x!=y from y!=x?
5. When comparison operators return elementwise comparisons, what to do about shortcut operators like A<B<C, A<B and C<D, A<B or C<D?
6. What to do about min() and max(), the ‘in’ and ‘not in’ operators, list.sort(), dictionary key comparison, and other uses of comparisons by built-in operations?

Proposed Resolutions

1. Full backwards compatibility can be achieved as follows. When an object defines tp_compare() but not tp_richcompare(), and a rich comparison is requested, the outcome of tp_compare() is used in the obvious way. E.g. if “<” is requested, an exception if tp_compare() raises an exception, the outcome is 1 if tp_compare() is negative, and 0 if it is zero or positive. Etc.

   Full forward compatibility can be achieved as follows. When a classic comparison is requested on an object that implements tp_richcompare(), up to three comparisons are used: first == is tried, and if it returns true, 0 is returned; next, < is tried and if it returns true, -1 is returned; next, > is tried and if it returns true, +1 is returned. If any operator tried returns a non-Boolean value (see below), the exception raised by conversion to Boolean is passed through. If none of the operators tried returns true, the classic comparison fallbacks are tried next.

   (I thought long and hard about the order in which the three comparisons should be tried. At one point I had a convincing argument for doing it in this order, based on the behavior of comparisons for cyclical data structures. But since that code has changed again, I’m not so sure that it makes a difference any more.)

2. Any type that returns a collection of Booleans instead of a single boolean should define nb_nonzero() to raise an exception. Such a type is considered a non-Boolean.
3. The == and != operators are not assumed to be each other’s complement (e.g. IEEE 754 floating point numbers do not satisfy this). It is up to the type to implement this if desired. Similar for < and >=, or > and <=; there are lots of examples where these assumptions aren’t true (e.g. tabnanny).
4. The reflexivity rules are assumed by Python. Thus, the interpreter may swap y>x with x<y, y>=x with x<=y, and may swap the arguments of x==y and x!=y. (Note: Python currently assumes that x==x is always true and x!=x is never true; this should not be assumed.)
5. In the current proposal, when A<B returns an array of elementwise comparisons, this outcome is considered non-Boolean, and its interpretation as Boolean by the shortcut operators raises an exception. David Ascher’s proposal tries to deal with this; I don’t think this is worth the additional complexity in the code generator. Instead of A<B<C, you can write (A<B)&(B<C).
6. The min() and list.sort() operations will only use the < operator; max() will only use the > operator. The ‘in’ and ‘not in’ operators and dictionary lookup will only use the == operator.

Implementation Proposal

This closely follows David Ascher’s proposal.

Copyright

This document has been placed in the public domain.

Appendix

Here is most of David Ascher’s original proposal (version 0.2.1, dated Wed Jul 22 16:49:28 1998; I’ve left the Contents, History and Patches sections out). It addresses almost all concerns above.

Abstract

A new mechanism allowing comparisons of Python objects to return values other than -1, 0, or 1 (or raise exceptions) is proposed. This mechanism is entirely backwards compatible, and can be controlled at the level of the C PyObject type or of the Python class definition. There are three cooperating parts to the proposed mechanism:

• the use of the last slot in the type object structure to store a pointer to a rich comparison function
• the addition of special methods for classes
• the addition of an optional argument to the builtin cmp() function.

Motivation

The current comparison protocol for Python objects assumes that any two Python objects can be compared (as of Python 1.5, object comparisons can raise exceptions), and that the return value for any comparison should be -1, 0 or 1. -1 indicates that the first argument to the comparison function is less than the right one, +1 indicating the contrapositive, and 0 indicating that the two objects are equal. While this mechanism allows the establishment of an order relationship (e.g. for use by the sort() method of list objects), it has proven to be limited in the context of Numeric Python (NumPy).

Specifically, NumPy allows the creation of multidimensional arrays, which support most of the numeric operators. Thus:

x = array((1,2,3,4))        y = array((2,2,4,4))

are two NumPy arrays. While they can be added elementwise,:

z = x + y   # z == array((3,4,7,8))

they cannot be compared in the current framework - the released version of NumPy compares the pointers, (thus yielding junk information) which was the only solution before the recent addition of the ability (in 1.5) to raise exceptions in comparison functions.

Even with the ability to raise exceptions, the current protocol makes array comparisons useless. To deal with this fact, NumPy includes several functions which perform the comparisons: less(), less_equal(), greater(), greater_equal(), equal(), not_equal(). These functions return arrays with the same shape as their arguments (modulo broadcasting), filled with 0’s and 1’s depending on whether the comparison is true or not for each element pair. Thus, for example, using the arrays x and y defined above:

less(x,y)

would be an array containing the numbers (1,0,0,0).

The current proposal is to modify the Python object interface to allow the NumPy package to make it so that x < y returns the same thing as less(x,y). The exact return value is up to the NumPy package – what this proposal really asks for is changing the Python core so that extension objects have the ability to return something other than -1, 0, 1, should their authors choose to do so.

Current State of Affairs

The current protocol is, at the C level, that each object type defines a tp_compare slot, which is a pointer to a function which takes two PyObject* references and returns -1, 0, or 1. This function is called by the PyObject_Compare() function defined in the C API. PyObject_Compare() is also called by the builtin function cmp() which takes two arguments.

x < y < z

temp1 = x < y
if temp1:
  return y < z
else:
  return temp1

x < y < z

temp1 = x < y
if temp1:
  temp2 = y < z
  return boolean_combine(temp1, temp2)
else:
  return temp1

def boolean_combine(a, b):
    if hasattr(a, '__boolean_and__') or \
       hasattr(b, '__boolean_and__'):
        try:
            return a.__boolean_and__(b)
        except:
            return b.__boolean_and__(a)
    else: # standard behavior
        if a:
            return b
        else:
            return 0