# 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 $\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.