Element comparison for Python classes

[vdelecroix]

In #17890 the comparison of elements (i.e. Element.__cmp__) and rich comparison of elements (i.e. Element.__richcmp__) have been simplified.

1 .If coercion has to be involved then the Python elements should implement:

• _richcmp_(left, right, op) for rich comparisons (i.e. operators <, <=, ==, !=, >= and >=)
• _cmp_(left, right) for comparisons (i.e. when calling cmp(x,y)) In these two methods, it can be assumed that both arguments left and right are subclasses of Element with the same parent. If _cmp_ makes sense it is possible to implement it only. If an element wants to implement == and != only, then it should just raise a NotImplementedError for other operators in _richcmp_(left,right,op).

2 . If comparison needs to not avoid coercion, then:

• rich comparison is possible through __eq__, __ne__, __lt__, etc (and all of these should be implemented)
• comparison is possible via __cmp__

With the current branch:

• make everything needed for rich comparisons available from Python: the branch adds py_rich_to_bool and op_EQ, op_NE, op_LT, op_LE, op_GE, op_GT in sage.structure.sage_object
• six elements are modified to use either _richcmp_ or _cmp_ instead of __eq__/__ne__/__lt__, etc (and #18303 takes care of sage.rings.qqbar)

Potentially to discuss:

• decide what should we do with respect to x < y when this makes no sense (some elements do raise a TypeError)
• remove the test in the default Element._cmp_ since an element implementing __cmp__ wants to avoid coercion

[jdemeyer]

I think in general, rich comparisons (both Cython's __richcmp__ and Python's __eq__ and friends) should be discouraged in favour of _cmp_, because the latter needs coercion only once. Only for more complicated types where rich comparisons cannot be implemented in terms of __cmp__ (intervals for example) should rich comparisons be used.

Do you agree?

[vdelecroix]

Replying to jdemeyer:

I think in general, rich comparisons (both Cython's __richcmp__ and Python's __eq__ and friends) should be discouraged in favour of _cmp_, because the latter needs coercion only once. Only for more complicated types where rich comparisons cannot be implemented in terms of __cmp__ (intervals for example) should rich comparisons be used.

Do you agree?

Partly. I agree that if _cmp_ is doable and cheap then it is preferable. But

• consider lists (or words or sequences), you have a cheap test to check whether they are different: comparing the length. So in that case, you might want to use it before comparing items one by one for getting the lexicographic ordering.
• there are elements where equality makes sense but not comparison. _richcmp_ can handle that but not _cmp_. In such case I would implement _richcmp_ and raise an error if the operator is not Py_EQ or Py_NE.

And I am not sure that I understand why _cmp_ needs less coercion than _richcmp_.

[vdelecroix]

Another example: embedded number fields in RR. If you want that rich comparisons coincide with the order on RR then == and != are cheap but not <, <=, > and >=.

Do you agree with the new description?

[vdelecroix]

I was able to modify six Python elements to use coercion for their comparisons. The code is simplified.

In order to do that, I had to modify slightly the implementation of _richcmp to not catch a TypeError when it calls _richcmp_. We should precise what elements should do when == and != makes sense but not <, <=, >=, >. Is TypeError appropriate?

Vincent

---

Last 10 new commits:

​04570b3	Fix bad doctest in etaproducts
​3976f2c	Add pointers for special uses of __richcmp__
​ce7e4f1	merge u/jdemeyer/ticket/17890 in Sage-6.7.beta3
​203820b	Trac 18305: py_rich_to_bool(_sgn) and operators
​c6d3e23	Trac 18305: use `_cmp_` for alternating sign matrices
​f3e46e3	Trac 18305: use _cmp_ for ideals of finite dimensional algebras
​b0c39b0	Trac 18305: _richcmp_ for indexed monoids and groups
​220a140	Trac 18305: _richcmp_ for Newton polygons
​042b6fe	Trac 18305: modify Element._richcmp so that _richcmp_ can raise errors
​7749fe8	Trac 18305: _richcmp_ for `finite dimensional algebra elements

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​81be759

Trac 18305: update comments in sage.structure.element

[jdemeyer]

I plan to have a look at this when #17890 is merged. I would also like to have some feedback on #18322, since both this ticket and #18322 change Element.

[vdelecroix]

Replying to jdemeyer:

I plan to have a look at this when #17890 is merged. I would also like to have some feedback on #18322, since both this ticket and #18322 change Element.

Perhaps I should set #18322 as a dependency? I do not think that there will be any conflict since nothing in Sage explicitely uses cmp (except doctests).

Vincent

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​b70f3f2	Trac 18305: py_rich_to_bool(_sgn) and operators
​2edd0d4	Trac 18305: use `_cmp_` for alternating sign matrices
​240ba64	Trac 18305: use _cmp_ for ideals of finite dimensional algebras
​7bccbcc	Trac 18305: _richcmp_ for indexed monoids and groups
​4663b80	Trac 18305: _richcmp_ for Newton polygons
​06e05f2	Trac 18305: modify Element._richcmp so that _richcmp_ can raise errors
​9ad4257	Trac 18305: _richcmp_ for `finite dimensional algebra elements
​df2b501	Trac 18305: update comments in sage.structure.element

[vdelecroix]

Rebase on sage-6.7.beta4

[jdemeyer]

Replying to vdelecroix:

​042b6fe

Trac 18305: modify Element._richcmp so that _richcmp_ can raise errors

I moved this to #18322 since I think it fits better there.

[vdelecroix]

Replying to jdemeyer:

Replying to vdelecroix:

​042b6fe

Trac 18305: modify Element._richcmp so that _richcmp_ can raise errors

I moved this to #18322 since I think it fits better there.

Good to me.

[jdemeyer]

About this ticket: I don't really like that you're making major unrelated changes, for example (but not only) in alternating sign matrices. Do you really need that? Could those changes be moved to a different ticket?

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​bb98fd0	_cmp should try _richcmp_ if _cmp_ failed
​d826520	Use LazyFormat for _cmp_ exception
​ac9ca1c	Update comment
​89d1b0b	Trac 18305: py_rich_to_bool(_sgn) and operators
​1078589	Trac 18305: use _cmp_ for ideals of finite dimensional algebras
​7f6c59f	Trac 18305: _richcmp_ for indexed monoids and groups
​0fb7c8e	Trac 18305: _richcmp_ for Newton polygons
​51abce8	Trac 18305: _richcmp_ for `finite dimensional algebra elements
​0259eb7	Trac 18305: update comments in sage.structure.element

[vdelecroix]

Rebased above #18322.

The alternating sign matrices is now #18383. What are the other "major unrelated changes"?

[jdemeyer]

I think having both py_rich_to_bool_sgn and py_rich_to_bool in Python is overkill. Since these are Python functions anyway, the overhead of the _sgn variant can be ignored.

And I don't like most of your comment changes to src/sage/structure/element.pyx: if you implement just _richcmp_, then you don't need __cmp__, not even for cmp(). Why did you remove or if that gives better performance. And the and are not identical (i.e. self is not other). addition is also wrong I think.

[jdemeyer]

Also, there is no need for the int in

def py_rich_to_bool_sgn(int op, int c)

(if we ever change the prototype of rich_to_bool_sgn, there is additional work for no reason)

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​c78d7ce	Trac 18305: py_rich_to_bool(_sgn) and operators
​1bc5ee9	Trac 18305: use _cmp_ for ideals of finite dimensional algebras
​71409ec	Trac 18305: _richcmp_ for indexed monoids and groups
​fc3b7a1	Trac 18305: _richcmp_ for Newton polygons
​17e7496	Trac 18305: _richcmp_ for `finite dimensional algebra elements
​17ed549	Trac #18305: comments about Python comparisons

[vdelecroix]

Rebased on 6.8.beta0.

I took care of your comments.

Vincent

[chapoton]

does not apply, needs rebase

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​522d61f	Trac 18305: py_rich_to_bool(_sgn) and operators
​6089576	Trac 18305: use _cmp_ for ideals of finite dimensional algebras
​2cc324c	Trac 18305: _richcmp_ for indexed monoids and groups
​88fd79e	Trac 18305: _richcmp_ for Newton polygons
​690b959	Trac 18305: _richcmp_ for `finite dimensional algebra elements
​d768d25	Trac #18305: comments about Python comparisons

[vdelecroix]

rebased on sage-6.9.beta1

[jdemeyer]

See also #19108 which solves the same problem in a different (more complicated) way.

[jdemeyer]

Can you split off the changes to src/sage/algebras to a different ticket?

[jdemeyer]

Replace

If you need to call this function from Cython prefer

by

Do not use this function from Cython. Instead, call

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​a9283cb	Trac 18305: py_rich_to_bool(_sgn) and operators
​e8b8182	Trac 18305: _richcmp_ for indexed monoids and groups
​950f3ec	Trac 18305: _richcmp_ for Newton polygons
​490de42	Trac 18305: comments about Python comparisons
​3f6ea84	Trac 18305: rephrased sentence in doc

[vdelecroix]

Replying to jdemeyer:

Can you split off the changes to src/sage/algebras to a different ticket?

It is now #19170

[jdemeyer]

This is not good, you're adding back stuff which was removed:

src/sage/structure/element.pyx

@@ -1043 +1043 @@
             return rich_to_bool(op, -1)
 
     ####################################################################
-    # For a Cython class, you must define either _cmp_ (if your subclass
-    # is totally ordered), _richcmp_ (if your subclass is partially
-    # ordered), or both (if your class has both a total order and a
-    # partial order, or if implementing both gives better performance).
+    # For a derived Cython class, you **must** put the __richcmp__
+    # method below in your subclasses, in order for it to take
+    # advantage of the above generic comparison code. If you want to use cmp()
+    # but did not implement a rich comparison, then you must copy paste the
+    # __cmp__ method below.
+    #
+    # In a Cython or a Python class, you must define either _cmp_
+    # (if your subclass is totally ordered), _richcmp_ (if your subclass
+    # is partially ordered), or both (if your class has both a total order
+    # and a partial order, or if that gives better performance).
     #
     # Rich comparisons (like a < b) will default to using _richcmp_,
     # three-way comparisons (like cmp(a,b)) will default to using

[jdemeyer]

Py_EQ should be op_EQ here:

    INPUT:

    - ``op`` -- a rich comparison operation (e.g. ``Py_EQ``)

c can be any integer, not only -1, 0 or 1:

    - ``c`` -- the result of an ordinary comparison: -1, 0 or 1.

No trailing slash needed:

        sage: from sage.structure.sage_object import (py_rich_to_bool, \
        ....:    op_EQ, op_NE, op_LT, op_LE, op_GT, op_GE)

[jdemeyer]

Please keep the doctests for IndexedMonoidElement.__ne__ like you did for the other comparisons.

[jdemeyer]

$ pyflakes src/sage/geometry/newton_polygon.py
src/sage/geometry/newton_polygon.py:20: 'op_GT' imported but unused
src/sage/geometry/newton_polygon.py:20: 'py_rich_to_bool' imported but unused

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​3959aad	Trac 18305: py_rich_to_bool(_sgn) and operators
​6be9889	Trac 18305: _richcmp_ for indexed monoids and groups
​f3450e0	Trac 18305: _richcmp_ for Newton polygons
​0ee1f3a	Trac 18305: comments about Python comparisons

[vdelecroix]

Hello Jeroen,

I rebased on the latest beta taking care of all your remarks.

Vincent

[jdemeyer]

Replying to vdelecroix:

I rebased on the latest beta taking care of all your remarks.

General comment: you should not rebase a branch which is being reviewed. For example, it is difficult for me to see what you changed since last time, which essentially forces me to re-review everything again.

[vdelecroix]

If you tell me, I can move back my changes on top of the previous commits. Sorry.

[vdelecroix]

Thanks Jeroen. And again, I am sorry for the too early rebase.

Vincent

[jdemeyer]

Replying to vdelecroix:

Thanks Jeroen. And again, I am sorry for the too early rebase.

Why "too early"? I don't think a ticket under review should be rebased at all.

Rebasing before review is fine for me.