#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:40 SimonKing]:
> > 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?
In this case it could just be done by explicitly asking the system to
discover A->B before installing A->D. However, proper cost accounting
shouldn't require discovery order to matter at all.
> - 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.
Just keep track of all discovered shortest paths (ordered by domain) into
the codomain, and try to extend the shortest path. Merge the new-found
paths (only store them if you found a shorter path or a path from a new
domain). As soon as you found a path from the required domain, prune by
length. Continue until all paths you have stored have been examined (and
further path is longer than what you've found). The expensive part is
still determining there is NO path, because no pruning can occur then.
> - 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.
That is right, but it's not a very clean problem either. You need
something to distinguish A->C->B from A->D->B. The only place where we
have enough information to insert this data is when we define A->D. Since
that coercion requires A->B, you could encode its cost to be cost(A->B) +
<something>. This is basically what path composition would do for you
normally. Since A->D is derived from A->B, you'll have to insert that
information in some other way.
> This is practical because this approach is close to what is done in
vanilla Sage. The current registration order is such that "it works".
If you want a practical solution, I think leaving the status quo for now
is the most practical. It's working now. Remember that the issue in the
ticket has not occurred in a practical example (yet). The main purpose of
this ticket as I see it is to document that we are not implementing the
model we think we're implementing. Changing it to another implementation
that also doesn't behave as our model isn't necessarily progress. It only
is if we're getting desired behaviour in a case that actually matters.
> The current registration order is such that "it works".
Hm, that may be backwards. Sage currently works because it's built with
the coercion discovery as it is at the moment. Patches wouldn't have made
it in if they didn't work (this is certainly true for doctest examples.
There can be other examples (future bug reports) out there that may fail.
We can of course try to rationalize the current model. It seems to me we
may be borrowing from the fact that the time line has no cycles (basically
the arrow of causality), so preferring maps that were put in "earlier"
should tend to not depend on later inserted maps.
Of course, this flies in the face of the model we're claiming to
implement: Properties of a digraph don't rely on the history of the
digraph. They only rely on the state of the graph.
If you want a history-sensitive graph, you could put as cost of the edge
the insertion time of the edge, and use the maximum over a path as the
cost of the path. Do you think that's a reasonable model?
--
Ticket URL: <http://trac.sagemath.org/ticket/15303#comment:41>
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.
