#19016 closed defect (fixed)
Better hash for Element
Reported by:  ncohen  Owned by:  

Priority:  critical  Milestone:  sage6.10 
Component:  misc  Keywords:  
Cc:  Merged in:  
Authors:  Nils Bruin, Vincent Delecroix  Reviewers:  Volker Braun 
Report Upstream:  N/A  Work issues:  
Branch:  c7b4f0e (Commits)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
As reported on sagedevel [1], Element
implements its hash based on its string representation. This causes a lot of troubles
 it breaks the
equality => same hash
assumption for finitely presented groupssage: G = groups.presentation.Cyclic(4) sage: G.cayley_graph().vertices() [1, a, a^2, a^2, a^3, a^1]
and symbolic expressionssage: f=sin(x)^2 sage: g=1cos(x)^2 sage: bool(f == g) True sage: hash(f) == hash(g) False
and possibly many others
 it is highly incompatible with the
rename
feature (see also #8119)sage: from sage.structure.element import Element sage: class E(Element): ....: def __init__(self): ....: Element.__init__(self, Parent()) sage: e = E() sage: hash(e) 4965357552728411610 sage: e.rename('hey') sage: hash(e) 6429308858210906323
and similarly, hashing should not be available on any mutable object.
There are several possibilities that are currently being discussed:
 make it return
0
by default (original proposition of the ticket)  make it raise a
TypeError
by default (as it the case forSageObject
, see #18246)  let it as it is but raise a Warning
[1] https://groups.google.com/d/topic/sagedevel/6rXKkF87Gtc/discussion
Change History (122)
comment:1 Changed 5 years ago by
 Branch set to u/ncohen/19016
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
 Commit set to 754dc5794a1a7004c8844cf7cfb64220957c36a5
comment:3 Changed 5 years ago by
Hi Nathann,
What about #18246? Just returning 0
will create many collisions that will be hard to track. I think that raising an error is more appropriate because you know what is to be fixed.
Vincent
comment:4 Changed 5 years ago by
If you see a way to turn #18246 into a needs_review
ticket soon, then I do not mind. But I don't want to fight against 800 screaming guys again, and I want this to be solved.
What about a middle ground: raise a warning, which would appear only once, whenever this 0 hash function is used?
This is a very bad bug and it needs to be fixed. Creating tickets that we forget is nto much more responsible than doing nothing.
Nathann
comment:5 Changed 5 years ago by
By the way, it is not even the same hash function. Here it is Element.__hash__
and it is SageObject.__hash__
in #18246. Both need to be solved of course.
comment:6 followup: ↓ 7 Changed 5 years ago by
Replying to ncohen:
If you see a way to turn #18246 into a
needs_review
ticket soon, then I do not mind. But I don't want to fight against 800 screaming guys again, and I want this to be solved.
Putting in needs_review
just need some efforts. I can dig into it if you are up for a review.
What about a middle ground: raise a warning, which would appear only once, whenever this 0 hash function is used?
It is already a bit better.
This is a very bad bug and it needs to be fixed.
It is.
Creating tickets that we forget is nto much more responsible than doing nothing.
I did not forget as you see ;)
With your implementation, I am pretty sure that the running time of the tests will be much slower. Sage very often put elements in dictionaries or sets. Your solution does not help users to see that __hash__
is important, because you will not run into bugs, just into very slow code. I agree that you fix the error but you open a much more annoying feature.
comment:7 in reply to: ↑ 6 Changed 5 years ago by
Putting in
needs_review
just need some efforts. I can dig into it if you are up for a review.
Remember that #18246 is not even about the hash function that I change here.
With your implementation, I am pretty sure that the running time of the tests will be much slower. Sage very often put elements in dictionaries or sets. Your solution does not help users to see that
__hash__
is important, because you will not run into bugs, just into very slow code. I agree that you fix the error but you open a much more annoying feature.
If you think that we can fix the bug *quickly* by removing the __hash__
function from Element, then let us do that. If the result is that my ticket will be put "on hold" waiting for something that never happens (like it happened 4 months ago on #18246), then this ticket is better than an imaginary one.
Concerns about efficiency do not weight much compares to wrong results.
Nathann
comment:8 followup: ↓ 10 Changed 5 years ago by
1 to a constant hash. That leads to such bad performance that it amounts to "wrong results".
+1 to removing silly default hashes. Hashing is simply not something that can be done on a very general level.
For your example, unless you come up with a canonical form for group elements that you can take the hash of, you really shouldn't have a hash function, by the way. These elements should be unhashable, not hashable with a constant hash value.
comment:9 Changed 5 years ago by
#18246 needs review (it removes the __hash__
from SageObject
).
comment:10 in reply to: ↑ 8 ; followup: ↓ 11 Changed 5 years ago by
1 to a constant hash. That leads to such bad performance that it amounts to "wrong results".
+1 to removing silly default hashes. Hashing is simply not something that can be done on a very general level.
What is your position for "constant hash" Vs "we change nothing and the bug stays"? How many classes do you think would be broken (and would have to be fixed) if this hash is removed? Are you willing to help?
Nathann
comment:11 in reply to: ↑ 10 ; followup: ↓ 12 Changed 5 years ago by
Replying to ncohen:
What is your position for "constant hash" Vs "we change nothing and the bug stays"?
"Change nothing". I think it's unfortunate that hashing by repr will usually work quite well in cases where a hash is possible: a hash usually requires a canonical form to compute the hash from and that canonical form will usually be used for printing, because that's nice. So in practice, the default hash (although much too slow to be a reasonable hash) will probably work when it should.
In cases where the current default hash *doesn't* work, I think that having it as it is now will lead to better detection than when we change it to a default hash of 0. When people find this in particular cases, the solution is clear: actively disable the hash.
Having to *disable* something is of course the wrong way around: the default hash shouldn't be there in the first place. But putting a constant 0 hash there instead doesn't make transitioning to the desired situation any easier.
comment:12 in reply to: ↑ 11 Changed 5 years ago by
 Milestone changed from sage6.9 to sageduplicate/invalid/wontfix
 Status changed from needs_review to positive_review
What is your position for "constant hash" Vs "we change nothing and the bug stays"?
"Change nothing".
I love those guys. "You fix a bug, but because it is not done the way I like I will block your tickets, and the bug will stay unsolved. And no, I will not help do it the way I want to see it done. You have to do it by yourself, while I watch you sweat".
Free software.
See, I wouldn't feel well with myself if after something like that I got to work and started implementing what you ask me to. So the bug will stay, thanks to you. Today, you contributed to the common effort for a better mathematical software.
Nathann
comment:13 followup: ↓ 14 Changed 5 years ago by
 Status changed from positive_review to needs_review
As I said in 9 I did remove the stupid __hash__
from SageObject
(this is #18246). Not setting it to 0
but making it raise a TypeError
. It was not a tremendous effort even if I had to dig in things that I do not understand.
I guess that the same strategy would also be good for Element
and I agree with Nils on this. The warning option proposed in 4 by Nathann looks also good to me because each time you program something you will notice that you are doing something wrong. Could we try to found a solution? This is annoying and I am willing to help to fix it.
comment:14 in reply to: ↑ 13 Changed 5 years ago by
Could we try to found a solution? This is annoying and I am willing to help to fix it.
I do not intend to touch this ticket again. I'm starting a new trend: when people tell me that my idea is bad, I stop fighting and leave (see #18904, though it's not the first). So that if I ever find something more interesting to do during my holidays than contribute to Sage, I won't hesitate to delete my account and move on to other things.
Nathann
comment:15 followup: ↓ 16 Changed 5 years ago by
The default __hash__
could be moved from Element to a CanonicalRepresentation (or so) category. After injecting that into a few basic categories there are probably not that many parents where it has to be added by hand... thoughts?
comment:16 in reply to: ↑ 15 Changed 5 years ago by
Replying to vbraun:
The default
__hash__
could be moved from Element to a CanonicalRepresentation (or so) category. After injecting that into a few basic categories there are probably not that many parents where it has to be added by hand... thoughts?
That might be an easy move since we would just have to change the category to something like PreviousCategory().WithCanonicalRepresentation()
. For me this has to be done on a case by case basis for each Parent
. The advantage would be the simplicity. But I found that this would mostly move the problem. But it would be better, because explicit in the parent implementation.
But in the long run, do we really want to use only once the string representation for the hash? Is that how we want the user to implement their own Parent/Element
? I like Nathann's idea of having a warning if the default hash is called (and the default could be either hash(repr(P))
or 0
I do not really care).
comment:17 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:18 Changed 5 years ago by
Often you can have normal forms on general grounds, so IMHO would be reasonable to just make CanonicalRepresentation
a part of vector spaces and such. Thats why I said we shouldn't have to do it for every parent by hand. For most parents the hash(repr(element))
is a good enough hash function. Sure you could make it faster by an overall constant factor, but its still gives you O(1) associative containers.
comment:19 Changed 5 years ago by
I definitely don't like to have 0 hashes everywhere. I like the solution proposed by Volker: having hash only on those parents where we actually have a canonical form for each element.
On the other hand, it will take some time to be implemented, and in the meantime, the problem stated by Nathan would persist. So my proposal for a temporary quick fix for that is the following: for finitely presented group elements, just hash its representation in the abelianization (or any other invariant of the element that can be computed quickly). It would work as a hash should (that is, it will distinguish elements in some cases, but will not distnguish different representations of the same element), even if there would still be some collisions.
comment:20 Changed 5 years ago by
I am getting the following errors:
mmarco@mountain ~/sage $ ./sage t src/sage/groups/finitely_presented.py Running doctests with ID 20150815002739750876a9. Git branch: t/19016/19016 Using optional=gdb,mpir,python2,sage,scons,tides Doctesting 1 file. sage t warnlong 59.1 src/sage/groups/finitely_presented.py ********************************************************************** File "src/sage/groups/finitely_presented.py", line 326, in sage.groups.finitely_presented.FinitelyPresentedGroupElement.__call__ Failed example: w(1, 2, check=False) # result depends on presentation of the group element Expected: 2 Got: 8 ********************************************************************** 1 item had failures: 1 of 10 in sage.groups.finitely_presented.FinitelyPresentedGroupElement.__call__ [310 tests, 1 failure, 6.06 s]  sage t warnlong 59.1 src/sage/groups/finitely_presented.py # 1 doctest failed  Total time for all tests: 6.1 seconds cpu time: 5.8 seconds cumulative wall time: 6.1 seconds
comment:21 Changed 5 years ago by
A little digging in Gap's FP compare functions source shows that for finite finitely presented groups, our hash, given these definitions:
FamilyObj=libgap.function_factory("FamilyObj") ElementsFamily=libgap.function_factory("ElementsFamily") FPFaithHom=libgap.function_factory("FPFaithHom") Image=libgap.function_factory("Image")
should probably look something like this:
sage: G=groups.presentation.Cyclic(4) sage: f=FPFaithHom(ElementsFamily(FamilyObj(G.gap()))) sage: newhash=lambda a: hash(Image(f,a.gap()))
A little test:
sage: import collections sage: L=[G.0^i for i in [5..5]] sage: collections.Counter(hash(a) == hash(b) for a in L for b in L if a==b) Counter({False: 20, True: 11}) sage: collections.Counter(newhash(a) == newhash(b) for a in L for b in L if a==b) Counter({True: 31}) sage: collections.Counter(newhash(a) == newhash(b) for a in L for b in L if a!=b) Counter({False: 90})
comment:22 followup: ↓ 23 Changed 5 years ago by
The problem is that we don't know, a priory, if a finitely presented group is finite or not. And just trying to check it automatically can take forever or exhaust the memory. That is why I proposed to go for the abelianization, which is an invariant of the element that can be always computed (and in a reasonably fast way). It still has some collisions, but it is way better than having always a collision.
comment:23 in reply to: ↑ 22 Changed 5 years ago by
Replying to mmarco:
The problem is that we don't know, a priory, if a finitely presented group is finite or not. And just trying to check it automatically can take forever or exhaust the memory. That is why I proposed to go for the abelianization, which is an invariant of the element that can be always computed (and in a reasonably fast way). It still has some collisions, but it is way better than having always a collision.
For finite simple groups I think "some collisions" is a bit of an understatement, but that's not the main point. The thing is: for pretty much any application of hashing, you will need equality testing too (this is definitely the case in Python's dicts), and then Gap will just go off and compute this stuff anyway, unless we go with Volker's suggestion of inheriting equality (and hashing) from the free covering presentation.
So we should definitely only compute the hash function lazily, but if it's asked for, I think we would incur a very small penalty in practice if we replicate the logic from Gap's MakeFpGroupCompMethod.
comment:24 Changed 5 years ago by
Just a small paranthesis: there are two very different things
 Changing the default behavior of the hash function
 Having a better hash for FP group elements
These deserve two tickets, don't you think? The initial purpose of the ticket was 1 and now you are mainly discussing 2. Could you open a ticket "better hash for FP Group element"?
Vincent
comment:25 followup: ↓ 26 Changed 5 years ago by
You are right, but i think they are very related, since FP groups is AFAIK the only parent where the default hash is problematic. So, maybe a solution for 2. would make 1. pointless (assuming there are no other places where the actual default hash is problematic in the same sense)
comment:26 in reply to: ↑ 25 ; followup: ↓ 29 Changed 5 years ago by
Replying to mmarco:
You are right, but i think they are very related, since FP groups is AFAIK the only parent where the default hash is problematic. So, maybe a solution for 2. would make 1. pointless (assuming there are no other places where the actual default hash is problematic in the same sense)
I agree that they are related. But __hash__
is problematic in other situations and two of them are mentioned in #18246. Solving the FP group problem will not solve everything as far as I understand it.
comment:27 Changed 5 years ago by
And note that in the ticket description it is written "Incidentally, it fixes the following bug:"...
comment:28 Changed 5 years ago by
Ok then.
In that case, i think it makes more sense to not have a hash by default, than having a constant one.
comment:29 in reply to: ↑ 26 ; followup: ↓ 30 Changed 5 years ago by
Replying to vdelecroix:
I agree that they are related. But
__hash__
is problematic in other situations and two of them are mentioned in #18246. Solving the FP group problem will not solve everything as far as I understand it.
Indeed, absolutely. And #18246 is now marked fixed. Another example is (of course) SR  another ring where equality and normal form are impossible to resolve in general
sage: f=sin(x)^2 sage: g=1cos(x)^2 sage: bool(f == g) True sage: hash(f) == hash(g) False
so, hopefully, with #18246 , the last command will lead to an error?
comment:30 in reply to: ↑ 29 ; followup: ↓ 32 Changed 5 years ago by
Replying to nbruin:
Replying to vdelecroix:
I agree that they are related. But
__hash__
is problematic in other situations and two of them are mentioned in #18246. Solving the FP group problem will not solve everything as far as I understand it.Indeed, absolutely. And #18246 is now marked fixed. Another example is (of course) SR  another ring where equality and normal form are impossible to resolve in general
sage: f=sin(x)^2 sage: g=1cos(x)^2 sage: bool(f == g) True sage: hash(f) == hash(g) Falseso, hopefully, with #18246 , the last command will lead to an error?
Sadly not
sage: f=sin(x)^2 sage: isinstance(f, sage.structure.element.Element) True
Element
does implement the return hash(str(self))
behavior. So this will incidentally be fixed with this ticket...
comment:31 Changed 5 years ago by
 Description modified (diff)
 Milestone changed from sageduplicate/invalid/wontfix to sage6.9
I wrote some more in the ticket description...
comment:32 in reply to: ↑ 30 Changed 5 years ago by
 Description modified (diff)
 Milestone changed from sage6.9 to sageduplicate/invalid/wontfix
Replying to vdelecroix:
Element
does implement thereturn hash(str(self))
behavior. So this will incidentally be fixed with this ticket...
Aw, that's unfortunate. Also, I'm pretty sure removing default hashes on elements is going to be a much more involved problem. This ticket should probably keep its general function and be retitled to: remove default hash on Element.
I have made #19038 for the FPGroup issue (where we're in much better shape in many individual cases)
comment:33 Changed 5 years ago by
 Description modified (diff)
Shoot. Is there a better way of reverting changes on trac? I ended up cutting and pasting from the change log diff.
comment:34 Changed 5 years ago by
 Description modified (diff)
 Milestone changed from sageduplicate/invalid/wontfix to sage6.9
 Summary changed from A more naive sage.structure.element.__hash__ to Better hash for Element and CategoryObject
comment:35 followup: ↓ 37 Changed 5 years ago by
 Description modified (diff)
 Summary changed from Better hash for Element and CategoryObject to Better hash for Element
Arghhh... there are two category tests which ask explicitely for parent.one()
and parent.zero()
to return hashable elements! These are
Magmas.Unital.ParentMethods._test_one
AdditiveMagmas.AdditiveUnital.ParentMethods._test_zero
(I do think that those tests are good because most of the time the result is cached)
In other words, any (additive or multiplicative) magma element should be immutable or adopt an mutable/immutable framework... might be a lot of work to fix!
Concerning Parent
and CategoryObject
from which it inherits I do not think it is a good idea to touch it for now. Most of the time we expect a Parent
to be immutable.
comment:36 Changed 5 years ago by
 Description modified (diff)
comment:37 in reply to: ↑ 35 ; followup: ↓ 38 Changed 5 years ago by
Replying to vdelecroix:
In other words, any (additive or multiplicative) magma element should be immutable or adopt an mutable/immutable framework... might be a lot of work to fix!
No, worse: any magma should have a decidable equality notion and a hash that's compatible with it. As we've already seen, the mathematical notion of equality in a magma need not be decidable. It makes no sense having a hash if you cannot test equality.
I think the proper solution is to lose this equality and hashing requirement and instead subclass to MagmaWithDecidableEquality
and put the hash & equality stuff there (or do it via categories/axioms if you think that's more appropriate, but I'd rather avoid that if at all possible).
Is that attainable? Another possibility is to by default only test equality in the free structure covering the magma, i.e., "presentation equality". But that's going to be very confusing.
comment:38 in reply to: ↑ 37 ; followups: ↓ 39 ↓ 40 Changed 5 years ago by
Replying to nbruin:
Replying to vdelecroix:
In other words, any (additive or multiplicative) magma element should be immutable or adopt an mutable/immutable framework... might be a lot of work to fix!
No, worse: any magma should have a decidable equality notion and a hash that's compatible with it.
Nope. To fix just these test_zero
and test_one
one way is to allow to hash the unit but no other elements... does it look reasonable from the point of view of this ticket? Whether we want to do better looks for me as a part #19038.
New bad news: hashing of ideals. The ResidueField
factory in sage.rings.finite_rings.residue_field
uses as keys ideals that do not implement hashing. And I guess in most non trivial case having a hash value would be hard. For principal ideal, it is easy to test equality but much harder to implement a hash.
comment:39 in reply to: ↑ 38 Changed 5 years ago by
Replying to vdelecroix:
Nope. To fix just these
test_zero
andtest_one
one way is to allow to hash the unit but no other elements...
which makes for horrible code! Are you referring to these lines?
# Check that zero is immutable by asking its hash: tester.assertEqual(type(zero.__hash__()), int) tester.assertEqual(zero.__hash__(), zero.__hash__())
It's better to implement this by asking hash(zero)
. The first test is then not even necessary, because the type will be confirmed in the protocol. Anyway, I think the check is wrong: objects can be immutable without being hashable.
I don't think python has a universal way of testing immutability, but I do think that our element types that can be mutable/immutable have a testing function for that. So we can check it if available:
if hasattr(zero,"is_immutable"): tester.assertEqual(zero.is_immutable(),True) if hasattr(zero,"is_mutable"): tester.assertEqual(zero.is_mutable(),False)
comment:40 in reply to: ↑ 38 Changed 5 years ago by
Replying to vdelecroix:
New bad news: hashing of ideals. The
ResidueField
factory insage.rings.finite_rings.residue_field
uses as keys ideals that do not implement hashing. And I guess in most non trivial case having a hash value would be hard. For principal ideal, it is easy to test equality but much harder to implement a hash.
These are prime ideals of number fields I presume? The HNF of a Zbasis of the ideal wrt. the chosen integral basis would do the trick, if all those things are available ...
I guess we've painted ourselves in a corner here by requiring unique parents, and hence if an ideal is part of the construction parameters we have to hash with it? Luckily Julian Reuth has been putting a door in that corner:
Perhaps ideals that cannot properly be hashed should have a _cache_key
method instead (see http://doc.sagemath.org/html/en/reference/misc/sage/misc/cachefunc.html). It's not the end of the world if residue_field(P1)
and residue_field(P2)
give nonidentical parents for ideals P1
and P2
that are equal, but not obviously so. So the _cache_key
can be a much sloppier hashlike function. Of course __hash__
must be equal for equal ideals.
Perhaps a reasonable measure is to define on Element
etc.:
def _cache_key(self): return (self.parent(),str(self))
and delete the __hash__
(as is the purpose of this ticket). That should allow most internal usage of elements (in caches), and would free up hash for more properly defined concepts. Note that _cache_key
is only a failover, so one still can get better performance once one defines a__hash__
.
comment:41 Changed 5 years ago by
 Branch changed from u/ncohen/19016 to u/nbruin/19016
comment:42 Changed 5 years ago by
 Commit changed from 754dc5794a1a7004c8844cf7cfb64220957c36a5 to 829d9cc04c024620af19922ebb91ffded223712a
Branch pushed to git repo; I updated commit sha1. New commits:
829d9cc  also equip LaurentPolynomial_mpair with a hash

comment:43 Changed 5 years ago by
Does this do the trick?
comment:44 followup: ↓ 51 Changed 5 years ago by
 Dependencies set to #18246
The branch must be based over #18246 (which is not yet merged). Otherwise it makes no sense!
I also did implement several hashes that I will add to the branch.
While going through the code I found
sage: M = MatrixSpace(GF(3),2,2).list() sage: for m in M: m.set_immutable() sage: len(M) 81 sage: len(set(map(hash,M))) 8
I opened #19050.
comment:45 followup: ↓ 50 Changed 5 years ago by
 Branch changed from u/nbruin/19016 to public/19016
 Commit 829d9cc04c024620af19922ebb91ffded223712a deleted
I am not sure I do like your changes to the unit tests in categories. The zero/one values are cached most of the time. If it was to be mutable then a Sage user might end up with a wrong unit by doing
sage: S = MyStructure() sage: e = S.one() sage: e.change_something()
comment:46 Changed 5 years ago by
 Commit set to ed8b2bf18e3be123b6a83934daea565a01be3509
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
072a017  Trac 18246: more cleanup

0bf7d7d  Trac 18246: typo

a722920  Trac 18246: fix a doctest in rigged_configurations.py

1f79aa5  Trac 19016: Remove silly repr hash on Element and fix failures

ec82c74  Trac 19016: also equip LaurentPolynomial_mpair with a hash

a2e69fb  Trac 19016: hash values for CFiniteSequence

e9b4340  Trac 19016: fix hash for abelian group elements

29d3351  Trac 19016: hash for matrix group element

70ecc29  Trac 19016: hash for indexed free monoid

ed8b2bf  Trac 19016: hash for free groups

comment:47 Changed 5 years ago by
comment:48 Changed 5 years ago by
 Commit changed from ed8b2bf18e3be123b6a83934daea565a01be3509 to 83a758f5c9e19daa0e60914a633ded84d75da4e0
Branch pushed to git repo; I updated commit sha1. New commits:
83a758f  Trac 19016: hash for poset elements

comment:49 Changed 5 years ago by
A rough estimation of the classes that need a hash from the doctests
 algebras.quatalg.quaternion_algebra.QuaternionFractionalIdeal_rational
 combinat
 alternating_sign_matrix.AlternatingSignMatrices_with_category.element_class
 crystals.affinization.AffinizationOfCrystal_with_category.element_class
 crystals.elementary_crystals.ComponentCrystal_with_category.element_class
 crystals.elementary_crystals.ElementaryCrystal_with_category.element_class
 crystals.fast_crystals.FastCrystal_with_category.element_class
 crystals.monomial_crystals.CrystalOfNakajimaMonomials_with_category.element_class
 crystals.monomial_crystals.InfinityCrystalOfNakajimaMonomials_with_category.element_class
 rigged_configurations.kleber_tree.KleberTreeNode
 root_system.associahedron.Associahedra_with_category.element_class
 similarity_class_type.PrimarySimilarityClassTypes_with_category.element_class
 geometry
 hyperplane_arrangement.hyperplane.AmbientVectorSpace_with_category.element_class
 polyhedron.backend_cdd.Polyhedra_RDF_cdd_with_category.element_class
 polyhedron.backend_field.Polyhedra_field_with_category.element_class
 polyhedron.backend_ppl.Polyhedra_QQ_ppl_with_category.element_class
 polyhedron.backend_ppl.Polyhedra_ZZ_ppl_with_category.element_class
 groups.additive_abelian.additive_abelian_group.AdditiveAbelianGroup_fixed_gens_with_category.element_class
 modular.overconvergent.weightspace.AlgebraicWeight
 monoids
 free_monoid_element.FreeMonoid_class_with_category.element_class
 free_monoid_element.FreeMonoidElement
 string_monoid_element.StringMonoidElement
 rings
 infinity.PlusInfinity
 polynomial.ideal.Ideal_1poly_field
 polynomial.infinite_polynomial_element.InfinitePolynomial_dense
 polynomial.infinite_polynomial_element.InfinitePolynomial_sparse
 polynomial.multi_polynomial_ideal.MPolynomialIdeal
 quotient_ring_element.QuotientRing_generic_with_category.element_class
comment:50 in reply to: ↑ 45 Changed 5 years ago by
Replying to vdelecroix:
I am not sure I do like your changes to the unit tests in categories. The zero/one values are cached most of the time. If it was to be mutable then a Sage user might end up with a wrong unit.
I don't think we have another option:
 testing if something is hashable doesn't test if something is mutable
 something that is immutable can be unhashable. Elements in monoids with an unsolved wordproblem are/should be examples of that
 python guidelines say that mutable elements should not be hashable, but this is not enforced.
 python simply doesn't provide a surefire way of testing if something is mutable.
 Note that even for properly hashable elements the internal data structure can still change (attributes, internal representation), as long as equality holds. But for reuse of elements those other attributes can still be important! So even hashability does not imply an element is safe for caching/reuse.
Feel free to extend the tests I've proposed. However, assuming 0 and 1 are hashable is not a good test for the stated goal.
comment:51 in reply to: ↑ 44 ; followup: ↓ 52 Changed 5 years ago by
Replying to vdelecroix:
The branch must be based over #18246 (which is not yet merged).
?? I wasn't able to pull that ticket, presumably because it is merged!
comment:52 in reply to: ↑ 51 Changed 5 years ago by
Replying to nbruin:
Replying to vdelecroix:
The branch must be based over #18246 (which is not yet merged).
?? I wasn't able to pull that ticket, presumably because it is merged!
Nope. It will be merged in sage6.9.beta3. Note that our branches are different. I just cherrypick your two commits above #18246.
comment:53 Changed 5 years ago by
 Commit changed from 83a758f5c9e19daa0e60914a633ded84d75da4e0 to 1e49723f1c40990c000b924059bf218bd1d100fd
Branch pushed to git repo; I updated commit sha1. New commits:
1e49723  some more hashes

comment:54 Changed 5 years ago by
 Commit changed from 1e49723f1c40990c000b924059bf218bd1d100fd to 79b1ab6293ad8872f8f43945a94a6870c916a372
Branch pushed to git repo; I updated commit sha1. New commits:
79b1ab6  Trac 19016: hash for linear expression

comment:55 Changed 5 years ago by
 Commit changed from 79b1ab6293ad8872f8f43945a94a6870c916a372 to 3932a7fc21b9f80f3b13101732f1ce6ddece9f62
Branch pushed to git repo; I updated commit sha1. New commits:
3932a7f  Trac 19016: hash for alternating sign matrices

comment:56 Changed 5 years ago by
 Commit changed from 3932a7fc21b9f80f3b13101732f1ce6ddece9f62 to 65f3226dfaf8219b35dd76f48ab1ff766632a09c
Branch pushed to git repo; I updated commit sha1. New commits:
65f3226  Trac 19016: all test pass in combinat/crystals

comment:57 Changed 5 years ago by
I had hard time with sage.structure.element_wrapper
which is intensively used in crystal code. The comparison code looks completely broken as I had to implement all the family of __eq__
, __ne__
, __lt__
, etc as well as __cmp__
.
I did not change any doctest in the code, but because I introduced many new functions some of them lack doctest.
comment:58 Changed 5 years ago by
 Commit changed from 65f3226dfaf8219b35dd76f48ab1ff766632a09c to 9e42b914d59bda3e0fe3825e6c00c9f377cb6bcc
Branch pushed to git repo; I updated commit sha1. New commits:
9e42b91  Trac 19016: hash for polyhedra (using Vrepresentation)

comment:59 Changed 5 years ago by
 Commit changed from 9e42b914d59bda3e0fe3825e6c00c9f377cb6bcc to 4a641fd4714a96cb6a5a7529a55378594633d492
Branch pushed to git repo; I updated commit sha1. New commits:
4a641fd  Trac 19016: fix infinite polynomial elements

comment:60 Changed 5 years ago by
 Commit changed from 4a641fd4714a96cb6a5a7529a55378594633d492 to 86834c5fd61df1714d08efd1cce5e3d540a16d07
Branch pushed to git repo; I updated commit sha1. New commits:
86834c5  Traac 19016: fix similarity classes

comment:61 Changed 5 years ago by
 Commit changed from 86834c5fd61df1714d08efd1cce5e3d540a16d07 to c224fcddc6cc8f7831c71dcf73faa9ff83db4bda
Branch pushed to git repo; I updated commit sha1. New commits:
c224fcd  Trac 19016: fix Kleber tree hash value

comment:62 Changed 5 years ago by
 Commit changed from c224fcddc6cc8f7831c71dcf73faa9ff83db4bda to 27d447ac8989c673ecdba4787875ff3970ea8a32
Branch pushed to git repo; I updated commit sha1. New commits:
27d447a  Trac 19016: fix hash for Additive abelian group elements

comment:63 Changed 5 years ago by
 Commit changed from 27d447ac8989c673ecdba4787875ff3970ea8a32 to fe1a6a7fbb08225f994a1e7efdeeb9f77a0d1bf3
comment:64 Changed 5 years ago by
 Commit changed from fe1a6a7fbb08225f994a1e7efdeeb9f77a0d1bf3 to b7692adc996c8eaeb9aaf29fb765622b10089d04
Branch pushed to git repo; I updated commit sha1. New commits:
b7692ad  Temporary commit: implement constant hash for ideals

comment:65 followup: ↓ 67 Changed 5 years ago by
Any progress? Is this really a blocker?
comment:66 Changed 5 years ago by
 Commit changed from b7692adc996c8eaeb9aaf29fb765622b10089d04 to 4449136135f4e9a13bd53d58eaea0f6597b6d5cc
Branch pushed to git repo; I updated commit sha1. New commits:
8d34cd3  Merge branch 'develop' into t/19016/public/19016

e3895da  trac 19016: doctest fixes and making some code deterministic

aa9bf97  trac 19016: fix doctest that was broken but apparently succeeded by some fluke

aa5f1c3  trac 19016: fix some nondeterministic doctests (and add some deterministic checks)

4449136  trac 19016: fix some doctests (ncalgebras print a set and hence their representation is nondeterministic)

comment:67 in reply to: ↑ 65 Changed 5 years ago by
Replying to vbraun:
Any progress? Is this really a blocker?
The work Vincent has done here is really amazing (because it's such a deep change, and a lot of the changes are really boring!). It'll be a difficult ticket to keep up to date and I think we're close to getting it into shippable form. Also, in the long run the change here is really beneficial. So, I'd hope we can treat it as a blocker so that we can get this in. Technically I don't think this *has* to be a blocker.
I did try to help with a little further progress here.
comment:68 Changed 5 years ago by
Not bad. sage tp all
gives (I did run the long tests though). I am having a look right now.
 sage t src/sage/geometry/polyhedron/library.py # Timed out sage t src/sage/geometry/polyhedron/ppl_lattice_polytope.py # 1 doctest failed sage t src/sage/combinat/posets/posets.py # 2 doctests failed sage t src/sage/structure/parent.pyx # 2 doctests failed sage t src/sage/categories/regular_crystals.py # 1 doctest failed 
Vincent
comment:69 Changed 5 years ago by
 Commit changed from 4449136135f4e9a13bd53d58eaea0f6597b6d5cc to a0f830bf8dc0cbdeb75e45ee7bfee7b4fad33768
comment:70 followup: ↓ 79 Changed 5 years ago by
The failing doctest in parent.pyx
is very weird! The doctest expected a coercion
(matrix space over QQ, number field K) > (matrix space over QQ)
but now it is
(matrix space over QQ, number field K) > (matrix space over K)
The reason is that before we had (keeping the notation from the failing doctest)
sage: ma = a.matrix() sage: cm = get_coercion_model() sage: cm.get_action(ma.parent(), b.parent(), operator.mul, ma, b) is None True
but with the patch applied
sage: cm.get_action(ma.parent(), b.parent(), operator.mul) Right scalar multiplication by Number Field in b241562 with defining polynomial x^2 + 272118 on Full MatrixSpace of 2 by 2 dense matrices over Rational Field
comment:71 followup: ↓ 72 Changed 5 years ago by
 Priority changed from blocker to critical
Since this ticket has a high likelihood to expose bugs/undocumented behaviour elsewhere (see the subtle doctest problem in comment:70, for instance) I think it would be unwise to merge it just prior to a release. I think this is highpriority work, but ideally we'd merge it early in a beta, so that at least it receives ample testing. Given where we are in the release cycle for 6.9, that's incompatible with this ticket being a blocker. I do hope we can find a way to not let this linger and rot, though.
(if someone disagrees, go ahead and set it back to blocker)
comment:72 in reply to: ↑ 71 ; followup: ↓ 75 Changed 5 years ago by
Given where we are in the release cycle for 6.9, that's incompatible with this ticket being a blocker. I do hope we can find a way to not let this linger and rot, though.
That is what stopgaps are made for: hard to fix quickly, and warn against mistakes.
I don't mind seing the status of this ticket change if we add a stopgap in the next release. That will not change the behaviour or anything, nor the doctests.
Nathann
comment:74 Changed 5 years ago by
 Priority changed from critical to blocker
Setting it back to 'blocker' while we have this discussion. This, to not run the risk that Volker announces the next release thinking that this issue is settled.
Nathann
comment:75 in reply to: ↑ 72 ; followup: ↓ 76 Changed 5 years ago by
Replying to ncohen:
That is what stopgaps are made for: hard to fix quickly, and warn against mistakes.
I don't mind seing the status of this ticket change if we add a stopgap in the next release. That will not change the behaviour or anything, nor the doctests.
I'd be OK with that. When one ends up in sage.structure.element.Element.hash , performance will be down the drain anyway, and the warning only prints once.
Incidentally, the hash of symbolic expressions is *not* this one. Furthermore, the renaming feature mentioned in the ticket is highly incompatible with sage's model of immutability and names having mathematical significance. So resolving the title of the ticket will not address several of the perceived issues mentioned in the description.
comment:76 in reply to: ↑ 75 Changed 5 years ago by
I'd be OK with that. When one ends up in sage.structure.element.Element.hash , performance will be down the drain anyway, and the warning only prints once.
Done at #19302 (needs review, blocker)
Nathann
comment:77 Changed 5 years ago by
 Priority changed from blocker to critical
comment:78 Changed 5 years ago by
 Dependencies #18246 deleted
 Description modified (diff)
comment:79 in reply to: ↑ 70 ; followups: ↓ 80 ↓ 84 Changed 5 years ago by
Replying to vdelecroix:
The failing doctest in
parent.pyx
is very weird!
I agree. In fact, I believe the doctest is exposing current buggy behaviour and the changed behaviour on this ticket is resolving this behaviour.
Currently (on unpatched sage) we have
sage: K.<a> = NumberField(x^2 + 2*3*7*11) sage: M = parent(a.matrix()) sage: K_into_MS = K.hom([a.matrix()]) sage: K._unset_coercions_used() sage: M.get_action(K) Right scalar multiplication by Number Field in a with defining polynomial x^2 + 462 on Full MatrixSpace of 2 by 2 dense matrices over Rational Field
and
sage: K.<a> = NumberField(x^2 + 2*3*7*11) sage: M = parent(a.matrix()) sage: K_into_MS = K.hom([a.matrix()]) sage: K._unset_coercions_used() sage: K.register_embedding(K_into_MS) sage: M.get_action(K) is None True
so adding an embedding (which adds edges to the coercion graph) prevents a discovery of an action! I don't think that can ever be OK.
Also note that anything that requires _unset_coercions_used
to be called is a hack (basically by definition).
So, I'm not so sure we should be trying to preserve this behaviour.
comment:80 in reply to: ↑ 79 Changed 5 years ago by
Replying to nbruin:
Replying to vdelecroix:
The failing doctest in
parent.pyx
is very weird!I agree.
I appreciate your support ;) Though, I would like to understand what is happening there. Why changing the hash of elements (not parents) should have something to do with coercions!?
Vincent
comment:81 Changed 5 years ago by
If I roll back all the way to before 2f1f19fbf7b3f5bee68261dd70d3f6fa955dfe23 then I get " M.get_action(K) is None", so it would seem that the change in fgp_element.py has something to do with the behaviour. However, if I revert *just* that change on the branch here I do not see a change.
comment:82 followup: ↓ 83 Changed 5 years ago by
Looks fishy... I propose to rebase the current branch here over #19321 where I cherrypick many of the commits from here. Do you agree to let me do that?
comment:83 in reply to: ↑ 82 Changed 5 years ago by
Replying to vdelecroix:
Looks fishy... I propose to rebase the current branch here over #19321 where I cherrypick many of the commits from here. Do you agree to let me do that?
yes, good idea.
comment:84 in reply to: ↑ 79 Changed 5 years ago by
Found it: the doctest is indeed broken.
Replying to nbruin:
sage: K.<a> = NumberField(x^2 + 2*3*7*11) sage: M = parent(a.matrix()) sage: K_into_MS = K.hom([a.matrix()]) sage: K._unset_coercions_used() sage: K.register_embedding(K_into_MS) sage: M.get_action(K) is None True
The appropriate way to construct the field would be via
sage: Ktemp.<atemp> = NumberField(x^2 + 2*3*7*11) sage: K.<a> = NumberField(atemp.minpoly(),embedding=atemp.matrix()) TypeError: <type 'sage.matrix.matrix_rational_dense.Matrix_rational_dense'> is not hashable and does not implement _cache_key()
which shows the real source of the change in behaviour: previously, the matrix used to define the embedding couldn't be used as a key in the UniqueFactory
cache. On our very first commit, I introduce a _cache_key
to compensate for the missing hash. So unhashable matrices can now be used as cache keys (but of course they shouldn't).
Certificate: You can toggle the behaviour by activating/deactivating the definition of _cache_key on Element.
So the doctest used to create a field that couldn't be directly constructed. With the introduced _cache_key, the field can be constructed.
During action discovery, the field does get reconstructed. This failed in an unexpected way before, which led to abandoning action discovery and then to using the specified embedding.
In our new setup, registering the embedding after the fact does not lead to breaking action discovery anymore, and hence we never get to using the embedding.
It is documented in get_coercion_model().bin_op
that it first tries to find an action and then tries to find a coercion. So this doctest is relying on erroneous behaviour: There is an action between M and K, so the meaning of M.0 * K.0 is: let K.0 act on M.0, not "try to coerce K.0 into M and then multiply M.0 with the result".
MAIN ACTION POINT:: kill offending doctest.
Followup work to be done:
 do we want
_cache_key
on elements? For matrices, the implementation proposed here is robust (i.e., the key is basically what one could get from making an immutable copy of the thing).  should embeddings take precedence over actions? I think that this would mean a horrible overhaul of the coercion framework, so I think the answer needs to be "no". People need to get used to the fact that implicit coercion can't do everything for you. Most of the time you're better of applying maps explicitly.
comment:85 followup: ↓ 86 Changed 5 years ago by
Though, we have currently the following behavior that I do not quite understand
sage: Ktemp.<atemp> = NumberField(x^2 + 2*3*7*11) sage: m = atemp.matrix() sage: m.set_immutable() sage: K.<a> = NumberField(atemp.minpoly(), embedding=m) sage: a*m [462 0] [ 0 462] sage: sage: a*m == m**2 True
comment:86 in reply to: ↑ 85 Changed 5 years ago by
Replying to vdelecroix:
Though, we have currently the following behavior that I do not quite understand
sage: Ktemp.<atemp> = NumberField(x^2 + 2*3*7*11) sage: m = atemp.matrix() sage: m.set_immutable() sage: K.<a> = NumberField(atemp.minpoly(), embedding=m) sage: a*m [462 0] [ 0 462] sage: sage: a*m == m**2 True
That's just because the matrix that is passed to "embedding" for the field that is reconstructed during action discovery is apparently newly constructed (probably it's embedding_morphism(K.0)
) and hence mutable again (you can verify by adding print self.is_mutable()
to _cache_key
). So while you can make the field properly by passing an immutable (and hence hashable) matrix, stock sage still gives buggy behaviour, because subsequent coercion discovery tries to construct the field in an invalid way (and then eats the exception and abandons action discovery).
This is an argument to make _cache_key more generally available: apparently it's difficult to ensure that reconstructed construction parameters are hashable. Of course, to get reliable behaviour we'd need to make sure that m._cache_key() == copy(m,is_immutable=True)
, which is not true presently. (otherwise one can get lots of equalbutnotidentical fields. But "embedding" is rather prone to that anyway)
comment:87 Changed 5 years ago by
 Branch changed from public/19016 to public/19016bis
 Commit changed from a0f830bf8dc0cbdeb75e45ee7bfee7b4fad33768 to 33bd4a92709db4fcf35047e90bf89fea4a35cba8
 Milestone changed from sage6.9 to sage6.10
Rebased version.
Last 10 new commits:
a64ff78  trac 19321: fix some nondeterministic doctests (and add some deterministic checks)

93b537d  trac 19321: doctest fixes and making some code deterministic

23b2b46  trac 19321: fix some doctests in polynomial/plural.pyx

bebb8af  Trac 19321: fix a doctest

7872725  Trac 19016: merge #19321

fc53a49  Trac 19016: Remove silly repr hash on Element and fix failures

6b14aba  Trac 19016: all test pass in combinat/crystals

cf1489d  Trac 19016: hash for quotient ring element

a8d0fca  Trac 19016: implement constant hash for ideals

33bd4a9  Trac 19016: change output order in documentation

comment:88 Changed 5 years ago by
 Commit changed from 33bd4a92709db4fcf35047e90bf89fea4a35cba8 to a7d950423f34fb963379dad74ed8805856c0df2d
Branch pushed to git repo; I updated commit sha1. New commits:
a7d9504  trac 19016: defang erroneous doctest in "parent.register_embedding" (proper fix to be made on other ticket)

comment:89 Changed 5 years ago by
See #19388 for a proper fix to the doctest on register_embedding. That's beyond the scope of this ticket. Hopefully we pass doctests now ...
comment:90 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:91 Changed 5 years ago by
 Commit changed from a7d950423f34fb963379dad74ed8805856c0df2d to f9d2380cd8aa7536949b0fd56d1e4e6fb18e8019
Branch pushed to git repo; I updated commit sha1. New commits:
f9d2380  trac 19016: add doctests to preserve coverage count

comment:92 Changed 5 years ago by
 Commit changed from f9d2380cd8aa7536949b0fd56d1e4e6fb18e8019 to d40eb01ea99eace166c7e132af2e4b36a72a8588
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
d40eb01  trac 19016: add doctests to preserve coverage count

comment:93 Changed 5 years ago by
 Commit changed from d40eb01ea99eace166c7e132af2e4b36a72a8588 to 26f29ab51ca67430951e953459091488973b2387
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
26f29ab  trac 19016: add doctests to preserve coverage count

comment:94 Changed 5 years ago by
 Commit changed from 26f29ab51ca67430951e953459091488973b2387 to d34e7c3dfcda5b31ea4b5f1d112d843ae0d0e549
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
d34e7c3  trac 19016: add doctests to preserve coverage count

comment:95 Changed 5 years ago by
OK, this should provide sufficient doctests to not let the formal coverage count decrease anywhere. There's a new failure that wasn't fixed yet, due to colored permutations being merged which newly depend on the old hash. It illustrates that if we don't merge this ticket soon, we'll just keep playing catchup, because people won't learn they have to provide their own hash.
comment:96 Changed 5 years ago by
I am in favor of merging this one...
comment:97 followup: ↓ 99 Changed 5 years ago by
 Status changed from needs_review to needs_work
 In
src/sage/rings/polynomial/laurent_polynomial.pyx
, the function__hash__
is defined twice in the same class.
 This isn't proper doctest syntax:
+ def __hash__(self): + """ + TESTS: + + It would be nice if the following would produce a list of + 15 distinct hashes. + + sage: K.<t> = FunctionField(QQ) + sage: len({hash(t^i+t^j) for i in [2..2] for j in [i..2]}) + 10 + """ + return hash(self._x)
 Could you justify the need to add lots of comparison functions?
 Why is this needed?
 return self.element_class(self, m) + return self.element_class(self, ZZ(m))
 This looks very suspicious:
[ 0 1] [272118 0]  sage: a.matrix() * b + sage: a.matrix() * b.matrix() [272118 0] [ 0 462]  sage: a * b.matrix() + sage: a.matrix() * b.matrix() [272118 0] [ 0 462]
comment:98 Changed 5 years ago by
 Do you really need to add the constantzero hash to the various ideal classes? Isn't it sufficient to add it to the base class
Ideal_generic
?
comment:99 in reply to: ↑ 97 ; followups: ↓ 101 ↓ 102 ↓ 105 Changed 5 years ago by
Replying to jdemeyer:
 In
src/sage/rings/polynomial/laurent_polynomial.pyx
, the function__hash__
is defined twice in the same class.
Can you give line numbers? I count only two definitions of __hash__
in
src/sage/rings/polynomial/laurent_polynomial.pyx
, and they are on distinct classes:
sage.rings.polynomial.laurent_polynomial.LaurentPolynomial_mpair.__hash__ sage.rings.polynomial.laurent_polynomial.LaurentPolynomial_univariate.__hash__
respectively.
 This isn't proper doctest syntax:
Thanks; should be fixed.
 Could you justify the need to add lots of comparison functions?
Yes, I wonder too. Not including those would save us adding a whole bunch of silly doctests too.
 Why is this needed?
 return self.element_class(self, m) + return self.element_class(self, ZZ(m))
If self.m
should be an Integer
this is a good way of enforcing it. I don't think we did this before? perhaps this is covered in element_class
already. I'm not familiar with this code (and didn't add that patch)
 This looks very suspicious:
[ 0 1] [272118 0]  sage: a.matrix() * b + sage: a.matrix() * b.matrix() [272118 0] [ 0 462]  sage: a * b.matrix() + sage: a.matrix() * b.matrix() [272118 0] [ 0 462]
See comment:86 and #19388.
 Do you really need to add the constantzero hash to the various ideal classes? Isn't it sufficient to add it to the base class
Ideal_generic
?
I think it's better in the long run for sage if we don't. Having a 0 hash is really bad, but not so easy to diagnose quickly. If it really is too difficult to normalize ideal generators in such a way that one can derive a reliable hash, it's probably better if those ideals are not hashable and hence are not used as dict keys. I think the present "0" hashes are just put in so that we don't break legacy code. Future ring implementations should pay more attention to if and how their ideals can be hashed. The problem is more visible if there is no hash available for ideals by default.
comment:100 Changed 5 years ago by
 Commit changed from d34e7c3dfcda5b31ea4b5f1d112d843ae0d0e549 to fcf799ce33270401e9dce7bfcf4f383dbcedc49d
Branch pushed to git repo; I updated commit sha1. New commits:
fcf799c  tract 19016: some further doctest fixes

comment:101 in reply to: ↑ 99 Changed 5 years ago by
Replying to nbruin:
Replying to jdemeyer:
 In
src/sage/rings/polynomial/laurent_polynomial.pyx
, the function__hash__
is defined twice in the same class.Can you give line numbers?
duplicated __hash__ function. I think the problem is that this __hash__
is already included in Sage 6.10.beta0.
I suggest to merge the latest beta in this branch, that will hopefully fix this.
comment:102 in reply to: ↑ 99 ; followup: ↓ 103 Changed 5 years ago by
Replying to nbruin:
The problem is more visible if there is no hash available for ideals by default.
This seems like an argument for not adding the 0 hash to Ideal_generic
then.
By the way, a small improvement might be to take the hash of the parent instead of a constant zero.
comment:103 in reply to: ↑ 102 ; followup: ↓ 104 Changed 5 years ago by
Replying to jdemeyer:
This seems like an argument for not adding the 0 hash to
Ideal_generic
then.
I agree with that. Furthermore, I think we can remove the 0 hash on Ideal_generic
without affecting doctests, so I'd say we should. Let's see what Vincent's opinion is.
By the way, a small improvement might be to take the hash of the parent instead of a constant zero.
Given that the only possibly legitimate use would be to put ideals from the same ring together, I don't think that would be an actual improvement. I'd say that 0 would reflect more properly that the hash is worthless. I also think we should back up each 0 hash with a ticket to either devise a proper hash function or make these unhashable.
comment:104 in reply to: ↑ 103 ; followup: ↓ 106 Changed 5 years ago by
Replying to nbruin:
Replying to jdemeyer:
This seems like an argument for not adding the 0 hash to
Ideal_generic
then.I agree with that. Furthermore, I think we can remove the 0 hash on
Ideal_generic
without affecting doctests, so I'd say we should. Let's see what Vincent's opinion is.
If it works without hash, let us go without of course!
By the way, a small improvement might be to take the hash of the parent instead of a constant zero.
Given that the only possibly legitimate use would be to put ideals from the same ring together, I don't think that would be an actual improvement. I'd say that 0 would reflect more properly that the hash is worthless. I also think we should back up each 0 hash with a ticket to either devise a proper hash function or make these unhashable.
I actually used some, for example in crystals/elementary_crystals.py
. But I tend to agree with Nils that in most cases, this will be useless (or badly used).
comment:105 in reply to: ↑ 99 Changed 5 years ago by
Replying to nbruin:
Replying to jdemeyer:
 Could you justify the need to add lots of comparison functions?
Yes, I wonder too. Not including those would save us adding a whole bunch of silly doctests too.
The only reason was some failing doctests. It appeared that most comparisons were not properly implemented in crystals. I do not care, but I did not find any simpler way to fix the doctests.
The best would be to implement an ElementWrapper_with_cmp
.
 Why is this needed?
 return self.element_class(self, m) + return self.element_class(self, ZZ(m))If
self.m
should be anInteger
this is a good way of enforcing it. I don't think we did this before? perhaps this is covered inelement_class
already. I'm not familiar with this code (and didn't add that patch)
I really don't remember why I did this. The crystal code is weirdly written, and most of my commits were obtained by try and errors.
Vincent
comment:106 in reply to: ↑ 104 Changed 5 years ago by
Replying to vdelecroix:
Replying to nbruin:
I think we can remove the 0 hash on
Ideal_generic
without affecting doctests, so I'd say we should. Let's see what Vincent's opinion is.If it works without hash, let us go without of course!
As Jeroen points out, this ticket needs another merge/rebase. I know I would screw that up. Would you be able to do it? I'd be fully in favour if you'd also implement some of the suggested changes here in the process.
I actually used some, for example in
crystals/elementary_crystals.py
. But I tend to agree with Nils that in most cases, this will be useless (or badly used).
I don't think you did. The hash(self.parent())
is on AbstractSingleCrystalElement
which has it eq
defined as self.parent() is other.parent()
, so making the hash equal to that of the parent is entirely justified there.
I think the self.element_class(self, ZZ(m))
looks justifiable, so I'd be OK with leaving that in.
comment:107 Changed 5 years ago by
 Commit changed from fcf799ce33270401e9dce7bfcf4f383dbcedc49d to aeb120cf3cbdad3e74607619a9ef49542aee0161
comment:108 Changed 5 years ago by
 Commit changed from aeb120cf3cbdad3e74607619a9ef49542aee0161 to c1cf361e83c117521c832a10f1d6248f264972d8
Branch pushed to git repo; I updated commit sha1. New commits:
c1cf361  trac 19016: fix laurent_polynomial hash doctest

comment:109 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:110 Changed 5 years ago by
*PING!* We have fully passing doctests for a week now and all issues raised up to now have been addressed. I also have the impression there is consensus that the "critical" status is warranted. Shall we positively review this ticket and merge it?
comment:111 Changed 5 years ago by
 Reviewers set to Volker Braun
comment:112 Changed 5 years ago by
comment:113 Changed 5 years ago by
 Status changed from needs_review to needs_info
Hi Volker,
Thanks for having a look. On which Sage version are you testing!? If this is not merged early in a beta we have few chances to let it pass! The doctest you mentioned are introduced by a ticket on asymptotic expansions not previously merged in sage.6.10.beta1. I am willing to merge the associated branch in this ticket but you must ensure me that I will not have to do it thousands time.
Vincent
comment:114 followup: ↓ 116 Changed 5 years ago by
How about you try to reproduce it with said ticket, if you can get a new branch by tomorrow I can merge it.
Can you also fix the random failure at #19488
comment:115 Changed 5 years ago by
 Commit changed from c1cf361e83c117521c832a10f1d6248f264972d8 to 81012bc59c29eea8162bcec1ecc21cafa9d1d826
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
2f434d7  write doc and many doctests for substitute

875542d  write AsymptoticExpansion.symbolic_expression

5ac0fea  extend SR._element_constructor_ to accept asymptotic expansions

fa814b0  Trac #19431: merge 6.10.beta0

6a6efc4  introduce parameter R in .symbolic_expression

f39b942  simplify SR._element_constructor

5c3cba3  fix checks whether parent is SR to check if instance of SymbolicRing

ee52932  fixup and doctest of parameter R in .symbolic_expression

04c79ad  Trac 19016: merge #19436

81012bc  Trac 19016: add hash value for asymptotic ring elt

comment:116 in reply to: ↑ 114 ; followup: ↓ 117 Changed 5 years ago by
Replying to vbraun:
How about you try to reproduce it with said ticket, if you can get a new branch by tomorrow I can merge it.
Can you also fix the random failure at #19488
The doctest gets introduced on this ticket and it's a bad one: it's just comparing the parents, so the result is fundamentally illdefined. Just delete the test (or check that it's not an error if you care about that behaviour. I'd say cmp(b,1)
should yield an error).
comment:117 in reply to: ↑ 116 Changed 5 years ago by
Replying to nbruin:
Replying to vbraun:
How about you try to reproduce it with said ticket, if you can get a new branch by tomorrow I can merge it.
Can you also fix the random failure at #19488
The doctest gets introduced on this ticket and it's a bad one: it's just comparing the parents, so the result is fundamentally illdefined. Just delete the test (or check that it's not an error if you care about that behaviour. I'd say
cmp(b,1)
should yield an error).
I agree with Nils that an error would be more appropriate. Though, for the sake of that ticket I would be inclined to follow the default comparison code from Element
(in sage.structure.element
) that is similar to Python one and compare by id
. It is also random though.
comment:118 Changed 5 years ago by
 Commit changed from 81012bc59c29eea8162bcec1ecc21cafa9d1d826 to c7b4f0e0210e6cbad4bcfd62ce3093239f071ff3
Branch pushed to git repo; I updated commit sha1. New commits:
c7b4f0e  Trac 19016: more robust doctest (see #19488)

comment:119 Changed 5 years ago by
 Status changed from needs_info to needs_review
Actually, for the sake of this ticket I think that we should not change anything to the previous behavior of cmp
... simple fix in my last commit.
New commits:
c7b4f0e  Trac 19016: more robust doctest (see #19488)

comment:120 Changed 5 years ago by
 Branch changed from public/19016bis to c7b4f0e0210e6cbad4bcfd62ce3093239f071ff3
 Resolution set to fixed
 Status changed from needs_review to closed
comment:121 Changed 5 years ago by
 Commit c7b4f0e0210e6cbad4bcfd62ce3093239f071ff3 deleted
(applause for what was done here)
comment:122 Changed 5 years ago by
Thanks Volker!
Branch pushed to git repo; I updated commit sha1. New commits:
trac 19016: A more naive sage.structure.element.__hash__