#11943: The category graph should comply with Python's method resolution order
---------------------------+------------------------------------------------
Reporter: SimonKing | Owner: nthiery
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.8
Component: categories | Keywords: category graph, method resolution
order
Work_issues: | Upstream: N/A
Reviewer: | Author: Simon King
Merged: | Dependencies: #11900
---------------------------+------------------------------------------------
Changes (by SimonKing):
* status: needs_work => needs_review
Comment:
Dear Nicolas,
Replying to [comment:18 nthiery]:
> 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.
But I think, in this particular case, nothing nasty can happen.
Ultimately, it is tested whether the argument c belongs to the list of all
super categories of `self`. Hence, unexpected things can only happen if c
is not a category but is equal to a category, or if
`self.super_categories()` contains something that is not a category.
> > So, my next patch version will remove these lines, provided that doc
tests pass.
>
> I don't remember anymore why I did a special case for join categories,
> so +1.
I have just attached a new version of my patch. I used several techniques
to speed up `is_subcategory`.
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.
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.
By consequence, I needed to introduce a `base()` method for various
settings. For example, tensor products preserve the base. And for join
categories, I argue: If `C = JoinCategory((C1,C2,...))` then `C.base()`
should be the first answer that one obtains by walking through the list
`C1.base(), C2.base(),...`.
I think this makes sense in the intended application: By #9138, 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).
The code of is_subcategory is now (with some comments added):
{{{
#!python
# No cached method, currently
def is_subcategory(self, c):
if c is self: # short path for a common case
return True
if isinstance(c, JoinCategory):
return all(self.is_subcategory(x) for x in
c._super_categories)
try:
# If the lazy attribute has already been computed, then we do
not
# need to bother about the categories having bases.
# Here, the trick is that we look in self.__dict__, so that we
do
# not trigger computation of self._set_of_super_categories, if
it has
# not been done before.
return c in self.__dict__['_set_of_super_categories']
except KeyError:
pass
# 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.
try:
cbase = c.base()
except (AttributeError, TypeError, NotImplementedError):
cbase = None
if cbase is not None:
try:
selfbase = self.base()
except (AttributeError, TypeError, NotImplementedError):
selfbase = None
if selfbase is not cbase:
return False
# Now, the only remaining thing to do is to look at the super
categories.
# Looking it up in a (frozen) set is quickest:
return c in self._set_of_super_categories
}}}
With the new patch, all long doctests pass - needs review!
I am now attending a lecture and will try to provide some timings
afterwards.
Apply trac11943_mro_for_all_super_categories_lazy.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11943#comment:19>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
