Better hash for Element

[ncohen]

As reported on sage-devel [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 groups

      sage: G = groups.presentation.Cyclic(4)
      sage: G.cayley_graph().vertices()
      [1, a, a^2, a^-2, a^3, a^-1]
  

  and symbolic expressions

  sage: f=sin(x)^2
  sage: g=1-cos(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.

• it might be very bad for performance: see #18215 and #18239 for examples

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 for SageObject, see #18246)
• let it as it is but raise a Warning

[1] ​https://groups.google.com/d/topic/sage-devel/6rXKkF87Gtc/discussion

See also: #19302, #19321, #19331

[git]

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

​754dc57

trac 19016: A more naive sage.structure.element.__hash__

[vdelecroix]

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

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

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

[ncohen]

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.

[vdelecroix]

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.

[ncohen]

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

[nbruin]

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

[vdelecroix]

#18246 needs review (it removes the __hash__ from SageObject).

[ncohen]

-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

[nbruin]

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.

[ncohen]

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

[vdelecroix]

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.

[ncohen]

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

[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?

[vdelecroix]

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

[vbraun]

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.

[mmarco]

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.

[mmarco]

I am getting the following errors:

mmarco@mountain ~/sage $ ./sage -t src/sage/groups/finitely_presented.py 
Running doctests with ID 2015-08-15-00-27-39-750876a9.
Git branch: t/19016/19016
Using --optional=gdb,mpir,python2,sage,scons,tides
Doctesting 1 file.
sage -t --warn-long 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 --warn-long 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

[nbruin]

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

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

[nbruin]

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.

[vdelecroix]

Just a small paranthesis: there are two very different things

1. Changing the default behavior of the hash function

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

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

[vdelecroix]

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.

[vdelecroix]

And note that in the ticket description it is written "Incidentally, it fixes the following bug:"...

[mmarco]

Ok then.

In that case, i think it makes more sense to not have a hash by default, than having a constant one.

[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=1-cos(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?

[vdelecroix]

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=1-cos(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?

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

[vdelecroix]

I wrote some more in the ticket description...

[nbruin]

Replying to vdelecroix:

Element does implement the return 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)

[nbruin]

Shoot. Is there a better way of reverting changes on trac? I ended up cutting and pasting from the change log diff.

[vdelecroix]

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.

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

[vdelecroix]

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.

[nbruin]

Replying to vdelecroix:

Nope. To fix just these test_zero and test_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)

[nbruin]

Replying to vdelecroix:

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.

These are prime ideals of number fields I presume? The HNF of a Z-basis 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 non-identical parents for ideals P1 and P2 that are equal, but not obviously so. So the _cache_key can be a much sloppier hash-like 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__.

[git]

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

​829d9cc

also equip LaurentPolynomial_mpair with a hash

[nbruin]

Does this do the trick?

[vdelecroix]

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.

[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 by doing

sage: S = MyStructure()
sage: e = S.one()
sage: e.change_something()

[git]

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

[git]

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

​83a758f

Trac 19016: hash for poset elements

[vdelecroix]

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

[nbruin]

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

[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!

[vdelecroix]

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 sage-6.9.beta3. Note that our branches are different. I just cherry-pick your two commits above #18246.

[git]

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

​1e49723

some more hashes

[git]

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

​79b1ab6

Trac 19016: hash for linear expression

[git]

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

​3932a7f

Trac 19016: hash for alternating sign matrices

[git]

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

​65f3226

Trac 19016: all test pass in combinat/crystals

[vdelecroix]

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.

[git]

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

​9e42b91

Trac 19016: hash for polyhedra (using Vrepresentation)

[git]

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

​4a641fd

Trac 19016: fix infinite polynomial elements

[git]

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

​86834c5

Traac 19016: fix similarity classes

[git]

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

​c224fcd

Trac 19016: fix Kleber tree hash value

[git]

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

​27d447a

Trac 19016: fix hash for Additive abelian group elements

[git]

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

​233d3a4	merge #19016 in Sage-6.9.beta3
​2f1f19f	Trac 19016: fix fgp vector conversion
​a580f01	Trac 19016: small optimization in ppl_lattice_polytope
​fe1a6a7	Trac 19016: hash for quotient ring element

[git]

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

​b7692ad

Temporary commit: implement constant hash for ideals

[vbraun]

Any progress? Is this really a blocker?

[git]

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 non-deterministic doctests (and add some deterministic checks)
​4449136	trac 19016: fix some doctests (ncalgebras print a set and hence their representation is non-deterministic)

[nbruin]

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.

[vdelecroix]

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

[git]

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

​88e063b	Trac 19016: faster hash for polyhedron
​a0f830b	Trac 19016: change output order in documentation

[vdelecroix]

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

[nbruin]

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 high-priority 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)

[ncohen]

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

[ncohen]

​http://doc.sagemath.org/html/en/developer/trac.html#stopgaps

[ncohen]

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

[nbruin]

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.

[ncohen]

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

[nbruin]

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.

[vdelecroix]

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

[nbruin]

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.

[vdelecroix]

Looks fishy... I propose to rebase the current branch here over #19321 where I cherry-pick many of the commits from here. Do you agree to let me do that?

[nbruin]

Replying to vdelecroix:

Looks fishy... I propose to rebase the current branch here over #19321 where I cherry-pick many of the commits from here. Do you agree to let me do that?

yes, good idea.

[nbruin]

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.

[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

[nbruin]

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 equal-but-not-identical fields. But "embedding" is rather prone to that anyway)

[vdelecroix]

Rebased version.

---

Last 10 new commits:

​a64ff78	trac 19321: fix some non-deterministic 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

[git]

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)

[nbruin]

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

[git]

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

​f9d2380

trac 19016: add doctests to preserve coverage count

[git]

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

[git]

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

[git]

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

[nbruin]

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 catch-up, because people won't learn they have to provide their own hash.

[vdelecroix]

I am in favor of merging this one...

[jdemeyer]

1. In src/sage/rings/polynomial/laurent_polynomial.pyx, the function __hash__ is defined twice in the same class.

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

3. Could you justify the need to add lots of comparison functions?

4. Why is this needed?

   -        return self.element_class(self, m)
   +        return self.element_class(self, ZZ(m))
   

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

[jdemeyer]

6. Do you really need to add the constant-zero hash to the various ideal classes? Isn't it sufficient to add it to the base class Ideal_generic?

[nbruin]

Replying to jdemeyer:

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

2. This isn't proper doctest syntax:

Thanks; should be fixed.

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

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

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

6. Do you really need to add the constant-zero 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.

[git]

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

​fcf799c

tract 19016: some further doctest fixes

[jdemeyer]

Replying to nbruin:

Replying to jdemeyer:

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

[jdemeyer]

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.

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

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.

[vdelecroix]

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

[vdelecroix]

Replying to nbruin:

Replying to jdemeyer:

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

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

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

[nbruin]

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.

[git]

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

​bfbd7c8	Trac 19016: merge sage-6.10.beta0
​aeb120c	Trac 19016: review #1

[git]

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

​c1cf361

trac 19016: fix laurent_polynomial hash doctest

[nbruin]

*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?

[vbraun]

Doctest failures:

​http://build.sagedev.org/release/builders/%20%20slow%20AIMS%20%20%28Debian%207%2064%20bit%29%20incremental/builds/155/steps/shell_4/logs/stdio

[vdelecroix]

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

[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

[git]

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

[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 ill-defined. 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).

[vdelecroix]

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

[git]

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

​c7b4f0e

Trac 19016: more robust doctest (see #19488)

[vdelecroix]

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)

[ncohen]

(applause for what was done here)

[vdelecroix]

Thanks Volker!