#12969: Coercion failures in symmetric functions
-------------------------------------------------+--------------------------
Reporter: aschilling | Owner: sage-combinat
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.3
Component: coercion | Resolution:
Keywords: symmetric functions, coercion | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Simon King | Merged in:
Dependencies: | Stopgaps:
-------------------------------------------------+--------------------------
Changes (by SimonKing):
* component: combinatorics => coercion
Old description:
> The following code triggers a coercion failure in the symmetric function
> code
>
> {{{
> 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())
> }}}
>
> The coercion path does exist, however!
>
> This can also be checked with the new syntax using the patches in #5457
> as follows:
>
> {{{
> 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())
> }}}
>
> The bug is in the coercion system. Sage does
> not find a path from P to Ht, whereas there definitely is one:
>
> {{{
> 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()
> }}}
>
> __Apply__
>
> * [attachment:trac12969_fix_coercion_cache.patch], if #5457 is not
> applied
> * Both patches, if #5457 is applied
New description:
The following code triggers a coercion failure in the symmetric function
code
{{{
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())
}}}
The coercion path does exist, however!
This can also be checked with the new syntax using the patches in #5457 as
follows:
{{{
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())
}}}
The bug is in the coercion system. Sage does
not find a path from P to Ht, whereas there definitely is one:
{{{
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()
}}}
__Apply__
* [attachment:trac12969_fix_coercion_cache.patch] and
[attachment:trac_12969-avoid_coercion_from_none.patch], if #5457 is not
applied
* All three patches, if #5457 is applied
--
Comment:
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.
1. 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 `_register_pair(B,A,"coerce")` -- that's existing
code.
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(C,A,"coerce")` has not been called for any
C different from B.
Here is a discussion of how it is justified.
* In a pure back-tracking algorithm searching for a path from A to B,
''any'' temporarily disregarded path starts in A. Hence, it is correct to
focus on such paths in 2. above.
* There are cases in which a `_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.
* 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.
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12969#comment:36>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
