#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 nbruin):
Replying to [comment:58 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.
--
Ticket URL: <http://trac.sagemath.org/ticket/15303#comment:59>
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.
