#13589: Controlling C3 to solve once for all the Method Resolution Order issues
for
category classes
-----------------------------------------------+----------------------------
Reporter: nthiery | Owner: nthiery
Type: defect | Status: new
Priority: major | Milestone: sage-5.5
Component: categories | Resolution:
Keywords: method resolution order, C3 | Work issues:
Report Upstream: N/A | Reviewers: Simon King,
Florent Hivert
Authors: Nicolas M. Thiéry | Merged in:
Dependencies: #13501 | Stopgaps:
-----------------------------------------------+----------------------------
Description changed by nthiery:
Old description:
> Python handles multiple inheritance by computing, for each class,
> a linear extension of all its super classes (the Method Resolution
> Order, MRO). The MRO is calculated recursively from local
> information (the *ordered* list of the direct super classes), with
> the so-called ``C3`` algorithm. This algorithm can fail if the local
> information is not consistent; worst, there exist hiearchies of
> classes with provably no consistent local information.
>
> For large hierarchy of classes, like those derived from categories in
> Sage, maintaining consistent local information by hand does not scale
> and leads to unpredictable ``C3`` failures (the dreaded "could not
> find a consistent method resolution order"); a maintenance nightmare.
>
> This patch implements a final solution to this problem. Namely, it
> allows for building automatically the local information from the bare
> class hierarchy in such a way that guarantees that the ``C3``
> algorithm will never fail.
>
> Err, but you said that this was provably impossible? Well, not if
> one relaxes a bit the hypotheses, but that's not something one
> would want to do by hand :-)
>
>
> Details: please see the extensive documentation at the top of the file
> sage/misc/c3_controlled.py in the attached patch.
>
> Status: the patch is functional, but still breaks a couple things here
> and there. In particular, some doctests need to be updated w.r.t. some
> changes in MRO and super_categories output. I will fix this as soon as
> the principle will be accepted.
>
> Credits: this patch is a followup to a study of the C3 algorithm together
> with Florent Hivert, and to discussions with Simon King and his
> implementation of C3.
New description:
Python handles multiple inheritance by computing, for each class,
a linear extension of all its super classes (the Method Resolution
Order, MRO). The MRO is calculated recursively from local
information (the *ordered* list of the direct super classes), with
the so-called ``C3`` algorithm. This algorithm can fail if the local
information is not consistent; worst, there exist hiearchies of
classes with provably no consistent local information.
For large hierarchy of classes, like those derived from categories in
Sage, maintaining consistent local information by hand does not scale
and leads to unpredictable ``C3`` failures (the dreaded "could not
find a consistent method resolution order"); a maintenance nightmare.
This patch implements a final solution to this problem. Namely, it
allows for building automatically the local information from the bare
class hierarchy in such a way that guarantees that the ``C3``
algorithm will never fail.
Err, but you said that this was provably impossible? Well, not if
one relaxes a bit the hypotheses, but that's not something one
would want to do by hand :-)
Details
-------
Please see the extensive documentation at the top of the file
sage/misc/c3_controlled.py in the attached patch.
Status
------
The patch is functional, but still breaks a couple things here and there.
In particular, some doctests need to be updated w.r.t. some changes in MRO
and super_categories output. I will fix this as soon as the principle will
be accepted.
The patch is also available on the Sage-Combinat queue (guarded out by
default by +functorial_construction).
Credits
-------
This patch is a followup to a study of the C3 algorithm together with
Florent Hivert, and to discussions with Simon King and his implementation
of C3.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13589#comment:1>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
