Opened 5 years ago

Closed 3 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) Commit: 07f12cdfd14f3a7af5445aab7419c0ddaea1074d
Dependencies: Stopgaps:

Description (last modified by rws)

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 5 years ago by vbraun

  • Component changed from PLEASE CHANGE to symbolics
  • Description modified (diff)
  • Type changed from PLEASE CHANGE to defect

comment:2 Changed 5 years ago by vbraun

  • Description modified (diff)

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

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

comment:5 Changed 5 years ago by vbraun

  • Branch set to u/vbraun/symbolic_cmp

comment:6 Changed 5 years ago by vdelecroix

  • Cc vdelecroix added
  • Commit set to 62be17eb6eccffcddcc61e4f18a2123ec0c364d8

New commits:

62be17eprint_sorted and math_sorted utility functions

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:8 Changed 5 years ago by rws

  • Branch changed from u/vbraun/symbolic_cmp to u/rws/symbolic_cmp

comment:9 Changed 5 years ago by rws

  • 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:

215cff4Merge branch 'develop' into t/16397/symbolic_cmp
af5f80016397: use print_sorted() in two further places; fix doctest

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

Last edited 5 years ago by vbraun (previous) (diff)

comment:11 Changed 5 years ago by rws

Yes, it's a bit over my head.

comment:12 follow-up: Changed 4 years ago by kcrisman

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 4 years ago by 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.

comment:14 Changed 4 years ago by rws

  • Milestone changed from sage-6.4 to sage-6.6

comment:15 Changed 4 years ago by rws

  • Priority changed from major to critical

comment:16 Changed 4 years ago by rws

  • Description modified (diff)

comment:17 Changed 4 years ago by mmezzarobba

  • Cc mmezzarobba added

comment:18 Changed 4 years ago by jpflori

  • Cc jpflori added

comment:19 Changed 4 years ago by rws

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

comment:20 Changed 4 years ago by rws

  • Branch u/rws/symbolic_cmp deleted
  • Commit af5f800fdc616022d503b5e845ec81ebfef7c25e deleted
  • Milestone changed from sage-6.6 to sage-6.10
  • Stopgaps set to #19465

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__

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

comment:22 Changed 3 years ago by rws

  • Branch set to public/16397-1

comment:23 Changed 3 years ago by rws

  • Authors set to Volker Braun, Ralf Stephan
  • 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:

62be17eprint_sorted and math_sorted utility functions
8d8c774Merge remote-tracking branch 'trac/u/vbraun/symbolic_cmp' into symbcmp
215cff4Merge branch 'develop' into t/16397/symbolic_cmp
af5f80016397: use print_sorted() in two further places; fix doctest
f32de00Merge remote-tracking branch 'trac/u/rws/symbolic_cmp' into symbcmp
237c17emixed order comparison
c92ffbafix wrong doctest

comment:24 Changed 3 years ago by git

  • Commit changed from c92ffba371de028843bcbb08a7813fda95b9448a to 06ea5a9957bcfd03fa1476f7651b2d9400e9e36b

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

06ea5a9fix doctest

comment:25 Changed 3 years ago by rws

  • Description modified (diff)

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

comment:27 in reply to: ↑ 26 Changed 3 years ago by rws

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
Last edited 3 years ago by rws (previous) (diff)

comment:28 Changed 3 years ago by rws

  • Status changed from needs_review to needs_work

comment:29 Changed 3 years ago by git

  • Commit changed from 06ea5a9957bcfd03fa1476f7651b2d9400e9e36b to c78d15119bf930af733b831bc83b54c40c56f800

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

c78d151add Constant.__lt__

comment:30 Changed 3 years ago by git

  • Commit changed from c78d15119bf930af733b831bc83b54c40c56f800 to 1381a89d5e960afb76815f85e771f71f99a3d1c1

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

1381a8916397: add tests

comment:31 Changed 3 years ago by rws

  • Status changed from needs_work to needs_review

comment:32 Changed 3 years ago by git

  • Commit changed from 1381a89d5e960afb76815f85e771f71f99a3d1c1 to 60370a98cc7b77a1c0884066dcc57d193dcf9a6c

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

585ceb8Merge branch 'develop' into symbcmp
60370a916397: fix typo

comment:33 Changed 3 years ago by rws

  • 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 3 years ago by dimpase

hmm, patchbots are still not happy...

comment:35 Changed 3 years ago by rws

That was a blind merge of develop, sigh.

comment:36 Changed 3 years ago by git

  • Commit changed from 60370a98cc7b77a1c0884066dcc57d193dcf9a6c to eab9ec2ce8ce805441543ffcbebcdf5fb527a2cb

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

f78854cfix depecrated import of python.pxi
eab9ec216397: fix doctest

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

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

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

Last edited 3 years ago by dimpase (previous) (diff)

comment:40 in reply to: ↑ 39 Changed 3 years ago by 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.

comment:41 Changed 3 years ago by git

  • Commit changed from eab9ec2ce8ce805441543ffcbebcdf5fb527a2cb to 07f12cdfd14f3a7af5445aab7419c0ddaea1074d

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

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

comment:42 Changed 3 years ago by 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]

Last edited 3 years ago by rws (previous) (diff)

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

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

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

comment:46 Changed 3 years ago by 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.)

Last edited 3 years ago by mmezzarobba (previous) (diff)

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

comment:48 in reply to: ↑ 47 Changed 3 years ago by 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.

comment:49 in reply to: ↑ 47 Changed 3 years ago by 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).

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

comment:51 in reply to: ↑ 50 Changed 3 years ago by 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.

comment:52 Changed 3 years ago by vbraun

  • 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 3 years ago by vbraun

  • Branch changed from public/16397-1 to 07f12cdfd14f3a7af5445aab7419c0ddaea1074d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.