Coercion discovery fails to be transitive

[nbruin]

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.

Depends on #14711
Depends on #15329
Depends on #15331

CC: @simon-king-jena @robertwb @jpflori

Component: coercion

Work Issues: rebase (11 files conflicting)

Author: Simon King

Branch/Commit: u/SimonKing/ticket/15303 @ 12e8055

Issue created by migration from https://trac.sagemath.org/ticket/15303

[nbruin]

comment:1

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.

[simon-king-jena]

comment:2

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.

[nbruin]

comment:3

Replying to @simon-king-jena:

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

[simon-king-jena]

comment:4

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.

[nbruin]

comment:5

Replying to @simon-king-jena:

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

[simon-king-jena]

comment:6

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.

[simon-king-jena]

Dependencies: #14711

[simon-king-jena]

comment:7

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.

[simon-king-jena]

comment:8

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.

[simon-king-jena]

comment:9

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

[simon-king-jena]

comment:10

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.