Opened 8 years ago
Closed 6 years ago
#16397 closed defect (fixed)
Symbolic cmp
Reported by:  vbraun  Owned by:  

Priority:  critical  Milestone:  sage7.1 
Component:  symbolics  Keywords:  
Cc:  vdelecroix, mmezzarobba, jpflori  Merged in:  
Authors:  Volker Braun, Ralf Stephan  Reviewers:  Ralf Stephan, Volker Braun 
Report Upstream:  N/A  Work issues:  
Branch:  07f12cd (Commits, GitHub, GitLab)  Commit:  07f12cdfd14f3a7af5445aab7419c0ddaea1074d 
Dependencies:  Stopgaps: 
Description (last modified by )
In the symbolic ring, cmp implements the print comparison which is probably not what you envisioned:
sage: cmp(1, sqrt(2)) # mathematically correct, uses rich comparison 1 sage: cmp(SR(1), sqrt(2)) # unexpectedly, you get the print sort order 1 sage: cmp(log(8), 3*log(2)) 1
Everybody who coerces to same parents internally before comparing trips over this, for example the real lazy field:
sage: RLF(1) < RLF(sqrt(2)) False
This also makes RealSet
unusable with symbolics:
sage: RealSet((0, pi),[pi, pi],(pi,4)) [pi, 4) sage: RealSet((0, pi),[0, pi],(pi,4)) [pi, 4) sage: RealSet((0, pi),[0, 3.5],(pi,4)) (pi, 4)
Change History (53)
comment:1 Changed 8 years ago by
 Component changed from PLEASE CHANGE to symbolics
 Description modified (diff)
 Type changed from PLEASE CHANGE to defect
comment:2 Changed 8 years ago by
 Description modified (diff)
comment:3 Changed 8 years ago by
comment:4 Changed 8 years ago by
Yes, thats what I'm thinking as well. I'll write a print_order
function and see if I can get rid of all cmp calls...
comment:5 Changed 8 years ago by
 Branch set to u/vbraun/symbolic_cmp
comment:6 Changed 8 years ago by
 Cc vdelecroix added
 Commit set to 62be17eb6eccffcddcc61e4f18a2123ec0c364d8
New commits:
62be17e  print_sorted and math_sorted utility functions

comment:7 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:8 Changed 7 years ago by
 Branch changed from u/vbraun/symbolic_cmp to u/rws/symbolic_cmp
comment:9 Changed 7 years ago by
 Commit changed from 62be17eb6eccffcddcc61e4f18a2123ec0c364d8 to af5f800fdc616022d503b5e845ec81ebfef7c25e
Trying to push this ticket a bit. I also found this cmp
call:
File "matrix_integer_dense.pyx", line 604, in sage.matrix.matrix_integer_dense.Matrix_integer_dense.__richcmp__ (build/cythonized/sage/matrix/matrix_integer_dense.c:9503) File "element.pyx", line 873, in sage.structure.element.Element._richcmp (build/cythonized/sage/structure/element.c:8891) File "element.pyx", line 855, in sage.structure.element.Element._richcmp_ (build/cythonized/sage/structure/element.c:8615) File "element.pyx", line 902, in sage.structure.element.Element._richcmp (build/cythonized/sage/structure/element.c:9316) File "element.pyx", line 949, in sage.structure.element.Element._richcmp_c_impl (build/cythonized/sage/structure/element.c:9645) File "matrix_dense.pyx", line 126, in sage.matrix.matrix_dense.Matrix_dense._cmp_c_impl (build/cythonized/sage/matrix/matrix_dense.c:3092) File "expression.pyx", line 3066, in sage.symbolic.expression.Expression.__cmp__ (build/cythonized/sage/symbolic/expression.cpp:16865)
Do I understand it right that this should call math_sorted
instead of cmp
?
New commits:
215cff4  Merge branch 'develop' into t/16397/symbolic_cmp

af5f800  16397: use print_sorted() in two further places; fix doctest

comment:10 Changed 7 years ago by
The problem is IMHO what to do with Python 3. Sure we can play the two different comparisons (cmp vs. rich) in Python 2 against each other, but in Py3 there will be only one comparison. So either
 Comparison is always symbolic, and sorting will have to call
__bool__
on the symbolic inequalities. We then need to make that a total order instead of returningFalse
all the time. Slow.  Comparison is never symbolic, and you need to call
x.symbolic_less(y)
. Could be beautified by the preparser. The actual comparison returns the internal term order. Fast.
Thought? Maybe that topic is more fodder for sagedevel...
comment:11 Changed 7 years ago by
Yes, it's a bit over my head.
comment:12 followup: ↓ 13 Changed 7 years ago by
Was there ever any consensus on sagedevel on this? I'm leaning toward the first option, but not strongly.
comment:13 in reply to: ↑ 12 Changed 7 years ago by
Replying to kcrisman:
Was there ever any consensus on sagedevel on this? I'm leaning toward the first option, but not strongly.
You probably mean https://groups.google.com/forum/?hl=en#!searchin/sagedevel/cmp/sagedevel/092yBmHfXQo/4qfS_JHLJdwJ and #16537, #17175. The newsgroup thread is mainly about equality/hashing and a bit of richcmp, not the two choices above. I am just starting to read about this.
comment:14 Changed 7 years ago by
 Milestone changed from sage6.4 to sage6.6
comment:15 Changed 7 years ago by
 Priority changed from major to critical
comment:16 Changed 7 years ago by
 Description modified (diff)
comment:17 Changed 7 years ago by
 Cc mmezzarobba added
comment:18 Changed 7 years ago by
 Cc jpflori added
comment:19 Changed 6 years ago by
When #19040 is done __cmp__
could simply delegate to __nonzero__
.
comment:20 Changed 6 years ago by
 Branch u/rws/symbolic_cmp deleted
 Commit af5f800fdc616022d503b5e845ec81ebfef7c25e deleted
 Milestone changed from sage6.6 to sage6.10
 Stopgaps set to #19465
comment:21 Changed 6 years ago by
There is also a more minimal solution (part of #19040): scan the expression, if it contains variables use print order, if not use math order.
comment:22 Changed 6 years ago by
 Branch set to public/163971
comment:23 Changed 6 years ago by
 Commit set to c92ffba371de028843bcbb08a7813fda95b9448a
 Milestone changed from sage6.10 to sage7.1
 Status changed from new to needs_review
With this we introduce a mixed sort key for symbolics which is numerically correct and symbolically fast. This is part of the work on #19040 and adds to/benefits from Volker's abstraction of orders of comparison.
New commits:
62be17e  print_sorted and math_sorted utility functions

8d8c774  Merge remotetracking branch 'trac/u/vbraun/symbolic_cmp' into symbcmp

215cff4  Merge branch 'develop' into t/16397/symbolic_cmp

af5f800  16397: use print_sorted() in two further places; fix doctest

f32de00  Merge remotetracking branch 'trac/u/rws/symbolic_cmp' into symbcmp

237c17e  mixed order comparison

c92ffba  fix wrong doctest

comment:24 Changed 6 years ago by
 Commit changed from c92ffba371de028843bcbb08a7813fda95b9448a to 06ea5a9957bcfd03fa1476f7651b2d9400e9e36b
Branch pushed to git repo; I updated commit sha1. New commits:
06ea5a9  fix doctest

comment:25 Changed 6 years ago by
 Description modified (diff)
comment:26 followup: ↓ 27 Changed 6 years ago by
The results for the RealSet
examples would be at the moment:
sage: RealSet((0, pi),[pi, pi],(pi,4)) [pi, 0) + (pi, 4) sage: RealSet((0, pi),[0, pi],(pi,4)) [pi, 0] + (pi, 0) + (pi, 4) sage: RealSet((0, pi),[0, 3.5],(pi,4)) (pi, 4)
comment:27 in reply to: ↑ 26 Changed 6 years ago by
So there is still
sage: cmp(pi,0) 1 sage: cmp(pi,SR(0)) 1 sage: cmp(0,pi) 1 sage: cmp(SR(0),pi) 1
comment:28 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:29 Changed 6 years ago by
 Commit changed from 06ea5a9957bcfd03fa1476f7651b2d9400e9e36b to c78d15119bf930af733b831bc83b54c40c56f800
Branch pushed to git repo; I updated commit sha1. New commits:
c78d151  add Constant.__lt__

comment:30 Changed 6 years ago by
 Commit changed from c78d15119bf930af733b831bc83b54c40c56f800 to 1381a89d5e960afb76815f85e771f71f99a3d1c1
Branch pushed to git repo; I updated commit sha1. New commits:
1381a89  16397: add tests

comment:31 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:32 Changed 6 years ago by
 Commit changed from 1381a89d5e960afb76815f85e771f71f99a3d1c1 to 60370a98cc7b77a1c0884066dcc57d193dcf9a6c
comment:33 Changed 6 years ago by
 Reviewers set to Ralf Stephan
 Stopgaps #19465 deleted
Consider the commit by Volker Braun (the first) reviewed by me. Please review everything else.
comment:34 Changed 6 years ago by
hmm, patchbots are still not happy...
comment:35 Changed 6 years ago by
That was a blind merge of develop, sigh.
comment:36 Changed 6 years ago by
 Commit changed from 60370a98cc7b77a1c0884066dcc57d193dcf9a6c to eab9ec2ce8ce805441543ffcbebcdf5fb527a2cb
comment:37 Changed 6 years ago by
It is interesting to see from the remaining fail in random_test
that print order itself is a buggy concept: it either makes incorrect comparisons (e>SR(0)
False) or fail transitivity if this is fixed in mixed order ((x>e,e>SR(0),x>SR(0)) > (True,True,False)
). So, mixed order in the present form would be no longer transitive.
comment:38 Changed 6 years ago by
Effectively the only way to refine comparison then is by introducing a None
result which would exclude the above case from being flagged. Opinions would be very welcome.
comment:39 followup: ↓ 40 Changed 6 years ago by
perhaps someone should have a look at interfaces/mathematica.py where one has __cmp__
for Mathematica objects, returning 1 if it falls through. Another bug? (cf. #18888)
comment:40 in reply to: ↑ 39 Changed 6 years ago by
comment:41 Changed 6 years ago by
 Commit changed from eab9ec2ce8ce805441543ffcbebcdf5fb527a2cb to 07f12cdfd14f3a7af5445aab7419c0ddaea1074d
comment:42 Changed 6 years ago by
This restores transitivity by moving all expressions with variables to the right of all the numbers in a sorted list: [1, sqrt(2), e, pi, sin(1/x), sqrt(x), x]
comment:43 Changed 6 years ago by
Isn't it dangerous to compare constants by float, this will go wrong because of rounding when you have equal or near equal numbers.
comment:44 Changed 6 years ago by
How about extending constants with an evalf
member so that in comparisons the precision can be successively increased. Reaching the prec limit before a decision will return 0, ie equal.
Isn't this quite hypothetical, compared to the concretely buggy behaviour now?
comment:45 Changed 6 years ago by
Its perhaps not that hypothetical, the old joke (aka Heegner number)
$ python >>> from math import exp, pi, sqrt >>> exp(pi*sqrt(163)) == 262537412640768256 True
comes to mind. But I agree that this could be tackled on a future ticket.
comment:46 Changed 6 years ago by
I don't understand what you are trying to do here, can someone please explain?
(In my understanding, calling cmp
means you are asking for a total order on the elements of the parent where the comparison ends up taking place. As most parents don't admit such an order that is compatible with their structure, it is a bug to call cmp
and expect a mathematically meaningful answer. In contrast, it is perfectly okay for cmp
to implement any arbitrary total order, provided that rich comparisons are implemented too. And it is acceptable, though not ideal due to the issues with Python3, to call cmp
when you need to sort elements in an arbitrary way.)
comment:47 followups: ↓ 48 ↓ 49 Changed 6 years ago by
At the moment there is one total order (print, mathematically wrong both in expressions with and without variables). Total math order OTOH is slow because of proving and undecidable. It is possible to have two total orders sidebyside where one half (within the set of expressions without variables) is fast, correct, and meaningful; and print order (within and with the set of expressions with variables) is fast as usual.
It is needed because cmp
is used in Sage to sort expressions in a meaningful way, contrary to what you state.
comment:48 in reply to: ↑ 47 Changed 6 years ago by
Replying to rws:
It is needed because
cmp
is used in Sage to sort expressions in a meaningful way, contrary to what you state.
I'm not saying that it is not used that way, I am saying that, as far as I understand, when it is used that way, the bug is there.
comment:49 in reply to: ↑ 47 Changed 6 years ago by
Replying to rws:
It is possible to have two total orders sidebyside where one half (within the set of expressions without variables) is fast, correct, and meaningful
It will never be correct in the sense that you can rely on it in mathematical algorithms, since the zero test for constant symbolic expressions is undecidable. At best it will be a nice and natural print order. Which is not a bad thing, but I don't understand if that's the goal of this ticket (and, if not, what the goal is).
comment:50 followup: ↓ 51 Changed 6 years ago by
Look at the ticket description. The goal is to fix those errors. If that means to remove the usage of cmp
in those parts of Sage, then please say so. I'm not a Python guy and am not in the know what cmp
is supposed to do. I want to fix those pesky errors that block the new piecewise functions for years now.
comment:51 in reply to: ↑ 50 Changed 6 years ago by
Replying to rws:
Look at the ticket description. The goal is to fix those errors. If that means to remove the usage of
cmp
in those parts of Sage, then please say so.
I don't know. I tried to explain what I believe is the convention used in sage (or perhaps the most reasonable of several incompatible conventions currently in use), but I'm genuinely interested in knowing if other people agree.
comment:52 Changed 6 years ago by
 Reviewers changed from Ralf Stephan to Ralf Stephan, Volker Braun
 Status changed from needs_review to positive_review
Better than what we currently have...
comment:53 Changed 6 years ago by
 Branch changed from public/163971 to 07f12cdfd14f3a7af5445aab7419c0ddaea1074d
 Resolution set to fixed
 Status changed from positive_review to closed
I can see how that might be surprising. :)
IIRC, that was a conscious decision to expose the print order from Pynac to Python/Sage to be used for sorting lists, etc. where symbolic expressions occur. I guess many places in the code call
cmp()
instead of using the comparison operators.We would need to get rid of this design for Python 3 compatibility anyway. Shall we remove support for
cmp()
and change all places where lists are returned from symbolics to explicitly call the print order?