Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#19016 closed defect (fixed)

Better hash for Element

Reported by: ncohen Owned by:
Priority: critical Milestone: sage-6.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 vdelecroix)

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

Change History (122)

comment:1 Changed 4 years ago by ncohen

  • Branch set to u/ncohen/19016
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by git

  • Commit set to 754dc5794a1a7004c8844cf7cfb64220957c36a5

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

754dc57trac 19016: A more naive sage.structure.element.__hash__

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

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

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

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

comment:7 in reply to: ↑ 6 Changed 4 years ago by 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

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

comment:9 Changed 4 years ago by vdelecroix

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

comment:10 in reply to: ↑ 8 ; follow-up: Changed 4 years ago by 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

comment:11 in reply to: ↑ 10 ; follow-up: Changed 4 years ago by 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.

Last edited 4 years ago by nbruin (previous) (diff)

comment:12 in reply to: ↑ 11 Changed 4 years ago by ncohen

  • Milestone changed from sage-6.9 to sage-duplicate/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 follow-up: Changed 4 years ago by vdelecroix

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

comment:15 follow-up: Changed 4 years ago by 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?

comment:16 in reply to: ↑ 15 Changed 4 years ago by 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).

comment:17 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

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

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

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

comment:21 Changed 4 years ago by 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})

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

comment:23 in reply to: ↑ 22 Changed 4 years ago by 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.

comment:24 Changed 4 years ago by vdelecroix

Just a small paranthesis: there are two very different things

  1. Changing the default behavior of the hash function
  1. 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 follow-up: Changed 4 years ago by 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)

comment:26 in reply to: ↑ 25 ; follow-up: Changed 4 years ago by 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.

comment:27 Changed 4 years ago by vdelecroix

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

Last edited 4 years ago by vdelecroix (previous) (diff)

comment:28 Changed 4 years ago by mmarco

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 ; follow-up: Changed 4 years ago by 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?

comment:30 in reply to: ↑ 29 ; follow-up: Changed 4 years ago by 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...

comment:31 Changed 4 years ago by vdelecroix

  • Description modified (diff)
  • Milestone changed from sage-duplicate/invalid/wontfix to sage-6.9

I wrote some more in the ticket description...

comment:32 in reply to: ↑ 30 Changed 4 years ago by nbruin

  • Description modified (diff)
  • Milestone changed from sage-6.9 to sage-duplicate/invalid/wontfix

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)

comment:33 Changed 4 years ago by nbruin

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

  • Description modified (diff)
  • Milestone changed from sage-duplicate/invalid/wontfix to sage-6.9
  • Summary changed from A more naive sage.structure.element.__hash__ to Better hash for Element and CategoryObject

comment:35 follow-up: Changed 4 years ago by vdelecroix

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

  • Description modified (diff)

comment:37 in reply to: ↑ 35 ; follow-up: Changed 4 years ago by 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.

comment:38 in reply to: ↑ 37 ; follow-ups: Changed 4 years ago by 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.

comment:39 in reply to: ↑ 38 Changed 4 years ago by 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)

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

Last edited 4 years ago by nbruin (previous) (diff)

comment:41 Changed 4 years ago by nbruin

  • Branch changed from u/ncohen/19016 to u/nbruin/19016

comment:42 Changed 4 years ago by git

  • Commit changed from 754dc5794a1a7004c8844cf7cfb64220957c36a5 to 829d9cc04c024620af19922ebb91ffded223712a

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

829d9ccalso equip LaurentPolynomial_mpair with a hash

comment:43 Changed 4 years ago by nbruin

Does this do the trick?

comment:44 follow-up: Changed 4 years ago by vdelecroix

  • 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 follow-up: Changed 4 years ago by vdelecroix

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

  • Commit set to ed8b2bf18e3be123b6a83934daea565a01be3509

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

072a017Trac 18246: more cleanup
0bf7d7dTrac 18246: typo
a722920Trac 18246: fix a doctest in rigged_configurations.py
1f79aa5Trac 19016: Remove silly repr hash on Element and fix failures
ec82c74Trac 19016: also equip LaurentPolynomial_mpair with a hash
a2e69fbTrac 19016: hash values for CFiniteSequence
e9b4340Trac 19016: fix hash for abelian group elements
29d3351Trac 19016: hash for matrix group element
70ecc29Trac 19016: hash for indexed free monoid
ed8b2bfTrac 19016: hash for free groups

comment:47 Changed 4 years ago by vdelecroix

  • Authors changed from Nathann Cohen to Nils Bruin, Vincent Delecroix

comment:48 Changed 4 years ago by git

  • Commit changed from ed8b2bf18e3be123b6a83934daea565a01be3509 to 83a758f5c9e19daa0e60914a633ded84d75da4e0

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

83a758fTrac 19016: hash for poset elements

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

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

comment:51 in reply to: ↑ 44 ; follow-up: Changed 4 years ago by 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!

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

comment:53 Changed 4 years ago by git

  • Commit changed from 83a758f5c9e19daa0e60914a633ded84d75da4e0 to 1e49723f1c40990c000b924059bf218bd1d100fd

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

1e49723some more hashes

comment:54 Changed 4 years ago by git

  • Commit changed from 1e49723f1c40990c000b924059bf218bd1d100fd to 79b1ab6293ad8872f8f43945a94a6870c916a372

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

79b1ab6Trac 19016: hash for linear expression

comment:55 Changed 4 years ago by git

  • Commit changed from 79b1ab6293ad8872f8f43945a94a6870c916a372 to 3932a7fc21b9f80f3b13101732f1ce6ddece9f62

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

3932a7fTrac 19016: hash for alternating sign matrices

comment:56 Changed 4 years ago by git

  • Commit changed from 3932a7fc21b9f80f3b13101732f1ce6ddece9f62 to 65f3226dfaf8219b35dd76f48ab1ff766632a09c

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

65f3226Trac 19016: all test pass in combinat/crystals

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

comment:58 Changed 4 years ago by git

  • Commit changed from 65f3226dfaf8219b35dd76f48ab1ff766632a09c to 9e42b914d59bda3e0fe3825e6c00c9f377cb6bcc

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

9e42b91Trac 19016: hash for polyhedra (using Vrepresentation)

comment:59 Changed 4 years ago by git

  • Commit changed from 9e42b914d59bda3e0fe3825e6c00c9f377cb6bcc to 4a641fd4714a96cb6a5a7529a55378594633d492

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

4a641fdTrac 19016: fix infinite polynomial elements

comment:60 Changed 4 years ago by git

  • Commit changed from 4a641fd4714a96cb6a5a7529a55378594633d492 to 86834c5fd61df1714d08efd1cce5e3d540a16d07

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

86834c5Traac 19016: fix similarity classes

comment:61 Changed 4 years ago by git

  • Commit changed from 86834c5fd61df1714d08efd1cce5e3d540a16d07 to c224fcddc6cc8f7831c71dcf73faa9ff83db4bda

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

c224fcdTrac 19016: fix Kleber tree hash value

comment:62 Changed 4 years ago by git

  • Commit changed from c224fcddc6cc8f7831c71dcf73faa9ff83db4bda to 27d447ac8989c673ecdba4787875ff3970ea8a32

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

27d447aTrac 19016: fix hash for Additive abelian group elements

comment:63 Changed 4 years ago by git

  • Commit changed from 27d447ac8989c673ecdba4787875ff3970ea8a32 to fe1a6a7fbb08225f994a1e7efdeeb9f77a0d1bf3

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

233d3a4merge #19016 in Sage-6.9.beta3
2f1f19fTrac 19016: fix fgp vector conversion
a580f01Trac 19016: small optimization in ppl_lattice_polytope
fe1a6a7Trac 19016: hash for quotient ring element

comment:64 Changed 4 years ago by git

  • Commit changed from fe1a6a7fbb08225f994a1e7efdeeb9f77a0d1bf3 to b7692adc996c8eaeb9aaf29fb765622b10089d04

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

b7692adTemporary commit: implement constant hash for ideals

comment:65 follow-up: Changed 4 years ago by vbraun

Any progress? Is this really a blocker?

comment:66 Changed 4 years ago by git

  • Commit changed from b7692adc996c8eaeb9aaf29fb765622b10089d04 to 4449136135f4e9a13bd53d58eaea0f6597b6d5cc

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

8d34cd3Merge branch 'develop' into t/19016/public/19016
e3895datrac 19016: doctest fixes and making some code deterministic
aa9bf97trac 19016: fix doctest that was broken but apparently succeeded by some fluke
aa5f1c3trac 19016: fix some non-deterministic doctests (and add some deterministic checks)
4449136trac 19016: fix some doctests (ncalgebras print a set and hence their representation is non-deterministic)

comment:67 in reply to: ↑ 65 Changed 4 years ago by 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.

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

comment:69 Changed 4 years ago by git

  • Commit changed from 4449136135f4e9a13bd53d58eaea0f6597b6d5cc to a0f830bf8dc0cbdeb75e45ee7bfee7b4fad33768

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

88e063bTrac 19016: faster hash for polyhedron
a0f830bTrac 19016: change output order in documentation

comment:70 follow-up: Changed 4 years ago by 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

comment:71 follow-up: Changed 4 years ago by nbruin

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

comment:72 in reply to: ↑ 71 ; follow-up: Changed 4 years ago by 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

Last edited 4 years ago by ncohen (previous) (diff)

comment:74 Changed 4 years ago by ncohen

  • 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 ; follow-up: Changed 4 years ago by 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.

comment:76 in reply to: ↑ 75 Changed 4 years ago by 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

comment:77 Changed 4 years ago by ncohen

  • Priority changed from blocker to critical

comment:78 Changed 4 years ago by vdelecroix

  • Dependencies #18246 deleted
  • Description modified (diff)

comment:79 in reply to: ↑ 70 ; follow-ups: Changed 4 years ago by 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.

comment:80 in reply to: ↑ 79 Changed 4 years ago by 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

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

comment:82 follow-up: Changed 4 years ago by 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?

comment:83 in reply to: ↑ 82 Changed 4 years ago by 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.

comment:84 in reply to: ↑ 79 Changed 4 years ago by 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.
Last edited 4 years ago by nbruin (previous) (diff)

comment:85 follow-up: Changed 4 years ago by 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

comment:86 in reply to: ↑ 85 Changed 4 years ago by 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)

comment:87 Changed 4 years ago by vdelecroix

  • Branch changed from public/19016 to public/19016-bis
  • Commit changed from a0f830bf8dc0cbdeb75e45ee7bfee7b4fad33768 to 33bd4a92709db4fcf35047e90bf89fea4a35cba8
  • Milestone changed from sage-6.9 to sage-6.10

Rebased version.


Last 10 new commits:

a64ff78trac 19321: fix some non-deterministic doctests (and add some deterministic checks)
93b537dtrac 19321: doctest fixes and making some code deterministic
23b2b46trac 19321: fix some doctests in polynomial/plural.pyx
bebb8afTrac 19321: fix a doctest
7872725Trac 19016: merge #19321
fc53a49Trac 19016: Remove silly repr hash on Element and fix failures
6b14abaTrac 19016: all test pass in combinat/crystals
cf1489dTrac 19016: hash for quotient ring element
a8d0fcaTrac 19016: implement constant hash for ideals
33bd4a9Trac 19016: change output order in documentation

comment:88 Changed 4 years ago by git

  • Commit changed from 33bd4a92709db4fcf35047e90bf89fea4a35cba8 to a7d950423f34fb963379dad74ed8805856c0df2d

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

a7d9504trac 19016: defang erroneous doctest in "parent.register_embedding" (proper fix to be made on other ticket)

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

comment:90 Changed 4 years ago by nbruin

  • Status changed from needs_work to needs_review

comment:91 Changed 4 years ago by git

  • Commit changed from a7d950423f34fb963379dad74ed8805856c0df2d to f9d2380cd8aa7536949b0fd56d1e4e6fb18e8019

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

f9d2380trac 19016: add doctests to preserve coverage count

comment:92 Changed 4 years ago by git

  • Commit changed from f9d2380cd8aa7536949b0fd56d1e4e6fb18e8019 to d40eb01ea99eace166c7e132af2e4b36a72a8588

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d40eb01trac 19016: add doctests to preserve coverage count

comment:93 Changed 4 years ago by git

  • Commit changed from d40eb01ea99eace166c7e132af2e4b36a72a8588 to 26f29ab51ca67430951e953459091488973b2387

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

26f29abtrac 19016: add doctests to preserve coverage count

comment:94 Changed 4 years ago by git

  • Commit changed from 26f29ab51ca67430951e953459091488973b2387 to d34e7c3dfcda5b31ea4b5f1d112d843ae0d0e549

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d34e7c3trac 19016: add doctests to preserve coverage count

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

comment:96 Changed 4 years ago by vdelecroix

I am in favor of merging this one...

comment:97 follow-up: Changed 4 years ago by jdemeyer

  • Status changed from needs_review to needs_work
  1. In src/sage/rings/polynomial/laurent_polynomial.pyx, the function __hash__ is defined twice in the same class.
  1. 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)
    
  1. Could you justify the need to add lots of comparison functions?
  1. Why is this needed?
    -        return self.element_class(self, m)
    +        return self.element_class(self, ZZ(m))
    
  1. 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]
    
Last edited 4 years ago by jdemeyer (previous) (diff)

comment:98 Changed 4 years ago by jdemeyer

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

comment:99 in reply to: ↑ 97 ; follow-ups: Changed 4 years ago by 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.

  1. This isn't proper doctest syntax:

Thanks; should be fixed.

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

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

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

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

Last edited 4 years ago by nbruin (previous) (diff)

comment:100 Changed 4 years ago by git

  • Commit changed from d34e7c3dfcda5b31ea4b5f1d112d843ae0d0e549 to fcf799ce33270401e9dce7bfcf4f383dbcedc49d

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

fcf799ctract 19016: some further doctest fixes

comment:101 in reply to: ↑ 99 Changed 4 years ago by 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.

comment:102 in reply to: ↑ 99 ; follow-up: Changed 4 years ago by 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.

comment:103 in reply to: ↑ 102 ; follow-up: Changed 4 years ago by 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.

comment:104 in reply to: ↑ 103 ; follow-up: Changed 4 years ago by 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).

comment:105 in reply to: ↑ 99 Changed 4 years ago by vdelecroix

Replying to nbruin:

Replying to jdemeyer:

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

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

comment:106 in reply to: ↑ 104 Changed 4 years ago by 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.

comment:107 Changed 4 years ago by git

  • Commit changed from fcf799ce33270401e9dce7bfcf4f383dbcedc49d to aeb120cf3cbdad3e74607619a9ef49542aee0161

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

bfbd7c8Trac 19016: merge sage-6.10.beta0
aeb120cTrac 19016: review #1

comment:108 Changed 4 years ago by git

  • Commit changed from aeb120cf3cbdad3e74607619a9ef49542aee0161 to c1cf361e83c117521c832a10f1d6248f264972d8

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

c1cf361trac 19016: fix laurent_polynomial hash doctest

comment:109 Changed 4 years ago by nbruin

  • Status changed from needs_work to needs_review

comment:110 Changed 4 years ago by 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?

comment:111 Changed 4 years ago by vbraun

  • Reviewers set to Volker Braun

comment:113 Changed 4 years ago by vdelecroix

  • 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 follow-up: Changed 4 years ago by 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

comment:115 Changed 4 years ago by git

  • Commit changed from c1cf361e83c117521c832a10f1d6248f264972d8 to 81012bc59c29eea8162bcec1ecc21cafa9d1d826

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

2f434d7write doc and many doctests for substitute
875542dwrite AsymptoticExpansion.symbolic_expression
5ac0feaextend SR._element_constructor_ to accept asymptotic expansions
fa814b0Trac #19431: merge 6.10.beta0
6a6efc4introduce parameter R in .symbolic_expression
f39b942simplify SR._element_constructor
5c3cba3fix checks whether parent is SR to check if instance of SymbolicRing
ee52932fixup and doctest of parameter R in .symbolic_expression
04c79adTrac 19016: merge #19436
81012bcTrac 19016: add hash value for asymptotic ring elt

comment:116 in reply to: ↑ 114 ; follow-up: Changed 4 years ago by 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).

comment:117 in reply to: ↑ 116 Changed 4 years ago by 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.

comment:118 Changed 4 years ago by git

  • Commit changed from 81012bc59c29eea8162bcec1ecc21cafa9d1d826 to c7b4f0e0210e6cbad4bcfd62ce3093239f071ff3

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

c7b4f0eTrac 19016: more robust doctest (see #19488)

comment:119 Changed 4 years ago by vdelecroix

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

c7b4f0eTrac 19016: more robust doctest (see #19488)

comment:120 Changed 4 years ago by vbraun

  • Branch changed from public/19016-bis to c7b4f0e0210e6cbad4bcfd62ce3093239f071ff3
  • Resolution set to fixed
  • Status changed from needs_review to closed

comment:121 Changed 4 years ago by ncohen

  • Commit c7b4f0e0210e6cbad4bcfd62ce3093239f071ff3 deleted

(applause for what was done here)

comment:122 Changed 4 years ago by vdelecroix

Thanks Volker!

Note: See TracTickets for help on using tickets.