Rich comparison for Elements
Franco Saliola
Here is a quick description of what is below: Subclasses of Element
complain that no sorting algorithm is defined even when all the rich
comparison methods have been implemented. Bug?
In the code sample below, C is a class that inherits from Element and
implements all the rich comparison methods.
{{{
sage: class C(sage.structure.element.Element):
... def __init__(self, a):
... self.a = a
... def __repr__(self):
... return str(self.a)
... def __eq__(self, other):
... return self.a == other.a
... def __ne__(self, other):
... return self.a != other.a
... def __lt__(self, other):
... return self.a < other.a
... def __le__(self, other):
... return self.a <= other.a
... def __gt__(self, other):
... return self.a > other.a
... def __ge__(self, other):
... return self.a >= other.a
}}}
In theory, the cmp function should use the rich comparison methods for
comparisions. However, since __cmp__ has also been implemented (it is
implemented by Element), cmp bypasses all the rich comparison methods and
calls __cmp__ directly. This leads to an error since Element requires
subclasses to define a sorting algorithm:
{{{
sage: a = C('a')
sage: b = C('b')
sage: a < b
True
sage: cmp(a,b)
------------------------------------------------------------
Traceback (most recent call last):
File "<ipython console>", line 1, in <module>
File "element.pyx", line 648, in
sage.structure.element.Element.__cmp__ (sage/structure/element.c:6064)
File "element.pyx", line 561, in sage.structure.element.Element._cmp
(sage/structure/element.c:5135)
File "element.pyx", line 663, in
sage.structure.element.Element._cmp_c_impl
(sage/structure/element.c:6239)
NotImplementedError: BUG: sort algorithm for elements of 'None' not implemented
}}}
And this leads to problems with sorting via the cmp function:
{{{
sage: sorted([b,a])
[a, b]
sage: sorted([b,a], cmp=cmp)
------------------------------------------------------------
Traceback (most recent call last):
File "<ipython console>", line 1, in <module>
File "element.pyx", line 648, in
sage.structure.element.Element.__cmp__ (sage/structure/element.c:6064)
File "element.pyx", line 561, in sage.structure.element.Element._cmp
(sage/structure/element.c:5135)
File "element.pyx", line 663, in
sage.structure.element.Element._cmp_c_impl
(sage/structure/element.c:6239)
NotImplementedError: BUG: sort algorithm for elements of 'None' not implemented
}}}
One can get around this by implementing __cmp__ as well as the rich
comparison methods, but I'm wondering whether it might be better for
Element to check for and use the rich comparison methods before freaking
out.
Is there a good reason (speed? efficiency?) for this behaviour? Should I
open a ticket?
(For the record, Nicolas tells me that the new category theory code does
not fix this issue.)
Franco
--
Nicolas M. Thiery
Many Sage-Combinat developers have been annoyed by this. The thing is
that cmp is often required, even for partial orders, because many
output routines call sorted(...).
I have seen this discussed over and over on the list. Is there a
definitive synthesis of the specifications and policy in the
developers guide for how to implement partial/total orders for Python
class in Sage? There are quite a few comments in element.py, but I
find them somewhat cryptic and incomplete.
If such specifications are not yet written / fully fixed, here is what
I would find the most practical:
- The class should implement _eq_(self, other) and _lt_(self, other)
which would be guaranteed to take elements of the same parent and
test respectively whether self == other or self < other.
Other names would be fine to me. Another option would be to
implement_richcmp(self, other) which returns whether self is
strictly smaller, strictly greater, equal or incomparable.
Both options could possibly be supported, as there are situations
where one or the other are more practical.
- By default, all the other rich comparisons (__eq__, __le__, __lt__,
__gt__, __ne__, ...) would be defined by calling the above.
- By default, __cmp___ would try to use _eq_ and _lt_. What to do if the
elements are incomparable? One option would be to compare them
w.r.t. some internal order; this internal order should depend only
on the value of the object and should be consistent within a Sage
session. An option would be to compare the hash values.
Of course if the class can do something better, it should!
- Should it be imposed that the total order be a linear extension of
the partial order?
> (For the record, Nicolas tells me that the new category theory code does
> not fix this issue.)
Yup. And it can't because given the inheritance order, code in Element
(and Parent) always override stuff from the categories.
Best,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
Ondrej Certik
>
> Hello,
>
> Here is a quick description of what is below: Subclasses of Element
> complain that no sorting algorithm is defined even when all the rich
> comparison methods have been implemented. Bug?
If it helps, I create this page, that lists when each method is being called:
http://docs.sympy.org/python-comparisons.html
note that this has changed in Python 3.0, where both cmp() and
__cmp__() were removed.
Ondrej
Franco Saliola
>
> On Mon, Jun 22, 2009 at 3:25 AM, Franco Saliola<sal...@gmail.com> wrote:
>>
>> Hello,
>>
>> Here is a quick description of what is below: Subclasses of Element
>> complain that no sorting algorithm is defined even when all the rich
>> comparison methods have been implemented. Bug?
>
> If it helps, I create this page, that lists when each method is being called:
>
> http://docs.sympy.org/python-comparisons.html
I used your code to track down my problem.
Thank you! It is an excellent resource.
Franco
--
Robert Bradshaw
I would very much be in favor of simplifying comparisons! There are a
couple reasons the code is the way it is. First, in Cython (well, any
Python Extension class), either __cmp__, __richcmp__ and __hash__ are
all inherited together, or none are. Second, the code was written
before cpdef methods, and had to handle both Python and Cython
classes. Finally, there's just a lot of cruft from all the years it's
gone through, and it's easy to break things mucking around with it so
no one's gone and really cleaned it up. (There was an effort to do so
as part of the late coercion branch, but it was too much on top of
all else that was going on).
I would be in favor of a SEP regarding these issues, as well as
summarizing the long thread we had earlier this year dealing with
incomparable items and whether or not RealField(200)(pi) == RealField
(100)(pi).
- Robert
Martin Raum
discussions whether certain objects should be comparable or not, the
standard implementation of richcmp immediately calls __cmp__. This
renders impossible to python classes using both comparisons, the
partial order via __richcmp__ etc. and the total oder via __cmp__.
One solution, which also passes all tests for 4.0.2, is to prefer
_cmp_ and _richcmp_ implementations, which basically is the same
approach used for _add_ etc. . And indeed everything in element.pyx is
written to behave like that except two functions. The following patch
modifies them and admits for example representations of dictionaries
with keys, which have not worked before - the reason why I've started
thinking about this.
http://www.matha.rwth-aachen.de/~martin/element.pyx.patch
May this help, too, Franco?
Martin