Would there be support for a more general cmp/__cmp__

Christopher Subich csubich.spam.block at spam.subich.block.com
Tue Oct 25 19:06:39 CEST 2005


Antoon Pardon wrote:
> Op 2005-10-25, Christopher Subich schreef <csubich.spam.block at spam.subich.block.com>:
> 

>>Which is exactly why a < b on sets returns True xor False, but cmp(a,b) 
>>throws an exception.
> 
> 
> I don't see the conection.
> 
> The documentation states that cmp(a,b) will return a negative value if
> a < b. So why should it throw an exception?

Because it's useful that cmp(a1, a2) should either (return a value) or 
(throw an exception) for any element a1, a2 within type(a1) cross 
type(a2).  If cmp sometimes is okay and sometimes throws an exception, 
then it leads to weird borkage in things like trees.

With that in mind, not all sets are comparable.  {a} and {b} have no 
comparison relationship, as you've pointed out, aside from not-equal. 
I'll get to why "not-equal" is a bad idea below.

>>cmp(a,b) asks for their relative rankings in some total ordering.
> 
> 
> The documentation doesn't state that. I also didn't find anything in
> the documentation on how the programmer should code in order to
> enforce this.

Most programmers are simply programmers; they haven't had the benefit of 
a couple years' pure-math education, so the distinction between "partial 
order" and "total order" is esoteric at best.

With that in mind, compare should conform, as best as possible, to 
"intuitive" behavior of comparison.  Since comparisons are mostly done 
on numbers, an extension of comparisons should behave "as much like 
numbers" as possible.

> 
> So someone who just use the rich comparisons to implement his
> partial order will screw up this total order that cmp is somehow
> providing.
> 
> And cmp doesn't provide a total ordering anyway. Sets are clearly
> uncomparable using cmp, so cmp doesn't provide a total order.

Cmp isn't supposed to "provide" a total order, it's supposed to reflect 
relative standing in one if one already exists for P1 x P2.  If one 
doesn't exist, I'd argue that it's the best course of action to throw an 
exception.

After all, rich comparisons were put in precisely to allow support of 
limited comparisons when a total order (or indeed full comparison) isn't 
appropriate.

> 
> Maybe the original idea was that cmp provided some total ordering,
> maybe the general idea is that cmp should provide a total ordering,
> but that is not documented, nor is there any documentation in
> helping the programmer in this. 

I doubt that anyone was thinking about it in such depth.  My bet is that 
the thought process goes this way:

Og compare numbers.  Numbers good, compare good.  Grunt grunt.
<some aeons pass>
Language designers: Wouldn't it be nice if we could allow user-defined 
objects, such as numbers with units, to compare properly with each 
other?  This would let us say (1 m) < (.5 mile) pretty easily, eh?

Guido: Let's let classes override a __cmp__ function for comparisons.

In programming language theory, comparisons were firstly about numbers, 
and their leading-order behaviour has always stayed about numbers. 
Comparing entities which are best represented in an... interesting 
formal mathematical way (i.e. partial orders, objects for which some 
comparisons are Just Plain Weird) works only as a side-effect of 
number-like behavior.

The lesson to take home from this: the less a custom class behaves like 
a number, the less intutitively meaningful (or even valid) comparisons 
will be on it.

> 
> And even if we leave sets aside it still isn't true.
> 
> 
>>>>from decimal import Decimal
>>>>Zero = Decimal(0)
>>>>cmp( ( ) , Zero)
> 
> -1
> 
>>>>cmp(Zero, 1)
> 
> -1
> 
>>>>cmp(1, ( ) )
> 
> -1

I'd argue that the wart here is that cmp doesn't throw an exception, not 
that it returns inconsistent results.  This is a classic case of 
incomparable objects, and saying that 1 < an empty tuple is bordering on 
meaningless.


> 
>>For a 
>>space that does not have a total ordering, cmp(a,b) is meaningless at 
>>best and dangerous at worst.
> 
> 
> The current specs and implemantation are.
> 
> I see nothing wrong with a function that would provide four kinds of
> results when given two elements. The same results as cmp gives now
> when it applies and None or other appropiate value or a raised
> exception when not.
> 
> Given how little this functionality differs from the current cmp,
> I don't see why it couldn't replace the current cmp.

My biggest complaint here is about returning None or IncomparableValue; 
if that happens, then all code that relies on cmp returning a numeric 
result will have to be rewritten.

Comparing incomparables is an exceptional case, and hence it should 
raise an exception.

As for saying that cmp should return some times and raise an exception 
other times, I just find it squicky.  Admittedly, this is entirely up to 
the class designer, and your proposed guideline wouldn't change cmp's 
behavior for clases that /are/ totally ordered.

Then again, sets excepted, your guideline doesn't seem very applicable 
in standard library code.

>>It /should/ throw an exception when the 
>>results of cmp aren't well-defined, consistent, antisymmetric, and 
>>transitive.
> 
> 
> That an order is not total in no way implies any of the above.
> The order on sets is well-defined, consistent, antisymmetric
> and transitive.

A partial order is by definition consistent, antisymmetric, and 
transitive.  A total order is furthermore universal, such that if a != 
b, aRb xor bRa.

This matches the normal use of cmp, and comparing two incomparable 
objects is an exceptional case -- hence the exception.  Although again, 
you're free to provide a cmp for your classes that operates only on a 
subset of type x type.



More information about the Python-list mailing list