#15303: Coercion discovery fails to be transitive
-------------------------------------+-------------------------------------
Reporter: nbruin | Owner:
Type: defect | Status: needs_work
Priority: major | Milestone: sage-5.13
Component: coercion | Resolution:
Keywords: | Merged in:
Authors: Simon King | Reviewers:
Report Upstream: N/A | Work issues: Implement
Branch: | backtracking properly
u/SimonKing/ticket/15303 | Commit:
Dependencies: #14711 | 74821fe5409c3104b5d6eb7407a8287d54170df9
| Stopgaps:
-------------------------------------+-------------------------------------
Comment (by SimonKing):
Replying to [comment:59 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.
--
Ticket URL: <http://trac.sagemath.org/ticket/15303#comment:61>
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.
