Sage: Ticket #15303: Coercion discovery fails to be transitive
https://trac.sagemath.org/ticket/15303
<p>
As found in <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a>:<a class="missing ticket" title="ticket comment does not exist">comment:134</a>, the following example shows that a combination of <code>register_embedding</code> and <code>register_coercion</code> can lead to a failure in transitivity for coercion discovery; also discussed on <a class="ext-link" href="https://groups.google.com/forum/?hl=en#!topic/sage-devel/pH-97DE41wA"><span class="icon"></span>sage-devel</a>:
</p>
<pre class="wiki">class pA(Parent): pass
class pB(Parent): pass
class pC(Parent): pass
A=pA(); B=pB(); C=pC()
BtoA=Hom(B,A)(lambda x: A(x))
AtoC=Hom(A,C)(lambda x: C(x))
A.register_coercion(BtoA)
A.register_embedding(AtoC)
G=get_coercion_model()
G.discover_coercion(A,C) #finds AtoC
G.discover_coercion(B,A) #finds BtoA
G.discover_coercion(B,C) #does not find the composition of BtoA with AtoC
</pre><p>
One workaround is simple: just don't use <code>register_embedding</code>. However, after <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a>, there are different lifetime implications between using <code>register_embedding</code> and <code>register_coercion</code>, so this workaround might not be desirable.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15303
Trac 1.1.6nbruinThu, 17 Oct 2013 22:18:57 GMT
https://trac.sagemath.org/ticket/15303#comment:1
https://trac.sagemath.org/ticket/15303#comment:1
<p>
The problem is that in the present implementation, both coercions are stored on <code>A</code>, so if a coercion from <code>B</code> to <code>C</code> is requested, it hard to realize that <code>A</code> should even be considered.
</p>
<p>
As far as I understand, the coercion model should behave as a digraph on the parents, where a coercion between parents exists if there is a path from one to the other. In that model, coercion existence should be transitive, so the behaviour described is a bug.
</p>
<p>
One way to work around it is, at least for coercion discovery, to store the coercion always on the codomain. By <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a> this can now happen without the implication that the codomain will keep the domain alive. We would have to store it in a place where it can be used for coercion discovery, though.
</p>
<p>
If it is desirable to keep the current lifetime implications for <code>register_embedding</code> (and it probably is) then we should ensure this separately, either by also storing the embedding map on the domain or by just having a direct reference from the domain to the codomain.
</p>
TicketSimonKingFri, 18 Oct 2013 09:20:44 GMT
https://trac.sagemath.org/ticket/15303#comment:2
https://trac.sagemath.org/ticket/15303#comment:2
<p>
It has also been discussed on sage-devel that the existence of a coercion from B to C would change over time. Namely:
</p>
<ol><li>Create B and C. You will not find a coercion, because A is not known yet.
</li><li>Create A, registering a coercion from B to A and an embedding of A into C.
</li><li>Provided that we fixed the problem of transitivity, we would now find a coercion from B to C via A.
</li></ol><p>
I suppose that this phenomenon can not be avoided: We can not have a static coercion digraph (otherwise we would restrict ourselves to a fixed finite set of usable parents), and when we have a dynamic coercion graph, then it is, well, dynamic.
</p>
<p>
However, one additional complication arises with the current implementation: The <em>absence</em> of a coercion is cached. Hence, if we asked for a coercion in 1., then in 3. you would still not get a coerce map, because the absence of a coercion has been cached in 1.
</p>
<p>
Let <code>phi: A -> B</code> and do <code>A.register_embedding(phi)</code>. Currently, <code>B</code> is not aware of the existence of <code>phi</code>. Hence, the backtracking algorithm will currently ignore <code>phi</code>. We don't want to store <code>phi</code> as a <em>strong</em> attribute of <code>B</code>, hence, don't want to put it into <code>B._coerce_from_list</code>. But perhaps we could create a new attribute of type <code>MonoDict</code> and store the embedding there? For example <code>B._coerce_embeddings_from[A] = phi</code>, <em>in addition</em> to <code>A._coerce_embedding = phi</code>. Since it is a <code>MonoDict</code> and thus has weak references to the keys, B would not prevent A from being garbage collected (but of course A would still keep B alive, because we registered the coerce embedding).
</p>
<p>
Once this is done, we could change the backtracking so that it not only iterates over <code>B._coerce_from_list</code>, but it <em>additionally</em> iterates over <code>B._coerce_embeddings_from</code>.
</p>
<p>
But what about the problem of caching coercions? We should carefully think if the current scenario (<code>A.register_coercion(B)</code> plus <code>A.register_embedding(C)</code>) is the only scenario that could dynamically change the coercion graph. Here, I assume that <code>self.register_embedding()</code> and <code>self.register_coercion()</code> are <em>only</em> called during <code>self.__init__()</code>.
</p>
<p>
How to make it possible to allow a coercion via a newly created parent?
</p>
<p>
Perhaps the following would be feasible: If we do <code>A.register_embedding(psi)</code>, where <code>psi: A -> C</code>, then we clear the coercion cache of <code>C</code>, in the sense of <em>all cache items stating the <strong>absence</strong> of a coercion to <code>C</code> will be deleted</em>.
</p>
<p>
Note that clearing it in the sense of <em>all cached coercions to <code>C</code> will be deleted</em> is likely to be a bad idea, because the cached coercions might have already been used. So, we should restrict ourselves to allowing new coercions by removing the "there is no coercion" flag.
</p>
<p>
So, would the suggestion make sense to you?
</p>
<ul><li>Have a new <code>MonoDict</code> that stores all coerce embeddings leading <em>into</em> the parent (hence, we would have a strong reference from domain to codomain, and I suggest adding a weak reference from codomain to domain), that will be used in the backtracking algorithm.
</li><li>When registering an embedding, then remove all "there is no coercion" flags from the coercion cache of the codomain.
</li></ul><p>
Hm. Probably this is not good enough. What if we have had <code>D.coerce_map_from(C)</code>, and had cached the absence of a coercion from <code>B</code> to <code>D</code>? After adding <code>A</code>, we would find a coercion from <code>B</code> to <code>D</code> via <code>A</code> and <code>C</code>. Hence, cleaning the coercion cache of <code>C</code> would not be enough---we would need to clean the coercion cache of all parents into which <code>C</code> coerces.
</p>
<p>
Given this example, it seems to me that we could only solve the problem in a drastic way: Do not cache the absence of a coercion at all. But caching the absence of a coercion is essential for speed. So, the drastic solution would probably be correct, but highly infeasible.
</p>
<p>
If nobody has a better suggestion, then I think we should restrict ourselves to just fix the transitivity problem; the cache problem (it seems to me) is not solvable without creating a drastic slow-down.
</p>
TicketnbruinFri, 18 Oct 2013 17:54:48 GMT
https://trac.sagemath.org/ticket/15303#comment:3
https://trac.sagemath.org/ticket/15303#comment:3
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:2" title="Comment 2">SimonKing</a>:
</p>
<blockquote class="citation">
<ol start="3"><li>Provided that we fixed the problem of transitivity, we would now find a coercion from B to C via A.
</li></ol></blockquote>
<p>
There would be an additional effect, by the way: If the coercion that does get discovered is stored as a composition (on C) then there is now a reference from C._coerce_from_hash to A. This reference lives in a <a class="missing wiki">MonoDict?</a> keyed by B, so this reference remains as long as B is alive. So we see that as long as B and C are alive, then A will be kept alive as well (thus, with monodicts we can have objects whose lifetime depends on two objects BOTH being alive)
</p>
<p>
Note that if the composition gets computed in a smarter way (for instance, a composition of homomorphisms between finitely generated rings could be explicitly computed by computing the images of the generators and constructing a straight homomorphism from B to C out of that) then the resulting coercion map might not refer to A anymore.
</p>
<p>
I am not saying that this is avoidable nor that we should consider this a memory leak: we're keeping A in memory for a good reason, even if the reason is not directly supplied by the user.
</p>
<blockquote class="citation">
<p>
However, one additional complication arises with the current implementation: The <em>absence</em> of a coercion is cached. Hence, if we asked for a coercion in 1., then in 3. you would still not get a coerce map, because the absence of a coercion has been cached in 1.
</p>
</blockquote>
<p>
There are milder ways of invalidating caches: We could mark cached non-existence with a "coercion graph version number". When a non-existence is retrieved, one could check the current "coercion graph version number" and if the current graph is newer, we'd have to reinvestigate the "None". Frankly, I don't believe that would give acceptable performance either, but we could at least be much more lazy about invalidating "no coercion exists" findings. The reason why I think this would still not be good enough is because I expect that coercion graph mutations occur fairly frequently (basically with any parent creation) and I don't see a way to localize coercion graph versions, so any mutation would invalidate ALL non-existence caches.
</p>
<blockquote class="citation">
<p>
For example <code>B._coerce_embeddings_from[A] = phi</code>, <em>in addition</em> to <code>A._coerce_embedding = phi</code>. Since it is a <code>MonoDict</code> and thus has weak references to the keys, B would not prevent A from being garbage collected (but of course A would still keep B alive, because we registered the coerce embedding).
</p>
</blockquote>
<p>
Yes, something along those lines. In fact, since <code>_coerce_embeddings_from</code> and <code>_coerce_from_list</code> would serve the same purpose from the perspective of coercion discoveries, I think the entries in <code>_coerce_from_list</code> should also be added to <code>_coerce_embeddings_from</code>, because it would simplify the code. By then it would make more sense to call the attribute <code>_coerce_from_to_be_used_in_backtracking</code> and the list that is now <code>_coerce_from_hash</code> could be <code>_coerce_from_cached_results</code>.
</p>
<p>
By then we should probably be storing ALL maps there in weakened form.
</p>
<p>
The only function of <code>_coerce_from_list</code> now is to keep domains alive, so it would be more economical to replace that by a list <code>_domains_to_keep_alive</code> where we can store strong references to the domains of the corresponding weakened maps that are now in <code>_coerce_from_to_be_used_in_backtracking</code>
</p>
<p>
So we would end up with (names up for choice):
</p>
<ul><li><code>P._coercion_cache</code>: MonoDict containing discovered (weakened) maps into P.
</li><li><code>P._coercion_maps</code>: MonoDict containing (weakened) maps into P that get used by backtracking
</li><li><code>P._domains_to_keep_alive</code>: List of domains that should be kept alive as long as P lives.
</li><li><code>P._codomains_to_keep_alive</code>: List of codomains that should be kept alive as long as P lives. Normally, such codomains Q would have an entry in <code>Q._coercion_maps[P]</code>. Just storing a map in P._coerce_embedding would also have this effect.
</li></ul><p>
In the present naming system, it wasn't immediately clear to me what purposes <code>_coerce_from_hash</code> and <code>_coerce_from_list</code> served, so changing those names could be beneficial.
</p>
<blockquote class="citation">
<p>
If nobody has a better suggestion, then I think we should restrict ourselves to just fix the transitivity problem; the cache problem (it seems to me) is not solvable without creating a drastic slow-down.
</p>
</blockquote>
<p>
Yes, I don't have any suggestions that I seriously believe would lead to acceptable performance.
</p>
TicketSimonKingSat, 19 Oct 2013 09:53:38 GMT
https://trac.sagemath.org/ticket/15303#comment:4
https://trac.sagemath.org/ticket/15303#comment:4
<p>
I was thinking about "versioning" of the coercion graph as well. Perhaps it would be worth trying.
</p>
<p>
The idea would be: We have one global variable, say, <code>cdef unsigned int coerce_graph_version</code>. Whenever we create a node that is neither a sink nor a source in the coerce graph, we increment the variable. This would be cheap, a simple test in <code>.register_coercion()</code> and <code>.register_embedding()</code>.
</p>
<p>
Instead of storing <code>None</code> when a coercion can not be found, we store the current version. Hence, if we do <code>mor = self._coerce_from_hash[P]</code>, a simple <code>isinstance(mor,int)</code> (or a faster version from the Python API that tests if the type of <code>mor</code> is <em>exactly</em> <code>int</code>) will tell us whether the absence of a coercion was cached. If <code>mor==coerce_graph_version</code> then we know that the cached absence of a coercion is reliable. Otherwise, we need to test.
</p>
<p>
Would this really be soooo expensive? I don't think so. Of course, it depends on how often we create non-sink non-source nodes---and I doubt that the combined use of <code>.register_embedding()</code> and <code>.register_coercion()</code> (which is the only way to create non-sink non-source) will happen very often.
</p>
<p>
So, I'd say we simply try.
</p>
TicketnbruinSat, 19 Oct 2013 14:27:46 GMT
https://trac.sagemath.org/ticket/15303#comment:5
https://trac.sagemath.org/ticket/15303#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:4" title="Comment 4">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Would this really be soooo expensive? I don't think so. Of course, it depends on how often we create non-sink non-source nodes---and I doubt that the combined use of <code>.register_embedding()</code> and <code>.register_coercion()</code> (which is the only way to create non-sink non-source) will happen very often.
</p>
</blockquote>
<p>
I don't think you can establish whether something is a non-sink, since <code>_coerce_from_map</code> gives programmatic answers about that. Things are very rarely going to be non-sinks, though, since usually ZZ will coerce into them (but ZZ will never be a problem. perhaps we can leave it out of consideration)
</p>
<p>
A start might be to only version up on "embedding" creations. That might very well be usable. I expect "embeddings" to be relatively rare, and I think we can declare in our documentation they are not the preferred way of expressing relations (they are vary prone to creating non-commutative diamonds).
</p>
TicketSimonKingSat, 19 Oct 2013 17:30:27 GMT
https://trac.sagemath.org/ticket/15303#comment:6
https://trac.sagemath.org/ticket/15303#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:5" title="Comment 5">nbruin</a>:
</p>
<blockquote class="citation">
<p>
I don't think you can establish whether something is a non-sink, since <code>_coerce_from_map</code> gives programmatic answers about that.
</p>
</blockquote>
<p>
Perhaps I have not been clear. A non-sink non-source is something that has both in-arrows (i.e., is codomain of a registered coercion or coerce embedding) and out-arrows (i.e., is domain of a registered coercion or coerce embedding). It is easy to keep track of this property while registering a coercion or coerce embedding.
</p>
<p>
But I actually think that your idea is better anyway:
</p>
<blockquote class="citation">
<p>
A start might be to only version up on "embedding" creations.
</p>
</blockquote>
<p>
It seems to me that this versioning would be complete under reasonable assumptions, based on the following lemma.
</p>
<p>
<strong>Lemma</strong>
</p>
<p>
Assume for all parents <code>P</code>, <code>Q</code>, <code>P.register_coercion(Q)</code> will be done in <code>P.__init__()</code>, but not later. Assume that parents <code>R</code> and <code>S</code> exist at time <code>t_0</code>, but there is no path from <code>R</code> to <code>S</code> in the coerce digraph at time <code>t_0</code>. Assume that between time <code>t_0</code> and time <code>t_1</code>, <code>.register_embedding()</code> has never been called. Then, there is no path from <code>R</code> to <code>S</code> in the coerce digraph at time <code>t_1</code>.
</p>
<p>
<span class="underline">Proof</span>
</p>
<p>
Proof be contradiction. We assume that there is a path from <code>R</code> to <code>S</code> at time <code>t_1</code>. Hence, this path contains an arrow <code>a</code> that has been added to the coerce digraph after <code>t_0</code>. Since no <code>register_embedding()</code> has occurred between <code>t_0</code> and <code>t_1</code>, all arrows created between <code>t_0</code> and <code>t_1</code> have been added by <code>register_coercion()</code>. But by hypothesis, <code>register_coercion()</code> is only called during <code>__init__</code> of the codomain.
</p>
<p>
Hence, all arrows created between <code>t_0</code> and <code>t_1</code> end at parents created after <code>t_0</code>. Therefore, a path in the coerce digraph at time <code>t_1</code> that contains <code>a</code> will necessarily end at a parent that has been created after <code>t_0</code>. This is a contradiction, since <code>S</code> has already existed at time <code>t_0</code>
</p>
<p>
<strong>q.e.d.</strong>
</p>
<blockquote class="citation">
<p>
That might very well be usable. I expect "embeddings" to be relatively rare, and I think we can declare in our documentation they are not the preferred way of expressing relations (they are vary prone to creating non-commutative diamonds).
</p>
</blockquote>
<p>
We could express in the documentation that one should call <code>register_coercion</code> only in the initialisation. Since <code>register_embedding</code> can only be called one time for each parent, I don't think we need to say that other methods of establishing a coercion are preferred.
</p>
TicketSimonKingSat, 19 Oct 2013 18:32:23 GMTdependencies set
https://trac.sagemath.org/ticket/15303#comment:7
https://trac.sagemath.org/ticket/15303#comment:7
<ul>
<li><strong>dependencies</strong>
set to <em>#14711</em>
</li>
</ul>
<p>
I hope you agree that we should start on top of <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a>, because you suggest to change a couple of attribute names that are touched in <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a>.
</p>
TicketSimonKingSat, 19 Oct 2013 19:20:18 GMT
https://trac.sagemath.org/ticket/15303#comment:8
https://trac.sagemath.org/ticket/15303#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:3" title="Comment 3">nbruin</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
For example <code>B._coerce_embeddings_from[A] = phi</code>, <em>in addition</em> to <code>A._coerce_embedding = phi</code>. Since it is a <code>MonoDict</code> and thus has weak references to the keys, B would not prevent A from being garbage collected (but of course A would still keep B alive, because we registered the coerce embedding).
</p>
</blockquote>
<p>
Yes, something along those lines. In fact, since <code>_coerce_embeddings_from</code> and <code>_coerce_from_list</code> would serve the same purpose from the perspective of coercion discoveries, I think the entries in <code>_coerce_from_list</code> should also be added to <code>_coerce_embeddings_from</code>, because it would simplify the code. By then it would make more sense to call the attribute <code>_coerce_from_to_be_used_in_backtracking</code> and the list that is now <code>_coerce_from_hash</code> could be <code>_coerce_from_cached_results</code>.
</p>
</blockquote>
<p>
Or shorter: <code>_coerce_from_backtracking</code> and <code>_coerce_from_cache</code>.
</p>
<blockquote class="citation">
<p>
By then we should probably be storing ALL maps there in weakened form.
</p>
</blockquote>
<p>
Probably.
</p>
<blockquote class="citation">
<p>
The only function of <code>_coerce_from_list</code> now is to keep domains alive, so it would be more economical to replace that by a list <code>_domains_to_keep_alive</code> where we can store strong references to the domains of the corresponding weakened maps that are now in <code>_coerce_from_to_be_used_in_backtracking</code>
</p>
</blockquote>
<p>
I have introduced <code>Parent._registered_domains</code> for exactly this purpose, at <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a>. So, we should extend its use.
</p>
<blockquote class="citation">
<ul><li><code>P._codomains_to_keep_alive</code>: List of codomains that should be kept alive as long as P lives. Normally, such codomains Q would have an entry in <code>Q._coercion_maps[P]</code>. Just storing a map in P._coerce_embedding would also have this effect.
</li></ul></blockquote>
<p>
Yes, and that's why I don't think we need <code>P._codomains_to_keep_alive</code> (I'd prefer the name <code>P._registered_codomains</code>). Even in weakened maps, we have a strong reference to the codomain.
</p>
TicketSimonKingSat, 19 Oct 2013 20:53:13 GMT
https://trac.sagemath.org/ticket/15303#comment:9
https://trac.sagemath.org/ticket/15303#comment:9
<p>
PS: We also have <code>convert_from_list</code>, and I guess we should proceed similarly for <code>coerce_from_list</code>.
</p>
TicketSimonKingSun, 20 Oct 2013 13:03:37 GMT
https://trac.sagemath.org/ticket/15303#comment:10
https://trac.sagemath.org/ticket/15303#comment:10
<p>
With the branch that I have just attached, one gets
</p>
<pre class="wiki">sage: class pA(Parent): pass
sage: class pB(Parent): pass
sage: class pC(Parent): pass
sage:
sage: A=pA(); B=pB(); C=pC()
sage:
sage: BtoA=Hom(B,A)(lambda x: A(x))
sage: AtoC=Hom(A,C)(lambda x: C(x))
sage: A.register_coercion(BtoA)
sage: A.register_embedding(AtoC)
sage: C.coerce_map_from(B)
Composite map:
From: <class '__main__.pB'>
To: <class '__main__.pC'>
WARNING: This map has apparently been used internally
in the coercion system. It may become defunct in the next
garbage collection. Please use a copy.
</pre><p>
What has been done in the patch:
</p>
<ul><li>renaming of attributes (<code>_coerce_from_backtracking</code> etc)
</li><li>do not use a list, but use a <code>MonoDict</code> for all morphisms that are supposed to be fundamental for backtracking. There is a list <code>_registered_domains</code>, so that domains of registered coercions are kept alive by the codomain, but the domain of a registered embedding is <em>not</em> kept alive by the codomain.
</li></ul><p>
Missing: Tests and versioning.
</p>
TicketSimonKingSun, 20 Oct 2013 13:03:53 GMTchangetime, time changed; branch set
https://trac.sagemath.org/ticket/15303#comment:11
https://trac.sagemath.org/ticket/15303#comment:11
<ul>
<li><strong>changetime</strong>
changed from <em>10/20/13 13:03:37</em> to <em>10/20/13 13:03:37</em>
</li>
<li><strong>branch</strong>
set to <em>u/SimonKing/ticket/15303</em>
</li>
<li><strong>time</strong>
changed from <em>10/17/13 22:06:13</em> to <em>10/17/13 22:06:13</em>
</li>
</ul>
TicketnbruinSun, 20 Oct 2013 16:11:56 GMTcommit set
https://trac.sagemath.org/ticket/15303#comment:12
https://trac.sagemath.org/ticket/15303#comment:12
<ul>
<li><strong>commit</strong>
set to <em>dcd8d68fb30f752bcd595d73fe2d3925e7db671f</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:9" title="Comment 9">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
PS: We also have <code>convert_from_list</code>, and I guess we should proceed similarly for <code>coerce_from_list</code>.
</p>
</blockquote>
<p>
yes, conversion probably needs some attention too. However, since conversions exits between a lot more pairs of parents, Do we use backtracking to discover them? There are almost certainly loops: trivially, because ZZ->Z/nZ and Z/nZ->ZZ are valid conversions.
</p>
<p>
If we want a memory leak-free implementation I suspect having conversion without lifetime implications in either direction is required. Definitely material for another ticket.
</p>
<hr />
<p>
Last 10 new commits:
</p>
<table class="wiki">
<tr><td>[changeset:dcd8d68]</td><td>Use registered embeddings for backtracking in the coercion model
</td></tr><tr><td>[changeset:85cf7e8]</td><td>Merge branch 'ticket/14711' into ticket/15303
</td></tr><tr><td>[changeset:364b985]</td><td>Add warning to string repr of weakened maps. Implement copying for *all* kinds of maps.
</td></tr><tr><td>[changeset:5168cfd]</td><td>Generic copy method for maps, using _update_slots Use a cdef _codomain, since the codomain is strongly refed anyway Add doctests
</td></tr><tr><td>[changeset:452d216]</td><td>Add docs to <a class="missing wiki">SchemeMorphism?</a>
</td></tr><tr><td>[changeset:05fb569]</td><td>Change <a class="missing wiki">SchemeMorphism?</a> back (to cope with a Cython bug), copying the new code from sage.categories.map.Map
</td></tr><tr><td>[changeset:8fd09d5]</td><td>Copying of <a class="missing wiki">PolynomialBaseringInjection?</a> and <a class="missing wiki">FormalCompositeMap?</a>
</td></tr><tr><td>[changeset:be37145]</td><td>Let <a class="missing wiki">SchemeMorphism?</a> inherit from Morphism, not from Element
</td></tr><tr><td>[changeset:0f38a2c]</td><td>Keep strong reference to codomain of weakened coerce maps Keep strong reference to domains of *registered* coercions
</td></tr><tr><td>[changeset:a53261d]</td><td>Keep a strong reference to the codomain of <a class="missing wiki">PrecomposedAction?</a>
</td></tr></table>
TicketgitSun, 20 Oct 2013 19:55:01 GMTcommit changed
https://trac.sagemath.org/ticket/15303#comment:13
https://trac.sagemath.org/ticket/15303#comment:13
<ul>
<li><strong>commit</strong>
changed from <em>dcd8d68fb30f752bcd595d73fe2d3925e7db671f</em> to <em>f837cbee8f81c4946a92193c73e86449c53515d9</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td>[changeset:f837cbe]</td><td>Store a version number for the coercion cache, depending on the registered embeddings
</td></tr></table>
TicketSimonKingSun, 20 Oct 2013 20:05:47 GMTstatus changed; author set
https://trac.sagemath.org/ticket/15303#comment:14
https://trac.sagemath.org/ticket/15303#comment:14
<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>
I have pushed a new commit that implements version numbers for the coercion cache, and I added a doctest along the following lines:
</p>
<pre class="wiki">sage: class pA(Parent): pass
sage: class pB(Parent): pass
sage: class pC(Parent): pass
sage: A=pA(); B=pB(); C=pC()
sage: BtoA=Hom(B,A)(lambda x: A(x))
sage: AtoC=Hom(A,C)(lambda x: C(x))
sage: A.register_coercion(BtoA)
sage: C.coerce_map_from(B)
sage: A.register_embedding(AtoC)
sage: C.coerce_map_from(B)
Composite map:
From: <class '__main__.pB'>
To: <class '__main__.pC'>
WARNING: This map has apparently been used internally
in the coercion system. It may become defunct in the next
garbage collection. Please use a copy.
</pre><p>
Hence, I think that the current commit solves our problem. In spite of the following "todo" list, I put it to "needs review" (but I am sure that further commits will be pushed soon).
</p>
<p>
TODO:
</p>
<ul><li>Add documentation, stating that registering of coercions should <em>only</em> be done during initialisation, and that registering of embeddings shouldn't be done too often.
</li><li>Run all doctests---since playing with the coercion digraph is asking for trouble, I wouldn't be surprised about bad surprises <code>:-P</code>
</li><li><strong>Important:</strong> Get timings for examples that should be most sensitive against slow-downs in coercion.
</li></ul>
TicketSimonKingSun, 20 Oct 2013 20:31:13 GMT
https://trac.sagemath.org/ticket/15303#comment:15
https://trac.sagemath.org/ticket/15303#comment:15
<p>
I already found that some test fails when <code>s = SymmetricFunctions(QQbar).s()</code> is done. "Of course", the error only occurs in <code>sage -t src/sage/combinat/sf/sfa.py</code>, but not if one just does <code>s = SymmetricFunctions(QQbar).s()</code> in an interactive session...
</p>
TicketnbruinSun, 20 Oct 2013 20:44:25 GMT
https://trac.sagemath.org/ticket/15303#comment:16
https://trac.sagemath.org/ticket/15303#comment:16
<blockquote class="citation">
<ul><li><strong>Important:</strong> Get timings for examples that should be most sensitive against slow-downs in coercion.
</li></ul></blockquote>
<p>
Looking at what happens for number fields, I have the impression that <code>QQ._populate_coercion_lists_</code> is most frequently used to supply embeddings (I'm not getting many hits on direct calls to !register_embedding, see below)
</p>
<p>
The only two classes I have been able to identify that actually install embeddings are numberfields (and not all of them) and !AbelianGroupWithValues_class
</p>
<p>
So, assuming that the version check itself is lightning-fast (and why shouldn't it be?) I expect that negatively affected examples would have to do a lot of number field or AbelianGroupWithValues creations interleaved with complicated coercion discovery that benefits a lot from knowing certain coercions do NOT exist.
</p>
<p>
There's AdditiveAbelianGroupWrapper which does an <code>_unset_coercions_used</code> together with a <code>register_embedding</code> (registering an "embedding" of the wrapper into the wrapped)
</p>
<p>
There's also UniversalCyclotomicField which registers an embedding into QQbar upon init, so that shouldn't really affect versioning.
</p>
TicketSimonKingSun, 20 Oct 2013 20:45:49 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/15303#comment:17
https://trac.sagemath.org/ticket/15303#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>analyse recursion error</em>
</li>
</ul>
<p>
The following runs into an infinite loop:
</p>
<pre class="wiki">sage: CF = CyclotomicField(5)
sage: UCF.<E> = UniversalCyclotomicField()
sage: CF = CyclotomicField(5,embedding=CC(exp(4*pi*i/5)))
sage: x = E(5)
sage: CC(x)
</pre>
TicketSimonKingSun, 20 Oct 2013 20:49:41 GMT
https://trac.sagemath.org/ticket/15303#comment:18
https://trac.sagemath.org/ticket/15303#comment:18
<p>
Shorter:
</p>
<pre class="wiki">sage: UCF.<E> = UniversalCyclotomicField()
sage: phi = copy(QQbar.coerce_map_from(UCF))
sage: x = E(5)
sage: phi(x)
</pre><p>
Hence, we do have a map, but applying it will run into a loop.
</p>
TicketSimonKingSun, 20 Oct 2013 20:53:31 GMT
https://trac.sagemath.org/ticket/15303#comment:19
https://trac.sagemath.org/ticket/15303#comment:19
<p>
PS: Note that the failing map is a coerce embedding. Hence, it could be that I messed up things in a way that are not related with the cache version. Anyway, I just tested that weakening the coerce embedding has not been the culprit.
</p>
TicketSimonKingSun, 20 Oct 2013 21:16:04 GMT
https://trac.sagemath.org/ticket/15303#comment:20
https://trac.sagemath.org/ticket/15303#comment:20
<p>
Further boiled down:
</p>
<pre class="wiki">sage: psi = QQbar.coerce_map_from(ZZ)
sage: psi(1)
<infinite loop>
</pre>
TicketSimonKingSun, 20 Oct 2013 21:28:56 GMT
https://trac.sagemath.org/ticket/15303#comment:21
https://trac.sagemath.org/ticket/15303#comment:21
<p>
Aha!
</p>
<p>
With my current branch, the coerce map from <code>ZZ</code> to <code>QQbar</code> goes <strong>via the universal cyclotomic field</strong>, if one has created the universal field before putting the coercion into the cache.
</p>
<p>
Obvious reason: With my patch, both registered coercions <em>and</em> registered embeddings are used for backtracking, in order to fix the example of the ticket description. However, <em>if</em> there is a registered coercion, then I guess it should have preference over the registered embedding for backtracking. After all, the registered embedding is some kind of "forward", not "back".
</p>
<p>
So, modified suggestion: We should not put both registered coercions and registered embeddings into <code>codomain._coerce_from_backtracking</code>, but we should have two separate containers, and should look for the coerce embeddings only if no registered coercions are left.
</p>
<p>
Rationale: We suppose that registering coercions happens during initialisation of the codomain, whereas registering an embedding will happen <em>after</em> creation of the codomain. Since the backtracking starts at the codomain, we should have a clear preference for using those maps that are closely tied to the codomain---and these are the maps registered during creation of the codomain.
</p>
TicketnbruinSun, 20 Oct 2013 22:02:34 GMT
https://trac.sagemath.org/ticket/15303#comment:22
https://trac.sagemath.org/ticket/15303#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:21" title="Comment 21">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Rationale: We suppose that registering coercions happens during initialisation of the codomain, whereas registering an embedding will happen <em>after</em> creation of the codomain. Since the backtracking starts at the codomain, we should have a clear preference for using those maps that are closely tied to the codomain---and these are the maps registered during creation of the codomain.
</p>
</blockquote>
<p>
I don't think that rationale is quite valid for the way it gets used. If we do
</p>
<pre class="wiki">a+b
</pre><p>
then we'll be investigating whether b can be coerced into the parent of a and whether a can be coerced into the parent of b. The original question doesn't actually specify a special role for the codomain (which is still up for choice!)
</p>
<p>
It seems to me that you want to argue (and your example backs you up in this) that while there can be multiple paths in the coercion graph, there are some paths that should be preferred over others. If we want to model this properly, we would have to include this information in the graph. One way would be to give each coercion a "cost" and we'd be looking for the lowest cost path (which could change with mutations of the graph!).
</p>
<p>
For your suggestion to fit in such a model, we would need that:
</p>
<ul><li>any path including an embedding is higher cost that a path without.
</li><li>if a path has been discovered, new paths between the same parents that may arise by graph mutations are higher cost
</li></ul><p>
It's not immediately clear to me that those assumptions are valid.
</p>
<p>
Note: what we're trying to solve on this ticket hasn't actually caused problems in real life, partly because embeddings are indeed rare. I could see the temporary outcome of this ticket being "yes, this is a potential problem, here are a few things we could do to fix it, but the cost of doing this is considerable. We'll revisit this if we run into a real-life situation that is actually affected by it".
</p>
<p>
The current approach is basically one where we ignore the cost of the last arrow, and otherwise make the cost of an embedding infinity (which gives a rather odd cost measure, but leads to somewhat desirable behaviour as we're finding out now)
</p>
TicketSimonKingSun, 20 Oct 2013 22:31:54 GMT
https://trac.sagemath.org/ticket/15303#comment:23
https://trac.sagemath.org/ticket/15303#comment:23
<p>
The example of <code>QQbar.coerce_map_from(ZZ)</code> fails as follows.
</p>
<p>
We want that the coercion is determined by <code>QQbar._coerce_map_from_(ZZ)</code> (which returns True). But apparently (with my current patch, at least), the backtracking has preference over what is returned by <code>_coerce_map_from_</code>. I don't understand the reason, yet.
</p>
TicketSimonKingSun, 20 Oct 2013 22:44:24 GMT
https://trac.sagemath.org/ticket/15303#comment:24
https://trac.sagemath.org/ticket/15303#comment:24
<p>
Aha! As it turns out, the "coerce costs" of the direct map are higher than the coerce costs of the composite map that goes via the universal cyclotomic field:
</p>
<pre class="wiki">sage: UCF.<E> = UniversalCyclotomicField()
sage: psi = QQbar.coerce_map_from(ZZ)
sage: psi._coerce_cost
30
</pre><p>
versus
</p>
<pre class="wiki">sage: psi = QQbar.coerce_map_from(ZZ)
sage: psi._coerce_cost
100
</pre><p>
EDIT: ... and this explains why the coercion model does not rely on the result of <code>QQbar._coerce_map_from_(ZZ)</code> (returning a map of cost 100), while the composite map only has the cost 30
</p>
TicketSimonKingSun, 20 Oct 2013 23:24:35 GMT
https://trac.sagemath.org/ticket/15303#comment:25
https://trac.sagemath.org/ticket/15303#comment:25
<p>
The coerce costs of a (generic) map with exact domain and codomain are 10, but 10000 if one of them is inexact. However, the coerce costs of a <code>DefaultConvertMap</code> are between 100 and 400. And it seems to me that this is not well balanced.
</p>
<p>
Namely, if the coercion model has to choose between a single default convert map and a composition of 10 generic maps, it would take the composition---which would of course normally be slower than a single map!
</p>
<p>
This decision has been made 5 years ago. Perhaps the coerce costs should be refactored?
</p>
<p>
It makes sense that the coerce costs for inexact (co)domain will be high. But a single map should certainly be better than a composite map with the same domain and codomain.
</p>
TicketSimonKingSun, 20 Oct 2013 23:27:08 GMTcc changed
https://trac.sagemath.org/ticket/15303#comment:26
https://trac.sagemath.org/ticket/15303#comment:26
<ul>
<li><strong>cc</strong>
<em>robertwb</em> added
</li>
</ul>
<p>
Robert, perhaps you can comment on the reasons for choosing the coerce costs for <code>DefaultConvertMap</code> and friends? Why are the costs so much higher than for a generic map?
</p>
TicketSimonKingMon, 21 Oct 2013 09:05:21 GMT
https://trac.sagemath.org/ticket/15303#comment:27
https://trac.sagemath.org/ticket/15303#comment:27
<p>
It seems to me that the <code>._coerce_costs</code> of a map are largely ignored. Namely, in <code>.discover_coercion()</code>, we have a parameter <code>num_paths</code>: If <code>num_paths</code> paths in the coercion graph are found by backtracking, then the path with the least <code>._coerce_costs</code> is returned. But since <code>num_paths=1</code>, in fact <em>the first</em> found coercion is returned.
</p>
<p>
The only exception is the user provided morphism. Here, the rule is: Even if the user provides a coerce morphism, then one still searches a coercion by backtracking, and in case of success the coerce costs of the user-provided morphism is compared with the other morphism.
</p>
<p>
This just isn't fair!!! I believe that the user-provided morphism should at least have the same priority as a morphism found by backtracking.
</p>
<p>
Two approaches, that are not mutually exclusive:
</p>
<ol><li>Amend the coerce costs, so that a simple map has less costs than a composite map, unless there is a very good reason.
</li><li>Let the user-provided morphism count for the number of morphisms found in <code>.discover_coercion()</code>. Hence, if <code>num_paths=1</code> and the user provides a morphism, then the maximal number of paths-to-be-considered is attained and hence the user-provided morphism is returned without backtracking.
</li></ol><p>
I think the second point is more important, and I will implement it now.
</p>
TicketSimonKingMon, 21 Oct 2013 09:18:58 GMT
https://trac.sagemath.org/ticket/15303#comment:28
https://trac.sagemath.org/ticket/15303#comment:28
<p>
Another issue we might <em>eventually</em> tackle: Connecting paths in the coerce digraph are found by depth first search. We might consider to replace it by a breadth first search. On a different ticket, perhaps, if there is interest.
</p>
TicketSimonKingMon, 21 Oct 2013 09:27:28 GMT
https://trac.sagemath.org/ticket/15303#comment:29
https://trac.sagemath.org/ticket/15303#comment:29
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:27" title="Comment 27">SimonKing</a>:
</p>
<blockquote class="citation">
<ol start="2"><li>Let the user-provided morphism count for the number of morphisms found in <code>.discover_coercion()</code>. Hence, if <code>num_paths=1</code> and the user provides a morphism, then the maximal number of paths-to-be-considered is attained and hence the user-provided morphism is returned without backtracking.
</li></ol><p>
I think the second point is more important, and I will implement it now.
</p>
</blockquote>
<p>
Note one remark in the code:
</p>
<pre class="wiki"> # If there is something better in the list, try to return that instead
# This is so, for example, _coerce_map_from_ can return True but still
# take advantage of the _populate_coercion_lists_ data.
</pre><p>
The <code>_populate_coercion_lists_</code> data are also put into <code>_coerce_from_cache</code>. Hence, these data will have priority over <code>_coerce_map_from_</code> in <code>self.coerce_map_from(other)</code>. Therefore, <code>self.discover_coerce_map_from(other)</code> will <em>only</em> be called if there are no relevant <code>_populate_coercion_lists_</code> data.
</p>
<p>
Hence, I believe that the remark is not valid, and will remove it.
</p>
TicketgitMon, 21 Oct 2013 09:32:53 GMTcommit changed
https://trac.sagemath.org/ticket/15303#comment:30
https://trac.sagemath.org/ticket/15303#comment:30
<ul>
<li><strong>commit</strong>
changed from <em>f837cbee8f81c4946a92193c73e86449c53515d9</em> to <em>74821fe5409c3104b5d6eb7407a8287d54170df9</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td>[changeset:74821fe]</td><td>Give user-provided coerce maps the same priority than to a coerce map found by backtracking
</td></tr></table>
TicketSimonKingMon, 21 Oct 2013 09:34:21 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/15303#comment:31
https://trac.sagemath.org/ticket/15303#comment:31
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>analyse recursion error</em> deleted
</li>
</ul>
<p>
The intermediate problem has been added as a doctest.
</p>
TicketSimonKingMon, 21 Oct 2013 12:22:18 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/15303#comment:32
https://trac.sagemath.org/ticket/15303#comment:32
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>Analyse recursion error</em>
</li>
</ul>
<p>
As it turns out, the last commit fixes <em>one</em> error, but the more problematic errors persist.
</p>
TicketSimonKingMon, 21 Oct 2013 12:36:21 GMT
https://trac.sagemath.org/ticket/15303#comment:33
https://trac.sagemath.org/ticket/15303#comment:33
<p>
The following sequence of commands results in a "recursion depth exceeded" (some other errors are expected, the example is taken from the doctests):
</p>
<pre class="wiki">Sym = SymmetricFunctions(QQ)
Q = Sym.kBoundedQuotient(3,t=1)
Q
km = Q.km()
km
F = Q.affineSchur()
F(km(F[3,1,1])) == F[3,1,1]
km(F(km([3,2]))) == km[3,2]
F[3,2].lift()
F[2,1]*F[2,1]
F[1,2]
km[2,1]*km[2,1]
HLPk = Q.kHallLittlewoodP()
HLPk[2,1]*HLPk[2,1]
dks = Q.dual_k_Schur()
dks[2,1]*dks[2,1]
Q = Sym.kBoundedQuotient(3)
Sym = SymmetricFunctions(QQ['t'].fraction_field())
Q = Sym.kBoundedQuotient(3)
km = Q.km()
F = Q.affineSchur()
F(km(F[3,1,1])) == F[3,1,1]
km(F(km([3,2]))) == km[3,2]
dks = Q.dual_k_Schur()
HLPk = Q.kHallLittlewoodP()
dks(HLPk(dks[3,1,1])) == dks[3,1,1]
km(dks(km([3,2]))) == km[3,2]
</pre><p>
Trying to minimise the example now...
</p>
TicketSimonKingMon, 21 Oct 2013 12:38:10 GMT
https://trac.sagemath.org/ticket/15303#comment:34
https://trac.sagemath.org/ticket/15303#comment:34
<p>
PS: Some of the commands seem to have a rather sluggish behaviour. Perhaps the example is also good for detecting a regression?
</p>
TicketSimonKingMon, 21 Oct 2013 13:03:34 GMT
https://trac.sagemath.org/ticket/15303#comment:35
https://trac.sagemath.org/ticket/15303#comment:35
<p>
I observe that the example sometimes works and sometimes fails. This seems to indicate that one "randomness" in my code is problematic.
</p>
<p>
Namely, with the current commits, the coercions that are used by the backtracking algorithm are stored in a <code>MonoDict</code> (<code>codomain._coerce_from_backtracking</code>). The hash depends on the id of the keys and is thus susceptible to change between different runs of Sage, and therefore the order in which the arrows of the coerce digraph are considered in the backtracking algorithm also changes between different runs of Sage.
</p>
<p>
I am not sure what I shall think of it. My first impulse: It does not matter <em>what</em> map is returned as result of backtracking, but in any case it must be a <em>valid</em> map. In the example of <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:32" title="Comment 32">comment:32</a>, it seems that some arrows in the coerce graph make assumptions on other arrows of the coerce graph (therefore the recursion), which is a bug.
</p>
TicketSimonKingMon, 21 Oct 2013 13:17:10 GMT
https://trac.sagemath.org/ticket/15303#comment:36
https://trac.sagemath.org/ticket/15303#comment:36
<p>
I think I see a potential problem. In <code>sage.combinat.sf.k_dual.DualkSchurFunctions.__init__</code>, there is
</p>
<pre class="wiki">kHLP = kBoundedRing.kHallLittlewoodP()
self.module_morphism(self._dks_to_khlp_on_basis,codomain=kHLP).register_as_coercion()
</pre><p>
Hence, a coercion is registered on <code>kHLP</code> <strong>after</strong> it is initialised. As we have seen in the proof of my Lemma, such registration should result in an increase of the cache version number.
</p>
<p>
Hence, I will change <code>Map.register_as_coercion()</code> so that it increases the cache version number.
</p>
TicketSimonKingMon, 21 Oct 2013 13:26:26 GMT
https://trac.sagemath.org/ticket/15303#comment:37
https://trac.sagemath.org/ticket/15303#comment:37
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:36" title="Comment 36">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Hence, I will change <code>Map.register_as_coercion()</code> so that it increases the cache version number.
</p>
</blockquote>
<p>
I think it should be done, but it turns out that it does not fix the problem.
</p>
TicketSimonKingMon, 21 Oct 2013 15:33:36 GMT
https://trac.sagemath.org/ticket/15303#comment:38
https://trac.sagemath.org/ticket/15303#comment:38
<p>
I found that the example above has the following structure:
</p>
<ul><li>We have parents <code>A</code> and <code>B</code>. We search a coercion <code>A -> B</code>.
</li><li><code>B</code> stores coercions (for backtracking) from parents <code>C</code> and <code>D</code>. Only <code>C</code> is registered by <code>B.register_coercion(...)</code>, whereas the coercion from <code>D</code> was registered in a different way, <em>after</em> initialisation of <code>B</code>.
</li><li>There is a coercion <code>phi</code> from <code>A</code> to <code>C</code> and a coercion <code>psi</code> from <code>A</code> to <code>D</code>. Sage knows that <code>phi</code> and <code>psi</code> exist. However, calling <code>psi</code> internally relies on a coercion from <code>A</code> to <code>B</code>.
</li><li>The coercion from <code>A</code> to <code>B</code> <strong>must</strong> go via <code>C</code>, starting with <code>phi</code>. Otherwise, if one tries to coerce <code>A</code> via <code>D</code> into <code>B</code>, calling <code>psi</code> (as part of a composite coerce map) will result in an infinite recursion.
</li></ul><p>
<span class="underline">Problem with the current commits</span>
</p>
<p>
It currently depends on a random choice whether the backtracking algorithm first goes back from <code>B</code> to <code>C</code> (and finds a good coerce map from <code>A</code>) or from <code>B</code> to <code>D</code> (and finds a map from <code>A</code> that crashes).
</p>
<p>
We need to give a hint to the coercion system that it should try <code>C</code> first. In vanilla Sage, this is easy, because the registered coercions are in a list, and the maps registered first are chosen first. But with my current patch, all registered coercions and coerce embeddings are stored in a <code>MonoDict</code>. Hence, the order of registration has no implication on the order of execution.
</p>
<p>
<span class="underline">Suggested solution</span>
</p>
<p>
This brings me back to the idea to keep a <strong>list</strong> of registered coercions, that would automatically keep the domain of registered coercions alive, and a <code>MonoDict</code> of other coercions used for backtracking (e.g. registered embeddings), whose domains are not necessarily kept alive.
</p>
<p>
In discover_coercion, we would then first consider the registered coercions, and only if their study is complete would the backtracking turn towards the other coercions.
</p>
<p>
<span class="underline">Perhaps useful</span>
</p>
<p>
We have <code>self.register_coercion(mor)</code>, that adds a coercion to the <em>list</em> of coercions that the backtracking algorithm is starting with. In addition, we might have a method <code>self.additional_coercion(mor)</code>, that will put <code>mor</code> only in the <code>MonoDict</code> of coercions that the backtracking algorithm is considering only later.
</p>
<p>
Would this be useful? If "yes", what lifetime implications do we want? Shall the domain of an "additional coercion" be kept alive?
</p>
TicketnbruinMon, 21 Oct 2013 16:01:01 GMT
https://trac.sagemath.org/ticket/15303#comment:39
https://trac.sagemath.org/ticket/15303#comment:39
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:38" title="Comment 38">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I found that the example above has the following structure:
</p>
<ul><li>We have parents <code>A</code> and <code>B</code>. We search a coercion <code>A -> B</code>.
</li><li><code>B</code> stores coercions (for backtracking) from parents <code>C</code> and <code>D</code>. Only <code>C</code> is registered by <code>B.register_coercion(...)</code>, whereas the coercion from <code>D</code> was registered in a different way, <em>after</em> initialisation of <code>B</code>.
</li><li>There is a coercion <code>phi</code> from <code>A</code> to <code>C</code> and a coercion <code>psi</code> from <code>A</code> to <code>D</code>. Sage knows that <code>phi</code> and <code>psi</code> exist. However, calling <code>psi</code> internally relies on a coercion from <code>A</code> to <code>B</code>.
</li><li>The coercion from <code>A</code> to <code>B</code> <strong>must</strong> go via <code>C</code>, starting with <code>phi</code>. Otherwise, if one tries to coerce <code>A</code> via <code>D</code> into <code>B</code>, calling <code>psi</code> (as part of a composite coerce map) will result in an infinite recursion.
</li></ul></blockquote>
<p>
It may well be that you can hide the problem by enforcing some lookup order, but you'd be introducing data (in this case list order) that is not part of our model. Hence, you'll end up relying on essentially unspecified (well, implementation-specified) behaviour. That makes it very hard to reason about how the system should behave and hence to determine (in the future) whether something is a bug. It may well be (in the end) that enforcing a lookup order turns out to be required to keep performance, but it would probably be preferable to find a better solution.
</p>
<p>
As you observe, the coercion A->D is in actuality derived from A->B, but apparently not by a straightforward composition. However, doesn't that mean that if A->D is discovered, then A->B must be discovered already? If A->D relies on A->B, I think part of registering A->D is ensuring that A->B is discovered.
</p>
<p>
Since it seems we need a tie-breaker for multiple paths anyway, and there is a cost system (which I think was primarily introduced for pushout construction!), it is then just a matter of ensuring that the cost of A->D is higher than the cost of A->B. Then anything that can be done from A and then via B or D will prefer the direct path A->B.
</p>
<p>
So it seems to me that the "theoretically" better solution (which may be prohibitive cost-wise!) would be:
</p>
<ul><li>recalibrate some of the costs
</li><li>take the costs properly into account
</li><li>probably do so via breadth-first (for finding shortest path, it allows much better pruning)
</li></ul><p>
I think that should solve the A->D problem as well.
</p>
TicketSimonKingMon, 21 Oct 2013 17:14:13 GMT
https://trac.sagemath.org/ticket/15303#comment:40
https://trac.sagemath.org/ticket/15303#comment:40
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:39" title="Comment 39">nbruin</a>:
</p>
<blockquote class="citation">
<p>
It may well be that you can hide the problem by enforcing some lookup order, but you'd be introducing data (in this case list order) that is not part of our model.
</p>
</blockquote>
<p>
How to formulate a model that takes into account dependencies between arrows of a digraph? In particular between arrows that may not even be adjacent?
</p>
<blockquote class="citation">
<p>
As you observe, the coercion A->D is in actuality derived from A->B, but apparently not by a straightforward composition.
</p>
</blockquote>
<p>
Correct. When calling the coercion A->D, some arithmetic is performed on underlying data, this involves coercion, and this is when A->B occurs.
</p>
<blockquote class="citation">
<p>
However, doesn't that mean that if A->D is discovered, then A->B must be discovered already?
</p>
</blockquote>
<p>
No. You can easily define a map and then compose with other maps, without calling it. A->B is only needed for <strong>calling</strong> A->D, but not for <strong>definining</strong> A->D.
</p>
<blockquote class="citation">
<p>
If A->D relies on A->B, I think part of registering A->D is ensuring that A->B is discovered.
</p>
</blockquote>
<p>
Yes, and how to model this?
</p>
<blockquote class="citation">
<p>
Since it seems we need a tie-breaker for multiple paths anyway, and there is a cost system (which I think was primarily introduced for pushout construction!), it is then just a matter of ensuring that the cost of A->D is higher than the cost of A->B. Then anything that can be done from A and then via B or D will prefer the direct path A->B.
</p>
</blockquote>
<p>
... but only if, in addition, we actually use the coerce costs in <code>discover_coercion()</code>, rather then returning the first map that came across.
</p>
<blockquote class="citation">
<p>
So it seems to me that the "theoretically" better solution (which may be prohibitive cost-wise!) would be:
</p>
<ul><li>recalibrate some of the costs
</li><li>take the costs properly into account
</li><li>probably do so via breadth-first (for finding shortest path, it allows much better pruning)
</li></ul><p>
I think that should solve the A->D problem as well.
</p>
</blockquote>
<p>
Perhaps.
</p>
<ul><li>Breadth first search might be a good idea. I don't know how to efficiently implement it, but I guess this should be done at some point.
</li><li>Calibrating the costs, such that <code>A->C->B</code> is guaranteed to have less cost than <code>A->D->B</code> for any example in which <code>A->C</code> is independent of but <code>A->D</code> is dependent on <code>A->B</code>, requires a case-by-case analysis. Not very practical, and moreover choosing parameters such that "it works" is kind of arbitrary. This is not a very clean solution either.
</li></ul><p>
Before we have implemented breadth first search, I believe it would be more practical to say that we should
</p>
<ul><li>give preference to maps registered during initialisation (<code>P.register_coercion(mor)</code>)
</li><li>give less preference to maps registered after initialisation (<code>mor.register_as_coercion()</code>)
</li><li>give least preference to registered embeddings (I am talking about backtracking here, not pushout).
</li></ul><p>
This is practical because this approach is close to what is done in vanilla Sage. The current registration order is such that "it works".
</p>
TicketnbruinMon, 21 Oct 2013 17:48:00 GMT
https://trac.sagemath.org/ticket/15303#comment:41
https://trac.sagemath.org/ticket/15303#comment:41
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:40" title="Comment 40">SimonKing</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
If A->D relies on A->B, I think part of registering A->D is ensuring that A->B is discovered.
</p>
</blockquote>
<p>
Yes, and how to model this?
</p>
</blockquote>
<p>
In this case it could just be done by explicitly asking the system to discover A->B before installing A->D. However, proper cost accounting shouldn't require discovery order to matter at all.
</p>
<blockquote class="citation">
<ul><li>Breadth first search might be a good idea. I don't know how to efficiently implement it, but I guess this should be done at some point.
</li></ul></blockquote>
<p>
Just keep track of all discovered shortest paths (ordered by domain) into the codomain, and try to extend the shortest path. Merge the new-found paths (only store them if you found a shorter path or a path from a new domain). As soon as you found a path from the required domain, prune by cost (you only need to store paths that could possibly lead to a cheaper path). Continue until all paths you have stored have been examined (and further path is longer than what you've found). The expensive part is still determining there is NO path, because no pruning can occur then.
</p>
<blockquote class="citation">
<ul><li>Calibrating the costs, such that <code>A->C->B</code> is guaranteed to have less cost than <code>A->D->B</code> for any example in which <code>A->C</code> is independent of but <code>A->D</code> is dependent on <code>A->B</code>, requires a case-by-case analysis. Not very practical, and moreover choosing parameters such that "it works" is kind of arbitrary. This is not a very clean solution either.
</li></ul></blockquote>
<p>
That is right, but it's not a very clean problem either. You need something to distinguish A->C->B from A->D->B. The only place where we have enough information to insert this data is when we define A->D. Since that coercion requires A->B, you could encode its cost to be cost(A->B) + <something>. This is basically what path composition would do for you normally. Since A->D is derived from A->B, you'll have to insert that information in some other way.
</p>
<blockquote class="citation">
<p>
This is practical because this approach is close to what is done in vanilla Sage. The current registration order is such that "it works".
</p>
</blockquote>
<p>
If you want a practical solution, I think leaving the status quo for now is the most practical. It's working now. Remember that the issue in the ticket has not occurred in a practical example (yet). The main purpose of this ticket as I see it is to document that we are not implementing the model we think we're implementing. Changing it to another implementation that also doesn't behave as our model isn't necessarily progress. It only is if we're getting desired behaviour in a case that actually matters.
</p>
<blockquote class="citation">
<p>
The current registration order is such that "it works".
</p>
</blockquote>
<p>
Hm, that may be backwards. Sage currently works because it's built with the coercion discovery as it is at the moment. Patches wouldn't have made it in if they didn't work (this is certainly true for doctest examples. There can be other examples (future bug reports) out there that may fail.
</p>
<p>
We can of course try to rationalize the current model. It seems to me we may be borrowing from the fact that the time line has no cycles (basically the arrow of causality), so preferring maps that were put in "earlier" should tend to not depend on later inserted maps.
</p>
<p>
Of course, this flies in the face of the model we're claiming to implement: Properties of a digraph don't rely on the history of the digraph. They only rely on the state of the graph.
</p>
<p>
If you want a history-sensitive graph, you could put as cost of the edge the insertion time of the edge, and use the maximum over a path as the cost of the path. Do you think that's a reasonable model?
</p>
TicketSimonKingMon, 21 Oct 2013 17:49:50 GMT
https://trac.sagemath.org/ticket/15303#comment:42
https://trac.sagemath.org/ticket/15303#comment:42
<p>
Sidenote: I tried to make it so that the registered coercions are studied first, in backtracking. It seems that it did fix the failing example above. However, further recursion errors remain.
</p>
TicketSimonKingMon, 21 Oct 2013 20:24:20 GMT
https://trac.sagemath.org/ticket/15303#comment:43
https://trac.sagemath.org/ticket/15303#comment:43
<p>
I think the attached branch <em>is</em> a progress towards a coercion system with a cleaner model. Even if there would remain rough edges.
</p>
<p>
My strategy: I'll try to analyse the remaining recursion errors, since this is likely to point us to fundamental flows. In the best case, the analysis will result in a better (formulation of) the model.
</p>
<p>
Currently, I am studying the following very simple example:
</p>
<pre class="wiki">sage: L.<i> = NumberField(x^2 + 1); L
Number Field in i with defining polynomial x^2 + 1
sage: K, from_K, to_K = L.change_generator(i/2 + 3)
<Recursion boom>
</pre>
TicketSimonKingMon, 21 Oct 2013 20:30:43 GMT
https://trac.sagemath.org/ticket/15303#comment:44
https://trac.sagemath.org/ticket/15303#comment:44
<p>
Shorter:
</p>
<pre class="wiki">sage: L.<i> = NumberField(x^2 + 1)
sage: K = NumberField(L(i/2+3).minpoly(), names=('i0',), embedding=L(i/2+3))
</pre>
TicketSimonKingMon, 21 Oct 2013 22:24:19 GMT
https://trac.sagemath.org/ticket/15303#comment:45
https://trac.sagemath.org/ticket/15303#comment:45
<p>
I wonder: Do we really insist on making the example from the ticket description work?
</p>
<p>
There are typical parents (e.g., CC) that have numerous registered coerce embeddings from other parents (e.g., from number fields). If we try to find a coercion from P into CC, it would normally not help to first search for a coercion from P into a number field instead.
</p>
<p>
So, perhaps we could say that registered embeddings should be ignored in backtracking (as they are now). If one wants something like the example from the ticket description, one should <em>not</em> use <code>.register_embedding()</code>, but do something like this:
</p>
<pre class="wiki">C.coerce_map_from(B) # returns None, since we have no A yet
A.register_coercion(BtoA)
AtoC.register_as_coercion() # should increase the cache version number according to the Lemma
C.coerce_map_from(B) # now returns a coercion via A, because the cached absence of a coercion
# will be ignored after the increment of the version number
</pre><p>
Do you agree on this change of aim?
</p>
TicketnbruinMon, 21 Oct 2013 22:43:08 GMT
https://trac.sagemath.org/ticket/15303#comment:46
https://trac.sagemath.org/ticket/15303#comment:46
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:45" title="Comment 45">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I wonder: Do we really insist on making the example from the ticket description work?
</p>
<p>
There are typical parents (e.g., CC) that have numerous registered coerce embeddings from other parents (e.g., from number fields). If we try to find a coercion from P into CC, it would normally not help to first search for a coercion from P into a number field instead.
</p>
</blockquote>
<p>
Ah right, you're saying there are certain "almost universal terminal" objects that tend to have a very large in-degree. Doing backtracking from them would be a rather expensive operation (independent of whether it's breadth-first (cheapest-first is a better name) or depth-first). So we mandate that any paths that would involve such a map should be explicitly offered, so that backtracking is not necessary for discovering paths that use it. That could make sense. In order for such a model to be usable, you'd have to write clear documentation/helper routines to ensure that the right maps are put in. What if discovery is needed in the process of finding coercions between polynomial rings/function fields/algebraic groups over certain bases etc? Can we write down rules that make for a transparent and usable model?
</p>
<blockquote class="citation">
<p>
So, perhaps we could say that registered embeddings should be ignored in backtracking (as they are now). If one wants something like the example from the ticket description, one should <em>not</em> use <code>.register_embedding()</code>, but do something like this:
</p>
<pre class="wiki">C.coerce_map_from(B) # returns None, since we have no A yet
A.register_coercion(BtoA)
AtoC.register_as_coercion() # should increase the cache version number according to the Lemma
C.coerce_map_from(B) # now returns a coercion via A, because the cached absence of a coercion
# will be ignored after the increment of the version number
</pre></blockquote>
<p>
Hm, where does <code>AtoC.register_as_coercion()</code> fit in with the "only initialize coercions upon <code>__init__</code> of the parent"?
</p>
<blockquote class="citation">
<p>
Do you agree on this change of aim?
</p>
</blockquote>
<p>
Well, I think what you're saying is that under certain conditions we require that the graph is fed more than just the backbone. Instead of relying on the coercion system to discover the full transitive closure, we mandate that the graph as offered should already be transitively closed in some aspects. If you can make those aspects clear and workable, I guess that could be a solution too.
</p>
TicketSimonKingTue, 22 Oct 2013 09:06:34 GMT
https://trac.sagemath.org/ticket/15303#comment:47
https://trac.sagemath.org/ticket/15303#comment:47
<p>
Hi!
</p>
<p>
First of all, note that the latest recursion errors refer to not-yet-committed code. It could be that by copy-and-pasting I somehow destroyed the backtracking algorithm by not properly marking a used arrow as not-to-be-tested-again. Thus the recursion.
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:46" title="Comment 46">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Hm, where does <code>AtoC.register_as_coercion()</code> fit in with the "only initialize coercions upon <code>__init__</code> of the parent"?
</p>
</blockquote>
<p>
Both <code>AtoC.register_as_coercion()</code> and <code>A.register_embedding(AtoC)</code> add an arrow to the coerce digraph <em>after</em> initialisation of C. With regard to the above lemma, one should only cache the absence of a coercion until an arrow is inserted with a previously existing codomain. Hence, in both cases we need to increase the cache version number.
</p>
TicketSimonKingTue, 22 Oct 2013 09:09:39 GMT
https://trac.sagemath.org/ticket/15303#comment:48
https://trac.sagemath.org/ticket/15303#comment:48
<p>
OUCH!!
</p>
<p>
I just found that <code>discover_coerce_map_from</code> did not mark arrows as "used" at all! Hence, there is (another) bug in our backtracking algorithm.
</p>
TicketSimonKingTue, 22 Oct 2013 10:42:13 GMTwork_issues changed
https://trac.sagemath.org/ticket/15303#comment:49
https://trac.sagemath.org/ticket/15303#comment:49
<ul>
<li><strong>work_issues</strong>
changed from <em>Analyse recursion error</em> to <em>Implement backtracking properly</em>
</li>
</ul>
<p>
In <a class="closed ticket" href="https://trac.sagemath.org/ticket/12969" title="defect: Coercion failures in symmetric functions (closed: fixed)">#12969</a>, I fixed the backtracking algorithm for the discovery of actions. There, the problem was that the absence of an action was cached in the middle of backtracking, i.e., even though some paths were <em>temporarily</em> forbidden, so that an action was easily found after allowing the paths again.
</p>
<p>
In the case of coerce maps, the backtracking algorithm is not properly implemented either. Namely, paths that have already been visited are not marked as "forbidden". I think this is a severe bug. It is amazing that it didn't show up before. In any case, it <em>must</em> be implemented here, since otherwise we will hardly be able to add the feature that this ticket is about.
</p>
TicketSimonKingTue, 22 Oct 2013 10:49:53 GMT
https://trac.sagemath.org/ticket/15303#comment:50
https://trac.sagemath.org/ticket/15303#comment:50
<p>
Oops, I spoke too soon. <a class="closed ticket" href="https://trac.sagemath.org/ticket/12969" title="defect: Coercion failures in symmetric functions (closed: fixed)">#12969</a> was in fact about backtracking for coerce maps (not for actions), and forbidden paths are in fact declared (<code>_register_pair(self, S,"coerce")</code>) if <code>discover_coerce_map_from()</code> is called by <code>coerce_map_from()</code>.
</p>
<p>
That said, I wonder if the whole registration business couldn't be done more efficiently. For example, the construction of coercions are thoroughly based on the comparison of parents by identity (this even holds for non-unique parents). Hence, <code>_register_pair</code> should be rewritten as well, so that only identity and not equality counts. That's for a different ticket.
</p>
TicketSimonKingTue, 22 Oct 2013 11:05:19 GMT
https://trac.sagemath.org/ticket/15303#comment:51
https://trac.sagemath.org/ticket/15303#comment:51
<p>
I think I have located the problem: If the pair <code>X,Y</code> already is registered and we do <code>X.coerce_map_from(Y)</code>, then <code>None</code> should be returned (but of course not cached). But currently it is still attempted to find a coercion from <code>Y</code> to <code>X</code>, resulting in an infinite loop.
</p>
TicketSimonKingTue, 22 Oct 2013 14:02:29 GMT
https://trac.sagemath.org/ticket/15303#comment:52
https://trac.sagemath.org/ticket/15303#comment:52
<p>
As it turns out, the recursion again occurs when <em>calling</em> (not when <em>constructing</em>!) a coerce map. Nevertheless, I think one should speed-up the backtracking based on comparison by identity. Perhaps one could even use a <code>TripleDict</code> for storage of temporarily forbidden paths.
</p>
<p>
The problematic map is a <code>DefaultConvertMap_unique</code>, and this could explain why the problem arose now: In vanilla Sage, this kind of maps is only returned if the backtracking finds nothing better.
</p>
<p>
But in one of my commits, I made sure that the backtracking is not attempted if <code>self._coerce_map_from_(S)</code> returns <code>True</code> or returns an actual map. The rationale for this change was that <code>self._coerce_map_from_(S)</code> is an answer given by a specific object and should just be preferred over an answer given by a general backtracking algorithm. As it turns out, Sage relies on the assumption that backtracking usually is better.
</p>
<p>
In other words: In vanilla Sage, dependencies between arrows of the coerce digraph are implicitly declared by
</p>
<ul><li>choosing an order of registered coercions
</li><li>avoiding <code>DefaultConverMap</code> and friends.
</li></ul><p>
I am not happy about the existing way of implicit declaration of dependencies and think we should do better!
</p>
TicketSimonKingTue, 22 Oct 2013 15:18:30 GMT
https://trac.sagemath.org/ticket/15303#comment:53
https://trac.sagemath.org/ticket/15303#comment:53
<p>
I think the following is both reasonable and reasonably close to the status quo:
</p>
<ul><li>if <code>_coerce_map_from_</code> returns a map, then we trust that it is a good choice.
</li><li>if <code>_coerce_map_from_</code> returns True, then we do not necessarily trust that <code>self._generic_convert_map(S)</code> is the best choice. So, we test if backtracking yields anything better.
</li></ul><p>
I found a couple of cases in which <code>_coerce_map_from_</code> returned <code>_generic_convert_map</code> (e.g. for <code>CC</code>!). It seems to me that one should return <code>True</code> instead.
</p>
TicketnbruinTue, 22 Oct 2013 15:44:15 GMT
https://trac.sagemath.org/ticket/15303#comment:54
https://trac.sagemath.org/ticket/15303#comment:54
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:53" title="Comment 53">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I think the following is both reasonable and reasonably close to the status quo:
</p>
<ul><li>if <code>_coerce_map_from_</code> returns a map, then we trust that it is a good choice.
</li><li>if <code>_coerce_map_from_</code> returns True, then we do not necessarily trust that <code>self._generic_convert_map(S)</code> is the best choice. So, we test if backtracking yields anything better.
</li></ul></blockquote>
<p>
Can we explain these rules purely in terms of the coercion graph? Does <code>_coerce_map_from_(..)==True</code> somehow indicate an edge with a property (colour?) that should be avoided or an edge with the cost modified (increased)? If the graph version is increased, do we invalidate paths with a bad colour as well, because now there might be one with a better colour? (OK, we can't call this property colour, obviously. That's just going to be too politically incorrect).
</p>
<p>
My hunch is that the undesirability of a certain edge can simply be expressed in its cost and that we only need a 1-dimensional cost parameter to capture all that we need [we'd have to think about calibration, though].
</p>
<p>
Above, you also talk about "forbidden" and "temporarily forbidden" paths. Are those part of the depth-first path discovery? That would be an even better reason to see if we can get a "cheapest first" search in, since that naturally avoids cycles.
</p>
TicketSimonKingThu, 24 Oct 2013 12:02:44 GMT
https://trac.sagemath.org/ticket/15303#comment:55
https://trac.sagemath.org/ticket/15303#comment:55
<p>
Good(?) news: I can track down the error to the following <em>in vanilla Sage</em>.
</p>
<pre class="wiki">sage: L.<i> = NumberField(x^2 + 1)
sage: K = NumberField(L(i/2+3).minpoly(), names=('i0',), embedding=L(i/2+3))
sage: from sage.rings.number_field import number_field_morphisms
sage: number_field_morphisms.EmbeddedNumberFieldMorphism(R, self)
Traceback (most recent call last):
...
RuntimeError: maximum recursion depth exceeded in __instancecheck__
</pre><p>
The point is that the <em>with my patch</em>, the above code is executed during construction of K, in order to internally construct something. I'll ask on sage-nt whether this code <em>should</em> give a map. I guess it should not, but perhaps the number theorists disagree. And if it should not give a map, then there should be a <code>TypeError</code> (or <code>ValueError</code>) raised, without infinite recursion.
</p>
TicketjpfloriThu, 24 Oct 2013 13:14:52 GMTcc changed
https://trac.sagemath.org/ticket/15303#comment:56
https://trac.sagemath.org/ticket/15303#comment:56
<ul>
<li><strong>cc</strong>
<em>jpflori</em> added
</li>
</ul>
TicketjpfloriThu, 24 Oct 2013 13:55:37 GMT
https://trac.sagemath.org/ticket/15303#comment:57
https://trac.sagemath.org/ticket/15303#comment:57
<p>
Great work, all of this looks really fine.
</p>
TicketSimonKingThu, 24 Oct 2013 14:36:36 GMT
https://trac.sagemath.org/ticket/15303#comment:58
https://trac.sagemath.org/ticket/15303#comment:58
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:54" title="Comment 54">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Above, you also talk about "forbidden" and "temporarily forbidden" paths. Are those part of the depth-first path discovery?
</p>
</blockquote>
<p>
Of course. By "temporarily forbidden", I mean those that have already been visited in the depth-first search and shall thus not be visited again during the same search. Thus "temporarily", because in the next search they could be visited.
</p>
<blockquote class="citation">
<p>
That would be an even better reason to see if we can get a "cheapest first" search in, since that naturally avoids cycles.
</p>
</blockquote>
<p>
How would that be?
</p>
<p>
Also note that if you want to compare costs, you need to construct the maps. It could become very costly, if you want to compare many paths.
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:53" title="Comment 53">SimonKing</a>:
Can we explain these rules purely in terms of the coercion graph?
</p>
</blockquote>
<p>
Somehow (see below).
</p>
<blockquote class="citation">
<p>
Does <code>_coerce_map_from_(..)==True</code> somehow indicate an edge with a property (colour?) that should be avoided or an edge with the cost modified (increased)?
</p>
</blockquote>
<p>
Not at all. <code>_coerce_map_from_</code> is only called if there is no edge. Note that "long time ago" (in one of the posts above) I talked about "short-cuts" in the coerce digraph. <code>_coerce_map_from_</code> is for the shortcuts, not for the edges.
</p>
<p>
So, in terms of the coerce digraph: We have a digraph with some connected components X,Y. It is possible that there is a coercion from a node x in X to a node y in Y; this is the case of <code>y._coerce_map_from_(x)</code> returns True or returns a map. However, this does not mean that an edge is inserted that would connect X and Y: The two components remain separate, and a reference to any node in Y does not prevent the whole component X from garbage collection.
</p>
<p>
This situation is easy. Difficulties only arise if x and y belong to <em>the same</em> component X. In this situation, we may have several possibilities to construct a map from x to y: There could be different paths in X, and there could be a map provided by <code>y._coerce_map_from_(x)</code>, or <code>y._coerce_map_from_(x)</code> returns True. In the latter case, it means that we can use <code>y._generic_convert_map(x)</code> for coercion.
</p>
<p>
Which of these maps to choose? It is required that these maps are mathematically the same. So, our choice can not be based on the maths only.
</p>
TicketnbruinThu, 24 Oct 2013 16:10:07 GMT
https://trac.sagemath.org/ticket/15303#comment:59
https://trac.sagemath.org/ticket/15303#comment:59
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:58" title="Comment 58">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Also note that if you want to compare costs, you need to construct the maps. It could become very costly, if you want to compare many paths.
</p>
</blockquote>
<p>
Well, you could hold off on actually creating the map composition until you've determined the lowest cost path. However, I think we have bigger problems to solve before we could contemplate doing this.
</p>
<blockquote class="citation">
<p>
So, in terms of the coerce digraph: We have a digraph with some connected components X,Y. It is possible that there is a coercion from a node x in X to a node y in Y; this is the case of <code>y._coerce_map_from_(x)</code> returns True or returns a map. However, this does not mean that an edge is inserted that would connect X and Y: The two components remain separate, and a reference to any node in Y does not prevent the whole component X from garbage collection.
</p>
<p>
This situation is easy. Difficulties only arise if x and y belong to <em>the same</em> component X. In this situation, we may have several possibilities to construct a map from x to y: There could be different paths in X, and there could be a map provided by <code>y._coerce_map_from_(x)</code>, or <code>y._coerce_map_from_(x)</code> returns True. In the latter case, it means that we can use <code>y._generic_convert_map(x)</code> for coercion.
</p>
</blockquote>
<p>
(nitpick: I don't think we want to talk about "connected components" if we're considering a digraph. Perhaps we should say y is "reachable" from x).
</p>
<p>
If <code>y._coerce_map_from_(x)</code> can return "true" or a map if the coercion graph otherwise doesn't have a path from x to y then the current coercion model is significantly different from the digraph model we're talking about. If we have a coercion path X->Z->Y where the coercion from Y to Z can only be found using <code>_coerce_map_from_</code> then we cannot discover the coercion from X to Y (how would we know to involve Z?) but we can discover the coercions X->Z and Z->Y. So we're fundamentally breaking transitivity already.
</p>
<p>
Perhaps one way out is if <code>_coerce_map_from_</code> indeed only returns "shortcuts": paths between nodes that exist otherwise, so only in the situation you describe as "Difficult".
</p>
<p>
If we cannot trust that the return map from <code>_coerce_map_from_</code> (either explicitly, or the implied conversion) is the best possible, then there's no use in having it return anything: we'd have to investigate the rest of the coercion graph anyway.
</p>
<p>
I agree that relying on conversion maps in the coercion framework looks very suspect: conversions are supposed to be trying coercion first!
</p>
<p>
So it seems to me that _coerce_map_from_ returning True should perhaps be abolished entirely and that in other cases one should be very careful with implementing _coerce_map_from_. It can certainly not be the only coercion hook one provides if we want to have a digraph model.
</p>
TicketnbruinThu, 24 Oct 2013 16:24:52 GMT
https://trac.sagemath.org/ticket/15303#comment:60
https://trac.sagemath.org/ticket/15303#comment:60
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:55" title="Comment 55">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Good(?) news: I can track down the error to the following <em>in vanilla Sage</em>.
</p>
<pre class="wiki">sage: L.<i> = NumberField(x^2 + 1)
sage: K = NumberField(L(i/2+3).minpoly(), names=('i0',), embedding=L(i/2+3))
sage: from sage.rings.number_field import number_field_morphisms
sage: number_field_morphisms.EmbeddedNumberFieldMorphism(R, self)
Traceback (most recent call last):
...
RuntimeError: maximum recursion depth exceeded in __instancecheck__
</pre><p>
The point is that the <em>with my patch</em>, the above code is executed during construction of K, in order to internally construct something. I'll ask on sage-nt whether this code <em>should</em> give a map. I guess it should not, but perhaps the number theorists disagree. And if it should not give a map, then there should be a <code>TypeError</code> (or <code>ValueError</code>) raised, without infinite recursion.
</p>
</blockquote>
<p>
I suppose you mean
</p>
<pre class="wiki">sage: number_field_morphisms.EmbeddedNumberFieldMorphism(K,L)
</pre><p>
According to the documentation it shouldn't because by default it tries to see if K and L are both naturally embedded in CC, and they are not.
</p>
<p>
The following already does work:
</p>
<pre class="wiki">sage: number_field_morphisms.EmbeddedNumberFieldMorphism(K,L,L) #any combination of K and L
Generic morphism:
From: Number Field in i0 with defining polynomial x^2 - 6*x + 37/4
To: Number Field in i with defining polynomial x^2 + 1
Defn: i0 -> 1/2*i + 3
sage: number_field_morphisms.EmbeddedNumberFieldMorphism(L,L)
Generic endomorphism of Number Field in i with defining polynomial x^2 + 1
Defn: i -> i
</pre><p>
The latter suggests that the routine does take some liberties. For K we get
</p>
<pre class="wiki">sage: number_field_morphisms.EmbeddedNumberFieldMorphism(K,K)
RuntimeError: maximum recursion depth exceeded while calling a Python object
</pre><p>
so the difference in behaviour between L and K seems dodgy.
</p>
TicketSimonKingThu, 24 Oct 2013 19:11:38 GMT
https://trac.sagemath.org/ticket/15303#comment:61
https://trac.sagemath.org/ticket/15303#comment:61
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:59" title="Comment 59">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Well, you could hold off on actually creating the map composition until you've determined the lowest cost path.
</p>
</blockquote>
<p>
No, because <code>K._coerce_map_from_(L)</code> gives you shortcuts. It may very well be that it returns a map that is <em>much</em> "cheaper" then a composition of registered coercions and registered embeddings leading from L to K.
</p>
<p>
And note that these shortcuts will also arise during backtracking. Namely, if K has registered coercions from R1,...,Rn, then the backtracking will involve to ask <code>R1._coerce_map_from_(L)</code>, ..., <code>Rn._coerce_map_from_(L)</code> for shortcuts.
</p>
<p>
Hence, it is not enough to assign costs to arrows in the digraph.
</p>
<blockquote class="citation">
<p>
(nitpick: I don't think we want to talk about "connected components" if we're considering a digraph. Perhaps we should say y is "reachable" from x).
</p>
</blockquote>
<p>
Correct.
</p>
<blockquote class="citation">
<p>
If <code>y._coerce_map_from_(x)</code> can return "true" or a map if the coercion graph otherwise doesn't have a path from x to y then the current coercion model is significantly different from the digraph model we're talking about.
</p>
</blockquote>
<p>
No. This is exactly the digraph-with-shortcuts model I kept talking about since comment 84 of <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a> (hence, since 3 weeks). Since then, I used the term "digraph model" only as an abbreviation of the lengthy term "digraph-with-shortcuts model".
</p>
<blockquote class="citation">
<p>
If we have a coercion path X->Z->Y where the coercion from Y to Z can only be found using <code>_coerce_map_from_</code>
</p>
</blockquote>
<p>
You mean from Z to Y?
</p>
<blockquote class="citation">
<p>
then we cannot discover the coercion from X to Y (how would we know to involve Z?) but we can discover the coercions X->Z and Z->Y. So we're fundamentally breaking transitivity already.
</p>
</blockquote>
<p>
Yes, which is part of the specification of the digraph-with-shortcuts model.
</p>
<p>
That said: We now have version numbers of the coerce digraph. Hence, caching the absence of a coercion would no longer be a problem, and I could imagine that by now it would be possible to turn a short-cut Z->Y into an actual arrow of the digraph.
</p>
<p>
However, I could also imagine that this would have two disadvantages:
</p>
<ol><li>It would depend on the command history whether Sage would find a coercion from X to Y (via Z) or not. Arguably, it would be better than the status quo, which is "we won't find a coercion from X to Y via Z, even if we know that Z exists and has a coercion into Y".
</li><li>The list of maps-to-be-considered in the backtracking algorithm grew. Hence, it would increase the running time for detecting a coerce map.
</li></ol><blockquote class="citation">
<p>
Perhaps one way out is if <code>_coerce_map_from_</code> indeed only returns "shortcuts": paths between nodes that exist otherwise, so only in the situation you describe as "Difficult".
</p>
</blockquote>
<p>
I don't understand what you mean by this.
</p>
<p>
In vanilla Sage, <code>_coerce_map_from_</code> does return nothing but "shortcuts" (i.e., things that the backtracking algorithm does not know about). It does so both in the easy situation and in the difficult situation. The easy situation is if the backtracking algorithm finds no path, hence, the shortcut is the only option, hence, we don't have the burden of choosing something (therefore the situation is "easy").
</p>
<blockquote class="citation">
<p>
If we cannot trust that the return map from <code>_coerce_map_from_</code> (either explicitly, or the implied conversion) is the best possible, then there's no use in having it return anything: we'd have to investigate the rest of the coercion graph anyway.
</p>
</blockquote>
<p>
I think I have already described what is currently done:
</p>
<ol><li>It is tested whether there is a short-cut phi (either explicitly or implicitly).
</li><li>Even if phi is found, backtracking is performed. Backtracking "goes back" according to the registered coercions, and may involve short-cuts by recursion. Let's call psi the first map found by backtracking (if there is any).
</li><li>If both phi and psi are available, then return the less costly. If only one of them is available, return it. Otherwise, there is no coercion.
</li></ol><p>
My current commits (at least those I have at home) change it as follows
</p>
<ul><li>If <code>_coerce_map_from_</code> explicitly returns an actual map, then the backtracking search is <em>not</em> performed, but it is trusted that the map is good to be used.
</li><li>If <code>_coerce_map_from_</code> returns True, then it says <em>implicitly</em> that <code>_generic_convert_map</code> could in principle be used for coercion, but there might be better options. Hence, similar to vanilla Sage, my branch would do a backtracking and return the less costly map.
</li><li>Registered <em>embeddings</em> are used for backtracking, too, whereas vanilla Sage only uses registered coercions.
</li></ul><p>
We might play with the idea of extending the last point, namely: Turn the short-cuts into permanent arrows, to be used by backtracking. But then we need to take care of lifetime implications, and we need to take care of a potential slow-down of the backtracking.
</p>
<blockquote class="citation">
<p>
I agree that relying on conversion maps in the coercion framework looks very suspect: conversions are supposed to be trying coercion first!
</p>
</blockquote>
<p>
I did not state that it looks suspect. Hence, we don't agree. Saying "we use conversion as coercion" is just short for "we take the map that is returned by <code>_generic_convert_map</code>, cache this map in <code>_coerce_from_cache</code>, and henceforth use this map for coercion (and of course for conversion, too)".
</p>
<blockquote class="citation">
<p>
So it seems to me that _coerce_map_from_ returning True should perhaps be abolished entirely and that in other cases one should be very careful with implementing _coerce_map_from_.
</p>
</blockquote>
<p>
I disagree.
</p>
<blockquote class="citation">
<p>
It can certainly not be the only coercion hook one provides if we want to have a digraph model.
</p>
</blockquote>
<p>
If we want to keep the current digraph-with-shortcuts model, then we indeed need at least two hooks: One that adds arrows to the digraph, and one that provides short-cuts. In my branch, I suggest to extend the role of registered embeddings, namely: To make them actual arrows, to be used in backtracking.
</p>
TicketnbruinThu, 24 Oct 2013 20:30:19 GMT
https://trac.sagemath.org/ticket/15303#comment:62
https://trac.sagemath.org/ticket/15303#comment:62
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:61" title="Comment 61">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
No, because <code>K._coerce_map_from_(L)</code> gives you shortcuts. It may very well be that it returns a map that is <em>much</em> "cheaper" then a composition of registered coercions and registered embeddings leading from L to K.
</p>
</blockquote>
<p>
So shouldn't the rule be: If <code>K._coerce_map_from_(L)</code> returns something then one of the following must be true
</p>
<ul><li>There is a registered coercion from L to K
</li><li>There is a registered embedding from L to K
</li><li>For any structure M that coerces into L, K._coerce_map_from_(M) also returns something.
</li></ul><p>
i.e., either the coercion system has enough information to compute transitive closures by itself or <code>_coerce_map_from_</code> ensures transitive closure by itself already.
</p>
<blockquote class="citation">
<p>
Hence, it is not enough to assign costs to arrows in the digraph.
</p>
</blockquote>
<p>
No, "shortcut" paths returned by <code>_coerce_map_from_</code> should carry a cost as well, obviously. And one would hope their cost roughly corresponds the cheapest path that can be discovered otherwise (perhaps with a small modifier to make it more attractive to use this particular path).
</p>
<p>
Aren't the "shortcuts" supposed to be an implementation detail to more efficiently implement the theoretical digraph model? In that case we can reason about their desired properties purely based on the theoretical digraph model.
</p>
<p>
If you're claiming the shortcuts are something else and deserve their own theoretical interpretation as well, I'd be interested in seeing what you mean by them.
</p>
<blockquote class="citation">
<p>
No. This is exactly the digraph-with-shortcuts model I kept talking about since comment 84 of <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a> (hence, since 3 weeks). Since then, I used the term "digraph model" only as an abbreviation of the lengthy term "digraph-with-shortcuts model".
</p>
</blockquote>
<p>
This makes me wonder what exactly the axioms of this "digraph-with-shortcuts model" is. I can see how "digraph-with-shortcuts" can be used to implement a proper digraph model more efficiently, if the shortcuts follow some rules (as stated above). If our theoretical model is "digraph-with-costs" I can see a "digraph-with-costs-and-shortcuts" implementation, where the shortcuts would obviously have to provide a cost on them too: the cost of the path they are providing the "shortcut" for (modulo little tweaks).
</p>
<blockquote class="citation">
<p>
You mean from Z to Y?
</p>
</blockquote>
<p>
Yes, sorry.
</p>
<blockquote class="citation">
<p>
Yes, which is part of the specification of the digraph-with-shortcuts model.
</p>
</blockquote>
<p>
My conclusion would be that our digraph-with-shortcuts implementation is failing to properly implement a straight digraph model.
</p>
<blockquote class="citation">
<p>
That said: We now have version numbers of the coerce digraph. Hence, caching the absence of a coercion would no longer be a problem, and I could imagine that by now it would be possible to turn a short-cut Z->Y into an actual arrow of the digraph.
</p>
</blockquote>
<p>
No, that's going to be a mess. I think the "actual arrow" would basically have to be there already (or be implied to be there by _coerce_map_from_ somehow magically ensuring that it will be returning results consistent with it).
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Perhaps one way out is if <code>_coerce_map_from_</code> indeed only returns "shortcuts": paths between nodes that exist otherwise, so only in the situation you describe as "Difficult".
</p>
</blockquote>
<p>
I don't understand what you mean by this.
</p>
</blockquote>
<p>
Hopefully my explanation above now clarifies this: In my opinion "-with-shortcuts" is an implementation detail to gain efficiency, not a part of the model, because I don't see what kind of reasonable model one would have then.
</p>
<blockquote class="citation">
<p>
I think I have already described what is currently done:
</p>
<ol><li>It is tested whether there is a short-cut phi (either explicitly or implicitly).
</li><li>Even if phi is found, backtracking is performed. Backtracking "goes back" according to the registered coercions, and may involve short-cuts by recursion. Let's call psi the first map found by backtracking (if there is any).
</li><li>If both phi and psi are available, then return the less costly. If only one of them is available, return it. Otherwise, there is no coercion.
</li></ol></blockquote>
<p>
It seems to me they are not just "shortcuts" then. It seems that an opportunity is provided to provide parts of the graph in a programmatic way. As pointed out, such a presentation is not transparent for backtracking, so if one wants to provide something that is closed under path composition, we would need that the implemented <code>_coerce_map_from_</code> ensures the closure by itself.
</p>
<p>
That means that providing coercions (just) via <code>_coerce_map_from_</code> is actually a rather difficult thing to do correctly, whereas presently I think we advertise it as the easier, almost preferred way of doing it.
</p>
<blockquote class="citation">
<p>
My current commits (at least those I have at home) change it as follows
</p>
<ul><li>If <code>_coerce_map_from_</code> explicitly returns an actual map, then the backtracking search is <em>not</em> performed, but it is trusted that the map is good to be used.
</li></ul></blockquote>
<p>
I think that's a reasonable thing to do.
</p>
<blockquote class="citation">
<ul><li>If <code>_coerce_map_from_</code> returns True, then it says <em>implicitly</em> that <code>_generic_convert_map</code> could in principle be used for coercion, but there might be better options.
</li></ul></blockquote>
<p>
A feature like that might be OK (I guess it makes it easier to reuse code, because the programming paradigm makes it a little easier to implement "conversions" (parent call) than to implement coercions directly, but "correct" use would need that map, or an equivalent one, to be available for backtracking as well, or above-described closed property of <code>_coerce_map_from_</code>.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
So it seems to me that _coerce_map_from_ returning True should perhaps be abolished entirely and that in other cases one should be very careful with implementing _coerce_map_from_.
</p>
</blockquote>
<p>
I disagree.
</p>
</blockquote>
<p>
What other purpose does <code>_coerce_map_from_</code> serve than shortcutting a backtracking search? If that is its only purpose then getting a result back that may compare unfavourably with alternative results from backtracking is useless. We may have the resulting _generic_convert_map as a registered coercion then, so that it naturally gets considered as part of the normal search.
</p>
<p>
OK, above I think we have identified that <code>_coerce_map_from_</code> serve another purpose: Providing paths into a parent programmatically, leaving transitive closure properties as a responsibility to the implementor of the specific <code>_coerce_map_from_</code> routine.
</p>
<p>
<strong>Conjecture:</strong> (Robert may be able to confirm or deny) The coercion model was designed to implement a digraph. However, the costs of full recursive backtracking were feared to be too high, so it was hoped that in a lot of cases, paths could be computed rather than recursively discovered, leaving only a relatively small number of candidates to be compared (i.e., <code>Y._coerce_map_from_(X)</code> should usually return a map directly, if there is one at all, so backtracking from Z shouldn't normally have to search very far to find a Y with a registered coercion into Z that knows how to handle X).
</p>
<p>
The cost in this approach is that <code>_coerce_map_from_</code> needs to handle transitive closure by itself already. Backing it up with registered coercions anyway would leave us with too many paths to backtrack on anyway [that's only slightly mitigated by your "early exit" proposal]
</p>
TicketSimonKingFri, 25 Oct 2013 11:36:08 GMT
https://trac.sagemath.org/ticket/15303#comment:63
https://trac.sagemath.org/ticket/15303#comment:63
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:62" title="Comment 62">nbruin</a>:
</p>
<blockquote class="citation">
<p>
So shouldn't the rule be: If <code>K._coerce_map_from_(L)</code> returns something then one of the following must be true
</p>
<ul><li>There is a registered coercion from L to K
</li><li>There is a registered embedding from L to K
</li></ul></blockquote>
<p>
Better: A sequence of registered embeddings and coercions.
</p>
<blockquote class="citation">
<ul><li>For any structure M that coerces into L, K._coerce_map_from_(M) also returns something.
</li></ul></blockquote>
<p>
I think so.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Hence, it is not enough to assign costs to arrows in the digraph.
</p>
</blockquote>
<p>
No, "shortcut" paths returned by <code>_coerce_map_from_</code> should carry a cost as well, obviously. And one would hope their cost roughly corresponds the cheapest path that can be discovered otherwise (perhaps with a small modifier to make it more attractive to use this particular path).
</p>
</blockquote>
<p>
Well, the point I wanted to make is: One needs to construct the maps, because only the map know about their costs.
</p>
<blockquote class="citation">
<p>
Aren't the "shortcuts" supposed to be an implementation detail to more efficiently implement the theoretical digraph model? In that case we can reason about their desired properties purely based on the theoretical digraph model.
</p>
</blockquote>
<p>
Perhaps. But it may also affect lifetime implications.
</p>
TicketnbruinFri, 25 Oct 2013 17:38:51 GMT
https://trac.sagemath.org/ticket/15303#comment:64
https://trac.sagemath.org/ticket/15303#comment:64
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:63" title="Comment 63">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Well, the point I wanted to make is: One needs to construct the maps, because only the map know about their costs.
</p>
</blockquote>
<p>
Don't we almost always have the map in hand? When we find the map as a registered coercion or embedding, we can readily read off the cost. We can also do that when we get a map back from <code>_coerce_map_from_</code>. The only case where we have to estimate the cost is when we get the existence of a map via <code>K._coerce_map_from_(L)==True</code>, but in that case I expect the cost is a fixed number anyway, because it's a generically constructed map.
</p>
<p>
I assume that the cost of a composition is the sum of the costs of the composed maps, because otherwise we are not working on a weighted digraph.
</p>
<p>
That means we can simply sum the costs of the edges to get the cost of a path. No need to compute the "composition" of the maps explicitly until we actually need it.
</p>
<p>
Your "don't consider other maps coming into <code>K</code> if we're getting an actual map back from <code>K._coerce_map_from_(L)</code>" is then simply an assumption that <code>K._coerce_map_from_(L)</code> returns the cheapest map available. I think it helps making such assumptions about the coercion discovery algorithm explicit.
</p>
TicketnbruinFri, 25 Oct 2013 21:03:46 GMT
https://trac.sagemath.org/ticket/15303#comment:65
https://trac.sagemath.org/ticket/15303#comment:65
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:53" title="Comment 53">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I think the following is both reasonable and reasonably close to the status quo:
</p>
<ul><li>if <code>_coerce_map_from_</code> returns a map, then we trust that it is a good choice.
</li><li>if <code>_coerce_map_from_</code> returns True, then we do not necessarily trust that <code>self._generic_convert_map(S)</code> is the best choice. So, we test if backtracking yields anything better.
</li></ul></blockquote>
<p>
Unfortunately, that doesn't seem to be a very good heuristic because it's not stable: <code>_coerce_map_from_</code> is supposed to do some backtracking on its own, so if <code>A._coerce_map_from(B)</code> happens to consider another parent <code>C</code> that coerces into <code>A</code> and find that <code>C._coerce_map_from(B)==True</code>, it would return an explicit composite map, with the generic conversion from B into C as one of the components. This map would receive preference, but this map should be even less attractive because on top of a generic conversion, it is also composed with some other map.
</p>
TicketgitFri, 25 Oct 2013 21:17:08 GMTcommit changed
https://trac.sagemath.org/ticket/15303#comment:66
https://trac.sagemath.org/ticket/15303#comment:66
<ul>
<li><strong>commit</strong>
changed from <em>74821fe5409c3104b5d6eb7407a8287d54170df9</em> to <em>5c0800a07bd83787e59713236e5ccc8dde434760</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td>[changeset:5c0800a]</td><td>_coerce_map_from_ shouldn't return default conversion maps. Fix for embedded number field morphisms
</td></tr><tr><td>[changeset:b7fe7fc]</td><td>Use registered coercions *and* embeddings for backtracking, but prefer the former.
</td></tr><tr><td>[changeset:a18e13e]</td><td>Increase coerce cache version in Morphism.register_as_coercion()
</td></tr></table>
TicketSimonKingFri, 25 Oct 2013 21:28:45 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/15303#comment:67
https://trac.sagemath.org/ticket/15303#comment:67
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>Implement backtracking properly</em> deleted
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:65" title="Comment 65">nbruin</a>:
</p>
<blockquote class="citation">
<p>
Unfortunately, that doesn't seem to be a very good heuristic because it's not stable: <code>_coerce_map_from_</code> is supposed to do some backtracking on its own, so if <code>A._coerce_map_from(B)</code> happens to consider another parent <code>C</code> that coerces into <code>A</code> and find that <code>C._coerce_map_from(B)==True</code>, it would return an explicit composite map, with the generic conversion from B into C as one of the components. This map would receive preference, but this map should be even less attractive because on top of a generic conversion, it is also composed with some other map.
</p>
</blockquote>
<p>
Why should <code>A._coerce_map_from(B)</code> return anything? Aren't you rather talking about <code>A.discover_coerce_map_from(B)</code> that recurses to C and thus calls <code>C._coerce_map_from_(B)</code>?
</p>
<p>
In any case, I have now pushed my recent commits. I did solve the recursion error with embedded number field morphism (solution: Raise a <code>TypeError</code> if one of the number fields actually is not embedded), and with this change
</p>
<pre class="wiki">sage: L.<i> = NumberField(x^2 + 1)
sage: K = NumberField(L(i/2+3).minpoly(), names=('i0',), embedding=L(i/2+3))
</pre><p>
works like a charm. I don't know yet whether it results in other problems, but in any case I'll revert to "needs review" now.
</p>
TicketSimonKingFri, 25 Oct 2013 21:30:54 GMT
https://trac.sagemath.org/ticket/15303#comment:68
https://trac.sagemath.org/ticket/15303#comment:68
<p>
PS: It might be a good idea to get some number theorist to look at the change to <code>EmbeddedNumberFieldMorphism</code> and confirm whether this change makes sense for the number theoretical applications.
</p>
TicketSimonKingFri, 25 Oct 2013 21:53:26 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/15303#comment:69
https://trac.sagemath.org/ticket/15303#comment:69
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>Crash in permgroup.py</em>
</li>
</ul>
TicketnbruinFri, 25 Oct 2013 22:39:16 GMT
https://trac.sagemath.org/ticket/15303#comment:70
https://trac.sagemath.org/ticket/15303#comment:70
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:67" title="Comment 67">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Why should <code>A._coerce_map_from(B)</code> return anything?
</p>
</blockquote>
<p>
Because if I'm not mistaken, the implementor of A can decide to implement coercion into A via _coerce_map_from_. Thus we'd have
</p>
<pre class="wiki">class type_of_A(...):
...
def _coerce_map_from_(self,S):
if S is self.C_on_which_A_is_based:
return True
return self._coerce_map_via([self.C_on_which_A_is_based],S)
class type_of_C(...):
...
def _coerce_map_from_(self,S):
if is_instance(S,type_of_B):
return True
<other stuff>
</pre><p>
With this one would get
</p>
<pre class="wiki">sage: A._coerce_map_from_(C)
True
sage: C._coerce_map_from_(B)
True
sage: A._coerce_map_from_(B)
Composite map ...
</pre><p>
As far as I can see (taking, for instance <code>CC._coerce_map_from_</code> as an example) this would be a legitimate way of implementing coercion, and as you can see, the map found from C to A is explicitly returned, but consists of maps that are generic conversion maps.
</p>
<blockquote class="citation">
<p>
Aren't you rather talking about <code>A.discover_coerce_map_from(B)</code> that recurses to C and thus calls <code>C._coerce_map_from_(B)</code>?
</p>
</blockquote>
<p>
No, I'm talking about implementing part of the coercion graph (with backtracking on its paths) programmatically as part of the implementation of a parent via <code>_coerce_map_from_</code>. I think this was expressly a part of the current design and I think there are many examples of this in sage.
</p>
<p>
Reading the documentation of <code>discover_coerce_map_from</code>, it seems that routine would have the same issue (because it also seems to dislike <code>DefaultConvertMap</code>, and the fragment above shows that it is quite possible to get a composition of <code>DefaultConvertMap</code>s back, which should be even more disliked)
</p>
<p>
At this point it seems to me the coercion graphs gets specified in two ways:
</p>
<ul><li>the <code>_coerce_map_from_</code> world, where coercions and backtracking procedures are provided in a distributed, programmatic fashion. One would hope that the paths returned by this bit are consistent with what you'd get from finding paths on an actual graph.
</li><li>the <code>_populate_coercion_lists_</code> world, which more readily corresponds to a graph presentation.
</li></ul><p>
The total coercion graph is supposed to be the union of the two, but the way in which the merger is done seems murky and extremely implementation-dependent to me at the moment (perhaps because the <code>_coerce_map_from_</code> world is completely implementation dependent by design).
</p>
<p>
I think we'd need to clarify the relation between the two a little more, and hopefully formulate some axioms that we can assume the <code>_coerce_map_from_</code> world is adhering to before it's wise to further complicate the situation by also implementing backtracking along embeddings.
</p>
<p>
I think the investigations here are very useful, because I think we are making explicit a lot of implicit facts and assumptions that have been floating around in the coercion system and probably got violated in the organic evolution of the system.
</p>
TicketSimonKingSat, 26 Oct 2013 07:57:42 GMT
https://trac.sagemath.org/ticket/15303#comment:71
https://trac.sagemath.org/ticket/15303#comment:71
<p>
These are the errors one is getting with the current commits:
</p>
<pre class="wiki">sage -t src/sage/groups/perm_gps/permgroup.py # Killed due to abort
sage -t src/sage/combinat/sf/sfa.py # 1 doctest failed
sage -t src/sage/rings/number_field/number_field.py # 11 doctests failed
sage -t src/sage/combinat/sf/new_kschur.py # 2 doctests failed
sage -t src/sage/tests/book_schilling_zabrocki_kschur_primer.py # 1 doctest failed
sage -t src/sage/combinat/root_system/weyl_characters.py # 1 doctest failed
sage -t src/sage/combinat/sf/sf.py # 2 doctests failed
sage -t src/sage/structure/parent.pyx # 1 doctest failed
sage -t src/sage/rings/residue_field.pyx # 1 doctest failed
sage -t src/sage/combinat/symmetric_group_algebra.py # 1 doctest failed
sage -t src/sage/combinat/ncsf_qsym/ncsf.py # 4 doctests failed
sage -t src/sage/rings/polynomial/multi_polynomial_libsingular.pyx # 1 doctest failed
sage -t src/sage/rings/number_field/number_field_morphisms.pyx # 1 doctest failed
sage -t src/sage/rings/universal_cyclotomic_field/universal_cyclotomic_field.py # 13 doctests failed
sage -t src/sage/rings/fraction_field_FpT.pyx # 2 doctests failed
sage -t src/sage/categories/algebras.py # 1 doctest failed
sage -t src/sage/categories/with_realizations.py # 1 doctest failed
sage -t src/sage/rings/padics/padic_base_coercion.pyx # 3 doctests failed
</pre><p>
It is perhaps not as bad as it looks. Some of these errors come from weakening of coerce maps, namely: Some of the coerce maps used in doctests were not weakened by <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a>, but became weakened now. So, that's trivial to fix.
</p>
<p>
What is bad is (at least) the crash in permgroup.py, and 11 errors on number fields also sounds like too many...
</p>
TicketgitSat, 26 Oct 2013 10:19:37 GMTcommit changed
https://trac.sagemath.org/ticket/15303#comment:72
https://trac.sagemath.org/ticket/15303#comment:72
<ul>
<li><strong>commit</strong>
changed from <em>5c0800a07bd83787e59713236e5ccc8dde434760</em> to <em>8d3caea741650a0590f27edc8df0a614aecd31a9</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td>[changeset:8d3caea]</td><td>Copy some coerce maps in doctests. Use default conversion to coerce ZZ into QQbar
</td></tr></table>
TicketSimonKingSat, 26 Oct 2013 10:21:34 GMT
https://trac.sagemath.org/ticket/15303#comment:73
https://trac.sagemath.org/ticket/15303#comment:73
<p>
I have just pushed a new commit that should fix most of the trivial problems. But not all is good, I guess
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td>[changeset:8d3caea]</td><td>Copy some coerce maps in doctests. Use default conversion to coerce ZZ into QQbar
</td></tr></table>
TicketSimonKingSat, 26 Oct 2013 12:57:02 GMT
https://trac.sagemath.org/ticket/15303#comment:74
https://trac.sagemath.org/ticket/15303#comment:74
<p>
I detected another bug in <em>vanilla Sage</em>, that becomes a problem with my commits:
</p>
<pre class="wiki">sage: from sage.categories.pushout import pushout
sage: pushout(Qp(7),RLF)
Traceback (most recent call last):
...
RuntimeError: maximum recursion depth exceeded while calling a Python object
</pre>
TicketSimonKingSat, 26 Oct 2013 13:07:43 GMT
https://trac.sagemath.org/ticket/15303#comment:75
https://trac.sagemath.org/ticket/15303#comment:75
<p>
PS: I believe that fixing above bug boils down to re-thinking how the <code>CompletionFunctor</code> construction functors merge. Namely, both <code>RLF</code> and <code>Qp(7)</code> are constructed by completion of <code>QQ</code>.
</p>
TicketSimonKingSat, 26 Oct 2013 13:13:54 GMT
https://trac.sagemath.org/ticket/15303#comment:76
https://trac.sagemath.org/ticket/15303#comment:76
<p>
PPS: ... how they merge or how they *commute*!
</p>
<p>
Namely, the different completion functors apparently don't merge, but they commute, and I guess I am to blame for it. I guess completion functors should only commute if they complete at the same point. E.g., completion at 7 with precision 20 and completion at 7 with precision 40 does commute. But completion at 7 and completion at +Infinity should not commute.
</p>
TicketgitSat, 26 Oct 2013 13:20:45 GMTcommit changed
https://trac.sagemath.org/ticket/15303#comment:77
https://trac.sagemath.org/ticket/15303#comment:77
<ul>
<li><strong>commit</strong>
changed from <em>8d3caea741650a0590f27edc8df0a614aecd31a9</em> to <em>f8f79b8d0e3f42b418703f094d7eb1dd3ff905e8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td>[changeset:f8f79b8]</td><td>Fix commutation of <a class="missing wiki">CompletionFunctor?</a>. Further fix for embedded number field morphisms
</td></tr></table>
TicketSimonKingSat, 26 Oct 2013 13:27:15 GMT
https://trac.sagemath.org/ticket/15303#comment:78
https://trac.sagemath.org/ticket/15303#comment:78
<p>
The new commit changes <code>CompletionFunctor.commutes(..)</code>, so that the completion functor only commutes with the <code>FractionField</code>, but not with other <code>CompletionFunctor</code>s (this is because other completion functors have already been taken care of by <code>CompletionFunctor.merge(..)</code>).
</p>
<p>
Also, it changes <code>_coerce_map_from_</code> of number fields according to the previous changes in <code>EmbeddedNumberFieldMorphism</code>.
</p>
<p>
With the current commit, all tests in <code>sage/rings/number_field/</code> pass.
</p>
TicketSimonKingSat, 26 Oct 2013 13:42:36 GMTattachment set
https://trac.sagemath.org/ticket/15303
https://trac.sagemath.org/ticket/15303
<ul>
<li><strong>attachment</strong>
set to <em>sage_crash_SqPXq6.log</em>
</li>
</ul>
<p>
Crash log
</p>
TicketSimonKingSat, 26 Oct 2013 13:43:44 GMT
https://trac.sagemath.org/ticket/15303#comment:79
https://trac.sagemath.org/ticket/15303#comment:79
<p>
I have attached the crash log that results from the permutation_group tests.
</p>
TicketgitSat, 26 Oct 2013 15:18:51 GMTcommit changed
https://trac.sagemath.org/ticket/15303#comment:80
https://trac.sagemath.org/ticket/15303#comment:80
<ul>
<li><strong>commit</strong>
changed from <em>f8f79b8d0e3f42b418703f094d7eb1dd3ff905e8</em> to <em>b9ebe8118451ec1f4df2c3c9714c95138d7615bd</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td>[changeset:b9ebe81]</td><td>Fix some tests by taking *copies* of coerce maps
</td></tr></table>
TicketSimonKingSat, 26 Oct 2013 15:22:11 GMT
https://trac.sagemath.org/ticket/15303#comment:81
https://trac.sagemath.org/ticket/15303#comment:81
<p>
I have pushed another commit. It fixes all remaining doctest errors, except the crash in permgroup.py. The fixes are rather easy: It was needed to add "..." to some expected error messages (reason: The changed string representation of weakened maps) and use non-weakened copies of some coerce maps. Apparently <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a> has not weakened <em>all</em> coercions.
</p>
<p>
Now, we can focus on the crash. No idea yet what is happening. Since it is an actual crash and not just an error that may be caught, I could imagine that some coercion is requested before relevant C data are provided.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td>[changeset:b9ebe81]</td><td>Fix some tests by taking *copies* of coerce maps
</td></tr></table>
TicketSimonKingSat, 26 Oct 2013 19:45:57 GMT
https://trac.sagemath.org/ticket/15303#comment:82
https://trac.sagemath.org/ticket/15303#comment:82
<p>
I would like to open two separate tickets for the two independent problems I mentioned. However, I was shooting myself into the foot: There are two relevant commits. The first commit deals with the first problem *and* with stuff that clearly belongs to here and not to a new ticket. The second commit deals with both the first *and* the second problem.
</p>
<p>
Anyway. I will try to rewrite the branch of this ticket and split off the two independent problems. Perhaps I will even try to "fold patches". Git certainly has the potential to let me do these changes.
</p>
<p>
Of course this means to change the history of the branch. But I strongly believe that only the net result of a ticket must matter. If a change in the history of a trac branch (without to change the resulting code!!!) causes problems for other trac branches that build on top of it, then this should be considered a bug in the current workflow. I will ignore this bug.
</p>
TicketSimonKingSun, 27 Oct 2013 01:29:09 GMTdependencies, work_issues changed
https://trac.sagemath.org/ticket/15303#comment:83
https://trac.sagemath.org/ticket/15303#comment:83
<ul>
<li><strong>dependencies</strong>
changed from <em>#14711</em> to <em>#14711 #15329 #15331</em>
</li>
<li><strong>work_issues</strong>
changed from <em>Crash in permgroup.py</em> to <em>Crash in permgroup.py; rebase</em>
</li>
</ul>
<p>
FWIW, I have created <a class="closed ticket" href="https://trac.sagemath.org/ticket/15329" title="defect: Fix pushout of completed fields (closed: fixed)">#15329</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/15331" title="defect: Do not try to create embedded number field morphisms for non-embedded ... (closed: fixed)">#15331</a> to deal with the two independent sub-problems. Both need review.
</p>
TicketSimonKingSun, 27 Oct 2013 11:23:42 GMTcommit, dependencies changed
https://trac.sagemath.org/ticket/15303#comment:84
https://trac.sagemath.org/ticket/15303#comment:84
<ul>
<li><strong>commit</strong>
changed from <em>b9ebe8118451ec1f4df2c3c9714c95138d7615bd</em> to <em>807550bbc45e9872ac365fc98b817ccd5bcfbb95</em>
</li>
<li><strong>dependencies</strong>
changed from <em>#14711 #15329 #15331</em> to <em>#14711, #15329, #15331</em>
</li>
</ul>
<p>
Last 10 new commits:
</p>
<table class="wiki">
<tr><td>[changeset:807550b]</td><td>Fix some tests by taking *copies* of coerce maps
</td></tr><tr><td>[changeset:1db6444]</td><td>Copy some coerce maps in doctests. Use default conversion to coerce ZZ into QQbar
</td></tr><tr><td>[changeset:810fad8]</td><td>_coerce_map_from_ shouldn't return default conversion maps.
</td></tr><tr><td>[changeset:d46cb9c]</td><td>Use registered coercions *and* embeddings for backtracking, but prefer the former.
</td></tr><tr><td>[changeset:a04b480]</td><td>Increase coerce cache version in Morphism.register_as_coercion()
</td></tr><tr><td>[changeset:1beac71]</td><td>Give user-provided coerce maps the same priority than to a coerce map found by backtracking
</td></tr><tr><td>[changeset:bae64c4]</td><td>Store a version number for the coercion cache, depending on the registered embeddings
</td></tr><tr><td>[changeset:7385549]</td><td>Use registered embeddings for backtracking in the coercion model
</td></tr><tr><td>[changeset:40c787d]</td><td>Merge branch 'ticket/15331' into ticket/15303
</td></tr><tr><td>[changeset:29ab8ee]</td><td>Merge branch 'ticket/15329' into ticket/15303
</td></tr></table>
TicketSimonKingSun, 27 Oct 2013 11:29:05 GMTwork_issues changed
https://trac.sagemath.org/ticket/15303#comment:85
https://trac.sagemath.org/ticket/15303#comment:85
<ul>
<li><strong>work_issues</strong>
changed from <em>Crash in permgroup.py; rebase</em> to <em>Crash in permgroup.py</em>
</li>
</ul>
<p>
I did the deed. That's to say, I changed what in the current workflow is called "history", but what I think should better be described as "re-organisation of bits of code in order to facilitate reviewing".
</p>
<p>
Whatever it is called, two independent issues are tracked at <a class="closed ticket" href="https://trac.sagemath.org/ticket/15329" title="defect: Fix pushout of completed fields (closed: fixed)">#15329</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/15331" title="defect: Do not try to create embedded number field morphisms for non-embedded ... (closed: fixed)">#15331</a>, and the crash in permgroup.py remains a problem.
</p>
TicketSimonKingSun, 27 Oct 2013 12:02:15 GMT
https://trac.sagemath.org/ticket/15303#comment:86
https://trac.sagemath.org/ticket/15303#comment:86
<p>
I have suggested to get both a speed-up and a cleaner behaviour of the backtracking algorithm with respect to "comparison of parents by identity".
</p>
<p>
Namely, paths in the coerce digraph are currently marked as "already used in backtracking" by the cdef function "_register_pair(x,y,tag)", and the mark is removed by another cdef function "_unregister_pair(x,y,tag)".
</p>
<p>
In both cases, the functions create an instance of the cdef class <code>EltPair</code>, and stores resp. removes it in some dictionary. The instances of <code>EltPair</code> are compared by comparing <code>(x,y,tag)</code>, and the hash also is obtained in that way.
</p>
<p>
But that means parents are compared by <code>==</code>, whereas in the innards of the coercion system parents (even non-unique parents!) are generally compared by <code>is</code>. Moreover, comparison by identity and hash by id would be a lot faster, and creating an instance of <code>EltPair</code> each time also is a waste of time.
</p>
<p>
Couldn't we use a <code>TripleDict</code> instead? It would compare by identity, it is about triples <code>x,y,tag</code>, and I think we have made tests showing that containment tests and so on are faster than when using a Python dict keyed by triples.
</p>
<p>
I only worry about the weak references. Could it happen that registered pairs will be automatically removed from the triple dict while backtracking, resulting in an infinite recursion? I guess this can not happen, because the backtracking algorithm will only visit parents that are strongly referenced.
</p>
<p>
Anyway, I'd say it is worth trying. If it works, then fine. If it doesn't, we can move this to a separate ticket, that will be using a <em>strong</em> version of <code>TripleDict</code>.
</p>
TicketSimonKingSun, 27 Oct 2013 13:29:45 GMT
https://trac.sagemath.org/ticket/15303#comment:87
https://trac.sagemath.org/ticket/15303#comment:87
<p>
Rather than <code>TripleDict</code>, one could also use a set (not a dict) and use <code>id(X)</code> for comparison. It would compare the parents in the same way as they are compared in the backtracking (namely by id), <em>and</em> it yields a speed-up.
</p>
<p>
Here is my benchmark. I've put the following into <code>sage.structure.parent</code>:
</p>
<div class="wiki-code"><div class="code"><pre><span class="k">def</span> <span class="nf">test_registration</span><span class="p">(</span><span class="nb">list</span> L<span class="p">):</span>
_coerce_test_dict<span class="o">.</span>clear<span class="p">()</span>
<span class="k">for</span> X <span class="ow">in</span> L<span class="p">:</span>
<span class="k">for</span> Y <span class="ow">in</span> L<span class="p">:</span>
_register_pair<span class="p">(</span>X<span class="p">,</span>Y<span class="p">,</span><span class="s">"test"</span><span class="p">)</span>
_is_registered_pair<span class="p">(</span>X<span class="p">,</span>Y<span class="p">,</span><span class="s">"test"</span><span class="p">)</span>
_is_registered_pair<span class="p">(</span>X<span class="p">,</span>Y<span class="p">,</span><span class="s">"fail"</span><span class="p">)</span>
<span class="k">for</span> X <span class="ow">in</span> L<span class="p">:</span>
<span class="k">for</span> Y <span class="ow">in</span> L<span class="p">:</span>
_unregister_pair<span class="p">(</span>X<span class="p">,</span>Y<span class="p">,</span><span class="s">"test"</span><span class="p">)</span>
<span class="kn">from</span> <span class="nn">sage.structure.coerce_dict</span> <span class="nn">cimport</span> <span class="nn">TripleDict</span>
<span class="k">def</span> <span class="nf">test_tripledict</span><span class="p">(</span><span class="nb">list</span> L<span class="p">):</span>
TestT <span class="o">=</span> TripleDict<span class="p">(</span><span class="mi">29</span><span class="p">)</span>
<span class="k">for</span> X <span class="ow">in</span> L<span class="p">:</span>
<span class="k">for</span> Y <span class="ow">in</span> L<span class="p">:</span>
TestT<span class="o">.</span>set<span class="p">(</span>X<span class="p">,</span>Y<span class="p">,</span><span class="s">"test"</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span>
<span class="p">(</span>X<span class="p">,</span>Y<span class="p">,</span><span class="s">"test"</span><span class="p">)</span> <span class="ow">in</span> TestT
<span class="p">(</span>X<span class="p">,</span>Y<span class="p">,</span><span class="s">"fail"</span><span class="p">)</span> <span class="ow">in</span> TestT
<span class="k">for</span> X <span class="ow">in</span> L<span class="p">:</span>
<span class="k">for</span> Y <span class="ow">in</span> L<span class="p">:</span>
<span class="k">del</span> TestT<span class="p">[</span>X<span class="p">,</span>Y<span class="p">,</span><span class="s">"test"</span><span class="p">]</span>
cdef <span class="nb">set</span> testset
<span class="k">def</span> <span class="nf">test_set</span><span class="p">(</span><span class="nb">list</span> L<span class="p">):</span>
<span class="k">global</span> testset
testset <span class="o">=</span> <span class="nb">set</span><span class="p">([])</span>
<span class="k">for</span> X <span class="ow">in</span> L<span class="p">:</span>
<span class="k">for</span> Y <span class="ow">in</span> L<span class="p">:</span>
testset<span class="o">.</span>add<span class="p">((</span><span class="nb">id</span><span class="p">(</span>X<span class="p">),</span><span class="nb">id</span><span class="p">(</span>Y<span class="p">),</span><span class="s">"test"</span><span class="p">))</span>
<span class="p">(</span><span class="nb">id</span><span class="p">(</span>X<span class="p">),</span><span class="nb">id</span><span class="p">(</span>Y<span class="p">),</span><span class="s">"test"</span><span class="p">)</span> <span class="ow">in</span> testset
<span class="p">(</span><span class="nb">id</span><span class="p">(</span>X<span class="p">),</span><span class="nb">id</span><span class="p">(</span>Y<span class="p">),</span><span class="s">"fail"</span><span class="p">)</span> <span class="ow">in</span> testset
<span class="k">for</span> X <span class="ow">in</span> L<span class="p">:</span>
<span class="k">for</span> Y <span class="ow">in</span> L<span class="p">:</span>
<span class="k">try</span><span class="p">:</span>
testset<span class="o">.</span>remove<span class="p">((</span><span class="nb">id</span><span class="p">(</span>X<span class="p">),</span><span class="nb">id</span><span class="p">(</span>Y<span class="p">),</span><span class="s">"test"</span><span class="p">))</span>
<span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
<span class="k">pass</span>
</pre></div></div><p>
With this, I get
</p>
<pre class="wiki">sage: L = [GF(p) for p in prime_range(10^4)]
sage: len(L)
1229
sage: from sage.structure.parent import test_registration, test_tripledict, test_set
sage: %time test_registration(L)
CPU times: user 16.75 s, sys: 0.10 s, total: 16.85 s
Wall time: 16.87 s
sage: %time test_tripledict(L)
CPU times: user 45.74 s, sys: 0.62 s, total: 46.36 s
Wall time: 46.44 s
sage: %time test_set(L)
CPU times: user 3.92 s, sys: 0.00 s, total: 3.93 s
Wall time: 3.93 s
</pre><p>
<span class="underline">Conclusion</span>
</p>
<p>
It is not a good idea to use a <code>TripleDict</code> here (because of speed and because of potential trouble with garbage collection). However, using a set makes sense for two reasons: Speed and consistency of the methods of comparison. And it might be possible to get a further speed-up by doing something like <code><long><void*>X</code> rather than <code>id(X)</code>.
</p>
TicketSimonKingSun, 27 Oct 2013 14:03:08 GMT
https://trac.sagemath.org/ticket/15303#comment:88
https://trac.sagemath.org/ticket/15303#comment:88
<p>
With
</p>
<div class="wiki-code"><div class="code"><pre><span class="k">def</span> <span class="nf">test_set2</span><span class="p">(</span><span class="nb">list</span> L<span class="p">):</span>
<span class="k">global</span> testset
testset <span class="o">=</span> <span class="nb">set</span><span class="p">([])</span>
<span class="k">for</span> X <span class="ow">in</span> L<span class="p">:</span>
<span class="k">for</span> Y <span class="ow">in</span> L<span class="p">:</span>
testset<span class="o">.</span>add<span class="p">((</span><span class="o"><</span>Py_ssize_t<span class="o">><</span>void <span class="o">*></span>X<span class="p">,</span> <span class="o"><</span>Py_ssize_t<span class="o">><</span>void <span class="o">*></span>Y<span class="p">,</span><span class="s">"test"</span><span class="p">))</span>
<span class="p">(</span><span class="o"><</span>Py_ssize_t<span class="o">><</span>void <span class="o">*></span>X<span class="p">,</span> <span class="o"><</span>Py_ssize_t<span class="o">><</span>void <span class="o">*></span>Y<span class="p">,</span><span class="s">"test"</span><span class="p">)</span> <span class="ow">in</span> testset
<span class="p">(</span><span class="o"><</span>Py_ssize_t<span class="o">><</span>void <span class="o">*></span>X<span class="p">,</span> <span class="o"><</span>Py_ssize_t<span class="o">><</span>void <span class="o">*></span>Y<span class="p">,</span><span class="s">"fail"</span><span class="p">)</span> <span class="ow">in</span> testset
<span class="k">for</span> X <span class="ow">in</span> L<span class="p">:</span>
<span class="k">for</span> Y <span class="ow">in</span> L<span class="p">:</span>
<span class="k">try</span><span class="p">:</span>
testset<span class="o">.</span>remove<span class="p">((</span><span class="o"><</span>Py_ssize_t<span class="o">><</span>void <span class="o">*></span>X<span class="p">,</span> <span class="o"><</span>Py_ssize_t<span class="o">><</span>void <span class="o">*></span>Y<span class="p">,</span><span class="s">"test"</span><span class="p">))</span>
<span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
<span class="k">pass</span>
</pre></div></div><p>
I get a further speed-up:
</p>
<pre class="wiki">sage: %time test_set2(L)
CPU times: user 3.18 s, sys: 0.00 s, total: 3.18 s
Wall time: 3.19 s
</pre><p>
So, the speed-up we can get for marking/unmarking/testing of arrows in the coerce digraph during backtracking is a factor of about 4.5.
</p>
TicketSimonKingSun, 27 Oct 2013 15:55:24 GMT
https://trac.sagemath.org/ticket/15303#comment:89
https://trac.sagemath.org/ticket/15303#comment:89
<p>
Question: Shall I try to attempt the speedup of backtracking here (of course in addition to fixing the crash in permgroup.py), or shall I leave this to a separate ticket?
</p>
TicketSimonKingSun, 27 Oct 2013 17:17:11 GMT
https://trac.sagemath.org/ticket/15303#comment:90
https://trac.sagemath.org/ticket/15303#comment:90
<p>
Argh. Not again. A Heisenbug.
</p>
<p>
<code>sage -t --verbose src/sage/groups/perm_gps/permgroup.py</code> and <code>sage -t src/sage/groups/perm_gps/permgroup.py</code> run individually and even <code>sage -tp src/sage/groups/perm_gps/</code> work fine.
</p>
<p>
But when doing <code>make ptest</code> with two parallel processes, I *always* get a crash. Bug hunt will be great fun...
</p>
TicketSimonKingSun, 27 Oct 2013 18:00:06 GMT
https://trac.sagemath.org/ticket/15303#comment:91
https://trac.sagemath.org/ticket/15303#comment:91
<p>
The attached crash log mentions <code>"Entered a critical block twice"</code>. This error comes from <code>libGAP</code>. The crash log also mentions weak references, hash and comparison. The usual suspects.
</p>
TicketSimonKingSun, 27 Oct 2013 18:09:52 GMT
https://trac.sagemath.org/ticket/15303#comment:92
https://trac.sagemath.org/ticket/15303#comment:92
<p>
<code>PyDict_DelItem</code> is mentioned as well. Smells like problems with a <code>WeakValueDictionary</code> such that the callback of a garbage collected value uses a key that is in the process of being garbage collected, too, and thus comparison of the key (which is needed to remove the item from the dictionary) fails.
</p>
TicketSimonKingSun, 27 Oct 2013 18:14:50 GMT
https://trac.sagemath.org/ticket/15303#comment:93
https://trac.sagemath.org/ticket/15303#comment:93
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:92" title="Comment 92">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
<code>PyDict_DelItem</code> is mentioned as well. Smells like problems with a <code>WeakValueDictionary</code> such that the callback of a garbage collected value uses a key that is in the process of being garbage collected, too, and thus comparison of the key (which is needed to remove the item from the dictionary) fails.
</p>
</blockquote>
<p>
Compare <a class="closed ticket" href="https://trac.sagemath.org/ticket/13394" title="enhancement: Write a WeakValueDictionary with safer key removal (closed: fixed)">#13394</a>
</p>
TicketSimonKingSun, 27 Oct 2013 18:18:18 GMT
https://trac.sagemath.org/ticket/15303#comment:94
https://trac.sagemath.org/ticket/15303#comment:94
<p>
And also compare our "old friend" <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>. There, we had problems with objects defined in the Gap pexpect interface (stored in a weak value dictionary)---and now it is <code>libGAP</code>.
</p>
TicketSimonKingSun, 27 Oct 2013 18:38:06 GMT
https://trac.sagemath.org/ticket/15303#comment:95
https://trac.sagemath.org/ticket/15303#comment:95
<p>
If I understand correctly, the crash occurs while computing the hash of a <code>sage.groups.libgap_wrapper.ElementLibGAP</code> object.
</p>
<p>
The hash is inherited from <code>sage.structure.element.Element</code> and relies on the string representation. The string representation relies on the result of the <code>is_one</code> method. This, in turn, amounts to comparison with <code>self.parent().one()</code>.
</p>
<p>
Now I wonder: Has self become defunct? Or has <code>self.parent().one()</code> become defunct? Is it (again) the <code>WeakValueDictionary</code> used by <code>CachedRepresentation</code> that is causing the trouble?
</p>
TicketgitThu, 31 Oct 2013 17:24:19 GMTcommit changed
https://trac.sagemath.org/ticket/15303#comment:96
https://trac.sagemath.org/ticket/15303#comment:96
<ul>
<li><strong>commit</strong>
changed from <em>807550bbc45e9872ac365fc98b817ccd5bcfbb95</em> to <em>528a03535447d67f04dc16d0a22cc38def54f9f1</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td>[changeset:528a035]</td><td>Merge branch 'ticket/13394' into ticket/15303, to make weak caches safer
</td></tr><tr><td>[changeset:851cc95]</td><td>Avoid some pointer casts in <a class="missing wiki">WeakValueDict?</a> callbacks
</td></tr><tr><td>[changeset:246518f]</td><td>Use <dict>'s internals in <a class="missing wiki">WeakValueDictionary?</a> and do not reinvent the bucket.
</td></tr><tr><td>[changeset:fab0ed4]</td><td>Use <a class="missing wiki">WeakValueDict?</a>'s iteration guard more consequently
</td></tr><tr><td>[changeset:e4adaeb]</td><td>Implement copy and deepcopy for <a class="missing wiki">WeakValueDictionary?</a>
</td></tr><tr><td>[changeset:70a7b8a]</td><td>Guard <a class="missing wiki">WeakValueDictionary?</a> against deletions during iteration
</td></tr><tr><td>[changeset:c3dba98]</td><td>Replace weakref.<a class="missing wiki">WeakValueDictionary?</a> by sage.misc.weak_dict.<a class="missing wiki">WeakValueDictionary?</a>
</td></tr><tr><td>[changeset:17b0236]</td><td>Documentation for <a class="missing wiki">WeakValueDictionary?</a>
</td></tr><tr><td>[changeset:f0ed60f]</td><td>Initial version of a safer and faster <a class="missing wiki">WeakValueDictionary?</a>
</td></tr></table>
TicketSimonKingThu, 31 Oct 2013 17:35:00 GMTstatus changed
https://trac.sagemath.org/ticket/15303#comment:97
https://trac.sagemath.org/ticket/15303#comment:97
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
I think <a class="closed ticket" href="https://trac.sagemath.org/ticket/13394" title="enhancement: Write a WeakValueDictionary with safer key removal (closed: fixed)">#13394</a> is working, and hence I merged <a class="closed ticket" href="https://trac.sagemath.org/ticket/13394" title="enhancement: Write a WeakValueDictionary with safer key removal (closed: fixed)">#13394</a> into the branch of this ticket. Before I pushed the changes, I did <code>make ptest</code>, and got
</p>
<pre class="wiki">----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 3859.6 seconds
cpu time: 6042.4 seconds
cumulative wall time: 7416.0 seconds
</pre><p>
Hence: Replacing <code>weakref.WeakValueDictionary</code> by the newer safer faster ... <code>sage.misc.weak_dict.WeakValueDictionary</code> has been enough to solve the problem with doctests crashing! So, I can put this to "needs review".
</p>
<p>
I just notice: With the branch from <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/15303" title="defect: Coercion discovery fails to be transitive (needs_work)">#15303</a>, the total time for make ptest is 4634.7 s (or 7269.1 CPU-s). With the branch from here, we are quite noticeably faster. So, could it be that the new approach of representing the dynamic coerce digraph is more efficient?
</p>
TicketjdemeyerTue, 26 Nov 2013 10:54:53 GMTmilestone changed
https://trac.sagemath.org/ticket/15303#comment:98
https://trac.sagemath.org/ticket/15303#comment:98
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.13</em> to <em>sage-6.0</em>
</li>
</ul>
TicketjdemeyerWed, 27 Nov 2013 16:06:33 GMT
https://trac.sagemath.org/ticket/15303#comment:99
https://trac.sagemath.org/ticket/15303#comment:99
<p>
I just noticed the following, is it perhaps related to this ticket?
</p>
<pre class="wiki">sage: ZZ(CC(1))
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-18-628bcdd9a52d> in <module>()
----> 1 ZZ(CC(Integer(1)))
/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8372)()
/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3856)()
/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3757)()
/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/rings/integer.so in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:7889)()
TypeError: unable to coerce <type 'sage.rings.complex_number.ComplexNumber'> to an integer
sage: ZZ(RR(CC(1)))
1
</pre>
TicketnbruinWed, 27 Nov 2013 18:19:38 GMT
https://trac.sagemath.org/ticket/15303#comment:100
https://trac.sagemath.org/ticket/15303#comment:100
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:99" title="Comment 99">jdemeyer</a>:
</p>
<blockquote class="citation">
<pre class="wiki">sage: ZZ(CC(1))
...
/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/rings/integer.so in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:7889)()
TypeError: unable to coerce <type 'sage.rings.complex_number.ComplexNumber'> to an integer
sage: ZZ(RR(CC(1)))
1
</pre></blockquote>
<p>
I don't think it necessarily is related: this is a conversion and given how liberal conversion is allowed/meant to be, I don't think we can expect convertibility to ever be transitive (I think it will even be path-dependent). As the trace shows, it fails in <code>sage.rings.integer.Integer.__init__</code>, i.e., just the integer constructor. I suspect RR has been special-cased there and CC is not (perhaps it should). So, the initializer attempts to see if straight coercion works and of course it doesn't.
</p>
<p>
I don't think these conversions are going to be terribly useful anyway:
</p>
<pre class="wiki">sage: ZZ(49*RR(1/49))
TypeError: Attempt to coerce non-integral RealNumber to Integer
</pre>
TicketdarijSat, 30 Nov 2013 06:55:20 GMT
https://trac.sagemath.org/ticket/15303#comment:101
https://trac.sagemath.org/ticket/15303#comment:101
<p>
This is red now :/
</p>
<pre class="wiki"> * branch u/SimonKing/ticket/15303 -> FETCH_HEAD
Auto-merging src/sage/tests/book_schilling_zabrocki_kschur_primer.py
Auto-merging src/sage/structure/parent.pyx
Auto-merging src/sage/rings/real_mpfr.pyx
Auto-merging src/sage/rings/number_field/number_field_rel.py
Auto-merging src/sage/rings/number_field/number_field.py
Auto-merging src/sage/misc/weak_dict.pyx
CONFLICT (add/add): Merge conflict in src/sage/misc/weak_dict.pyx
Auto-merging src/sage/combinat/symmetric_group_algebra.py
Auto-merging src/sage/combinat/sf/new_kschur.py
Auto-merging src/sage/combinat/ncsf_qsym/ncsf.py
Auto-merging src/sage/categories/pushout.py
Auto-merging src/sage/categories/morphism.pyx
Automatic merge failed; fix conflicts and then commit the result.
</pre>
TicketSimonKingSat, 30 Nov 2013 09:28:22 GMT
https://trac.sagemath.org/ticket/15303#comment:102
https://trac.sagemath.org/ticket/15303#comment:102
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:101" title="Comment 101">darij</a>:
</p>
<blockquote class="citation">
<p>
Automatic merge failed; fix conflicts and then commit the result.
</p>
</blockquote>
<p>
Does this mean I need to do
</p>
<pre class="wiki">git checkout trac/master
git pull
git checkout ticket/15303
</pre><p>
and then try to merge trac/master into my branch, resolving conflicts?
</p>
TicketSimonKingSat, 30 Nov 2013 09:31:06 GMT
https://trac.sagemath.org/ticket/15303#comment:103
https://trac.sagemath.org/ticket/15303#comment:103
<p>
Or better "git pull trac"...
</p>
TicketSimonKingSat, 30 Nov 2013 09:36:48 GMT
https://trac.sagemath.org/ticket/15303#comment:104
https://trac.sagemath.org/ticket/15303#comment:104
<p>
WTF??
</p>
<p>
I see the same merge conflict. So, I try "git mergetool", which (for my setup) means that "meld" is started to help me resolve conflict.
</p>
<p>
From looking at it, the two versions of weak_dict.pyx look <em>identical</em>! Nevertheless both the local and the remote version of the file are all marked red in meld, i.e., they are in 100% conflict.
</p>
<p>
Sorry, but if this is a feature of git then I must say that it sucks.
</p>
TicketSimonKingSat, 30 Nov 2013 09:51:06 GMT
https://trac.sagemath.org/ticket/15303#comment:105
https://trac.sagemath.org/ticket/15303#comment:105
<p>
Gosh, I hate git!!!
</p>
<p>
After giving up on the merge, I tried "git checkout master", but it told me
</p>
<pre class="wiki">src/sage/misc/weak_dict.pyx: needs merge
src/sage/schemes/generic/morphism.py: needs merge
error: Du musst zuerst deine aktuelle Bereitstellung auflösen.
</pre><p>
Sorry, but I simply don't want to continue with this merge! How do I tell git that it shall please forget about this merge and bring me back to either a clear master branch or a clear ticket branch?
</p>
TicketmmezzarobbaSat, 30 Nov 2013 12:37:38 GMT
https://trac.sagemath.org/ticket/15303#comment:106
https://trac.sagemath.org/ticket/15303#comment:106
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:105" title="Comment 105">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
How do I tell git that it shall please forget about this merge and bring me back to either a clear master branch or a clear ticket branch?
</p>
</blockquote>
<p>
<code>git reset --hard</code>
</p>
TicketmmezzarobbaSat, 30 Nov 2013 13:15:23 GMT
https://trac.sagemath.org/ticket/15303#comment:107
https://trac.sagemath.org/ticket/15303#comment:107
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:104" title="Comment 104">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
From looking at it, the two versions of weak_dict.pyx look <em>identical</em>!
</p>
</blockquote>
<p>
Do they? To me it looks like the version in <code>trac/master</code> is more recent. (Do <code>git diff :2:src/sage/misc/weak_dict.pyx :3:src/sage/misc/weak_dict.pyx</code> to see the diff between the two versions without taking into account the—empty—common ancestor.) Just in cas it helps, I pushed a merge based on this assumption to <code>u/mmezzarobba/ticket/15303</code>.
</p>
TicketSimonKingSat, 30 Nov 2013 13:37:33 GMT
https://trac.sagemath.org/ticket/15303#comment:108
https://trac.sagemath.org/ticket/15303#comment:108
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:107" title="Comment 107">mmezzarobba</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:104" title="Comment 104">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
From looking at it, the two versions of weak_dict.pyx look <em>identical</em>!
</p>
</blockquote>
<p>
Do they?
</p>
</blockquote>
<p>
Meanwhile I found that they differ.
</p>
<p>
Usually, the mergetool I am using (meld) just shows me the differences and lets me decide which to take. However, this time, meld gave me the impression that the two versions differ by 100%. It did not even show a single line which is common to both versions. And that's clearly wrong.
</p>
<blockquote class="citation">
<p>
To me it looks like the version in <code>trac/master</code> is more recent.
</p>
</blockquote>
<p>
It is. There also is another file with conflicts (sage/schemes/generic/morphism.py)
</p>
<blockquote class="citation">
<p>
Just in cas it helps, I pushed a merge based on this assumption to <code>u/mmezzarobba/ticket/15303</code>.
</p>
</blockquote>
<p>
Thank you. How to access it (with either git or the dev scripts)?
</p>
TicketmmezzarobbaSat, 30 Nov 2013 14:37:19 GMT
https://trac.sagemath.org/ticket/15303#comment:109
https://trac.sagemath.org/ticket/15303#comment:109
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:108" title="Comment 108">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Usually, the mergetool I am using (meld) just shows me the differences and lets me decide which to take. However, this time, meld gave me the impression that the two versions differ by 100%. It did not even show a single line which is common to both versions.
</p>
</blockquote>
<p>
As far as I understand, that's because both versions were added independently to their respective branches. So each of the two diffs from the common ancestor contains a single hunk with the whole contents of the file, and <code>merge</code> doesn't find any common block to remove.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Just in cas it helps, I pushed a merge based on this assumption to <code>u/mmezzarobba/ticket/15303</code>.
</p>
</blockquote>
<p>
Thank you. How to access it (with either git or the dev scripts)?
</p>
</blockquote>
<p>
It depends a little bit on your setup, but something like
</p>
<pre class="wiki">git fetch trac u/mmezzarobba/ticket/15303
git checkout u/mmezzarobba/ticket/15303 -m mybranch
</pre><p>
(or <code>git merge --ff-only u/mmezzarobba/ticket/15303</code> if you are already on your ticket branch and want to add the merge commit to that branch) should work.
</p>
<p>
Please check that what I did is really what you had in mind!
</p>
TicketSimonKingSat, 30 Nov 2013 15:13:40 GMT
https://trac.sagemath.org/ticket/15303#comment:110
https://trac.sagemath.org/ticket/15303#comment:110
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:109" title="Comment 109">mmezzarobba</a>:
</p>
<blockquote class="citation">
<pre class="wiki">git fetch trac u/mmezzarobba/ticket/15303
git checkout u/mmezzarobba/ticket/15303 -m mybranch
</pre><p>
(or <code>git merge --ff-only u/mmezzarobba/ticket/15303</code> if you are already on your ticket branch and want to add the merge commit to that branch) should work.
</p>
</blockquote>
<p>
The fetch command worked. However, the rest of it didn't.
</p>
<pre class="wiki">king@linux-etl7:~/Sage/git/sage> git fetch trac u/mmezzarobba/ticket/15303
Enter passphrase for key '/home/king/.ssh/id_rsa':
remote: Counting objects: 161, done.
remote: Compressing objects: 100% (55/55), done.
remote: Total 55 (delta 53), reused 0 (delta 0)
Unpacking objects: 100% (55/55), done.
Von ssh://trac.sagemath.org:2222/sage
* branch u/mmezzarobba/ticket/15303 -> FETCH_HEAD
king@linux-etl7:~/Sage/git/sage> git merge --ff-only u/mmezzarobba/ticket/15303
fatal: u/mmezzarobba/ticket/15303 - nichts was wir zusammenführen können
king@linux-etl7:~/Sage/git/sage> git checkout u/mmezzarobba/ticket/15303 -m ticket/15303mezzarobba
error: pathspec 'u/mmezzarobba/ticket/15303' did not match any file(s) known to git.
error: pathspec 'ticket/15303mezzarobba' did not match any file(s) known to git.
</pre><p>
However, since apparently git decided to assign your branch to FETCH_HEAD, <code>git merge --ff-only FETCH_HEAD</code> seems to work.
</p>
TicketSimonKingSat, 30 Nov 2013 15:21:10 GMT
https://trac.sagemath.org/ticket/15303#comment:111
https://trac.sagemath.org/ticket/15303#comment:111
<p>
How can I see what you did? I tried <code>git diff HEAD^2</code>, but it doesn't really look like what I expected from resolving a merge conflict, since it touches stuff that did not conflict.
</p>
<pre class="wiki">diff --git a/src/doc/en/reference/coercion/index.rst b/src/doc/en/reference/coercion/index.rst
index 933098a..e72339e 100644
--- a/src/doc/en/reference/coercion/index.rst
+++ b/src/doc/en/reference/coercion/index.rst
@@ -269,8 +269,21 @@ discovered between steps 1 and 2 above.
sage: f = QQ.coerce_map_from(ZZ)
sage: f(3).parent()
Rational Field
+
+Note that by :trac:`14711` Sage's coercion system uses maps with weak
+references to the domain. Such maps should only be used internally, and so a
+copy should be used instead (unless one knows what one is doing)::
+
sage: QQ.coerce_map_from(int)
Native morphism:
+ From: Set of Python objects of type 'int'
+ To: Rational Field
+ <BLANKLINE>
+ WARNING: This morphism has apparently been used internally
+ in the coercion system. It may become defunct in the next
+ garbage collection. Please use a copy.
+ sage: copy(QQ.coerce_map_from(int))
+ Native morphism:
From: Set of Python objects of type 'int'
To: Rational Field
sage: QQ.has_coerce_map_from(RR)
diff --git a/src/doc/en/thematic_tutorials/coercion_and_categories.rst b/src/doc/en/thematic_tutorials/coercion_and_categories.rst
index 1a31e7a..fd38034 100644
--- a/src/doc/en/thematic_tutorials/coercion_and_categories.rst
+++ b/src/doc/en/thematic_tutorials/coercion_and_categories.rst
@@ -750,15 +750,19 @@ thus have::
sage: P1.has_coerce_map_from(P2)
True
- sage: P1.coerce_map_from(P2)
+ sage: copy(P1.coerce_map_from(P2))
Call morphism:
From: Multivariate Polynomial Ring in w, v over Integer Ring
To: Multivariate Polynomial Ring in v, w over Rational Field
+Note that we used a copy of the coerce map because of :trac:`14711`: Sage's
+coercion system internally uses maps with weak references to their domain, and
+only copies of such maps should be used outside of the coercion system.
etc. pp.
</pre><p>
Or is <code>git diff HEAD^2</code> not the right thing to do in order to see your changes?
</p>
TicketmmezzarobbaSat, 30 Nov 2013 15:26:57 GMT
https://trac.sagemath.org/ticket/15303#comment:112
https://trac.sagemath.org/ticket/15303#comment:112
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:110" title="Comment 110">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:109" title="Comment 109">mmezzarobba</a>:
</p>
<blockquote class="citation">
<pre class="wiki">git fetch trac u/mmezzarobba/ticket/15303
git checkout u/mmezzarobba/ticket/15303 -m mybranch
</pre><p>
(or <code>git merge --ff-only u/mmezzarobba/ticket/15303</code> if you are already on your ticket branch and want to add the merge commit to that branch) should work.
</p>
</blockquote>
<p>
The fetch command worked. However, the rest of it didn't.
</p>
</blockquote>
<p>
Sorry, I meant to write
</p>
<pre class="wiki">git checkout trac/u/mmezzarobba/ticket/15303 -m mybranch
</pre>
TicketSimonKingSat, 30 Nov 2013 15:46:49 GMT
https://trac.sagemath.org/ticket/15303#comment:113
https://trac.sagemath.org/ticket/15303#comment:113
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:112" title="Comment 112">mmezzarobba</a>:
</p>
<blockquote class="citation">
<p>
Sorry, I meant to write
</p>
<pre class="wiki">git checkout trac/u/mmezzarobba/ticket/15303 -m mybranch
</pre></blockquote>
<pre class="wiki">git checkout trac/u/mmezzarobba/ticket/15303 -m ticket/15303/mezzarobba
error: pathspec 'trac/u/mmezzarobba/ticket/15303' did not match any file(s) known to git.
error: pathspec 'ticket/15303/mezzarobba' did not match any file(s) known to git.
</pre><p>
So, that's not it.
</p>
<p>
However, as I said above: After the fetch command, I did <code>git merge --ff-only FETCH_HEAD</code> (being on my branch for this ticket), and I hope that this was one way to incorporate your merge resolution.
</p>
<p>
However, how can I <em>see</em> your merge resolution?
</p>
TicketSimonKingSat, 30 Nov 2013 15:47:03 GMT
https://trac.sagemath.org/ticket/15303#comment:114
https://trac.sagemath.org/ticket/15303#comment:114
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:112" title="Comment 112">mmezzarobba</a>:
</p>
<blockquote class="citation">
<p>
Sorry, I meant to write
</p>
<pre class="wiki">git checkout trac/u/mmezzarobba/ticket/15303 -m mybranch
</pre></blockquote>
<pre class="wiki">git checkout trac/u/mmezzarobba/ticket/15303 -m ticket/15303/mezzarobba
error: pathspec 'trac/u/mmezzarobba/ticket/15303' did not match any file(s) known to git.
error: pathspec 'ticket/15303/mezzarobba' did not match any file(s) known to git.
</pre><p>
So, that's not it.
</p>
<p>
However, as I said above: After the fetch command, I did <code>git merge --ff-only FETCH_HEAD</code> (being on my branch for this ticket), and I hope that this was one way to incorporate your merge resolution.
</p>
<p>
However, how can I <em>see</em> your merge resolution?
</p>
TicketmmezzarobbaSat, 30 Nov 2013 15:51:08 GMT
https://trac.sagemath.org/ticket/15303#comment:115
https://trac.sagemath.org/ticket/15303#comment:115
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:111" title="Comment 111">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
How can I see what you did? I tried <code>git diff HEAD^2</code>, but it doesn't really look like what I expected from resolving a merge conflict, since it touches stuff that did not conflict.
</p>
</blockquote>
<p>
<code>git diff HEAD^2</code> gives you all the differences between one of the parents (in our case, <code>master</code>) and HEAD, without taking into account the other parent at all. To see the effect of a merge, you can try viewing the "combined diff" of HEAD and both parents (<code>git show HEAD</code>). But this will omit all files that agree entirely with <em>either</em> of the parents. Also, the output will include the parts of the merge that were automatically resolved.
</p>
<p>
All I did manually was to choose the version of <code>morphism.pyx</code> that looked more recent, and to merge the imports of <code>morphism.py</code> as follows:
</p>
<pre class="wiki"> -from sage.categories.homset import Homset
+from sage.categories.homset import Homset, Hom
- from sage.rings.all import is_RingHomomorphism, is_CommutativeRing,
+ from sage.rings.all import Integer
+ from sage.rings.commutative_ring import is_CommutativeRing
+ from sage.rings.morphism import is_RingHomomorphism
</pre>
TicketSimonKingSat, 30 Nov 2013 16:01:50 GMT
https://trac.sagemath.org/ticket/15303#comment:116
https://trac.sagemath.org/ticket/15303#comment:116
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:115" title="Comment 115">mmezzarobba</a>:
</p>
<blockquote class="citation">
<p>
To see the effect of a merge, you can try viewing the "combined diff" of HEAD and both parents (<code>git show HEAD</code>). But this will omit all files that agree entirely with <em>either</em> of the parents. Also, the output will include the parts of the merge that were automatically resolved.
</p>
</blockquote>
<p>
I see. So, you took the version of <code>src/sage/misc/weak_dictionary.pyx</code> from master, and ...
</p>
<blockquote class="citation">
<p>
All I did manually was to choose the version of <code>morphism.pyx</code> that looked more recent,
</p>
</blockquote>
<p>
I have not even been aware that this has changed. So, someone has made morphisms that are defined by generator images hashable? Nice!
</p>
<blockquote class="citation">
<p>
and to merge the imports of <code>morphism.py</code> as follows:
</p>
<pre class="wiki"> -from sage.categories.homset import Homset
+from sage.categories.homset import Homset, Hom
- from sage.rings.all import is_RingHomomorphism, is_CommutativeRing,
+ from sage.rings.all import Integer
+ from sage.rings.commutative_ring import is_CommutativeRing
+ from sage.rings.morphism import is_RingHomomorphism
</pre></blockquote>
<p>
Didn't you also do something with <code>src/sage/combinat/ncsf_qsym/ncsf.py</code>?
</p>
<p>
Anyway, the output of <code>git show HEAD</code> looks good to me. So, I will try <code>make ptest</code> now. Is "crash in pergroup.py" still an issue? We will see...
</p>
TicketmmezzarobbaSat, 30 Nov 2013 16:09:20 GMT
https://trac.sagemath.org/ticket/15303#comment:117
https://trac.sagemath.org/ticket/15303#comment:117
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:116" title="Comment 116">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I see. So, you took the version of <code>src/sage/misc/weak_dictionary.pyx</code> from master, and ...
</p>
<blockquote class="citation">
<p>
All I did manually was to choose the version of <code>morphism.pyx</code> that looked more recent,
</p>
</blockquote>
</blockquote>
<p>
Of <code>weak_dictionary.pyx</code>, sorry (I guess I need to catch up on sleep...). The merge of <code>morphism.pyx</code> was automatic.
</p>
<blockquote class="citation">
<p>
Didn't you also do something with <code>src/sage/combinat/ncsf_qsym/ncsf.py</code>?
</p>
</blockquote>
<p>
No, there was no conflict there either.
</p>
TicketSimonKingSat, 30 Nov 2013 16:28:49 GMT
https://trac.sagemath.org/ticket/15303#comment:118
https://trac.sagemath.org/ticket/15303#comment:118
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:117" title="Comment 117">mmezzarobba</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Didn't you also do something with <code>src/sage/combinat/ncsf_qsym/ncsf.py</code>?
</p>
</blockquote>
<p>
No, there was no conflict there either.
</p>
</blockquote>
<p>
Then I show you what <code>git show HEAD</code> shows me:
</p>
<div class="wiki-code"><div class="code"><pre>commit 2712c53cb68d2668b47ccc923b5a77421ff04bbd
Merge: 528a035 0c6fcdf
Author: Marc Mezzarobba <marc@mezzarobba.net>
Date: Sat Nov 30 14:10:11 2013 +0100
Merge 'trac/master' into ticket/15303
Conflicts:
src/sage/misc/weak_dict.pyx
src/sage/schemes/generic/morphism.py
<span class="gh">diff --cc src/sage/categories/morphism.pyx
index 74f600f,47aa188..a9f44c8
</span><span class="gd">--- a/src/sage/categories/morphism.pyx
</span><span class="gi">+++ b/src/sage/categories/morphism.pyx
</span><span class="gu">@@@ -249,8 -214,58 +290,58 @@@ garbage collection. Please use a copy."
</span> sage: ZZ(x)
-1
"""
- self.codomain().register_conversion(self)
+ self._codomain.register_conversion(self)
<span class="gi">+ # You *must* override this method in all cython classes
+ # deriving from this class.
+ # If you are happy with this implementation (typically
+ # is your domain has generators), simply write:
+ # def __hash__(self):
+ # return Morphism.__hash__(self)
+ def __hash__(self):
+ """
+ Return a hash of this morphism.
+
+ It is the hash of the triple (domain, codomain, definition)
+ where ``definition`` is:
+
+ - a tuple consisting of the images of the generators
+ of the domain if domain has generators
+
+ - the string representation of this morphism otherwise
+
+ AUTHOR:
+
+ - Xavier Caruso (2012-07-09)
+ """
+ domain = self.domain()
+ codomain = self.codomain()
+ try:
+ gens = domain.gens()
+ definition = tuple([self(x) for x in gens])
+ except (AttributeError, NotImplementedError):
+ definition = self.__repr__()
+ return hash((domain, codomain, definition))
+
+ def __richcmp__(left, right, int op):
+ return (<Element>left)._richcmp(right, op)
+
+ cdef int _cmp_c_impl(left, Element right) except -2:
+ if left is right: return 0
+ domain = left.domain()
+ c = cmp(domain, right.domain())
+ if c: return c
+ c = cmp(left.codomain(), right.codomain())
+ if c: return c
+ try:
+ gens = domain.gens()
+ for x in gens:
+ c = cmp(left(x), right(x))
+ if c: return c
+ except (AttributeError, NotImplementedError):
+ raise NotImplementedError
+
+
</span> cdef class FormalCoercionMorphism(Morphism):
def __init__(self, parent):
Morphism.__init__(self, parent)
<span class="gh">diff --cc src/sage/combinat/ncsf_qsym/ncsf.py
index 6478d46,7d84562..febf995
</span><span class="gd">--- a/src/sage/combinat/ncsf_qsym/ncsf.py
</span><span class="gi">+++ b/src/sage/combinat/ncsf_qsym/ncsf.py
</span><span class="gu">@@@ -238,12 -249,11 +249,12 @@@ class NonCommutativeSymmetricFunctions(
</span> sage: elementary(ribbon[2,1,2,1])
L[1, 3, 2] - L[1, 5] - L[4, 2] + L[6]
<span class="gd">- TODO: explain the other changes of bases!
</span><span class="gi">+ .. TODO:: explain the other changes of bases!
</span>
- Here is how to fetch the conversion morphisms::
+ Here is how to fetch the coerce morphisms. Note that by :trac:`15303`, we
+ should use a copy of the maps being used in the coercion system::
- sage: f = complete.coerce_map_from(elementary); f
+ sage: f = copy(complete.coerce_map_from(elementary)); f
Generic morphism:
From: NCSF in the Elementary basis
To: NCSF in the Complete basis
<span class="gh">diff --cc src/sage/schemes/generic/morphism.py
index 3a6c351,09c6bc3..ab59866
</span><span class="gd">--- a/src/sage/schemes/generic/morphism.py
</span><span class="gi">+++ b/src/sage/schemes/generic/morphism.py
</span><span class="gu">@@@ -79,10 -75,12 +79,12 @@@ AUTHORS
</span> #*****************************************************************************
-from sage.structure.element import AdditiveGroupElement, RingElement, Element, generic_power
+from sage.structure.element import AdditiveGroupElement, RingElement, Element, generic_power, parent
from sage.structure.sequence import Sequence
-from sage.categories.homset import Homset
+from sage.categories.homset import Homset, Hom
<span class="gd">- from sage.rings.all import is_RingHomomorphism, is_CommutativeRing, Integer
</span><span class="gi">+ from sage.rings.all import Integer
+ from sage.rings.commutative_ring import is_CommutativeRing
+ from sage.rings.morphism import is_RingHomomorphism
</span> from point import is_SchemeTopologicalPoint
from sage.rings.infinity import infinity
import scheme
</pre></div></div><p>
<code>git blame</code> shows me that the change in ncsf.py seems to be authored by me. But why is <code>git show HEAD</code> showing it?
</p>
TicketmmezzarobbaSat, 30 Nov 2013 16:51:53 GMT
https://trac.sagemath.org/ticket/15303#comment:119
https://trac.sagemath.org/ticket/15303#comment:119
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:118" title="Comment 118">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
<code>git blame</code> shows me that the change in ncsf.py seems to be authored by me. But why is <code>git show HEAD</code> showing it?
</p>
</blockquote>
<p>
Because <code>ncsf.py</code> contains both lines that come from <code>master</code> (i.e., changes introduced by the merge from the point of view of your branch) and lines that come from your branch (i.e. changes w.r.t. master). The two columns of plus/minus/space correspond to these two sets of changes.
</p>
TicketSimonKingSat, 30 Nov 2013 18:09:47 GMTwork_issues deleted
https://trac.sagemath.org/ticket/15303#comment:120
https://trac.sagemath.org/ticket/15303#comment:120
<ul>
<li><strong>work_issues</strong>
<em>Crash in permgroup.py</em> deleted
</li>
</ul>
<p>
Good and bad news. The good news: I did not see a crash in permgroup.py, even though it used to <em>always</em> occur with <code>make ptest</code> (not with other methods of testing). The bad news:
</p>
<pre class="wiki">sage -t src/sage/combinat/ncsf_qsym/qsym.py # 2 doctests failed
sage -t src/sage/schemes/projective/projective_morphism.py # 1 doctest failed
sage -t src/sage/schemes/projective/projective_point.py # 1 doctest failed
sage -t src/sage/rings/finite_rings/finite_field_base.pyx # 1 doctest failed
sage -t src/sage/rings/finite_rings/hom_prime_finite_field.pyx # 3 doctests failed
</pre><p>
The number of failing tests indicates that it could be mostly harmless.
</p>
<p>
I'll soon push the branch (even though it actually is your branch, but I guess it is ok.
</p>
TicketdarijSat, 30 Nov 2013 18:13:03 GMT
https://trac.sagemath.org/ticket/15303#comment:121
https://trac.sagemath.org/ticket/15303#comment:121
<p>
What is broken in qsym.py? I'm asking because I'm editing the file currently.
</p>
TicketSimonKingSat, 30 Nov 2013 19:07:36 GMT
https://trac.sagemath.org/ticket/15303#comment:122
https://trac.sagemath.org/ticket/15303#comment:122
<p>
Oooops, what is that?
</p>
<pre class="wiki">sage -t src/sage/schemes/projective/projective_morphism.py
**********************************************************************
File "src/sage/schemes/projective/projective_morphism.py", line 1326, in sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space.canonical_height
Failed example:
f.canonical_height(Q,badprimes=[2])
Expected:
0.0013538030870311431824555314882
Got:
verbose 0 (3533: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
verbose 0 (3533: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
0.0013538030870311431824555314882
**********************************************************************
1 item had failures:
1 of 16 in sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space.canonical_height
[481 tests, 1 failure, 8.40 s]
----------------------------------------------------------------------
sage -t src/sage/schemes/projective/projective_morphism.py # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 8.6 seconds
cpu time: 7.7 seconds
cumulative wall time: 8.4 seconds
</pre><p>
So, why is the slow toy implementation being used when coercion is changed?
</p>
TicketSimonKingSat, 30 Nov 2013 19:09:03 GMT
https://trac.sagemath.org/ticket/15303#comment:123
https://trac.sagemath.org/ticket/15303#comment:123
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:121" title="Comment 121">darij</a>:
</p>
<blockquote class="citation">
<p>
What is broken in qsym.py? I'm asking because I'm editing the file currently.
</p>
</blockquote>
<p>
Here is the diff that I did to fix the failure:
</p>
<div class="wiki-code"><div xmlns="http://www.w3.org/1999/xhtml" class="diff">
<ul class="entries">
<li class="entry">
<h2>
<a>src/sage/combinat/ncsf_qsym/qsym.py</a>
</h2>
<pre>diff --git a/src/sage/combinat/ncsf_qsym/qsym.py b/src/sage/combinat/ncsf_qsym/qsym.py
index 583ca87..f127c19 100644</pre>
<table class="trac-diff inline" summary="Differences" cellspacing="0">
<colgroup><col class="lineno" /><col class="lineno" /><col class="content" /></colgroup>
<thead>
<tr>
<th title="File a/src/sage/combinat/ncsf_qsym/qsym.py">
a
</th>
<th title="File b/src/sage/combinat/ncsf_qsym/qsym.py">
b
</th>
<td><em> class QuasiSymmetricFunctions(UniqueRepresentation, Parent):</em> </td>
</tr>
</thead>
<tbody class="unmod">
<tr>
<th>2232</th><th>2232</th><td class="l"><span> def __init_extra__(self):</span></td>
</tr><tr>
<th>2233</th><th>2233</th><td class="l"><span> """</span></td>
</tr><tr>
<th>2234</th><th>2234</th><td class="l"><span> Set up caches for the transition maps to and from the monomial</span></td>
</tr>
</tbody><tbody class="mod">
<tr class="first">
<th>2235</th><th> </th><td class="l"><span> basis, and register them as coercions.</span></td>
</tr>
<tr>
<th> </th><th>2235</th><td class="r"><span> basis, and register them as coercions. By :trac:`15303`, we need</span></td>
</tr><tr>
<th> </th><th>2236</th><td class="r"><span> to copy coerce maps before exposing them outside of the coercion</span></td>
</tr><tr class="last">
<th> </th><th>2237</th><td class="r"><span> system.</span></td>
</tr>
</tbody><tbody class="unmod">
<tr>
<th>2236</th><th>2238</th><td class="l"><span></span></td>
</tr><tr>
<th>2237</th><th>2239</th><td class="l"><span> TESTS::</span></td>
</tr><tr>
<th>2238</th><th>2240</th><td class="l"><span></span></td>
</tr><tr>
<th>2239</th><th>2241</th><td class="l"><span> sage: HWL = QuasiSymmetricFunctions(QQ).HazewinkelLambda()</span></td>
</tr><tr>
<th>2240</th><th>2242</th><td class="l"><span> sage: M = QuasiSymmetricFunctions(QQ).Monomial()</span></td>
</tr>
</tbody><tbody class="mod">
<tr class="first">
<th>2241</th><th> </th><td class="l"><span> sage: <del>HWL.coerce_map_from(M)</del></span></td>
</tr>
<tr class="last">
<th> </th><th>2243</th><td class="r"><span> sage: <ins>M2HWL = copy(HWL.coerce_map_from(M)); M2HWL</ins></span></td>
</tr>
</tbody><tbody class="unmod">
<tr>
<th>2242</th><th>2244</th><td class="l"><span> Generic morphism:</span></td>
</tr><tr>
<th>2243</th><th>2245</th><td class="l"><span> From: Quasisymmetric functions over the Rational Field in the Monomial basis</span></td>
</tr><tr>
<th>2244</th><th>2246</th><td class="l"><span> To: Quasisymmetric functions over the Rational Field in the HazewinkelLambda basis</span></td>
</tr>
</tbody><tbody class="mod">
<tr class="first">
<th>2245</th><th> </th><td class="l"><span> sage: <del>M.coerce_map_from(HWL)</del></span></td>
</tr>
<tr class="last">
<th> </th><th>2247</th><td class="r"><span> sage: <ins>HWL2M = copy(M.coerce_map_from(HWL)); HWL2M</ins></span></td>
</tr>
</tbody><tbody class="unmod">
<tr>
<th>2246</th><th>2248</th><td class="l"><span> Generic morphism:</span></td>
</tr><tr>
<th>2247</th><th>2249</th><td class="l"><span> From: Quasisymmetric functions over the Rational Field in the HazewinkelLambda basis</span></td>
</tr><tr>
<th>2248</th><th>2250</th><td class="l"><span> To: Quasisymmetric functions over the Rational Field in the Monomial basis</span></td>
</tr>
</tbody><tbody class="mod">
<tr class="first">
<th>2249</th><th> </th><td class="l"><span> sage: <del>M.coerce_map_from(HWL)</del>(HWL[2])</span></td>
</tr>
<tr class="last">
<th> </th><th>2251</th><td class="r"><span> sage: <ins>HWL2M</ins>(HWL[2])</span></td>
</tr>
</tbody><tbody class="unmod">
<tr>
<th>2250</th><th>2252</th><td class="l"><span> M[1, 1]</span></td>
</tr>
</tbody><tbody class="mod">
<tr class="first">
<th>2251</th><th> </th><td class="l"><span> sage: <del>HWL.coerce_map_from(M)</del>(M[2])</span></td>
</tr>
<tr class="last">
<th> </th><th>2253</th><td class="r"><span> sage: <ins>M2HWL</ins>(M[2])</span></td>
</tr>
</tbody><tbody class="unmod">
<tr>
<th>2252</th><th>2254</th><td class="l"><span> HWL[1, 1] - 2*HWL[2]</span></td>
</tr><tr>
<th>2253</th><th>2255</th><td class="l"><span> """</span></td>
</tr><tr>
<th>2254</th><th>2256</th><td class="l"><span> M = self.realization_of().M()</span></td>
</tr>
</tbody>
</table>
</li>
</ul>
</div></div>
TicketSimonKingSat, 30 Nov 2013 19:23:55 GMT
https://trac.sagemath.org/ticket/15303#comment:124
https://trac.sagemath.org/ticket/15303#comment:124
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15303#comment:122" title="Comment 122">SimonKing</a>:
</p>
<blockquote class="citation">
<blockquote>
<p>
Oooops, what is that?
</p>
</blockquote>
<p>
...
</p>
<blockquote>
<p>
So, why is the slow toy implementation being used when coercion is changed?
</p>
</blockquote>
</blockquote>
<p>
Same problem in <code>sage -t src/sage/schemes/projective/projective_point.py</code>.
</p>
<p>
And I guess the other errors should rather be fixed at <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a>, because they are about "weakened coerce maps".
</p>
TicketgitSun, 01 Dec 2013 21:00:04 GMTcommit changed
https://trac.sagemath.org/ticket/15303#comment:125
https://trac.sagemath.org/ticket/15303#comment:125
<ul>
<li><strong>commit</strong>
changed from <em>528a03535447d67f04dc16d0a22cc38def54f9f1</em> to <em>12e80554ac2d23d7727d315649a698a3cd78f0f4</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=12e8055"><span class="icon"></span>12e8055</a></td><td>Merge branch 'ticket/14711' into ticket/15303
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ee30c20"><span class="icon"></span>ee30c20</a></td><td>Address the "check" keyword of scheme morphisms by name, not position
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d68c5df"><span class="icon"></span>d68c5df</a></td><td>Minor fixes, that became needed since <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a> was not merged quickly enough
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c42b539"><span class="icon"></span>c42b539</a></td><td>Merge branch 'master' into ticket/14711
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2712c53"><span class="icon"></span>2712c53</a></td><td>Merge 'trac/master' into ticket/15303
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=23f18f2"><span class="icon"></span>23f18f2</a></td><td>Merge branch 'master' into ticket/14711
</td></tr></table>
TicketSimonKingSun, 01 Dec 2013 21:32:13 GMT
https://trac.sagemath.org/ticket/15303#comment:126
https://trac.sagemath.org/ticket/15303#comment:126
<p>
Since <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a> has changed, I have merged the new commits from there.
</p>
<p>
And I have included Marc's master merge.
</p>
<p>
Doctests pass for me.
</p>
Ticketvbraun_spamTue, 17 Dec 2013 18:39:51 GMTmilestone changed
https://trac.sagemath.org/ticket/15303#comment:127
https://trac.sagemath.org/ticket/15303#comment:127
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.0</em> to <em>sage-6.1</em>
</li>
</ul>
TicketmmezzarobbaFri, 20 Dec 2013 09:00:15 GMT
https://trac.sagemath.org/ticket/15303#comment:128
https://trac.sagemath.org/ticket/15303#comment:128
<p>
This branch (more precisely, commit 1db6444c33c5b41bf600b6446badd92ddbe3c018) conflicts with that from <a class="closed ticket" href="https://trac.sagemath.org/ticket/10963" title="enhancement: Axioms and more functorial constructions (closed: fixed)">#10963</a> (more precisely, with 9d9cae35053bca7c47466a6f64ee142748eddec1).
</p>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/15303#comment:129
https://trac.sagemath.org/ticket/15303#comment:129
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketrwsSat, 05 Apr 2014 15:36:53 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/15303#comment:130
https://trac.sagemath.org/ticket/15303#comment:130
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>rebase (11 files conflicting)</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/15303#comment:131
https://trac.sagemath.org/ticket/15303#comment:131
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/15303#comment:132
https://trac.sagemath.org/ticket/15303#comment:132
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
Ticket