Python's total_ordering decorator: a misnomer

A fundamental aspect of software design is modeling real-world object with mathematical concepts, implemented by data structures. Sometimes things get lost in translation. Recently, I came across an interesting example of modeling sortable objects with the total_ordering method in Python’s functools module, but it doesn’t adhere to total order’s mathematical definition!

From the Wikipedia page of total order:

A Total Order is a binary relation on some set X, which is antisymmetric, transitive, and a connex relation. Formally, a binary relation ≤ is a Total Order on a set X if the following statements hold for all a, b and c in X:

  • Antisymmetry: If a≤b∧b≤a then a=b;

  • Transitivity: If a≤b∧b≤c then a≤c;

  • Connexity: a≤b∨b≤a.

This definition works pretty naturally with the usual sequences like the natural numbers or the English alphabet. Take the natural numbers as an example:

Now that we’ve established what an total order is, let’s look at Python’s modeling of it. It turns out that Python’s total_ordering does not actually model the definition of total orders that we’ve just established. From the Python documentation:

Given a class defining one or more rich comparison ordering methods, this class decorator supplies the rest. This simplifies the effort involved in specifying all of the possible rich comparison operations:

The class must define one of __lt__(), __le__(), __gt__(), or __ge__(). In addition, the class should supply an __eq__() method.

As we can see, the Python total_ordering method enforces connexity by requiring the user to define one of __lt__(), __le__(), __gt__() or __ge__(), but it does not enforce antisymmetry. In Python’s implementation, __eq__() is a function supplied by the user, not one that’s implied by a≤b and b≤a both holding true.

The implication of this discrepancy between the mathematical definition and the Python implementation is that we can use total_ordering to implement sets that are definitely not total orders mathematically. For example, a total preorder, which only satisfies transitivity and connexity.

Case Study

Suppose we have a simple class that keeps track of API calls in a log:

We want to be able to sort a list of API calls, so comparison operators are useful. We’ll also implement pretty print.

@total_ordering
class APICall:
    def __init__(self, timestamp, call):
        self.timestamp = timestamp
        self.call = call

    def __repr__(self):
        return str(self.timestamp) + " " + self.call

    def __le__(self, other):
        return self.timestamp <= other.timestamp

Let’s try it out in a simple script:

API_log = []
API_log.append(APICall(0, "POST"))
API_log.append(APICall(0, "PUT"))
API_log.append(APICall(1, "GET"))
API_log.append(APICall(1, "DELETE"))
API_log.append(APICall(2, "GET"))
API_log.append(APICall(0, "GET"))

print(sorted(API_log))
print(API_log[0] == API_log[1])

The output is

[0 GET, 0 PUT, 0 POST, 1 DELETE, 1 GET, 2 GET]
False

This implements a class using total_ordering that is not a total order! The APICall class satisfies transitivity and connexity, but not antisymmetry. Turns out, Python does not enforce that the user has to have __eq__() defined for their class at all. As we can verify from the source code, total_ordering merely generates all rich comparison methods from one supplied by the user:

def _gt_from_lt(self, other, NotImplemented=NotImplemented):
    'Return a > b.  Computed by @total_ordering from (not a < b) and (a != b).'
    op_result = self.__lt__(other)
    if op_result is NotImplemented:
        return op_result
    return not op_result and self != other

def _le_from_lt(self, other, NotImplemented=NotImplemented):
    ...

def _ge_from_lt(self, other, NotImplemented=NotImplemented):
    ...

def _ge_from_le(self, other, NotImplemented=NotImplemented):
    ...

def _lt_from_le(self, other, NotImplemented=NotImplemented):
    ...

def _gt_from_le(self, other, NotImplemented=NotImplemented):
    ...

def _lt_from_gt(self, other, NotImplemented=NotImplemented):
    ...

def _ge_from_gt(self, other, NotImplemented=NotImplemented):
    ...

def _le_from_gt(self, other, NotImplemented=NotImplemented):
    ...

def _le_from_ge(self, other, NotImplemented=NotImplemented):
    ...

def _gt_from_ge(self, other, NotImplemented=NotImplemented):
    ...

def _lt_from_ge(self, other, NotImplemented=NotImplemented):
    ...

_convert = {
    '__lt__': [('__gt__', _gt_from_lt),
               ('__le__', _le_from_lt),
               ('__ge__', _ge_from_lt)],
    '__le__': [('__ge__', _ge_from_le),
               ('__lt__', _lt_from_le),
               ('__gt__', _gt_from_le)],
    '__gt__': [('__lt__', _lt_from_gt),
               ('__ge__', _ge_from_gt),
               ('__le__', _le_from_gt)],
    '__ge__': [('__le__', _le_from_ge),
               ('__gt__', _gt_from_ge),
               ('__lt__', _lt_from_ge)]
}

def total_ordering(cls):
    """Class decorator that fills in missing ordering methods"""
    # Find user-defined comparisons (not those inherited from object).
    roots = {op for op in _convert if getattr(cls, op, None) is not getattr(object, op, None)}
    if not roots:
        raise ValueError('must define at least one ordering operation: < > <= >=')
    root = max(roots)       # prefer __lt__ to __le__ to __gt__ to __ge__
    for opname, opfunc in _convert[root]:
        if opname not in roots:
            opfunc.__name__ = opname
            setattr(cls, opname, opfunc)
    return cls

Thus, the total_ordering does not enforce the mathematical definition of a total order, and we can use it to implement a total preorder and Python won’t stop us!

Come to think of it, it makes sense for Python’s total_ordering to cover more than just total orders — real-life objects are rarely as clean-cut as mathematical concepts. However, it’s still intriguing to see how the meaning of a term evolves as we move from theory to practice.