Opened 6 years ago

Last modified 5 years ago

#15303 needs_work defect

Coercion discovery fails to be transitive

Reported by: nbruin Owned by:
Priority: major Milestone: sage-6.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) 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 sage-devel:

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)

sage_crash_SqPXq6.log (107.0 KB) - added by SimonKing 6 years ago.
Crash log

Download all attachments as: .zip

Change History (133)

comment:1 Changed 6 years ago by nbruin

The problem is that in the present implementation, both coercions are stored on A, so if a coercion from B to C is requested, it hard to realize that A 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.

comment:2 follow-up: Changed 6 years ago by SimonKing

It has also been discussed on sage-devel that the existence of a coercion from B to C would change over time. Namely:

  1. Create B and C. You will not find a coercion, because A is not known yet.
  2. Create A, registering a coercion from B to A and an embedding of A into C.
  3. 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 enough---we 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 slow-down.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 6 years ago by nbruin

Replying to SimonKing:

  1. 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 non-existence with a "coercion graph version number". When a non-existence is retrieved, one could check the current "coercion graph version number" and if the current graph is newer, we'd have to reinvestigate the "None". Frankly, I don't believe that would give acceptable performance either, but we could at least be much more lazy about invalidating "no coercion exists" findings. The reason why I think this would still not be good enough is because I expect that coercion graph mutations occur fairly frequently (basically with any parent creation) and I don't see a way to localize coercion graph versions, so any mutation would invalidate ALL non-existence caches.

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).

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 backtracking
  • P._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 in Q._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 slow-down.

Yes, I don't have any suggestions that I seriously believe would lead to acceptable performance.

comment:4 follow-up: Changed 6 years ago by SimonKing

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 non-sink non-source nodes---and I doubt that the combined use of .register_embedding() and .register_coercion() (which is the only way to create non-sink non-source) will happen very often.

So, I'd say we simply try.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 6 years ago by nbruin

Replying to SimonKing:

Would this really be soooo expensive? I don't think so. Of course, it depends on how often we create non-sink non-source nodes---and I doubt that the combined use of .register_embedding() and .register_coercion() (which is the only way to create non-sink non-source) will happen very often.

I don't think you can establish whether something is a non-sink, since _coerce_from_map gives programmatic answers about that. Things are very rarely going to be non-sinks, though, since usually ZZ will coerce into them (but ZZ will never be a problem. perhaps we can leave it out of consideration)

A start might be to only version up on "embedding" creations. That might very well be usable. I expect "embeddings" to be relatively rare, and I think we can declare in our documentation they are not the preferred way of expressing relations (they are vary prone to creating non-commutative diamonds).

comment:6 in reply to: ↑ 5 Changed 6 years ago by SimonKing

Replying to nbruin:

I don't think you can establish whether something is a non-sink, since _coerce_from_map gives programmatic answers about that.

Perhaps I have not been clear. A non-sink non-source is something that has both in-arrows (i.e., is codomain of a registered coercion or coerce embedding) and out-arrows (i.e., is domain of a registered coercion or coerce embedding). It is easy to keep track of this property while registering a coercion or coerce embedding.

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 non-commutative 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.

Last edited 6 years ago by SimonKing (previous) (diff)

comment:7 Changed 6 years ago by SimonKing

  • Dependencies set to #14711

I hope you agree that we should start on top of #14711, because you suggest to change a couple of attribute names that are touched in #14711.

comment:8 in reply to: ↑ 3 Changed 6 years ago by SimonKing

Replying to nbruin:

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).

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 in Q._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 follow-up: Changed 6 years ago by SimonKing

PS: We also have convert_from_list, and I guess we should proceed similarly for coerce_from_list.

comment:10 Changed 6 years ago by SimonKing

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 6 years ago by SimonKing

  • 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 6 years ago by nbruin

  • Commit set to dcd8d68fb30f752bcd595d73fe2d3925e7db671f

Replying to SimonKing:

PS: We also have convert_from_list, and I guess we should proceed similarly for coerce_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 leak-free 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 6 years ago by git

  • 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 follow-up: Changed 6 years ago by SimonKing

  • Authors set to Simon King
  • 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 doctests---since 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 slow-downs in coercion.

comment:15 Changed 6 years ago by SimonKing

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 6 years ago by nbruin

  • Important: Get timings for examples that should be most sensitive against slow-downs 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 lightning-fast (and why shouldn't it be?) I expect that negatively affected examples would have to do a lot of number field or AbelianGroupWithValues creations interleaved with complicated coercion discovery that benefits a lot from knowing certain coercions do NOT exist.

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 6 years ago by SimonKing

  • 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 6 years ago by SimonKing

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 6 years ago by SimonKing

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 6 years ago by SimonKing

Further boiled down:

sage: psi = QQbar.coerce_map_from(ZZ)
sage: psi(1)
<infinite loop>

comment:21 follow-up: Changed 6 years ago by SimonKing

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 codomain---and these are the maps registered during creation of the codomain.

comment:22 in reply to: ↑ 21 Changed 6 years ago by nbruin

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 codomain---and 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 real-life 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 6 years ago by SimonKing

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 6 years ago by SimonKing

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

Last edited 6 years ago by SimonKing (previous) (diff)

comment:25 Changed 6 years ago by SimonKing

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 composition---which 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 6 years ago by SimonKing

  • 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 follow-up: Changed 6 years ago by SimonKing

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 user-provided morphism is compared with the other morphism.

This just isn't fair!!! I believe that the user-provided morphism should at least have the same priority as a morphism found by backtracking.

Two approaches, that are not mutually exclusive:

  1. Amend the coerce costs, so that a simple map has less costs than a composite map, unless there is a very good reason.
  2. Let the user-provided morphism count for the number of morphisms found in .discover_coercion(). Hence, if num_paths=1 and the user provides a morphism, then the maximal number of paths-to-be-considered is attained and hence the user-provided morphism is returned without backtracking.

I think the second point is more important, and I will implement it now.

comment:28 Changed 6 years ago by SimonKing

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 6 years ago by SimonKing

Replying to SimonKing:

  1. Let the user-provided morphism count for the number of morphisms found in .discover_coercion(). Hence, if num_paths=1 and the user provides a morphism, then the maximal number of paths-to-be-considered is attained and hence the user-provided morphism is returned without backtracking.

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 6 years ago by git

  • Commit changed from f837cbee8f81c4946a92193c73e86449c53515d9 to 74821fe5409c3104b5d6eb7407a8287d54170df9

Branch pushed to git repo; I updated commit sha1. New commits:

[changeset:74821fe]Give user-provided coerce maps the same priority than to a coerce map found by backtracking

comment:31 Changed 6 years ago by SimonKing

  • 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 6 years ago by SimonKing

  • 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 6 years ago by SimonKing

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 6 years ago by SimonKing

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 6 years ago by SimonKing

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 follow-up: Changed 6 years ago by SimonKing

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.

Last edited 6 years ago by SimonKing (previous) (diff)

comment:37 in reply to: ↑ 36 Changed 6 years ago by SimonKing

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 follow-up: Changed 6 years ago by SimonKing

I found that the example above has the following structure:

  • We have parents A and B. We search a coercion A -> B.
  • B stores coercions (for backtracking) from parents C and D. Only C is registered by B.register_coercion(...), whereas the coercion from D was registered in a different way, after initialisation of B.
  • There is a coercion phi from A to C and a coercion psi from A to D. Sage knows that phi and psi exist. However, calling psi internally relies on a coercion from A to B.
  • The coercion from A to B must go via C, starting with phi. Otherwise, if one tries to coerce A via D into B, calling psi (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?

Last edited 6 years ago by SimonKing (previous) (diff)

comment:39 in reply to: ↑ 38 ; follow-up: Changed 6 years ago by nbruin

Replying to SimonKing:

I found that the example above has the following structure:

  • We have parents A and B. We search a coercion A -> B.
  • B stores coercions (for backtracking) from parents C and D. Only C is registered by B.register_coercion(...), whereas the coercion from D was registered in a different way, after initialisation of B.
  • There is a coercion phi from A to C and a coercion psi from A to D. Sage knows that phi and psi exist. However, calling psi internally relies on a coercion from A to B.
  • The coercion from A to B must go via C, starting with phi. Otherwise, if one tries to coerce A via D into B, calling psi (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, implementation-specified) behaviour. That makes it very hard to reason about how the system should behave and hence to determine (in the future) whether something is a bug. It may well be (in the end) that enforcing a lookup order turns out to be required to keep performance, but it would probably be preferable to find a better solution.

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 tie-breaker for multiple paths anyway, and there is a cost system (which I think was primarily introduced for pushout construction!), it is then just a matter of ensuring that the cost of A->D is higher than the cost of A->B. Then anything that can be done from A and then via B or D will prefer the direct path A->B.

So it seems to me that the "theoretically" better solution (which may be prohibitive cost-wise!) would be:

  • recalibrate some of the costs
  • take the costs properly into account
  • probably do so via breadth-first (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 ; follow-up: Changed 6 years ago by SimonKing

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 tie-breaker for multiple paths anyway, and there is a cost system (which I think was primarily introduced for pushout construction!), it is then just a matter of ensuring that the cost of A->D is higher than the cost of A->B. Then anything that can be done from A and then via B or D will prefer the direct path A->B.

... 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 cost-wise!) would be:

  • recalibrate some of the costs
  • take the costs properly into account
  • probably do so via breadth-first (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 than A->D->B for any example in which A->C is independent of but A->D is dependent on A->B, requires a case-by-case analysis. Not very practical, and moreover choosing parameters such that "it works" is kind of arbitrary. This is not a very clean solution either.

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 6 years ago by nbruin

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 new-found paths (only store them if you found a shorter path or a path from a new domain). As soon as you found a path from the required domain, prune by cost (you only need to store paths that could possibly lead to a cheaper path). Continue until all paths you have stored have been examined (and further path is longer than what you've found). The expensive part is still determining there is NO path, because no pruning can occur then.

  • Calibrating the costs, such that A->C->B is guaranteed to have less cost than A->D->B for any example in which A->C is independent of but A->D is dependent on A->B, requires a case-by-case analysis. Not very practical, and moreover choosing parameters such that "it works" is kind of arbitrary. This is not a very clean solution either.

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 history-sensitive graph, you could put as cost of the edge the insertion time of the edge, and use the maximum over a path as the cost of the path. Do you think that's a reasonable model?

Last edited 6 years ago by nbruin (previous) (diff)

comment:42 Changed 6 years ago by SimonKing

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 6 years ago by SimonKing

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 6 years ago by SimonKing

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 follow-up: Changed 6 years ago by 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.

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 ; follow-up: Changed 6 years ago by nbruin

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 in-degree. Doing backtracking from them would be a rather expensive operation (independent of whether it's breadth-first (cheapest-first is a better name) or depth-first). So we mandate that any paths that would involve such a map should be explicitly offered, so that backtracking is not necessary for discovering paths that use it. That could make sense. In order for such a model to be usable, you'd have to write clear documentation/helper routines to ensure that the right maps are put in. What if discovery is needed in the process of finding coercions between polynomial rings/function fields/algebraic groups over certain bases etc? Can we write down rules that make for a transparent and usable model?

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 6 years ago by SimonKing

Hi!

First of all, note that the latest recursion errors refer to not-yet-committed code. It could be that by copy-and-pasting I somehow destroyed the backtracking algorithm by not properly marking a used arrow as not-to-be-tested-again. Thus the recursion.

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 6 years ago by SimonKing

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 6 years ago by SimonKing

  • 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 6 years ago by SimonKing

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 non-unique 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 6 years ago by SimonKing

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 6 years ago by SimonKing

As it turns out, the recursion again occurs when calling (not when constructing!) a coerce map. Nevertheless, I think one should speed-up 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 follow-ups: Changed 6 years ago by 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 that self._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 ; follow-up: Changed 6 years ago by nbruin

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 that self._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 1-dimensional 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 depth-first path discovery? That would be an even better reason to see if we can get a "cheapest first" search in, since that naturally avoids cycles.

comment:55 follow-up: Changed 6 years ago by 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 sage-nt 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.

Last edited 6 years ago by SimonKing (previous) (diff)

comment:56 Changed 6 years ago by jpflori

  • Cc jpflori added

comment:57 Changed 6 years ago by jpflori

Great work, all of this looks really fine.

comment:58 in reply to: ↑ 54 ; follow-up: Changed 6 years ago by SimonKing

Replying to nbruin:

Above, you also talk about "forbidden" and "temporarily forbidden" paths. Are those part of the depth-first path discovery?

Of course. By "temporarily forbidden", I mean those that have already been visited in the depth-first search and shall thus not be visited again during the same search. Thus "temporarily", because in the next search they could be visited.

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 "short-cuts" 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 ; follow-up: Changed 6 years ago by nbruin

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), 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.

(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 6 years ago by nbruin

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 sage-nt 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.

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 ; follow-up: Changed 6 years ago by SimonKing

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 digraph-with-shortcuts 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 "digraph-with-shortcuts 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 digraph-with-shortcuts 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 short-cut Z->Y into an actual arrow of the digraph.

However, I could also imagine that this would have two disadvantages:

  1. 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".
  2. The list of maps-to-be-considered 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:

  1. It is tested whether there is a short-cut phi (either explicitly or implicitly).
  2. Even if phi is found, backtracking is performed. Backtracking "goes back" according to the registered coercions, and may involve short-cuts by recursion. Let's call psi the first map found by backtracking (if there is any).
  3. 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 short-cuts into permanent arrows, to be used by backtracking. But then we need to take care of lifetime implications, and we need to take care of a potential slow-down of the backtracking.

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 digraph-with-shortcuts model, then we indeed need at least two hooks: One that adds arrows to the digraph, and one that provides short-cuts. In my branch, I suggest to extend the role of registered embeddings, namely: To make them actual arrows, to be used in backtracking.

comment:62 in reply to: ↑ 61 ; follow-up: Changed 6 years ago by nbruin

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 digraph-with-shortcuts 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 "digraph-with-shortcuts model".

This makes me wonder what exactly the axioms of this "digraph-with-shortcuts model" is. I can see how "digraph-with-shortcuts" can be used to implement a proper digraph model more efficiently, if the shortcuts follow some rules (as stated above). If our theoretical model is "digraph-with-costs" I can see a "digraph-with-costs-and-shortcuts" implementation, where the shortcuts would obviously have to provide a cost on them too: the cost of the path they are providing the "shortcut" for (modulo little tweaks).

You mean from Z to Y?

Yes, sorry.

Yes, which is part of the specification of the digraph-with-shortcuts model.

My conclusion would be that our digraph-with-shortcuts 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 short-cut 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 "-with-shortcuts" is an implementation detail to gain efficiency, not a part of the model, because I don't see what kind of reasonable model one would have then.

I think I have already described what is currently done:

  1. It is tested whether there is a short-cut phi (either explicitly or implicitly).
  2. Even if phi is found, backtracking is performed. Backtracking "goes back" according to the registered coercions, and may involve short-cuts by recursion. Let's call psi the first map found by backtracking (if there is any).
  3. 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 above-described 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 ; follow-up: Changed 6 years ago by SimonKing

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 6 years ago by nbruin

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 ; follow-up: Changed 6 years ago by nbruin

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 that self._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 6 years ago by git

  • 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 ; follow-up: Changed 6 years ago by SimonKing

  • 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 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.

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 6 years ago by SimonKing

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 6 years ago by SimonKing

  • Status changed from needs_review to needs_work
  • Work issues set to Crash in permgroup.py

comment:70 in reply to: ↑ 67 Changed 6 years ago by nbruin

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 calls C._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 DefaultConvertMaps 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 implementation-dependent 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 6 years ago by SimonKing

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 6 years ago by git

  • 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 6 years ago by SimonKing

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 6 years ago by SimonKing

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 6 years ago by SimonKing

PS: I believe that fixing above bug boils down to re-thinking how the CompletionFunctor construction functors merge. Namely, both RLF and Qp(7) are constructed by completion of QQ.

comment:76 Changed 6 years ago by SimonKing

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 6 years ago by git

  • 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 6 years ago by SimonKing

The new commit changes CompletionFunctor.commutes(..), so that the completion functor only commutes with the FractionField, but not with other CompletionFunctors (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.

Changed 6 years ago by SimonKing

Crash log

comment:79 Changed 6 years ago by SimonKing

I have attached the crash log that results from the permutation_group tests.

comment:80 Changed 6 years ago by git

  • 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 6 years ago by SimonKing

I have pushed another commit. It fixes all remaining doctest errors, except the crash in permgroup.py. The fixes are rather easy: It was needed to add "..." to some expected error messages (reason: The changed string representation of weakened maps) and use non-weakened copies of some coerce maps. Apparently #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 6 years ago by SimonKing

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 6 years ago by SimonKing

  • Dependencies changed from #14711 to #14711 #15329 #15331
  • Work issues changed from Crash in permgroup.py to Crash in permgroup.py; rebase

FWIW, I have created #15329 and #15331 to deal with the two independent sub-problems. Both need review.

comment:84 Changed 6 years ago by SimonKing

  • 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 user-provided 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 6 years ago by SimonKing

  • 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 "re-organisation 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 6 years ago by SimonKing

I have suggested to get both a speed-up and a cleaner behaviour of the backtracking algorithm with respect to "comparison of parents by identity".

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 non-unique 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 6 years ago by SimonKing

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 speed-up.

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 speed-up by doing something like <long><void*>X rather than id(X).

comment:88 Changed 6 years ago by SimonKing

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 speed-up:

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 speed-up 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 6 years ago by SimonKing

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 6 years ago by SimonKing

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 6 years ago by SimonKing

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 follow-up: Changed 6 years ago by SimonKing

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 6 years ago by SimonKing

Replying to SimonKing:

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.

Compare #13394

comment:94 Changed 6 years ago by SimonKing

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 6 years ago by SimonKing

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 6 years ago by git

  • 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 6 years ago by SimonKing

  • 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 CPU-s). With the branch from here, we are quite noticeably faster. So, could it be that the new approach of representing the dynamic coerce digraph is more efficient?

comment:98 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.13 to sage-6.0

comment:99 follow-up: Changed 6 years ago by jdemeyer

I just noticed the following, is it perhaps related to this ticket?

sage: ZZ(CC(1))
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-18-628bcdd9a52d> in <module>()
----> 1 ZZ(CC(Integer(1)))

/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8372)()

/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3856)()

/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3757)()

/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/rings/integer.so in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:7889)()

TypeError: unable to coerce <type 'sage.rings.complex_number.ComplexNumber'> to an integer
sage: ZZ(RR(CC(1)))
1

comment:100 in reply to: ↑ 99 Changed 6 years ago by nbruin

Replying to jdemeyer:

sage: ZZ(CC(1))
...
/usr/local/src/sage-5.13.beta1/local/lib/python2.7/site-packages/sage/rings/integer.so in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:7889)()

TypeError: unable to coerce <type 'sage.rings.complex_number.ComplexNumber'> to an integer
sage: ZZ(RR(CC(1)))
1

I don't think it necessarily is related: this is a conversion and given how liberal conversion is allowed/meant to be, I don't think we can expect convertibility to ever be transitive (I think it will even be path-dependent). As the trace shows, it fails in sage.rings.integer.Integer.__init__, i.e., just the integer constructor. I suspect RR has been special-cased there and CC is not (perhaps it should). So, the initializer attempts to see if straight coercion works and of course it doesn't.

I don't think these conversions are going to be terribly useful anyway:

sage: ZZ(49*RR(1/49))
TypeError: Attempt to coerce non-integral RealNumber to Integer
Last edited 6 years ago by nbruin (previous) (diff)

comment:101 follow-up: Changed 6 years ago by darij

This is red now :/

 * branch            u/SimonKing/ticket/15303 -> FETCH_HEAD
Auto-merging src/sage/tests/book_schilling_zabrocki_kschur_primer.py
Auto-merging src/sage/structure/parent.pyx
Auto-merging src/sage/rings/real_mpfr.pyx
Auto-merging src/sage/rings/number_field/number_field_rel.py
Auto-merging src/sage/rings/number_field/number_field.py
Auto-merging src/sage/misc/weak_dict.pyx
CONFLICT (add/add): Merge conflict in src/sage/misc/weak_dict.pyx
Auto-merging src/sage/combinat/symmetric_group_algebra.py
Auto-merging src/sage/combinat/sf/new_kschur.py
Auto-merging src/sage/combinat/ncsf_qsym/ncsf.py
Auto-merging src/sage/categories/pushout.py
Auto-merging src/sage/categories/morphism.pyx
Automatic merge failed; fix conflicts and then commit the result.

comment:102 in reply to: ↑ 101 Changed 6 years ago by SimonKing

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 6 years ago by SimonKing

Or better "git pull trac"...

comment:104 follow-up: Changed 6 years ago by SimonKing

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 follow-up: Changed 6 years ago by SimonKing

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 6 years ago by mmezzarobba

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 ; follow-up: Changed 6 years ago by mmezzarobba

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 ; follow-up: Changed 6 years ago by SimonKing

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 ; follow-up: Changed 6 years ago by mmezzarobba

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 --ff-only 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 ; follow-up: Changed 6 years ago by SimonKing

Replying to mmezzarobba:

git fetch trac u/mmezzarobba/ticket/15303
git checkout u/mmezzarobba/ticket/15303 -m mybranch

(or git merge --ff-only 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@linux-etl7:~/Sage/git/sage> git fetch trac u/mmezzarobba/ticket/15303
Enter passphrase for key '/home/king/.ssh/id_rsa': 
remote: Counting objects: 161, done.
remote: Compressing objects: 100% (55/55), done.
remote: Total 55 (delta 53), reused 0 (delta 0)
Unpacking objects: 100% (55/55), done.
Von ssh://trac.sagemath.org:2222/sage
 * branch            u/mmezzarobba/ticket/15303 -> FETCH_HEAD
king@linux-etl7:~/Sage/git/sage> git merge --ff-only u/mmezzarobba/ticket/15303
fatal: u/mmezzarobba/ticket/15303 - nichts was wir zusammenführen können
king@linux-etl7:~/Sage/git/sage> git checkout u/mmezzarobba/ticket/15303 -m ticket/15303mezzarobba
error: pathspec 'u/mmezzarobba/ticket/15303' did not match any file(s) known to git.
error: pathspec 'ticket/15303mezzarobba' did not match any file(s) known to git.

However, since apparently git decided to assign your branch to FETCH_HEAD, git merge --ff-only FETCH_HEAD seems to work.

comment:111 follow-up: Changed 6 years ago by 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.

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 ; follow-ups: Changed 6 years ago by mmezzarobba

Replying to SimonKing:

Replying to mmezzarobba:

git fetch trac u/mmezzarobba/ticket/15303
git checkout u/mmezzarobba/ticket/15303 -m mybranch

(or git merge --ff-only 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 6 years ago by SimonKing

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 --ff-only 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 6 years ago by SimonKing

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 --ff-only 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 ; follow-up: Changed 6 years ago by mmezzarobba

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 ; follow-up: Changed 6 years ago by SimonKing

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 ; follow-up: Changed 6 years ago by mmezzarobba

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 ; follow-up: Changed 6 years ago by SimonKing

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 (2012-07-09)
+         """
+         domain = self.domain()
+         codomain = self.codomain()
+         try:
+             gens = domain.gens()
+             definition = tuple([self(x) for x in gens])
+         except (AttributeError, NotImplementedError):
+             definition = self.__repr__()
+         return hash((domain, codomain, definition))
+ 
+     def __richcmp__(left, right, int op):
+         return (<Element>left)._richcmp(right, op)
+ 
+     cdef int _cmp_c_impl(left, Element right) except -2:
+         if left is right: return 0
+         domain = left.domain()
+         c = cmp(domain, right.domain())
+         if c: return c
+         c = cmp(left.codomain(), right.codomain())
+         if c: return c
+         try:
+             gens = domain.gens()
+             for x in gens:
+                 c = cmp(left(x), right(x))
+                 if c: return c
+         except (AttributeError, NotImplementedError):
+             raise NotImplementedError
+ 
+ 
  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 6 years ago by mmezzarobba

Replying to SimonKing:

git blame shows me that the change in ncsf.py seems to be authored by me. But why is git 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 6 years ago by SimonKing

  • 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 follow-up: Changed 6 years ago by darij

What is broken in qsym.py? I'm asking because I'm editing the file currently.

comment:122 follow-up: Changed 6 years ago by SimonKing

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 6 years ago by SimonKing

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): 
    22322232        def __init_extra__(self):
    22332233            """
    22342234            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.
    22362238
    22372239            TESTS::
    22382240
    22392241                sage: HWL = QuasiSymmetricFunctions(QQ).HazewinkelLambda()
    22402242                sage: M = QuasiSymmetricFunctions(QQ).Monomial()
    2241                 sage: HWL.coerce_map_from(M)
     2243                sage: M2HWL = copy(HWL.coerce_map_from(M)); M2HWL
    22422244                Generic morphism:
    22432245                  From: Quasisymmetric functions over the Rational Field in the Monomial basis
    22442246                  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
    22462248                Generic morphism:
    22472249                  From: Quasisymmetric functions over the Rational Field in the HazewinkelLambda basis
    22482250                  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])
    22502252                M[1, 1]
    2251                 sage: HWL.coerce_map_from(M)(M[2])
     2253                sage: M2HWL(M[2])
    22522254                HWL[1, 1] - 2*HWL[2]
    22532255            """
    22542256            M = self.realization_of().M()

comment:124 in reply to: ↑ 122 Changed 6 years ago by SimonKing

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 6 years ago by git

  • Commit changed from 528a03535447d67f04dc16d0a22cc38def54f9f1 to 12e80554ac2d23d7727d315649a698a3cd78f0f4

Branch pushed to git repo; I updated commit sha1. New commits:

12e8055Merge branch 'ticket/14711' into ticket/15303
ee30c20Address the "check" keyword of scheme morphisms by name, not position
d68c5dfMinor fixes, that became needed since #14711 was not merged quickly enough
c42b539Merge branch 'master' into ticket/14711
2712c53Merge 'trac/master' into ticket/15303
23f18f2Merge branch 'master' into ticket/14711

comment:126 Changed 6 years ago by SimonKing

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 5 years ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:128 Changed 5 years ago by mmezzarobba

This branch (more precisely, commit 1db6444c33c5b41bf600b6446badd92ddbe3c018) conflicts with that from #10963 (more precisely, with 9d9cae35053bca7c47466a6f64ee142748eddec1).

comment:129 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:130 Changed 5 years ago by rws

  • Status changed from needs_review to needs_work
  • Work issues set to rebase (11 files conflicting)

comment:131 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:132 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.