Symbolic cmp

[vbraun]

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)

CC: @videlec @mezzarobba @jpflori

Component: symbolics

Author: Volker Braun, Ralf Stephan

Branch/Commit: 07f12cd

Reviewer: Ralf Stephan, Volker Braun

Issue created by migration from https://trac.sagemath.org/ticket/16397

[burcin]

comment:3

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?

[vbraun]

comment:4

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

[vbraun]

Branch: u/vbraun/symbolic_cmp

[videlec]

Commit: 62be17e

[videlec]

New commits:

62be17e

print_sorted and math_sorted utility functions

[rwst]

Changed branch from u/vbraun/symbolic_cmp to u/rws/symbolic_cmp

[rwst]

comment:9

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

[rwst]

Changed commit from 62be17e to af5f800

[vbraun]

comment:10

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 returning False 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...

[rwst]

comment:11

Yes, it's a bit over my head.

[kcrisman]

comment:12

Was there ever any consensus on sage-devel on this? I'm leaning toward the first option, but not strongly.

[rwst]

comment:13

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.

[rwst]

comment:19

When #19040 is done __cmp__ could simply delegate to __nonzero__.

[rwst]

Stopgaps: #19465

[rwst]

Changed branch from u/rws/symbolic_cmp to none

[rwst]

Changed commit from af5f800 to none

[rwst]

comment:20

The newest verson of #19040 is in the u/rws/19312-1 branch of #19312

So, the way to resolve this IMO would be to

1. merge Update to pynac-0.5.2 #19312
2. merge rewrite Expression.__nonzero__() #19040 using the u/rws/19312-1 branch of Update to pynac-0.5.2 #19312
3. using __nonzero__ to implement __cmp__

[dimpase]

comment:34

hmm, patchbots are still not happy...

[rwst]

comment:35

That was a blind merge of develop, sigh.

[sagetrac-git]

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

f78854c	fix depecrated import of python.pxi
eab9ec2	16397: fix doctest

[sagetrac-git]

Changed commit from 60370a9 to eab9ec2

[rwst]

comment:37

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.

[rwst]

comment:38

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.

[dimpase]

comment:39

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)

[rwst]

comment:40

Replying to @dimpase:

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)

Has nothing to do with this ticket.

[sagetrac-git]

Changed commit from eab9ec2 to 07f12cd

[sagetrac-git]

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

24450f8	Merge branch 'public/16397-1' of git://trac.sagemath.org/sage into tmp04
07f12cd	16397: restore transitivity

[rwst]

comment:42

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]

[vbraun]

comment:43

Isn't it dangerous to compare constants by float, this will go wrong because of rounding when you have equal or near equal numbers.

[rwst]

comment:44

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?

[vbraun]

comment:45

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.

[mezzarobba]

comment:46

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.)

[rwst]

comment:47

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.

[mezzarobba]

comment:48

Replying to @rwst:

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.

[mezzarobba]

comment:49

Replying to @rwst:

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).

[rwst]

comment:50

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.

[mezzarobba]

comment:51

Replying to @rwst:

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.

[vbraun]

comment:52

Better than what we currently have...

[vbraun]

Changed reviewer from Ralf Stephan to Ralf Stephan, Volker Braun

[vbraun]

Changed branch from public/16397-1 to 07f12cd