Sage: Ticket #11943: The category graph should comply with Python's method resolution order
https://trac.sagemath.org/ticket/11943
<p>
Let C be a category. <code>C.all_super_categories()</code> starts with <code>C.super_categories()</code> and finds all super categories inductively.
</p>
<p>
Unfortunately, the algorithm of <code>C.all_super_categories()</code> does not comply with the C3 algorithm, that is used by Python to determine the method resolution order for <code>C.parent_class</code> and <code>C.element_class</code>.
</p>
<p>
The aim of this ticket is to be more consistent. Eventually, for any category C (perhaps with modifications for hom categories), one should have
</p>
<pre class="wiki">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
</pre><p>
and that test should become part of the test suite.
</p>
<p>
At <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>, the implementation of <code>all_super_categories()</code> has been changed, so, work should rely on <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>.
</p>
<p>
Unfortunately, it seems that the C3 algorithm can not simply be imported from Python, even though Python uses it internally, namely in <code>Objects/typeobject.c</code>. Looking at the implementation, it requires that one gets a list of types, while we want to use it on a list of objects.
</p>
<p>
Therefore, we need to implement C3 from scratch. Implementing C3 is easy, but if it shall be fast, one needs to be careful.
</p>
<p>
In particular, one needs to be able to <code>L.pop(0)</code> quickly, where L is a list. Unfortunately, <code>L.pop(0)</code> is slow, even in Cython. I found that, if the lists are not too long, it is best to revert L and do <code>L.pop()</code> instead, which is optimized in Cython. See the discussion at <a class="ext-link" href="http://groups.google.com/group/sage-support/browse_thread/thread/317aecee64ddab48"><span class="icon"></span>sage-devel</a>.
</p>
<p>
What my patch does:
</p>
<ul><li>Provide the C3 algorithm in a new extension module <code>sage.misc.c3</code>
</li><li>Use it to compute <code>all_super_categories()</code>
</li><li>Add a test <code>_test_category_graph</code>, asserting that <code>self.parent_class.mro()</code> and <code>self.all_super_categories()</code> are compatible.
</li></ul><p>
Apply:
</p>
<blockquote>
<p>
<a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11943/trac11943_mro_for_all_super_categories_lazy_hook.patch" title="Attachment 'trac11943_mro_for_all_super_categories_lazy_hook.patch' in Ticket #11943">trac11943_mro_for_all_super_categories_lazy_hook.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11943/trac11943_mro_for_all_super_categories_lazy_hook.patch" title="Download"></a>
<a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11943/trac11943_mro_for_all_super_categories_lazy_hook-review-nt.patch" title="Attachment 'trac11943_mro_for_all_super_categories_lazy_hook-review-nt.patch' in Ticket #11943">trac11943_mro_for_all_super_categories_lazy_hook-review-nt.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11943/trac11943_mro_for_all_super_categories_lazy_hook-review-nt.patch" title="Download"></a>
</p>
</blockquote>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11943
Trac 1.1.6SimonKingFri, 21 Oct 2011 16:22:13 GMT
https://trac.sagemath.org/ticket/11943#comment:1
https://trac.sagemath.org/ticket/11943#comment:1
<p>
With the new test, I found a bug in algebra_ideals:
</p>
<pre class="wiki">sage: C = AlgebraIdeals(FreeAlgebra(QQ,2,'a,b'))
sage: C.parent_class
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (396, 0))
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
/home/king/Seminar/<ipython console> in <module>()
/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/lazy_attribute.pyc in __get__(self, a, cls)
507 if a is None: # when doing cls.x for cls a class and x a lazy attribute
508 return self
--> 509 result = self.f(a)
510 if result is NotImplemented:
511 # Workaround: we make sure that cls is the class
/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/categories/category.pyc in parent_class(self)
626 """
627 return dynamic_class("%s.parent_class"%self.__class__.__name__,
--> 628 tuple(cat.parent_class for cat in self.super_categories()),
629 self.ParentMethods,
630 reduction = (getattr, (self, "parent_class")))
/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/cachefunc.pyc in __call__(self, *args, **kwds)
553 return self.cache[k]
554 except KeyError:
--> 555 w = self._cachedmethod._instance_call(self._instance, *args, **kwds)
556 self.cache[k] = w
557 return w
/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/cachefunc.pyc in _instance_call(self, inst, *args, **kwds)
776
777 """
--> 778 return self._cachedfunc.f(inst, *args, **kwds)
779
780 def _get_instance_cache(self, inst):
/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/categories/algebra_ideals.pyc in super_categories(self)
67 [Category of algebra modules over Univariate Polynomial Ring in x over Rational Field]
68 """
69 from algebra_modules import AlgebraModules
70 R = self.algebra()
---> 71 return [AlgebraModules(R)]
/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/classcall_metaclass.pyc in __call__(cls, *args, **options)
256 return cls.__classcall_private__(cls, *args, **options)
257 elif hasattr(cls, "__classcall__"):
--> 258 return cls.__classcall__(cls, *args, **options)
259 else:
260 return type.__call__(cls, *args, **options)
/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/cachefunc.pyc in __call__(self, *args, **kwds)
176 return self.cache[k]
177 except KeyError:
--> 178 w = self.f(*args, **kwds)
179 self.cache[k] = w
180 return w
/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/structure/unique_representation.pyc in __classcall__(cls, *args, **options)
447 True
448 """
--> 449 instance = type.__call__(cls, *args, **options)
450 assert isinstance( instance, cls )
451 if instance.__class__.__reduce__ == UniqueRepresentation.__reduce__:
/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/categories/algebra_modules.pyc in __init__(self, A)
53 from sage.categories.commutative_algebras import CommutativeAlgebras
54 if not hasattr(A, "base_ring") or not A in CommutativeAlgebras(A.base_ring()):
---> 55 raise TypeError, "A (=%s) must be a commutative algebra"%A
56 Category_module.__init__(self, A)
57
TypeError: A (=Free Algebra on 2 generators (a, b) over Rational Field) must be a commutative algebra
</pre><p>
Thus, apparently, that category has never been used.
</p>
<p>
The problem is that the super categories of the category of algebra ideals should be the category of algebra modules. However, while the former accepts non-commutative algebras, the latter wants to see commutative algebras.
</p>
<p>
The clean way to proceed would be: Make algebra modules work over non-commutative rings. If that is too much of work, C.super_categories() should be <code>[]</code> if C is the category of algebra ideals over a non-commutative rings.
</p>
TicketSimonKingFri, 21 Oct 2011 21:15:59 GMTstatus changed; dependencies, author set
https://trac.sagemath.org/ticket/11943#comment:2
https://trac.sagemath.org/ticket/11943#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>dependencies</strong>
set to <em>#11900</em>
</li>
<li><strong>author</strong>
set to <em>Simon King</em>
</li>
</ul>
<p>
Patch's up!
</p>
<p>
To my surprise, the change in the order of super categories was relatively harmless. In few cases, a test involving all_super_categories had to change.
</p>
<p>
I added a test <code>_test_category_graph</code> to the Test Suite of categories. By that test, I found one bug in algebra_ideals, which I fixed. Hom categories can not use the new test yet, since it tests the mro of the parent class against the list of parent classes of all super categories - which is fairly inconsistent for hom categories. That is already a "to do", and should be part of the next category overhaule.
</p>
<p>
Apart from these small changes, all doc tests passed! In particular, I did not need to change <code>super_categories</code> (except for algebra ideals): The current category graph seems to be consistent!!
</p>
<p>
That was the good news.
</p>
<p>
The bad news is that we have a regression in the computation of <code>all_super_categories</code>. With <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>, we have
</p>
<pre class="wiki">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.74 s, sys: 0.01 s, total: 0.75 s
Wall time: 0.75 s
</pre><p>
With the patches from here added, we only have
</p>
<pre class="wiki">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 1.06 s, sys: 0.02 s, total: 1.07 s
Wall time: 1.08 s
</pre><p>
I tried hard to make my C3 implementation as fast as possible in the range we need: few lists (say, 4) of moderate length (not more than 60).
</p>
<p>
I think the performance should be improved. But a review can already be started.
</p>
TicketnthieryFri, 21 Oct 2011 22:10:46 GMT
https://trac.sagemath.org/ticket/11943#comment:3
https://trac.sagemath.org/ticket/11943#comment:3
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:1" title="Comment 1">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
With the new test, I found a bug in algebra_ideals:
The problem is that the super categories of the category of algebra ideals should be the category of algebra modules. However, while the former accepts non-commutative algebras, the latter wants to see commutative algebras.
The clean way to proceed would be: Make algebra modules work over non-commutative rings. If that is too much of work, C.super_categories() should be <code>[]</code> if C is the category of algebra ideals over a non-commutative rings.
</p>
</blockquote>
<p>
+1. Actually my patch on <a class="closed ticket" href="https://trac.sagemath.org/ticket/10963" title="enhancement: Axioms and more functorial constructions (closed: fixed)">#10963</a> is adding a TODO about it :-)
</p>
TicketnthieryFri, 21 Oct 2011 22:13:55 GMT
https://trac.sagemath.org/ticket/11943#comment:4
https://trac.sagemath.org/ticket/11943#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:2" title="Comment 2">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
To my surprise, the change in the order of super categories was relatively harmless. In few cases, a test involving all_super_categories had to change.
</p>
</blockquote>
<p>
I am not so surprised, since most categories are actually used by some
parent (which detects any incompatibility). But it's very nice to
detect such incompatibilities earlier on and to catch them
systematically in the <a class="missing wiki">TestSuite?</a>!
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketSimonKingSun, 23 Oct 2011 14:08:28 GMT
https://trac.sagemath.org/ticket/11943#comment:5
https://trac.sagemath.org/ticket/11943#comment:5
<p>
I tried to track down the regression of <code>all_super_categories</code>. Recall that my patch from <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a> did improve the implementation of <code>all_super_categories</code>, but did not change the algorithm.
</p>
<p>
With <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>, the main work is done in <code>_all_super_categories_raw</code>. With the patch from here, the work is done in <code>c3_algorithm</code> - and according to %prun, <em>less</em> time is spent in <code>c3_algorithm</code> than it was in <code>_all_super_categories_raw</code>. However, more time is spent in the expression
</p>
<pre class="wiki">C.all_super_categories() for C in self.super_categories()
</pre><p>
I guess I have to improve the implementation of the recursion.
</p>
TicketSimonKingSun, 23 Oct 2011 14:13:11 GMT
https://trac.sagemath.org/ticket/11943#comment:6
https://trac.sagemath.org/ticket/11943#comment:6
<p>
PS: It also seems that much time is spent in <code>super_categories()</code>, which is a cached method. Probably it would be better to turn it into a lazy attribute (or have <em>two</em> lazy attributes, namely for the case <code>proper=True</code> and <code>proper=False</code>).
</p>
<p>
Namely, even though <a class="closed ticket" href="https://trac.sagemath.org/ticket/11115" title="enhancement: Rewrite cached_method in Cython (closed: fixed)">#11115</a> will almost totally reduce the overhead of calling a cached function, a lazy attribute will always be faster.
</p>
TicketSimonKingSun, 23 Oct 2011 16:27:38 GMT
https://trac.sagemath.org/ticket/11943#comment:7
https://trac.sagemath.org/ticket/11943#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:6" title="Comment 6">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
PS: It also seems that much time is spent in <code>super_categories()</code>, which is a cached method. Probably it would be better to turn it into a lazy attribute (or have <em>two</em> lazy attributes, namely for the case <code>proper=True</code> and <code>proper=False</code>).
</p>
</blockquote>
<p>
Sorry, I meant: One lazy attribute C.super_categories, and two lazy attributes C.all_super_categories and C.all_super_categories_proper (super_categories() has no arguments).
</p>
TicketSimonKingSun, 23 Oct 2011 21:48:56 GMTdescription changed
https://trac.sagemath.org/ticket/11943#comment:8
https://trac.sagemath.org/ticket/11943#comment:8
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11943?action=diff&version=8">diff</a>)
</li>
</ul>
<p>
I have created a more invasive patch: It turns <code>C.super_categories()</code> and <code>C.all_super_categories(proper)</code> into lazy attributes, and it uses the C3 algorithm in a more efficient way.
</p>
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/11935" title="enhancement: Make parent/element classes independent of base rings (closed: fixed)">#11935</a> needs to be rebased.
</p>
<p>
I just tested that all doctests pass, with sage-4.7.2.alpha3+<a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>+the second patch from here.
</p>
<p>
And here are some timings:
With just <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>:
</p>
<pre class="wiki">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
</pre><p>
and
</p>
<pre class="wiki">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
</pre><p>
With <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>+the second patch from here:
</p>
<pre class="wiki">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
</pre><p>
and
</p>
<pre class="wiki">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
</pre><p>
Note an additional doc test, demonstrating that the new version of all_super_categories can detect inconsistencies:
</p>
<pre class="wiki">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()
</pre><p>
Python is not able to create a consistent mro for the parent class - and all_super_categories detects that inconsistency as well:
</p>
<pre class="wiki">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.
</pre><p>
Of course, there still is the new consistency test for the category graph in the test suite.
</p>
<p>
So, it can really be reviewed now, and my suggestion is:
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy.patch
</p>
TicketSimonKingWed, 26 Oct 2011 19:20:20 GMT
https://trac.sagemath.org/ticket/11943#comment:9
https://trac.sagemath.org/ticket/11943#comment:9
<p>
There was no reply on sage-combinat-devel and only little reply on sage-devel: The only reply was Jason Grout stating that the use of attributes is often more pythonic than the use of a method.
</p>
<p>
So, the idea to turn super_categories and all_super_categories into lazy attributes is supported.
</p>
TicketSimonKingSat, 29 Oct 2011 05:53:52 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/11943#comment:10
https://trac.sagemath.org/ticket/11943#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>Preserve super_categories etc. as methods, but introduce a lazy attribute _super_categories</em>
</li>
</ul>
<p>
<a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_thread/thread/ab03a0d422810e73"><span class="icon"></span>Maarten</a> suggested the following:
</p>
<pre class="wiki">What I think would be the best solution in this case would be is:
make lazy attributes
_super_categories and
_all_super_categories
Make the functions super_categories and all_super_categories say in the
documentation that developers shouldn't use these but that they should use
the lazy attributes.
</pre><p>
I think that this would be a very good solution indeed.
</p>
TicketSimonKingSat, 29 Oct 2011 08:53:25 GMT
https://trac.sagemath.org/ticket/11943#comment:11
https://trac.sagemath.org/ticket/11943#comment:11
<p>
I think the following model is best for preserving backwards compatibility:
</p>
<ul><li>If one wants to provide the super categories of a category, one should implement a method super_categories() - this is what one would currently do.
</li><li>There is a new lazy attribute _super_categories defined for the base class of categories. That lazy attribute calls the method super_categories(). Of course, calling the method happens only once, so that the speed is acceptable.
</li><li>In all <em>applications</em>, the method call super_categories() shall be replaced by getting the attribute _super_categories. That is explained in a note to the developers in the documentation of super_categories.
</li><li>There is a lazy attribute _all_super_categories and _all_super_categories_proper, and there is still a method all_super_categories(proper=False). The method returns the appropriate lazy attribute, and the documentation of the method states that one should better use the lazy attributes.
</li></ul>
TicketSimonKingSat, 29 Oct 2011 15:17:21 GMTstatus changed; cc set; work_issues deleted
https://trac.sagemath.org/ticket/11943#comment:12
https://trac.sagemath.org/ticket/11943#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>cc</strong>
<em>hivert</em> <em>mderickx</em> added
</li>
<li><strong>work_issues</strong>
<em>Preserve super_categories etc. as methods, but introduce a lazy attribute _super_categories</em> deleted
</li>
</ul>
<p>
I have changed my patch according to what I learnt from the discussion on <a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_thread/thread/ab03a0d422810e73"><span class="icon"></span>sage-devel</a>. Namely:
</p>
<ul><li>I preserved the old methods <code>super_categories</code> and <code>all_super_categories</code>, so that the users can still work with them and can read their documentation.
</li><li>In particular, if one wants to define a new category, one would still define a <em>method</em> (no need for a cached method) called <code>super_categories</code> that returns the immediate super categories. However, the documentation now also states that internally (i.e., for development), the new lazy attributes explained below should be used.
</li><li>The patch introduces three lazy attributes <code>_super_categories</code>, <code>_all_super_categories</code> and <code>_all_super_categories_proper</code> that carry the lists of (immediate or all) super categories. If one asks for the super categories in code, the fastest way is to request these lazy attributes, not calling the old methods.
</li></ul><p>
Anyway, why do I see a need to make things faster? Recall that the purpose of this ticket is to order the list of all super categories according to Python's method resolution order, i.e., the C3 algorithm. I did my very best to implement the C3 algorithm as fast as possible. However:
</p>
<ul><li>When I keep super_categories() what they are, then even my best attempt to implement all_super_categories based on C3 resulted in a mild regression.
</li><li>When I keep super_categories() what they are (namely cached methods) and use <a class="closed ticket" href="https://trac.sagemath.org/ticket/11115" title="enhancement: Rewrite cached_method in Cython (closed: fixed)">#11115</a>, then there is neither a regression nor a speed-up.
</li><li>When I replace super_categories() by _super_categories (a lazy attribute), then I am getting a speed-up, even without <a class="closed ticket" href="https://trac.sagemath.org/ticket/11115" title="enhancement: Rewrite cached_method in Cython (closed: fixed)">#11115</a>.
</li></ul><p>
Here are the data. I've run <code>sage -t devel/sage/sage/schemes/</code> and found these total running times:
</p>
<ul><li>620.7 seconds with sage-4.7.3.alpha3
</li><li>600.1 seconds with sage-4.7.3.alpha3 and <a class="closed ticket" href="https://trac.sagemath.org/ticket/11943" title="enhancement: The category graph should comply with Python's method resolution order (closed: fixed)">#11943</a> (plus dependencies)
</li></ul><p>
That's not much (3.3% speedup), but certainly better than a regression.
</p>
TicketSimonKingSat, 29 Oct 2011 15:21:33 GMT
https://trac.sagemath.org/ticket/11943#comment:13
https://trac.sagemath.org/ticket/11943#comment:13
<p>
I forgot the patch bot:
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy.patch
</p>
TicketSimonKingThu, 03 Nov 2011 09:03:25 GMTstatus changed
https://trac.sagemath.org/ticket/11943#comment:14
https://trac.sagemath.org/ticket/11943#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
There is a new suggestion, also based on the <a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_thread/thread/ab03a0d422810e73"><span class="icon"></span>sage-devel thread</a>:
</p>
<p>
If we want to test whether a category C is a super category of a category D, then we currently try to find C in the <em>list</em> of all super categories. But it is much faster to search it in a <em>frozen set</em> of super categories.
</p>
<p>
So, I suggest to use a lazy attribute <code>_set_of_super_categories</code>, providing the frozen set. It will be used in <code>is_subcategory</code>. Of course, the <em>list</em> of super categories should still be available, and its order should comply with Python's mro, according to the subject of this ticket.
</p>
<p>
Since <a class="closed ticket" href="https://trac.sagemath.org/ticket/11115" title="enhancement: Rewrite cached_method in Cython (closed: fixed)">#11115</a> is merged into sage-4.7.3.alpha1, I wonder whether it is still necessary to have the list of all super categories as a lazy attribute, or whether a cached method is fast enough. I'll need some tests.
</p>
<p>
However, I think it is a good idea to have a lazy attribute <code>_super_categories</code>. In that way, we have the speed even if the user does not use @cached_method when (s)he implements the method <code>super_categories()</code>.
"Needs work", until I have sorted it out.
</p>
TicketSimonKingThu, 03 Nov 2011 14:19:08 GMT
https://trac.sagemath.org/ticket/11943#comment:15
https://trac.sagemath.org/ticket/11943#comment:15
<p>
I found another detail that may fit here: <code>Category.is_subcategory</code> contains the lines
</p>
<pre class="wiki"> assert(isinstance(c, Category))
if isinstance(self, JoinCategory):
for cat in self._super_categories:
if cat.is_subcategory(c):
return True
return False
</pre><p>
First, I don't see why it should be needed to assert that c is a Category. It seems like a waste of time to me.
</p>
<p>
Secondly, the loop does nothing more than to test the cat is in the set of super categories of self. So, it can be safely erased. And it is a lot faster. For example:
</p>
<p>
With my current patch, we have
</p>
<pre class="wiki">sage: P.<x,y> = QQ[]
sage: C = CommutativeRings()
sage: P.category()
Join of Category of unique factorization domains and Category of commutative algebras over Rational Field
sage: P in C
True
sage: %timeit P in C
625 loops, best of 3: 12.1 µs per loop
</pre><p>
With my patch after deletion of the lines criticised above, we have
</p>
<pre class="wiki">sage: P.<x,y> = QQ[]
sage: C = CommutativeRings()
sage: P.category()
Join of Category of unique factorization domains and Category of commutative algebras over Rational Field
sage: P in C
True
sage: %timeit P in C
625 loops, best of 3: 6.39 µs per loop
</pre><p>
So, my next patch version will remove these lines, provided that doc tests pass.
</p>
TicketjdemeyerThu, 03 Nov 2011 16:14:43 GMTmilestone deleted
https://trac.sagemath.org/ticket/11943#comment:16
https://trac.sagemath.org/ticket/11943#comment:16
<ul>
<li><strong>milestone</strong>
<em>sage-4.7.3</em> deleted
</li>
</ul>
<p>
Milestone sage-4.7.3 deleted
</p>
TicketnthieryThu, 03 Nov 2011 23:40:31 GMTmilestone set
https://trac.sagemath.org/ticket/11943#comment:17
https://trac.sagemath.org/ticket/11943#comment:17
<ul>
<li><strong>milestone</strong>
set to <em>sage-4.8</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:14" title="Comment 14">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
So, I suggest to use a lazy attribute <code>_set_of_super_categories</code>, providing the frozen set. It will be used in <code>is_subcategory</code>. Of course, the <em>list</em> of super categories should still be available, and its order should comply with Python's mro, according to the subject of this ticket.
</p>
</blockquote>
<p>
+1 (obviously :-)), though I kind of like better _all_super_categories_as_set to insist on the fact that it is very close to all_super_categories.
</p>
<blockquote class="citation">
<p>
Since <a class="closed ticket" href="https://trac.sagemath.org/ticket/11115" title="enhancement: Rewrite cached_method in Cython (closed: fixed)">#11115</a> is merged into sage-4.7.3.alpha1, I wonder whether it is still necessary to have the list of all super categories as a lazy attribute, or whether a cached method is fast enough. I'll need some tests.
</p>
</blockquote>
<p>
+1 on getting rid of this lazy attribute, unless there is a very clearly defined use case where speed is essential.
</p>
<blockquote class="citation">
<p>
However, I think it is a good idea to have a lazy attribute <code>_super_categories</code>. In that way, we have the speed even if the user does not use @cached_method when (s)he implements the method <code>super_categories()</code>.
</p>
</blockquote>
<p>
+1
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketnthieryThu, 03 Nov 2011 23:55:33 GMT
https://trac.sagemath.org/ticket/11943#comment:18
https://trac.sagemath.org/ticket/11943#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:15" title="Comment 15">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I found another detail that may fit here: <code>Category.is_subcategory</code> contains the lines
</p>
<pre class="wiki"> assert(isinstance(c, Category))
if isinstance(self, JoinCategory):
for cat in self._super_categories:
if cat.is_subcategory(c):
return True
return False
</pre><p>
First, I don't see why it should be needed to assert that c is a Category. It seems like a waste of time to me.
</p>
</blockquote>
<p>
As for any reasonable programming language, Python allows to
completely disable assertion tests, to encourage the programmer to put
more safety guards and write programmatically his
preconditions/assertions/..., knowing that in production there won't
be any penalty. Alas, this can't be done on the fly like in MuPAD for
switching between debugging and full speed computation modes inside a
given session (a feature I loved). Still this can be achieved in
principle on a new session by passing -O to the Python
interpreter. Maybe we should add this option to the Sage script
itself.
</p>
<p>
In that particular case, I guess I once met a bug where something was
passed to is_subcategory which was not a category, so I felt safer
with the assertion test.
</p>
<blockquote class="citation">
<p>
Secondly, the loop does nothing more than to test the cat is in the
set of super categories of self. So, it can be safely erased. And it
is a lot faster. ...
So, my next patch version will remove these lines, provided that doc tests pass.
</p>
</blockquote>
<p>
I don't remember anymore why I did a special case for join categories,
so +1.
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketSimonKingFri, 04 Nov 2011 11:02:59 GMTstatus changed
https://trac.sagemath.org/ticket/11943#comment:19
https://trac.sagemath.org/ticket/11943#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Dear Nicolas,
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:18" title="Comment 18">nthiery</a>:
</p>
<blockquote class="citation">
<p>
In that particular case, I guess I once met a bug where something was
passed to is_subcategory which was not a category, so I felt safer
with the assertion test.
</p>
</blockquote>
<p>
But I think, in this particular case, nothing nasty can happen.
</p>
<p>
Ultimately, it is tested whether the argument c belongs to the list of all super categories of <code>self</code>. Hence, unexpected things can only happen if c is not a category but is equal to a category, or if <code>self.super_categories()</code> contains something that is not a category.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
So, my next patch version will remove these lines, provided that doc tests pass.
</p>
</blockquote>
<p>
I don't remember anymore why I did a special case for join categories,
so +1.
</p>
</blockquote>
<p>
I have just attached a new version of my patch. I used several techniques to speed up <code>is_subcategory</code>.
</p>
<p>
In particular, I rely on the hypothesis that if a category C1 has a base (ring) and is super-category of C2, then C2 must have the same base (ring). Hence, if the base rings differ or C2 has no base ring then we can very quickly conclude that C1 is not a super-categoriy of C2.
</p>
<p>
This turns out to be very helpful in elliptic curve computations. Namely, it often suffices to study the base rings, so that it is not needed to construct the list of all super categories.
</p>
<p>
By consequence, I needed to introduce a <code>base()</code> method for various settings. For example, tensor products preserve the base. And for join categories, I argue: If <code>C = JoinCategory((C1,C2,...))</code> then <code>C.base()</code> should be the first answer that one obtains by walking through the list <code>C1.base(), C2.base(),...</code>.
</p>
<p>
I think this makes sense in the intended application: By <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>, polynomial rings over F belong to a join category of a base-free category (unique factorization domains) and a category with base F (F-algebras).
</p>
<p>
The code of is_subcategory is now (with some comments added):
</p>
<div class="wiki-code"><div class="code"><pre><span class="c"># No cached method, currently</span>
<span class="k">def</span> <span class="nf">is_subcategory</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> c<span class="p">):</span>
<span class="k">if</span> c <span class="ow">is</span> <span class="bp">self</span><span class="p">:</span> <span class="c"># short path for a common case</span>
<span class="k">return</span> <span class="bp">True</span>
<span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span>c<span class="p">,</span> JoinCategory<span class="p">):</span>
<span class="k">return</span> <span class="nb">all</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span>is_subcategory<span class="p">(</span>x<span class="p">)</span> <span class="k">for</span> x <span class="ow">in</span> c<span class="o">.</span>_super_categories<span class="p">)</span>
<span class="k">try</span><span class="p">:</span>
<span class="c"># If the lazy attribute has already been computed, then we do not</span>
<span class="c"># need to bother about the categories having bases.</span>
<span class="c"># Here, the trick is that we look in self.__dict__, so that we do</span>
<span class="c"># not trigger computation of self._set_of_super_categories, if it has</span>
<span class="c"># not been done before.</span>
<span class="k">return</span> c <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span>__dict__<span class="p">[</span><span class="s">'_set_of_super_categories'</span><span class="p">]</span>
<span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
<span class="k">pass</span>
<span class="c"># In elliptic curves, one often has categories over different base rings.</span>
<span class="c"># Thus, as a short-path, we compare the base rings first, before we try</span>
<span class="c"># to compute the set of all super-categories.</span>
<span class="k">try</span><span class="p">:</span>
cbase <span class="o">=</span> c<span class="o">.</span>base<span class="p">()</span>
<span class="k">except</span> <span class="p">(</span><span class="ne">AttributeError</span><span class="p">,</span> <span class="ne">TypeError</span><span class="p">,</span> <span class="ne">NotImplementedError</span><span class="p">):</span>
cbase <span class="o">=</span> <span class="bp">None</span>
<span class="k">if</span> cbase <span class="ow">is</span> <span class="ow">not</span> <span class="bp">None</span><span class="p">:</span>
<span class="k">try</span><span class="p">:</span>
selfbase <span class="o">=</span> <span class="bp">self</span><span class="o">.</span>base<span class="p">()</span>
<span class="k">except</span> <span class="p">(</span><span class="ne">AttributeError</span><span class="p">,</span> <span class="ne">TypeError</span><span class="p">,</span> <span class="ne">NotImplementedError</span><span class="p">):</span>
selfbase <span class="o">=</span> <span class="bp">None</span>
<span class="k">if</span> selfbase <span class="ow">is</span> <span class="ow">not</span> cbase<span class="p">:</span>
<span class="k">return</span> <span class="bp">False</span>
<span class="c"># Now, the only remaining thing to do is to look at the super categories.</span>
<span class="c"># Looking it up in a (frozen) set is quickest:</span>
<span class="k">return</span> c <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span>_set_of_super_categories
</pre></div></div><p>
With the new patch, all long doctests pass - needs review!
</p>
<p>
I am now attending a lecture and will try to provide some timings afterwards.
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy.patch
</p>
TicketSimonKingFri, 04 Nov 2011 13:21:59 GMTstatus changed
https://trac.sagemath.org/ticket/11943#comment:20
https://trac.sagemath.org/ticket/11943#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:19" title="Comment 19">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:18" title="Comment 18">nthiery</a>:
By consequence, I needed to introduce a <code>base()</code> method for various settings. For example, tensor products preserve the base. And for join categories, I argue: If <code>C = JoinCategory((C1,C2,...))</code> then <code>C.base()</code> should be the first answer that one obtains by walking through the list <code>C1.base(), C2.base(),...</code>.
</p>
</blockquote>
<p>
I think that's a bad idea, after all. For example, one would have
</p>
<pre class="wiki">sage: C = Category.join([Algebras(GF(5)),Modules(ZZ)])
sage: C.is_subcategory(Modules(ZZ))
False
</pre><p>
But I have a suggestion:
</p>
<p>
<code>base()</code> provides a speed-up in an important application: Polynomial rings over F. In that situation, one has a join category that clearly should have a base, namely F. So, perhaps one should add an optional parameter <code>base=None</code> to the construction of a join category.
</p>
<p>
So, one could have something like
</p>
<pre class="wiki">sage: P.<x,y> = QQ[]
sage: P.category()
Join over Rational Field of Category of unique factorization domains and Category of commutative algebras over Rational Field
sage: P.category().base()
Rational Field
</pre><p>
and at the same time
</p>
<pre class="wiki">sage: C = Category.join([Algebras(GF(5)),Modules(ZZ)])
sage: print C.base()
None
</pre><p>
What do you think?
</p>
TicketmderickxFri, 04 Nov 2011 16:25:00 GMT
https://trac.sagemath.org/ticket/11943#comment:21
https://trac.sagemath.org/ticket/11943#comment:21
<p>
Where can I find the specific elliptic curve code you mention?
</p>
TicketSimonKingFri, 04 Nov 2011 16:50:28 GMT
https://trac.sagemath.org/ticket/11943#comment:22
https://trac.sagemath.org/ticket/11943#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:21" title="Comment 21">mderickx</a>:
</p>
<blockquote class="citation">
<p>
Where can I find the specific elliptic curve code you mention?
</p>
</blockquote>
<p>
I was referring to the things that were discussed on <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>. That ticket is about a serious speed regression in elliptic curves caused by <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>. And analysing it, using prun and so on, it turned out that really a lot of time has been spent on computing the list of all super categories. The problem is that caching the list of super categories does not really help, since one has many different categories (of algebras, for example) over different base fields.
</p>
<p>
But now that you mention it: It could be that the remark in the code above
</p>
<pre class="wiki"> # In elliptic curves, one often has categories over different base rings.
# Thus, as a short-path, we compare the base rings first, before we try
# to compute the set of all super-categories.
</pre><p>
is misleading.
</p>
<p>
The code is supposed to recognise very quickly that a category with base is not contained in a category with a different base. I am afraid I can not show you the original example that made me suggest this bit of code. However, here are some examples showing that it helps.
</p>
<p>
With the base test (each example being in a new session):
</p>
<pre class="wiki">sage: L = [GF(p)['x','y'] for p in prime_range(5000)]
sage: C = CommutativeRings()
# here the test is not used - this is to show that there is almost no regression
sage: %time [X in C for X in L]
CPU times: user 0.29 s, sys: 0.00 s, total: 0.29 s
Wall time: 0.29 s
</pre><pre class="wiki">sage: L = [GF(p)['x','y'] for p in prime_range(5000)]
sage: D = Modules(ZZ)
sage: %time [X in D for X in L]
CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s
Wall time: 0.06 s
</pre><p>
With the base test commented out:
</p>
<pre class="wiki">sage: L = [GF(p)['x','y'] for p in prime_range(5000)]
sage: C = CommutativeRings()
sage: %time [X in C for X in L]
CPU times: user 0.26 s, sys: 0.00 s, total: 0.26 s
Wall time: 0.27 s
</pre><pre class="wiki">sage: L = [GF(p)['x','y'] for p in prime_range(5000)]
sage: D = Modules(ZZ)
sage: %time [X in D for X in L]
CPU times: user 0.28 s, sys: 0.00 s, total: 0.28 s
Wall time: 0.28 s
</pre><p>
So, if base rings are involved then the test is much faster, and if no base rings are involved, the test is not much slower.
</p>
TicketSimonKingFri, 04 Nov 2011 18:14:30 GMT
https://trac.sagemath.org/ticket/11943#comment:23
https://trac.sagemath.org/ticket/11943#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:22" title="Comment 22">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I am afraid I can not show you the original example that made me suggest this bit of code.
</p>
</blockquote>
<p>
Now I remember the story.
</p>
<p>
By <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>, we have that the category of a polynomial ring is the join of a category of algebras with a base-free algebra, for example:
</p>
<pre class="wiki">sage: P.<x,y> = ZZ[]
sage: P.category()
Join of Category of unique factorization domains and Category of commutative algebras over Integer Ring
</pre><p>
Originally, that category has been computed via
</p>
<pre class="wiki">sage: Category.join([UniqueFactorizationDomains(), CommutativeAlgebras(ZZ)])
Join of Category of unique factorization domains and Category of commutative algebras over Integer Ring
</pre><p>
But that turned out to be a problem for elliptic curve computations:
</p>
<ul><li>In the benchmarks discussed on <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>, polynomial rings over many different finite fields are constructed.
</li><li>For each of them, <code>Category.join(...)</code> was called.
</li><li>Internally, <code>Category.join(...)</code> tests whether the categories to be joined are sub-categories of each other.
</li><li>Hence, for each prime p, one had to compute <code>CommutativeAlgebras(GF(p)).all_super_categories()</code>, in order to test whether it is a sub-category of <code>UniqueFactorizationDomains()</code>.
</li></ul><p>
In fact, that was the main reason for the speed regression from <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>.
</p>
<p>
For fixing it, I had (at least) the following two ideas:
</p>
<ol><li>Do not call <code>Category.join(...)</code>, but construct <code>JoinCategory(...)</code> directly. Advantage: <code>JoinCategory.__init__</code> does not test for sub-categories. So, no time is wasted.
</li><li>When testing <code>UniqueFactorizationDomains().is_subcategory(CommutativeAlgebras(F))</code>, one does not need to waste time by computing <code>CommutativeAlgebras(F).all_super_categories()</code>. The fact that <code>UniqueFactorizationDomains()</code> has no base ring suffices to recognise that it is not a sub-category.
</li></ol><p>
In <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>, I went for the first approach. Here, I'd like to also add the second approach. It is not needed for fixing an existing regression, but I still think it is a good idea.
</p>
<p>
Here is an example for what I have explained:
</p>
<p>
We start with a list of categories of algebras over different finite fields. The aim is to compute the join with the category of unique factorization domains.
</p>
<pre class="wiki">sage: L = [CommutativeAlgebras(GF(p)) for p in prime_range(5000)]
sage: C = UniqueFactorizationDomains()
</pre><p>
With sage-4.6.2 (as an old reference):
</p>
<pre class="wiki">sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.65 s, sys: 0.00 s, total: 0.65 s
Wall time: 0.65 s
</pre><p>
With sage-4.7.2.alpha3 (hence, with <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>, but without <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>):
</p>
<pre class="wiki">sage: L = [CommutativeAlgebras(GF(p)) for p in prime_range(5000)]
sage: C = UniqueFactorizationDomains()
sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.76 s, sys: 0.00 s, total: 0.77 s
Wall time: 0.77 s
</pre><p>
With unpatched sage-4.7.3.alpha1 (which contains <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>):
</p>
<pre class="wiki">sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.59 s, sys: 0.01 s, total: 0.60 s
Wall time: 0.61 s
</pre><p>
With sage-4.7.3.alpha1 plus the patch from here (thus, using base rings):
</p>
<pre class="wiki">sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.39 s, sys: 0.00 s, total: 0.39 s
Wall time: 0.39 s
</pre><p>
Believe it or not, but that kind of differences had a noticeable effect, as I found out while working on <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>.
</p>
<p>
<strong><span class="underline">Conclusion</span></strong>
</p>
<p>
I still believe that one should exploit the base of a category for short-cuts in subcategory tests.
</p>
TicketSimonKingFri, 04 Nov 2011 18:51:51 GMTstatus changed
https://trac.sagemath.org/ticket/11943#comment:24
https://trac.sagemath.org/ticket/11943#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
I have updated my patch. As I have announced, I add the possibility to define a join category with a base. It is used for polynomial rings, who clearly should belong to a category with a base, but also to a join category.
</p>
TicketmderickxFri, 04 Nov 2011 19:56:39 GMT
https://trac.sagemath.org/ticket/11943#comment:25
https://trac.sagemath.org/ticket/11943#comment:25
<p>
I think base has nothing to do with join logically so I think it is a bad idea to only add it to joins of categories for this shortcut purpose. Also I don't like your 'base' concept since it is just a speedup thing right now and doesn't relate to something wich has a real mathematical meaning.
The second thing is that I don't like the way how the code is organized right now in is_subclass. The reason for this is that this way of making shortcuts scales very bad and that other people thinking of other specific shortcuts to speed stuff up might make this a very cluttered method very soon. I'd say its cluttered already since this generic method already has special code for categories witch are a join of something and special code for the case that self and other have a base method. I think it is better to provide a truly generic implementation in combination with something like a <span class="underline">subclasshook</span> as python has for Abstract Base Classes <a class="ext-link" href="http://docs.python.org/library/abc.html#abc.ABCMeta.__subclasshook"><span class="icon"></span>http://docs.python.org/library/abc.html#abc.ABCMeta.__subclasshook</a><span class="underline"> . In this way you we can have the <a class="missing wiki">JoinCategory?</a> specific code where it belongs and you can have your "base" optimisation in the place where it belongs, and other people can add their own shortcuts as they please.
</span></p>
TicketmderickxFri, 04 Nov 2011 20:02:04 GMTstatus changed
https://trac.sagemath.org/ticket/11943#comment:26
https://trac.sagemath.org/ticket/11943#comment:26
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
something went wrong with the previous link cause of the wiki formatting it should be <a class="ext-link" href="http://docs.python.org/library/abc.html#abc.ABCMeta.__subclasshook__"><span class="icon"></span>this link</a>
</p>
TicketSimonKingFri, 04 Nov 2011 20:43:01 GMT
https://trac.sagemath.org/ticket/11943#comment:27
https://trac.sagemath.org/ticket/11943#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:25" title="Comment 25">mderickx</a>:
</p>
<blockquote class="citation">
<p>
I think base has nothing to do with join logically
</p>
</blockquote>
<p>
I think it does, to some extent. If C is a category with a base B, then all its objects are supposed to have this base B as well. If you form a join J of C with another category, then all objects of J are also objects of C and thus have the base B.
</p>
<p>
It only starts to lack logic if you join categories with distinct bases.
</p>
<p>
But if you join a list of categories such that at least one of them has base B and all other categories on the list either have no base at all or have the base B as well, then I think it is alright to say that the join has base B.
</p>
<blockquote class="citation">
<p>
The second thing is that I don't like the way how the code is organized right now in is_subclass. ... I think it is better to provide a truly generic implementation in combination with something like a <code>__subclasshook__</code>
</p>
</blockquote>
<p>
One could argue that <code>super_categories()</code> alreay plays the role of <code>__subclasshook__</code>: It determines how different categories are contained in one another, and is used in a generic method <code>Category.is_subcategory</code>.
</p>
<p>
But I agree that it is conceivable that <code>JoinCategory</code> or <code>Category_over_base</code> could benefit from using a specialised method for detecting subcategories.
</p>
TicketmderickxFri, 04 Nov 2011 21:03:11 GMT
https://trac.sagemath.org/ticket/11943#comment:28
https://trac.sagemath.org/ticket/11943#comment:28
<p>
No, super_categories() plays the exact opposite role of __subclashook__ . The subclass hook allows you to define what you consider as subclass of self and not what you consider a super class. What you claim is sort of saying that class inheritance plays the same role as <span class="underline">subclasshook</span>!
</p>
TicketmderickxFri, 04 Nov 2011 21:49:38 GMT
https://trac.sagemath.org/ticket/11943#comment:29
https://trac.sagemath.org/ticket/11943#comment:29
<p>
Maybe my real problem is with the way how you implement the base logic. I think that asuming that if two categories have a different base then they cannot be sub categories of each other is way to strict, this is not an interface wich I like to program to. And that by your current implementation you add way to much specific code to the general parts of the category framework that will not nicely generalize to more situations and don't fit nicely with the mathematical concept of base.
</p>
TicketSimonKingSat, 05 Nov 2011 08:45:00 GMT
https://trac.sagemath.org/ticket/11943#comment:30
https://trac.sagemath.org/ticket/11943#comment:30
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:28" title="Comment 28">mderickx</a>:
</p>
<blockquote class="citation">
<p>
No, super_categories() plays the exact opposite role of __subclashook__ . The subclass hook allows you to define what you consider as subclass of self and not what you consider a super class.
</p>
</blockquote>
<p>
Yes, you are right! Even though a while ago I did some experiments with the ABC module, I forgot that one is registering sub-classes, not super-classes. Sorry.
</p>
<p>
Let me see. When we do <code>A.is_subcategory(B)</code> then <em>with or without my patch</em> we make a special case when B is a join category. With my patch, we also make a special case when B has a base - and actually what we <em>really</em> want is a special case for <code>Category_over_base</code> (recall the original use case, where A is the category of unique factorization domains and B is a category of algebras).
</p>
<p>
So, it seems like a good idea that both <code>JoinCategory</code> and <code>Category_over_base</code> and perhaps also <code>TensorProductsCategory</code> get a method <code>subcategory_hook</code>, and that <code>Category.is_subcategory</code> then looks as follows:
</p>
<div class="wiki-code"><div class="code"><pre><span class="k">def</span> <span class="nf">is_subcategory</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> C<span class="p">):</span>
<span class="k">try</span><span class="p">:</span>
<span class="k">return</span> C<span class="o">.</span>subcategory_hook<span class="p">(</span><span class="bp">self</span><span class="p">)</span>
<span class="k">except</span> <span class="ne">AttributeError</span><span class="p">:</span>
<span class="k">return</span> C <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span>_set_of_super_categories
</pre></div></div><p>
Of course, one should add a comment about the new "magical" method into the docs.
</p>
<p>
Is that what you suggested?
</p>
TicketmderickxSat, 05 Nov 2011 09:47:47 GMT
https://trac.sagemath.org/ticket/11943#comment:31
https://trac.sagemath.org/ticket/11943#comment:31
<p>
That is indeed my suggestion. But my specific implementation would be:
</p>
<div class="wiki-code"><div class="code"><pre><span class="k">def</span> <span class="nf">is_subcategory</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> C<span class="p">):</span>
hook_result <span class="o">=</span> C<span class="o">.</span>subcategory_hook<span class="p">(</span><span class="bp">self</span><span class="p">)</span>
<span class="k">if</span> hook_result <span class="ow">is</span> <span class="ow">not</span> <span class="bp">NotImplemented</span><span class="p">:</span>
<span class="k">return</span> hook_result
<span class="k">return</span> C <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span>_set_of_super_categories
</pre></div></div><p>
So that it is more similar to the __subclasshook__ that python provides and your shortcut can just return <a class="missing wiki">NotImplemented?</a> to signify that the shortcut didn't work (just like you can do with the subclasshook). And make a default implementation in Category that just returns <a class="missing wiki">NotImplemented?</a>. The new magical method should indeed be documented.
</p>
TicketmderickxSat, 05 Nov 2011 09:49:28 GMT
https://trac.sagemath.org/ticket/11943#comment:32
https://trac.sagemath.org/ticket/11943#comment:32
<p>
and maybe it should be _subcategory_hook_ since I consider it more of a developer thing then an enduser.
</p>
TicketSimonKingSat, 05 Nov 2011 12:55:54 GMT
https://trac.sagemath.org/ticket/11943#comment:33
https://trac.sagemath.org/ticket/11943#comment:33
<p>
Now I wonder how we should proceed. Namely, I introduced the special case for categories with base not here, but in <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>.
</p>
<p>
I would argue as follows: <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a> is explicitly about speed. It provides speed. Hence, let it stay as it is.
</p>
<p>
The ticket here is more about structure. Hence, part of it should be to fix <em>here</em> my messy code from <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>.
</p>
TicketSimonKingSat, 05 Nov 2011 13:51:59 GMT
https://trac.sagemath.org/ticket/11943#comment:34
https://trac.sagemath.org/ticket/11943#comment:34
<p>
I am now rewriting it, and first tests seem to indicate that a cleaner implementation of is_subcategory is <em>faster</em> than the current mess. So, thank you for your suggestion, Maarten!
</p>
TicketmderickxSat, 05 Nov 2011 14:56:32 GMT
https://trac.sagemath.org/ticket/11943#comment:35
https://trac.sagemath.org/ticket/11943#comment:35
<p>
No problem :). I think you deserve way more credit, considering the huge amount of work you have done to make the category framework better lately.
</p>
TicketSimonKingSun, 06 Nov 2011 12:16:33 GMTwork_issues set
https://trac.sagemath.org/ticket/11943#comment:36
https://trac.sagemath.org/ticket/11943#comment:36
<ul>
<li><strong>work_issues</strong>
set to <em>use a "_subcategory_hook_" and document it</em>
</li>
</ul>
<p>
I will add documentation to <code>sage.categories.primer</code>. The section in the primer on "how to implement a new category" is rather short anyway. It even does not explain that one should provide a method <code>super_categories</code> (it only tells that the order of super-categories should follow certain rules), and it does not mention <code>ParentMethods</code> and <code>ElementMethods</code> at all. I'll add that, plus some words on the new <code>_subcategory_hook_</code>.
</p>
TicketSimonKingMon, 07 Nov 2011 09:09:33 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/11943#comment:37
https://trac.sagemath.org/ticket/11943#comment:37
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>use a "_subcategory_hook_" and document it</em> deleted
</li>
</ul>
<p>
I have added Maarten's idea of a _subcategory_hook_ and documented it. The subcategory hook is used for <code>Category_over_base</code> (hence, it is not needed to check for the existence of a base() attribute).
</p>
<p>
Moreover, in order to keep the generic implementation of <code>is_subcategory</code> clean, I provided <code>JoinCategory</code> with a specialised <code>is_subcategory</code>.
</p>
<p>
The documentation looks fine to me, and all tests pass. Needs review!
</p>
TicketSimonKingMon, 07 Nov 2011 09:10:58 GMTdescription changed
https://trac.sagemath.org/ticket/11943#comment:38
https://trac.sagemath.org/ticket/11943#comment:38
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11943?action=diff&version=38">diff</a>)
</li>
</ul>
<p>
I forgot to inform the patch bot:
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy_hook.patch
</p>
TicketSimonKingMon, 07 Nov 2011 13:33:55 GMT
https://trac.sagemath.org/ticket/11943#comment:39
https://trac.sagemath.org/ticket/11943#comment:39
<p>
I updated the patch. Only change: I added some doc tests that I had previously forgotten to include.
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy_hook.patch
</p>
TicketSimonKingMon, 07 Nov 2011 21:43:02 GMT
https://trac.sagemath.org/ticket/11943#comment:40
https://trac.sagemath.org/ticket/11943#comment:40
<p>
I updated the patch again. Reason: The previous one was relative to sage-4.7.3.alpha1, which includes <a class="closed ticket" href="https://trac.sagemath.org/ticket/11068" title="enhancement: Basic implementation of one- and twosided ideals of non-commutative ... (closed: fixed)">#11068</a>. But sage-4.8.alpha0 does not include <a class="closed ticket" href="https://trac.sagemath.org/ticket/11068" title="enhancement: Basic implementation of one- and twosided ideals of non-commutative ... (closed: fixed)">#11068</a>. I modified one hunk of the patch such that the order in which this patch and the patches from <a class="closed ticket" href="https://trac.sagemath.org/ticket/11068" title="enhancement: Basic implementation of one- and twosided ideals of non-commutative ... (closed: fixed)">#11068</a> are applied will hopefully not matter.
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy_hook.patch
</p>
TicketSimonKingTue, 08 Nov 2011 09:58:31 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/11943#comment:41
https://trac.sagemath.org/ticket/11943#comment:41
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>Remove dead code</em>
</li>
</ul>
<p>
I noticed that once again I was commenting out old code, rather than properly removing it. Sorry. I will remove the commented-out code from <code>is_subcategory</code> and update my patch soon.
</p>
TicketSimonKingTue, 08 Nov 2011 10:05:08 GMTstatus, description changed; work_issues deleted
https://trac.sagemath.org/ticket/11943#comment:42
https://trac.sagemath.org/ticket/11943#comment:42
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11943?action=diff&version=42">diff</a>)
</li>
<li><strong>work_issues</strong>
<em>Remove dead code</em> deleted
</li>
</ul>
<p>
Dead code is removed, ticket description updated.
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy_hook.patch
</p>
TicketSimonKingTue, 08 Nov 2011 14:59:58 GMT
https://trac.sagemath.org/ticket/11943#comment:43
https://trac.sagemath.org/ticket/11943#comment:43
<p>
I found that there is a trivial conflict with <a class="closed ticket" href="https://trac.sagemath.org/ticket/11068" title="enhancement: Basic implementation of one- and twosided ideals of non-commutative ... (closed: fixed)">#11068</a>. Therefore, I updated the patches from here and from there, so that it wouldn't matter in which order both tickets are merged.
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy_hook.patch
</p>
TicketnthieryWed, 16 Nov 2011 08:45:17 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/11943#comment:44
https://trac.sagemath.org/ticket/11943#comment:44
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>Remove the base method for cartesian_product (now unneeded) or reduce it to base_ring.</em>
</li>
</ul>
TicketSimonKingWed, 16 Nov 2011 12:40:41 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/11943#comment:45
https://trac.sagemath.org/ticket/11943#comment:45
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>Remove the base method for cartesian_product (now unneeded) or reduce it to base_ring.</em> deleted
</li>
</ul>
<p>
I have replaced the <code>base()</code> method of Cartesian products by a <code>base_ring()</code> method. I think it holds true that if some category has a base ring then all cartesian products of its objects have the same base ring. This may be not so sure when doing the same with a general bases.
</p>
<p>
I did not run full doctests yet, but the original example that made me introduce the <code>base()</code> method in <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a> is still working:
</p>
<pre class="wiki">sage: P.<x,y,z> = QQ[]
sage: P in Algebras(QQ)
True
sage: P.category()
Join of Category of unique factorization domains and Category of commutative algebras over Rational Field
</pre><p>
Benchmark, for avoiding to return to the old regression:
</p>
<pre class="wiki">sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.78 s, sys: 0.08 s, total: 3.86 s
Wall time: 4.10 s
</pre><p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/11935" title="enhancement: Make parent/element classes independent of base rings (closed: fixed)">#11935</a> will make this even faster.
</p>
TicketSimonKingWed, 16 Nov 2011 12:41:56 GMT
https://trac.sagemath.org/ticket/11943#comment:46
https://trac.sagemath.org/ticket/11943#comment:46
<p>
I forgot the patch bot:
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy_hook.patch
</p>
TicketSimonKingWed, 16 Nov 2011 14:14:21 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/11943#comment:47
https://trac.sagemath.org/ticket/11943#comment:47
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>R doctest</em>
</li>
</ul>
<p>
I find one very strange doctest error in sage/interfaces/r.py, and I have so far no clue what goes wrong.
</p>
TicketSimonKingWed, 16 Nov 2011 14:20:30 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/11943#comment:48
https://trac.sagemath.org/ticket/11943#comment:48
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>R doctest</em> deleted
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:47" title="Comment 47">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I find one very strange doctest error in sage/interfaces/r.py, and I have so far no clue what goes wrong.
</p>
</blockquote>
<p>
And now I cannot reproduce the error. So, even more mysterious. I put it back to "needs review", as repeting the failing test did not reproduce the error.
</p>
TicketSimonKingWed, 23 Nov 2011 10:23:48 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/11943#comment:49
https://trac.sagemath.org/ticket/11943#comment:49
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>Rebase wrt the new version of #11900; Use ideas from there to improve is_subcategory for Category_singleton</em>
</li>
</ul>
TicketSimonKingWed, 23 Nov 2011 10:40:40 GMT
https://trac.sagemath.org/ticket/11943#comment:50
https://trac.sagemath.org/ticket/11943#comment:50
<p>
For the record: With the current version of the patch, we have numerous mismatches, namely in
</p>
<pre class="wiki">sage/categories/bimodules.py
sage/categories/category.py
sage/categories/category_types.py
sage/categories/euclidean_domains.py
sage/categories/fields.py
sage/categories/homset.py
sage/categories/modules.py
sage/categories/ring_ideals.py
sage/categories/semirings.py
sage/categories/vector_spaces.py
</pre>
TicketSimonKingWed, 23 Nov 2011 11:00:42 GMTwork_issues changed
https://trac.sagemath.org/ticket/11943#comment:51
https://trac.sagemath.org/ticket/11943#comment:51
<ul>
<li><strong>work_issues</strong>
changed from <em>Rebase wrt the new version of #11900; Use ideas from there to improve is_subcategory for Category_singleton</em> to <em>Use ideas from #11900 to improve is_subcategory</em>
</li>
</ul>
<p>
I have updated the patch, so that (1) it applies, and (2) Sage starts. But I'd certainly like to improve the _subcategory_hook_ by using subclass check of parent classes. This would work generally, not only for Category_singleton. In <a class="closed ticket" href="https://trac.sagemath.org/ticket/11935" title="enhancement: Make parent/element classes independent of base rings (closed: fixed)">#11935</a>, it would then be needed to refine the _subcategory_hook_ for subclasses of <code>CategoryWithParameter</code>, because of sharing parent classes.
</p>
TicketSimonKingWed, 23 Nov 2011 12:35:27 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/11943#comment:52
https://trac.sagemath.org/ticket/11943#comment:52
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>Use ideas from #11900 to improve is_subcategory</em> deleted
</li>
</ul>
<p>
The patch is updated, and with it all tests should pass.
</p>
<p>
The patch uses the <code>_subcategory_hook_</code> mechanism, which will make it easier in <a class="closed ticket" href="https://trac.sagemath.org/ticket/11935" title="enhancement: Make parent/element classes independent of base rings (closed: fixed)">#11935</a> to cope with the case of shared parent classes. However, for now, the default <code>_subcategory_hook_</code>, which tests whether one parent class is subclass of the other, is actually sufficient to determine subcategories, with the only exception of join categories.
</p>
<p>
Needs review, I'd say!
</p>
TicketSimonKingWed, 23 Nov 2011 15:06:40 GMT
https://trac.sagemath.org/ticket/11943#comment:53
https://trac.sagemath.org/ticket/11943#comment:53
<p>
The patchbot got it wrong:
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy_hook.patch
</p>
TicketSimonKingMon, 05 Dec 2011 17:45:29 GMTwork_issues set
https://trac.sagemath.org/ticket/11943#comment:54
https://trac.sagemath.org/ticket/11943#comment:54
<ul>
<li><strong>work_issues</strong>
set to <em>Is the base() method removed?</em>
</li>
</ul>
<p>
Mental note: The <code>base()</code> method for <code>CartesianProductCategory</code> that has been introduced in <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a> should be removed here, if possible. Could be that it is already done in the patch (no time to check it now, though).
</p>
TicketjdemeyerFri, 09 Dec 2011 14:55:20 GMT
https://trac.sagemath.org/ticket/11943#comment:55
https://trac.sagemath.org/ticket/11943#comment:55
<p>
How close is this ticket to being finished? Since <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/11943" title="enhancement: The category graph should comply with Python's method resolution order (closed: fixed)">#11943</a> are related, I am thinking about merging them all together. Do you think this is a good idea?
</p>
TicketSimonKingFri, 09 Dec 2011 15:33:49 GMTstatus, work_issues changed
https://trac.sagemath.org/ticket/11943#comment:56
https://trac.sagemath.org/ticket/11943#comment:56
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
changed from <em>Is the base() method removed?</em> to <em>Rebase. Is the base() method removed?</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:55" title="Comment 55">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
How close is this ticket to being finished? Since <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/11943" title="enhancement: The category graph should comply with Python's method resolution order (closed: fixed)">#11943</a> are related, I am thinking about merging them all together. Do you think this is a good idea?
</p>
</blockquote>
<p>
<em>If</em> this ticket is close to being finished, then merging the three together would be a good idea. I am not sure how much work needs to be done, in particular since Nicolas seems to have problems building sage-4.8.alpha3.
</p>
<p>
Anyway, it does need work since a couple of hunks do not apply when starting with sage-4.8.alpha3 and applying the latest patch version from <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a> (namely the one that does not use Category_singleton for Finite*, which Nicolas seems to prefer).
</p>
TicketSimonKingFri, 09 Dec 2011 15:43:54 GMT
https://trac.sagemath.org/ticket/11943#comment:57
https://trac.sagemath.org/ticket/11943#comment:57
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:55" title="Comment 55">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
How close is this ticket to being finished? Since <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/11943" title="enhancement: The category graph should comply with Python's method resolution order (closed: fixed)">#11943</a> are related, I am thinking about merging them all together. Do you think this is a good idea?
</p>
</blockquote>
<p>
Yes, I think it is a good idea. But perhaps one should also ask the opposite: Do you think it is a good idea to <em>not</em> merge <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>, if <a class="closed ticket" href="https://trac.sagemath.org/ticket/11943" title="enhancement: The category graph should comply with Python's method resolution order (closed: fixed)">#11943</a> is not ready? Here, my answer would be "no".
</p>
<p>
Personally, I want to have <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a> and thus <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>. I could live without <a class="closed ticket" href="https://trac.sagemath.org/ticket/11943" title="enhancement: The category graph should comply with Python's method resolution order (closed: fixed)">#11943</a>, even though it cleans up some stuff.
</p>
TicketSimonKingFri, 09 Dec 2011 16:32:08 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/11943#comment:58
https://trac.sagemath.org/ticket/11943#comment:58
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>Rebase. Is the base() method removed?</em> deleted
</li>
</ul>
<p>
I have updated the patch.
</p>
<p>
Concerning the <code>base()</code> method for Cartesian products: If I remember correctly, Nicolas and I agreed that it is ok to have a <code>base_ring()</code> method for Cartesian products (meaning: If a category is defined over a base ring then the category of Cartesian products of objects in that category is defined over the same base ring). Thus, the patch renames the method.
</p>
<p>
The patch should work on top of the positively reviewed patch from <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>.
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy_hook.patch
</p>
TicketSimonKingFri, 09 Dec 2011 16:33:50 GMT
https://trac.sagemath.org/ticket/11943#comment:59
https://trac.sagemath.org/ticket/11943#comment:59
<p>
PS: <code>./sage -tp 5 devel/sage/sage</code> and <code>./sage -tp 5 devel/sage/doc</code> pass for me.
</p>
TicketSimonKingTue, 13 Dec 2011 09:17:45 GMT
https://trac.sagemath.org/ticket/11943#comment:60
https://trac.sagemath.org/ticket/11943#comment:60
<p>
I'm awfully sorry: I just noticed that I forgot to include the name change "<code>base() -> base_ring()</code> in my patch. It has now been updated.
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy_hook.patch
</p>
TicketmderickxSat, 17 Dec 2011 15:25:30 GMT
https://trac.sagemath.org/ticket/11943#comment:61
https://trac.sagemath.org/ticket/11943#comment:61
<p>
I'm now starting to review it. At least it passes al tests when applied to sage 4.8.alpha4 + dependencies. I'm reading through your code now.
</p>
TicketnthieryFri, 09 Mar 2012 15:23:52 GMT
https://trac.sagemath.org/ticket/11943#comment:62
https://trac.sagemath.org/ticket/11943#comment:62
<p>
Hi Simon,
</p>
<p>
I am including your patch in the queue to handle conflicts with various other patches in finalization (and reviewing it by the way). The systematic removal of
</p>
<p>
Do you insist on systematically removing "cached_method" to all super_categories methods? I am not so sure about it. And practically speaking it does create quite a few conflicts; I am fine resolving them, but only if it's for the good cause. What do you think?
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketSimonKingFri, 09 Mar 2012 16:00:25 GMT
https://trac.sagemath.org/ticket/11943#comment:63
https://trac.sagemath.org/ticket/11943#comment:63
<blockquote class="citation">
<p>
Do you insist on systematically removing "cached_method" to all super_categories methods?
</p>
</blockquote>
<p>
Not necessarily.
</p>
<p>
The main reason for having super_categories cached was speed: One wouldn't like to create the list of super categories repeatedly. However, with my patch, it is cached in a different way, namely as an attribute, and that's even faster than a cached method.
</p>
<p>
In fact, i is kind of courtesy: Before, if the user forgot to use @cached_method then it became slower. Now, it doesn't matter whether or not the user knows of @cached_method.
</p>
<p>
From that point of view, it doesn't matter whether the cached_method decorator is systematically removed or not. With perhaps one exception: Calling a cached method hundred times takes shorter than calling a non-cached method hundred times. But calling the cached method just once takes longer than calling a non-cached method just once.
</p>
<p>
Hence, I could imagine that in the following setting, using my patch without cached_method would be noticeable faster than using my patch with cached_method (but I hope that using cached_method with my patch will still be slower than using cached_method without my patch...):
</p>
<ul><li>Create many different categories
</li><li>For each pair C1,C2, determine whether one is subcategory of the other
</li></ul><p>
I intend to try and provide an example. But I am having trouble with my mercurial queue.
</p>
TicketSimonKingFri, 09 Mar 2012 16:17:14 GMT
https://trac.sagemath.org/ticket/11943#comment:64
https://trac.sagemath.org/ticket/11943#comment:64
<p>
To my great surprise, using cached method seems to be <em>faster</em>, even with my patch:
</p>
<pre class="wiki">sage: class MyCat1(Category):
....: def __init__(self, R):
....: self.R = R
....: Category.__init__(self)
....: def super_categories(self):
....: return [Algebras(self.R)]
....:
sage: class MyCat2(Category):
....: def __init__(self, R):
....: self.R = R
....: @cached_method
....: def super_categories(self):
....: return [Algebras(self.R)]
....:
sage: L1 = [MyCat1(GF(p)) for p in prime_range(10000)]
sage: L2 = [MyCat2(GF(p)) for p in prime_range(10000)]
sage: def test_cats(L):
....: for A in L:
....: for B in L:
....: A.is_subcategory(B)
....:
sage: %time test_cats(L1)
CPU times: user 3.53 s, sys: 0.04 s, total: 3.56 s
Wall time: 3.58 s
sage: %time test_cats(L2)
CPU times: user 2.35 s, sys: 0.01 s, total: 2.36 s
Wall time: 2.36 s
</pre><p>
Of course, as soon as the super categories are obtained and put in the cache, there is no difference anymore:
</p>
<pre class="wiki">sage: %time test_cats(L1)
CPU times: user 2.17 s, sys: 0.00 s, total: 2.17 s
Wall time: 2.18 s
sage: %time test_cats(L2)
CPU times: user 2.15 s, sys: 0.01 s, total: 2.16 s
Wall time: 2.16 s
</pre><p>
So, after all: Yes, I do not insist on removing all cached_method decorators on the super_categories methods, but I still think removing them would be better aesthetically.
</p>
TicketSimonKingFri, 09 Mar 2012 16:23:50 GMTstatus, dependencies changed; work_issues set
https://trac.sagemath.org/ticket/11943#comment:65
https://trac.sagemath.org/ticket/11943#comment:65
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>dependencies</strong>
changed from <em>#11900</em> to <em>#11900, #12357</em>
</li>
<li><strong>work_issues</strong>
set to <em>Rebase rel #12357</em>
</li>
</ul>
<p>
But there is something else: <a class="closed ticket" href="https://trac.sagemath.org/ticket/12357" title="defect: Make groupoids garbage collectable (closed: duplicate)">#12357</a> has a positive review, but it brings a conflict. So, I need to rebase my patch.
</p>
TicketSimonKingFri, 09 Mar 2012 16:24:44 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/11943#comment:66
https://trac.sagemath.org/ticket/11943#comment:66
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>Rebase rel #12357</em> deleted
</li>
</ul>
<p>
Or perhaps better I shouldn't: <a class="closed ticket" href="https://trac.sagemath.org/ticket/12357" title="defect: Make groupoids garbage collectable (closed: duplicate)">#12357</a> is pending. So, let's do it the other way around...
</p>
TicketSimonKingFri, 09 Mar 2012 16:25:27 GMTdependencies changed
https://trac.sagemath.org/ticket/11943#comment:67
https://trac.sagemath.org/ticket/11943#comment:67
<ul>
<li><strong>dependencies</strong>
changed from <em>#11900, #12357</em> to <em>#11900</em>
</li>
</ul>
<p>
Oops, the "dependencies" field should only contain <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>...
</p>
TicketnthieryFri, 09 Mar 2012 16:43:59 GMTdependencies changed
https://trac.sagemath.org/ticket/11943#comment:68
https://trac.sagemath.org/ticket/11943#comment:68
<ul>
<li><strong>dependencies</strong>
changed from <em>#11900</em> to <em>#11900, #7980</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:67" title="Comment 67">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Oops, the "dependencies" field should only contain <a class="closed ticket" href="https://trac.sagemath.org/ticket/11900" title="defect: Serious regression caused by #9138 (closed: fixed)">#11900</a>...
</p>
</blockquote>
<p>
For the record: I have already slightly rebased your patch on top of <a class="closed ticket" href="https://trac.sagemath.org/ticket/7980" title="enhancement: Implement generic support for parents with (multiple) realizations (closed: fixed)">#7980</a> (multiple realizations) which conflicted and is almost positive review.
</p>
<p>
Thanks for your comments. I'll see if I keep the cached_methods in there or not depending on how the conflict resolution goes.
</p>
<p>
Ah one thing: for all the attributes like _all_super_categories, shouldn't we use tuples rather than lists for safety?
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketSimonKingFri, 09 Mar 2012 17:08:31 GMT
https://trac.sagemath.org/ticket/11943#comment:69
https://trac.sagemath.org/ticket/11943#comment:69
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:68" title="Comment 68">nthiery</a>:
</p>
<blockquote class="citation">
<p>
Ah one thing: for all the attributes like _all_super_categories, shouldn't we use tuples rather than lists for safety?
</p>
</blockquote>
<p>
Well, they used to be lists (and were cached).
</p>
<p>
If I remember correctly, I tried at some point whether a tuple would be better, but it was too slow. I think the reason was that during the creation of the list of all super categories, one would naturally operate with lists, and the transformation of the final list into a tuple was too time consuming in some elliptic curve computations.
</p>
<p>
If you like, I could try again, but probably only in a couple of days.
</p>
TicketnthieryFri, 09 Mar 2012 17:58:30 GMT
https://trac.sagemath.org/ticket/11943#comment:70
https://trac.sagemath.org/ticket/11943#comment:70
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:69" title="Comment 69">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
If I remember correctly, I tried at some point whether a tuple would be better, but it was too slow. I think the reason was that during the creation of the list of all super categories, one would naturally operate with lists, and the transformation of the final list into a tuple was too time consuming in some elliptic curve computations.
</p>
<p>
If you like, I could try again, but probably only in a couple of days.
</p>
</blockquote>
<p>
Ok; let's postpone this to a later patch. I'll just mention that the
lazy attributes will probably become tuples at some point.
</p>
<p>
On another note: why not systematically build _set_of_super_categories
as frozenset(_all_super_categories_proper) and
_all_super_categories_proper as _all_super_categories[1:]? Otherwise
it seems likely that C3 could often be called three times for a single
given category.
</p>
<p>
Besides C3_algorithm_set and the proper option would not be needed in
that case, and the overall logic be simplified a bit.
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketSimonKingSat, 10 Mar 2012 06:26:22 GMT
https://trac.sagemath.org/ticket/11943#comment:71
https://trac.sagemath.org/ticket/11943#comment:71
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:68" title="Comment 68">nthiery</a>:
</p>
<blockquote class="citation">
<p>
For the record: I have already slightly rebased your patch on top of <a class="closed ticket" href="https://trac.sagemath.org/ticket/7980" title="enhancement: Implement generic support for parents with (multiple) realizations (closed: fixed)">#7980</a>
</p>
</blockquote>
<p>
Where are the patches from <a class="closed ticket" href="https://trac.sagemath.org/ticket/7980" title="enhancement: Implement generic support for parents with (multiple) realizations (closed: fixed)">#7980</a>? Where is my rebased patch from here?
</p>
TicketSimonKingSat, 10 Mar 2012 06:38:01 GMT
https://trac.sagemath.org/ticket/11943#comment:72
https://trac.sagemath.org/ticket/11943#comment:72
<p>
O dear. Last night, I installed sage-5.0.beta7. The patch from here won't apply anymore, because the file age/categories/partially_ordered_sets.py has not been found.
</p>
<p>
Can you tell me the ticket which has removed that file?
</p>
TicketSimonKingSat, 10 Mar 2012 06:47:15 GMTstatus, dependencies changed; work_issues set
https://trac.sagemath.org/ticket/11943#comment:73
https://trac.sagemath.org/ticket/11943#comment:73
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>dependencies</strong>
changed from <em>#11900, #7980</em> to <em>#11900, #7980, #10998</em>
</li>
<li><strong>work_issues</strong>
set to <em>rebase</em>
</li>
</ul>
<p>
Apparently it is <a class="closed ticket" href="https://trac.sagemath.org/ticket/10998" title="enhancement: Categories for posets (closed: fixed)">#10998</a>. Needs to be rebased, then.
</p>
<p>
Nicolas, you said that you have rebased my patch. Is it relative to <a class="closed ticket" href="https://trac.sagemath.org/ticket/10998" title="enhancement: Categories for posets (closed: fixed)">#10998</a>? Can you post it here? And please, do post <a class="closed ticket" href="https://trac.sagemath.org/ticket/7980" title="enhancement: Implement generic support for parents with (multiple) realizations (closed: fixed)">#7980</a> as well.
</p>
TicketSimonKingSat, 10 Mar 2012 06:56:07 GMTstatus, dependencies changed
https://trac.sagemath.org/ticket/11943#comment:74
https://trac.sagemath.org/ticket/11943#comment:74
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>dependencies</strong>
changed from <em>#11900, #7980, #10998</em> to <em>#11900, #7980</em>
</li>
</ul>
<p>
OK, I have updated my patch, simply by removing one of the hooks that removes a cached method.
</p>
<p>
My patch should now apply, regardless whether <a class="closed ticket" href="https://trac.sagemath.org/ticket/10998" title="enhancement: Categories for posets (closed: fixed)">#10998</a> is applied or not. So, needs review again.
</p>
<p>
But please, do post the stuff from <a class="closed ticket" href="https://trac.sagemath.org/ticket/7980" title="enhancement: Implement generic support for parents with (multiple) realizations (closed: fixed)">#7980</a>, so that I can rebase my patch relative to it.
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy_hook.patch
</p>
TicketnthierySat, 10 Mar 2012 08:15:11 GMT
https://trac.sagemath.org/ticket/11943#comment:75
https://trac.sagemath.org/ticket/11943#comment:75
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:74" title="Comment 74">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
OK, I have updated my patch, simply by removing one of the hooks that removes a cached method.
</p>
<p>
My patch should now apply, regardless whether <a class="closed ticket" href="https://trac.sagemath.org/ticket/10998" title="enhancement: Categories for posets (closed: fixed)">#10998</a> is applied or not. So, needs review again.
</p>
<p>
But please, do post the stuff from <a class="closed ticket" href="https://trac.sagemath.org/ticket/7980" title="enhancement: Implement generic support for parents with (multiple) realizations (closed: fixed)">#7980</a>, so that I can rebase my patch relative to it.
</p>
<p>
Apply trac11943_mro_for_all_super_categories_lazy_hook.patch
</p>
</blockquote>
<p>
Don't waste your time: I told you I am handling it (on the Sage-Combinat queue), as well as <a class="closed ticket" href="https://trac.sagemath.org/ticket/11935" title="enhancement: Make parent/element classes independent of base rings (closed: fixed)">#11935</a>. I haven't pushed yet, because there are quite a few conflicts to resolve with the other category patches there. I'll post it here when I am done (probably monday).
</p>
TicketnthierySat, 10 Mar 2012 08:45:55 GMTstatus changed
https://trac.sagemath.org/ticket/11943#comment:76
https://trac.sagemath.org/ticket/11943#comment:76
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Ok, I pushed on the Sage-Combinat queue; I haven't finished the merging so the patches are still disabled; I still need to decide on keeping or not a couple cashed methods to best resolve the conflicts.
</p>
<p>
Please let me know about my question above about building _set_of_super_categories.
</p>
TicketSimonKingSat, 10 Mar 2012 08:52:51 GMT
https://trac.sagemath.org/ticket/11943#comment:77
https://trac.sagemath.org/ticket/11943#comment:77
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:76" title="Comment 76">nthiery</a>:
</p>
<blockquote class="citation">
<p>
Please let me know about my question above about building _set_of_super_categories.
</p>
</blockquote>
<p>
That will probably take a while. I am still in the process of getting sage-5.0.beta7 to work with all my patches applied (so that I can work on my ext algebra project), have to finish writing some paper, and have some other urgent things to do, that will essentially occupy this weekend.
</p>
TicketnthierySat, 10 Mar 2012 09:55:40 GMT
https://trac.sagemath.org/ticket/11943#comment:78
https://trac.sagemath.org/ticket/11943#comment:78
<blockquote class="citation">
<p>
That will probably take a while. I am still in the process of getting sage-5.0.beta7 to work with all my patches applied (so that I can work on my ext algebra project), have to finish writing some paper, and have some other urgent things to do, that will essentially occupy this weekend.
</p>
</blockquote>
<p>
I just meant: do you agree if I do this change in my reviewer patch?
</p>
TicketnthieryMon, 02 Apr 2012 20:05:52 GMT
https://trac.sagemath.org/ticket/11943#comment:79
https://trac.sagemath.org/ticket/11943#comment:79
<p>
For the record: the Sage-Combinat queue has been rebased on top of this patch. To this end,
I stripped away from this patch the "cached_method" changes concerning categories that won't have a super_categories method after <a class="closed ticket" href="https://trac.sagemath.org/ticket/10963" title="enhancement: Axioms and more functorial constructions (closed: fixed)">#10963</a> anyway. I am writing a small review patch with some improvements (including the "_set_of_super_categories" thingie discussed above). At this point, all tests pass on 5.0.beta10.
</p>
<p>
I hope to finish the review shortly.
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketnthieryFri, 06 Apr 2012 16:06:49 GMT
https://trac.sagemath.org/ticket/11943#comment:80
https://trac.sagemath.org/ticket/11943#comment:80
<p>
Hi Simon,
</p>
<p>
I have finished my review. I'll push shortly my reviewer's patch on the Sage-Combinat queue
</p>
<p>
<a class="ext-link" href="http://combinat.sagemath.org/patches/file/tip/trac11943_mro_for_all_super_categories_lazy_hook-review-nt.patch"><span class="icon"></span>http://combinat.sagemath.org/patches/file/tip/trac11943_mro_for_all_super_categories_lazy_hook-review-nt.patch</a>
</p>
<p>
Overall, I am happy with it, and it's almost good to go if you are happy with my changes. Thanks for your hard work!
</p>
<p>
Just two little details:
</p>
<ul><li>in covariant_functorial_construction.py, the method is_subcategory is not documented, and I am not sure why it is required. Please remove, or add documentation and tests with a comment on the rationale for this method
</li></ul><ul><li>in the C3 algorithm: Cython knows that <code></code>tails<code></code> is a list, so one would assume that tails[i] is optimized. Is it really faster to use PyList_GET_ITEM(tails,i) rather than just tails[i]? Otherwise, please use the later which is more readable. Same thing for the other PyList_*.
</li></ul><p>
Once those are done, and it is confirmed that all tests pass (I am running them), you can set a positive review on my behalf (I'll be away for the week-end).
</p>
<p>
Happy easter!
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketnthieryFri, 06 Apr 2012 16:09:13 GMT
https://trac.sagemath.org/ticket/11943#comment:81
https://trac.sagemath.org/ticket/11943#comment:81
<p>
Hold on a minute; I need to rebase a bit of stuff before pushing, and before that pickup the girls at school ...
</p>
TicketnthieryFri, 06 Apr 2012 16:54:33 GMT
https://trac.sagemath.org/ticket/11943#comment:82
https://trac.sagemath.org/ticket/11943#comment:82
<p>
Pushed. I am running the tests now. Note: I also had to make some modifications to the original patch; so please start from <a class="ext-link" href="http://combinat.sagemath.org/patches/file/tip/trac11943_mro_for_all_super_categories_lazy_hook.patch"><span class="icon"></span>http://combinat.sagemath.org/patches/file/tip/trac11943_mro_for_all_super_categories_lazy_hook.patch</a>.
</p>
<p>
As far as I remember, all I did to this patch was, as discussed, to remove the hunks that were removing "cached_method"'s on those super_categories methods that are going to disapear with <a class="closed ticket" href="https://trac.sagemath.org/ticket/10963" title="enhancement: Axioms and more functorial constructions (closed: fixed)">#10963</a> anyway. That to make the rebase of <a class="closed ticket" href="https://trac.sagemath.org/ticket/10963" title="enhancement: Axioms and more functorial constructions (closed: fixed)">#10963</a> easier.
</p>
<p>
I'll upload both patches here once the tests are positive.
</p>
TicketnthieryFri, 06 Apr 2012 17:10:39 GMTattachment set
https://trac.sagemath.org/ticket/11943
https://trac.sagemath.org/ticket/11943
<ul>
<li><strong>attachment</strong>
set to <em>trac11943_mro_for_all_super_categories_lazy_hook.patch</em>
</li>
</ul>
<p>
Order the super categories of a category according to Python's mro. Internally replace (all_)super_categories by lazy attributes, to prevent a regression. Use _subcategory_hook_
</p>
TicketnthieryFri, 06 Apr 2012 17:12:57 GMTstatus, description changed; work_issues deleted
https://trac.sagemath.org/ticket/11943#comment:83
https://trac.sagemath.org/ticket/11943#comment:83
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11943?action=diff&version=83">diff</a>)
</li>
<li><strong>work_issues</strong>
<em>rebase</em> deleted
</li>
</ul>
TicketnthieryFri, 06 Apr 2012 17:13:52 GMT
https://trac.sagemath.org/ticket/11943#comment:84
https://trac.sagemath.org/ticket/11943#comment:84
<p>
All tests pass; latest versions of the patches uploaded. Please fold the two patches once you have reviewed my changes.
</p>
TicketSimonKingMon, 09 Apr 2012 23:34:52 GMT
https://trac.sagemath.org/ticket/11943#comment:85
https://trac.sagemath.org/ticket/11943#comment:85
<p>
Sorry, I can not do (reviewing or other) work, being in the middle of holidays. I'll return next week.
</p>
TicketnthieryTue, 10 Apr 2012 08:51:20 GMT
https://trac.sagemath.org/ticket/11943#comment:86
https://trac.sagemath.org/ticket/11943#comment:86
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:85" title="Comment 85">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Sorry, I can not do (reviewing or other) work, being in the middle of holidays. I'll return next week.
</p>
</blockquote>
<p>
Sure: enjoy your vacations!
</p>
<p>
Just in case: are you ok with, e.g., Florent finishing the review, or do you prefer double checking things yourself? (just to give a chance to the patch to go into 5.0).
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketnthieryTue, 10 Apr 2012 10:08:05 GMT
https://trac.sagemath.org/ticket/11943#comment:87
https://trac.sagemath.org/ticket/11943#comment:87
<p>
On 5.0.beta13, I was getting a random doctest failure due to the order
of the classes changing in Python's error message about MRO's:
</p>
<pre class="wiki">File "/home/nthiery/sage-5.0.beta13/devel/sage-combinat/sage/misc/c3.pyx", line 81:
sage: F.parent_class
Expected:
Traceback (most recent call last):
...
TypeError: Cannot create a consistent method resolution
order (MRO) for bases X.parent_class, Y.parent_class
Got:
Traceback (most recent call last):
... File "/home/nthiery/sage-5.0.beta13/local/bin/ncadoctest.py", line 1231, in run_one_test
TypeError: Cannot create a consistent method resolution
order (MRO) for bases Y.parent_class, X.parent_class
</pre><p>
The updated patch uses "..." instead of X and Y.
</p>
TicketSimonKingTue, 10 Apr 2012 17:19:31 GMT
https://trac.sagemath.org/ticket/11943#comment:88
https://trac.sagemath.org/ticket/11943#comment:88
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:86" title="Comment 86">nthiery</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:85" title="Comment 85">SimonKing</a>:
Sure: enjoy your vacations!
</p>
</blockquote>
<p>
Thank you! By the way, it is in France.
</p>
<blockquote class="citation">
<p>
Just in case: are you ok with, e.g., Florent finishing the review
</p>
</blockquote>
<p>
Of course! Just go ahead.
</p>
TicketSimonKingSat, 14 Apr 2012 19:30:09 GMT
https://trac.sagemath.org/ticket/11943#comment:89
https://trac.sagemath.org/ticket/11943#comment:89
<p>
The reviewer patch mostly looks fine to me (running tests now). But I think one should use the occasion and apply the trac directive in the Sphynx markup. Hence,
</p>
<pre class="wiki">... in :trac:`11943`
</pre><p>
rather than
</p>
<pre class="wiki">... in trac ticket #11943
</pre><p>
When I wrote the original patch, I have not been aware of the directive.
</p>
TicketnthieryMon, 16 Apr 2012 14:16:09 GMT
https://trac.sagemath.org/ticket/11943#comment:90
https://trac.sagemath.org/ticket/11943#comment:90
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:89" title="Comment 89">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
The reviewer patch mostly looks fine to me (running tests now). But I think one should use the occasion and apply the trac directive in the Sphynx markup. Hence,
</p>
<pre class="wiki">... in :trac:`11943`
</pre><p>
rather than
</p>
<pre class="wiki">... in trac ticket #11943
</pre><p>
When I wrote the original patch, I have not been aware of the directive.
</p>
</blockquote>
<p>
Perfect; I was about to upload an updated patch doing just that after a suggestion by Florent on Friday :-) Give me two minutes.
</p>
TicketnthieryMon, 16 Apr 2012 14:17:17 GMTattachment set
https://trac.sagemath.org/ticket/11943
https://trac.sagemath.org/ticket/11943
<ul>
<li><strong>attachment</strong>
set to <em>trac11943_mro_for_all_super_categories_lazy_hook-review-nt.patch</em>
</li>
</ul>
TicketnthieryMon, 16 Apr 2012 14:21:04 GMT
https://trac.sagemath.org/ticket/11943#comment:91
https://trac.sagemath.org/ticket/11943#comment:91
<p>
There it is. Here is the diff between the two patches (oops, sorry, I did the diff the wrong way):
</p>
<pre class="wiki"> diff --git a/sage/categories/algebras.py b/sage/categories/algebras.py
--- a/sage/categories/algebras.py
@@ -155,7 +155,7 @@
+ All the super categories of this category, including this category.
- TEST::
-+ Since :trac:`11943`, the order of super categories is
++ Since trac ticket #11943, the order of super categories is
+ determined by Python's method resolution order C3 algorithm.
- sage: Rngs()._all_super_categories_raw()
@@ -193,7 +193,7 @@
+ r"""
+ All the proper super categories of this category.
+
-+ Since :trac:`11943`, the order of super categories is
++ Since trac ticket #11943, the order of super categories is
+ determined by Python's method resolution order C3 algorithm.
+
+ .. seealso:: :meth:`all_super_categories`
@@ -266,7 +266,7 @@
+ - ``proper`` -- a boolean (default: ``False``); whether to exclude this category.
- FIXME:
-+ Since :trac:`11943`, the order of super categories is
++ Since trac ticket #11943, the order of super categories is
+ determined by Python's method resolution order C3 algorithm.
- - make sure that this is compatible with the python algorithm
@@ -422,7 +422,7 @@
- By trac ticket #11943, the list of categories returned by :meth:`all_super_categories`
- is supposed to correspond to the method resolution order of the parent or element
- classes. This method verifies it.
-+ By :trac:`11943`, the list of categories returned by
++ By trac ticket #11943, the list of categories returned by
+ :meth:`all_super_categories` is supposed to match with the
+ method resolution order of the parent and element
+ classes. This method checks this.
</pre><p>
If you are happy with the changes, please fold the two patches, and double check the patch header.
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketSimonKingMon, 16 Apr 2012 14:27:09 GMTattachment set
https://trac.sagemath.org/ticket/11943
https://trac.sagemath.org/ticket/11943
<ul>
<li><strong>attachment</strong>
set to <em>trac11943_mro_for_all_super_categories_combined.patch</em>
</li>
</ul>
<p>
Replaces the two other patches: Order the super categories of a category according to Python's mro. Internally replace (all_)super_categories by lazy attributes, to prevent a regression. Use _subcategory_hook_
</p>
TicketSimonKingMon, 16 Apr 2012 14:28:59 GMTdescription changed
https://trac.sagemath.org/ticket/11943#comment:92
https://trac.sagemath.org/ticket/11943#comment:92
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11943?action=diff&version=92">diff</a>)
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11943#comment:91" title="Comment 91">nthiery</a>:
</p>
<blockquote class="citation">
<p>
If you are happy with the changes, please fold the two patches, and double check the patch header.
</p>
</blockquote>
<p>
Done! I am happy with your reviewer patch (which is folded into the combined patch), and if you think it is appropriate, please give it a positive review.
</p>
<p>
Apply trac11943_mro_for_all_super_categories_combined.patch
</p>
TicketnthieryMon, 16 Apr 2012 17:29:38 GMTstatus changed
https://trac.sagemath.org/ticket/11943#comment:93
https://trac.sagemath.org/ticket/11943#comment:93
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketjdemeyerThu, 19 Apr 2012 09:46:23 GMTmilestone changed
https://trac.sagemath.org/ticket/11943#comment:94
https://trac.sagemath.org/ticket/11943#comment:94
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.0</em> to <em>sage-5.1</em>
</li>
</ul>
TicketjdemeyerMon, 30 Apr 2012 08:30:32 GMTreviewer set
https://trac.sagemath.org/ticket/11943#comment:95
https://trac.sagemath.org/ticket/11943#comment:95
<ul>
<li><strong>reviewer</strong>
set to <em>Nicolas M. Thiéry</em>
</li>
</ul>
TicketjdemeyerSun, 06 May 2012 12:15:10 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/11943#comment:96
https://trac.sagemath.org/ticket/11943#comment:96
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.1.beta0</em>
</li>
</ul>
Ticket