#11943: The category graph should comply with Python's method resolution order
---------------------------+------------------------------------------------
Reporter: SimonKing | Owner: nthiery
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7.3
Component: categories | Keywords: category graph, method resolution
order
Work_issues: | Upstream: N/A
Reviewer: | Author: Simon King
Merged: | Dependencies: #11900
---------------------------+------------------------------------------------
Old description:
> Let C be a category. `C.all_super_categories()` starts with
> `C.super_categories()` and finds all super categories inductively.
>
> Unfortunately, the algorithm of `C.all_super_categories()` does not
> comply with the C3 algorithm, that is used by Python to determine the
> method resolution order for `C.parent_class` and `C.element_class`.
>
> The aim of this ticket is to be more consistent. Eventually, for any
> category C (perhaps with modifications for hom categories), one should
> have
> {{{
> sage: C.parent_class.mro() == [X.parent_class for X in
> C.all_super_categories()] + [object]
> True
> sage: C.element_class.mro() == [X.element_class for X in
> C.all_super_categories()] + [object]
> True
> }}}
> and that test should become part of the test suite.
>
> At #11900, the implementation of `all_super_categories()` has been
> changed, so, work should rely on #11900.
>
> Unfortunately, it seems that the C3 algorithm can not simply be imported
> from Python, even though Python uses it internally, namely in
> `Objects/typeobject.c`. Looking at the implementation, it requires that
> one gets a list of types, while we want to use it on a list of objects.
>
> Therefore, we need to implement C3 from scratch. Implementing C3 is easy,
> but if it shall be fast, one needs to be careful.
>
> In particular, one needs to be able to `L.pop(0)` quickly, where L is a
> list. Unfortunately, `L.pop(0)` is slow, even in Cython. I found that, if
> the lists are not too long, it is best to revert L and do `L.pop()`
> instead, which is optimized in Cython. See the discussion at
> [http://groups.google.com/group/sage-
> support/browse_thread/thread/317aecee64ddab48 sage-devel].
>
> My plan is:
>
> * Provide the C3 algorithm in a new extension module `sage.misc.c3`
> * Use it to compute `all_super_categories()`
> * Add a test `_test_category_graph`, asserting that
> `self.parent_class.mro()` and `self.all_super_categories()` are
> compatible.
>
> First tests indicate that the change of order on
> `C.all_super_categories()` is fine (sage does not crash, and most tests
> in sage.categories pass. However, one really needs to look at the
> performance.
New description:
Let C be a category. `C.all_super_categories()` starts with
`C.super_categories()` and finds all super categories inductively.
Unfortunately, the algorithm of `C.all_super_categories()` does not comply
with the C3 algorithm, that is used by Python to determine the method
resolution order for `C.parent_class` and `C.element_class`.
The aim of this ticket is to be more consistent. Eventually, for any
category C (perhaps with modifications for hom categories), one should
have
{{{
sage: C.parent_class.mro() == [X.parent_class for X in
C.all_super_categories()] + [object]
True
sage: C.element_class.mro() == [X.element_class for X in
C.all_super_categories()] + [object]
True
}}}
and that test should become part of the test suite.
At #11900, the implementation of `all_super_categories()` has been
changed, so, work should rely on #11900.
Unfortunately, it seems that the C3 algorithm can not simply be imported
from Python, even though Python uses it internally, namely in
`Objects/typeobject.c`. Looking at the implementation, it requires that
one gets a list of types, while we want to use it on a list of objects.
Therefore, we need to implement C3 from scratch. Implementing C3 is easy,
but if it shall be fast, one needs to be careful.
In particular, one needs to be able to `L.pop(0)` quickly, where L is a
list. Unfortunately, `L.pop(0)` is slow, even in Cython. I found that, if
the lists are not too long, it is best to revert L and do `L.pop()`
instead, which is optimized in Cython. See the discussion at
[http://groups.google.com/group/sage-
support/browse_thread/thread/317aecee64ddab48 sage-devel].
My plan is:
* Provide the C3 algorithm in a new extension module `sage.misc.c3`
* Use it to compute `all_super_categories()`
* Add a test `_test_category_graph`, asserting that
`self.parent_class.mro()` and `self.all_super_categories()` are
compatible.
First tests indicate that the change of order on
`C.all_super_categories()` is fine (sage does not crash, and most tests in
sage.categories pass. However, one really needs to look at the
performance.
Apply:
[attachment:trac11943_mro_for_all_super_categories_lazy.patch]
--
Comment(by SimonKing):
I have created a more invasive patch: It turns `C.super_categories()` and
`C.all_super_categories(proper)` into lazy attributes, and it uses the C3
algorithm in a more efficient way.
The two patches are alternative. Personally, I prefer the second patch. If
the reviewer disagrees and suggests to use the first patch, I'd like to
add one improvement to the first patch. If the reviewer agrees with me,
then eventually either this patch or the patch from #11935 needs to be
rebased.
I just tested that all doctests pass, with sage-4.7.2.alpha3+#11900+the
second patch from here.
And here are some timings:
With just #11900:
{{{
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage
elltest1.sage
real 0m18.089s
user 0m17.633s
sys 0m0.344s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage
ellbsd.sage
real 0m5.578s
user 0m5.084s
sys 0m0.400s
}}}
and
{{{
sage: L = [Algebras(GF(p)) for p in prime_range(10000)]
sage: %time X = [C.all_super_categories() for C in L]
CPU times: user 0.72 s, sys: 0.01 s, total: 0.72 s
Wall time: 0.73 s
}}}
With #11900+the second patch from here:
{{{
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage
elltest1.sage
real 0m17.799s
user 0m17.333s
sys 0m0.384s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage
ellbsd.sage
real 0m5.408s
user 0m4.956s
sys 0m0.376s
}}}
and
{{{
sage: L = [Algebras(GF(p)) for p in prime_range(10000)]
# all_super_categories is lazy now, we are not calling it
sage: %time X = [C.all_super_categories for C in L]
CPU times: user 0.54 s, sys: 0.00 s, total: 0.54 s
Wall time: 0.54 s
}}}
Note an additional doc test, demonstrating that the new version of
all_super_categories can detect inconsistencies:
{{{
sage: class X(Category):
... @lazy_attribute
... def super_categories(self):
... return [Objects()]
sage: class X(Category):
... @lazy_attribute
... def super_categories(self):
... return [Objects()]
sage: class Y(Category):
... @lazy_attribute
... def super_categories(self):
... return [Objects()]
sage: class A(Category):
... @lazy_attribute
... def super_categories(self):
... return [X(),Y()]
sage: class B(Category):
... @lazy_attribute
... def super_categories(self):
... return [Y(),X()]
sage: class Foo(Category):
... @lazy_attribute
... def super_categories(self):
... return [A(),B()]
sage: F = Foo()
}}}
Python is not able to create a consistent mro for the parent class - and
all_super_categories detects that inconsistency as well:
{{{
sage: F.parent_class
Traceback (most recent call last):
...
TypeError: Cannot create a consistent method resolution
order (MRO) for bases X.parent_class, Y.parent_class
sage: F.all_super_categories
Traceback (most recent call last):
...
ValueError: Can not merge the items Category of x, Category of y.
}}}
Of course, there still is the new consistency test for the category graph
in the test suite.
So, it can really be reviewed now, and my suggestion is:
Apply trac11943_mro_for_all_super_categories_lazy.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11943#comment:8>
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.
