Removed unused and potentially misleading Morphism.__hash__

[embray]

As far as I can tell there is no code using the ability to hash Morphisms, and having this in the base class is misleading since there are subclasses which are not immutable and should not be hashable anyways. It would be better to implement __hash__ on an as-needed basis for those classes that can guarantee immutability.

Original description

ContinuousMap is impacted by #24551 in that it defines an __eq__, so its default hash is not inherited from its base class, Morphism (which does define __hash__).

This is one of the classes impacted by the issue raised in this comment.

I'm not sure what the best solution is. Right now I feel like it's somewhat ill-defined, because it's possible to have two ContinuousMaps that compare as equal, but have different hashes. That's not necessarily wrong, but it isn't obviously right either. If x == y, then hash(x) == hash(y) for a correct implementation. Technically I believe you can get away with the inverse--having hash(x) == hash(y) but x != y--but it is advisable for performance to avoid this.

CC: @fchapoton @egourgoulhon

Component: geometry

Author: Erik Bray

Branch/Commit: u/embray/misc/ticket-25393 @ 1a99057

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

[embray]

Description changed:

--- 
+++ 
@@ -2,4 +2,4 @@
 
 This is one of the classes impacted by the issue raised [in this comment](https://github.com/sagemath/sage/issues/25387#comment:3).
 
-I'm not sure what the best solution is.  Right now I feel like it's somewhat ill-defined, because it's possible to have two `ContinuousMaps` that compare as equal, but have different hashes.  That's not necessarily wrong, but it isn't obviously right either.
+I'm not sure what the best solution is.  Right now I feel like it's somewhat ill-defined, because it's possible to have two `ContinuousMaps` that compare as equal, but have different hashes.  That's not necessarily wrong, but it isn't obviously right either.  If two instances of the same class have the same hash, they must also be equal to each other with `==`.  Technically I believe you can get away with the inverse--having different hashes but equivalent via `==`--but it's not advisable and is a bad smell.

[tscrim]

comment:3

If two instances of the same class have the same hash, they must also be equal to each other with ==

That is true iff a perfect hash function exists, which it generally does not. In fact, that is not mandated by Python. For example, a valid hash function is 0 for all objects, but you loose performance benefits from dict because it becomes a list search.

The converse is really what you want: == implies same hash. (Also to be hashable, the hash should be immutable.) You can get away with it, but it causes problems when you try to put it into a set/dictionary as you get multiple instances of equal objects.

The issue with this class is that we have essentially a mutable element class. So I think the proper thing to do is just disable hashing. We do something similar for vectors and matrices.

[embray]

comment:4

I think you must have misread me or something. I didn't mean that if two instances have the same hash it implies they are ==. I mean that in order for hashing to be implemented correctly, then as you said if they are == they must have the same hash.

It actually wasn't immediately obvious to me that this class is not immutable. Where can it be mutated? All I noticed is that you define two ContinuousMaps that are the same except that one is constructed with is_isomorphism=True and the other with is_isomorphism=False. In this case they are == but have different hashes.

[tscrim]

comment:5

Replying to @embray:

I think you must have misread me or something. I didn't mean that if two instances have the same hash it implies they are ==. I mean that in order for hashing to be implemented correctly, then as you said if they are == they must have the same hash.

Paraphrasing what you wrote: if x.__class__ == y.__class__ and hash(x) == hash(y), then x == y. It is a bad smell for x == y with hash(x) == hash(y). We're on the same page with what needs to be done, but I just saying the ticket description needed an update, which I have just done.

IMO, it is not a code smell to have hash(x) == hash(y) but x != y. However, I do agree that it is better to have a more perfect hash function, but there are only so many hash values since hashes are limited to 64 bit integers (unless I am misunderstanding something in Python).

It actually wasn't immediately obvious to me that this class is not immutable. Where can it be mutated? All I noticed is that you define two ContinuousMaps that are the same except that one is constructed with is_isomorphism=True and the other with is_isomorphism=False. In this case they are == but have different hashes.

See add_expr and set_expr.

[tscrim]

Description changed:

--- 
+++ 
@@ -2,4 +2,4 @@
 
 This is one of the classes impacted by the issue raised [in this comment](https://github.com/sagemath/sage/issues/25387#comment:3).
 
-I'm not sure what the best solution is.  Right now I feel like it's somewhat ill-defined, because it's possible to have two `ContinuousMaps` that compare as equal, but have different hashes.  That's not necessarily wrong, but it isn't obviously right either.  If two instances of the same class have the same hash, they must also be equal to each other with `==`.  Technically I believe you can get away with the inverse--having different hashes but equivalent via `==`--but it's not advisable and is a bad smell.
+I'm not sure what the best solution is.  Right now I feel like it's somewhat ill-defined, because it's possible to have two `ContinuousMaps` that compare as equal, but have different hashes.  That's not necessarily wrong, but it isn't obviously right either.  If `x == y`, then `hash(x) == hash(y)` for a correct implementation.  Technically I believe you can get away with the inverse--having `hash(x) == hash(y)` but `x != y`--but it is advisable for performance to avoid this.

[embray]

comment:6

Well in that case this is already fixed for free on Python 3 since it sets __hash__ = None automatically for any class that defines __eq__ but not __hash__, and this should just be done explicitly for this class.

In general should Morphism even have a default hash? It doesn't seem that immediately useful to me.

[tscrim]

comment:7

Replying to @embray:

Well in that case this is already fixed for free on Python 3 since it sets __hash__ = None automatically for any class that defines __eq__ but not __hash__, and this should just be done explicitly for this class.

I agree. That is probably the correct thing to for this class.

In general should Morphism even have a default hash? It doesn't seem that immediately useful to me.

I cannot think of a general mechanism that would require morphisms to be keys to a cache. Ideally matrices should be a subclass of Morphism, which would break the implicit Morphism is meant to be immutable. Although the fact that a Morphism can be stored via a coercion might lead to subtle bugs when it is mutable.

[embray]

comment:8

Okay then, I think I'll just try removing Morphism.__hash__. Neither the commit that added it, nor the associated ticket (#13214) provide any explanation for why it was added. It just was.

I don't think we should be adding __hash__ implementations anywhere that it isn't explicitly needed (or at least a specific use case is being imagined). Especially not for base classes that could have mutable subclasses (one could make exceptions of course but in that case it would also be good to have an explicit mechanism for marking whether or not instances of some class are expected to be immutable).

[embray]

comment:9

Oh fun. Deleting Morphism.__hash__ causes segfaults :) No, I was just misreading the test output. It wasn't segfaults, just timeouts (the stack traces threw me off). Still I wonder if that was a regression...