# 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!

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

• Antisymmetry: If $a \le b \land b \le a$ then $a = b$;

• Transitivity: If $a \le b \land b \le c$ then $a \le c$;

• Connexity: $a \le b \lor b \le 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:

• Antisymmetry: $\forall x, y \in N$, suppose $a \le b \land b \le a$. If $a \ne b$, then there are 2 cases:

• $a < b$. This contradicts the premise that $b \le a$.

• $a > b$. This contradicts the premise that $a \le b$.
Therefore, $a = b$.

• Transitivity: $\forall x, y \in N$, suppose $a \le b \land b \le c$. If $a > c$, given that $b \le c$, $a, b$ must be on opposite sides of $c$ and $a > b$. This contradicts the premise that $a \le b$.
Therefore, $a \le c$.

• Connexity: Suppose $\exists x, y \in N$ such that $\neg (a \le b \land b \le a)$. This implies $a > b \land b > a$, which is not true for any two natural numbers.
Therefore, $a \le b \lor b \le a$.

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 \le b$ and $b \le 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.