Sage: Ticket #19016: Better hash for Element
https://trac.sagemath.org/ticket/19016
<p>
As reported on sage-devel [1], <code>Element</code> implements its hash based on its string representation. This causes a lot of troubles
</p>
<ul><li>it breaks the <code>equality => same hash</code> assumption for finitely presented groups
<pre class="wiki"> sage: G = groups.presentation.Cyclic(4)
sage: G.cayley_graph().vertices()
[1, a, a^2, a^-2, a^3, a^-1]
</pre>and symbolic expressions
<pre class="wiki">sage: f=sin(x)^2
sage: g=1-cos(x)^2
sage: bool(f == g)
True
sage: hash(f) == hash(g)
False
</pre></li></ul><blockquote>
<p>
and possibly many others
</p>
</blockquote>
<ul><li>it is highly incompatible with the <code>rename</code> feature (see also <a class="closed ticket" href="https://trac.sagemath.org/ticket/8119" title="defect: Rename change the hash value of some objects (closed: fixed)">#8119</a>)
<pre class="wiki">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
</pre>and similarly, hashing should not be available on any mutable object.
</li></ul><ul><li>it might be very bad for performance: see <a class="closed ticket" href="https://trac.sagemath.org/ticket/18215" title="enhancement: Huge speed up for hash of quadratic number field elements (closed: fixed)">#18215</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/18239" title="defect: Constructing Cayley graphs is slow (closed: fixed)">#18239</a> for examples
</li></ul><p>
There are several possibilities that are currently being discussed:
</p>
<ul><li>make it return <code>0</code> by default (original proposition of the ticket)
</li><li>make it raise a <code>TypeError</code> by default (as it the case for <code>SageObject</code>, see <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a>)
</li><li>let it as it is but raise a Warning
</li></ul><p>
[1] <a class="ext-link" href="https://groups.google.com/d/topic/sage-devel/6rXKkF87Gtc/discussion"><span class="icon"></span>https://groups.google.com/d/topic/sage-devel/6rXKkF87Gtc/discussion</a>
</p>
<p>
See also: <a class="closed ticket" href="https://trac.sagemath.org/ticket/19302" title="defect: Stopgap for Element.__hash__ (closed: fixed)">#19302</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/19321" title="enhancement: provide better hash functions (closed: fixed)">#19321</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/19331" title="enhancement: Make Element.__hash__ return 0 by default (closed: fixed)">#19331</a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/19016
Trac 1.1.6ncohenWed, 12 Aug 2015 11:19:36 GMTstatus, description changed; branch set
https://trac.sagemath.org/ticket/19016#comment:1
https://trac.sagemath.org/ticket/19016#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/19016?action=diff&version=1">diff</a>)
</li>
<li><strong>branch</strong>
set to <em>u/ncohen/19016</em>
</li>
</ul>
TicketgitWed, 12 Aug 2015 11:21:30 GMTcommit set
https://trac.sagemath.org/ticket/19016#comment:2
https://trac.sagemath.org/ticket/19016#comment:2
<ul>
<li><strong>commit</strong>
set to <em>754dc5794a1a7004c8844cf7cfb64220957c36a5</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=754dc5794a1a7004c8844cf7cfb64220957c36a5"><span class="icon"></span>754dc57</a></td><td><code>trac 19016: A more naive sage.structure.element.__hash__</code>
</td></tr></table>
TicketvdelecroixWed, 12 Aug 2015 11:26:43 GMT
https://trac.sagemath.org/ticket/19016#comment:3
https://trac.sagemath.org/ticket/19016#comment:3
<p>
Hi Nathann,
</p>
<p>
What about <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a>? Just returning <code>0</code> 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.
</p>
<p>
Vincent
</p>
TicketncohenWed, 12 Aug 2015 11:30:00 GMT
https://trac.sagemath.org/ticket/19016#comment:4
https://trac.sagemath.org/ticket/19016#comment:4
<p>
If you see a way to turn <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a> into a <code>needs_review</code> 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.
</p>
<p>
What about a middle ground: raise a warning, which would appear only once, whenever this 0 hash function is used?
</p>
<p>
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.
</p>
<p>
Nathann
</p>
TicketncohenWed, 12 Aug 2015 11:32:49 GMT
https://trac.sagemath.org/ticket/19016#comment:5
https://trac.sagemath.org/ticket/19016#comment:5
<p>
By the way, it is not even the same hash function. Here it is <code>Element.__hash__</code> and it is <code>SageObject.__hash__</code> in <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a>. Both need to be solved of course.
</p>
TicketvdelecroixWed, 12 Aug 2015 11:36:53 GMT
https://trac.sagemath.org/ticket/19016#comment:6
https://trac.sagemath.org/ticket/19016#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:4" title="Comment 4">ncohen</a>:
</p>
<blockquote class="citation">
<p>
If you see a way to turn <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a> into a <code>needs_review</code> 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.
</p>
</blockquote>
<p>
Putting in <code>needs_review</code> just need some efforts. I can dig into it if you are up for a review.
</p>
<blockquote class="citation">
<p>
What about a middle ground: raise a warning, which would appear only once, whenever this 0 hash function is used?
</p>
</blockquote>
<p>
It is already a bit better.
</p>
<blockquote class="citation">
<p>
This is a very bad bug and it needs to be fixed.
</p>
</blockquote>
<p>
It is.
</p>
<blockquote class="citation">
<p>
Creating tickets that we forget is nto much more responsible than doing nothing.
</p>
</blockquote>
<p>
I did not forget as you see ;-)
</p>
<p>
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 <code>__hash__</code> 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.
</p>
TicketncohenWed, 12 Aug 2015 11:57:21 GMT
https://trac.sagemath.org/ticket/19016#comment:7
https://trac.sagemath.org/ticket/19016#comment:7
<blockquote class="citation">
<p>
Putting in <code>needs_review</code> just need some efforts. I can dig into it if you are up for a review.
</p>
</blockquote>
<p>
Remember that <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a> is not even about the hash function that I change here.
</p>
<blockquote class="citation">
<p>
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 <code>__hash__</code> 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.
</p>
</blockquote>
<p>
If you think that we can fix the bug *quickly* by removing the <code>__hash__</code> 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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a>), then this ticket is better than an imaginary one.
</p>
<p>
Concerns about efficiency do not weight much compares to wrong results.
</p>
<p>
Nathann
</p>
TicketnbruinWed, 12 Aug 2015 16:50:16 GMT
https://trac.sagemath.org/ticket/19016#comment:8
https://trac.sagemath.org/ticket/19016#comment:8
<p>
-1 to a constant hash. That leads to such bad performance that it amounts to "wrong results".
</p>
<p>
+1 to removing silly default hashes. Hashing is simply not something that can be done on a very general level.
</p>
<p>
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.
</p>
TicketvdelecroixWed, 12 Aug 2015 17:18:59 GMT
https://trac.sagemath.org/ticket/19016#comment:9
https://trac.sagemath.org/ticket/19016#comment:9
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a> needs review (it removes the <code>__hash__</code> from <code>SageObject</code>).
</p>
TicketncohenWed, 12 Aug 2015 17:22:26 GMT
https://trac.sagemath.org/ticket/19016#comment:10
https://trac.sagemath.org/ticket/19016#comment:10
<blockquote class="citation">
<p>
-1 to a constant hash. That leads to such bad performance that it amounts to "wrong results".
</p>
<p>
+1 to removing silly default hashes. Hashing is simply not something that can be done on a very general level.
</p>
</blockquote>
<p>
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?
</p>
<p>
Nathann
</p>
TicketnbruinWed, 12 Aug 2015 18:01:26 GMT
https://trac.sagemath.org/ticket/19016#comment:11
https://trac.sagemath.org/ticket/19016#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:10" title="Comment 10">ncohen</a>:
</p>
<blockquote class="citation">
<p>
What is your position for "constant hash" Vs "we change nothing and the bug stays"?
</p>
</blockquote>
<p>
"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.
</p>
<p>
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.
</p>
<p>
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.
</p>
TicketncohenWed, 12 Aug 2015 18:11:49 GMTstatus, milestone changed
https://trac.sagemath.org/ticket/19016#comment:12
https://trac.sagemath.org/ticket/19016#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.9</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
<blockquote class="citation">
<blockquote class="citation">
<p>
What is your position for "constant hash" Vs "we change nothing and the bug stays"?
</p>
</blockquote>
<p>
"Change nothing".
</p>
</blockquote>
<p>
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".
</p>
<p>
Free software.
</p>
<p>
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.
</p>
<p>
Nathann
</p>
TicketvdelecroixWed, 12 Aug 2015 18:20:33 GMTstatus changed
https://trac.sagemath.org/ticket/19016#comment:13
https://trac.sagemath.org/ticket/19016#comment:13
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_review</em>
</li>
</ul>
<p>
As I said in <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:9" title="Comment 9">9</a> I did remove the stupid <code>__hash__</code> from <code>SageObject</code> (this is <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a>). Not setting it to <code>0</code> but making it raise a <code>TypeError</code>. It was not a tremendous effort even if I had to dig in things that I do not understand.
</p>
<p>
I guess that the same strategy would also be good for <code>Element</code> and I agree with Nils on this. The warning option proposed in <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:4" title="Comment 4">4</a> 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.
</p>
TicketncohenWed, 12 Aug 2015 18:25:05 GMT
https://trac.sagemath.org/ticket/19016#comment:14
https://trac.sagemath.org/ticket/19016#comment:14
<blockquote class="citation">
<p>
Could we try to found a solution? This is annoying and I am willing to help to fix it.
</p>
</blockquote>
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/18904" title="enhancement: Automatically test optional non-packages (CPLEX, Gurobi, Maple?, ..) (closed: fixed)">#18904</a>, 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.
</p>
<p>
Nathann
</p>
TicketvbraunWed, 12 Aug 2015 19:03:47 GMT
https://trac.sagemath.org/ticket/19016#comment:15
https://trac.sagemath.org/ticket/19016#comment:15
<p>
The default <code>__hash__</code> 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?
</p>
TicketvdelecroixWed, 12 Aug 2015 19:42:54 GMT
https://trac.sagemath.org/ticket/19016#comment:16
https://trac.sagemath.org/ticket/19016#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:15" title="Comment 15">vbraun</a>:
</p>
<blockquote class="citation">
<p>
The default <code>__hash__</code> 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?
</p>
</blockquote>
<p>
That might be an easy move since we would just have to change the category to something like <code>PreviousCategory().WithCanonicalRepresentation()</code>. For me this has to be done on a case by case basis for each <code>Parent</code>. 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.
</p>
<p>
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 <code>Parent/Element</code>? I like Nathann's idea of having a warning if the default hash is called (and the default could be either <code>hash(repr(P))</code> or <code>0</code> I do not really care).
</p>
TicketvdelecroixWed, 12 Aug 2015 20:23:17 GMTstatus changed
https://trac.sagemath.org/ticket/19016#comment:17
https://trac.sagemath.org/ticket/19016#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketvbraunWed, 12 Aug 2015 21:57:39 GMT
https://trac.sagemath.org/ticket/19016#comment:18
https://trac.sagemath.org/ticket/19016#comment:18
<p>
Often you can have normal forms on general grounds, so IMHO would be reasonable to just make <code>CanonicalRepresentation</code> 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 <code>hash(repr(element))</code> 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.
</p>
TicketmmarcoWed, 12 Aug 2015 22:57:01 GMT
https://trac.sagemath.org/ticket/19016#comment:19
https://trac.sagemath.org/ticket/19016#comment:19
<p>
I definitely don't like to have 0 hashes everywhere. I like the solution proposed by Volker: having <span class="underline">hash</span> only on those parents where we actually have a canonical form for each element.
</p>
<p>
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.
</p>
TicketmmarcoFri, 14 Aug 2015 22:35:17 GMT
https://trac.sagemath.org/ticket/19016#comment:20
https://trac.sagemath.org/ticket/19016#comment:20
<p>
I am getting the following errors:
</p>
<pre class="wiki">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
</pre>
TicketnbruinSat, 15 Aug 2015 03:43:35 GMT
https://trac.sagemath.org/ticket/19016#comment:21
https://trac.sagemath.org/ticket/19016#comment:21
<p>
A little digging in Gap's FP compare functions <a class="ext-link" href="https://github.com/gap-system/gap/blob/master/lib/grpfp.gi#L236"><span class="icon"></span>source</a> shows that for finite finitely presented groups, our hash, given these definitions:
</p>
<pre class="wiki">FamilyObj=libgap.function_factory("FamilyObj")
ElementsFamily=libgap.function_factory("ElementsFamily")
FPFaithHom=libgap.function_factory("FPFaithHom")
Image=libgap.function_factory("Image")
</pre><p>
should probably look something like this:
</p>
<pre class="wiki">sage: G=groups.presentation.Cyclic(4)
sage: f=FPFaithHom(ElementsFamily(FamilyObj(G.gap())))
sage: newhash=lambda a: hash(Image(f,a.gap()))
</pre><p>
A little test:
</p>
<pre class="wiki">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})
</pre>
TicketmmarcoSat, 15 Aug 2015 10:20:55 GMT
https://trac.sagemath.org/ticket/19016#comment:22
https://trac.sagemath.org/ticket/19016#comment:22
<p>
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.
</p>
TicketnbruinSat, 15 Aug 2015 17:19:14 GMT
https://trac.sagemath.org/ticket/19016#comment:23
https://trac.sagemath.org/ticket/19016#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:22" title="Comment 22">mmarco</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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.
</p>
<p>
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 <a class="ext-link" href="https://github.com/gap-system/gap/blob/master/lib/grpfp.gi#L236"><span class="icon"></span>MakeFpGroupCompMethod</a>.
</p>
TicketvdelecroixSat, 15 Aug 2015 17:32:35 GMT
https://trac.sagemath.org/ticket/19016#comment:24
https://trac.sagemath.org/ticket/19016#comment:24
<p>
Just a small paranthesis: there are two very different things
</p>
<ol><li>Changing the <strong>default</strong> behavior of the hash function
</li></ol><ol start="2"><li>Having a better hash for FP group elements
</li></ol><p>
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"?
</p>
<p>
Vincent
</p>
TicketmmarcoSat, 15 Aug 2015 17:38:59 GMT
https://trac.sagemath.org/ticket/19016#comment:25
https://trac.sagemath.org/ticket/19016#comment:25
<p>
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)
</p>
TicketvdelecroixSat, 15 Aug 2015 17:47:22 GMT
https://trac.sagemath.org/ticket/19016#comment:26
https://trac.sagemath.org/ticket/19016#comment:26
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:25" title="Comment 25">mmarco</a>:
</p>
<blockquote class="citation">
<p>
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)
</p>
</blockquote>
<p>
I agree that they are related. But <code>__hash__</code> is problematic in other situations and two of them are mentioned in <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a>. Solving the FP group problem will not solve everything as far as I understand it.
</p>
TicketvdelecroixSat, 15 Aug 2015 17:48:43 GMT
https://trac.sagemath.org/ticket/19016#comment:27
https://trac.sagemath.org/ticket/19016#comment:27
<p>
And note that in the ticket description it is written "<strong>Incidentally</strong>, it fixes the following bug:"...
</p>
TicketmmarcoSat, 15 Aug 2015 17:56:13 GMT
https://trac.sagemath.org/ticket/19016#comment:28
https://trac.sagemath.org/ticket/19016#comment:28
<p>
Ok then.
</p>
<p>
In that case, i think it makes more sense to not have a hash by default, than having a constant one.
</p>
TicketnbruinSat, 15 Aug 2015 18:10:14 GMT
https://trac.sagemath.org/ticket/19016#comment:29
https://trac.sagemath.org/ticket/19016#comment:29
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:26" title="Comment 26">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
I agree that they are related. But <code>__hash__</code> is problematic in other situations and two of them are mentioned in <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a>. Solving the FP group problem will not solve everything as far as I understand it.
</p>
</blockquote>
<p>
Indeed, absolutely. And <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a> is now marked fixed. Another example is (of course) SR -- another ring where equality and normal form are impossible to resolve in general
</p>
<pre class="wiki">sage: f=sin(x)^2
sage: g=1-cos(x)^2
sage: bool(f == g)
True
sage: hash(f) == hash(g)
False
</pre><p>
so, hopefully, with <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a> , the last command will lead to an error?
</p>
TicketvdelecroixSat, 15 Aug 2015 18:13:45 GMT
https://trac.sagemath.org/ticket/19016#comment:30
https://trac.sagemath.org/ticket/19016#comment:30
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:29" title="Comment 29">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:26" title="Comment 26">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
I agree that they are related. But <code>__hash__</code> is problematic in other situations and two of them are mentioned in <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a>. Solving the FP group problem will not solve everything as far as I understand it.
</p>
</blockquote>
<p>
Indeed, absolutely. And <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a> is now marked fixed. Another example is (of course) SR -- another ring where equality and normal form are impossible to resolve in general
</p>
<pre class="wiki">sage: f=sin(x)^2
sage: g=1-cos(x)^2
sage: bool(f == g)
True
sage: hash(f) == hash(g)
False
</pre><p>
so, hopefully, with <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a> , the last command will lead to an error?
</p>
</blockquote>
<p>
Sadly not
</p>
<pre class="wiki">sage: f=sin(x)^2
sage: isinstance(f, sage.structure.element.Element)
True
</pre><p>
<code>Element</code> does implement the <code>return hash(str(self))</code> behavior. So this will incidentally be fixed with this ticket...
</p>
TicketvdelecroixSat, 15 Aug 2015 18:45:42 GMTdescription, milestone changed
https://trac.sagemath.org/ticket/19016#comment:31
https://trac.sagemath.org/ticket/19016#comment:31
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/19016?action=diff&version=31">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-duplicate/invalid/wontfix</em> to <em>sage-6.9</em>
</li>
</ul>
<p>
I wrote some more in the ticket description...
</p>
TicketnbruinSat, 15 Aug 2015 19:11:23 GMTdescription, milestone changed
https://trac.sagemath.org/ticket/19016#comment:32
https://trac.sagemath.org/ticket/19016#comment:32
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/19016?action=diff&version=32">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.9</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:30" title="Comment 30">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
<code>Element</code> does implement the <code>return hash(str(self))</code> behavior. So this will incidentally be fixed with this ticket...
</p>
</blockquote>
<p>
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.
</p>
<p>
I have made <a class="new ticket" href="https://trac.sagemath.org/ticket/19038" title="defect: Better hash on FPGroups (new)">#19038</a> for the FPGroup issue (where we're in much better shape in many individual cases)
</p>
TicketnbruinSat, 15 Aug 2015 19:27:54 GMTdescription changed
https://trac.sagemath.org/ticket/19016#comment:33
https://trac.sagemath.org/ticket/19016#comment:33
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/19016?action=diff&version=33">diff</a>)
</li>
</ul>
<p>
Shoot. Is there a better way of reverting changes on trac? I ended up cutting and pasting from the change log diff.
</p>
TicketvdelecroixSat, 15 Aug 2015 19:41:18 GMTmilestone, description, summary changed
https://trac.sagemath.org/ticket/19016#comment:34
https://trac.sagemath.org/ticket/19016#comment:34
<ul>
<li><strong>milestone</strong>
changed from <em>sage-duplicate/invalid/wontfix</em> to <em>sage-6.9</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/19016?action=diff&version=34">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>A more naive sage.structure.element.__hash__</em> to <em>Better hash for Element and CategoryObject</em>
</li>
</ul>
TicketvdelecroixSun, 16 Aug 2015 19:10:45 GMTdescription, summary changed
https://trac.sagemath.org/ticket/19016#comment:35
https://trac.sagemath.org/ticket/19016#comment:35
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/19016?action=diff&version=35">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Better hash for Element and CategoryObject</em> to <em>Better hash for Element</em>
</li>
</ul>
<p>
Arghhh... there are two category tests which ask explicitely for <code>parent.one()</code> and <code>parent.zero()</code> to return hashable elements! These are
</p>
<ul><li><code>Magmas.Unital.ParentMethods._test_one</code>
</li><li><code>AdditiveMagmas.AdditiveUnital.ParentMethods._test_zero</code>
</li></ul><p>
(I do think that those tests are good because most of the time the result is cached)
</p>
<p>
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!
</p>
<p>
Concerning <code>Parent</code> and <code>CategoryObject</code> 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 <code>Parent</code> to be immutable.
</p>
TicketvdelecroixSun, 16 Aug 2015 19:13:01 GMTdescription changed
https://trac.sagemath.org/ticket/19016#comment:36
https://trac.sagemath.org/ticket/19016#comment:36
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/19016?action=diff&version=36">diff</a>)
</li>
</ul>
TicketnbruinSun, 16 Aug 2015 20:05:39 GMT
https://trac.sagemath.org/ticket/19016#comment:37
https://trac.sagemath.org/ticket/19016#comment:37
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:35" title="Comment 35">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
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!
</p>
</blockquote>
<p>
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.
</p>
<p>
I think the proper solution is to lose this equality and hashing requirement and instead subclass to <code>MagmaWithDecidableEquality</code> 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).
</p>
<p>
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.
</p>
TicketvdelecroixSun, 16 Aug 2015 20:30:02 GMT
https://trac.sagemath.org/ticket/19016#comment:38
https://trac.sagemath.org/ticket/19016#comment:38
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:37" title="Comment 37">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:35" title="Comment 35">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
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!
</p>
</blockquote>
<p>
No, worse: any magma should have a decidable equality notion and a hash that's compatible with it.
</p>
</blockquote>
<p>
Nope. To fix just these <code>test_zero</code> and <code>test_one</code> 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 <a class="new ticket" href="https://trac.sagemath.org/ticket/19038" title="defect: Better hash on FPGroups (new)">#19038</a>.
</p>
<p>
New bad news: hashing of ideals. The <code>ResidueField</code> factory in <code>sage.rings.finite_rings.residue_field</code> 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.
</p>
TicketnbruinMon, 17 Aug 2015 02:33:45 GMT
https://trac.sagemath.org/ticket/19016#comment:39
https://trac.sagemath.org/ticket/19016#comment:39
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:38" title="Comment 38">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Nope. To fix just these <code>test_zero</code> and <code>test_one</code> one way is to allow to hash the unit but no other elements...
</p>
</blockquote>
<p>
which makes for horrible code! Are you referring to these lines?
</p>
<pre class="wiki"> # Check that zero is immutable by asking its hash:
tester.assertEqual(type(zero.__hash__()), int)
tester.assertEqual(zero.__hash__(), zero.__hash__())
</pre><p>
It's better to implement this by asking <code>hash(zero)</code>. 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.
</p>
<p>
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:
</p>
<pre class="wiki">if hasattr(zero,"is_immutable"):
tester.assertEqual(zero.is_immutable(),True)
if hasattr(zero,"is_mutable"):
tester.assertEqual(zero.is_mutable(),False)
</pre>
TicketnbruinMon, 17 Aug 2015 02:51:37 GMT
https://trac.sagemath.org/ticket/19016#comment:40
https://trac.sagemath.org/ticket/19016#comment:40
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:38" title="Comment 38">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
New bad news: hashing of ideals. The <code>ResidueField</code> factory in <code>sage.rings.finite_rings.residue_field</code> 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.
</p>
</blockquote>
<p>
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 ...
</p>
<p>
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:
</p>
<p>
Perhaps ideals that cannot properly be hashed should have a <code>_cache_key</code> method instead (see <a class="ext-link" href="http://doc.sagemath.org/html/en/reference/misc/sage/misc/cachefunc.html"><span class="icon"></span>http://doc.sagemath.org/html/en/reference/misc/sage/misc/cachefunc.html</a>). It's not the end of the world if <code>residue_field(P1)</code> and <code>residue_field(P2)</code> give non-identical parents for ideals <code>P1</code> and <code>P2</code> that are equal, but not obviously so. So the <code>_cache_key</code> can be a much sloppier hash-like function. Of course <code>__hash__</code> must be equal for equal ideals.
</p>
<p>
Perhaps a reasonable measure is to define on <code>Element</code> etc.:
</p>
<pre class="wiki">def _cache_key(self):
return (self.parent(),str(self))
</pre><p>
and delete the <code>__hash__</code> (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 <code>_cache_key</code> is only a failover, so one still can get better performance once one defines a<code>__hash__</code>.
</p>
TicketnbruinTue, 18 Aug 2015 08:33:49 GMTbranch changed
https://trac.sagemath.org/ticket/19016#comment:41
https://trac.sagemath.org/ticket/19016#comment:41
<ul>
<li><strong>branch</strong>
changed from <em>u/ncohen/19016</em> to <em>u/nbruin/19016</em>
</li>
</ul>
TicketgitTue, 18 Aug 2015 08:48:09 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:42
https://trac.sagemath.org/ticket/19016#comment:42
<ul>
<li><strong>commit</strong>
changed from <em>754dc5794a1a7004c8844cf7cfb64220957c36a5</em> to <em>829d9cc04c024620af19922ebb91ffded223712a</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=829d9cc04c024620af19922ebb91ffded223712a"><span class="icon"></span>829d9cc</a></td><td><code>also equip LaurentPolynomial_mpair with a hash</code>
</td></tr></table>
TicketnbruinTue, 18 Aug 2015 08:49:14 GMT
https://trac.sagemath.org/ticket/19016#comment:43
https://trac.sagemath.org/ticket/19016#comment:43
<p>
Does this do the trick?
</p>
TicketvdelecroixTue, 18 Aug 2015 10:41:44 GMTdependencies set
https://trac.sagemath.org/ticket/19016#comment:44
https://trac.sagemath.org/ticket/19016#comment:44
<ul>
<li><strong>dependencies</strong>
set to <em>#18246</em>
</li>
</ul>
<p>
The branch must be based over <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a> (which is not yet merged). Otherwise it makes no sense!
</p>
<p>
I also did implement several hashes that I will add to the branch.
</p>
<p>
While going through the code I found
</p>
<pre class="wiki">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
</pre><p>
I opened <a class="closed ticket" href="https://trac.sagemath.org/ticket/19050" title="defect: hash values for matrices (closed: duplicate)">#19050</a>.
</p>
TicketvdelecroixTue, 18 Aug 2015 10:48:24 GMTbranch changed; commit deleted
https://trac.sagemath.org/ticket/19016#comment:45
https://trac.sagemath.org/ticket/19016#comment:45
<ul>
<li><strong>commit</strong>
<em>829d9cc04c024620af19922ebb91ffded223712a</em> deleted
</li>
<li><strong>branch</strong>
changed from <em>u/nbruin/19016</em> to <em>public/19016</em>
</li>
</ul>
<p>
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
</p>
<pre class="wiki">sage: S = MyStructure()
sage: e = S.one()
sage: e.change_something()
</pre>
TicketgitTue, 18 Aug 2015 10:48:51 GMTcommit set
https://trac.sagemath.org/ticket/19016#comment:46
https://trac.sagemath.org/ticket/19016#comment:46
<ul>
<li><strong>commit</strong>
set to <em>ed8b2bf18e3be123b6a83934daea565a01be3509</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=072a017bd5c28142ed12f2b0f1a63f06ae4f3b88"><span class="icon"></span>072a017</a></td><td><code>Trac 18246: more cleanup</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0bf7d7d0676b0363e62925aa5e2aad5ea77eb4a7"><span class="icon"></span>0bf7d7d</a></td><td><code>Trac 18246: typo</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a72292076043e6d73214642c981f3475c7345aef"><span class="icon"></span>a722920</a></td><td><code>Trac 18246: fix a doctest in rigged_configurations.py</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1f79aa545ac445aea7ebcf827a442d94ebd0eb8f"><span class="icon"></span>1f79aa5</a></td><td><code>Trac 19016: Remove silly repr hash on Element and fix failures</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ec82c740383752b8f32c454b6d31bc13fe49ba7e"><span class="icon"></span>ec82c74</a></td><td><code>Trac 19016: also equip LaurentPolynomial_mpair with a hash</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a2e69fb1a65dc462877405f21c480f11c123aac3"><span class="icon"></span>a2e69fb</a></td><td><code>Trac 19016: hash values for CFiniteSequence</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e9b4340d7e0238029e356f79e56ea5d12f0ed404"><span class="icon"></span>e9b4340</a></td><td><code>Trac 19016: fix hash for abelian group elements</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=29d33515ba59e3e08a73c64e93ae20f569b6639a"><span class="icon"></span>29d3351</a></td><td><code>Trac 19016: hash for matrix group element</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=70ecc290ffea673a8caa371feb7a0c7b94421c4e"><span class="icon"></span>70ecc29</a></td><td><code>Trac 19016: hash for indexed free monoid</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ed8b2bf18e3be123b6a83934daea565a01be3509"><span class="icon"></span>ed8b2bf</a></td><td><code>Trac 19016: hash for free groups</code>
</td></tr></table>
TicketvdelecroixTue, 18 Aug 2015 11:35:38 GMTauthor changed
https://trac.sagemath.org/ticket/19016#comment:47
https://trac.sagemath.org/ticket/19016#comment:47
<ul>
<li><strong>author</strong>
changed from <em>Nathann Cohen</em> to <em>Nils Bruin, Vincent Delecroix</em>
</li>
</ul>
TicketgitTue, 18 Aug 2015 11:38:16 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:48
https://trac.sagemath.org/ticket/19016#comment:48
<ul>
<li><strong>commit</strong>
changed from <em>ed8b2bf18e3be123b6a83934daea565a01be3509</em> to <em>83a758f5c9e19daa0e60914a633ded84d75da4e0</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=83a758f5c9e19daa0e60914a633ded84d75da4e0"><span class="icon"></span>83a758f</a></td><td><code>Trac 19016: hash for poset elements</code>
</td></tr></table>
TicketvdelecroixTue, 18 Aug 2015 14:26:41 GMT
https://trac.sagemath.org/ticket/19016#comment:49
https://trac.sagemath.org/ticket/19016#comment:49
<p>
A rough estimation of the classes that need a hash from the doctests
</p>
<ul><li>algebras.quatalg.quaternion_algebra.QuaternionFractionalIdeal_rational
</li><li>combinat
<ul><li>alternating_sign_matrix.AlternatingSignMatrices_with_category.element_class
</li><li>crystals.affinization.AffinizationOfCrystal_with_category.element_class
</li><li>crystals.elementary_crystals.ComponentCrystal_with_category.element_class
</li><li>crystals.elementary_crystals.ElementaryCrystal_with_category.element_class
</li><li>crystals.fast_crystals.FastCrystal_with_category.element_class
</li><li>crystals.monomial_crystals.CrystalOfNakajimaMonomials_with_category.element_class
</li><li>crystals.monomial_crystals.InfinityCrystalOfNakajimaMonomials_with_category.element_class
</li><li>rigged_configurations.kleber_tree.KleberTreeNode
</li><li>root_system.associahedron.Associahedra_with_category.element_class
</li><li>similarity_class_type.PrimarySimilarityClassTypes_with_category.element_class
</li></ul></li><li>geometry
<ul><li>hyperplane_arrangement.hyperplane.AmbientVectorSpace_with_category.element_class
</li><li>polyhedron.backend_cdd.Polyhedra_RDF_cdd_with_category.element_class
</li><li>polyhedron.backend_field.Polyhedra_field_with_category.element_class
</li><li>polyhedron.backend_ppl.Polyhedra_QQ_ppl_with_category.element_class
</li><li>polyhedron.backend_ppl.Polyhedra_ZZ_ppl_with_category.element_class
</li></ul></li><li>groups.additive_abelian.additive_abelian_group.AdditiveAbelianGroup_fixed_gens_with_category.element_class
</li><li>modular.overconvergent.weightspace.AlgebraicWeight
</li><li>monoids
<ul><li>free_monoid_element.FreeMonoid_class_with_category.element_class
</li><li>free_monoid_element.FreeMonoidElement
</li><li>string_monoid_element.StringMonoidElement
</li></ul></li><li>rings
<ul><li>infinity.PlusInfinity
</li><li>polynomial.ideal.Ideal_1poly_field
</li><li>polynomial.infinite_polynomial_element.InfinitePolynomial_dense
</li><li>polynomial.infinite_polynomial_element.InfinitePolynomial_sparse
</li><li>polynomial.multi_polynomial_ideal.MPolynomialIdeal
</li><li>quotient_ring_element.QuotientRing_generic_with_category.element_class
</li></ul></li></ul>
TicketnbruinTue, 18 Aug 2015 15:09:26 GMT
https://trac.sagemath.org/ticket/19016#comment:50
https://trac.sagemath.org/ticket/19016#comment:50
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:45" title="Comment 45">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
I don't think we have another option:
</p>
<ul><li>testing if something is hashable doesn't test if something is mutable
</li><li>something that is immutable can be unhashable. Elements in monoids with an unsolved wordproblem are/should be examples of that
</li><li>python guidelines <em>say</em> that mutable elements should not be hashable, but this is not enforced.
</li><li>python simply doesn't provide a sure-fire way of testing if something is mutable.
</li><li>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.
</li></ul><p>
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.
</p>
TicketnbruinTue, 18 Aug 2015 15:16:15 GMT
https://trac.sagemath.org/ticket/19016#comment:51
https://trac.sagemath.org/ticket/19016#comment:51
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:44" title="Comment 44">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
The branch must be based over <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a> (which is not yet merged).
</p>
</blockquote>
<p>
?? I wasn't able to pull that ticket, presumably because it is merged!
</p>
TicketvdelecroixTue, 18 Aug 2015 15:22:24 GMT
https://trac.sagemath.org/ticket/19016#comment:52
https://trac.sagemath.org/ticket/19016#comment:52
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:51" title="Comment 51">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:44" title="Comment 44">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
The branch must be based over <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a> (which is not yet merged).
</p>
</blockquote>
<p>
?? I wasn't able to pull that ticket, presumably because it is merged!
</p>
</blockquote>
<p>
Nope. It will be merged in sage-6.9.beta3. Note that our branches are different. I just cherry-pick your two commits above <a class="closed ticket" href="https://trac.sagemath.org/ticket/18246" title="defect: remove naive __hash__ from SageObject (closed: fixed)">#18246</a>.
</p>
TicketgitWed, 19 Aug 2015 05:22:39 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:53
https://trac.sagemath.org/ticket/19016#comment:53
<ul>
<li><strong>commit</strong>
changed from <em>83a758f5c9e19daa0e60914a633ded84d75da4e0</em> to <em>1e49723f1c40990c000b924059bf218bd1d100fd</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1e49723f1c40990c000b924059bf218bd1d100fd"><span class="icon"></span>1e49723</a></td><td><code>some more hashes</code>
</td></tr></table>
TicketgitWed, 19 Aug 2015 10:23:10 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:54
https://trac.sagemath.org/ticket/19016#comment:54
<ul>
<li><strong>commit</strong>
changed from <em>1e49723f1c40990c000b924059bf218bd1d100fd</em> to <em>79b1ab6293ad8872f8f43945a94a6870c916a372</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=79b1ab6293ad8872f8f43945a94a6870c916a372"><span class="icon"></span>79b1ab6</a></td><td><code>Trac 19016: hash for linear expression</code>
</td></tr></table>
TicketgitWed, 19 Aug 2015 10:38:06 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:55
https://trac.sagemath.org/ticket/19016#comment:55
<ul>
<li><strong>commit</strong>
changed from <em>79b1ab6293ad8872f8f43945a94a6870c916a372</em> to <em>3932a7fc21b9f80f3b13101732f1ce6ddece9f62</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3932a7fc21b9f80f3b13101732f1ce6ddece9f62"><span class="icon"></span>3932a7f</a></td><td><code>Trac 19016: hash for alternating sign matrices</code>
</td></tr></table>
TicketgitWed, 19 Aug 2015 13:20:45 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:56
https://trac.sagemath.org/ticket/19016#comment:56
<ul>
<li><strong>commit</strong>
changed from <em>3932a7fc21b9f80f3b13101732f1ce6ddece9f62</em> to <em>65f3226dfaf8219b35dd76f48ab1ff766632a09c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=65f3226dfaf8219b35dd76f48ab1ff766632a09c"><span class="icon"></span>65f3226</a></td><td><code>Trac 19016: all test pass in combinat/crystals</code>
</td></tr></table>
TicketvdelecroixWed, 19 Aug 2015 13:22:40 GMT
https://trac.sagemath.org/ticket/19016#comment:57
https://trac.sagemath.org/ticket/19016#comment:57
<p>
I had hard time with <code>sage.structure.element_wrapper</code> which is intensively used in crystal code. The comparison code looks completely broken as I had to implement all the family of <code>__eq__</code>, <code>__ne__</code>, <code>__lt__</code>, etc as well as <code>__cmp__</code>.
</p>
<p>
I did not change any doctest in the code, but because I introduced many new functions some of them lack doctest.
</p>
TicketgitWed, 19 Aug 2015 14:17:39 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:58
https://trac.sagemath.org/ticket/19016#comment:58
<ul>
<li><strong>commit</strong>
changed from <em>65f3226dfaf8219b35dd76f48ab1ff766632a09c</em> to <em>9e42b914d59bda3e0fe3825e6c00c9f377cb6bcc</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=9e42b914d59bda3e0fe3825e6c00c9f377cb6bcc"><span class="icon"></span>9e42b91</a></td><td><code>Trac 19016: hash for polyhedra (using Vrepresentation)</code>
</td></tr></table>
TicketgitWed, 19 Aug 2015 18:10:25 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:59
https://trac.sagemath.org/ticket/19016#comment:59
<ul>
<li><strong>commit</strong>
changed from <em>9e42b914d59bda3e0fe3825e6c00c9f377cb6bcc</em> to <em>4a641fd4714a96cb6a5a7529a55378594633d492</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4a641fd4714a96cb6a5a7529a55378594633d492"><span class="icon"></span>4a641fd</a></td><td><code>Trac 19016: fix infinite polynomial elements</code>
</td></tr></table>
TicketgitWed, 19 Aug 2015 22:58:26 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:60
https://trac.sagemath.org/ticket/19016#comment:60
<ul>
<li><strong>commit</strong>
changed from <em>4a641fd4714a96cb6a5a7529a55378594633d492</em> to <em>86834c5fd61df1714d08efd1cce5e3d540a16d07</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=86834c5fd61df1714d08efd1cce5e3d540a16d07"><span class="icon"></span>86834c5</a></td><td><code>Traac 19016: fix similarity classes</code>
</td></tr></table>
TicketgitWed, 19 Aug 2015 23:07:27 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:61
https://trac.sagemath.org/ticket/19016#comment:61
<ul>
<li><strong>commit</strong>
changed from <em>86834c5fd61df1714d08efd1cce5e3d540a16d07</em> to <em>c224fcddc6cc8f7831c71dcf73faa9ff83db4bda</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c224fcddc6cc8f7831c71dcf73faa9ff83db4bda"><span class="icon"></span>c224fcd</a></td><td><code>Trac 19016: fix Kleber tree hash value</code>
</td></tr></table>
TicketgitWed, 19 Aug 2015 23:18:24 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:62
https://trac.sagemath.org/ticket/19016#comment:62
<ul>
<li><strong>commit</strong>
changed from <em>c224fcddc6cc8f7831c71dcf73faa9ff83db4bda</em> to <em>27d447ac8989c673ecdba4787875ff3970ea8a32</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=27d447ac8989c673ecdba4787875ff3970ea8a32"><span class="icon"></span>27d447a</a></td><td><code>Trac 19016: fix hash for Additive abelian group elements</code>
</td></tr></table>
TicketgitSun, 23 Aug 2015 10:55:30 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:63
https://trac.sagemath.org/ticket/19016#comment:63
<ul>
<li><strong>commit</strong>
changed from <em>27d447ac8989c673ecdba4787875ff3970ea8a32</em> to <em>fe1a6a7fbb08225f994a1e7efdeeb9f77a0d1bf3</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=233d3a4cb40325194bce01c7ed5098af15e343ca"><span class="icon"></span>233d3a4</a></td><td><code>merge #19016 in Sage-6.9.beta3</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2f1f19fbf7b3f5bee68261dd70d3f6fa955dfe23"><span class="icon"></span>2f1f19f</a></td><td><code>Trac 19016: fix fgp vector conversion</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a580f0140148220fc96bcf5060c4e0a53ea66d22"><span class="icon"></span>a580f01</a></td><td><code>Trac 19016: small optimization in ppl_lattice_polytope</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=fe1a6a7fbb08225f994a1e7efdeeb9f77a0d1bf3"><span class="icon"></span>fe1a6a7</a></td><td><code>Trac 19016: hash for quotient ring element</code>
</td></tr></table>
TicketgitSun, 23 Aug 2015 18:08:51 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:64
https://trac.sagemath.org/ticket/19016#comment:64
<ul>
<li><strong>commit</strong>
changed from <em>fe1a6a7fbb08225f994a1e7efdeeb9f77a0d1bf3</em> to <em>b7692adc996c8eaeb9aaf29fb765622b10089d04</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b7692adc996c8eaeb9aaf29fb765622b10089d04"><span class="icon"></span>b7692ad</a></td><td><code>Temporary commit: implement constant hash for ideals</code>
</td></tr></table>
TicketvbraunFri, 25 Sep 2015 21:57:56 GMT
https://trac.sagemath.org/ticket/19016#comment:65
https://trac.sagemath.org/ticket/19016#comment:65
<p>
Any progress? Is this really a blocker?
</p>
TicketgitSat, 26 Sep 2015 01:35:43 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:66
https://trac.sagemath.org/ticket/19016#comment:66
<ul>
<li><strong>commit</strong>
changed from <em>b7692adc996c8eaeb9aaf29fb765622b10089d04</em> to <em>4449136135f4e9a13bd53d58eaea0f6597b6d5cc</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8d34cd3ca4df88a502dee956dbead93b085aaed5"><span class="icon"></span>8d34cd3</a></td><td><code>Merge branch 'develop' into t/19016/public/19016</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e3895daa2425be20dda105637d27f0f9f9533d36"><span class="icon"></span>e3895da</a></td><td><code>trac 19016: doctest fixes and making some code deterministic</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=aa9bf976ab3922c1d65d11d48045a2b6b2ddab2c"><span class="icon"></span>aa9bf97</a></td><td><code>trac 19016: fix doctest that was broken but apparently succeeded by some fluke</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=aa5f1c36469807146ff850d61c708e36d5d30e74"><span class="icon"></span>aa5f1c3</a></td><td><code>trac 19016: fix some non-deterministic doctests (and add some deterministic checks)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4449136135f4e9a13bd53d58eaea0f6597b6d5cc"><span class="icon"></span>4449136</a></td><td><code>trac 19016: fix some doctests (ncalgebras print a set and hence their representation is non-deterministic)</code>
</td></tr></table>
TicketnbruinSat, 26 Sep 2015 01:40:47 GMT
https://trac.sagemath.org/ticket/19016#comment:67
https://trac.sagemath.org/ticket/19016#comment:67
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:65" title="Comment 65">vbraun</a>:
</p>
<blockquote class="citation">
<p>
Any progress? Is this really a blocker?
</p>
</blockquote>
<p>
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.
</p>
<p>
I did try to help with a little further progress here.
</p>
TicketvdelecroixSat, 26 Sep 2015 02:28:47 GMT
https://trac.sagemath.org/ticket/19016#comment:68
https://trac.sagemath.org/ticket/19016#comment:68
<p>
Not bad. <code>sage -tp --all</code> gives (I did run the long tests though). I am having a look right now.
</p>
<pre class="wiki">----------------------------------------------------------------------
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
----------------------------------------------------------------------
</pre><p>
Vincent
</p>
TicketgitSat, 26 Sep 2015 03:35:15 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:69
https://trac.sagemath.org/ticket/19016#comment:69
<ul>
<li><strong>commit</strong>
changed from <em>4449136135f4e9a13bd53d58eaea0f6597b6d5cc</em> to <em>a0f830bf8dc0cbdeb75e45ee7bfee7b4fad33768</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=88e063b644c37afe7c0e13ff8359adc4efd89b3d"><span class="icon"></span>88e063b</a></td><td><code>Trac 19016: faster hash for polyhedron</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a0f830bf8dc0cbdeb75e45ee7bfee7b4fad33768"><span class="icon"></span>a0f830b</a></td><td><code>Trac 19016: change output order in documentation</code>
</td></tr></table>
TicketvdelecroixSat, 26 Sep 2015 03:44:25 GMT
https://trac.sagemath.org/ticket/19016#comment:70
https://trac.sagemath.org/ticket/19016#comment:70
<p>
The failing doctest in <code>parent.pyx</code> is very weird! The doctest expected a coercion
</p>
<pre class="wiki">(matrix space over QQ, number field K) -> (matrix space over QQ)
</pre><p>
but now it is
</p>
<pre class="wiki">(matrix space over QQ, number field K) -> (matrix space over K)
</pre><p>
The reason is that before we had (keeping the notation from the failing doctest)
</p>
<pre class="wiki">sage: ma = a.matrix()
sage: cm = get_coercion_model()
sage: cm.get_action(ma.parent(), b.parent(), operator.mul, ma, b) is None
True
</pre><p>
but with the patch applied
</p>
<pre class="wiki">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
</pre>
TicketnbruinMon, 28 Sep 2015 17:02:00 GMTpriority changed
https://trac.sagemath.org/ticket/19016#comment:71
https://trac.sagemath.org/ticket/19016#comment:71
<ul>
<li><strong>priority</strong>
changed from <em>blocker</em> to <em>critical</em>
</li>
</ul>
<p>
Since this ticket has a high likelihood to expose bugs/undocumented behaviour elsewhere (see the subtle doctest problem in <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:70" title="Comment 70">comment:70</a>, 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.
</p>
<p>
(if someone disagrees, go ahead and set it back to blocker)
</p>
TicketncohenMon, 28 Sep 2015 17:05:30 GMT
https://trac.sagemath.org/ticket/19016#comment:72
https://trac.sagemath.org/ticket/19016#comment:72
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
That is what stopgaps are made for: hard to fix quickly, and warn against mistakes.
</p>
<p>
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.
</p>
<p>
Nathann
</p>
TicketncohenMon, 28 Sep 2015 17:07:52 GMT
https://trac.sagemath.org/ticket/19016#comment:73
https://trac.sagemath.org/ticket/19016#comment:73
<p>
<a class="ext-link" href="http://doc.sagemath.org/html/en/developer/trac.html#stopgaps"><span class="icon"></span>http://doc.sagemath.org/html/en/developer/trac.html#stopgaps</a>
</p>
TicketncohenMon, 28 Sep 2015 17:12:09 GMTpriority changed
https://trac.sagemath.org/ticket/19016#comment:74
https://trac.sagemath.org/ticket/19016#comment:74
<ul>
<li><strong>priority</strong>
changed from <em>critical</em> to <em>blocker</em>
</li>
</ul>
<p>
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.
</p>
<p>
Nathann
</p>
TicketnbruinMon, 28 Sep 2015 17:56:22 GMT
https://trac.sagemath.org/ticket/19016#comment:75
https://trac.sagemath.org/ticket/19016#comment:75
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:72" title="Comment 72">ncohen</a>:
</p>
<blockquote class="citation">
<p>
That is what stopgaps are made for: hard to fix quickly, and warn against mistakes.
</p>
<p>
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.
</p>
</blockquote>
<p>
I'd be OK with that. When one ends up in sage.structure.element.Element.<span class="underline">hash</span> , performance will be down the drain anyway, and the warning only prints once.
</p>
<p>
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.
</p>
TicketncohenMon, 28 Sep 2015 18:36:34 GMT
https://trac.sagemath.org/ticket/19016#comment:76
https://trac.sagemath.org/ticket/19016#comment:76
<blockquote class="citation">
<p>
I'd be OK with that. When one ends up in sage.structure.element.Element.<span class="underline">hash</span> , performance will be down the drain anyway, and the warning only prints once.
</p>
</blockquote>
<p>
Done at <a class="closed ticket" href="https://trac.sagemath.org/ticket/19302" title="defect: Stopgap for Element.__hash__ (closed: fixed)">#19302</a> (needs review, blocker)
</p>
<p>
Nathann
</p>
TicketncohenMon, 28 Sep 2015 18:36:51 GMTpriority changed
https://trac.sagemath.org/ticket/19016#comment:77
https://trac.sagemath.org/ticket/19016#comment:77
<ul>
<li><strong>priority</strong>
changed from <em>blocker</em> to <em>critical</em>
</li>
</ul>
TicketvdelecroixFri, 02 Oct 2015 00:39:23 GMTdescription changed; dependencies deleted
https://trac.sagemath.org/ticket/19016#comment:78
https://trac.sagemath.org/ticket/19016#comment:78
<ul>
<li><strong>dependencies</strong>
<em>#18246</em> deleted
</li>
<li><strong>description</strong>
modified (<a href="/ticket/19016?action=diff&version=78">diff</a>)
</li>
</ul>
TicketnbruinFri, 09 Oct 2015 00:17:04 GMT
https://trac.sagemath.org/ticket/19016#comment:79
https://trac.sagemath.org/ticket/19016#comment:79
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:70" title="Comment 70">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
The failing doctest in <code>parent.pyx</code> is very weird!
</p>
</blockquote>
<p>
I agree. In fact, I believe the doctest is exposing current buggy behaviour and the changed behaviour on this ticket is resolving this behaviour.
</p>
<p>
Currently (on unpatched sage) we have
</p>
<pre class="wiki">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
</pre><p>
and
</p>
<pre class="wiki">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
</pre><p>
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.
</p>
<p>
Also note that anything that requires <code>_unset_coercions_used</code> to be called is a hack (basically by definition).
</p>
<p>
So, I'm not so sure we should be trying to preserve this behaviour.
</p>
TicketvdelecroixFri, 09 Oct 2015 02:55:21 GMT
https://trac.sagemath.org/ticket/19016#comment:80
https://trac.sagemath.org/ticket/19016#comment:80
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:79" title="Comment 79">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:70" title="Comment 70">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
The failing doctest in <code>parent.pyx</code> is very weird!
</p>
</blockquote>
<p>
I agree.
</p>
</blockquote>
<p>
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!?
</p>
<p>
Vincent
</p>
TicketnbruinFri, 09 Oct 2015 04:59:16 GMT
https://trac.sagemath.org/ticket/19016#comment:81
https://trac.sagemath.org/ticket/19016#comment:81
<p>
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.
</p>
TicketvdelecroixFri, 09 Oct 2015 09:13:17 GMT
https://trac.sagemath.org/ticket/19016#comment:82
https://trac.sagemath.org/ticket/19016#comment:82
<p>
Looks fishy... I propose to rebase the current branch here over <a class="closed ticket" href="https://trac.sagemath.org/ticket/19321" title="enhancement: provide better hash functions (closed: fixed)">#19321</a> where I cherry-pick many of the commits from here. Do you agree to let me do that?
</p>
TicketnbruinFri, 09 Oct 2015 16:30:21 GMT
https://trac.sagemath.org/ticket/19016#comment:83
https://trac.sagemath.org/ticket/19016#comment:83
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:82" title="Comment 82">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Looks fishy... I propose to rebase the current branch here over <a class="closed ticket" href="https://trac.sagemath.org/ticket/19321" title="enhancement: provide better hash functions (closed: fixed)">#19321</a> where I cherry-pick many of the commits from here. Do you agree to let me do that?
</p>
</blockquote>
<p>
yes, good idea.
</p>
TicketnbruinFri, 09 Oct 2015 18:32:05 GMT
https://trac.sagemath.org/ticket/19016#comment:84
https://trac.sagemath.org/ticket/19016#comment:84
<p>
Found it: the doctest is indeed broken.
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:79" title="Comment 79">nbruin</a>:
</p>
<blockquote class="citation">
<pre class="wiki">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
</pre></blockquote>
<p>
The appropriate way to construct the field would be via
</p>
<pre class="wiki">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()
</pre><p>
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 <code>UniqueFactory</code> cache. On our very first commit, I introduce a <code>_cache_key</code> to compensate for the missing hash. So unhashable matrices can now be used as cache keys (but of course they shouldn't).
</p>
<p>
<strong>Certificate:</strong> You can toggle the behaviour by activating/deactivating the definition of _cache_key on Element.
</p>
<p>
So the doctest used to create a field that couldn't be directly constructed. With the introduced _cache_key, the field can be constructed.
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
It is documented in <code>get_coercion_model().bin_op</code> 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".
</p>
<p>
<strong>MAIN ACTION POINT:</strong>: kill offending doctest.
</p>
<p>
Followup work to be done:
</p>
<ul><li>do we want <code>_cache_key</code> 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).
</li><li>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.
</li></ul>
TicketvdelecroixSat, 10 Oct 2015 04:26:19 GMT
https://trac.sagemath.org/ticket/19016#comment:85
https://trac.sagemath.org/ticket/19016#comment:85
<p>
Though, we have currently the following behavior that I do not quite understand
</p>
<pre class="wiki">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
</pre>
TicketnbruinSat, 10 Oct 2015 05:08:49 GMT
https://trac.sagemath.org/ticket/19016#comment:86
https://trac.sagemath.org/ticket/19016#comment:86
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:85" title="Comment 85">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Though, we have currently the following behavior that I do not quite understand
</p>
<pre class="wiki">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
</pre></blockquote>
<p>
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 <code>embedding_morphism(K.0)</code>) and hence mutable again (you can verify by adding <code>print self.is_mutable()</code> to <code>_cache_key</code>). 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).
</p>
<p>
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 <code>m._cache_key() == copy(m,is_immutable=True)</code>, which is not true presently. (otherwise one can get lots of equal-but-not-identical fields. But "embedding" is rather prone to that anyway)
</p>
TicketvdelecroixSat, 10 Oct 2015 14:30:06 GMTcommit, branch, milestone changed
https://trac.sagemath.org/ticket/19016#comment:87
https://trac.sagemath.org/ticket/19016#comment:87
<ul>
<li><strong>commit</strong>
changed from <em>a0f830bf8dc0cbdeb75e45ee7bfee7b4fad33768</em> to <em>33bd4a92709db4fcf35047e90bf89fea4a35cba8</em>
</li>
<li><strong>branch</strong>
changed from <em>public/19016</em> to <em>public/19016-bis</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.9</em> to <em>sage-6.10</em>
</li>
</ul>
<p>
Rebased version.
</p>
<hr />
<p>
Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a64ff78d0d1a6d232e3fb6eafad43f66c6ad952b"><span class="icon"></span>a64ff78</a></td><td><code>trac 19321: fix some non-deterministic doctests (and add some deterministic checks)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=93b537d6d02ba40bb5253faeae2aa293756b055a"><span class="icon"></span>93b537d</a></td><td><code>trac 19321: doctest fixes and making some code deterministic</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=23b2b461a1821aba592c09e85ae9c19846bad1bc"><span class="icon"></span>23b2b46</a></td><td><code>trac 19321: fix some doctests in polynomial/plural.pyx</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=bebb8af5eaa7ff834a03e9c887da69b118a257af"><span class="icon"></span>bebb8af</a></td><td><code>Trac 19321: fix a doctest</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7872725ec7e313eb9cd0b9cb6a204147b7a8caac"><span class="icon"></span>7872725</a></td><td><code>Trac 19016: merge #19321</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=fc53a493965bf3767e47be2552425fca4e70e483"><span class="icon"></span>fc53a49</a></td><td><code>Trac 19016: Remove silly repr hash on Element and fix failures</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6b14aba8ab15850a7a496094580fa81adf446cef"><span class="icon"></span>6b14aba</a></td><td><code>Trac 19016: all test pass in combinat/crystals</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=cf1489d694224bbe6563b7837fa68615d6038a03"><span class="icon"></span>cf1489d</a></td><td><code>Trac 19016: hash for quotient ring element</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a8d0fcaffaa977c297db52176041c38807cc55da"><span class="icon"></span>a8d0fca</a></td><td><code>Trac 19016: implement constant hash for ideals</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=33bd4a92709db4fcf35047e90bf89fea4a35cba8"><span class="icon"></span>33bd4a9</a></td><td><code>Trac 19016: change output order in documentation</code>
</td></tr></table>
TicketgitSat, 10 Oct 2015 18:58:35 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:88
https://trac.sagemath.org/ticket/19016#comment:88
<ul>
<li><strong>commit</strong>
changed from <em>33bd4a92709db4fcf35047e90bf89fea4a35cba8</em> to <em>a7d950423f34fb963379dad74ed8805856c0df2d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a7d950423f34fb963379dad74ed8805856c0df2d"><span class="icon"></span>a7d9504</a></td><td><code>trac 19016: defang erroneous doctest in "parent.register_embedding" (proper fix to be made on other ticket)</code>
</td></tr></table>
TicketnbruinSat, 10 Oct 2015 19:22:27 GMT
https://trac.sagemath.org/ticket/19016#comment:89
https://trac.sagemath.org/ticket/19016#comment:89
<p>
See <a class="new ticket" href="https://trac.sagemath.org/ticket/19388" title="enhancement: Write better doctest for parent.register_embedding (new)">#19388</a> for a proper fix to the doctest on register_embedding. That's beyond the scope of this ticket. Hopefully we pass doctests now ...
</p>
TicketnbruinSat, 10 Oct 2015 21:58:17 GMTstatus changed
https://trac.sagemath.org/ticket/19016#comment:90
https://trac.sagemath.org/ticket/19016#comment:90
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketgitFri, 16 Oct 2015 19:11:09 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:91
https://trac.sagemath.org/ticket/19016#comment:91
<ul>
<li><strong>commit</strong>
changed from <em>a7d950423f34fb963379dad74ed8805856c0df2d</em> to <em>f9d2380cd8aa7536949b0fd56d1e4e6fb18e8019</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f9d2380cd8aa7536949b0fd56d1e4e6fb18e8019"><span class="icon"></span>f9d2380</a></td><td><code>trac 19016: add doctests to preserve coverage count</code>
</td></tr></table>
TicketgitSat, 17 Oct 2015 19:54:32 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:92
https://trac.sagemath.org/ticket/19016#comment:92
<ul>
<li><strong>commit</strong>
changed from <em>f9d2380cd8aa7536949b0fd56d1e4e6fb18e8019</em> to <em>d40eb01ea99eace166c7e132af2e4b36a72a8588</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d40eb01ea99eace166c7e132af2e4b36a72a8588"><span class="icon"></span>d40eb01</a></td><td><code>trac 19016: add doctests to preserve coverage count</code>
</td></tr></table>
TicketgitSat, 17 Oct 2015 20:10:14 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:93
https://trac.sagemath.org/ticket/19016#comment:93
<ul>
<li><strong>commit</strong>
changed from <em>d40eb01ea99eace166c7e132af2e4b36a72a8588</em> to <em>26f29ab51ca67430951e953459091488973b2387</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=26f29ab51ca67430951e953459091488973b2387"><span class="icon"></span>26f29ab</a></td><td><code>trac 19016: add doctests to preserve coverage count</code>
</td></tr></table>
TicketgitSat, 17 Oct 2015 20:13:01 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:94
https://trac.sagemath.org/ticket/19016#comment:94
<ul>
<li><strong>commit</strong>
changed from <em>26f29ab51ca67430951e953459091488973b2387</em> to <em>d34e7c3dfcda5b31ea4b5f1d112d843ae0d0e549</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d34e7c3dfcda5b31ea4b5f1d112d843ae0d0e549"><span class="icon"></span>d34e7c3</a></td><td><code>trac 19016: add doctests to preserve coverage count</code>
</td></tr></table>
TicketnbruinSat, 17 Oct 2015 20:17:30 GMT
https://trac.sagemath.org/ticket/19016#comment:95
https://trac.sagemath.org/ticket/19016#comment:95
<p>
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.
</p>
TicketvdelecroixSat, 17 Oct 2015 20:47:04 GMT
https://trac.sagemath.org/ticket/19016#comment:96
https://trac.sagemath.org/ticket/19016#comment:96
<p>
I am in favor of merging this one...
</p>
TicketjdemeyerSat, 17 Oct 2015 20:48:56 GMTstatus changed
https://trac.sagemath.org/ticket/19016#comment:97
https://trac.sagemath.org/ticket/19016#comment:97
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<ol><li>In <code>src/sage/rings/polynomial/laurent_polynomial.pyx</code>, the function <code>__hash__</code> is defined twice in the same class.
</li></ol><ol start="2"><li>This isn't proper doctest syntax:
<div class="wiki-code"><div class="code"><pre><span class="gi">+ 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)
</span></pre></div></div></li></ol><ol start="3"><li>Could you justify the need to add lots of comparison functions?
</li></ol><ol start="4"><li>Why is this needed?
<div class="wiki-code"><div class="code"><pre><span class="gd">- return self.element_class(self, m)
</span><span class="gi">+ return self.element_class(self, ZZ(m))
</span></pre></div></div></li></ol><ol start="5"><li>This looks very suspicious:
<div class="wiki-code"><div class="code"><pre> [ 0 1]
[-272118 0]
<span class="gd">- sage: a.matrix() * b
</span><span class="gi">+ sage: a.matrix() * b.matrix()
</span> [-272118 0]
[ 0 -462]
<span class="gd">- sage: a * b.matrix()
</span><span class="gi">+ sage: a.matrix() * b.matrix()
</span> [-272118 0]
[ 0 -462]
</pre></div></div></li></ol>
TicketjdemeyerSat, 17 Oct 2015 21:13:17 GMT
https://trac.sagemath.org/ticket/19016#comment:98
https://trac.sagemath.org/ticket/19016#comment:98
<ol start="6"><li>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 <code>Ideal_generic</code>?
</li></ol>
TicketnbruinSun, 18 Oct 2015 01:25:12 GMT
https://trac.sagemath.org/ticket/19016#comment:99
https://trac.sagemath.org/ticket/19016#comment:99
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:97" title="Comment 97">jdemeyer</a>:
</p>
<blockquote class="citation">
<ol><li>In <code>src/sage/rings/polynomial/laurent_polynomial.pyx</code>, the function <code>__hash__</code> is defined twice in the same class.
</li></ol></blockquote>
<p>
Can you give line numbers? I count only two definitions of <code>__hash__</code> in
<code>src/sage/rings/polynomial/laurent_polynomial.pyx</code>, and they are on distinct classes:
</p>
<pre class="wiki">sage.rings.polynomial.laurent_polynomial.LaurentPolynomial_mpair.__hash__
sage.rings.polynomial.laurent_polynomial.LaurentPolynomial_univariate.__hash__
</pre><p>
respectively.
</p>
<blockquote class="citation">
<ol start="2"><li>This isn't proper doctest syntax:
</li></ol></blockquote>
<p>
Thanks; should be fixed.
</p>
<blockquote class="citation">
<ol start="3"><li>Could you justify the need to add lots of comparison functions?
</li></ol></blockquote>
<p>
Yes, I wonder too. Not including those would save us adding a whole bunch of silly doctests too.
</p>
<blockquote class="citation">
<ol start="4"><li>Why is this needed?
<div class="wiki-code"><div class="code"><pre><span class="gd">- return self.element_class(self, m)
</span><span class="gi">+ return self.element_class(self, ZZ(m))
</span></pre></div></div></li></ol></blockquote>
<p>
If <code>self.m</code> should be an <code>Integer</code> this is a good way of enforcing it. I don't think we did this before? perhaps this is covered in <code>element_class</code> already. I'm not familiar with this code (and didn't add that patch)
</p>
<blockquote class="citation">
<ol start="5"><li>This looks very suspicious:
<div class="wiki-code"><div class="code"><pre> [ 0 1]
[-272118 0]
<span class="gd">- sage: a.matrix() * b
</span><span class="gi">+ sage: a.matrix() * b.matrix()
</span> [-272118 0]
[ 0 -462]
<span class="gd">- sage: a * b.matrix()
</span><span class="gi">+ sage: a.matrix() * b.matrix()
</span> [-272118 0]
[ 0 -462]
</pre></div></div></li></ol></blockquote>
<p>
See <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:86" title="Comment 86">comment:86</a> and <a class="new ticket" href="https://trac.sagemath.org/ticket/19388" title="enhancement: Write better doctest for parent.register_embedding (new)">#19388</a>.
</p>
<blockquote class="citation">
<ol start="6"><li>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 <code>Ideal_generic</code>?
</li></ol></blockquote>
<p>
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.
</p>
TicketgitSun, 18 Oct 2015 02:56:27 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:100
https://trac.sagemath.org/ticket/19016#comment:100
<ul>
<li><strong>commit</strong>
changed from <em>d34e7c3dfcda5b31ea4b5f1d112d843ae0d0e549</em> to <em>fcf799ce33270401e9dce7bfcf4f383dbcedc49d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=fcf799ce33270401e9dce7bfcf4f383dbcedc49d"><span class="icon"></span>fcf799c</a></td><td><code>tract 19016: some further doctest fixes</code>
</td></tr></table>
TicketjdemeyerSun, 18 Oct 2015 07:12:21 GMT
https://trac.sagemath.org/ticket/19016#comment:101
https://trac.sagemath.org/ticket/19016#comment:101
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:99" title="Comment 99">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:97" title="Comment 97">jdemeyer</a>:
</p>
<blockquote class="citation">
<ol><li>In <code>src/sage/rings/polynomial/laurent_polynomial.pyx</code>, the function <code>__hash__</code> is defined twice in the same class.
</li></ol></blockquote>
<p>
Can you give line numbers?
</p>
</blockquote>
<p>
<a class="ext-link" href="http://git.sagemath.org/sage.git/diff/src/sage/rings/polynomial/laurent_polynomial.pyx?id=0a2e3c93c5f5c2751aaf051c40ae6d8a199c3b3b&ss=1&context=20"><span class="icon"></span>duplicated __hash__ function</a>. I think the problem is that this <code>__hash__</code> is already included in Sage 6.10.beta0.
</p>
<p>
I suggest to merge the latest beta in this branch, that will hopefully fix this.
</p>
TicketjdemeyerSun, 18 Oct 2015 07:30:47 GMT
https://trac.sagemath.org/ticket/19016#comment:102
https://trac.sagemath.org/ticket/19016#comment:102
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:99" title="Comment 99">nbruin</a>:
</p>
<blockquote class="citation">
<p>
The problem is more visible if there is no hash available for ideals by default.
</p>
</blockquote>
<p>
This seems like an argument for <em>not</em> adding the 0 hash to <code>Ideal_generic</code> then.
</p>
<p>
By the way, a small improvement might be to take the hash of the parent instead of a constant zero.
</p>
TicketnbruinSun, 18 Oct 2015 18:32:37 GMT
https://trac.sagemath.org/ticket/19016#comment:103
https://trac.sagemath.org/ticket/19016#comment:103
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:102" title="Comment 102">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
This seems like an argument for <em>not</em> adding the 0 hash to <code>Ideal_generic</code> then.
</p>
</blockquote>
<p>
I agree with that. Furthermore, I think we can remove the 0 hash on <code>Ideal_generic</code> without affecting doctests, so I'd say we should. Let's see what Vincent's opinion is.
</p>
<blockquote class="citation">
<p>
By the way, a small improvement might be to take the hash of the parent instead of a constant zero.
</p>
</blockquote>
<p>
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.
</p>
TicketvdelecroixMon, 19 Oct 2015 02:38:32 GMT
https://trac.sagemath.org/ticket/19016#comment:104
https://trac.sagemath.org/ticket/19016#comment:104
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:103" title="Comment 103">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:102" title="Comment 102">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
This seems like an argument for <em>not</em> adding the 0 hash to <code>Ideal_generic</code> then.
</p>
</blockquote>
<p>
I agree with that. Furthermore, I think we can remove the 0 hash on <code>Ideal_generic</code> without affecting doctests, so I'd say we should. Let's see what Vincent's opinion is.
</p>
</blockquote>
<p>
If it works without hash, let us go without of course!
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
By the way, a small improvement might be to take the hash of the parent instead of a constant zero.
</p>
</blockquote>
<p>
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.
</p>
</blockquote>
<p>
I actually used some, for example in <code>crystals/elementary_crystals.py</code>. But I tend to agree with Nils that in most cases, this will be useless (or badly used).
</p>
TicketvdelecroixMon, 19 Oct 2015 02:46:29 GMT
https://trac.sagemath.org/ticket/19016#comment:105
https://trac.sagemath.org/ticket/19016#comment:105
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:99" title="Comment 99">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:97" title="Comment 97">jdemeyer</a>:
</p>
<blockquote class="citation">
<ol start="3"><li>Could you justify the need to add lots of comparison functions?
</li></ol></blockquote>
<p>
Yes, I wonder too. Not including those would save us adding a whole bunch of silly doctests too.
</p>
</blockquote>
<p>
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.
</p>
<p>
The best would be to implement an <code>ElementWrapper_with_cmp</code>.
</p>
<blockquote class="citation">
<blockquote class="citation">
<ol start="4"><li>Why is this needed?
<div class="wiki-code"><div class="code"><pre><span class="gd">- return self.element_class(self, m)
</span><span class="gi">+ return self.element_class(self, ZZ(m))
</span></pre></div></div></li></ol></blockquote>
<p>
If <code>self.m</code> should be an <code>Integer</code> this is a good way of enforcing it. I don't think we did this before? perhaps this is covered in <code>element_class</code> already. I'm not familiar with this code (and didn't add that patch)
</p>
</blockquote>
<p>
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.
</p>
<p>
Vincent
</p>
TicketnbruinMon, 19 Oct 2015 18:32:37 GMT
https://trac.sagemath.org/ticket/19016#comment:106
https://trac.sagemath.org/ticket/19016#comment:106
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:104" title="Comment 104">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:103" title="Comment 103">nbruin</a>:
</p>
<blockquote class="citation">
<p>
I think we can remove the 0 hash on <code>Ideal_generic</code> without affecting doctests, so I'd say we should. Let's see what Vincent's opinion is.
</p>
</blockquote>
<p>
If it works without hash, let us go without of course!
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
I actually used some, for example in <code>crystals/elementary_crystals.py</code>. But I tend to agree with Nils that in most cases, this will be useless (or badly used).
</p>
</blockquote>
<p>
I don't think you did. The <code>hash(self.parent())</code> is on <code>AbstractSingleCrystalElement</code> which has it <code>eq</code> defined as <code>self.parent() is other.parent()</code>, so making the hash equal to that of the parent is entirely justified there.
</p>
<p>
I think the <code>self.element_class(self, ZZ(m))</code> looks justifiable, so I'd be OK with leaving that in.
</p>
TicketgitTue, 20 Oct 2015 00:02:01 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:107
https://trac.sagemath.org/ticket/19016#comment:107
<ul>
<li><strong>commit</strong>
changed from <em>fcf799ce33270401e9dce7bfcf4f383dbcedc49d</em> to <em>aeb120cf3cbdad3e74607619a9ef49542aee0161</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=bfbd7c8c61747920bd525648a6d38d41a787cfe4"><span class="icon"></span>bfbd7c8</a></td><td><code>Trac 19016: merge sage-6.10.beta0</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=aeb120cf3cbdad3e74607619a9ef49542aee0161"><span class="icon"></span>aeb120c</a></td><td><code>Trac 19016: review #1</code>
</td></tr></table>
TicketgitTue, 20 Oct 2015 15:53:25 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:108
https://trac.sagemath.org/ticket/19016#comment:108
<ul>
<li><strong>commit</strong>
changed from <em>aeb120cf3cbdad3e74607619a9ef49542aee0161</em> to <em>c1cf361e83c117521c832a10f1d6248f264972d8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c1cf361e83c117521c832a10f1d6248f264972d8"><span class="icon"></span>c1cf361</a></td><td><code>trac 19016: fix laurent_polynomial hash doctest</code>
</td></tr></table>
TicketnbruinTue, 20 Oct 2015 15:54:14 GMTstatus changed
https://trac.sagemath.org/ticket/19016#comment:109
https://trac.sagemath.org/ticket/19016#comment:109
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketnbruinTue, 27 Oct 2015 15:46:05 GMT
https://trac.sagemath.org/ticket/19016#comment:110
https://trac.sagemath.org/ticket/19016#comment:110
<p>
*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?
</p>
TicketvbraunTue, 27 Oct 2015 16:30:16 GMTreviewer set
https://trac.sagemath.org/ticket/19016#comment:111
https://trac.sagemath.org/ticket/19016#comment:111
<ul>
<li><strong>reviewer</strong>
set to <em>Volker Braun</em>
</li>
</ul>
TicketvbraunTue, 27 Oct 2015 20:08:59 GMT
https://trac.sagemath.org/ticket/19016#comment:112
https://trac.sagemath.org/ticket/19016#comment:112
<p>
Doctest failures:
</p>
<p>
<a class="ext-link" href="http://build.sagedev.org/release/builders/%20%20slow%20AIMS%20%20%28Debian%207%2064%20bit%29%20incremental/builds/155/steps/shell_4/logs/stdio"><span class="icon"></span>http://build.sagedev.org/release/builders/%20%20slow%20AIMS%20%20%28Debian%207%2064%20bit%29%20incremental/builds/155/steps/shell_4/logs/stdio</a>
</p>
TicketvdelecroixTue, 27 Oct 2015 20:39:01 GMTstatus changed
https://trac.sagemath.org/ticket/19016#comment:113
https://trac.sagemath.org/ticket/19016#comment:113
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Hi Volker,
</p>
<p>
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.
</p>
<p>
Vincent
</p>
TicketvbraunTue, 27 Oct 2015 22:52:26 GMT
https://trac.sagemath.org/ticket/19016#comment:114
https://trac.sagemath.org/ticket/19016#comment:114
<p>
How about you try to reproduce it with said ticket, if you can get a new branch by tomorrow I can merge it.
</p>
<p>
Can you also fix the random failure at <a class="closed ticket" href="https://trac.sagemath.org/ticket/19488" title="defect: Random failure in AffineCrystalFromClassicalElement.__cmp__ (closed: fixed)">#19488</a>
</p>
TicketgitTue, 27 Oct 2015 23:33:19 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:115
https://trac.sagemath.org/ticket/19016#comment:115
<ul>
<li><strong>commit</strong>
changed from <em>c1cf361e83c117521c832a10f1d6248f264972d8</em> to <em>81012bc59c29eea8162bcec1ecc21cafa9d1d826</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2f434d7237bff661589d4fe75bf323cb9020a766"><span class="icon"></span>2f434d7</a></td><td><code>write doc and many doctests for substitute</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=875542da5e016b418c99b275f1e1057489ecd565"><span class="icon"></span>875542d</a></td><td><code>write AsymptoticExpansion.symbolic_expression</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5ac0feaa2faebd303bd3d4ed53ce40b60c22311c"><span class="icon"></span>5ac0fea</a></td><td><code>extend SR._element_constructor_ to accept asymptotic expansions</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=fa814b0680e8f7edc2ed3e181f5b9750678db04f"><span class="icon"></span>fa814b0</a></td><td><code>Trac #19431: merge 6.10.beta0</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6a6efc41e89adc6d16a8e9c4f348b4ab2e076099"><span class="icon"></span>6a6efc4</a></td><td><code>introduce parameter R in .symbolic_expression</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f39b94226944f107bb11b91483949406be75ecd5"><span class="icon"></span>f39b942</a></td><td><code>simplify SR._element_constructor</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5c3cba330f79abf2864651d38e4545e1246ac9ad"><span class="icon"></span>5c3cba3</a></td><td><code>fix checks whether parent is SR to check if instance of SymbolicRing</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ee5293298a509cb15da000f87ba25adb75f4f63d"><span class="icon"></span>ee52932</a></td><td><code>fixup and doctest of parameter R in .symbolic_expression</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=04c79ade018d97d7d031f3b18243807e528ff7dc"><span class="icon"></span>04c79ad</a></td><td><code>Trac 19016: merge #19436</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=81012bc59c29eea8162bcec1ecc21cafa9d1d826"><span class="icon"></span>81012bc</a></td><td><code>Trac 19016: add hash value for asymptotic ring elt</code>
</td></tr></table>
TicketnbruinTue, 27 Oct 2015 23:48:50 GMT
https://trac.sagemath.org/ticket/19016#comment:116
https://trac.sagemath.org/ticket/19016#comment:116
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:114" title="Comment 114">vbraun</a>:
</p>
<blockquote class="citation">
<p>
How about you try to reproduce it with said ticket, if you can get a new branch by tomorrow I can merge it.
</p>
<p>
Can you also fix the random failure at <a class="closed ticket" href="https://trac.sagemath.org/ticket/19488" title="defect: Random failure in AffineCrystalFromClassicalElement.__cmp__ (closed: fixed)">#19488</a>
</p>
</blockquote>
<p>
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 <code>cmp(b,1)</code> <em>should</em> yield an error).
</p>
TicketvdelecroixTue, 27 Oct 2015 23:56:50 GMT
https://trac.sagemath.org/ticket/19016#comment:117
https://trac.sagemath.org/ticket/19016#comment:117
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:116" title="Comment 116">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19016#comment:114" title="Comment 114">vbraun</a>:
</p>
<blockquote class="citation">
<p>
How about you try to reproduce it with said ticket, if you can get a new branch by tomorrow I can merge it.
</p>
<p>
Can you also fix the random failure at <a class="closed ticket" href="https://trac.sagemath.org/ticket/19488" title="defect: Random failure in AffineCrystalFromClassicalElement.__cmp__ (closed: fixed)">#19488</a>
</p>
</blockquote>
<p>
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 <code>cmp(b,1)</code> <em>should</em> yield an error).
</p>
</blockquote>
<p>
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 <code>Element</code> (in <code>sage.structure.element</code>) that is similar to Python one and compare by <code>id</code>. It is also random though.
</p>
TicketgitTue, 27 Oct 2015 23:59:35 GMTcommit changed
https://trac.sagemath.org/ticket/19016#comment:118
https://trac.sagemath.org/ticket/19016#comment:118
<ul>
<li><strong>commit</strong>
changed from <em>81012bc59c29eea8162bcec1ecc21cafa9d1d826</em> to <em>c7b4f0e0210e6cbad4bcfd62ce3093239f071ff3</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c7b4f0e0210e6cbad4bcfd62ce3093239f071ff3"><span class="icon"></span>c7b4f0e</a></td><td><code>Trac 19016: more robust doctest (see #19488)</code>
</td></tr></table>
TicketvdelecroixWed, 28 Oct 2015 00:00:37 GMTstatus changed
https://trac.sagemath.org/ticket/19016#comment:119
https://trac.sagemath.org/ticket/19016#comment:119
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Actually, for the sake of this ticket I think that we should not change anything to the previous behavior of <code>cmp</code>... simple fix in my last commit.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c7b4f0e0210e6cbad4bcfd62ce3093239f071ff3"><span class="icon"></span>c7b4f0e</a></td><td><code>Trac 19016: more robust doctest (see #19488)</code>
</td></tr></table>
TicketvbraunWed, 28 Oct 2015 08:48:50 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/19016#comment:120
https://trac.sagemath.org/ticket/19016#comment:120
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/19016-bis</em> to <em>c7b4f0e0210e6cbad4bcfd62ce3093239f071ff3</em>
</li>
</ul>
TicketncohenWed, 28 Oct 2015 08:50:54 GMTcommit deleted
https://trac.sagemath.org/ticket/19016#comment:121
https://trac.sagemath.org/ticket/19016#comment:121
<ul>
<li><strong>commit</strong>
<em>c7b4f0e0210e6cbad4bcfd62ce3093239f071ff3</em> deleted
</li>
</ul>
<p>
(applause for what was done here)
</p>
TicketvdelecroixWed, 28 Oct 2015 20:38:30 GMT
https://trac.sagemath.org/ticket/19016#comment:122
https://trac.sagemath.org/ticket/19016#comment:122
<p>
Thanks Volker!
</p>
Ticket