Opened 8 years ago
Last modified 7 years ago
#15303 needs_work defect
Coercion discovery fails to be transitive
Reported by:  nbruin  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  coercion  Keywords:  
Cc:  SimonKing, robertwb, jpflori  Merged in:  
Authors:  Simon King  Reviewers:  
Report Upstream:  N/A  Work issues:  rebase (11 files conflicting) 
Branch:  u/SimonKing/ticket/15303 (Commits, GitHub, GitLab)  Commit:  12e80554ac2d23d7727d315649a698a3cd78f0f4 
Dependencies:  #14711, #15329, #15331  Stopgaps: 
Description
As found in #14711:comment:134, the following example shows that a combination of register_embedding
and register_coercion
can lead to a failure in transitivity for coercion discovery; also discussed on sagedevel:
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
One workaround is simple: just don't use register_embedding
. However, after #14711, there are different lifetime implications between using register_embedding
and register_coercion
, so this workaround might not be desirable.
Attachments (1)
Change History (133)
comment:1 Changed 8 years ago by
comment:2 followup: ↓ 3 Changed 8 years ago by
It has also been discussed on sagedevel that the existence of a coercion from B to C would change over time. Namely:
 Create B and C. You will not find a coercion, because A is not known yet.
 Create A, registering a coercion from B to A and an embedding of A into C.
 Provided that we fixed the problem of transitivity, we would now find a coercion from B to C via A.
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.
However, one additional complication arises with the current implementation: The absence 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.
Let phi: A > B
and do A.register_embedding(phi)
. Currently, B
is not aware of the existence of phi
. Hence, the backtracking algorithm will currently ignore phi
. We don't want to store phi
as a strong attribute of B
, hence, don't want to put it into B._coerce_from_list
. But perhaps we could create a new attribute of type MonoDict
and store the embedding there? For example B._coerce_embeddings_from[A] = phi
, in addition to A._coerce_embedding = phi
. Since it is a MonoDict
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).
Once this is done, we could change the backtracking so that it not only iterates over B._coerce_from_list
, but it additionally iterates over B._coerce_embeddings_from
.
But what about the problem of caching coercions? We should carefully think if the current scenario (A.register_coercion(B)
plus A.register_embedding(C)
) is the only scenario that could dynamically change the coercion graph. Here, I assume that self.register_embedding()
and self.register_coercion()
are only called during self.__init__()
.
How to make it possible to allow a coercion via a newly created parent?
Perhaps the following would be feasible: If we do A.register_embedding(psi)
, where psi: A > C
, then we clear the coercion cache of C
, in the sense of all cache items stating the absence of a coercion to C
will be deleted.
Note that clearing it in the sense of all cached coercions to C
will be deleted 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.
So, would the suggestion make sense to you?
 Have a new
MonoDict
that stores all coerce embeddings leading into 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.  When registering an embedding, then remove all "there is no coercion" flags from the coercion cache of the codomain.
Hm. Probably this is not good enough. What if we have had D.coerce_map_from(C)
, and had cached the absence of a coercion from B
to D
? After adding A
, we would find a coercion from B
to D
via A
and C
. Hence, cleaning the coercion cache of C
would not be enoughwe would need to clean the coercion cache of all parents into which C
coerces.
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.
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 slowdown.
comment:3 in reply to: ↑ 2 ; followup: ↓ 8 Changed 8 years ago by
Replying to SimonKing:
 Provided that we fixed the problem of transitivity, we would now find a coercion from B to C via A.
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 MonoDict? 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)
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.
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.
However, one additional complication arises with the current implementation: The absence 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.
There are milder ways of invalidating caches: We could mark cached nonexistence with a "coercion graph version number". When a nonexistence 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 nonexistence caches.
For example
B._coerce_embeddings_from[A] = phi
, in addition toA._coerce_embedding = phi
. Since it is aMonoDict
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).
Yes, something along those lines. In fact, since _coerce_embeddings_from
and _coerce_from_list
would serve the same purpose from the perspective of coercion discoveries, I think the entries in _coerce_from_list
should also be added to _coerce_embeddings_from
, because it would simplify the code. By then it would make more sense to call the attribute _coerce_from_to_be_used_in_backtracking
and the list that is now _coerce_from_hash
could be _coerce_from_cached_results
.
By then we should probably be storing ALL maps there in weakened form.
The only function of _coerce_from_list
now is to keep domains alive, so it would be more economical to replace that by a list _domains_to_keep_alive
where we can store strong references to the domains of the corresponding weakened maps that are now in _coerce_from_to_be_used_in_backtracking
So we would end up with (names up for choice):
P._coercion_cache
: MonoDict containing discovered (weakened) maps into P.P._coercion_maps
: MonoDict containing (weakened) maps into P that get used by backtrackingP._domains_to_keep_alive
: List of domains that should be kept alive as long as P lives.P._codomains_to_keep_alive
: List of codomains that should be kept alive as long as P lives. Normally, such codomains Q would have an entry inQ._coercion_maps[P]
. Just storing a map in P._coerce_embedding would also have this effect.
In the present naming system, it wasn't immediately clear to me what purposes _coerce_from_hash
and _coerce_from_list
served, so changing those names could be beneficial.
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 slowdown.
Yes, I don't have any suggestions that I seriously believe would lead to acceptable performance.
comment:4 followup: ↓ 5 Changed 8 years ago by
I was thinking about "versioning" of the coercion graph as well. Perhaps it would be worth trying.
The idea would be: We have one global variable, say, cdef unsigned int coerce_graph_version
. 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 .register_coercion()
and .register_embedding()
.
Instead of storing None
when a coercion can not be found, we store the current version. Hence, if we do mor = self._coerce_from_hash[P]
, a simple isinstance(mor,int)
(or a faster version from the Python API that tests if the type of mor
is exactly int
) will tell us whether the absence of a coercion was cached. If mor==coerce_graph_version
then we know that the cached absence of a coercion is reliable. Otherwise, we need to test.
Would this really be soooo expensive? I don't think so. Of course, it depends on how often we create nonsink nonsource nodesand I doubt that the combined use of .register_embedding()
and .register_coercion()
(which is the only way to create nonsink nonsource) will happen very often.
So, I'd say we simply try.
comment:5 in reply to: ↑ 4 ; followup: ↓ 6 Changed 8 years ago by
Replying to SimonKing:
Would this really be soooo expensive? I don't think so. Of course, it depends on how often we create nonsink nonsource nodesand I doubt that the combined use of
.register_embedding()
and.register_coercion()
(which is the only way to create nonsink nonsource) will happen very often.
I don't think you can establish whether something is a nonsink, since _coerce_from_map
gives programmatic answers about that. Things are very rarely going to be nonsinks, though, since usually ZZ will coerce into them (but ZZ will never be a problem. perhaps we can leave it out of consideration)
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 noncommutative diamonds).
comment:6 in reply to: ↑ 5 Changed 8 years ago by
Replying to nbruin:
I don't think you can establish whether something is a nonsink, since
_coerce_from_map
gives programmatic answers about that.
Perhaps I have not been clear. A nonsink nonsource is something that has both inarrows (i.e., is codomain of a registered coercion or coerce embedding) and outarrows (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.
But I actually think that your idea is better anyway:
A start might be to only version up on "embedding" creations.
It seems to me that this versioning would be complete under reasonable assumptions, based on the following lemma.
Lemma
Assume for all parents P
, Q
, P.register_coercion(Q)
will be done in P.__init__()
, but not later. Assume that parents R
and S
exist at time t_0
, but there is no path from R
to S
in the coerce digraph at time t_0
. Assume that between time t_0
and time t_1
, .register_embedding()
has never been called. Then, there is no path from R
to S
in the coerce digraph at time t_1
.
Proof
Proof be contradiction. We assume that there is a path from R
to S
at time t_1
. Hence, this path contains an arrow a
that has been added to the coerce digraph after t_0
. Since no register_embedding()
has occurred between t_0
and t_1
, all arrows created between t_0
and t_1
have been added by register_coercion()
. But by hypothesis, register_coercion()
is only called during __init__
of the codomain.
Hence, all arrows created between t_0
and t_1
end at parents created after t_0
. Therefore, a path in the coerce digraph at time t_1
that contains a
will necessarily end at a parent that has been created after t_0
. This is a contradiction, since S
has already existed at time t_0
q.e.d.
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 noncommutative diamonds).
We could express in the documentation that one should call register_coercion
only in the initialisation. Since register_embedding
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.
comment:7 Changed 8 years ago by
 Dependencies set to #14711
comment:8 in reply to: ↑ 3 Changed 8 years ago by
Replying to nbruin:
For example
B._coerce_embeddings_from[A] = phi
, in addition toA._coerce_embedding = phi
. Since it is aMonoDict
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).Yes, something along those lines. In fact, since
_coerce_embeddings_from
and_coerce_from_list
would serve the same purpose from the perspective of coercion discoveries, I think the entries in_coerce_from_list
should also be added to_coerce_embeddings_from
, because it would simplify the code. By then it would make more sense to call the attribute_coerce_from_to_be_used_in_backtracking
and the list that is now_coerce_from_hash
could be_coerce_from_cached_results
.
Or shorter: _coerce_from_backtracking
and _coerce_from_cache
.
By then we should probably be storing ALL maps there in weakened form.
Probably.
The only function of
_coerce_from_list
now is to keep domains alive, so it would be more economical to replace that by a list_domains_to_keep_alive
where we can store strong references to the domains of the corresponding weakened maps that are now in_coerce_from_to_be_used_in_backtracking
I have introduced Parent._registered_domains
for exactly this purpose, at #14711. So, we should extend its use.
P._codomains_to_keep_alive
: List of codomains that should be kept alive as long as P lives. Normally, such codomains Q would have an entry inQ._coercion_maps[P]
. Just storing a map in P._coerce_embedding would also have this effect.
Yes, and that's why I don't think we need P._codomains_to_keep_alive
(I'd prefer the name P._registered_codomains
). Even in weakened maps, we have a strong reference to the codomain.
comment:9 followup: ↓ 12 Changed 8 years ago by
PS: We also have convert_from_list
, and I guess we should proceed similarly for coerce_from_list
.
comment:10 Changed 8 years ago by
With the branch that I have just attached, one gets
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.
What has been done in the patch:
 renaming of attributes (
_coerce_from_backtracking
etc)  do not use a list, but use a
MonoDict
for all morphisms that are supposed to be fundamental for backtracking. There is a list_registered_domains
, so that domains of registered coercions are kept alive by the codomain, but the domain of a registered embedding is not kept alive by the codomain.
Missing: Tests and versioning.
comment:11 Changed 8 years ago by
 Branch set to u/SimonKing/ticket/15303
 Created changed from 10/17/13 22:06:13 to 10/17/13 22:06:13
 Modified changed from 10/20/13 13:03:37 to 10/20/13 13:03:37
comment:12 in reply to: ↑ 9 Changed 8 years ago by
 Commit set to dcd8d68fb30f752bcd595d73fe2d3925e7db671f
Replying to SimonKing:
PS: We also have
convert_from_list
, and I guess we should proceed similarly forcoerce_from_list
.
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.
If we want a memory leakfree implementation I suspect having conversion without lifetime implications in either direction is required. Definitely material for another ticket.
Last 10 new commits:
[changeset:dcd8d68]  Use registered embeddings for backtracking in the coercion model 
[changeset:85cf7e8]  Merge branch 'ticket/14711' into ticket/15303 
[changeset:364b985]  Add warning to string repr of weakened maps. Implement copying for *all* kinds of maps. 
[changeset:5168cfd]  Generic copy method for maps, using _update_slots Use a cdef _codomain, since the codomain is strongly refed anyway Add doctests 
[changeset:452d216]  Add docs to SchemeMorphism? 
[changeset:05fb569]  Change SchemeMorphism? back (to cope with a Cython bug), copying the new code from sage.categories.map.Map 
[changeset:8fd09d5]  Copying of PolynomialBaseringInjection? and FormalCompositeMap? 
[changeset:be37145]  Let SchemeMorphism? inherit from Morphism, not from Element 
[changeset:0f38a2c]  Keep strong reference to codomain of weakened coerce maps Keep strong reference to domains of *registered* coercions 
[changeset:a53261d]  Keep a strong reference to the codomain of PrecomposedAction? 
comment:13 Changed 8 years ago by
 Commit changed from dcd8d68fb30f752bcd595d73fe2d3925e7db671f to f837cbee8f81c4946a92193c73e86449c53515d9
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:f837cbe]  Store a version number for the coercion cache, depending on the registered embeddings 
comment:14 followup: ↓ 16 Changed 8 years ago by
 Status changed from new to needs_review
I have pushed a new commit that implements version numbers for the coercion cache, and I added a doctest along the following lines:
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.
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).
TODO:
 Add documentation, stating that registering of coercions should only be done during initialisation, and that registering of embeddings shouldn't be done too often.
 Run all doctestssince playing with the coercion digraph is asking for trouble, I wouldn't be surprised about bad surprises
:P
 Important: Get timings for examples that should be most sensitive against slowdowns in coercion.
comment:15 Changed 8 years ago by
I already found that some test fails when s = SymmetricFunctions(QQbar).s()
is done. "Of course", the error only occurs in sage t src/sage/combinat/sf/sfa.py
, but not if one just does s = SymmetricFunctions(QQbar).s()
in an interactive session...
comment:16 in reply to: ↑ 14 Changed 8 years ago by
 Important: Get timings for examples that should be most sensitive against slowdowns in coercion.
Looking at what happens for number fields, I have the impression that QQ._populate_coercion_lists_
is most frequently used to supply embeddings (I'm not getting many hits on direct calls to !register_embedding, see below)
The only two classes I have been able to identify that actually install embeddings are numberfields (and not all of them) and !AbelianGroupWithValues_class
So, assuming that the version check itself is lightningfast (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.
There's AdditiveAbelianGroupWrapper which does an _unset_coercions_used
together with a register_embedding
(registering an "embedding" of the wrapper into the wrapped)
There's also UniversalCyclotomicField which registers an embedding into QQbar upon init, so that shouldn't really affect versioning.
comment:17 Changed 8 years ago by
 Status changed from needs_review to needs_work
 Work issues set to analyse recursion error
The following runs into an infinite loop:
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)
comment:18 Changed 8 years ago by
Shorter:
sage: UCF.<E> = UniversalCyclotomicField() sage: phi = copy(QQbar.coerce_map_from(UCF)) sage: x = E(5) sage: phi(x)
Hence, we do have a map, but applying it will run into a loop.
comment:19 Changed 8 years ago by
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.
comment:20 Changed 8 years ago by
Further boiled down:
sage: psi = QQbar.coerce_map_from(ZZ) sage: psi(1) <infinite loop>
comment:21 followup: ↓ 22 Changed 8 years ago by
Aha!
With my current branch, the coerce map from ZZ
to QQbar
goes via the universal cyclotomic field, if one has created the universal field before putting the coercion into the cache.
Obvious reason: With my patch, both registered coercions and registered embeddings are used for backtracking, in order to fix the example of the ticket description. However, if 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".
So, modified suggestion: We should not put both registered coercions and registered embeddings into codomain._coerce_from_backtracking
, but we should have two separate containers, and should look for the coerce embeddings only if no registered coercions are left.
Rationale: We suppose that registering coercions happens during initialisation of the codomain, whereas registering an embedding will happen after 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 codomainand these are the maps registered during creation of the codomain.
comment:22 in reply to: ↑ 21 Changed 8 years ago by
Replying to SimonKing:
Rationale: We suppose that registering coercions happens during initialisation of the codomain, whereas registering an embedding will happen after 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 codomainand these are the maps registered during creation of the codomain.
I don't think that rationale is quite valid for the way it gets used. If we do
a+b
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!)
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!).
For your suggestion to fit in such a model, we would need that:
 any path including an embedding is higher cost that a path without.
 if a path has been discovered, new paths between the same parents that may arise by graph mutations are higher cost
It's not immediately clear to me that those assumptions are valid.
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 reallife situation that is actually affected by it".
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)
comment:23 Changed 8 years ago by
The example of QQbar.coerce_map_from(ZZ)
fails as follows.
We want that the coercion is determined by QQbar._coerce_map_from_(ZZ)
(which returns True). But apparently (with my current patch, at least), the backtracking has preference over what is returned by _coerce_map_from_
. I don't understand the reason, yet.
comment:24 Changed 8 years ago by
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:
sage: UCF.<E> = UniversalCyclotomicField() sage: psi = QQbar.coerce_map_from(ZZ) sage: psi._coerce_cost 30
versus
sage: psi = QQbar.coerce_map_from(ZZ) sage: psi._coerce_cost 100
EDIT: ... and this explains why the coercion model does not rely on the result of QQbar._coerce_map_from_(ZZ)
(returning a map of cost 100), while the composite map only has the cost 30
comment:25 Changed 8 years ago by
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 DefaultConvertMap
are between 100 and 400. And it seems to me that this is not well balanced.
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 compositionwhich would of course normally be slower than a single map!
This decision has been made 5 years ago. Perhaps the coerce costs should be refactored?
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.
comment:26 Changed 8 years ago by
 Cc robertwb added
Robert, perhaps you can comment on the reasons for choosing the coerce costs for DefaultConvertMap
and friends? Why are the costs so much higher than for a generic map?
comment:27 followup: ↓ 29 Changed 8 years ago by
It seems to me that the ._coerce_costs
of a map are largely ignored. Namely, in .discover_coercion()
, we have a parameter num_paths
: If num_paths
paths in the coercion graph are found by backtracking, then the path with the least ._coerce_costs
is returned. But since num_paths=1
, in fact the first found coercion is returned.
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 userprovided morphism is compared with the other morphism.
This just isn't fair!!! I believe that the userprovided morphism should at least have the same priority as a morphism found by backtracking.
Two approaches, that are not mutually exclusive:
 Amend the coerce costs, so that a simple map has less costs than a composite map, unless there is a very good reason.
 Let the userprovided morphism count for the number of morphisms found in
.discover_coercion()
. Hence, ifnum_paths=1
and the user provides a morphism, then the maximal number of pathstobeconsidered is attained and hence the userprovided morphism is returned without backtracking.
I think the second point is more important, and I will implement it now.
comment:28 Changed 8 years ago by
Another issue we might eventually 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.
comment:29 in reply to: ↑ 27 Changed 8 years ago by
Replying to SimonKing:
 Let the userprovided morphism count for the number of morphisms found in
.discover_coercion()
. Hence, ifnum_paths=1
and the user provides a morphism, then the maximal number of pathstobeconsidered is attained and hence the userprovided morphism is returned without backtracking.I think the second point is more important, and I will implement it now.
Note one remark in the code:
# 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.
The _populate_coercion_lists_
data are also put into _coerce_from_cache
. Hence, these data will have priority over _coerce_map_from_
in self.coerce_map_from(other)
. Therefore, self.discover_coerce_map_from(other)
will only be called if there are no relevant _populate_coercion_lists_
data.
Hence, I believe that the remark is not valid, and will remove it.
comment:30 Changed 8 years ago by
 Commit changed from f837cbee8f81c4946a92193c73e86449c53515d9 to 74821fe5409c3104b5d6eb7407a8287d54170df9
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:74821fe]  Give userprovided coerce maps the same priority than to a coerce map found by backtracking 
comment:31 Changed 8 years ago by
 Status changed from needs_work to needs_review
 Work issues analyse recursion error deleted
The intermediate problem has been added as a doctest.
comment:32 Changed 8 years ago by
 Status changed from needs_review to needs_work
 Work issues set to Analyse recursion error
As it turns out, the last commit fixes one error, but the more problematic errors persist.
comment:33 Changed 8 years ago by
The following sequence of commands results in a "recursion depth exceeded" (some other errors are expected, the example is taken from the doctests):
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]
Trying to minimise the example now...
comment:34 Changed 8 years ago by
PS: Some of the commands seem to have a rather sluggish behaviour. Perhaps the example is also good for detecting a regression?
comment:35 Changed 8 years ago by
I observe that the example sometimes works and sometimes fails. This seems to indicate that one "randomness" in my code is problematic.
Namely, with the current commits, the coercions that are used by the backtracking algorithm are stored in a MonoDict
(codomain._coerce_from_backtracking
). 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.
I am not sure what I shall think of it. My first impulse: It does not matter what map is returned as result of backtracking, but in any case it must be a valid map. In the example of comment:32, 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.
comment:36 followup: ↓ 37 Changed 8 years ago by
I think I see a potential problem. In sage.combinat.sf.k_dual.DualkSchurFunctions.__init__
, there is
kHLP = kBoundedRing.kHallLittlewoodP() self.module_morphism(self._dks_to_khlp_on_basis,codomain=kHLP).register_as_coercion()
Hence, a coercion is registered on kHLP
after 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.
Hence, I will change Map.register_as_coercion()
so that it increases the cache version number.
comment:37 in reply to: ↑ 36 Changed 8 years ago by
Replying to SimonKing:
Hence, I will change
Map.register_as_coercion()
so that it increases the cache version number.
I think it should be done, but it turns out that it does not fix the problem.
comment:38 followup: ↓ 39 Changed 8 years ago by
I found that the example above has the following structure:
 We have parents
A
andB
. We search a coercionA > B
. B
stores coercions (for backtracking) from parentsC
andD
. OnlyC
is registered byB.register_coercion(...)
, whereas the coercion fromD
was registered in a different way, after initialisation ofB
. There is a coercion
phi
fromA
toC
and a coercionpsi
fromA
toD
. Sage knows thatphi
andpsi
exist. However, callingpsi
internally relies on a coercion fromA
toB
.  The coercion from
A
toB
must go viaC
, starting withphi
. Otherwise, if one tries to coerceA
viaD
intoB
, callingpsi
(as part of a composite coerce map) will result in an infinite recursion.
Problem with the current commits
It currently depends on a random choice whether the backtracking algorithm first goes back from B
to C
(and finds a good coerce map from A
) or from B
to D
(and finds a map from A
that crashes).
We need to give a hint to the coercion system that it should try C
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 MonoDict
. Hence, the order of registration has no implication on the order of execution.
Suggested solution
This brings me back to the idea to keep a list of registered coercions, that would automatically keep the domain of registered coercions alive, and a MonoDict
of other coercions used for backtracking (e.g. registered embeddings), whose domains are not necessarily kept alive.
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.
Perhaps useful
We have self.register_coercion(mor)
, that adds a coercion to the list of coercions that the backtracking algorithm is starting with. In addition, we might have a method self.additional_coercion(mor)
, that will put mor
only in the MonoDict
of coercions that the backtracking algorithm is considering only later.
Would this be useful? If "yes", what lifetime implications do we want? Shall the domain of an "additional coercion" be kept alive?
comment:39 in reply to: ↑ 38 ; followup: ↓ 40 Changed 8 years ago by
Replying to SimonKing:
I found that the example above has the following structure:
 We have parents
A
andB
. We search a coercionA > B
.B
stores coercions (for backtracking) from parentsC
andD
. OnlyC
is registered byB.register_coercion(...)
, whereas the coercion fromD
was registered in a different way, after initialisation ofB
. There is a coercion
phi
fromA
toC
and a coercionpsi
fromA
toD
. Sage knows thatphi
andpsi
exist. However, callingpsi
internally relies on a coercion fromA
toB
. The coercion from
A
toB
must go viaC
, starting withphi
. Otherwise, if one tries to coerceA
viaD
intoB
, callingpsi
(as part of a composite coerce map) will result in an infinite recursion.
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, implementationspecified) 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.
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.
Since it seems we need a tiebreaker 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.
So it seems to me that the "theoretically" better solution (which may be prohibitive costwise!) would be:
 recalibrate some of the costs
 take the costs properly into account
 probably do so via breadthfirst (for finding shortest path, it allows much better pruning)
I think that should solve the A>D problem as well.
comment:40 in reply to: ↑ 39 ; followup: ↓ 41 Changed 8 years ago by
Replying to nbruin:
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.
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?
As you observe, the coercion A>D is in actuality derived from A>B, but apparently not by a straightforward composition.
Correct. When calling the coercion A>D, some arithmetic is performed on underlying data, this involves coercion, and this is when A>B occurs.
However, doesn't that mean that if A>D is discovered, then A>B must be discovered already?
No. You can easily define a map and then compose with other maps, without calling it. A>B is only needed for calling A>D, but not for definining A>D.
If A>D relies on A>B, I think part of registering A>D is ensuring that A>B is discovered.
Yes, and how to model this?
Since it seems we need a tiebreaker 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.
... but only if, in addition, we actually use the coerce costs in discover_coercion()
, rather then returning the first map that came across.
So it seems to me that the "theoretically" better solution (which may be prohibitive costwise!) would be:
 recalibrate some of the costs
 take the costs properly into account
 probably do so via breadthfirst (for finding shortest path, it allows much better pruning)
I think that should solve the A>D problem as well.
Perhaps.
 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.
 Calibrating the costs, such that
A>C>B
is guaranteed to have less cost thanA>D>B
for any example in whichA>C
is independent of butA>D
is dependent onA>B
, requires a casebycase analysis. Not very practical, and moreover choosing parameters such that "it works" is kind of arbitrary. This is not a very clean solution either.
Before we have implemented breadth first search, I believe it would be more practical to say that we should
 give preference to maps registered during initialisation (
P.register_coercion(mor)
)  give less preference to maps registered after initialisation (
mor.register_as_coercion()
)  give least preference to registered embeddings (I am talking about backtracking here, not pushout).
This is practical because this approach is close to what is done in vanilla Sage. The current registration order is such that "it works".
comment:41 in reply to: ↑ 40 Changed 8 years ago by
Replying to SimonKing:
If A>D relies on A>B, I think part of registering A>D is ensuring that A>B is discovered.
Yes, and how to model this?
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.
 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.
Just keep track of all discovered shortest paths (ordered by domain) into the codomain, and try to extend the shortest path. Merge the newfound 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.
 Calibrating the costs, such that
A>C>B
is guaranteed to have less cost thanA>D>B
for any example in whichA>C
is independent of butA>D
is dependent onA>B
, requires a casebycase analysis. Not very practical, and moreover choosing parameters such that "it works" is kind of arbitrary. This is not a very clean solution either.
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.
This is practical because this approach is close to what is done in vanilla Sage. The current registration order is such that "it works".
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.
The current registration order is such that "it works".
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.
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.
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.
If you want a historysensitive 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?
comment:42 Changed 8 years ago by
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.
comment:43 Changed 8 years ago by
I think the attached branch is a progress towards a coercion system with a cleaner model. Even if there would remain rough edges.
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.
Currently, I am studying the following very simple example:
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>
comment:44 Changed 8 years ago by
Shorter:
sage: L.<i> = NumberField(x^2 + 1) sage: K = NumberField(L(i/2+3).minpoly(), names=('i0',), embedding=L(i/2+3))
comment:45 followup: ↓ 46 Changed 8 years ago by
I wonder: Do we really insist on making the example from the ticket description work?
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.
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 not use .register_embedding()
, but do something like this:
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
Do you agree on this change of aim?
comment:46 in reply to: ↑ 45 ; followup: ↓ 47 Changed 8 years ago by
Replying to SimonKing:
I wonder: Do we really insist on making the example from the ticket description work?
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.
Ah right, you're saying there are certain "almost universal terminal" objects that tend to have a very large indegree. Doing backtracking from them would be a rather expensive operation (independent of whether it's breadthfirst (cheapestfirst is a better name) or depthfirst). 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?
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 not use
.register_embedding()
, but do something like this: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
Hm, where does AtoC.register_as_coercion()
fit in with the "only initialize coercions upon __init__
of the parent"?
Do you agree on this change of aim?
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.
comment:47 in reply to: ↑ 46 Changed 8 years ago by
Hi!
First of all, note that the latest recursion errors refer to notyetcommitted code. It could be that by copyandpasting I somehow destroyed the backtracking algorithm by not properly marking a used arrow as nottobetestedagain. Thus the recursion.
Replying to nbruin:
Hm, where does
AtoC.register_as_coercion()
fit in with the "only initialize coercions upon__init__
of the parent"?
Both AtoC.register_as_coercion()
and A.register_embedding(AtoC)
add an arrow to the coerce digraph after 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.
comment:48 Changed 8 years ago by
OUCH!!
I just found that discover_coerce_map_from
did not mark arrows as "used" at all! Hence, there is (another) bug in our backtracking algorithm.
comment:49 Changed 8 years ago by
 Work issues changed from Analyse recursion error to Implement backtracking properly
In #12969, 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 temporarily forbidden, so that an action was easily found after allowing the paths again.
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 must be implemented here, since otherwise we will hardly be able to add the feature that this ticket is about.
comment:50 Changed 8 years ago by
Oops, I spoke too soon. #12969 was in fact about backtracking for coerce maps (not for actions), and forbidden paths are in fact declared (_register_pair(self, S,"coerce")
) if discover_coerce_map_from()
is called by coerce_map_from()
.
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 nonunique parents). Hence, _register_pair
should be rewritten as well, so that only identity and not equality counts. That's for a different ticket.
comment:51 Changed 8 years ago by
I think I have located the problem: If the pair X,Y
already is registered and we do X.coerce_map_from(Y)
, then None
should be returned (but of course not cached). But currently it is still attempted to find a coercion from Y
to X
, resulting in an infinite loop.
comment:52 Changed 8 years ago by
As it turns out, the recursion again occurs when calling (not when constructing!) a coerce map. Nevertheless, I think one should speedup the backtracking based on comparison by identity. Perhaps one could even use a TripleDict
for storage of temporarily forbidden paths.
The problematic map is a DefaultConvertMap_unique
, 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.
But in one of my commits, I made sure that the backtracking is not attempted if self._coerce_map_from_(S)
returns True
or returns an actual map. The rationale for this change was that self._coerce_map_from_(S)
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.
In other words: In vanilla Sage, dependencies between arrows of the coerce digraph are implicitly declared by
 choosing an order of registered coercions
 avoiding
DefaultConverMap
and friends.
I am not happy about the existing way of implicit declaration of dependencies and think we should do better!
comment:53 followups: ↓ 54 ↓ 65 Changed 8 years ago by
I think the following is both reasonable and reasonably close to the status quo:
 if
_coerce_map_from_
returns a map, then we trust that it is a good choice.  if
_coerce_map_from_
returns True, then we do not necessarily trust thatself._generic_convert_map(S)
is the best choice. So, we test if backtracking yields anything better.
I found a couple of cases in which _coerce_map_from_
returned _generic_convert_map
(e.g. for CC
!). It seems to me that one should return True
instead.
comment:54 in reply to: ↑ 53 ; followup: ↓ 58 Changed 8 years ago by
Replying to SimonKing:
I think the following is both reasonable and reasonably close to the status quo:
 if
_coerce_map_from_
returns a map, then we trust that it is a good choice. if
_coerce_map_from_
returns True, then we do not necessarily trust thatself._generic_convert_map(S)
is the best choice. So, we test if backtracking yields anything better.
Can we explain these rules purely in terms of the coercion graph? Does _coerce_map_from_(..)==True
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).
My hunch is that the undesirability of a certain edge can simply be expressed in its cost and that we only need a 1dimensional cost parameter to capture all that we need [we'd have to think about calibration, though].
Above, you also talk about "forbidden" and "temporarily forbidden" paths. Are those part of the depthfirst 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.
comment:55 followup: ↓ 60 Changed 8 years ago by
Good(?) news: I can track down the error to the following in vanilla Sage.
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__
The point is that the with my patch, the above code is executed during construction of K, in order to internally construct something. I'll ask on sagent whether this code should 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 TypeError
(or ValueError
) raised, without infinite recursion.
comment:56 Changed 8 years ago by
 Cc jpflori added
comment:57 Changed 8 years ago by
Great work, all of this looks really fine.
comment:58 in reply to: ↑ 54 ; followup: ↓ 59 Changed 8 years ago by
Replying to nbruin:
Above, you also talk about "forbidden" and "temporarily forbidden" paths. Are those part of the depthfirst path discovery?
Of course. By "temporarily forbidden", I mean those that have already been visited in the depthfirst search and shall thus not be visited again during the same search. Thus "temporarily", because in the next search they could be visited.
That would be an even better reason to see if we can get a "cheapest first" search in, since that naturally avoids cycles.
How would that be?
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.
Replying to SimonKing: Can we explain these rules purely in terms of the coercion graph?
Somehow (see below).
Does
_coerce_map_from_(..)==True
somehow indicate an edge with a property (colour?) that should be avoided or an edge with the cost modified (increased)?
Not at all. _coerce_map_from_
is only called if there is no edge. Note that "long time ago" (in one of the posts above) I talked about "shortcuts" in the coerce digraph. _coerce_map_from_
is for the shortcuts, not for the edges.
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 y._coerce_map_from_(x)
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.
This situation is easy. Difficulties only arise if x and y belong to the same 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 y._coerce_map_from_(x)
, or y._coerce_map_from_(x)
returns True. In the latter case, it means that we can use y._generic_convert_map(x)
for coercion.
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.
comment:59 in reply to: ↑ 58 ; followup: ↓ 61 Changed 8 years ago by
Replying to SimonKing:
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.
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.
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
y._coerce_map_from_(x)
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.This situation is easy. Difficulties only arise if x and y belong to the same 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
y._coerce_map_from_(x)
, ory._coerce_map_from_(x)
returns True. In the latter case, it means that we can usey._generic_convert_map(x)
for coercion.
(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).
If y._coerce_map_from_(x)
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 _coerce_map_from_
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.
Perhaps one way out is if _coerce_map_from_
indeed only returns "shortcuts": paths between nodes that exist otherwise, so only in the situation you describe as "Difficult".
If we cannot trust that the return map from _coerce_map_from_
(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.
I agree that relying on conversion maps in the coercion framework looks very suspect: conversions are supposed to be trying coercion first!
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.
comment:60 in reply to: ↑ 55 Changed 8 years ago by
Replying to SimonKing:
Good(?) news: I can track down the error to the following in vanilla Sage.
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__The point is that the with my patch, the above code is executed during construction of K, in order to internally construct something. I'll ask on sagent whether this code should 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
TypeError
(orValueError
) raised, without infinite recursion.
I suppose you mean
sage: number_field_morphisms.EmbeddedNumberFieldMorphism(K,L)
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.
The following already does work:
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
The latter suggests that the routine does take some liberties. For K we get
sage: number_field_morphisms.EmbeddedNumberFieldMorphism(K,K) RuntimeError: maximum recursion depth exceeded while calling a Python object
so the difference in behaviour between L and K seems dodgy.
comment:61 in reply to: ↑ 59 ; followup: ↓ 62 Changed 8 years ago by
Replying to nbruin:
Well, you could hold off on actually creating the map composition until you've determined the lowest cost path.
No, because K._coerce_map_from_(L)
gives you shortcuts. It may very well be that it returns a map that is much "cheaper" then a composition of registered coercions and registered embeddings leading from L to K.
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 R1._coerce_map_from_(L)
, ..., Rn._coerce_map_from_(L)
for shortcuts.
Hence, it is not enough to assign costs to arrows in the digraph.
(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).
Correct.
If
y._coerce_map_from_(x)
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.
No. This is exactly the digraphwithshortcuts model I kept talking about since comment 84 of #14711 (hence, since 3 weeks). Since then, I used the term "digraph model" only as an abbreviation of the lengthy term "digraphwithshortcuts model".
If we have a coercion path X>Z>Y where the coercion from Y to Z can only be found using
_coerce_map_from_
You mean from Z to Y?
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.
Yes, which is part of the specification of the digraphwithshortcuts model.
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 shortcut Z>Y into an actual arrow of the digraph.
However, I could also imagine that this would have two disadvantages:
 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".
 The list of mapstobeconsidered in the backtracking algorithm grew. Hence, it would increase the running time for detecting a coerce map.
Perhaps one way out is if
_coerce_map_from_
indeed only returns "shortcuts": paths between nodes that exist otherwise, so only in the situation you describe as "Difficult".
I don't understand what you mean by this.
In vanilla Sage, _coerce_map_from_
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").
If we cannot trust that the return map from
_coerce_map_from_
(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.
I think I have already described what is currently done:
 It is tested whether there is a shortcut phi (either explicitly or implicitly).
 Even if phi is found, backtracking is performed. Backtracking "goes back" according to the registered coercions, and may involve shortcuts by recursion. Let's call psi the first map found by backtracking (if there is any).
 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.
My current commits (at least those I have at home) change it as follows
 If
_coerce_map_from_
explicitly returns an actual map, then the backtracking search is not performed, but it is trusted that the map is good to be used.  If
_coerce_map_from_
returns True, then it says implicitly that_generic_convert_map
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.  Registered embeddings are used for backtracking, too, whereas vanilla Sage only uses registered coercions.
We might play with the idea of extending the last point, namely: Turn the shortcuts 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 slowdown of the backtracking.
I agree that relying on conversion maps in the coercion framework looks very suspect: conversions are supposed to be trying coercion first!
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 _generic_convert_map
, cache this map in _coerce_from_cache
, and henceforth use this map for coercion (and of course for conversion, too)".
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_.
I disagree.
It can certainly not be the only coercion hook one provides if we want to have a digraph model.
If we want to keep the current digraphwithshortcuts model, then we indeed need at least two hooks: One that adds arrows to the digraph, and one that provides shortcuts. In my branch, I suggest to extend the role of registered embeddings, namely: To make them actual arrows, to be used in backtracking.
comment:62 in reply to: ↑ 61 ; followup: ↓ 63 Changed 8 years ago by
Replying to SimonKing:
No, because
K._coerce_map_from_(L)
gives you shortcuts. It may very well be that it returns a map that is much "cheaper" then a composition of registered coercions and registered embeddings leading from L to K.
So shouldn't the rule be: If K._coerce_map_from_(L)
returns something then one of the following must be true
 There is a registered coercion from L to K
 There is a registered embedding from L to K
 For any structure M that coerces into L, K._coerce_map_from_(M) also returns something.
i.e., either the coercion system has enough information to compute transitive closures by itself or _coerce_map_from_
ensures transitive closure by itself already.
Hence, it is not enough to assign costs to arrows in the digraph.
No, "shortcut" paths returned by _coerce_map_from_
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).
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.
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.
No. This is exactly the digraphwithshortcuts model I kept talking about since comment 84 of #14711 (hence, since 3 weeks). Since then, I used the term "digraph model" only as an abbreviation of the lengthy term "digraphwithshortcuts model".
This makes me wonder what exactly the axioms of this "digraphwithshortcuts model" is. I can see how "digraphwithshortcuts" 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 "digraphwithcosts" I can see a "digraphwithcostsandshortcuts" 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).
You mean from Z to Y?
Yes, sorry.
Yes, which is part of the specification of the digraphwithshortcuts model.
My conclusion would be that our digraphwithshortcuts implementation is failing to properly implement a straight digraph model.
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 shortcut Z>Y into an actual arrow of the digraph.
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).
Perhaps one way out is if
_coerce_map_from_
indeed only returns "shortcuts": paths between nodes that exist otherwise, so only in the situation you describe as "Difficult".I don't understand what you mean by this.
Hopefully my explanation above now clarifies this: In my opinion "withshortcuts" 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.
I think I have already described what is currently done:
 It is tested whether there is a shortcut phi (either explicitly or implicitly).
 Even if phi is found, backtracking is performed. Backtracking "goes back" according to the registered coercions, and may involve shortcuts by recursion. Let's call psi the first map found by backtracking (if there is any).
 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.
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 _coerce_map_from_
ensures the closure by itself.
That means that providing coercions (just) via _coerce_map_from_
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.
My current commits (at least those I have at home) change it as follows
 If
_coerce_map_from_
explicitly returns an actual map, then the backtracking search is not performed, but it is trusted that the map is good to be used.
I think that's a reasonable thing to do.
 If
_coerce_map_from_
returns True, then it says implicitly that_generic_convert_map
could in principle be used for coercion, but there might be better options.
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 abovedescribed closed property of _coerce_map_from_
.
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_.
I disagree.
What other purpose does _coerce_map_from_
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.
OK, above I think we have identified that _coerce_map_from_
serve another purpose: Providing paths into a parent programmatically, leaving transitive closure properties as a responsibility to the implementor of the specific _coerce_map_from_
routine.
Conjecture: (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., Y._coerce_map_from_(X)
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).
The cost in this approach is that _coerce_map_from_
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]
comment:63 in reply to: ↑ 62 ; followup: ↓ 64 Changed 8 years ago by
Replying to nbruin:
So shouldn't the rule be: If
K._coerce_map_from_(L)
returns something then one of the following must be true
 There is a registered coercion from L to K
 There is a registered embedding from L to K
Better: A sequence of registered embeddings and coercions.
 For any structure M that coerces into L, K._coerce_map_from_(M) also returns something.
I think so.
Hence, it is not enough to assign costs to arrows in the digraph.
No, "shortcut" paths returned by
_coerce_map_from_
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).
Well, the point I wanted to make is: One needs to construct the maps, because only the map know about their costs.
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.
Perhaps. But it may also affect lifetime implications.
comment:64 in reply to: ↑ 63 Changed 8 years ago by
Replying to SimonKing:
Well, the point I wanted to make is: One needs to construct the maps, because only the map know about their costs.
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 _coerce_map_from_
. The only case where we have to estimate the cost is when we get the existence of a map via K._coerce_map_from_(L)==True
, but in that case I expect the cost is a fixed number anyway, because it's a generically constructed map.
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.
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.
Your "don't consider other maps coming into K
if we're getting an actual map back from K._coerce_map_from_(L)
" is then simply an assumption that K._coerce_map_from_(L)
returns the cheapest map available. I think it helps making such assumptions about the coercion discovery algorithm explicit.
comment:65 in reply to: ↑ 53 ; followup: ↓ 67 Changed 8 years ago by
Replying to SimonKing:
I think the following is both reasonable and reasonably close to the status quo:
 if
_coerce_map_from_
returns a map, then we trust that it is a good choice. if
_coerce_map_from_
returns True, then we do not necessarily trust thatself._generic_convert_map(S)
is the best choice. So, we test if backtracking yields anything better.
Unfortunately, that doesn't seem to be a very good heuristic because it's not stable: _coerce_map_from_
is supposed to do some backtracking on its own, so if A._coerce_map_from(B)
happens to consider another parent C
that coerces into A
and find that C._coerce_map_from(B)==True
, 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.
comment:66 Changed 8 years ago by
 Commit changed from 74821fe5409c3104b5d6eb7407a8287d54170df9 to 5c0800a07bd83787e59713236e5ccc8dde434760
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:5c0800a]  _coerce_map_from_ shouldn't return default conversion maps. Fix for embedded number field morphisms 
[changeset:b7fe7fc]  Use registered coercions *and* embeddings for backtracking, but prefer the former. 
[changeset:a18e13e]  Increase coerce cache version in Morphism.register_as_coercion() 
comment:67 in reply to: ↑ 65 ; followup: ↓ 70 Changed 8 years ago by
 Status changed from needs_work to needs_review
 Work issues Implement backtracking properly deleted
Replying to nbruin:
Unfortunately, that doesn't seem to be a very good heuristic because it's not stable:
_coerce_map_from_
is supposed to do some backtracking on its own, so ifA._coerce_map_from(B)
happens to consider another parentC
that coerces intoA
and find thatC._coerce_map_from(B)==True
, 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.
Why should A._coerce_map_from(B)
return anything? Aren't you rather talking about A.discover_coerce_map_from(B)
that recurses to C and thus calls C._coerce_map_from_(B)
?
In any case, I have now pushed my recent commits. I did solve the recursion error with embedded number field morphism (solution: Raise a TypeError
if one of the number fields actually is not embedded), and with this change
sage: L.<i> = NumberField(x^2 + 1) sage: K = NumberField(L(i/2+3).minpoly(), names=('i0',), embedding=L(i/2+3))
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.
comment:68 Changed 8 years ago by
PS: It might be a good idea to get some number theorist to look at the change to EmbeddedNumberFieldMorphism
and confirm whether this change makes sense for the number theoretical applications.
comment:69 Changed 8 years ago by
 Status changed from needs_review to needs_work
 Work issues set to Crash in permgroup.py
comment:70 in reply to: ↑ 67 Changed 8 years ago by
Replying to SimonKing:
Why should
A._coerce_map_from(B)
return anything?
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
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>
With this one would get
sage: A._coerce_map_from_(C) True sage: C._coerce_map_from_(B) True sage: A._coerce_map_from_(B) Composite map ...
As far as I can see (taking, for instance CC._coerce_map_from_
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.
Aren't you rather talking about
A.discover_coerce_map_from(B)
that recurses to C and thus callsC._coerce_map_from_(B)
?
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 _coerce_map_from_
. I think this was expressly a part of the current design and I think there are many examples of this in sage.
Reading the documentation of discover_coerce_map_from
, it seems that routine would have the same issue (because it also seems to dislike DefaultConvertMap
, and the fragment above shows that it is quite possible to get a composition of DefaultConvertMap
s back, which should be even more disliked)
At this point it seems to me the coercion graphs gets specified in two ways:
 the
_coerce_map_from_
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.  the
_populate_coercion_lists_
world, which more readily corresponds to a graph presentation.
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 implementationdependent to me at the moment (perhaps because the _coerce_map_from_
world is completely implementation dependent by design).
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 _coerce_map_from_
world is adhering to before it's wise to further complicate the situation by also implementing backtracking along embeddings.
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.
comment:71 Changed 8 years ago by
These are the errors one is getting with the current commits:
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
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 #14711, but became weakened now. So, that's trivial to fix.
What is bad is (at least) the crash in permgroup.py, and 11 errors on number fields also sounds like too many...
comment:72 Changed 8 years ago by
 Commit changed from 5c0800a07bd83787e59713236e5ccc8dde434760 to 8d3caea741650a0590f27edc8df0a614aecd31a9
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:8d3caea]  Copy some coerce maps in doctests. Use default conversion to coerce ZZ into QQbar 
comment:73 Changed 8 years ago by
I have just pushed a new commit that should fix most of the trivial problems. But not all is good, I guess
New commits:
[changeset:8d3caea]  Copy some coerce maps in doctests. Use default conversion to coerce ZZ into QQbar 
comment:74 Changed 8 years ago by
I detected another bug in vanilla Sage, that becomes a problem with my commits:
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
comment:75 Changed 8 years ago by
PS: I believe that fixing above bug boils down to rethinking how the CompletionFunctor
construction functors merge. Namely, both RLF
and Qp(7)
are constructed by completion of QQ
.
comment:76 Changed 8 years ago by
PPS: ... how they merge or how they *commute*!
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.
comment:77 Changed 8 years ago by
 Commit changed from 8d3caea741650a0590f27edc8df0a614aecd31a9 to f8f79b8d0e3f42b418703f094d7eb1dd3ff905e8
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:f8f79b8]  Fix commutation of CompletionFunctor?. Further fix for embedded number field morphisms 
comment:78 Changed 8 years ago by
The new commit changes CompletionFunctor.commutes(..)
, so that the completion functor only commutes with the FractionField
, but not with other CompletionFunctor
s (this is because other completion functors have already been taken care of by CompletionFunctor.merge(..)
).
Also, it changes _coerce_map_from_
of number fields according to the previous changes in EmbeddedNumberFieldMorphism
.
With the current commit, all tests in sage/rings/number_field/
pass.
comment:79 Changed 8 years ago by
I have attached the crash log that results from the permutation_group tests.
comment:80 Changed 8 years ago by
 Commit changed from f8f79b8d0e3f42b418703f094d7eb1dd3ff905e8 to b9ebe8118451ec1f4df2c3c9714c95138d7615bd
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:b9ebe81]  Fix some tests by taking *copies* of coerce maps 
comment:81 Changed 8 years ago by
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 nonweakened copies of some coerce maps. Apparently #14711 has not weakened all coercions.
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.
New commits:
[changeset:b9ebe81]  Fix some tests by taking *copies* of coerce maps 
comment:82 Changed 8 years ago by
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.
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.
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.
comment:83 Changed 8 years ago by
 Dependencies changed from #14711 to #14711 #15329 #15331
 Work issues changed from Crash in permgroup.py to Crash in permgroup.py; rebase
comment:84 Changed 8 years ago by
 Commit changed from b9ebe8118451ec1f4df2c3c9714c95138d7615bd to 807550bbc45e9872ac365fc98b817ccd5bcfbb95
 Dependencies changed from #14711 #15329 #15331 to #14711, #15329, #15331
Last 10 new commits:
[changeset:807550b]  Fix some tests by taking *copies* of coerce maps 
[changeset:1db6444]  Copy some coerce maps in doctests. Use default conversion to coerce ZZ into QQbar 
[changeset:810fad8]  _coerce_map_from_ shouldn't return default conversion maps. 
[changeset:d46cb9c]  Use registered coercions *and* embeddings for backtracking, but prefer the former. 
[changeset:a04b480]  Increase coerce cache version in Morphism.register_as_coercion() 
[changeset:1beac71]  Give userprovided coerce maps the same priority than to a coerce map found by backtracking 
[changeset:bae64c4]  Store a version number for the coercion cache, depending on the registered embeddings 
[changeset:7385549]  Use registered embeddings for backtracking in the coercion model 
[changeset:40c787d]  Merge branch 'ticket/15331' into ticket/15303 
[changeset:29ab8ee]  Merge branch 'ticket/15329' into ticket/15303 
comment:85 Changed 8 years ago by
 Work issues changed from Crash in permgroup.py; rebase to Crash in permgroup.py
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 "reorganisation of bits of code in order to facilitate reviewing".
Whatever it is called, two independent issues are tracked at #15329 and #15331, and the crash in permgroup.py remains a problem.
comment:86 Changed 8 years ago by
I have suggested to get both a speedup and a cleaner behaviour of the backtracking algorithm with respect to "comparison of parents by identity".
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)".
In both cases, the functions create an instance of the cdef class EltPair
, and stores resp. removes it in some dictionary. The instances of EltPair
are compared by comparing (x,y,tag)
, and the hash also is obtained in that way.
But that means parents are compared by ==
, whereas in the innards of the coercion system parents (even nonunique parents!) are generally compared by is
. Moreover, comparison by identity and hash by id would be a lot faster, and creating an instance of EltPair
each time also is a waste of time.
Couldn't we use a TripleDict
instead? It would compare by identity, it is about triples x,y,tag
, 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.
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.
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 strong version of TripleDict
.
comment:87 Changed 8 years ago by
Rather than TripleDict
, one could also use a set (not a dict) and use id(X)
for comparison. It would compare the parents in the same way as they are compared in the backtracking (namely by id), and it yields a speedup.
Here is my benchmark. I've put the following into sage.structure.parent
:
def test_registration(list L): _coerce_test_dict.clear() for X in L: for Y in L: _register_pair(X,Y,"test") _is_registered_pair(X,Y,"test") _is_registered_pair(X,Y,"fail") for X in L: for Y in L: _unregister_pair(X,Y,"test") from sage.structure.coerce_dict cimport TripleDict def test_tripledict(list L): TestT = TripleDict(29) for X in L: for Y in L: TestT.set(X,Y,"test",1) (X,Y,"test") in TestT (X,Y,"fail") in TestT for X in L: for Y in L: del TestT[X,Y,"test"] cdef set testset def test_set(list L): global testset testset = set([]) for X in L: for Y in L: testset.add((id(X),id(Y),"test")) (id(X),id(Y),"test") in testset (id(X),id(Y),"fail") in testset for X in L: for Y in L: try: testset.remove((id(X),id(Y),"test")) except KeyError: pass
With this, I get
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
Conclusion
It is not a good idea to use a TripleDict
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 speedup by doing something like <long><void*>X
rather than id(X)
.
comment:88 Changed 8 years ago by
With
def test_set2(list L): global testset testset = set([]) for X in L: for Y in L: testset.add((<Py_ssize_t><void *>X, <Py_ssize_t><void *>Y,"test")) (<Py_ssize_t><void *>X, <Py_ssize_t><void *>Y,"test") in testset (<Py_ssize_t><void *>X, <Py_ssize_t><void *>Y,"fail") in testset for X in L: for Y in L: try: testset.remove((<Py_ssize_t><void *>X, <Py_ssize_t><void *>Y,"test")) except KeyError: pass
I get a further speedup:
sage: %time test_set2(L) CPU times: user 3.18 s, sys: 0.00 s, total: 3.18 s Wall time: 3.19 s
So, the speedup we can get for marking/unmarking/testing of arrows in the coerce digraph during backtracking is a factor of about 4.5.
comment:89 Changed 8 years ago by
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?
comment:90 Changed 8 years ago by
Argh. Not again. A Heisenbug.
sage t verbose src/sage/groups/perm_gps/permgroup.py
and sage t src/sage/groups/perm_gps/permgroup.py
run individually and even sage tp src/sage/groups/perm_gps/
work fine.
But when doing make ptest
with two parallel processes, I *always* get a crash. Bug hunt will be great fun...
comment:91 Changed 8 years ago by
The attached crash log mentions "Entered a critical block twice"
. This error comes from libGAP
. The crash log also mentions weak references, hash and comparison. The usual suspects.
comment:92 followup: ↓ 93 Changed 8 years ago by
PyDict_DelItem
is mentioned as well. Smells like problems with a WeakValueDictionary
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.
comment:93 in reply to: ↑ 92 Changed 8 years ago by
Replying to SimonKing:
PyDict_DelItem
is mentioned as well. Smells like problems with aWeakValueDictionary
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.
Compare #13394
comment:94 Changed 8 years ago by
And also compare our "old friend" #12313. There, we had problems with objects defined in the Gap pexpect interface (stored in a weak value dictionary)and now it is libGAP
.
comment:95 Changed 8 years ago by
If I understand correctly, the crash occurs while computing the hash of a sage.groups.libgap_wrapper.ElementLibGAP
object.
The hash is inherited from sage.structure.element.Element
and relies on the string representation. The string representation relies on the result of the is_one
method. This, in turn, amounts to comparison with self.parent().one()
.
Now I wonder: Has self become defunct? Or has self.parent().one()
become defunct? Is it (again) the WeakValueDictionary
used by CachedRepresentation
that is causing the trouble?
comment:96 Changed 8 years ago by
 Commit changed from 807550bbc45e9872ac365fc98b817ccd5bcfbb95 to 528a03535447d67f04dc16d0a22cc38def54f9f1
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:528a035]  Merge branch 'ticket/13394' into ticket/15303, to make weak caches safer 
[changeset:851cc95]  Avoid some pointer casts in WeakValueDict? callbacks 
[changeset:246518f]  Use <dict>'s internals in WeakValueDictionary? and do not reinvent the bucket. 
[changeset:fab0ed4]  Use WeakValueDict?'s iteration guard more consequently 
[changeset:e4adaeb]  Implement copy and deepcopy for WeakValueDictionary? 
[changeset:70a7b8a]  Guard WeakValueDictionary? against deletions during iteration 
[changeset:c3dba98]  Replace weakref.WeakValueDictionary? by sage.misc.weak_dict.WeakValueDictionary? 
[changeset:17b0236]  Documentation for WeakValueDictionary? 
[changeset:f0ed60f]  Initial version of a safer and faster WeakValueDictionary? 
comment:97 Changed 8 years ago by
 Status changed from needs_work to needs_review
I think #13394 is working, and hence I merged #13394 into the branch of this ticket. Before I pushed the changes, I did make ptest
, and got
 All tests passed!  Total time for all tests: 3859.6 seconds cpu time: 6042.4 seconds cumulative wall time: 7416.0 seconds
Hence: Replacing weakref.WeakValueDictionary
by the newer safer faster ... sage.misc.weak_dict.WeakValueDictionary
has been enough to solve the problem with doctests crashing! So, I can put this to "needs review".
I just notice: With the branch from #15303, the total time for make ptest is 4634.7 s (or 7269.1 CPUs). 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?
comment:98 Changed 8 years ago by
 Milestone changed from sage5.13 to sage6.0
comment:99 followup: ↓ 100 Changed 8 years ago by
I just noticed the following, is it perhaps related to this ticket?
sage: ZZ(CC(1))  TypeError Traceback (most recent call last) <ipythoninput18628bcdd9a52d> in <module>() > 1 ZZ(CC(Integer(1))) /usr/local/src/sage5.13.beta1/local/lib/python2.7/sitepackages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8372)() /usr/local/src/sage5.13.beta1/local/lib/python2.7/sitepackages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3856)() /usr/local/src/sage5.13.beta1/local/lib/python2.7/sitepackages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3757)() /usr/local/src/sage5.13.beta1/local/lib/python2.7/sitepackages/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
comment:100 in reply to: ↑ 99 Changed 8 years ago by
Replying to jdemeyer:
sage: ZZ(CC(1)) ... /usr/local/src/sage5.13.beta1/local/lib/python2.7/sitepackages/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
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 pathdependent). As the trace shows, it fails in sage.rings.integer.Integer.__init__
, i.e., just the integer constructor. I suspect RR has been specialcased there and CC is not (perhaps it should). So, the initializer attempts to see if straight coercion works and of course it doesn't.
I don't think these conversions are going to be terribly useful anyway:
sage: ZZ(49*RR(1/49)) TypeError: Attempt to coerce nonintegral RealNumber to Integer
comment:101 followup: ↓ 102 Changed 8 years ago by
This is red now :/
* branch u/SimonKing/ticket/15303 > FETCH_HEAD Automerging src/sage/tests/book_schilling_zabrocki_kschur_primer.py Automerging src/sage/structure/parent.pyx Automerging src/sage/rings/real_mpfr.pyx Automerging src/sage/rings/number_field/number_field_rel.py Automerging src/sage/rings/number_field/number_field.py Automerging src/sage/misc/weak_dict.pyx CONFLICT (add/add): Merge conflict in src/sage/misc/weak_dict.pyx Automerging src/sage/combinat/symmetric_group_algebra.py Automerging src/sage/combinat/sf/new_kschur.py Automerging src/sage/combinat/ncsf_qsym/ncsf.py Automerging src/sage/categories/pushout.py Automerging src/sage/categories/morphism.pyx Automatic merge failed; fix conflicts and then commit the result.
comment:102 in reply to: ↑ 101 Changed 8 years ago by
Replying to darij:
Automatic merge failed; fix conflicts and then commit the result.
Does this mean I need to do
git checkout trac/master git pull git checkout ticket/15303
and then try to merge trac/master into my branch, resolving conflicts?
comment:103 Changed 8 years ago by
Or better "git pull trac"...
comment:104 followup: ↓ 107 Changed 8 years ago by
WTF??
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.
From looking at it, the two versions of weak_dict.pyx look identical! Nevertheless both the local and the remote version of the file are all marked red in meld, i.e., they are in 100% conflict.
Sorry, but if this is a feature of git then I must say that it sucks.
comment:105 followup: ↓ 106 Changed 8 years ago by
Gosh, I hate git!!!
After giving up on the merge, I tried "git checkout master", but it told me
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.
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?
comment:106 in reply to: ↑ 105 Changed 8 years ago by
Replying to SimonKing:
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?
git reset hard
comment:107 in reply to: ↑ 104 ; followup: ↓ 108 Changed 8 years ago by
Replying to SimonKing:
From looking at it, the two versions of weak_dict.pyx look identical!
Do they? To me it looks like the version in trac/master
is more recent. (Do git diff :2:src/sage/misc/weak_dict.pyx :3:src/sage/misc/weak_dict.pyx
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 u/mmezzarobba/ticket/15303
.
comment:108 in reply to: ↑ 107 ; followup: ↓ 109 Changed 8 years ago by
Replying to mmezzarobba:
Replying to SimonKing:
From looking at it, the two versions of weak_dict.pyx look identical!
Do they?
Meanwhile I found that they differ.
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.
To me it looks like the version in
trac/master
is more recent.
It is. There also is another file with conflicts (sage/schemes/generic/morphism.py)
Just in cas it helps, I pushed a merge based on this assumption to
u/mmezzarobba/ticket/15303
.
Thank you. How to access it (with either git or the dev scripts)?
comment:109 in reply to: ↑ 108 ; followup: ↓ 110 Changed 8 years ago by
Replying to SimonKing:
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.
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 merge
doesn't find any common block to remove.
Just in cas it helps, I pushed a merge based on this assumption to
u/mmezzarobba/ticket/15303
.Thank you. How to access it (with either git or the dev scripts)?
It depends a little bit on your setup, but something like
git fetch trac u/mmezzarobba/ticket/15303 git checkout u/mmezzarobba/ticket/15303 m mybranch
(or git merge ffonly u/mmezzarobba/ticket/15303
if you are already on your ticket branch and want to add the merge commit to that branch) should work.
Please check that what I did is really what you had in mind!
comment:110 in reply to: ↑ 109 ; followup: ↓ 112 Changed 8 years ago by
Replying to mmezzarobba:
git fetch trac u/mmezzarobba/ticket/15303 git checkout u/mmezzarobba/ticket/15303 m mybranch(or
git merge ffonly u/mmezzarobba/ticket/15303
if you are already on your ticket branch and want to add the merge commit to that branch) should work.
The fetch command worked. However, the rest of it didn't.
king@linuxetl7:~/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@linuxetl7:~/Sage/git/sage> git merge ffonly u/mmezzarobba/ticket/15303 fatal: u/mmezzarobba/ticket/15303  nichts was wir zusammenführen können king@linuxetl7:~/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.
However, since apparently git decided to assign your branch to FETCH_HEAD, git merge ffonly FETCH_HEAD
seems to work.
comment:111 followup: ↓ 115 Changed 8 years ago by
How can I see what you did? I tried git diff HEAD^2
, but it doesn't really look like what I expected from resolving a merge conflict, since it touches stuff that did not conflict.
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.
Or is git diff HEAD^2
not the right thing to do in order to see your changes?
comment:112 in reply to: ↑ 110 ; followups: ↓ 113 ↓ 114 Changed 8 years ago by
Replying to SimonKing:
Replying to mmezzarobba:
git fetch trac u/mmezzarobba/ticket/15303 git checkout u/mmezzarobba/ticket/15303 m mybranch(or
git merge ffonly u/mmezzarobba/ticket/15303
if you are already on your ticket branch and want to add the merge commit to that branch) should work.The fetch command worked. However, the rest of it didn't.
Sorry, I meant to write
git checkout trac/u/mmezzarobba/ticket/15303 m mybranch
comment:113 in reply to: ↑ 112 Changed 8 years ago by
Replying to mmezzarobba:
Sorry, I meant to write
git checkout trac/u/mmezzarobba/ticket/15303 m mybranch
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.
So, that's not it.
However, as I said above: After the fetch command, I did git merge ffonly FETCH_HEAD
(being on my branch for this ticket), and I hope that this was one way to incorporate your merge resolution.
However, how can I see your merge resolution?
comment:114 in reply to: ↑ 112 Changed 8 years ago by
Replying to mmezzarobba:
Sorry, I meant to write
git checkout trac/u/mmezzarobba/ticket/15303 m mybranch
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.
So, that's not it.
However, as I said above: After the fetch command, I did git merge ffonly FETCH_HEAD
(being on my branch for this ticket), and I hope that this was one way to incorporate your merge resolution.
However, how can I see your merge resolution?
comment:115 in reply to: ↑ 111 ; followup: ↓ 116 Changed 8 years ago by
Replying to SimonKing:
How can I see what you did? I tried
git diff HEAD^2
, but it doesn't really look like what I expected from resolving a merge conflict, since it touches stuff that did not conflict.
git diff HEAD^2
gives you all the differences between one of the parents (in our case, master
) 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 (git show HEAD
). But this will omit all files that agree entirely with either of the parents. Also, the output will include the parts of the merge that were automatically resolved.
All I did manually was to choose the version of morphism.pyx
that looked more recent, and to merge the imports of morphism.py
as follows:
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
comment:116 in reply to: ↑ 115 ; followup: ↓ 117 Changed 8 years ago by
Replying to mmezzarobba:
To see the effect of a merge, you can try viewing the "combined diff" of HEAD and both parents (
git show HEAD
). But this will omit all files that agree entirely with either of the parents. Also, the output will include the parts of the merge that were automatically resolved.
I see. So, you took the version of src/sage/misc/weak_dictionary.pyx
from master, and ...
All I did manually was to choose the version of
morphism.pyx
that looked more recent,
I have not even been aware that this has changed. So, someone has made morphisms that are defined by generator images hashable? Nice!
and to merge the imports of
morphism.py
as follows: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
Didn't you also do something with src/sage/combinat/ncsf_qsym/ncsf.py
?
Anyway, the output of git show HEAD
looks good to me. So, I will try make ptest
now. Is "crash in pergroup.py" still an issue? We will see...
comment:117 in reply to: ↑ 116 ; followup: ↓ 118 Changed 8 years ago by
Replying to SimonKing:
I see. So, you took the version of
src/sage/misc/weak_dictionary.pyx
from master, and ...All I did manually was to choose the version of
morphism.pyx
that looked more recent,
Of weak_dictionary.pyx
, sorry (I guess I need to catch up on sleep...). The merge of morphism.pyx
was automatic.
Didn't you also do something with
src/sage/combinat/ncsf_qsym/ncsf.py
?
No, there was no conflict there either.
comment:118 in reply to: ↑ 117 ; followup: ↓ 119 Changed 8 years ago by
Replying to mmezzarobba:
Didn't you also do something with
src/sage/combinat/ncsf_qsym/ncsf.py
?No, there was no conflict there either.
Then I show you what git show HEAD
shows me:
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 diff cc src/sage/categories/morphism.pyx index 74f600f,47aa188..a9f44c8  a/src/sage/categories/morphism.pyx +++ b/src/sage/categories/morphism.pyx @@@ 249,8 214,58 +290,58 @@@ garbage collection. Please use a copy." sage: ZZ(x) 1 """  self.codomain().register_conversion(self) + self._codomain.register_conversion(self) + # 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 (20120709) + """ + 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 + + cdef class FormalCoercionMorphism(Morphism): def __init__(self, parent): Morphism.__init__(self, parent) diff cc src/sage/combinat/ncsf_qsym/ncsf.py index 6478d46,7d84562..febf995  a/src/sage/combinat/ncsf_qsym/ncsf.py +++ b/src/sage/combinat/ncsf_qsym/ncsf.py @@@ 238,12 249,11 +249,12 @@@ class NonCommutativeSymmetricFunctions( sage: elementary(ribbon[2,1,2,1]) L[1, 3, 2]  L[1, 5]  L[4, 2] + L[6]  TODO: explain the other changes of bases! + .. TODO:: explain the other changes of bases!  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 diff cc src/sage/schemes/generic/morphism.py index 3a6c351,09c6bc3..ab59866  a/src/sage/schemes/generic/morphism.py +++ b/src/sage/schemes/generic/morphism.py @@@ 79,10 75,12 +79,12 @@@ AUTHORS #***************************************************************************** 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  from sage.rings.all import is_RingHomomorphism, is_CommutativeRing, Integer + from sage.rings.all import Integer + from sage.rings.commutative_ring import is_CommutativeRing + from sage.rings.morphism import is_RingHomomorphism from point import is_SchemeTopologicalPoint from sage.rings.infinity import infinity import scheme
git blame
shows me that the change in ncsf.py seems to be authored by me. But why is git show HEAD
showing it?
comment:119 in reply to: ↑ 118 Changed 8 years ago by
Replying to SimonKing:
git blame
shows me that the change in ncsf.py seems to be authored by me. But why isgit show HEAD
showing it?
Because ncsf.py
contains both lines that come from master
(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.
comment:120 Changed 8 years ago by
 Work issues Crash in permgroup.py deleted
Good and bad news. The good news: I did not see a crash in permgroup.py, even though it used to always occur with make ptest
(not with other methods of testing). The bad news:
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
The number of failing tests indicates that it could be mostly harmless.
I'll soon push the branch (even though it actually is your branch, but I guess it is ok.
comment:121 followup: ↓ 123 Changed 8 years ago by
What is broken in qsym.py? I'm asking because I'm editing the file currently.
comment:122 followup: ↓ 124 Changed 8 years ago by
Oooops, what is that?
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
So, why is the slow toy implementation being used when coercion is changed?
comment:123 in reply to: ↑ 121 Changed 8 years ago by
Replying to darij:
What is broken in qsym.py? I'm asking because I'm editing the file currently.
Here is the diff that I did to fix the failure:

src/sage/combinat/ncsf_qsym/qsym.py
diff git a/src/sage/combinat/ncsf_qsym/qsym.py b/src/sage/combinat/ncsf_qsym/qsym.py index 583ca87..f127c19 100644
a b class QuasiSymmetricFunctions(UniqueRepresentation, Parent): 2232 2232 def __init_extra__(self): 2233 2233 """ 2234 2234 Set up caches for the transition maps to and from the monomial 2235 basis, and register them as coercions. 2235 basis, and register them as coercions. By :trac:`15303`, we need 2236 to copy coerce maps before exposing them outside of the coercion 2237 system. 2236 2238 2237 2239 TESTS:: 2238 2240 2239 2241 sage: HWL = QuasiSymmetricFunctions(QQ).HazewinkelLambda() 2240 2242 sage: M = QuasiSymmetricFunctions(QQ).Monomial() 2241 sage: HWL.coerce_map_from(M)2243 sage: M2HWL = copy(HWL.coerce_map_from(M)); M2HWL 2242 2244 Generic morphism: 2243 2245 From: Quasisymmetric functions over the Rational Field in the Monomial basis 2244 2246 To: Quasisymmetric functions over the Rational Field in the HazewinkelLambda basis 2245 sage: M.coerce_map_from(HWL)2247 sage: HWL2M = copy(M.coerce_map_from(HWL)); HWL2M 2246 2248 Generic morphism: 2247 2249 From: Quasisymmetric functions over the Rational Field in the HazewinkelLambda basis 2248 2250 To: Quasisymmetric functions over the Rational Field in the Monomial basis 2249 sage: M.coerce_map_from(HWL)(HWL[2])2251 sage: HWL2M(HWL[2]) 2250 2252 M[1, 1] 2251 sage: HWL.coerce_map_from(M)(M[2])2253 sage: M2HWL(M[2]) 2252 2254 HWL[1, 1]  2*HWL[2] 2253 2255 """ 2254 2256 M = self.realization_of().M()
comment:124 in reply to: ↑ 122 Changed 8 years ago by
Replying to SimonKing:
Oooops, what is that?
...
So, why is the slow toy implementation being used when coercion is changed?
Same problem in sage t src/sage/schemes/projective/projective_point.py
.
And I guess the other errors should rather be fixed at #14711, because they are about "weakened coerce maps".
comment:125 Changed 8 years ago by
 Commit changed from 528a03535447d67f04dc16d0a22cc38def54f9f1 to 12e80554ac2d23d7727d315649a698a3cd78f0f4
Branch pushed to git repo; I updated commit sha1. New commits:
12e8055  Merge branch 'ticket/14711' into ticket/15303 
ee30c20  Address the "check" keyword of scheme morphisms by name, not position 
d68c5df  Minor fixes, that became needed since #14711 was not merged quickly enough 
c42b539  Merge branch 'master' into ticket/14711 
2712c53  Merge 'trac/master' into ticket/15303 
23f18f2  Merge branch 'master' into ticket/14711 
comment:126 Changed 8 years ago by
Since #14711 has changed, I have merged the new commits from there.
And I have included Marc's master merge.
Doctests pass for me.
comment:127 Changed 8 years ago by
 Milestone changed from sage6.0 to sage6.1
comment:128 Changed 8 years ago by
This branch (more precisely, commit 1db6444c33c5b41bf600b6446badd92ddbe3c018) conflicts with that from #10963 (more precisely, with 9d9cae35053bca7c47466a6f64ee142748eddec1).
comment:129 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:130 Changed 7 years ago by
 Status changed from needs_review to needs_work
 Work issues set to rebase (11 files conflicting)
comment:131 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:132 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
The problem is that in the present implementation, both coercions are stored on
A
, so if a coercion fromB
toC
is requested, it hard to realize thatA
should even be considered.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.
One way to work around it is, at least for coercion discovery, to store the coercion always on the codomain. By #14711 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.
If it is desirable to keep the current lifetime implications for
register_embedding
(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.