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.

To motivate the design, we need to come back to the basics: the purpose of Sage is to do mathematical computations, and this requires modeling mathematical objects and operations on the computer. Let us review some examples of such objects and operations:

- An integer: \(+\), \(*\), factorization
- A matrix: \(+\), \(*\), determinant
- A word: pattern matching, ...
- The permutations of 5, the rational points of an elliptic curve: counting, listing, random generation
- A language (set of words): rationality testing, counting elements, generating series
- A finite semigroup: left/right ideals, center, representation theory
- A vector space, an algebra: cartesian product, tensor product, quotient
- The category of algebras: what’s its initial object? its super categories? its dual category?

The fundamental principle of object oriented programming (OOP) is that
any object that a program is to manipulate should be modeled by an
*instance* of a *class*. The class implements:

- a
data structure: which describes how the object is storedmethods: which describe the operations on the object

The instance itself contains the data for the given object, according to the specified data structure.

Hence, all the objects mentionned above should be instances of some classes. For example, an integer in Sage is an instance of the class Integer (and it knows about 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: p = 6*x^2 + 12*x + 6
sage: type(p)
<type 'sage.symbolic.expression.Expression'>
sage: p.factor()
6*(x + 1)^2
sage: R.<x> = PolynomialRing(QQ, sparse=True)
sage: pQ = R ( p )
sage: type(pQ)
<class 'sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse_field'>
sage: pQ.factor()
(6) * (x + 1)^2
sage: pZ = ZZ[x] ( p )
sage: type(pZ)
<type 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>
sage: pZ.factor()
2 * 3 * (x + 1)^2
```

Factoring integers, expressions, or polynomials are distinct tasks,
with completely different algorithms. Yet, from a user (or caller)
point of view, all those objects can be manipulated alike. This
illustrates the OOP concepts of *polymorphism*, *data abstraction*,
and *encapsulation*.

Let us be curious, and see where some methods are defined. This can be done by introspection:

`sage: i._mul_?? # not tested`

For plain Python methods, one can also just ask in which module they are implemented:

```
sage: i._pow_.__module__
'sage.categories.semigroups'
sage: pQ._mul_.__module__
'sage.rings.polynomial.polynomial_element_generic'
sage: pQ._pow_.__module__
'sage.categories.semigroups'
```

We see that integers and polynomials have each their own multiplication method: the multiplication algorithms are indeed unrelated and deeply tied to their respective datastructures.

On the other hand, they share the same powering method. Mathematically speaking the sets \(\ZZ\) of integers, and the set \(\QQ[x]\) of polynomials are both semigroups: i.e. sets endowed with an associative binary internal lay \(*\). Once we know how to compute products, the powering operation is the same for all semigroups; hence it can be implemented once for all for all semigroups.

This illustrates the use of *hierarchy of classes* to share common
code between classes having common behaviour. Namely, the class for
integers and the class for polynomials both derive from an *abstract
class* for elements of a semigroups, which factors out the *generic*
methods like `_pow_`.

OOP design is all about isolating the objects that one wants to model
and their operations, and building up an appropriate hierarchy of
classes for organizing the code. Luckily for mathematicians, a lot of
this work is given for free by abstract algebra. Namely, the
hierarchy of classes can be modeled upon the hierarchy of abstract
algebraic structures (i.e. *categories*): semigroups, monoids, groups,
rings, algebras, etc. For example, a group is a special case of a
monoid (i.e. the category of groups is a subcategory of the category
of monoids). Therefore, the abstract class for elements of a group
should derive from the abstract classes for elements of monoid.

Before going further, let us recall that we do not just want to compute with elements of mathematical sets, but with the sets themselves:

```
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
```

Hence there should be another hierarchy of classes for those sets.

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!)

Here is some mathematical information that Sage is aware of:

```
sage: 1.parent()
Integer Ring
sage: ZZ
Integer Ring
sage: ZZ.category()
Category of euclidean domains
sage: ZZ.categories()
[Category of euclidean domains,
Category of principal ideal domains,
Category of unique factorization domains,
Category of gcd domains,
Category of integral domains,
Category of domains,
Category of commutative rings,
Category of rings,
Category of rngs,
Category of semirings,
Category of monoids,
Category of semigroups,
Category of magmas,
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]
sage: EuclideanDomains().category_graph().plot(talk = True)
```

This illustrates the following relations between mathematical objects:

- elements <-> parent
- parents <-> category
- subcategory <-> super category

**Parent**A parent is a Python instance representing a set of mathematical elements together with its additional (algebraic) strcuture.

Examples include the ring of integers, the group \(S_3\), 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 divisibility or 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

**Element**An element is a Python instance representing a mathematical element of a set.

Examples of element include 5 in the integer ring, \(x^3 - x\) in the polynomial ring in \(x\) over the rationals, \(4 + O(3^3)\) in the 3-adics, the transposition \((1 2)\) in \(S_3\), and the identity morphism in the set of linear maps from \(\QQ^3\) to \(\QQ^3\).

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 a parent 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`.**Category**A category is a Python instance representing a mathematical category.

Examples of categories include the category of finite semigroups, the category of \(\ZZ\)-algebras, the category of bigraded \(\QQ\)-algebras, the category of all (Python) objects, and the category of cartesian products of \(\ZZ\)-algebras:

sage: FiniteSemigroups() Category of finite semigroups sage: Algebras(ZZ) Category of algebras over Integer Ring sage: Objects() Category of objects sage: Algebras(ZZ).CartesianProducts() Category of Cartesian products of algebras over Integer Ring

(mind the ‘s’ in the names of the categories above;

`GroupAlgebra`and`GroupAlgebras`are distinct things).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:

- to provide a model for the mathematical concept of a category and the associated structures (homsets, morphisms, functorial constructions)
- to organize and promote generic code, naming conventions, documentation, and tests across similar mathematical structures.

**CategoryObjects**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:

```
sage: S = FiniteSemigroups().example()
sage: S? # not tested
```

Now would be a good time to go through the
`sage.categories.tutorial`!

Where do all the operations on `S` and its elements come from?

```
sage: x = S('a')
```

`_repr_` is a technical method which comes with the data structure
(ElementWrapper), however we can’t see it in python because it is an
extension class (it is in \(sage.structure.element_wrapper\)):

```
sage: x._repr_.__module__
```

`__pow__` is a generic method for all finite semigroups:

```
sage: x.__pow__.__module__
'sage.categories.semigroups'
```

`_mul_` is a default implementation from the `Magmas`
category (a *magma* is a set with an inner law \(*\), not necessarily
associative):

```
sage: x.__mul__.__module__
'sage.categories.magmas'
```

It delegates the work to the parent (if you do not know what to do, ask your parent):

`sage: x.__mul__?? # not tested`

`product` is a mathematical method implemented by the parent:

```
sage: S.product.__module__
'sage.categories.examples.finite_semigroups'
```

`cayley_graph` is a generic method on the parent, provided by the
`FiniteSemigroups` category:

```
sage: S.cayley_graph.__module__
'sage.categories.semigroups'
```

`multiplication_table` is a generic method on the parent, provided
by the `Magmas` category (it does not require associativity):

```
sage: S.multiplication_table.__module__
'sage.categories.magmas'
```

Consider now 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 implementing 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. It could typically implement `is_idempotent` to
always return `True`.

A (not yet complete) list of mandatory and optional methods to be implemented can be found by introspection with:

```
sage: from sage.misc.abstract_method import abstract_methods_of_class
sage: abstract_methods_of_class(FiniteSemigroups().element_class)
{'required': [], 'optional': ['_mul_']}
sage: abstract_methods_of_class(FiniteSemigroups().parent_class)
{'required': ['__contains__'], 'optional': []}
```

Documentation about those methods can be obtained with:

```
sage: C = FiniteSemigroups().element_class
sage: C._mul_? # not tested
```

See also the `abstract_methods` decorator.

Here 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'>,
<class 'sage.structure.unique_representation.CachedRepresentation'>,
<type 'sage.misc.fast_methods.WithEqualityById'>,
<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'>,
<type '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'>]
```

Another feature that a parent receive from its categories are generic
tests; their purpose is to check (at least to some extent) that the
parent has the required mathematical properties (is my semigroup
indeed associative?) and is implemented according to the
specifications (does the method `an_element` indeed return an
element of the parent?):

```
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_eq() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass
pass
running ._test_elements_eq_reflexive() . . . pass
running ._test_elements_eq_symmetric() . . . pass
running ._test_elements_eq_transitive() . . . pass
running ._test_elements_neq() . . . pass
running ._test_enumerated_set_contains() . . . pass
running ._test_enumerated_set_iter_cardinality() . . . pass
running ._test_enumerated_set_iter_list() . . . pass
running ._test_eq() . . . 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)
```

See `TestSuite` for more information.

Let us see what happens when the test fails. Here we redefine the product of \(S\) to something definitely not associative. Since enumeration of elements uses the product, we need to determine a list of elements first:

```
sage: L = list(S.some_elements()); len(L)
4
```

Now we break the product:

```
sage: %pdb # not tested
sage: S.product = lambda x, y: S("("+x.value +y.value+")")
```

Combined with the use of the debugger and introspection, those tests gives instantly a counter example to the associativity of our broken semigroup:

```
sage: S._test_associativity(elements=L)
Traceback (most recent call last):
...
File ".../sage/categories/semigroups.py", line ..., in _test_associativity
tester.assert_((x * y) * z == x * (y * z))
...
AssertionError: False is not true
```

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")
sage: B = HopfAlgebrasWithBasis(QQ).example(); B.rename("B")
sage: C = cartesian_product([A, B, B]); C
A (+) B (+) B
sage: C.one()
B[(0, word: )] + B[(1, ())] + B[(2, ())]
sage: cartesian_product([A.one(), B.one(), B.one()])
B[(0, word: )] + B[(1, ())] + B[(2, ())]
sage: C.one?? # not tested
sage: C.product?? # not tested
sage: C.categories()
[Category of Cartesian products of algebras with basis over Rational Field,
Category of algebras with basis 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 semirings,
Category of Cartesian products of monoids,
Category of monoids,
Category of Cartesian products of semigroups,
Category of semigroups,
Category of Cartesian products of magmas,
Category of magmas,
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 modules over Rational Field,
Category of bimodules over Rational Field on the left and Rational Field on the right,
Category of right modules over Rational Field,
Category of left 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 Cartesian products of sets,
Category of sets,
Category of sets with partial maps,
Category of objects]
```

Wrapup:

- All the mathematical information about algebras with basis (properties of elements, parents, morphisms, cartesian products, tensor products) is gathered in AlgebrasWithBasis

Let \(A\) and \(B\) be two parents, and let us construct their cartesian product \(A\times B\). In which category should this new parent be? For example, if both \(A\) and \(B\) are monoids, then \(A\times B\) is naturally endowed with a monoid structure. Similarly, it could potentially be an algebra, a coalgebra, a differential module, and possibly finite dimensional, graded, or ...

This can only be decided at runtime, by introspection into the properties of \(A\) and \(B\). Furthermore the number of possible combinations (e.g. finite dimensional differential algebra) grows exponnentially with the number of properties.

- Functorial constructions:
- Cartesian products (see
`cartesian_product`) - Tensor products (see
`tensor`) - Subquotients / quotients / subobjects / isomorphic objects
(see
`Sets().Subquotients()`,`Sets().Quotients(), ``Sets().Subobjects()`,`Sets().IsomorphicObjects()` - Dual
- Algebras (see e.g.
`Sets().Algebras(QQ)`) - Morphisms

- Cartesian products (see
- Full subcategories (work in progress):
- finite dimensional / graded? / graded connected
- finite / infinite
- commutative

- Wrapup:
- There is a combinatorial explosion of potential classes
- This explosion can be controlled by implementing “few” building
blocks, and using dynamic classes to
*compose*them together, lazily, according to the needs.

Each category \(C\) **must** be provided with a method `C.super_categories()`
and *can* be provided with a method `C._subcategory_hook_(D)`. Also, it
may be needed to insert \(C\) into the output of the `super_categories()` method
of some other category. This determines the position of \(C\) in the category graph.

A category *may* provide methods that can be used by all its objects,
respectively by all elements of its objects.

Each category *should* come with a good example, in `sage.categories.examples`.

`C.super_categories()` must return a list of categories, namely the
*immediate* super categories of \(C\). Of course, if you know that your
new category \(C\) is an immediate super category of some existing
category \(D\), then you should modify \(D\)‘s `super_categories` to
include \(C\).

The generic method `C.all_super_categories()` will recursively
determine the list of *all* super categories of \(C\). The order of the
categories in this list does influences the inheritance of methods for
parents and elements. Namely, if \(P\) is an object in the category \(C\)
and if \(C_1\) and \(C_2\) are both super categories of \(C\) defining some
method `foo`, then \(P\) will use \(C_1\)‘s version of `foo` if and
only if \(C_1\) appears in `C.all_super_categories()` before \(C_2\).
However this must be considered as an *implementation detail*: if \(C_1\)
and \(C_2\) are incomparable categories, then the order in which they
appear must be mathematically irrelevant: the methods `foo` in \(C_1\)
and \(C_2\) must have the same semantic. Code should not rely on any
specific order, as it it subject to later change. In case one of the
implementation is prefered in a common subcategory of \(C_1\) and \(C_2\),
for example for efficiency reasons, then the ambiguity should be
resolved explicitly by definining a method `foo` in this
category. See the method `some_elements` in the code of the category
`FiniteCoxeterGroups` for an example.

Since trac ticket #11943, `C.all_super_categories()` is computed by the
so-called `C3` algorithm used by Python to compute Method Resolution
Order of new-style classes. Thus the order in
`C.all_super_categories()`, `C.parent_class.mro()` and
`C.element_class.mro()` are guaranteed to be consistent.

Since trac ticket #13589, the `C3` algorithm is put under control of some
total order on categories. This order is not necessarily meaningful,
but it guarantees that `C3` always finds a consistent Method
Resolution Order. For background, see
`sage.misc.c3_controlled`. A visible effect is that the order in
which categories are specified in `C.super_categories()`, or in a
join category, no longer influences the result of
`C.all_super_categories()`.

The default implementation of the method `C.is_subcategory(D)` is to
look up whether \(D\) appears in `C.all_super_categories()`. However,
building the list of all the super categories of \(C\) is an expensive
operation that is sometimes best avoided. For example, if both \(C\) and
\(D\) are categories defined over a base, but the bases differ, then one
knows right away that they can not be subcategories of each other.

When such a short-path is known, one can implement a method
`_subcategory_hook_`. `C.is_subcategory(D)` first calls
`D._subcategory_hook_(C)`. If this returns `Unknown`, then
`C.is_subcategory(D)` tries to find `D` in
`C.all_super_categories()`. Otherwise, `C.is_subcategory(D)`
returns the result of `D._subcategory_hook_(C)`.

By default, `D._subcategory_hook_(C)` tests
`issubclass(C.parent_class,D.parent_class)`, which is very often
giving the right answer:

```
sage: Rings()._subcategory_hook_(Algebras(QQ))
True
sage: HopfAlgebras(QQ)._subcategory_hook_(Algebras(QQ))
False
sage: Algebras(QQ)._subcategory_hook_(HopfAlgebras(QQ))
True
```

Different objects of the same category share some algebraic features, and very often these features can be encoded in a method, in a generic way. For example, for every commutative additive monoid, it makes sense to ask for the sum of a list of elements. Sage’s category framework allows to provide a generic implementation for all objects of a category.

If you want to provide your new category with generic methods for objects
(or elements of objects), then you simply add an attribute called
`ParentMethods` (or `ElementMethods`) carrying a class. The methods
of that class will automatically become methods of the objects (or the
elements). For instance:

```
sage: P.<x,y> = ZZ[]
sage: P.sum([x,y,1])
x + y + 1
sage: P.sum.__module__
'sage.categories.commutative_additive_monoids'
sage: P.sum.__func__ is CommutativeAdditiveMonoids().ParentMethods.sum.__func__
True
```

We recommend to study the code of one example:

```
sage: C = CommutativeAdditiveMonoids()
sage: C?? # not tested
```