#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 nbruin):
Replying to [comment:38 SimonKing]:
> I found that the example above has the following structure:
> - We have parents `A` and `B`. We search a coercion `A -> B`.
> - `B` stores coercions (for backtracking) from parents `C` and `D`. Only
`C` is registered by `B.register_coercion(...)`, whereas the coercion from
`D` was registered in a different way, ''after'' initialisation of `B`.
> - There is a coercion `phi` from `A` to `C` and a coercion `psi` from
`A` to `D`. Sage knows that `phi` and `psi` exist. However, calling `psi`
internally relies on a coercion from `A` to `B`.
> - The coercion from `A` to `B` '''must''' go via `C`, starting with
`phi`. Otherwise, if one tries to coerce `A` via `D` into `B`, calling
`psi` (as part of a composite coerce map) will result in an infinite
recursion.
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. Hence, you'll end up relying on essentially unspecified
(well, implementation-specified) behaviour. That makes it very hard to
reason about how the system should behave and hence to determine (in the
future) whether something is a bug. It may well be (in the end) that
enforcing a lookup order turns out to be required to keep performance, but
it would probably be preferable to find a better solution.
As you observe, the coercion A->D is in actuality derived from A->B, but
apparently not by a straightforward composition. However, doesn't that
mean that if A->D is discovered, then A->B must be discovered already? If
A->D relies on A->B, I think part of registering A->D is ensuring that
A->B is discovered.
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.
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.
--
Ticket URL: <http://trac.sagemath.org/ticket/15303#comment:39>
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.
