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)

[burcin]

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]

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

[vdelecroix]

New commits:

​62be17e

print_sorted and math_sorted utility functions

[rws]

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

[vbraun]

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

[rws]

Yes, it's a bit over my head.

[kcrisman]

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

[rws]

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.

[rws]

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

[rws]

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 #19312
2. merge #19040 using the u/rws/19312-1 branch of #19312
3. using __nonzero__ to implement __cmp__

[rws]

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.

[rws]

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

[git]

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

​06ea5a9

fix doctest

[rws]

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)

[rws]

So there is still

sage: cmp(pi,0)
1
sage: cmp(pi,SR(0))
-1

[git]

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

​c78d151

add Constant.__lt__

[git]

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

​1381a89

16397: add tests

[git]

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

​585ceb8	Merge branch 'develop' into symbcmp
​60370a9	16397: fix typo

[rws]

Consider the commit by Volker Braun (the first) reviewed by me. Please review everything else.

[dimpase]

hmm, patchbots are still not happy...

[rws]

That was a blind merge of develop, sigh.

[git]

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

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

[rws]

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.

[rws]

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]

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)

[rws]

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.

[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

[rws]

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]

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

[rws]

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]

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.

[mmezzarobba]

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

[rws]

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.

[mmezzarobba]

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.

[mmezzarobba]

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

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

[mmezzarobba]

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.

[vbraun]

Better than what we currently have...