#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: Analyse recursion
Branch: | error
u/SimonKing/ticket/15303 | Commit:
Dependencies: #14711 | 74821fe5409c3104b5d6eb7407a8287d54170df9
| Stopgaps:
-------------------------------------+-------------------------------------
Comment (by SimonKing):
Replying to [comment:39 nbruin]:
> It may well be that you can hide the problem by enforcing some lookup
order, but you'd be introducing data (in this case list order) that is not
part of our model.
How to formulate a model that takes into account dependencies between
arrows of a digraph? In particular between arrows that may not even be
adjacent?
> As you observe, the coercion A->D is in actuality derived from A->B, but
apparently not by a straightforward composition.
Correct. When calling the coercion A->D, some arithmetic is performed on
underlying data, this involves coercion, and this is when A->B occurs.
> However, doesn't that mean that if A->D is discovered, then A->B must be
discovered already?
No. You can easily define a map and then compose with other maps, without
calling it. A->B is only needed for '''calling''' A->D, but not for
'''definining''' A->D.
> If A->D relies on A->B, I think part of registering A->D is ensuring
that A->B is discovered.
Yes, and how to model this?
> Since it seems we need a tie-breaker for multiple paths anyway, and
there is a cost system (which I think was primarily introduced for pushout
construction!), it is then just a matter of ensuring that the cost of A->D
is higher than the cost of A->B. Then anything that can be done from A and
then via B or D will prefer the direct path A->B.
... but only if, in addition, we actually use the coerce costs in
`discover_coercion()`, rather then returning the first map that came
across.
> So it seems to me that the "theoretically" better solution (which may be
prohibitive cost-wise!) would be:
> - recalibrate some of the costs
> - take the costs properly into account
> - probably do so via breadth-first (for finding shortest path, it
allows much better pruning)
>
> I think that should solve the A->D problem as well.
Perhaps.
- Breadth first search might be a good idea. I don't know how to
efficiently implement it, but I guess this should be done at some point.
- Calibrating the costs, such that `A->C->B` is guaranteed to have less
cost than `A->D->B` for any example in which `A->C` is independent of but
`A->D` is dependent on `A->B`, requires a case-by-case analysis. Not very
practical, and moreover choosing parameters such that "it works" is kind
of arbitrary. This is not a very clean solution either.
Before we have implemented breadth first search, I believe it would be
more practical to say that we should
- give preference to maps registered during initialisation
(`P.register_coercion(mor)`)
- give less preference to maps registered after initialisation
(`mor.register_as_coercion()`)
- give least preference to registered embeddings (I am talking about
backtracking here, not pushout).
This is practical because this approach is close to what is done in
vanilla Sage. The current registration order is such that "it works".
--
Ticket URL: <http://trac.sagemath.org/ticket/15303#comment:40>
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.
