The purpose of categories in Sage is to translate the mathematical concept of categories (category of groups, of vector spaces, ...) into a concrete software engineering design pattern for:
- organizing and promoting generic code
- fostering consistency across the Sage library (naming conventions, doc, tests)
- embedding more mathematical knowledge into the system
This design pattern is largely inspired from Axiom and its followers (Aldor, Fricas, MuPAD, ...). It differs from those by:
- blending in the Magma inspired concept of Parent/Element
- being built on top of (and not into) the standard Python object oriented and class hierarchy mechanism. This did not require changing the language, and could in principle be implemented in any language allowing for dynamically creating new classes.
Goal: mathematical computations
Requires modeling mathematical objects and operations on the computer
Examples:
A mathematical object is modeled by an instance of a class.
For example, an integer in Sage is an instance of the class Integer (and knows it!):
sage: i = 12
sage: type(i)
<type 'sage.rings.integer.Integer'>
Applying an operation is generally done by calling a method:
sage: i.factor()
2^2 * 3
sage: type(x^2+2*x+1)
<type 'sage.symbolic.expression.Expression'>
sage: (x^2+2*x+1).factor()
(x + 1)^2
This illustrates polymorphism, data abstraction, and encapsulation.
Let us be curious:
sage: i.is_one?? # not tested
sage: i.__add__?? # not tested
sage: i._add_?? # not tested
Some examples of mathematical sets and operations on them:
sage: ZZ.one()
1
sage: R = QQ['x,y']
sage: R.krull_dimension()
2
sage: A = R.quotient( R.ideal(x^2 - 2) )
sage: A.krull_dimension() # todo: not implemented
Philosophy: Building mathematical information into the system yields more expressive, more conceptual and, at the end, easier to maintain and faster code.
(within a programming realm; this would not necessarily apply to specialized libraries like gmp!)
Example of mathematical information:
sage: i.parent()
Integer Ring
sage: i.parent().category()
Category of euclidean domains
sage: i.parent().categories()
[Category of euclidean domains,
Category of principal ideal domains,
Category of gcd domains,
Category of integral domains,
Category of commutative rings,
Category of domains,
Category of rings,
Category of rngs,
Category of commutative additive groups,
Category of commutative additive monoids,
Category of commutative additive semigroups,
Category of additive magmas,
Category of monoids,
Category of semigroups,
Category of magmas,
Category of sets,
Category of sets with partial maps,
Category of objects]
sage: EuclideanDomains().category_graph().plot(talk = True)
This illustrates the following relations between mathematical objects:
A parent is a Python instance representing a set of mathematical elements.
Examples include the ring of integers, the group , the set of
prime numbers, the set of linear maps between a given two vector
spaces, and a given finite semigroup.
These sets are often equipped with additional structure: the set of all integers forms a ring. The main way of encoding this information is specifying which categories a parent belongs to.
It is completely possible to have different Python instances representing the same set of elements. For example, one might want to consider the ring of integers, or the poset of integers under their standard order, or the poset of integers under divisibilityor the semiring of integers under the operations of addition and maximum. Each of these would be a different instance, belonging to different categories.
For a given model, there should be a unique instance in Sage representing that parent:
sage: IntegerRing() is IntegerRing()
True
An element is a Python instance representing a mathematical element of a set.
Examples of element include 5 in the integer ring, in
the polynomial ring in
over the rationals,
in the
3-adics, the transposition
in
, and the identity
morphism in the set of linear maps from
to
.
Every element in Sage has a parent. The standard mechanism in Sage for creating elements is to create their parent, and then provide enough data to define the element:
sage: R = PolynomialRing(ZZ, name='x')
sage: R([1,2,3])
3*x^2 + 2*x + 1
One can also create elements using various methods on the parent and arithmetic of elements:
sage: x = R.gen()
sage: 1 + 2*x + 3*x^2
3*x^2 + 2*x + 1
Unlike parents, elements in Sage are not necessarily unique:
sage: ZZ(5040) is ZZ(5040)
False
Many parents represent algebraic structures, and their elements support arithmetic operations. One often further wants to do arithmetic by combining elements from different parents: adding together integers and rationals for example. Sage supports this feature using coercion (see sage.structure.coerce for more details).
It is possible for parents to also have simultaneously the structure of an element. Consider for example the monoid of all finite groups, endowed with the cartesian product operation. Then, every finite group (which is a parent) is also an element of this monoid. This is not yet implemented, and the design details are not yet fixed but experiments are underway in this direction.
TODO: give a concrete example, typically using ElementWrapper.
A category is a Python instance representing a mathematical category.
Examples of categories include the category of rings, the category
of finite semigroups, the category of bigraded -algebras, the
category of Python objects, and the category of cartesian products of
free modules.
Every parent belongs to a collection of categories. Moreover, these categories are related by the relation of being super categories. For example, the category of rings is a super category of the category of fields, because every field is also a ring.
A category serves two roles:
Objects of a mathematical category are not necessarily parents. Parent has a superclass that provides a means of modeling such.
For example, schemes do not have a faithful forgetful functor to the category of Sets, so it does not make sense to talk about Schemes as Parents.
(Todo: include a picture!)
Let us look at a semigroup (now would be a good time to go through the sage.categories.tutorial):
sage: S = FiniteSemigroups().example()
sage: S? # not tested
Where do all the operations come from?
sage: x = S(‘a’)
_repr_ is a technical method which comes with the data structure (ElementWrapper):
sage: x._repr_?? # not tested
is_idempotent is a mathematical method provided by the parent (which knows that all its elements are idempotents!):
sage: x.is_idempotent?? # not tested
__pow__ is a generic method for all finite semigroups:
sage: x.__pow__?? # not tested
_mul_ delegates the work to the parent (if you do not know what to do, ask your parent):
sage: x.__mul__?? # not tested
cayley_graph is a generic method on the parent, provided by finite semigroups
sage: S.cayley_graph?? # not tested
Consider the implementation of the semigroup:
sage: S?? # not tested
This implementation specifies a data structure for the parents and the elements, and makes a promise: the implemented parent is a semigroup. Then it fullfills the promise by implemented the basic operations product and semigroup_generators. In exchange of this promise, S and its elements receive generic implementations of all the other operations. S may override any of the operations by more efficient ones, like for is_idempotent.
There is the code for the finite semigroups category:
sage: FiniteSemigroups?? # not tested
Wrapup: the mathematical relations between elements, parents, and categories translates into inheritance between classes:
sage: FiniteSemigroups().all_super_categories()
[Category of finite semigroups,
Category of semigroups,
Category of magmas,
Category of finite enumerated sets,
Category of enumerated sets,
Category of sets,
Category of sets with partial maps,
Category of objects]
sage: S.__class__.mro()
[<class 'sage.categories.examples.finite_semigroups.LeftRegularBand_with_category'>,
<class 'sage.categories.examples.finite_semigroups.LeftRegularBand'>,
<class 'sage.structure.unique_representation.UniqueRepresentation'>,
<type 'sage.structure.parent.Parent'>,
<type 'sage.structure.category_object.CategoryObject'>,
<type 'sage.structure.sage_object.SageObject'>,
<class 'sage.categories.finite_semigroups.FiniteSemigroups.parent_class'>,
<class 'sage.categories.semigroups.Semigroups.parent_class'>,
<class 'sage.categories.magmas.Magmas.parent_class'>,
<class 'sage.categories.finite_enumerated_sets.FiniteEnumeratedSets.parent_class'>,
<class 'sage.categories.enumerated_sets.EnumeratedSets.parent_class'>,
<class 'sage.categories.sets_cat.Sets.parent_class'>,
<class 'sage.categories.category.SetsWithPartialMaps.parent_class'>,
<class 'sage.categories.objects.Objects.parent_class'>,
<type 'object'>]
sage: x.__class__.mro()
[<class 'sage.categories.examples.finite_semigroups.LeftRegularBand_with_category.element_class'>,
<class 'sage.categories.examples.finite_semigroups.LeftRegularBand.Element'>,
<class 'sage.structure.element_wrapper.ElementWrapper'>,
<type 'sage.structure.element.Element'>,
<type 'sage.structure.sage_object.SageObject'>,
<class 'sage.categories.category.FiniteSemigroups.element_class'>,
<class 'sage.categories.semigroups.Semigroups.element_class'>,
<class 'sage.categories.magmas.Magmas.element_class'>,
<class 'sage.categories.category.FiniteEnumeratedSets.element_class'>,
<class 'sage.categories.enumerated_sets.EnumeratedSets.element_class'>,
<class 'sage.categories.sets_cat.Sets.element_class'>,
<class 'sage.categories.category.SetsWithPartialMaps.element_class'>,
<class 'sage.categories.objects.Objects.element_class'>,
<type 'object'>]
sage: S=FiniteSemigroups().example(alphabet=('a', 'b'))
sage: TestSuite(S).run(verbose = True)
running ._test_an_element() . . . pass
running ._test_associativity() . . . pass
running ._test_category() . . . pass
running ._test_elements() . . .
Running the test suite of self.an_element()
running ._test_category() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass
pass
running ._test_enumerated_set_contains() . . . pass
running ._test_enumerated_set_iter_cardinality() . . . pass
running ._test_enumerated_set_iter_list() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass
running ._test_some_elements() . . . pass
sage: S._test_associativity?? # not tested
sage: S._test_associativity(elements=S)
Let us now test broken code:
sage: %pdb # not tested
sage: S.product = lambda x, y: S("("+x.value +y.value+")")
sage: S._test_associativity()
Traceback (most recent call last):
...
File ".../sage/categories/semigroups.py", line ..., in _test_associativity
tester.assert_((x * y) * z == x * (y * z))
...
AssertionError
Wrapup:
- Categories bring not only code, but also testing tools
- This enforces robustness and consistency (despite using an interpreted language)
sage: HopfAlgebrasWithBasis(QQ)?? # not tested
sage: HopfAlgebrasWithBasis(QQ).category_graph().plot()
sage: A = AlgebrasWithBasis(QQ).example(); A.rename("A") # todo: not implemented
sage: B = HopfAlgebrasWithBasis(QQ).example(); B.rename("B") # todo: not implemented
sage: C = cartesian_product([A, B, B]); C # todo: not implemented
A (+) B (+) B
sage: C.one() # todo: not implemented
A[(0, ())] + B[(1, ())] + B[(2, ())]
sage: cartesian_product([A.one(), B.one(), B.one()]) # todo: not implemented
A[(0, ())] + B[(1, ())] + B[(2, ())]
sage: C.one?? # todo: not implemented
sage: C.product?? # todo: not implemented
sage: C.categories() # todo: not implemented
[Join of Category of cartesian products of algebras with basis over Rational Field and Category of cartesian products of modules with basis over Rational Field and Category of cartesian products of algebras over Rational Field,
Category of cartesian products of algebras with basis over Rational Field,
Category of algebras with basis over Rational Field,
Category of cartesian products of modules with basis over Rational Field,
Category of modules with basis over Rational Field,
Category of vector spaces over Rational Field,
Category of cartesian products of algebras over Rational Field,
Category of algebras over Rational Field,
Category of rings,
Category of rngs,
Category of monoids,
Category of semigroups,
Category of modules over Rational Field,
Category of bimodules over Rational Field on the left and Rational Field on the right,
Category of left modules over Rational Field,
Category of right modules over Rational Field,
Category of abelian groups,
Category of abelian monoids,
Category of abelian semigroups,
Category of sets,
Category of objects]
Other functorial constructions:
- cartesian product
- quotient / sub / subquotient
- tensor product
- dual
- morphisms
Each category should come with a good example, in sage.categories.examples.
The order between super categories should not be mathematically relevant (otherwise this usually means the category hierarchy is wrong). One the other hand, it should be consistent, to help Python build the method resolution order for the generated classes (it always respects inheritance, and tries to respect the order of the bases).
The current convention is to order them lexicographically w.r.t. the following criterions:
- Graded... or Finite dimensional... first
- ...WithBasis first
- Algebras before Coalgebras
- Modules first
This gives the following order:
sage: GradedHopfAlgebrasWithBasis(QQ).all_super_categories()
[Category of graded hopf algebras with basis over Rational Field,
Category of graded bialgebras with basis over Rational Field,
Category of graded algebras with basis over Rational Field,
Category of graded coalgebras with basis over Rational Field,
Category of graded modules with basis over Rational Field,
Category of graded hopf algebras over Rational Field,
Category of graded bialgebras over Rational Field,
Category of graded algebras over Rational Field,
Category of graded coalgebras over Rational Field,
Category of graded modules over Rational Field,
Category of hopf algebras with basis over Rational Field,
Category of bialgebras with basis over Rational Field,
Category of algebras with basis over Rational Field,
Category of coalgebras with basis over Rational Field,
Category of modules with basis over Rational Field,
Category of vector spaces over Rational Field,
Category of hopf algebras over Rational Field,
Category of bialgebras over Rational Field,
Category of algebras over Rational Field,
Category of rings,
Category of rngs,
Category of monoids,
Category of semigroups,
Category of magmas,
Category of coalgebras over Rational Field,
Category of modules over Rational Field,
Category of bimodules over Rational Field on the left and Rational Field on the right,
Category of left modules over Rational Field,
Category of right modules over Rational Field,
Category of commutative additive groups,
Category of commutative additive monoids,
Category of commutative additive semigroups,
Category of additive magmas,
Category of sets,
Category of sets with partial maps,
Category of objects]
Todo: any better convention? Maybe we should further specify that subcategories of Modules() go first?