Closed anneschilling closed 12 years ago
simon-king-jena
commented
12 years ago Just for the record: My impression was that solving this ticket could also help with a couple of coercion-related memory leaks considered in #715, #12215, #12313 and so on.
simon-king-jena
commented
12 years ago I can confirm that the problem occurs with vanilla sage-5.2.rc0, namely resulting in this error:
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)Observation: When starting with your example, one gets
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)
FalseThus, apparently the problem is that "coerce_map_from" does not call discover_coercion when it should. Broken cache, apparently. Non-unique parents?
simon-king-jena
commented
12 years ago In sage.structure.parent.Parent.coerce_map_from, I see the lines
mor = self.discover_coerce_map_from(S)
#if mor is not None:
# # Need to check that this morphism doesn't connect previously unconnected parts of the coercion diagram
# if self._embedding is not None and not self._embedding.codomain().has_coerce_map_from(S):
# # The following if statement may call this function with self and S. If so, we want to return None,
# # so that it doesn't use this path for the existence of a coercion path.
# # We disable this for now because it is too strict
# pass
# # print "embed problem: the following morphisms connect unconnected portions of the coercion graph\n%s\n%s"%(self._embedding, mor)
# # mor = None
if mor is not None:
# NOTE: this line is what makes the coercion detection stateful
# self._coerce_from_list.append(mor)
pass
self._coerce_from_hash[S] = morLooks suspicious to me. A lot of commented-out code, and an empty special case when the coercion is not None.
simon-king-jena
commented
12 years ago 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 NoneQuestion: Why is that method not overridden for the different realisations of MacdonaldPolynomials?
simon-king-jena
commented
12 years ago If I understand correctly, the coercion maps are supposed to go via Schur basis. But while one has
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)
Trueone has (or does in fact not have)
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'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?
simon-king-jena
commented
12 years ago Adding
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_sto MacdonaldPolynomials_generic solves the problem. But I first have to check whether the original coercion from P to Ht (which exists if one does not do m(P.one())) is the same.
simon-king-jena
commented
12 years ago Helas. It is not the same. Doing the above, one gets an awfully complicated composition of maps, probably rather inefficient.
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 FieldI added
def test_coercions(self):
return self._coerce_from_hashto self.structure.parent.Parent, and obtain
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
TrueIn other words, trying to find the coercion from P to m changes the coercion cache of Ht. Funny.
anneschilling
commented
12 years ago Description changed:
---
+++
@@ -12,7 +12,7 @@
The coercion path does exist, however!
-This can also be checked with the new syntax using the patches in the sage-combinat queue as follows:
+This can also be checked with the new syntax using the patches in [https://github.com/sagemath/sage/issues/5457](https://github.com/sagemath/sage/issues/5457) as follows:
sage: R = QQ['q,t'].fraction_field()Hi Simon!
Thank you for investigating this. I should mention that Mike Zabrocki and I just finished a patch in https://github.com/sagemath/sage/issues/5457 which changes the syntax for symmetric functions. As far as I know the coercion also breaks in that set-up.
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 https://github.com/sagemath/sage/issues/8899. Franco, could you post your precise failure?
Anne
saliola
commented
12 years ago Replying to @anneschilling:
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 https://github.com/sagemath/sage/issues/8899. Franco, could you post your precise failure?
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 #8899 (we are only implementing the "classical" bases in this first stage).
Franco
nthiery
commented
12 years ago Replying to @simon-king-jena:
Helas. It is not the same. Doing the above, one gets an awfully complicated composition of maps, probably rather inefficient.
Yes that's the well know issue (#8878) of the current coercion model implementation: it does a depth first search rather than a breath first.
nthiery
commented
12 years ago Question: Why is that method not overridden for the different realisations of
MacdonaldPolynomials?
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).
Cheers, Nicolas
simon-king-jena
commented
12 years ago I think I can explain (and thus, solve) the problem!
The bug is in the backtracking algorithm for finding a coercion path.
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.
Now consider the following situation, where arrows denote registered coercions (partially the coercions are registered in both directions - that's what happening in the symmetric functions code):
X -> B2 <-> A <-> B1We first ask for a coercion from X to A.
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.
But when later asking for a coercion from X to B1, the cache states that there is no coercion!
Here's the bug: The absence of a coercion from X to B1 must only 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).
simon-king-jena
commented
12 years ago 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.
simon-king-jena
commented
12 years ago Replying to @simon-king-jena:
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.
No, to my surprise, it isn't:
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 loopSets seem slower than dictionaries by 5%.
simon-king-jena
commented
12 years ago Replying to @nthiery:
Yes that's the well know issue (#8878) of the current coercion model implementation: it does a depth first search rather than a breath first.
OK. I think #8878 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 here. And if in future someone will tackle #8878, he/she should do so on top of that fix.
nthiery
commented
12 years ago Replying to @simon-king-jena:
OK. I think #8878 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 here. And if in future someone will tackle #8878, he/she should do so on top of that fix.
I actually have an implementation for #8878 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.
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.
Cheers, Nicolas
simon-king-jena
commented
12 years ago Question: Is #5457 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 #5457), or use the new syntax (in that case, due to deprecation warnings, #5457 would become a dependency for this ticket).
For now, I will use the old syntax.
simon-king-jena
commented
12 years ago The attached patch seems to fix the problem.
Questions:
Is there a speed regression?
With my patch, the absence of a coercion from X to Y is only cached, if no coercion path from X to Z (with Z different from Y) is temporarily disabled. But if there really 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.
What about #5457
I did not run the tests, yet. But the new test in my patch would fail because of the deprecation warnings introduced by #5457. So, we must decide whether making #5457 depend on this ticket or the other way around?
For the record: Without #5457, I now get
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[]and
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(the latter being the same as in vanilla sage)
simon-king-jena
commented
12 years ago Author: Simon King
simon-king-jena
commented
12 years ago 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.
simon-king-jena
commented
12 years ago 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.
anneschilling
commented
12 years ago Replying to @simon-king-jena:
Question: Is #5457 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 #5457), or use the new syntax (in that case, due to deprecation warnings, #5457 would become a dependency for this ticket).
For now, I will use the old syntax.
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.
Anne
simon-king-jena
commented
12 years ago Replying to @anneschilling:
Replying to @simon-king-jena:
Question: Is #5457 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 #5457), or use the new syntax (in that case, due to deprecation warnings, #5457 would become a dependency for this ticket).
For now, I will use the old syntax.
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.
OK. The only problem related with #5457 is the syntax in one new doctest. I suggest that I provide a second optional patch (like: if #5457 is in then use both patches, otherwise only use one patch).
simon-king-jena
commented
12 years ago Attachment: trac12969_fix_coercion_cache.patch.gz
Using the old syntax for symmetric function algebras (pre-#5457)
simon-king-jena
commented
12 years ago I have slightly updated the patch. Only difference: A dictionary, that previously was declared as "cdef object", is now "cdef dict".
I repeated timings for sage -t devel/sage/sage/schemes/elliptic_curves/. I did three runs, the time is in seconds:
Vanilla sage-5.2.rc0
442.5, 441.9, 442.3
sage-5.2.rc0 plus the patch
443.3, 440.8, 442.1
So, apparently the 2.3% regression that I found earlier has been random noise.
simon-king-jena
commented
12 years ago Attachment: trac12969_rel_5457.patch.gz
Rewrite one doctest to use the syntax introduced in #5457
simon-king-jena
commented
12 years ago I have attached a second patch. It is only needed if #5457 is applied.
Since there seems to be no regression, I think it can now be reviewed.
For the release manager: Use the second patch on top of that, as soon as #5457 is merged.
For the patchbot:
Apply trac12969_fix_coercion_cache.patch
simon-king-jena
commented
12 years ago Description changed:
---
+++
@@ -12,7 +12,7 @@
The coercion path does exist, however!
-This can also be checked with the new syntax using the patches in [https://github.com/sagemath/sage/issues/5457](https://github.com/sagemath/sage/issues/5457) as follows:
+This can also be checked with the new syntax using the patches in #5457 as follows:
sage: R = QQ['q,t'].fraction_field()@@ -57,3 +57,8 @@ G = coercion_graph(Ht) G.show()
+
+__Apply__
+
+* [attachment: trac12969_fix_coercion_cache.patch](https://github.com/sagemath/sage-prod/files/10655542/trac12969_fix_coercion_cache.patch.gz), if #5457 is not applied
+* Both patches, if #5457 is appliedThe patch seems to work. But meanwhile I wonder whether my fix is really correct.
The aim is: Find a coercion from X to Y.
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.
In particular, the recursive search will always start at X.
Hence, it was my understanding that all temporarily disregarded paths start at X. That's why I wrote
cdef bint _may_cache_none(x, y, tag) except -1:
# Are we allowed to cache the absence of a coercion
# from y to x? We are only allowed, if y is *not*
# part of any coerce path that is temporarily disregarded,
# with the only exception of the path from y to x.
# See #12969.
cdef EltPair P
for P in _coerce_test_dict.iterkeys():
if (P.y is y) and (P.x is not x) and (P.tag is tag):
return 0
return 1However, to be on the safe side, I tested whether I drew the correct conclusion. Apparently I didn't.
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 x2 + 1" to the rational field is temporarily disregarded.
Even weirder: When doing m(P.one()) 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.
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.
simon-king-jena
commented
12 years ago I found that a coercion from None is sought when asking the following:
sage: P = QQ['x','y','a']
sage: P.has_coerce_map_from(str)I suggest to fix that here, unless it is too complicated.
simon-king-jena
commented
12 years ago Got it. In sage/structure/parent_old.pyx, which unfortunately is still involved in MPolynomialRing_libsingular, there is line 152:
sage_type = py_scalar_parent(S)However, is S is <type 'str'> 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.
simon-king-jena
commented
12 years ago It turns out: When making a special case when py_scalar_parent is None, then indeed in our example 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.
However, when starting Sage, it is still the case that the path from Number Field in I with defining polynomial x^2 + 1 to Rational Field is blocked while searching for a path from Complex Lazy Field to Integer Ring, or Algebraic Field to Real Field with 53 bits of precision is blocked while searching for <type 'float'> to Algebraic Field.
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, CC._coerce_map_from_(P) is called at some point. But the last line of that method calls CC._coerce_map_via([CLF],P). 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.
I tend to say that it is the responsibility of the person writing _coerce_map_from_ for a parent to avoid ill effects.
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."
Thoughts?
nthiery
commented
12 years ago 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.
Thanks!
simon-king-jena
commented
12 years ago Shortcut when searching for a coercion from a type that is no parent (e.g.,
simon-king-jena
commented
12 years ago Description changed:
---
+++
@@ -60,5 +60,5 @@
__Apply__
-* [attachment: trac12969_fix_coercion_cache.patch](https://github.com/sagemath/sage-prod/files/10655542/trac12969_fix_coercion_cache.patch.gz), if #5457 is not applied
-* Both patches, if #5457 is applied
+* [attachment: trac12969_fix_coercion_cache.patch](https://github.com/sagemath/sage-prod/files/10655542/trac12969_fix_coercion_cache.patch.gz) and [attachment: trac_12969-avoid_coercion_from_none.patch](https://github.com/sagemath/sage-prod/files/10655544/trac_12969-avoid_coercion_from_none.patch.gz), if #5457 is not applied
+* All three patches, if #5457 is appliedAttachment: trac_12969-avoid_coercion_from_none.patch.gz
I added another patch. Its purpose:
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., <type 'str'>, do not correspond to a parent, hence py_scalar_parent(str) returns None.
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.
For the reviewer:
Here is a summary of how the main patch trac12969_fix_coercion_cache.patch works.
_register_pair(B,A,"coerce") -- that's existing code._register_pair(C,A,"coerce") has not been called for any C different from B.Here is a discussion of how it is justified.
_coerce_map_from_ 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 _coerce_map_from_ 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._coerce_map_from_ that it does not occur in reality.If the reviewer disagrees and believes that we must exclude the theoretical possibility of a failure, we could modify 2. above, as follows:
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 _register_pair(D,C,"coerce") has not been called for any (C,D) different from (A,B).
Anyway. Since tests pass and since (even better) the sporadic errors with #715, #12215, #11521 and #12313 seem to vanish with the patch, I would suggest to keep the patch as it is now.
PS: I am changing the component, since it isn't about combinatorics but about coercion.
Apply trac12969_fix_coercion_cache.patch trac_12969-avoid_coercion_from_none.patch
simon-king-jena
commented
12 years ago Replying to @nthiery:
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.
I agree. The main purpose is a fix of the existing algorithm, so that the memleak fixes in #715, #12215, #11521 and #12313 work reliably. I am confident that a fix relying on a new algorithm should work as well.
anneschilling
commented
12 years ago 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.
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).
Anne
anneschilling
commented
12 years ago Reviewer: Anne Schilling
jdemeyer
commented
12 years ago Merged: sage-5.3.beta0
fchapoton
commented
9 years ago Description changed:
---
+++
@@ -30,14 +30,14 @@
def coercion_graph(self, G = None):return G
R = QQ['q,t'].fraction_field() R.rename("R")
The following code triggers a coercion failure in the symmetric function code
The coercion path does exist, however!
This can also be checked with the new syntax using the patches in #5457 as follows:
The bug is in the coercion system. Sage does not find a path from P to Ht, whereas there definitely is one:
Apply
CC: @sagetrac-sage-combinat @saliola @zabrocki
Component: coercion
Keywords: symmetric functions
Author: Simon King
Reviewer: Anne Schilling
Merged: sage-5.3.beta0
Issue created by migration from https://trac.sagemath.org/ticket/12969