Opened 7 years ago
Closed 5 years ago
#16397 closed defect (fixed)
Symbolic cmp
Reported by: | vbraun | Owned by: | |
---|---|---|---|
Priority: | critical | Milestone: | sage-7.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 7 years ago by
- Component changed from PLEASE CHANGE to symbolics
- Description modified (diff)
- Type changed from PLEASE CHANGE to defect
comment:2 Changed 7 years ago by
- Description modified (diff)
comment:3 Changed 7 years ago by
comment:4 Changed 7 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 7 years ago by
- Branch set to u/vbraun/symbolic_cmp
comment:6 Changed 7 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 sage-6.3 to sage-6.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 sage-devel...
comment:11 Changed 7 years ago by
Yes, it's a bit over my head.
comment:12 follow-up: ↓ 13 Changed 6 years ago by
Was there ever any consensus on sage-devel on this? I'm leaning toward the first option, but not strongly.
comment:13 in reply to: ↑ 12 Changed 6 years ago by
Replying to kcrisman:
Was there ever any consensus on sage-devel on this? I'm leaning toward the first option, but not strongly.
You probably mean https://groups.google.com/forum/?hl=en#!searchin/sage-devel/cmp/sage-devel/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 6 years ago by
- Milestone changed from sage-6.4 to sage-6.6
comment:15 Changed 6 years ago by
- Priority changed from major to critical
comment:16 Changed 6 years ago by
- Description modified (diff)
comment:17 Changed 6 years ago by
- Cc mmezzarobba added
comment:18 Changed 6 years ago by
- Cc jpflori added
comment:19 Changed 5 years ago by
When #19040 is done __cmp__
could simply delegate to __nonzero__
.
comment:20 Changed 5 years ago by
- Branch u/rws/symbolic_cmp deleted
- Commit af5f800fdc616022d503b5e845ec81ebfef7c25e deleted
- Milestone changed from sage-6.6 to sage-6.10
- Stopgaps set to #19465
comment:21 Changed 5 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 5 years ago by
- Branch set to public/16397-1
comment:23 Changed 5 years ago by
- Commit set to c92ffba371de028843bcbb08a7813fda95b9448a
- Milestone changed from sage-6.10 to sage-7.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 remote-tracking 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 remote-tracking branch 'trac/u/rws/symbolic_cmp' into symbcmp
|
237c17e | mixed order comparison
|
c92ffba | fix wrong doctest
|
comment:24 Changed 5 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 5 years ago by
- Description modified (diff)
comment:26 follow-up: ↓ 27 Changed 5 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 5 years ago by
So there is still
sage: cmp(pi,0) 1 sage: cmp(pi,SR(0)) -1
comment:28 Changed 5 years ago by
- Status changed from needs_review to needs_work
comment:29 Changed 5 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 5 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 5 years ago by
- Status changed from needs_work to needs_review
comment:32 Changed 5 years ago by
- Commit changed from 1381a89d5e960afb76815f85e771f71f99a3d1c1 to 60370a98cc7b77a1c0884066dcc57d193dcf9a6c
comment:33 Changed 5 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 5 years ago by
hmm, patchbots are still not happy...
comment:35 Changed 5 years ago by
That was a blind merge of develop, sigh.
comment:36 Changed 5 years ago by
- Commit changed from 60370a98cc7b77a1c0884066dcc57d193dcf9a6c to eab9ec2ce8ce805441543ffcbebcdf5fb527a2cb
comment:37 Changed 5 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 5 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 follow-up: ↓ 40 Changed 5 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 5 years ago by
comment:41 Changed 5 years ago by
- Commit changed from eab9ec2ce8ce805441543ffcbebcdf5fb527a2cb to 07f12cdfd14f3a7af5445aab7419c0ddaea1074d
comment:42 Changed 5 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 5 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 5 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 5 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 5 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 follow-ups: ↓ 48 ↓ 49 Changed 5 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 side-by-side 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 5 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 5 years ago by
Replying to rws:
It is possible to have two total orders side-by-side 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 follow-up: ↓ 51 Changed 5 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 5 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 5 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 5 years ago by
- Branch changed from public/16397-1 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?