Sage: Ticket #12969: Coercion failures in symmetric functions
https://trac.sagemath.org/ticket/12969
<p>
The following code triggers a coercion failure in the symmetric function code
</p>
<pre class="wiki"> sage: H = MacdonaldPolynomialsH(QQ)
sage: P = MacdonaldPolynomialsP(QQ)
sage: m = SFAMonomial(P.base_ring())
sage: Ht = MacdonaldPolynomialsHt(QQ)
sage: m(P.one())
m[]
sage: Ht(P.one())
</pre><p>
The coercion path does exist, however!
</p>
<p>
This can also be checked with the new syntax using the patches in <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> as follows:
</p>
<pre class="wiki"> sage: R = QQ['q,t'].fraction_field()
sage: Sym = sage.combinat.sf.sf.SymmetricFunctions(R)
sage: H = Sym.macdonald().H();
sage: P = Sym.macdonald().P();
sage: m = Sym.monomial();
sage: Ht = Sym.macdonald().Ht();
sage: m(P.one())
sage: Ht(P.one())
</pre><p>
The bug is in the coercion system. Sage does
not find a path from P to Ht, whereas there definitely is one:
</p>
<pre class="wiki"> def coercion_graph(self, G = None):
if G is None:
G = DiGraph()
if self not in G.vertices():
G.add_vertex(self)
for h in self._introspect_coerce()['_coerce_from_list']:
coercion_graph(h.domain(), G)
G.add_edge(h.domain(), self)
return G
R = QQ['q,t'].fraction_field()
R.rename("R")
Sym = sage.combinat.sf.sf.SymmetricFunctions(R); Sym.rename("Sym")
p = Sym.p(); p.rename("p")
s = Sym.schur(); s.rename("s")
e = Sym.elementary(); e.rename("e")
m = Sym.monomial(); m.rename("m")
h = Sym.complete(); h.rename("h")
H = Sym.macdonald().H(); H.rename("H")
P = Sym.macdonald().P(); P.rename("P")
J = Sym.macdonald().J(); J.rename("J")
S = Sym.macdonald().S(); S.rename("S")
Ht = Sym.macdonald().Ht(); Ht.rename("Ht")
m.coerce_map_from(P);
print Ht.coerce_map_from(P)
G = coercion_graph(Ht)
G.show()
</pre><p>
<span class="underline">Apply</span>
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/12969/trac12969_fix_coercion_cache.patch" title="Attachment 'trac12969_fix_coercion_cache.patch' in Ticket #12969">trac12969_fix_coercion_cache.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/12969/trac12969_fix_coercion_cache.patch" title="Download"></a> and <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/12969/trac_12969-avoid_coercion_from_none.patch" title="Attachment 'trac_12969-avoid_coercion_from_none.patch' in Ticket #12969">trac_12969-avoid_coercion_from_none.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/12969/trac_12969-avoid_coercion_from_none.patch" title="Download"></a>, if <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> is not applied
</li><li>All three patches, if <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> is applied
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/12969
Trac 1.1.6saliolaFri, 13 Jul 2012 02:38:56 GMTcc changed
https://trac.sagemath.org/ticket/12969#comment:1
https://trac.sagemath.org/ticket/12969#comment:1
<ul>
<li><strong>cc</strong>
<em>saliola</em> added
</li>
</ul>
TicketSimonKingFri, 20 Jul 2012 06:17:24 GMT
https://trac.sagemath.org/ticket/12969#comment:2
https://trac.sagemath.org/ticket/12969#comment:2
<p>
Just for the record: My impression was that solving this ticket could also help with a couple of coercion-related memory leaks considered in <a class="closed ticket" href="https://trac.sagemath.org/ticket/715" title="defect: Parents probably not reclaimed due to too much caching (closed: fixed)">#715</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/12215" title="defect: Memleak in UniqueRepresentation, @cached_method (closed: fixed)">#12215</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/12313" title="defect: Fix yet another memory leak caused by caching of coercion data (closed: fixed)">#12313</a> and so on.
</p>
TicketSimonKingFri, 20 Jul 2012 20:15:48 GMT
https://trac.sagemath.org/ticket/12969#comment:3
https://trac.sagemath.org/ticket/12969#comment:3
<p>
I can confirm that the problem occurs with vanilla sage-5.2.rc0, namely resulting in this error:
</p>
<pre class="wiki">TypeError: do not know how to make x (= McdP[]) an element of self (=Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field)
</pre>
TicketSimonKingSat, 21 Jul 2012 08:17:44 GMT
https://trac.sagemath.org/ticket/12969#comment:4
https://trac.sagemath.org/ticket/12969#comment:4
<p>
Observation: When starting with your example, one gets
</p>
<pre class="wiki">sage: from sage.structure.element import get_coercion_model
sage: cm = get_coercion_model()
sage: Ht.has_coerce_map_from(P)
False
sage: cm.discover_coercion(P,Ht)
(None, Composite map:
From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
Defn: Composite map:
From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
Defn: Generic morphism:
From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
then
Generic morphism:
From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
then
Generic morphism:
From: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field)
sage: Ht.has_coerce_map_from(P)
False
sage: cm.discover_coercion(Ht,P)
(Composite map:
From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
Defn: Composite map:
From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
Defn: Generic morphism:
From: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
then
Generic morphism:
From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
then
Generic morphism:
From: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, None)
sage: Ht.has_coerce_map_from(P)
False
</pre><p>
Thus, apparently the problem is that "coerce_map_from" does not call discover_coercion when it should. Broken cache, apparently. Non-unique parents?
</p>
TicketSimonKingSat, 21 Jul 2012 08:22:13 GMT
https://trac.sagemath.org/ticket/12969#comment:5
https://trac.sagemath.org/ticket/12969#comment:5
<p>
In sage.structure.parent.Parent.coerce_map_from, I see the lines
</p>
<div class="wiki-code"><div class="code"><pre> mor <span class="o">=</span> <span class="bp">self</span><span class="o">.</span>discover_coerce_map_from<span class="p">(</span>S<span class="p">)</span>
<span class="c">#if mor is not None:</span>
<span class="c"># # Need to check that this morphism doesn't connect previously unconnected parts of the coercion diagram</span>
<span class="c"># if self._embedding is not None and not self._embedding.codomain().has_coerce_map_from(S):</span>
<span class="c"># # The following if statement may call this function with self and S. If so, we want to return None,</span>
<span class="c"># # so that it doesn't use this path for the existence of a coercion path.</span>
<span class="c"># # We disable this for now because it is too strict</span>
<span class="c"># pass</span>
<span class="c"># # print "embed problem: the following morphisms connect unconnected portions of the coercion graph\n%s\n%s"%(self._embedding, mor)</span>
<span class="c"># # mor = None</span>
<span class="k">if</span> mor <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
<span class="c"># NOTE: this line is what makes the coercion detection stateful</span>
<span class="c"># self._coerce_from_list.append(mor)</span>
<span class="k">pass</span>
<span class="bp">self</span><span class="o">.</span>_coerce_from_hash<span class="p">[</span>S<span class="p">]</span> <span class="o">=</span> mor
</pre></div></div><p>
Looks suspicious to me. A lot of commented-out code, and an empty special case when the coercion is not None.
</p>
TicketSimonKingSat, 21 Jul 2012 10:43:51 GMT
https://trac.sagemath.org/ticket/12969#comment:6
https://trac.sagemath.org/ticket/12969#comment:6
<pre class="wiki">sage: Ht._coerce_map_from_??
Type: builtin_function_or_method
Base Class: <type 'builtin_function_or_method'>
String Form: <built-in method _coerce_map_from_ of MacdonaldPolynomials_ht_with_category object at 0x4686c50>
Namespace: Interactive
Definition: Ht._coerce_map_from_(self, S)
Source:
cpdef _coerce_map_from_(self, S):
"""
Override this method to specify coercions beyond those specified
in coerce_list.
If no such coercion exists, return None or False. Otherwise, it may
return either an actual Map to use for the coercion, a callable
(in which case it will be wrapped in a Map), or True (in which case
a generic map will be provided).
"""
return None
</pre><p>
Question: Why is that method not overridden for the different realisations of <code>MacdonaldPolynomials</code>?
</p>
TicketSimonKingSat, 21 Jul 2012 11:13:07 GMT
https://trac.sagemath.org/ticket/12969#comment:7
https://trac.sagemath.org/ticket/12969#comment:7
<p>
If I understand correctly, the coercion maps are supposed to go via Schur basis. But while one has
</p>
<pre class="wiki">sage: H = MacdonaldPolynomialsH(QQ)
sage: P = MacdonaldPolynomialsP(QQ)
sage: m = SFAMonomial(P.base_ring())
sage: Ht = MacdonaldPolynomialsHt(QQ)
sage: Ht._s
Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
sage: Ht._s.has_coerce_map_from(P)
True
</pre><p>
one has (or does in fact <em>not</em> have)
</p>
<pre class="wiki">sage: P._s
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
/home/simon/SAGE/prerelease/sage-5.2.rc0/<ipython console> in <module>()
/home/simon/SAGE/prerelease/sage-5.2.rc0/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__getattr__ (sage/structure/parent.c:5967)()
/home/simon/SAGE/prerelease/sage-5.2.rc0/local/lib/python2.7/site-packages/sage/structure/misc.so in sage.structure.misc.getattr_from_other_class (sage/structure/misc.c:1427)()
AttributeError: 'MacdonaldPolynomials_p_with_category' object has no attribute '_s'
sage: P._self_to_s(P.one())
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
/home/simon/SAGE/prerelease/sage-5.2.rc0/<ipython console> in <module>()
/home/simon/SAGE/prerelease/sage-5.2.rc0/local/lib/python2.7/site-packages/sage/combinat/sf/macdonald.pyc in _self_to_s(self, x)
421 (3*q-6)*s[1, 1, 1] + (-4*q+1)*s[2, 1]
422 """
--> 423 return self._s._from_cache(x, self._s_cache, self._self_to_s_cache, q = self.q, t = self.t) # do we want this t = self.t?
424
425 def c1(self, part):
/home/simon/SAGE/prerelease/sage-5.2.rc0/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__getattr__ (sage/structure/parent.c:5967)()
/home/simon/SAGE/prerelease/sage-5.2.rc0/local/lib/python2.7/site-packages/sage/structure/misc.so in sage.structure.misc.getattr_from_other_class (sage/structure/misc.c:1427)()
AttributeError: 'MacdonaldPolynomials_p_with_category' object has no attribute '_s'
</pre>
TicketSimonKingSat, 21 Jul 2012 11:18:16 GMT
https://trac.sagemath.org/ticket/12969#comment:8
https://trac.sagemath.org/ticket/12969#comment:8
<p>
Looking at sage/combinat/sf/macdonald.py, there is a cache from different realisations (bases) to Schur basis. There are two exceptions: The P-basis and the Q-basis. Why? Perhaps that is the culprit?
</p>
TicketSimonKingSat, 21 Jul 2012 12:13:59 GMT
https://trac.sagemath.org/ticket/12969#comment:9
https://trac.sagemath.org/ticket/12969#comment:9
<p>
Adding
</p>
<pre class="wiki"> def _coerce_map_from_(self,S):
if not hasattr(self,'_s'):
return None
try:
S_to_s = self._s.coerce_map_from(S)
except:
return None
if S_to_s is None:
return None
return self.coerce_map_from(self._s)*S_to_s
</pre><p>
to <code>MacdonaldPolynomials_generic</code> solves the problem. But I first have to check whether the original coercion from P to Ht (which exists if one does <em>not</em> do <code>m(P.one())</code>) is the same.
</p>
TicketSimonKingSat, 21 Jul 2012 12:27:42 GMT
https://trac.sagemath.org/ticket/12969#comment:10
https://trac.sagemath.org/ticket/12969#comment:10
<p>
Helas. It is <em>not</em> the same. Doing the above, one gets an awfully complicated composition of maps, probably rather inefficient.
</p>
<pre class="wiki">sage: H = MacdonaldPolynomialsH(QQ)
sage: P = MacdonaldPolynomialsP(QQ)
sage: m = SFAMonomial(P.base_ring())
sage: Ht = MacdonaldPolynomialsHt(QQ)
sage: Ht.coerce_map_from(P)
Composite map:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
Defn: Composite map:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
Defn: Composite map:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the H basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
Defn: Composite map:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
Defn: Composite map:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the J basis with q=q and t=t over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
Defn: Composite map:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
Defn: Composite map:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the S basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
Defn: Composite map:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
Defn: Generic morphism:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
then
Generic morphism:
From: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
then
Generic morphism:
From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
To: Macdonald polynomials in the S basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
then
Generic morphism:
From: Macdonald polynomials in the S basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
then
Generic morphism:
From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
To: Macdonald polynomials in the J basis with q=q and t=t over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
then
Generic morphism:
From: Macdonald polynomials in the J basis with q=q and t=t over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
then
Generic morphism:
From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
To: Macdonald polynomials in the H basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
then
Generic morphism:
From: Macdonald polynomials in the H basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
then
Generic morphism:
From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
To: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
</pre>
TicketSimonKingSat, 21 Jul 2012 14:20:43 GMT
https://trac.sagemath.org/ticket/12969#comment:11
https://trac.sagemath.org/ticket/12969#comment:11
<p>
I added
</p>
<div class="wiki-code"><div class="code"><pre> <span class="k">def</span> <span class="nf">test_coercions</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span>_coerce_from_hash
</pre></div></div><p>
to self.structure.parent.Parent, and obtain
</p>
<pre class="wiki">sage: H = MacdonaldPolynomialsH(QQ)
sage: P = MacdonaldPolynomialsP(QQ)
sage: m = SFAMonomial(P.base_ring())
sage: Ht = MacdonaldPolynomialsHt(QQ)
sage: P in Ht.test_coercions()
False
sage: P.one()
McdP[]
sage: P in Ht.test_coercions()
False
sage: phi = m.coerce_map_from(P)
sage: P in Ht.test_coercions()
True
sage: Ht.test_coercions()[P] is None
True
</pre><p>
In other words, trying to find the coercion from P to m changes the coercion cache of Ht. Funny.
</p>
TicketaschillingSat, 21 Jul 2012 15:48:39 GMTdescription changed
https://trac.sagemath.org/ticket/12969#comment:12
https://trac.sagemath.org/ticket/12969#comment:12
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12969?action=diff&version=12">diff</a>)
</li>
</ul>
TicketaschillingSat, 21 Jul 2012 15:50:19 GMTcc changed
https://trac.sagemath.org/ticket/12969#comment:13
https://trac.sagemath.org/ticket/12969#comment:13
<ul>
<li><strong>cc</strong>
<em>zabrocki</em> added
</li>
</ul>
TicketaschillingSat, 21 Jul 2012 15:53:42 GMT
https://trac.sagemath.org/ticket/12969#comment:14
https://trac.sagemath.org/ticket/12969#comment:14
<p>
Hi Simon!
</p>
<p>
Thank you for investigating this. I should mention that Mike Zabrocki and I just finished a patch in <a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/5457"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/5457</a> which changes the syntax for symmetric functions. As far as I know the coercion also breaks in that set-up.
</p>
<p>
At the Sage Days in Minneapolis last week, Franco Saliola also told me that he was hit by the coercion bug in their code on quasisymmetric functions <a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/8899"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/8899</a>. Franco, could you post your precise failure?
</p>
<p>
Anne
</p>
TicketsaliolaSun, 22 Jul 2012 01:28:16 GMT
https://trac.sagemath.org/ticket/12969#comment:15
https://trac.sagemath.org/ticket/12969#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12969#comment:14" title="Comment 14">aschilling</a>:
</p>
<blockquote class="citation">
<p>
At the Sage Days in Minneapolis last week, Franco Saliola also told me that he was hit by the coercion bug in their code on quasisymmetric functions <a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/8899"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/8899</a>. Franco, could you post your precise failure?
</p>
</blockquote>
<p>
If I recall correctly, we didn't hit upon the problem with the current code, but with new bases that we implemented on top of it. These new bases are not going in to Sage as part of <a class="closed ticket" href="https://trac.sagemath.org/ticket/8899" title="enhancement: Implement non commutative symmetric functions (closed: fixed)">#8899</a> (we are only implementing the "classical" bases in this first stage).
</p>
<p>
Franco
</p>
TicketnthierySun, 22 Jul 2012 08:01:46 GMT
https://trac.sagemath.org/ticket/12969#comment:16
https://trac.sagemath.org/ticket/12969#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12969#comment:10" title="Comment 10">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Helas. It is <em>not</em> the same. Doing the above, one gets an awfully complicated composition of maps, probably rather inefficient.
</p>
</blockquote>
<p>
Yes that's the well know issue (<a class="needs_work ticket" href="https://trac.sagemath.org/ticket/8878" title="defect: Use Dijkstra to discover shortest coercion path (needs_work)">#8878</a>) of the current coercion model implementation: it does a depth first search rather than a breath first.
</p>
TicketnthierySun, 22 Jul 2012 08:04:49 GMT
https://trac.sagemath.org/ticket/12969#comment:17
https://trac.sagemath.org/ticket/12969#comment:17
<blockquote class="citation">
<p>
Question: Why is that method not overridden for the different realisations of <code>MacdonaldPolynomials</code>?
</p>
</blockquote>
<p>
Because the coercions are registered explicitly during the initialization of Sym / macdonald polynomials. This is better because it leaves maximal freedom to the coercion model (e.g. the coercion model can't do transitivity with _coerce_map_from).
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketSimonKingSun, 22 Jul 2012 08:23:18 GMT
https://trac.sagemath.org/ticket/12969#comment:18
https://trac.sagemath.org/ticket/12969#comment:18
<p>
I think I can explain (and thus, solve) the problem!
</p>
<p>
The bug is in the backtracking algorithm for finding a coercion path.
</p>
<p>
Every parent A has a list of other parents B1, B2, ... such that a coercion from B1, B2 to A is registered. When searching for a coercion from parent X to A, and a direct coercion is not registered, then a coercion from X to B1, B2, ... is (in that order!) is searched. But of course one must avoid infinite recursions, and thus any coercion path from X to B1, B2, via X is disregarded. Disregarding one node in the backtracking algorithm is the purpose of _register_pair in sage.structure.parent.
</p>
<p>
Now consider the following situation, where arrows denote registered coercions (partially the coercions are registered in <em>both</em> directions - that's what happening in the symmetric functions code):
</p>
<pre class="wiki"> X -> B2 <-> A <-> B1
</pre><p>
We first ask for a coercion from X to A.
</p>
<p>
There is no coercion from X to A found in the cache. Thus, we disregard (X,A) in our backtracking algorithm, and search for a coercion from X to B1. The only coercion path from X to B1 would be via A, but that is disregarded in the backtracking algorithm. The absence of a coercion from X to B1 is cached. In the next step, a coercion from X to A via B2 is found, cached and returned.
</p>
<p>
But when later asking for a coercion from X to B1, the cache states that there is no coercion!
</p>
<p>
Here's the bug: The absence of a coercion from X to B1 must <em>only</em> be cached if X is not the starting point of any disregarded search path (such as (X,A) in the example above), with the only exception of (X,B1).
</p>
TicketSimonKingSun, 22 Jul 2012 08:25:48 GMT
https://trac.sagemath.org/ticket/12969#comment:19
https://trac.sagemath.org/ticket/12969#comment:19
<p>
And while we are at it: _register_pair uses a dictionary in order to implement a set. I think it would be more efficient to use a set right away.
</p>
TicketSimonKingSun, 22 Jul 2012 08:31:38 GMT
https://trac.sagemath.org/ticket/12969#comment:20
https://trac.sagemath.org/ticket/12969#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12969#comment:19" title="Comment 19">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
And while we are at it: _register_pair uses a dictionary in order to implement a set. I think it would be more efficient to use a set right away.
</p>
</blockquote>
<p>
No, to my surprise, it isn't:
</p>
<pre class="wiki">sage: cython("""
....: def testD(dict D):
....: cdef int i
....: for i from 0<=i<10000:
....: b = (i in D)
....: def testS(set S):
....: cdef int i
....: for i from 0<=i<10000:
....: b = (i in S)
....: """)
sage: D = dict([(i,1) for i in range(5000)])
sage: S = set(range(5000))
sage: %timeit testD(D)
625 loops, best of 3: 495 µs per loop
sage: %timeit testS(S)
625 loops, best of 3: 520 µs per loop
sage: %timeit testD(D)
625 loops, best of 3: 496 µs per loop
sage: %timeit testS(S)
625 loops, best of 3: 520 µs per loop
</pre><p>
Sets seem slower than dictionaries by 5%.
</p>
TicketSimonKingSun, 22 Jul 2012 08:39:33 GMT
https://trac.sagemath.org/ticket/12969#comment:21
https://trac.sagemath.org/ticket/12969#comment:21
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12969#comment:16" title="Comment 16">nthiery</a>:
</p>
<blockquote class="citation">
<p>
Yes that's the well know issue (<a class="needs_work ticket" href="https://trac.sagemath.org/ticket/8878" title="defect: Use Dijkstra to discover shortest coercion path (needs_work)">#8878</a>) of the current coercion model implementation: it does a depth first search rather than a breath first.
</p>
</blockquote>
<p>
OK. I think <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/8878" title="defect: Use Dijkstra to discover shortest coercion path (needs_work)">#8878</a> would involve a considerable amount of work. So, for simplicity, I suggest to fix the cache bug in the current implementation of depth first search <em>here</em>. And if in future someone will tackle <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/8878" title="defect: Use Dijkstra to discover shortest coercion path (needs_work)">#8878</a>, he/she should do so on top of that fix.
</p>
TicketnthierySun, 22 Jul 2012 09:00:29 GMT
https://trac.sagemath.org/ticket/12969#comment:22
https://trac.sagemath.org/ticket/12969#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12969#comment:21" title="Comment 21">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
OK. I think <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/8878" title="defect: Use Dijkstra to discover shortest coercion path (needs_work)">#8878</a> would involve a considerable amount of work. So, for simplicity, I suggest to fix the cache bug in the current implementation of depth first search <em>here</em>. And if in future someone will tackle <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/8878" title="defect: Use Dijkstra to discover shortest coercion path (needs_work)">#8878</a>, he/she should do so on top of that fix.
</p>
</blockquote>
<p>
I actually have an implementation for <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/8878" title="defect: Use Dijkstra to discover shortest coercion path (needs_work)">#8878</a> in the queue I had written two years ago; however it's disabled because there remained quite some work cleaning up Sage here and there for things to work smoothly.
</p>
<p>
So, yes, if you have a quick fix to the depth first search, please go ahead; my patch certainly needs a lot of rebasing anyway.
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketSimonKingSun, 22 Jul 2012 09:06:41 GMT
https://trac.sagemath.org/ticket/12969#comment:23
https://trac.sagemath.org/ticket/12969#comment:23
<p>
Question: Is <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> very close to being positively reviewed? Namely, we must decide whether we use the old syntax for the to-be-written doctest (in that case, this ticket would be a dependency for <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a>), or use the new syntax (in that case, due to deprecation warnings, <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> would become a dependency for this ticket).
</p>
<p>
For now, I will use the old syntax.
</p>
TicketSimonKingSun, 22 Jul 2012 09:24:33 GMTstatus changed; author set
https://trac.sagemath.org/ticket/12969#comment:24
https://trac.sagemath.org/ticket/12969#comment:24
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Simon King</em>
</li>
</ul>
<p>
The attached patch seems to fix the problem.
</p>
<p>
Questions:
</p>
<p>
<span class="underline">Is there a speed regression? </span>
</p>
<p>
With my patch, the absence of a coercion from X to Y is <em>only</em> cached, if no coercion path from X to Z (with Z different from Y) is temporarily disabled. But if there <em>really</em> is no coercion from X to Y, then the fix might involve a speed regression. Potential solution: If the old buggy depth first algorithm would cache the absence of a coercion from X to Y, while the new fixed version wouldn't, then we might investigate the paths from X to Y again, right after re-enabling the other paths starting from X.
</p>
<p>
<span class="underline">What about <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a></span>
</p>
<p>
I did not run the tests, yet. But the new test in my patch would fail because of the deprecation warnings introduced by <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a>. So, we must decide whether making <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> depend on this ticket or the other way around?
</p>
<p>
For the record: Without <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a>, I now get
</p>
<pre class="wiki">sage: H = MacdonaldPolynomialsH(QQ)
sage: P = MacdonaldPolynomialsP(QQ)
sage: m = SFAMonomial(P.base_ring())
sage: Ht = MacdonaldPolynomialsHt(QQ)
sage: m(P.one())
m[]
sage: Ht(P.one())
McdHt[]
</pre><p>
and
</p>
<pre class="wiki">sage: Ht.coerce_map_from(P)
Composite map:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
Defn: Composite map:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
Defn: Generic morphism:
From: Macdonald polynomials in the P basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
then
Generic morphism:
From: Macdonald polynomials in the J basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
To: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
then
Generic morphism:
From: Symmetric Function Algebra over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field, Schur symmetric functions as basis
To: Macdonald polynomials in the Ht basis over Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field
</pre><p>
(the latter being the same as in vanilla sage)
</p>
TicketSimonKingSun, 22 Jul 2012 12:02:49 GMT
https://trac.sagemath.org/ticket/12969#comment:25
https://trac.sagemath.org/ticket/12969#comment:25
<p>
For the record: With my patch, all tests pass on bsd.math. However, with the patch, it takes 6403.9 seconds, but it is 6106.7 seconds without the patch. Hence, it could be that we have a serious regression, but of course it could also be due to the machine being busy. Should be investigated.
</p>
TicketSimonKingSun, 22 Jul 2012 12:52:46 GMT
https://trac.sagemath.org/ticket/12969#comment:26
https://trac.sagemath.org/ticket/12969#comment:26
<p>
Another data point: On my laptop, the tests for sage/schemes/elliptic_curves took 431.4 seconds without the patch, but 441.4 seconds with the patch. That means a regression of 2.3%, which probably isn't significant. But I'd feel better if the reviewer did some timings as well.
</p>
TicketaschillingMon, 23 Jul 2012 07:30:03 GMT
https://trac.sagemath.org/ticket/12969#comment:27
https://trac.sagemath.org/ticket/12969#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12969#comment:23" title="Comment 23">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Question: Is <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> very close to being positively reviewed? Namely, we must decide whether we use the old syntax for the to-be-written doctest (in that case, this ticket would be a dependency for <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a>), or use the new syntax (in that case, due to deprecation warnings, <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> would become a dependency for this ticket).
</p>
<p>
For now, I will use the old syntax.
</p>
</blockquote>
<p>
Mike and I already cross reviewed 5457. We are just waiting for green light from Dan Bump or Franco Saliola. So hopefully (!?) 5457 will go in soon.
</p>
<p>
Anne
</p>
TicketSimonKingMon, 23 Jul 2012 08:20:15 GMT
https://trac.sagemath.org/ticket/12969#comment:28
https://trac.sagemath.org/ticket/12969#comment:28
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12969#comment:27" title="Comment 27">aschilling</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12969#comment:23" title="Comment 23">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Question: Is <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> very close to being positively reviewed? Namely, we must decide whether we use the old syntax for the to-be-written doctest (in that case, this ticket would be a dependency for <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a>), or use the new syntax (in that case, due to deprecation warnings, <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> would become a dependency for this ticket).
</p>
<p>
For now, I will use the old syntax.
</p>
</blockquote>
<p>
Mike and I already cross reviewed 5457. We are just waiting for green light from Dan Bump or Franco Saliola. So hopefully (!?) 5457 will go in soon.
</p>
</blockquote>
<p>
OK. The only problem related with <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> is the syntax in one new doctest. I suggest that I provide a second optional patch (like: if <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> is in then use both patches, otherwise only use one patch).
</p>
TicketSimonKingMon, 23 Jul 2012 11:30:58 GMTattachment set
https://trac.sagemath.org/ticket/12969
https://trac.sagemath.org/ticket/12969
<ul>
<li><strong>attachment</strong>
set to <em>trac12969_fix_coercion_cache.patch</em>
</li>
</ul>
<p>
Using the old syntax for symmetric function algebras (pre-<a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a>)
</p>
TicketSimonKingMon, 23 Jul 2012 11:33:45 GMT
https://trac.sagemath.org/ticket/12969#comment:29
https://trac.sagemath.org/ticket/12969#comment:29
<p>
I have slightly updated the patch. Only difference: A dictionary, that previously was declared as "cdef object", is now "cdef dict".
</p>
<p>
I repeated timings for <code>sage -t devel/sage/sage/schemes/elliptic_curves/</code>. I did three runs, the time is in seconds:
</p>
<p>
<span class="underline">Vanilla sage-5.2.rc0</span>
</p>
<p>
442.5, 441.9, 442.3
</p>
<p>
<span class="underline">sage-5.2.rc0 plus the patch</span>
</p>
<p>
443.3, 440.8, 442.1
</p>
<p>
So, apparently the 2.3% regression that I found earlier has been random noise.
</p>
TicketSimonKingMon, 23 Jul 2012 11:39:02 GMTattachment set
https://trac.sagemath.org/ticket/12969
https://trac.sagemath.org/ticket/12969
<ul>
<li><strong>attachment</strong>
set to <em>trac12969_rel_5457.patch</em>
</li>
</ul>
<p>
Rewrite one doctest to use the syntax introduced in <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a>
</p>
TicketSimonKingMon, 23 Jul 2012 11:42:38 GMTdescription changed
https://trac.sagemath.org/ticket/12969#comment:30
https://trac.sagemath.org/ticket/12969#comment:30
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12969?action=diff&version=30">diff</a>)
</li>
</ul>
<p>
I have attached a second patch. It is <em>only</em> needed if <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> is applied.
</p>
<p>
Since there seems to be no regression, I think it can now be reviewed.
</p>
<p>
For the release manager: Use the second patch on top of that, as soon as <a class="closed ticket" href="https://trac.sagemath.org/ticket/5457" title="enhancement: Refactor symmetric functions and k-bounded subspace (closed: fixed)">#5457</a> is merged.
</p>
<p>
For the patchbot:
</p>
<p>
Apply trac12969_fix_coercion_cache.patch
</p>
TicketSimonKingTue, 24 Jul 2012 07:01:51 GMT
https://trac.sagemath.org/ticket/12969#comment:31
https://trac.sagemath.org/ticket/12969#comment:31
<p>
The patch seems to work. But meanwhile I wonder whether my fix is really correct.
</p>
<p>
The aim is: Find a coercion from X to Y.
</p>
<p>
Backtracking means: We know some B1,B2,... that coerce into Y. Hence, we try to find a coercion from X to B1,B2,... but avoiding Y, so that there is no infinite loop. That's why the pair (X,Y) is temporarily disregarded when searching for a coerce path.
</p>
<p>
In particular, the recursive search will always start at X.
</p>
<p>
Hence, it was my understanding that all temporarily disregarded paths start at X. That's why I wrote
</p>
<div class="wiki-code"><div class="code"><pre>cdef bint _may_cache_none<span class="p">(</span>x<span class="p">,</span> y<span class="p">,</span> tag<span class="p">)</span> <span class="k">except</span> <span class="o">-</span><span class="mi">1</span><span class="p">:</span>
<span class="c"># Are we allowed to cache the absence of a coercion</span>
<span class="c"># from y to x? We are only allowed, if y is *not*</span>
<span class="c"># part of any coerce path that is temporarily disregarded,</span>
<span class="c"># with the only exception of the path from y to x.</span>
<span class="c"># See #12969.</span>
cdef EltPair P
<span class="k">for</span> P <span class="ow">in</span> _coerce_test_dict<span class="o">.</span>iterkeys<span class="p">():</span>
<span class="k">if</span> <span class="p">(</span>P<span class="o">.</span>y <span class="ow">is</span> y<span class="p">)</span> <span class="ow">and</span> <span class="p">(</span>P<span class="o">.</span>x <span class="ow">is</span> <span class="ow">not</span> x<span class="p">)</span> <span class="ow">and</span> <span class="p">(</span>P<span class="o">.</span>tag <span class="ow">is</span> tag<span class="p">):</span>
<span class="k">return</span> <span class="mi">0</span>
<span class="k">return</span> <span class="mi">1</span>
</pre></div></div><p>
However, to be on the safe side, I tested whether I drew the correct conclusion. Apparently I didn't.
</p>
<p>
Namely, when Sage starts and a coercion from the complex double field into, say, the integer ring is sought, then the path from the complex lazy field to the complex double field is disregarded. Also, while trying to find a coercion from the complex lazy field to the integers, the search path from "Number Field in I with defining polynomial x<sup>2</sup> + 1" to the rational field is temporarily disregarded.
</p>
<p>
Even weirder: When doing <code>m(P.one())</code> in the example from the ticket description, the coercion from "<type 'str'>" to Fraction Field of Multivariate Polynomial Ring in q, t over Rational Field is disregarded, while searching for a coerce path from None (sic!) to the ring of integers.
</p>
<p>
I wonder how this can possibly happen, given how backtracking works. And what does that mean for the patch? I guess the cleanest solution would be to find out why the wrong paths are temporarily disregarded, and why the heck a coercion from None to anything is requested.
</p>
TicketSimonKingTue, 24 Jul 2012 07:42:08 GMT
https://trac.sagemath.org/ticket/12969#comment:32
https://trac.sagemath.org/ticket/12969#comment:32
<p>
I found that a coercion from None is sought when asking the following:
</p>
<pre class="wiki">sage: P = QQ['x','y','a']
sage: P.has_coerce_map_from(str)
</pre><p>
I suggest to fix that <em>here</em>, unless it is too complicated.
</p>
TicketSimonKingTue, 24 Jul 2012 07:51:50 GMT
https://trac.sagemath.org/ticket/12969#comment:33
https://trac.sagemath.org/ticket/12969#comment:33
<p>
Got it. In sage/structure/parent_old.pyx, which unfortunately is still involved in <code>MPolynomialRing_libsingular</code>, there is line 152:
</p>
<pre class="wiki"> sage_type = py_scalar_parent(S)
</pre><p>
However, is S is <code><type 'str'></code> then its py_scalar_parent is None (which seems wrong, or if it isn't wrong then one should at least catch the special case None). The function py_scalar_parent is in sage/structure/coerce.pyx.
</p>
TicketSimonKingTue, 24 Jul 2012 08:43:36 GMT
https://trac.sagemath.org/ticket/12969#comment:34
https://trac.sagemath.org/ticket/12969#comment:34
<p>
It turns out: When making a special case when py_scalar_parent is None, then indeed <em>in our example</em> it is always the case that the starting point of a coerce path we are looking for is the same as the starting point of any path we temporarily disregard. This is how it should be. I will update my patch a bit later.
</p>
<p>
However, when starting Sage, it is still the case that the path from <code>Number Field in I with defining polynomial x^2 + 1</code> to <code>Rational Field</code> is blocked while searching for a path from <code>Complex Lazy Field</code> to <code>Integer Ring</code>, or <code>Algebraic Field</code> to <code>Real Field with 53 bits of precision</code> is blocked while searching for <code><type 'float'></code> to <code>Algebraic Field</code>.
</p>
<p>
But I think I understand that as well: When searching for a coercion from P to, e.g., the complex field CC, the first thing the coercion model does is to temporarily disregard (P,CC) for the backtracking algorithm. Then, <code>CC._coerce_map_from_(P)</code> is called at some point. But the last line of that method calls <code>CC._coerce_map_via([CLF],P)</code>. Hence, while (P,CC) is still disregarded, not only a coerce path from P to CLF but also a coerce path from CLF to CC is sought.
</p>
<p>
I tend to say that it is the responsibility of the person writing <code>_coerce_map_from_</code> for a parent to avoid ill effects.
</p>
<p>
Therefore, I still think that the solution of my patch ("do not cache the absence of a coerce path from A to B if there is any temporarily disregarded path that stars at A") is fine. If the reviewer disagrees then we may consider a very strict solution: "do not cache the absence of a coerce path from A to B if there is any temporarily disregarded path besides (A,B) itself."
</p>
<p>
Thoughts?
</p>
TicketnthieryTue, 24 Jul 2012 08:48:43 GMT
https://trac.sagemath.org/ticket/12969#comment:35
https://trac.sagemath.org/ticket/12969#comment:35
<p>
I haven't checked the detail, but the music sounds good. In any cases, we are just looking for a temporary fix that improves the situation until we rewrite completely the search algorithm; if it's not perfect, so be it. So I would say: if all tests pass, go for it.
</p>
<p>
Thanks!
</p>
TicketSimonKingTue, 24 Jul 2012 10:22:22 GMTattachment set
https://trac.sagemath.org/ticket/12969
https://trac.sagemath.org/ticket/12969
<ul>
<li><strong>attachment</strong>
set to <em>trac_12969-avoid_coercion_from_none.patch</em>
</li>
</ul>
<p>
Shortcut when searching for a coercion from a type that is no parent (e.g., <str>)
</p>
TicketSimonKingTue, 24 Jul 2012 10:44:24 GMTcomponent, description changed
https://trac.sagemath.org/ticket/12969#comment:36
https://trac.sagemath.org/ticket/12969#comment:36
<ul>
<li><strong>component</strong>
changed from <em>combinatorics</em> to <em>coercion</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12969?action=diff&version=36">diff</a>)
</li>
</ul>
<p>
I added another patch. Its purpose:
</p>
<p>
Python types are sometimes considered as parents. There is a function sage.structure.coerce.py_scalar_parent returning a parent that corresponds to a type. Some types, e.g., <code><type 'str'></code>, do not correspond to a parent, hence py_scalar_parent(str) returns None.
</p>
<p>
Still, the code in sage.structure.parent_old would try to construct a coercion from None (the non-existing parent) to self. The result is clear a-priori: There is no such coercion. The new patch establishes a short-cut.
</p>
<p>
For the reviewer:
</p>
<p>
Here is a summary of how the main patch trac12969_fix_coercion_cache.patch works.
</p>
<ol><li>When searching for a coerce path from A to B by back-tracking, it is vital that it is not attempted to construct a path from A to B in the inner parts of the recursion. Hence, the path from A to B is temporarily disregarded, by calling <code>_register_pair(B,A,"coerce")</code> -- that's existing code.
</li><li>When a coercion from A to B is found, then it is cached. When a coercion from A to B is not found, then the unpatched code would cache that as well. With the patch, the absence of a coercion from A to B is only cached, if <code>_register_pair(C,A,"coerce")</code> has not been called for any C different from B.
</li></ol><p>
Here is a discussion of how it is justified.
</p>
<ul><li>In a pure back-tracking algorithm searching for a path from A to B, <em>any</em> temporarily disregarded path starts in A. Hence, it is correct to focus on such paths in 2. above.
</li><li>There are cases in which a <code>_coerce_map_from_</code> method breaks the pure back-tracking algorithm. So, theoretically, the following can happen: i) We search a path from A to B, which is temporarily disregarded in back-tracking. ii) While searching, a <code>_coerce_map_from_</code> method is called that internally searches a path from C to D. iii) There is a path from C to D, but it would involve a path from A to B. iv) Since that path is disregarded and since "A is not C", we would cache the absence of a coercion from C to D in 2. above - which may be wrong.
</li><li>While the preceding point is a theoretical possibility, it is the responsibility of the author of _coerce_map_from_ that it does not occur in reality.
</li></ul><p>
If the reviewer disagrees and believes that we must exclude the theoretical possibility of a failure, we could modify 2. above, as follows:
</p>
<blockquote>
<p>
2'. When a coercion from A to B is found, then it is cached. When a coercion from A to B is not found, then the unpatched code would cache that as well. With the patch, the absence of a coercion from A to B is only cached, if <code>_register_pair(D,C,"coerce")</code> has not been called for any (C,D) different from (A,B).
</p>
</blockquote>
<p>
Anyway. Since tests pass and since (even better) the sporadic errors with <a class="closed ticket" href="https://trac.sagemath.org/ticket/715" title="defect: Parents probably not reclaimed due to too much caching (closed: fixed)">#715</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/12215" title="defect: Memleak in UniqueRepresentation, @cached_method (closed: fixed)">#12215</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/11521" title="defect: Use weak references to cache homsets (closed: fixed)">#11521</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/12313" title="defect: Fix yet another memory leak caused by caching of coercion data (closed: fixed)">#12313</a> seem to vanish with the patch, I would suggest to keep the patch as it is now.
</p>
<p>
PS: I am changing the component, since it isn't about combinatorics but about coercion.
</p>
<p>
Apply trac12969_fix_coercion_cache.patch trac_12969-avoid_coercion_from_none.patch
</p>
TicketSimonKingTue, 24 Jul 2012 10:50:01 GMT
https://trac.sagemath.org/ticket/12969#comment:37
https://trac.sagemath.org/ticket/12969#comment:37
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12969#comment:35" title="Comment 35">nthiery</a>:
</p>
<blockquote class="citation">
<p>
In any cases, we are just looking for a temporary fix that improves the situation until we rewrite completely the search algorithm; if it's not perfect, so be it. So I would say: if all tests pass, go for it.
</p>
</blockquote>
<p>
I agree. The main purpose is a fix of the existing algorithm, so that the memleak fixes in <a class="closed ticket" href="https://trac.sagemath.org/ticket/715" title="defect: Parents probably not reclaimed due to too much caching (closed: fixed)">#715</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/12215" title="defect: Memleak in UniqueRepresentation, @cached_method (closed: fixed)">#12215</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/11521" title="defect: Use weak references to cache homsets (closed: fixed)">#11521</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/12313" title="defect: Fix yet another memory leak caused by caching of coercion data (closed: fixed)">#12313</a> work reliably. I am confident that a fix relying on a new algorithm should work as well.
</p>
TicketaschillingWed, 25 Jul 2012 02:15:40 GMT
https://trac.sagemath.org/ticket/12969#comment:38
https://trac.sagemath.org/ticket/12969#comment:38
<p>
Thanks, Simon, for fixing this bug! Your solution looks ok to me, though I strongly recommend that someone reprograms the coercion algorithm in the future.
</p>
<p>
I ran all tests on top of 5457 and all tests passed! So I am giving this a positive review. Hopefully it can be merged together with 5457 (but if 5457 gets held up, this can go in nonetheless).
</p>
<p>
Anne
</p>
TicketaschillingWed, 25 Jul 2012 02:16:10 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/12969#comment:39
https://trac.sagemath.org/ticket/12969#comment:39
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Anne Schilling</em>
</li>
</ul>
TicketjdemeyerWed, 01 Aug 2012 12:11:36 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/12969#comment:40
https://trac.sagemath.org/ticket/12969#comment:40
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.3.beta0</em>
</li>
</ul>
TicketchapotonSun, 06 Sep 2015 17:42:52 GMTdescription changed
https://trac.sagemath.org/ticket/12969#comment:41
https://trac.sagemath.org/ticket/12969#comment:41
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12969?action=diff&version=41">diff</a>)
</li>
</ul>
Ticket