#15303: Coercion discovery fails to be transitive
----------------------------+-------------------------
Reporter: nbruin | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-5.13
Component: coercion | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
----------------------------+-------------------------
Comment (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.
--
Ticket URL: <http://trac.sagemath.org/ticket/15303#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
