Opened 7 years ago

Closed 6 years ago

#18305 closed enhancement (fixed)

Element comparison for Python classes

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.9
Component: coercion Keywords:
Cc: jdemeyer, jpflori Merged in:
Authors: Vincent Delecroix Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: 0ee1f3a (Commits, GitHub, GitLab) Commit: 0ee1f3a96c0db1834efe22def0c2556b9e83355b
Dependencies: Stopgaps:

Status badges

Description (last modified by 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

Change History (43)

comment:1 follow-up: Changed 7 years ago by 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?

comment:2 in reply to: ↑ 1 Changed 7 years ago by 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_.

comment:3 Changed 7 years ago by vdelecroix

  • Description modified (diff)

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?

comment:4 follow-up: Changed 7 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Branch set to u/vdelecroix/18305
  • Commit set to 7749fe882a88d0978413e9c58b9d2660e0de23a6
  • Dependencies changed from #17890, #18303 to #17890
  • Description modified (diff)

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:

04570b3Fix bad doctest in etaproducts
3976f2cAdd pointers for special uses of __richcmp__
ce7e4f1merge u/jdemeyer/ticket/17890 in Sage-6.7.beta3
203820bTrac 18305: py_rich_to_bool(_sgn) and operators
c6d3e23Trac 18305: use `_cmp_` for alternating sign matrices
f3e46e3Trac 18305: use _cmp_ for ideals of finite dimensional algebras
b0c39b0Trac 18305: _richcmp_ for indexed monoids and groups
220a140Trac 18305: _richcmp_ for Newton polygons
042b6feTrac 18305: modify Element._richcmp so that _richcmp_ can raise errors
7749fe8Trac 18305: _richcmp_ for `finite dimensional algebra elements

comment:5 Changed 7 years ago by git

  • Commit changed from 7749fe882a88d0978413e9c58b9d2660e0de23a6 to 81be759f0e28dc13aa17e2f7df72bee0e729ee8f

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

81be759Trac 18305: update comments in sage.structure.element

comment:6 Changed 7 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from new to needs_review

comment:7 follow-up: Changed 7 years ago by 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.

comment:8 in reply to: ↑ 7 Changed 7 years ago by 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

comment:9 Changed 7 years ago by git

  • Commit changed from 81be759f0e28dc13aa17e2f7df72bee0e729ee8f to df2b501daa2d5b9ebde44d8e698f3d7f51228299

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

b70f3f2Trac 18305: py_rich_to_bool(_sgn) and operators
2edd0d4Trac 18305: use `_cmp_` for alternating sign matrices
240ba64Trac 18305: use _cmp_ for ideals of finite dimensional algebras
7bccbccTrac 18305: _richcmp_ for indexed monoids and groups
4663b80Trac 18305: _richcmp_ for Newton polygons
06e05f2Trac 18305: modify Element._richcmp so that _richcmp_ can raise errors
9ad4257Trac 18305: _richcmp_ for `finite dimensional algebra elements
df2b501Trac 18305: update comments in sage.structure.element

comment:10 Changed 7 years ago by vdelecroix

Rebase on sage-6.7.beta4

comment:11 Changed 7 years ago by vdelecroix

  • Dependencies #17890 deleted

comment:12 in reply to: ↑ 4 ; follow-up: Changed 7 years ago by jdemeyer

Replying to vdelecroix:

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

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

comment:13 in reply to: ↑ 12 Changed 7 years ago by vdelecroix

  • Dependencies set to #18322
  • Status changed from needs_review to needs_work

Replying to jdemeyer:

Replying to vdelecroix:

042b6feTrac 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.

comment:14 Changed 7 years ago by 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?

comment:15 Changed 7 years ago by git

  • Commit changed from df2b501daa2d5b9ebde44d8e698f3d7f51228299 to 0259eb7814ac159722db566fcd52c21e040cb233

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

bb98fd0_cmp should try _richcmp_ if _cmp_ failed
d826520Use LazyFormat for _cmp_ exception
ac9ca1cUpdate comment
89d1b0bTrac 18305: py_rich_to_bool(_sgn) and operators
1078589Trac 18305: use _cmp_ for ideals of finite dimensional algebras
7f6c59fTrac 18305: _richcmp_ for indexed monoids and groups
0fb7c8eTrac 18305: _richcmp_ for Newton polygons
51abce8Trac 18305: _richcmp_ for `finite dimensional algebra elements
0259eb7Trac 18305: update comments in sage.structure.element

comment:16 Changed 7 years ago by vdelecroix

Rebased above #18322.

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

comment:17 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:18 Changed 7 years ago by jpflori

  • Cc jpflori added

comment:19 Changed 7 years ago by 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.

comment:20 Changed 7 years ago by 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)

comment:21 Changed 7 years ago by git

  • Commit changed from 0259eb7814ac159722db566fcd52c21e040cb233 to 17ed5499a2113637034ffc8ef2210f949896e5c6

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

c78d7ceTrac 18305: py_rich_to_bool(_sgn) and operators
1bc5ee9Trac 18305: use _cmp_ for ideals of finite dimensional algebras
71409ecTrac 18305: _richcmp_ for indexed monoids and groups
fc3b7a1Trac 18305: _richcmp_ for Newton polygons
17e7496Trac 18305: _richcmp_ for `finite dimensional algebra elements
17ed549Trac #18305: comments about Python comparisons

comment:22 Changed 7 years ago by vdelecroix

  • Dependencies #18322 deleted
  • Description modified (diff)

Rebased on 6.8.beta0.

I took care of your comments.

Vincent

comment:23 Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

does not apply, needs rebase

comment:24 Changed 6 years ago by git

  • Commit changed from 17ed5499a2113637034ffc8ef2210f949896e5c6 to d768d2524b35e70345bf3b94392dd3e44ade9376

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

522d61fTrac 18305: py_rich_to_bool(_sgn) and operators
6089576Trac 18305: use _cmp_ for ideals of finite dimensional algebras
2cc324cTrac 18305: _richcmp_ for indexed monoids and groups
88fd79eTrac 18305: _richcmp_ for Newton polygons
690b959Trac 18305: _richcmp_ for `finite dimensional algebra elements
d768d25Trac #18305: comments about Python comparisons

comment:25 Changed 6 years ago by vdelecroix

  • Milestone changed from sage-6.7 to sage-6.9
  • Status changed from needs_work to needs_review

rebased on sage-6.9.beta1

comment:26 Changed 6 years ago by jdemeyer

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

comment:27 follow-up: Changed 6 years ago by jdemeyer

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

comment:28 Changed 6 years ago by jdemeyer

Replace

If you need to call this function from Cython prefer

by

Do not use this function from Cython. Instead, call

comment:29 Changed 6 years ago by git

  • Commit changed from d768d2524b35e70345bf3b94392dd3e44ade9376 to 3f6ea84eb645f1e29426bedc7763c9f31997867b

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

a9283cbTrac 18305: py_rich_to_bool(_sgn) and operators
e8b8182Trac 18305: _richcmp_ for indexed monoids and groups
950f3ecTrac 18305: _richcmp_ for Newton polygons
490de42Trac 18305: comments about Python comparisons
3f6ea84Trac 18305: rephrased sentence in doc

comment:30 in reply to: ↑ 27 Changed 6 years ago by vdelecroix

Replying to jdemeyer:

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

It is now #19170

Last edited 6 years ago by vdelecroix (previous) (diff)

comment:31 Changed 6 years ago by jdemeyer

  • Status changed from needs_review to needs_work

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

  • src/sage/structure/element.pyx

    diff --git a/src/sage/structure/element.pyx b/src/sage/structure/element.pyx
    index ede0157..4208a50 100644
    a b cdef class Element(SageObject): 
    10431043            return rich_to_bool(op, -1)
    10441044
    10451045    ####################################################################
    1046     # For a Cython class, you must define either _cmp_ (if your subclass
    1047     # is totally ordered), _richcmp_ (if your subclass is partially
    1048     # ordered), or both (if your class has both a total order and a
    1049     # partial order, or if implementing both gives better performance).
     1046    # For a derived Cython class, you **must** put the __richcmp__
     1047    # method below in your subclasses, in order for it to take
     1048    # advantage of the above generic comparison code. If you want to use cmp()
     1049    # but did not implement a rich comparison, then you must copy paste the
     1050    # __cmp__ method below.
     1051    #
     1052    # In a Cython or a Python class, you must define either _cmp_
     1053    # (if your subclass is totally ordered), _richcmp_ (if your subclass
     1054    # is partially ordered), or both (if your class has both a total order
     1055    # and a partial order, or if that gives better performance).
    10501056    #
    10511057    # Rich comparisons (like a < b) will default to using _richcmp_,
    10521058    # three-way comparisons (like cmp(a,b)) will default to using

comment:32 Changed 6 years ago by 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)

comment:33 Changed 6 years ago by jdemeyer

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

Last edited 6 years ago by jdemeyer (previous) (diff)

comment:34 Changed 6 years ago by 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

comment:35 Changed 6 years ago by git

  • Commit changed from 3f6ea84eb645f1e29426bedc7763c9f31997867b to 0ee1f3a96c0db1834efe22def0c2556b9e83355b

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

3959aadTrac 18305: py_rich_to_bool(_sgn) and operators
6be9889Trac 18305: _richcmp_ for indexed monoids and groups
f3450e0Trac 18305: _richcmp_ for Newton polygons
0ee1f3aTrac 18305: comments about Python comparisons

comment:36 follow-up: Changed 6 years ago by vdelecroix

Hello Jeroen,

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

Vincent

Last edited 6 years ago by vdelecroix (previous) (diff)

comment:37 Changed 6 years ago by vdelecroix

  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_work to needs_review

comment:38 in reply to: ↑ 36 Changed 6 years ago by 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.

comment:39 Changed 6 years ago by vdelecroix

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

comment:40 Changed 6 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:41 follow-up: Changed 6 years ago by vdelecroix

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

Vincent

comment:42 in reply to: ↑ 41 Changed 6 years ago by 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.

comment:43 Changed 6 years ago by vbraun

  • Branch changed from u/vdelecroix/18305 to 0ee1f3a96c0db1834efe22def0c2556b9e83355b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.