Cross-type comparisons

[Marc Mezzarobba]

Hi,

Does Element.__richcmp__() (via CoercionModel_cache_maps.richcmp())
really need to fall back on comparing by type/id when no common parent
is found? Since comparison operators are part of the coercion
framework, it would seem more sensible to raise an error.

Moreover, having an essentially arbitrary return value is dangerous,
because the user can easily mistake it for a mathematical result. My
immediate reason for asking this question is an example of this kind.
I'm trying to finally remove the coercions from floating-point parents
to interval parents (as discussed here long ago). But doing so would
cause comparisons such as RIF(-1,1) < RR(2) to return nonsensical
results, while they currently give the correct answer at least when the
floating-point operand is a constant (as opposed to the result of a
floating-point computation). (Now, I can perhaps think of ad-hoc fixes
that might be enough in this particular case, but I believe the issue
is more general.)

In contrast, the only reason I can see for this code path to exist in
the first place is that--if I understand right--Python calls
a.__richcmp__(), not a.__cmp__(), when cmp() is applied to objects a
and b whose common superclass does not implement __cmp__. Therefore,
one can end up in Element.__richcmp__() while comparing an Element to a
non-Element via cmp(). And unfortunately, there does not seem to be any
simple way to distinguish between this situation and calls to
__richcmp__() coming from comparison operators. Is this correct? Did I
miss another reason?

If that's really the main reason, I'd argue that having cmp() fail in
some cases is not as bad as having comparison operators return nonsense
on Elements. (Besides, all cases where this could be a problem will
have to be fixed anyway to port Sage to Python3, won't they?) What do
you think?

Note that as a middle ground, we could raise an error when coercion
fails with both operands being Elements, while still returning a result
at all costs when comparing an Element with a non-Element. However,
this wouldn't help in cases like RIF(-1, 1) < float(2).

It would also be safe--though not ideal--to keep returning False for
comparisons using ==, and sort-of-okay to return True when comparing
with !=. And, for example, the following patch, which also whitelists
comparisons with strings (because there are typically safe and seem to
be in wide use in combinat/) only leaves us with about 40 test failures
(many of which trivial).

@@ -1870,8 +1871,6 @@ cdef class
CoercionModel_cache_maps(CoercionModel):

(<Element>x)._parent.get_flag(Parent_richcmp_element_without_coercion))
return PyObject_RichCompare(x, y, op)

- # Comparing with coercion didn't work, try something else.
-
# Try y.__richcmp__(x, revop) where revop is the reversed
# operation (<= becomes >=).
# This only makes sense when y is not a Sage Element, otherwise
@@ -1883,18 +1882,23 @@ cdef class
CoercionModel_cache_maps(CoercionModel):
if res is not NotImplemented:
return res

- # Final attempt: compare by id()
- if (<unsigned long><PyObject*>x) >= (<unsigned
long><PyObject*>y):
- # It cannot happen that x is y, since they don't
- # have the same parent.
- return rich_to_bool(op, 1)
+ if op == Py_EQ:
+ return False
+ elif op == Py_NE:
+ return True
+ elif type(y) is str:
+ return rich_to_bool(op, cmp(type(x), type(y)))
else:
- return rich_to_bool(op, -1)
+ raise bin_op_exception(operator_object(op), x, y)

def _coercion_error(self, x, x_map, x_elt, y, y_map, y_elt):
"""
@@ -1924,3 +1928,18 @@ Original elements %r (parent %s) and %r
(parent %s) and maps
%s %r""" % (x_elt, y_elt, parent_c(x_elt), parent_c(y_elt),
x, parent_c(x), y, parent_c(y),
type(x_map), x_map, type(y_map), y_map))
+
+cdef object operator_object(int op):
+ if op == Py_LT:
+ return operator.lt
+ elif op == Py_LE:
+ return operator.le
+ elif op == Py_EQ:
+ return operator.eq
+ elif op == Py_NE:
+ return operator.ne
+ elif op == Py_GE:
+ return operator.ge
+ elif op == Py_GT:
+ return operator.gt

(By the way, does operator_object already exist somewhere?)

Thanks for your input,

--
Marc

[Frédéric Chapoton]

There is currently an effort being made (by me and a few referees) to get rid of cmp() in all pyx files. And the Element/Parent is one of the hardest cases remaining. Getting rid of all calls to cmp( ) is necessary for compatibility with python3. The intermediate objective is to be able to compile all cython files with py3. So at some point I am going to try to handle the very same problem your are asking about.

richcmp, when not knowing what to do, should most probably return NotImplemented

I do not think we should whitelist comparison with strings.

What do the mostly-trivial 40 test failures look like ?

Frederic

[Volker Braun]

In the Python3 spirit, it would be nice to get a type error instead of ordering by id:

$ python3

>>> 1 < 'a'

Traceback (most recent call last):

  File "<stdin>", line 1, in <module>

TypeError: unorderable types: int() < str()

The current behavior is certainly not great, and was just defaulted because thats what Python2 does.

[Marc Mezzarobba]

Frédéric Chapoton wrote:
> richcmp, when not knowing what to do, should most probably return
> NotImplemented

In the case of Element.__richcmp__: not when both operands are Elements,
IMO, but perhaps indeed when the other one is a non-Element.

> I do not think we should whitelist comparison with strings.

That was just an example of a temporary kludge that could make things
simpler :-)

> What do the mostly-trivial 40 test failures look like ?

I didn't keep the list, sorry. Quite a few duplicates from all the
translations of the part of the tutorial that explains comparisons with
coercions. Probably a lot of mixed-type lists to be sorted and the
like. And a few that might actually have been bugs, but I didn't look
closely.

--
Marc Mezzarobba

[Travis Scrimshaw]

On Sunday, December 4, 2016 at 1:59:00 PM UTC-6, Frédéric Chapoton wrote:

There is currently an effort being made (by me and a few referees) to get rid of cmp() in all pyx files. And the Element/Parent is one of the hardest cases remaining. Getting rid of all calls to cmp( ) is necessary for compatibility with python3. The intermediate objective is to be able to compile all cython files with py3. So at some point I am going to try to handle the very same problem your are asking about.

richcmp, when not knowing what to do, should most probably return NotImplemented

We need to be very careful about defining "not knowing". I (stongly) believe when the objects/types are incomparable (say the rings ZZ and QQ), then == should return False and != should return True. Subsequently, when there is no coercion between the parents, they should not raise an error.

Best,
Travis

[Marc Mezzarobba]

Travis Scrimshaw wrote:
> We need to be very careful about defining "not knowing". I (stongly)
> believe when the objects/types are incomparable (say the rings ZZ and
> QQ), then == should return False and != should return True.

Sorry, I don't understand your example: I think everyone agrees that
ZZ == QQ should be False, but many people think that ZZ(1) == QQ(1)
should be True (though I personally disagree), and my post only was
about Elements.

> Subsequently, when there is no coercion between the parents, they
> should not raise an error.

Regarding ==, I believe it is a matter of convenience and consistency.
Raising an error makes it easier to catch bugs, while returning False
when there is no coercion allows things like [a for a in [1, "banana"]
if a == 1].

Regarding !=, I am less convinced. Returning True would imply that the
objects are known to be different (as opposed to: not known to be
equal, in the case of ==), while the coercion may not be implemented
but otherwise make perfect sense.

And in any case, I don't see what else than raising an error we could do
in the case of <, <=, >, >=.

--
Marc

[Jeroen Demeyer]

On 2016-12-04 19:39, Marc Mezzarobba wrote:
> Hi,
>
> Does Element.__richcmp__() (via CoercionModel_cache_maps.richcmp())
> really need to fall back on comparing by type/id when no common parent
> is found?

No. As far as I know, It does so for historical reasons only. I am in
favour of making elements without a common parent uncomparable.

[Marc Mezzarobba]

Frédéric Chapoton wrote:
> There is currently an effort being made (by me and a few referees) to
> get rid of cmp() in all pyx files.

Is there already a replacement for cmp() in Sage (i.e., something that
allows one to sort arbitrary objects--say, for printing them--and calls
_cmp_() in the case of Elements)? If not, is there a plan to add one?

Thanks,

--
Marc

[Travis Scrimshaw]

> We need to be very careful about defining "not knowing". I (stongly)
> believe when the objects/types are incomparable (say the rings ZZ and
> QQ), then == should return False and != should return True.

Sorry, I don't understand your example: I think everyone agrees that
ZZ == QQ should be False, but many people think that ZZ(1) == QQ(1)
should be True (though I personally disagree), and my post only was
about Elements.

One potential side effect of what you're proposing is that ZZ == QQ should raise an error. How can we tell they are not equal? They are isomorphic as sets. ZZ is a subring of QQ and we could potentially test an infinite number of points and not find something distinct from QQ. What distinguishes them are their types (IntegerRing vs RationalField).

> Subsequently, when there is no coercion between the parents, they
> should not raise an error.

Regarding ==, I believe it is a matter of convenience and consistency.
Raising an error makes it easier to catch bugs, while returning False
when there is no coercion allows things like [a for a in [1, "banana"]
if a == 1].

It also makes it significantly harder to work with heterogeneous data and really doesn't do too much to catch bugs. You end up with more complicated code that has to often consider more cases. Suppose ZZ(1) == QQ(1) raises an error. Then you have to manually do coercions and make extra sure about your data types in a weakly typed language, which is really hard from my experience.

Regarding !=, I am less convinced. Returning True would imply that the
objects are known to be different (as opposed to: not known to be
equal, in the case of ==), while the coercion may not be implemented
but otherwise make perfect sense.

If the coercion is not implemented, then I would say that is a bug that would need to be fixed. However, that is a good point about != being not known to be == vs truly distinct. Although I would argue that not known to be equal is an equivalent problem to knowing to be distinct, and so the desire for an unknown result is good. Although it should not be an error.

And in any case, I don't see what else than raising an error we could do
in the case of <, <=, >, >=.

 Here I completely agree with raising an error as you need some sort of (canonical) (partial) order, to which there often is none.

Best,
Travis

[Thierry]

Note that there are not only "mathemathical" orderings, but also
"algorithmic" ones. It is useful (and i bet assumed in various Sage
algorithms) to be able to totally order any pair of Python objects, e.g.
when you want to traverse a graph, or even identify edges:

sage: Graph({2:['a']}).edges(labels=False)
[(2, 'a')]
sage: Graph({'a':[2]}).edges(labels=False)
[(2, 'a')]
sage: 2 < 'a'
True

I guess we can try to use equality test and `id()` for such a purpose, but
it might force us to change a lot of code.

Ciao,
Thierry


> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[Marc Mezzarobba]

Thierry wrote:
> Note that there are not only "mathemathical" orderings, but also
> "algorithmic" ones. It is useful (and i bet assumed in various Sage
> algorithms) to be able to totally order any pair of Python objects,
> e.g. when you want to traverse a graph, or even identify edges:
>
> sage: Graph({2:['a']}).edges(labels=False)
> [(2, 'a')]
> sage: Graph({'a':[2]}).edges(labels=False)
> [(2, 'a')]
> sage: 2 < 'a'
> True

Yes, but that's essentially the difference between comparison and cmp()
(at least in the current best practice as I understand it).

And indeed, when the order is not going to be presented to the user, it
is probably better to compare id()s in this case.

--
Marc

[Nils Bruin]

Yes, there is one in python in general. With

sort(<list>, key=str)

you'll be able to sort lists of all kinds of stuff. You can write your own key function if you need more sophisticated ordering. We could of course host some key functions as part of sage, but when this came up on https://trac.sagemath.org/ticket/20028 it didn't seem there was sufficient need for it.

[Marc Mezzarobba]

Nils Bruin wrote:
> Yes, there is one in python in general. With
>
> sort(<list>, key=str)
>
> you'll be able to sort lists of all kinds of stuff.

Well, sort(key=str) and sort(key=id) certainly help in many cases, but
they clearly don't suffice in general. Neither is able to use an order
defined by the common class when it exists, and key=str may be very
costly.

--
Marc

[Thierry]

Indeed, id() alone can not decide when two objects are equal, so there
should be at least one equality test before using id().

However, mixing the internal order of a common class when it exists
together with id() would loose the transitivity property, so i guess those
two kind of tests should remain separate.

Ciao,
Thierry


> --
> Marc

[Marc Mezzarobba]

Travis Scrimshaw wrote:
>> Sorry, I don't understand your example: I think everyone agrees that
>> ZZ == QQ should be False, but many people think that ZZ(1) == QQ(1)
>> should be True (though I personally disagree), and my post only was
>> about Elements.
>
> One potential side effect of what you're proposing is that ZZ == QQ
> should raise an error.

No, my suggestion is strictly about Elements. (And if we'll have lots of
deeper changes to make if we want objects that are both Parents and
Elements!)

>> > Subsequently, when there is no coercion between the parents, they
>> > should not raise an error.
>>
>> Regarding ==, I believe it is a matter of convenience and
>> consistency. Raising an error makes it easier to catch bugs, while
>> returning False when there is no coercion allows things like [a for a
>> in [1, "banana"] if a == 1].
>

> It also makes it *significantly* harder to work with heterogeneous

> data and really doesn't do too much to catch bugs. You end up with
> more complicated code that has to often consider more cases. Suppose
> ZZ(1) == QQ(1) raises an error. Then you have to manually do coercions
> and make extra sure about your data types in a weakly typed language,
> which is really hard from my experience.

From my POV, the two most consistent options would be:

- either comparison operators that don't perform any coercions (except
perhaps in an ad-hoc way between closely cooperating parents), respect
Python semantics (wrt hash() & co), and return False for Elements that
don't have the same parent,

- or operators that are part of the coercion framework, and raise an
error when they don't find a common parent.

In the case of equality, I think it is pretty clear that both variants
are useful and should exist in some form. The main question is which of
the two should correspond to the Python comparison operators.
Compatibility with Python collections and other non-Sage objects is a
strong argument in favor of the former. Ease of use in interactive
usage and backward compatibility are strong arguments in favor of the
latter.

That being said, I think it would be acceptable to special-case equality
even if it does use coercion and make it return False when coercion
fails.

> If the coercion is not implemented, then I would say that is a bug
> that would need to be fixed.

In easy cases, yes, but in some cases it may very well correspond to an
undecidable problem...

> However, that is a good point about !=
> being not known to be == vs truly distinct. Although I would argue
> that not known to be equal is an equivalent problem to knowing to be
> distinct, and so the desire for an unknown result is good. Although it
> should not be an error.

Wait. To make sure we understand each other: I'm not saying that the
error is here to indicate an unknown result. Since it is not possible
to implement a reasonable three-valued logic for programming in Python,
I think we should stick as much as possible to the convention
that "True means true, False means false or unknown" (that already is
the dominant one in Sage as far as I can tell), and that's why I'm
saying that having == return False when it should actually fail is more
acceptable that having != return True in the same situation.

--
Marc

[Marc Mezzarobba]

Thierry wrote:
> However, mixing the internal order of a common class when it exists
> together with id() would loose the transitivity property, so i guess
> those two kind of tests should remain separate.

I'm not sure I follow you: doesn't what cmp() does (if I understand
right: use the internal order when possible, otherwise sort by type and
refine by id) do the job? But then, of course, this behavior cannot be
implemented as a key function, only as a comparison function...

--
Marc

[Nils Bruin]

On Monday, December 5, 2016 at 9:15:50 AM UTC-8, Marc Mezzarobba wrote:

I'm not sure I follow you: doesn't what cmp() does (if I understand
right: use the internal order when possible, otherwise sort by type and
refine by id) do the job? But then, of course, this behavior cannot be
implemented as a key function, only as a comparison function...

There's a transform that allows you to implement any comparison via a key:

https://docs.python.org/2/library/functools.html#functools.cmp_to_key

See also

https://docs.python.org/3/howto/sorting.html#sortinghowto

for the straightforward implementation that allows you to implement whatever comparison you like.

(of course this all doesn't solve the fundamental difficulty that there isn't an ordering that is both total and intuitive/mathematically meaningful)

[Marc Mezzarobba]

Nils Bruin wrote:
> There's a transform that allows you to implement any comparison via a
> key:

[...]

> (of course this all doesn't solve the fundamental difficulty that
> there isn't an ordering that is both total and
> intuitive/mathematically meaningful)

Indeed--and regarding this, I'd be interested in your opinion about

https://trac.sagemath.org/ticket/22029#comment:5

--
Marc

[Marc Mezzarobba]

Jeroen Demeyer wrote:
>> Does Element.__richcmp__() (via CoercionModel_cache_maps.richcmp())
>> really need to fall back on comparing by type/id when no common
>> parent is found?
>
> No. As far as I know, It does so for historical reasons only. I am in
> favour of making elements without a common parent uncomparable.

Okay, here is an attempt at doing so:

https://trac.sagemath.org/ticket/22029

I had to touch corners of Sage I'm far for comfortable with; if people
more familiar with them can have a look at the changes and perhaps help
with cleaner fixes, that would be more than welcome!

src/doc/de/tutorial/programming.rst | 12 ------
src/doc/en/reference/graphs/index.rst | 1 +
src/doc/en/tutorial/programming.rst | 10 -----
src/doc/en/tutorial/tour_coercion.rst | 2 -
src/doc/fr/tutorial/programming.rst | 10 -----
src/doc/fr/tutorial/tour_coercion.rst | 2 -
src/doc/ja/tutorial/programming.rst | 11 -----
src/doc/ja/tutorial/tour_coercion.rst | 2 -
src/doc/pt/tutorial/programming.rst | 10 -----
src/doc/pt/tutorial/tour_coercion.rst | 2 -
src/doc/ru/tutorial/programming.rst | 9 -----
src/module_list.py | 3 ++
src/sage/algebras/group_algebra.py | 4 +-
src/sage/categories/finite_posets.py | 4 +-
src/sage/categories/sets_cat.py | 2 +-
src/sage/combinat/crystals/alcove_path.py | 2 +-
src/sage/combinat/crystals/fast_crystals.py | 6 ++-
src/sage/combinat/designs/incidence_structures.py | 8 +++-
src/sage/combinat/finite_state_machine.py | 19 +++++++--
src/sage/combinat/misc.py | 2 +-
src/sage/combinat/posets/posets.py | 9 +++--
src/sage/combinat/rigged_configurations/bij_type_A2_even.py | 13 +++---
src/sage/combinat/sf/sfa.py | 2 +-
src/sage/combinat/species/product_species.py | 2 +-
src/sage/combinat/species/recursive_species.py | 2 +-
src/sage/combinat/species/series_order.py | 49 +++++++++++++++++++++++
src/sage/combinat/species/species.py | 7 ++--
src/sage/combinat/subset.py | 3 +-
src/sage/combinat/words/abstract_word.py | 5 ++-
src/sage/combinat/words/finite_word.py | 6 +--
src/sage/combinat/words/morphism.py | 8 ++--
src/sage/combinat/words/words.py | 16 ++++++--
src/sage/geometry/cone.py | 4 --
src/sage/geometry/fan.py | 2 -
src/sage/geometry/polyhedron/base.py | 7 ----
src/sage/geometry/toric_lattice.py | 2 -
src/sage/geometry/triangulation/element.py | 2 -
src/sage/graphs/base/c_graph.pyx | 30 ++++++++++++--
src/sage/graphs/base/label_cmp.pxd | 4 ++
src/sage/graphs/base/label_cmp.pyx | 84 +++++++++++++++++++++++++++++++++++++++
src/sage/graphs/base/sparse_graph.pyx | 21 ++++++----
src/sage/graphs/generic_graph.py | 46 +++++++++++++--------
src/sage/graphs/graph_plot.py | 29 +++++++++-----
src/sage/graphs/schnyder.py | 6 +--
src/sage/groups/affine_gps/group_element.py | 2 -
src/sage/homology/chain_complex.py | 17 ++++----
src/sage/homology/simplicial_complex.py | 25 ++++++------
src/sage/interfaces/ecm.py | 2 +-
src/sage/libs/ntl/ntl_mat_ZZ.pyx | 4 --
src/sage/misc/misc.py | 12 +++---
src/sage/modular/abvar/abvar.py | 2 +-
src/sage/modular/abvar/finite_subgroup.py | 4 --
src/sage/modular/abvar/torsion_subgroup.py | 2 -
src/sage/modular/hecke/ambient_module.py | 9 ++++-
src/sage/modules/multi_filtered_vector_space.py | 6 ++-
src/sage/modules/quotient_module.py | 2 -
src/sage/plot/graphics.py | 4 +-
src/sage/plot/plot3d/base.pyx | 4 +-
src/sage/plot/plot3d/platonic.py | 2 +-
src/sage/quivers/representation.py | 4 +-
src/sage/rings/number_field/number_field.py | 2 +-
src/sage/rings/rational.pyx | 5 ++-
src/sage/sandpiles/sandpile.py | 6 +--
src/sage/schemes/elliptic_curves/ell_number_field.py | 4 +-
src/sage/schemes/elliptic_curves/height.py | 5 ++-
src/sage/schemes/elliptic_curves/isogeny_class.py | 6 +--
src/sage/schemes/toric/variety.py | 2 +-
src/sage/sets/totally_ordered_finite_set.py | 27 ++++---------
src/sage/structure/coerce.pyx | 82 +++++++++++++++++++++++++++++---------
src/sage/structure/element_wrapper.pyx | 13 +++---
src/sage/structure/formal_sum.py | 18 +++++----
src/sage/symbolic/expression.pyx | 2 +-
72 files changed, 468 insertions(+), 285 deletions(-)

Thanks,

--
Marc

[Marc Mezzarobba]

Travis Scrimshaw wrote:
> We need to be very careful about defining "not knowing". I (stongly)
> believe when the objects/types are incomparable (say the rings ZZ and
> QQ), then == should return False and != should return True.
> Subsequently, when there is no coercion between the parents, they
> should not raise an error.

Does anyone else have comments on this issue? Specifically, what should
x != y do in your opinion when
- x is a Sage Element,
- y is
(i) another Element, or
(ii) a non-Element that does not implement rich comparison
with Elements,
- and the coercion framework finds no common parent for x and y?
The main options are to:
(a) return True,
(b) raise a TypeError.
Note that this is not equivalent to asking what == should do in a
similar situation.


I guess the main argument in favor of (a) is that it makes it possible
to say things like

if x != "foo":
x.frobnicate()

more or less whatever x is. Forbidding it may lead to problems in
existing external code, and the alternative version

if not (x == "foo"):
x.frobnicate()

(which would still work) is uglier and counter-intuitive.


The main argument I see for (b) is consistency with how coercion works
in general. When y is a string as above, or even when y is an Element
that has nothing to do with x, choosing (b) over (a) might help catch
some bugs, but I don't think there is much that can go wrong with (a).
The situation is more complicated when there is a common parent where
the comparison could be performed but the coercion framework is not
powerful enough to find it, like

sage: K.<sqrt2> = QQ[sqrt(2)]
sage: sqrt2 != QQbar(sqrt(2)) # mathematically wrong result!
True

or when the user (being used to Sage trying to make sense of comparisons
between elements of different parents) could mistake the output for more
than what it is, e.g.,

sage: QQ['x'].one() != QQ['y'].one()
True

sage: QQ['x'].one() != GF(2).one() # False with ZZ['x']
True

sage: RLF(pi) != pi
True

sage: RIF(-1, 1) != RBF(0) # are [-1,1] and {0} disjoint?
True

Incidentally, forcing people to change x != y to not(x == y) in some
cases may not be such a bad thing. Indeed, the two are not always
equivalent (the archetypal examples being intervals and domains where
equality is mathematically well-defined but undecidable), and situations
where option (b) would make x != y fail often are cases where the
programmer actually means not(x == y).

--
Marc

[Jeroen Demeyer]

On 2016-12-15 10:23, Marc Mezzarobba wrote:
> Travis Scrimshaw wrote:
>> We need to be very careful about defining "not knowing". I (stongly)
>> believe when the objects/types are incomparable (say the rings ZZ and
>> QQ), then == should return False and != should return True.
>> Subsequently, when there is no coercion between the parents, they
>> should not raise an error.
>
> Does anyone else have comments on this issue? Specifically, what should
> x != y do in your opinion when
> - x is a Sage Element,
> - y is
> (i) another Element, or
> (ii) a non-Element that does not implement rich comparison
> with Elements,
> - and the coercion framework finds no common parent for x and y?
> The main options are to:
> (a) return True,
> (b) raise a TypeError.

Don't forget the option

(c) return NotImplemented

I would say:

Case (i): (b)
Case (ii): (c)

[Marc Mezzarobba]

Jeroen Demeyer wrote:
> Don't forget the option
>
> (c) return NotImplemented
>
> I would say:
>
> Case (i): (b)
> Case (ii): (c)

Yes, I kept that out because my current patches don't change that part
of the logic, but I think I agree.

--
Marc

[Nathann Cohen]

Honnêtement je suis content de plus être dev, parce qu'un ticket comme ca m'aurait re-garanti une engueulade.

Ce que tu fais dans le dossier graphe est complètement irresponsable. Tu es en train de ralentir le cas d'usage le plus classique pour ne rien pouvoir garantir de mieux sur le cas général. Tout ca en ajoutant que ton nouveau code ne doit pas être utilisé dans le futur. Vu le temps qui a été investi pour avoir de la perf dans ce code, ca fait rever.

Nathann

[Marc Mezzarobba]

Marc Mezzarobba wrote:
> I had to touch corners of Sage I'm far for comfortable with; if people
> more familiar with them can have a look at the changes and perhaps
> help with cleaner fixes, that would be more than welcome!

In particular, Nathann sent me a private e-mail to complain that my
patches would likely slow down important use cases of the graph code.
Does anyone have benchmark problems handy that I could use to check?

Thanks,

--
Marc

[Marc Mezzarobba]

What about making a finer distinction, like

- (b), i.e. fail, when y is a SageObject or can be converted using
py_scalar_to_element(),

- (c), i.e. return NotImplemented, otherwise?

--
Marc

[Jeroen Demeyer]

On 2016-12-15 10:58, Marc Mezzarobba wrote:
> - (b), i.e. fail, when y is a SageObject or can be converted using
> py_scalar_to_element(),

I would prefer to treat these as any other non-Element. I see no reason
for the special case.

[Marc Mezzarobba]

Jeroen Demeyer wrote:
> I would prefer to treat these as any other non-Element. I see no
> reason for the special case.

It would catch cases like QQ(1) != ZZ or (going back to the case of
general rich comparison) float(1) < RIF(pi) where Python2 would compare
by type otherwise.

--
Marc

[Kwankyu Lee]

On Thursday, December 15, 2016 at 10:24:05 AM UTC+1, Marc Mezzarobba wrote:

Travis Scrimshaw wrote:
> We need to be very careful about defining "not knowing". I (stongly)
> believe when the objects/types are incomparable (say the rings ZZ and
> QQ), then == should return False and != should return True.
> Subsequently, when there is no coercion between the parents, they
> should not raise an error.

Does anyone else have comments on this issue? Specifically, what should
x != y do in your opinion when
  - x is a Sage Element,
  - y is
      (i) another Element, or
     (ii) a non-Element that does not implement rich comparison
          with Elements,
  - and the coercion framework finds no common parent for x and y?
The main options are to:
  (a) return True,
  (b) raise a TypeError.
Note that this is not equivalent to asking what == should do in a
similar situation.

After I read this, I have read only Python3 doc about == and != comparison operators. From this base, my simple-minded opinion(or expectation) is:

(1) "x != y" should behave always and exactly as "not (x == y)"

(2) When parents of x and y are different after coercion, "x != y" ("x == y") returns True (False) for both (i) and (ii)

(3) "x != y" and "x == y" never raise an exception.

I seems to agree with Travis.

[Marc Mezzarobba]

Thank you for you comments.

Kwankyu Lee wrote:
> (1) "x != y" should behave always and exactly as "not (x == y)"

This is difficult to achieve.

For example, in interval arithmetic, one usually expects a == b to
return True iff a and b are equal point intervals, and a != b to return
True iff a and b are disjoint intervals. Also, for lots of objects
coming up in computer algebra (e.g., symbolic expressions in one
variable), the equality test is either undecidable or at least not known
to be decidable.

In all these cases, there are at least three possible outcomes for the
comparison a == b:

- a and b can be determined to be equal,

- a and b can be determined to be different,

- a and b are neither known to be equal nor known to be different
(and perhaps, sometimes, variants like "a and b are known to be
neither equal nor different": e.g., the IEEE standard for floating-
point arithmetic says that NaN == NaN and NaN != NaN should both
return False, and it is not clear that this can be considered a case
where the "actual" result is unknown, as with interval arithmetic).

Then, the questions "are a and b known to be equal" and "are a and b
known to be different" are not the same. For example, if you are trying
to make sure that a matrix is nonsingular, you will usually want to test
that its determinant is known to be nonzero. If, however, you are trying
to decide whether a term can be dropped from the representation of a
polynomial, you'll usually want to test if it is known to be zero.

A partial solution to these problems is to allow comparisons to return
"Unknown" instead of just "True" or "False". This is in fact possible;
however (as discussed at length on sage-devel in the past), Python will
need to convert the "Unknown" result to a boolean as soon as it is used
as part of a conditional expression, so that we essentially are back to
the previous problem.

(I guess one could implement a more explicit, if essentially equivalent,
way of handling that, e.g. have comparisons themselves return Unknown,
conversions from Unknown objects to boolean raise an exception, and
introduce "modality" operators for the various possible conversions from
{True,False,Unknown} to {True,False}. But that's not how things are done
in Sage for now.)

> (2) When parents of x and y are different after coercion, "x != y" ("x
> == y") returns True (False) for both (i) and (ii)

Why only "after coercion"? I would understand that x != y return False
as soon as x and y have different parents--that would actually be the
best convention from my POV, but many people disagree, and that would be
a major break of compatibility. But I don't like the idea that a
comparison that makes sense mathematically returns True or False
depending whether the coercion system finds a common parent or not.
Besides, it is not hard to find cases where the user could *expect* the
system to make sense of the comparison, even though x and y actually
have good reasons not to have a common parent.

In other words: the choice has been made, long ago, to have ==/!= in
Sage stand for "semantic" comparison of mathematical objects rather than
"syntactic" comparison of data structures. I don't think it was the
right choice, but as long as we stick to it, it seems to me that
comparisons that don't have a well-defined mathematical result should
fail whenever practical, and return False (under the above asymmetric
interpretation) if they really need to return a boolean result.

> (3) "x != y" and "x == y" never raise an exception.

Why? We are not talking about raising exceptions all the time, only in
cases where it is likely that there is a bug...

--
Marc

[Thierry]

Hi,

On Sun, Dec 18, 2016 at 10:58:26AM +0100, Marc Mezzarobba wrote:
[...]

> In other words: the choice has been made, long ago, to have ==/!= in
> Sage stand for "semantic" comparison of mathematical objects rather than
> "syntactic" comparison of data structures. I don't think it was the
> right choice, but as long as we stick to it, it seems to me that
> comparisons that don't have a well-defined mathematical result should
> fail whenever practical, and return False (under the above asymmetric
> interpretation) if they really need to return a boolean result.

Note that this is also Python (2 and 3) choice:

>>> a = 1
>>> b = 1.
>>> type(a)
<class 'int'>
>>> type(b)
<class 'float'>
>>> a == b
True

Ciao,
Thirry

[Kwankyu Lee]

On Sunday, December 18, 2016 at 10:58:42 AM UTC+1, Marc Mezzarobba wrote:

Thank you for you comments.

Kwankyu Lee wrote:
> (1) "x != y" should behave always and exactly as "not (x == y)"

This is difficult to achieve. 

For example, in interval arithmetic, one usually expects a == b to
return True iff a and b are equal point intervals, and a != b to return
True iff a and b are disjoint intervals.

  

Do we have such cases in Python proper? I mean a case that disobeys (1).  It is unfortunate if Sage is different in this respect.

Also, for lots of objects
coming up in computer algebra (e.g., symbolic expressions in one
variable), the equality test is either undecidable or at least not known
to be decidable.

I see "==/!=" more as programming tools, and expect that they do not attempt to do difficult mathematical comparison that can lead to long computation or results other than True or False.

I expect that the comparison operators try to return mathematically sensible result as far as it is practical (one systematic way is to use coercion), and do something else (but still True or False) that is clearly documented as soon as any difficulty you mentioned can arise.

> (3) "x != y" and "x == y" never raise an exception.

Why? We are not talking about raising exceptions all the time, only in
cases where it is likely that there is a bug... 

Because you mentioned TypeError as an option.

[Simon King]

Hi!

On 2016-12-19, Kwankyu Lee <ekwa...@gmail.com> wrote:
> I see "==/!=" more as programming tools, and expect that they do not
> attempt to do difficult mathematical comparison that can lead to long
> computation or results other than True or False.

I could be mistaken, but I think what you describe is what cmp used to
mean (at least for Sage), whereas "==/!=" has not been considered a
programming tool but a mathematical tool.

So, it is really unfortunate that cmp disappearing forces us to
reconsider the rôle of ==/!=. A *mathematical* software obviously needs
a mathematical notion of comparison, but at the same time it is obvious
that a mathematical *software* needs a programmatical/practical notion
of comparison. Even more so as Python decided against a ternary logic
with "Unknown" being a valid result of comparison.

I didn't closely follow the discussion here. Have there been suggestions
how Sage should in future distinguish the two meanings of comparison
(maths vs programming)? It would obviously be rather awkward to have
to do "A.is_equal(B)" for a mathematical equality test.

Best regards,
Simon

[Marc Mezzarobba]

Simon King wrote:
> I didn't closely follow the discussion here. Have there been
> suggestions how Sage should in future distinguish the two meanings of
> comparison (maths vs programming)?

Not in this thread. However, if I understood right, several people who
worked on getting rid of cmp() came to the conclusion that having a
total order on all objects like cmp() used to (sort of!) promise wasn't
that useful.

Yet, it would be nice to standardize a few additional comparison
functions with well-specified semantics. (That's not what I'm trying to
do at the moment, however.)

> It would obviously be rather awkward to have to do "A.is_equal(B)" for
> a mathematical equality test.

It would nevertheless be the best option, IMO, if we were starting from
scratch. But that's not the case.

--
Marc

[Marc Mezzarobba]

Kwankyu Lee wrote:
> Do we have such cases in Python proper? I mean a case that disobeys
> (1).

I can't think of any example for base types(*). But this is explicitly
allowed by PEP207:

| 3 The == and != operators are not assumed to be each other's
| complement (e.g. IEEE 754 floating point numbers do not satisfy
| this). It is up to the type to implement this if desired.

and I guess there are a number of other libraries that use this option.

(*) What I said about NaNs earlier in the thread was incorrect: I think
the rule is actually that NaN < a, NaN > a, NaN == a are all false for
all a (even when a is [the same] NaN), but NaN != a is true for all a.
And that's, of course, assuming a particular mapping of the language's
comparison operators to IEEE754 comparison predicates, which is the job
of the language specification. And hence I don't understand what the
remark about IEEE754 in the above quotation refers to.

--
Marc

[Marc Mezzarobba]

Kwankyu Lee wrote:
> I expect that the comparison operators try to return mathematically
> sensible result as far as it is practical (one systematic way is to
> use coercion), and do something else (but still True or False) that is
> clearly documented as soon as any difficulty you mentioned can arise.

What about <, <=, etc.? Do you agree that they should fail when rather
than return a result with no mathematical meaning, even if the result is
clearly documented?

>> (3) "x != y" and "x == y" never raise an exception.
>>
>> Why? We are not talking about raising exceptions all the time, only
>> in cases where it is likely that there is a bug...
>
> Because you mentioned TypeError as an option.

Yes, sorry if I wasn't clear: what I'm aksing is what benefit you see of
returning False instead of raising an error (in the case of !=).

Thanks again,

--
Marc

[Kwankyu Lee]

On Monday, December 19, 2016 at 12:51:10 PM UTC+1, Marc Mezzarobba wrote:

What about <, <=, etc.? Do you agree that they should fail when rather
than return a result with no mathematical meaning, even if the result is
clearly documented?

I am divided between those operators being "mathematical" operators and "programming" operators. If I see them as "mathematical", I would agree that they should fail when there is no mathematical meaning. But if I see them as programming tool, I would expect that they give True/False results even when there is no mathematical meaning. 

 

 what I'm aksing is what benefit you see of
returning False instead of raising an error (in the case of !=). 

I see no benefit except consistency (that ==/!= operators do not raise exceptions.)