#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:61 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]
--
Ticket URL: <http://trac.sagemath.org/ticket/15303#comment:62>
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.
