Dear Sage developers,
> On Tue, Aug 19, 2008 at 8:14 PM, Bill Page <[EMAIL PROTECTED]> wrote:
> >> The Sage concept of 'parent' is an attempt to capture similar generic
> >> relationships that are represented by categories in Axiom, but I do
> >> not like the fact that this concept needs to be added on to Sage
> >> rather than being supported by some more fundamental feature of
> >> Python, e.g. Python meta-types.
> William Stein:
> Unlike you, I personally like that parent is not a fundamental
> feature of Python, but a "design pattern" that can be implemented on
> top of Python. That means one can directly use the same idea in
> C/C++/etc. code.
Let me reuse this thread for further discussions about categories.
To start with: a disclaimer. I am a complete practitioner
here. Language design is not at all my specialty. But I do have a bit
of experience using and designing categories in MuPAD (MuPAD-Combinat
adds about 60 categories to the standard MuPAD hierarchy) as a design
pattern for organizing and factoring out generic code.
My feeling is that we need both concepts of parents *and* of
categories (more rant about this upon request). And I like the idea of
having them as design pattern not tighten too much to the language. In
particular, this means that we can progressively improve the design
pattern to increase its expressiveness in our context. We used that a
lot in MuPAD. Of course, in the long run, further and deeper support
from the language could help improve the safety.
With Florent, Mike, and Robert we spent some time discussing about
categories for Sage. I am now implementing a prototype (available in
sage-combinat), whose design differs slightly from that of:
http://trac.sagemath.org/sage_trac/ticket/4301
The idea is to let a category define generic code for parents and
elements through standard class inheritance (with some class surgery
done automatically behind the scene). It's a bit more tricky to setup
internally, but avoids messing around with getattr (that is in
practice introducing another technical way for doing multiple
inheritance; I am not speaking of cython object there, which probably
will need some getattr tricks since standard multiple inheritance does
not work).
The current design should leave the door open for those who will want
to do category theory (i.e. calculations on the categories
themselves), rather than using them to organize generic code which is
my own main goal.
See the attached files for some details.
My plan, with the help of Teresa, is to setup soon a full category
hierarchy (with most categories being dummy for the moment), as we had
discussed with Robert and others during Sage days 7 (most inspiration
coming from Axiom/MuPAD). Before we proceed, we have some questions:
- Has anyone done work in this direction lately?
- Did anyone keep a list or graph of the desired categories from sage days 7?
For reference, the hierarchy for MuPAD-Combinat is available there:
http://mupad-combinat.sourceforge.net/Papers/Categories.pdf
- Are the Sage categories currently used for anything but documenting
and testing the mathematical properties of parents?
- In particular, does anything depend on the current category
hierarchy, as defined at the end of categories/category_types.py,
or should we feel free to reorganize / extend it in any
mathematically meaningful way?
- Do we want to stick to the (possibly questionable) Axiom/MuPAD
convention to distinguish between monoids (or groups/...) written
additively or multiplicatively:
- AbelianGroup, AbelianMonoid, ...: structure for the + operation
- Monoid, Group, CommutativeGroup, ...: structure for the * operation
With this convention, a Ring is both an AbelianGroup and a Monoid
Alternatively, one could use the more verbose AdditiveMonoid
w.r.t. MultiplicativeMonoid; other suggestions are welcome.
Part of the question is whether we will ever want to have a
category for non abelian monoids written additively (I would
personnaly frown upon this, as much as I dislike using + for
concatenation of lists and strings; but that might be just me).
Best regards,
Nicolas
--
Nicolas M. Thiéry "Isil" <[EMAIL PROTECTED]>
http://Nicolas.Thiery.name/
--~--~---------~--~----~------------~-------~--~----~
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-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
"""
Categories
AUTHORS: David Kohel and William Stein
Every SAGE object lies in a category. Categories in SAGE are modeled on
the mathematical idea of category, and are distinct from Python
classes, which are a programming construct.
In most cases, typing \code{x.category()} returns the category to
which $x$ belongs. If $C$ is a category and $x$ is any object, $C(x)$
tries to make an object in $C$ from $x$.
See Category? for more details
EXAMPLES:
We create a couple of categories.
sage: Sets()
Category of sets
sage: GSets(AbelianGroup([2,4,9]))
Category of G-sets for Multiplicative Abelian Group isomorphic to C2 x C4 x C9
sage: Semigroups()
Category of semigroups
sage: VectorSpaces(FiniteField(11))
Category of vector spaces over Finite Field of size 11
sage: Ideals(IntegerRing())
Category of ring ideals in Integer Ring
The default category for elements $x$ of an objects $O$ is the
category of all objects of $O$. For example,
sage: V = VectorSpace(RationalField(), 3)
sage: x = V.gen(1)
sage: x.category()
Category of elements of Vector space of dimension 3 over Rational Field
"""
#*****************************************************************************
# Copyright (C) 2005 David Kohel <[EMAIL PROTECTED]> and
# William Stein <[EMAIL PROTECTED]>
#
# Distributed under the terms of the GNU General Public License (GPL)
#
# This code is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty
# of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
#
# See the GNU General Public License for more details; the full text
# is available at:
#
# http://www.gnu.org/licenses/
#*****************************************************************************
__doc_exclude = ['k', 'uniq', 'uniq1', 'latex', \
'Category', 'Category_ideal', 'Category_in_ambient', \
'Category_module', 'Category_over_base', \
'Category_over_base_ring','SageObject']
from sage.misc.latex import latex
from sage.structure.sage_object import SageObject
from sage import graphs
from sage.misc.lazy_attribute import lazy_attribute
from sage.misc.cachefunc import cached_function
@cached_function
def build_class_inner(cls, super_classes, name):
return type(name,
cls.__bases__ + super_classes,
dict(cls.__dict__))
def build_class(cls, super_classes, name):
return build_class_inner(cls, tuple(super_classes), name)
class Category(SageObject):
r"""
The base class for all categories.
Categories in Sage model the mathematical idea of category, and
are distinct from Python classes, which are a programming construct.
Here are some examples:
\begin{description}
\item[Groups()] the category of groups
\item[EuclideanRings()] the category of euclidean rings
\item[VectorSpaces(QQ)] the category of vector spaces over the field of rational
\end{description}
Technically, a category is an instance of the class Category of
some of its subclasses. Some categories, like VectorSpaces, are
parametrized: VectorSpaces(QQ) is one of many instances of the
class VectorSpaces. On the other hand, EuclideanRings() is the
single instance of the class EuclideanRings.
Recall that an algebraic structure (say the ring QQ[x]) is
modelled in Sage by an object which is called a parent. This
object belongs to certain categories (here EuclideanRings() and
Algebras()). The elements of the ring are themselves objects.
The class of a category (say EuclideanRings) can define simultaneously:
\begin{itemize}
\item Operations on the category itself (what are its super categories, its category of
morphisms?, its dual category)
\item Generic operations on parents in this category, like the ring QQ[x]
\item Generic operations on elements (Euclide algorithm for computing gcds)
\end{itemize}
This is achieved as follows:
sage: from sage.categories.category_types import Category
sage: from sage.categories.category import uniq
sage: class EuclideanRings(uniq, Category):
... # operations on the category itself
... def super_categories(self):
... [Rings()]
...
... def dummy(self): # TODO: find some good examples
... pass
...
... class Parent: # holds the generic operations on parents
... # find a good example of operation
... pass
...
... class Element:# holds the generic operations on elements
... def gcd(x,y):
... # Euclid algorithms
... pass
Note that the EuclideanRings.Parent and .Element class above do
not inherit from anything. They are merely containers of
operations. The hierarchy between the different categories is
defined once at the level of the categories. Behind the scene, a
parallel hierarchy of classes is built automatically from all the
.Parent classes. Then, a parent in a category receives the
appropriate operations from all the super categories by usual
class inheritance. Similarly, a third hierarchy of classes is
built for elements from the .Elements.
EXAMPLES:
We define a hierarchy of four categories As(), Bs(), Cs(), Ds()
with a diamond inheritance. Think for example:
\begin{description}
\item[As()] the category of sets
\item[Bs()] the category of additive groups
\item[Cs()] the category of multiplicative monoids
\item[Ds()] the category of rings
\end{description}
sage: from sage.categories.category_types import Category
sage: from sage.categories.category import uniq
sage: from sage.misc.lazy_attribute import lazy_attribute
sage: class As (uniq, Category):
... @lazy_attribute
... def super_categories(self):
... return []
...
... class Parent:
... def fA(self):
... return "A"
... f = fA
...
sage: class Bs (uniq, Category):
... @lazy_attribute
... def super_categories(self):
... return [As()]
...
... class Parent:
... def fB(self):
... return "B"
...
sage: class Cs (uniq, Category):
... @lazy_attribute
... def super_categories(self):
... return [As()]
...
... class Parent:
... def fC(self):
... return "C"
... f = fC
...
sage: class Ds (uniq, Category):
... @lazy_attribute
... def super_categories(self):
... return [Bs(),Cs()]
...
... class Parent:
... def fD(self):
... return "D"
...
Categories should always have uniq representation. We check
this before proceeding:
FIXME: should Category inherit from a generalized uniq class?
sage: id(As()) == id(As())
True
sage: As().parent_class == As().parent_class
True
We construct a parent in the category Ds() (that is an instance of
Ds().parent_class, and check that it has access to all the
methods provided by all the categories, with the appropriate
inheritance order.
sage: D = Ds().parent_class()
sage: [ D.fA(), D.fB(), D.fC(), D.fD() ]
['A', 'B', 'C', 'D']
sage: D.f()
'C'
sage: C = Cs().parent_class()
sage: [ C.fA(), C.fC() ]
['A', 'C']
sage: C.f()
'C'
Here is the parallel hierarchy of classes which has been built
automatically, together with the method resolution order (.mro()):
sage: As().parent_class
<class '__main__.As.parent_class'>
sage: As().parent_class.__bases__
(<type 'object'>,)
sage: As().parent_class.mro()
[<class '__main__.As.parent_class'>, <type 'object'>]
sage: Bs().parent_class
<class '__main__.Bs.parent_class'>
sage: Bs().parent_class.__bases__
(<class '__main__.As.parent_class'>,)
sage: Bs().parent_class.mro()
[<class '__main__.Bs.parent_class'>, <class '__main__.As.parent_class'>, <type 'object'>]
sage: Cs().parent_class
<class '__main__.Cs.parent_class'>
sage: Cs().parent_class.__bases__
(<class '__main__.As.parent_class'>,)
sage: Cs().parent_class.__mro__
(<class '__main__.Cs.parent_class'>, <class '__main__.As.parent_class'>, <type 'object'>)
sage: Ds().parent_class
<class '__main__.Ds.parent_class'>
sage: Ds().parent_class.__bases__
(<class '__main__.Bs.parent_class'>, <class '__main__.Cs.parent_class'>)
sage: Ds().parent_class.mro()
[<class '__main__.Ds.parent_class'>, <class '__main__.Bs.parent_class'>, <class '__main__.Cs.parent_class'>, <class '__main__.As.parent_class'>, <type 'object'>]
Note that that two categories in the same class need not have the
same super_categories. For example, Algebras(QQ) has
VectorSpaces(QQ) as super category, whereas Algebras(ZZ) only has
Modules(ZZ) as super category. In particular, the constructed
parent_class and element_class will differ (inheriting, or not,
methods specific for vector spaces). On the other hand, caching
ensures that two identical hierarchy of classes are built only
once:
# TODO: redo the same with Algebras
# and show the mro for Algebras(QQ) w.r.t Algebras(ZZ)
sage: Coalgebras(QQ).parent_class is Coalgebras(FractionField(QQ[x])).parent_class
True
We now construct a parent in the usual way:
sage: from sage.categories.category import build_class
sage: class myparent(Parent):
... def __init__(self):
... Parent.__init__(self, categories=[Ds()])
... def g(self):
... return "myparent"
sage: D = myparent()
sage: D.__class__
<class '__main__.myparent_with_categories'>
sage: D.__class__.__bases__
(<type 'sage.structure.parent.Parent'>, <class '__main__.Ds.parent_class'>)
sage: D.__class__.mro()
[<class '__main__.myparent_with_categories'>, <type 'sage.structure.parent.Parent'>, <type 'sage.structure.category_object.CategoryObject'>, <type 'sage.structure.sage_object.SageObject'>, <class '__main__.Ds.parent_class'>, <class '__main__.Bs.parent_class'>, <class '__main__.Cs.parent_class'>, <class '__main__.As.parent_class'>, <type 'object'>]
sage: D.fA()
'A'
sage: D.fB()
'B'
sage: D.fC()
'C'
sage: D.fD()
'D'
sage: D.f()
'C'
sage: D.g()
'myparent'
"""
def __init__(self, s=None):
if s is None: # figure out from the type name!
t = str(type(self))
t = t[t.rfind('.')+1:]
s = t[:t.rfind("'")]
self.__label = s
i = -1
while i < len(s)-1:
for i in range(len(s)):
if s[i].isupper():
s = s[:i] + " " + s[i].lower() + s[i+1:]
break
s = s.lstrip()
elif isinstance(s, str):
self.__label = s
else:
raise TypeError, "Argument string must be a string."
self.__category = s
def __call__(self, x):
if x in self:
return x
return self._call_(x)
def _call_(self, x):
raise NotImplementedError
def _repr_(self):
return "Category of %s"%self.__category
def _latex_(self):
return "\\mbox{\\bf %s}"%self.__label
def __hash__(self):
return hash(self.__category)
def short_name(self):
return ''.join([x.capitalize() for x in self.__category.split()])
def __contains__(self, x):
try:
c = x.category()
except AttributeError:
return False
return c.is_subcategory(self)
def is_abelian(self):
return False
def is_subcategory(self, c):
"""
Returns True if self is naturally embedded as a subcategory of c.
EXAMPLES:
sage: Rings = Rings()
sage: AbGrps = AbelianGroups()
sage: Rings.is_subcategory(AbGrps)
True
sage: AbGrps.is_subcategory(Rings)
False
The \code{is_subcategory} function takes into account the base.
sage: M3 = VectorSpaces(FiniteField(3))
sage: M9 = VectorSpaces(FiniteField(9, 'a'))
sage: M3.is_subcategory(M9)
False
"""
# TODO: use all_super_categories()
if not isinstance(c, Category):
raise TypeError, "Argument c (= %s, type = %s) must be a category"%(c, type(c))
if self == c: return True
# if c in self.all_super_categories():
# return True
# For backward compatibility
from category_types import category_hierarchy
if category_hierarchy.has_key(self.__class__):
S = category_hierarchy[self.__class__]
if not c.__class__ in S:
return False
return c._parameters().issubset(self._parameters())
return False
# def all_super_categories_graph(self):
# r"""
# Returns the graph of all super categories of this category
# """
# done = set()
# g = graphs.graph.DiGraph([self])
# def add_successors(cat): # Factor this out!
# if cat in done:
# return;
# for super in cat.super_categories:
# g.add_vertex(super)
# g.add_edge([cat, super])
# add_successors(super)
# add_successors(self)
# return g
def all_super_categories(self):
r"""
Returns a linear extension (topological sort) of all the super categories
of this category, and cache the result
FIXME: make sure this is compatible with the python algorithm
and make it O(n+m)
"""
if not hasattr(self, "_all_super_categories"):
# done = set()
all_categories = []
def add_successors(cat): # Factor this out!
# if cat in done:
# return;
# done.add(cat)
for super in cat.super_categories:
all_categories.append(super)
add_successors(super)
add_successors(self)
all_categories.reverse()
done = set()
linear_extension = []
for cat in all_categories:
if not cat in done:
done.add(cat)
linear_extension.append(cat)
linear_extension.reverse()
self._all_super_categories = linear_extension
return self._all_super_categories
class Parent:
pass
@lazy_attribute
def parent_class(self):
return build_class(self.Parent,
(cat.parent_class for cat in self.super_categories),
name = "%s.parent_class"%self.__class__.__name__)
def _is_subclass(self, c,):
from category_types import category_hierarchy
if isinstance(c, Category):
return self.is_subcategory(c)
if self.__class__ == c:
return True
return c in category_hierarchy[self.__class__]
def __eq__(self, c):
if self is c:
return True
return False
def _parameters(self):
return set([])
def category(self):
return Objects()
def is_Category(x):
"""
Returns True if x is a category.
"""
return isinstance(x, Category)
#############################################################
# ...
#############################################################
class uniq(object):
__new__ = cached_function(object.__new__)
uniq1 = uniq
#############################################################
# Join of several categories
#############################################################
class JoinCategory(uniq, Category):
"""
The join of several categorie
EXAMPLES:
sage: from sage.categories.category import JoinCategory
sage: JoinCategory(Groups(), AbelianMonoids())
Join of Category of groups and Category of abelian monoids
sage: AbelianGroups().super_categories
[Category of groups, Category of abelian monoids]
sage: AbelianGroups().all_super_categories()
[Category of groups,
Category of abelian monoids,
Category of monoids,
Category of abelian semigroups,
Category of semigroups,
Category of sets]
"""
def __init__(self, *super_categories):
self.super_categories = super_categories
def _repr_(self):
return "Join of %s"%(" and ".join(str(cat) for cat in self.super_categories))
def __reduce__(self):
"""
EXAMPLES:
sage: from sage.categories.category import JoinCategory
sage: C = JoinCategory(Groups(), AbelianMonoids())
sage: loads(C.dumps()) == C
True
"""
return JoinCategory, tuple(self.super_categories)
from category_types import Category_over_base_ring
from sage.categories.all import Category, TensorialCategory, DualityCategory, Algebras, Coalgebras
from sage.misc.lazy_attribute import lazy_attribute
class HopfAlgebras(Category_over_base_ring, TensorialCategory, DualityCategory):
"""
The category of Hopf algebras
EXAMPLES:
sage: HopfAlgebras(QQ)
Category of hopf algebras over Rational Field
sage: HopfAlgebras(QQ).super_categories
[Category of algebras over Rational Field, Category of coalgebras over Rational Field]
"""
@lazy_attribute
def super_categories(self):
R = self.base_ring()
return [Algebras(R), Coalgebras(R)]
def dual(self): # The category of Hopf Algebra is self dual
self
class Element:
def antipode(self):
# delegates to the overloading mechanism
# result not guaranted to be in self
operator.antipode(self)
class Parent:
def __setup__(self): # Check the conventions for _setup_ or __setup__
if self.implements("antipode"):
coercion.declare(operator.antipode, [self], self.antipode)
@lazy_attribute
def antipode(self):
# delegates to the overloading mechanism but
# guarantees that the result is in self
compose(self, operator.antipode, domain=self)
class Morphism(Category):
"""
The category of Hopf algebra morphisms
"""
pass
class TensorCategory(Category_over_base_ring):
"""
The category of Hopf algebras constructed by tensor product of Hopf algebras
"""
@lazy_attribute
def super_categories(self):
return [Hopfalgebras(self.base_ring),
Algebras(self.base_ring).TensorCategory(),
Coalgebras(self.base_ring).TensorCategory()]
class Parent:
"""
implements operations on tensor products of Hopf algebras
"""
@lazy_attribute
def antipode(self):
operator.tensor(module.antipode for module in self.modules)
class Element:
"""
implements operations on elements of tensor products of Hopf algebras
"""
pass
class DualCategory(Category_over_base_ring):
"""
The category of Hopf algebras constructed as dual of a Hopf algebra
"""
class Parent:
"""
implements operations on the dual of a Hopf algebra
"""
@lazy_attribute
def antipode(self):
self.dual().antipode.dual() # Check that this is the correct formula
