All published worksheets from http://sagenb.org
Image: ubuntu2004
Note that an updated version of this worksheet is available in the new "flask notebook server".
How to implement basic algebraic structures
Simon KingFriedrich-Schiller-Universität JenaE-mail: simon dot king at uni hyphen jena dot de© 2011The aim of this tutorial is to explain how one can benefit from Sage's category framework and coercion model when implementing new algebraic structures.
On the one hand, we try to explain the theoretical background. On the other hand, we beef up the theory with a sample implementation of fraction fields. The example is quite thorough and detailed. It covers Sage's category framework, the construction of unique parents, and both simple and advanced parts of Sage's coercion model.
The example is developed step by step, so that it should be easy to follow. Not all applications will require all details that we expose here, so that the reader may pick the cherries that are needed for her or his own work.
Chosing a base class
In Sage, objects that "contain" other objects and belong to a mathematical category (such as the category of sets or the category of algebras over the rational field) are called Parent. Hence, a parent in Sage and an object of a category are very similar notions. A member of a parent is called an element.
When implementing a parent in Sage, one should start with a class that inherits from :class:`sage.structure.parent.Parent`. Note that there exist some very old parents in Sage that are derived from other classes. We aim at refactoring them, but there needs more work to be done (volunteers welcome). Similarly, when implementing an element in Sage, one should start with a class that inherits from :class:' sage.structure.element.Element`.
Sage also provides certain sub-classes that provide the basic framework for a variety of more concrete algebraic parents, such as groups, rings, or fields, and of their elements.
The parent
We want to implement a field, and we should thus start with the base class :class:`sage.rings.field.Field`.
Let us compare the methods provided by that class with the methods provided by a general parent:
Any ring in Sage has a so-called base and a base ring (sometimes the base ring, the base and the ring itself coincide). In our implementation of fraction fields, we use R as base of the fraction field of R, and we use the base ring of R as the base ring of its fraction field. The usual implementation of fraction fields in Sage does the same:
Note that some rings coincide with their base. And also note that not all quotient fields in Sage use base() to tell what ring they were obtained from. A notorious exception is the rational field:
It is very easy to declare a ring as the base of a field: One just passes the ring as argument to the field constructor.
Hence, in our first approach, we simply write a class inheriting from Field, and can use the default initialisation. We provide our class with a custom string representation, such that it prints like a fraction field. In Python, the string representation is given by a method __repr__. Sage has a default implementation of __repr__, that relies on another method: _repr_, with single underscore. Hence, one implements _repr_, not __repr__. We have already mentioned the base_ring method, and a method returning the characteristic of the field is implicitly used in an example below.
Note that some parts of our example depend on fixes that are provided in trac tickets #9944 and #9138. We test whether they are merged into the Sage version you are using, such that we can work around, if needed.
It is automatically tested whether the base ring is actually a ring (if #9138 is merged). But it is not tested whether it is a unique factorisation domain; we will see to that later.
The elements
We use the base class :class:`sage.structure.element.FieldElement`. Note that field elements do not require that their parent is a field:
An element of a fraction field is determined by a numerator and a denominator, which both live in the base ring of the fraction field, and the denominator must not be zero. We take care of that during initialisation, where we also normalise the denominator. By default, the denominator is one.
We provide methods that return numerator and denominator, and we provide a string representation that differs from the usual representation of fraction field elements in Sage, in order to see more easily whether an example uses the existing fraction fields or our new implementation.
Implementing arithmetic operations
In Python and Cython, arithmetic operations are implemented using double underscore methods such as __add__, __mul__, __div__, __invert__. Again, for most of them, Sage provides a default implementation that makes use of a single underscore method to be provided by the user. The default implementation uses Sage's powerful coercion model (see below). Therefore, one must not override the default arithmetic methods.
Before a single underscore method is called, the default implementation of the double underscore methods makes sure that all arguments belong to the same parent. So, when implementing the single underscore methods, we can assume that both arguments belong to the same parent.
Let us now refine our element class, so that we can do some arithmetic. Note that when constructing a new element, we do not directly name our class MyElement. Instead, we return an instance of the same class as self. The reason is that later we will in fact work with sub-classes of MyElement.
We also implement comparison with the method __cmp__, where we can again assume that both arguments belong to the same parent. Note that if you program in Cython, you must use a slightly different way, that is explained in the module sage.structure.element.
Note that there is a default implementation of exponentiation. Hence, unless you want to provide a more efficient way, you can rely on the default:
We verify that the comparison does as we wish:
Also note that there is a default implementation of element tests. So, we can do
but we can, for example, not verify that the integers are contained in the fraction field of the ring of integers:
We will take care of that later.
Chosing a category
As we have mentioned above, a parent can be understood as an object of a category (in the sense of algebra). It is no surprise that our parent P defined above knows that it belongs to the category of fields, as it is derived from the base class of fields.
However, we could choose a smaller category, namely the category of quotient fields.
Why should one choose a category?
As usual in Python, one can define base classes, and then all classes derived from them inherit certain default methods; we have seen examples above. In addition to that, one can provide default methods for all objects of a category, and for all elements of such objects. In other words, there is a different way of inheriting useful stuff. It does not rely on implementation (such as class inheritance), but it relies on mathematical concepts.
In addition, the categories define test suites for their objects and elements. Hence, one also gets basic sanity tests for free.
How does this so-called category framework work?
Any category defines a base class for their objects ("parent class") and of the elements of their objects ("element class"). If the category is declared during initialisation of a parent, then the class of that parent is automatically dynamically changed into a sub-class of the category's parent class. Hence, it inherits additional methods. Note that dynamic classes do not work in Cython. Nevertheless, if one writes a parent in Cython, it still inherits the methods from the category: It is not by class inheritance but by virtue of a default implementation of __getattr__ that mimmicks the class inheritance.
So, it is strongly recommended to use the category framework both in Python and in Cython.
Let us see whether there is any gain in chosing the category of quotient fields instead of the category of fields:
So, there is no immediate gain for the parent, but there is more structure for the elements.
Category framework for the parent
Let us start by modifying the parent's initialisation, such that the correct category is chosen resp. the correct category can be provided by the user.
We demonstrate that by declaring the category, when constructing instances of MyFrac, their class is dynamically changed into a new class MyFrac_with_category. It is a common sub-class of MyFrac and of the category's parent class.
We can now demonstrate that P inherits additional methods. The base class Field does not have a method `sum`. But the parent class of the category of fields does have such method (in fact, it is defined for the category of commutative additive monoids), and it is available for P:
However, it does not work, yet, because some other stuff is not properly implemented:
Category framework for the elements
The basic idea remains the same: A Python class is dynamically changed into a sub-class of the element class of a category, and that behaviour is mimmicked for Cython classes as well. However, the category framework is invoked in a different way for elements than for parents.
One has to provide the parent with an attribute called "Element", whose value is the class that is used to implement all elements of that parent. Then, there is a :class:`~sage.misc.lazy_attribute.lazy_attribute` of the name "element_class", that automatically mixes the class provided by "Element" with the element class of the parent's category. Note that this holds if the parent class is written in Python. For parents written in Cython, lazy attributes will only be available if trac ticket #11115 is merged.
For providing our fraction fields with their own element classes, we just need to add a single line to our class:
That little change has dramatic consequences. We can now create elements by simply calling the parent, we can suddenly use a method zero_element, and the "sum" method works:
How did that happen?
Since we provided the attribute "Element", P has now also an attribute "element_class", that is a sub-class of both MyElement and of `P.category().element_class`:
The default __call__ method of a parent P simply passes the arguments to P.element_class, adding a named argument "parent=P". That is the reason for the choice of argument names in MyElement.__init__, and for their order.
In particular, elements obtained by calling P are instances of that new automatically created class.
That is the reason why we did not explicitly name the class in the arithmetic methods of MyElement. If we create one element by calling P (this is the case, e.g., for P.zero_element()), and add any other instance of MyElement to it, then the sum will also be an instance of P.element_class. Since P.zero_element() is an instance of P.element_class and since P.sum([...]) starts with P.zero_element(), we thus have:
We have already seen above that the element class of P.category() provides a method factor(). Let us try if it works:
It does! That may come as a surprise, since a is actually not an instance of P.element_class, and its class does not know about the factor method. But, as we have mentioned earlier, the __getattr__ method works around a missing class inheritance.
Note, however, that the access to the factor method is much faster if one has an actual instance of P.element_class:
Uniqueness of parents
In sage, all parents should be globally unique. That means: If two parents are equal then they should actually be the same objects - even if their definition looks different. For example:
That requirement is not met by our implementation, yet:
There are several tools in Sage to construct unique parents. See, for instance, :class:`sage.structure.factory.UniqueFactory`, which can be used for rather complicated cases, where very different input may result in the same objects.
Here, we have a simpler case, and we use Python, so that we can use :class:`sage.structure.unique_representation.UniqueRepresentation`. The simplemost usage would be to make MyFrac inherit first from UniqueRepresentation and then from sage.rings.field.Field.
However, as we have announced above, we want that our fraction fields test whether the given ring is a unique factorisation domain. Therefore, we want to preprocess the arguments before passing them to the __init__ method. That can be done in a __classcall__ method, that needs to be a static method.
Note that testing whether a ring is a unique factorisation domain requires trac ticket #9138 being merged - without that, even the ring of integers would not known as a unique factorisation domain (even though it is known as Euclidean domain). Anyway, we make our test depend on the variable is_9138_merged defined above; if the ticket is not merged, then we simply test if the input is a ring.
Now, uniqueness holds, and rings that are no unique factorisation domains are refused.
Note that Sage's tools for creating unique parents also take care of pickling (at least to some extent):
Coercion - the basics
Coercion is involved if one wants to be able to do arithmetic, comparisons, etc. between elements of distinct parents.
Theoretical background
Dissociation from type conversion
Perhaps the reader is familiar with the concept of coercion in the programming language C, which is more or less a synonyme for "automatic type conversion". A very basic example of an automatic type conversion is the sum of an integer with a floating point number: The integer is automatically converted into a floating point number, and then the summation takes place.
However, coercion in Sage is not about a change of types, but about a change of parents. Elements of the same type may have very different parents, such as here:
Every element of P2 can be naturally interpreted as an element of P1. So, it makes sense to be able to add elements of the two rings - the result should then live in P1:
It would be rather inconvenient if one needed to explicitly convert an element of P2 into P1 before adding. The coercion system does that conversion automatically.
Of course, one must not overdo the automatic conversion. There are situations in which a conversion is possible, but one would not want to use that conversion for arithmetics. For example, while every element of a finite prime field can be converted into an integer (by chosing a representative), one would certainly not want to add elements of GF(2) with elements of GF(3); in particular one would not want that the result is an integer.
Coercion versus conversion
A coercion happens implicitly, without being explicitly requested by the user. Hence, coercion must be based on mathematical rigour. The user may want to convert a finite field element into an integer, and can do so explicitly - but such conversion must never happen implicitly. We elaborate on the conditions that a conversion needs to satisfy in order to be eligible as a coercion.
A coercion is a map, a conversion is a partial map
Let P1 and P2 be two parents. It is possible that some elements of P1 can be converted into P2, but others can't. For example, a polynomial of degree zero over the integers can be interpreted as an integer - but there is no general conversion of a polynomial into an integer.
The first requirement is:
The coercion of elements of P1 into P2 must be defined for all elements of P1. There may be a conversion of some elements of P1 into P2, but if it is not globally defined, then it is no coercion.
Hence, coercion maps are defined on the level of parents, and they can be requested with the following methods:
A coercion is structure preserving
Any real number can be converted to an integer, namely by rounding. However, such a conversion is not useful in arithmetic operations:
The reason is that rounding real numbers is no ring homomorphism. So, the next requirement is:
Coercion maps are morphisms, i.e., they are structure preserving.
It depends on the parents which structure is to be preserved. For example, if one parent is a ring and the other parent is a field, then a coercion between the two must be a ring homomorphism. The coercion from the integers into the rational field, for instance, is a homomorphism of euclidean domains:
There is at most one coercion map between two parents
There are, in general, many different homomorphisms from a ring P1 to a ring P2. It is possible that none of them is used for coercion; however, it must never occur that two different coercions are simultaneously used.
Coercion maps can be composed
If there is a coercion φ from P1 to P2 and another coercion ψ from P2 to P3, then the composition of φ followed by ψ must yield a (the) coercion from P1 to P3.
The identity is a coercion
There is a coercion from any parent into itself, namely the identity map. Together with the two preceding requirements, it follows: If there are conversions from P1 to P2 and from P2 to P1, then they are mutually inverse.
How to fulfill the above requirements, and preserve common sense
As an illustration, we discuss here the rationale behind the choice of coercions between multivariate polynomial rings in Sage. Let R be a ring.
Obviously, there can be many ring homomorphisms between two polynomial rings over R. So, we have to fix a canonical choice. If the polynomial ring P2 has at least as many generators as P1, then one could map generator number n of P1 to generator number n of P2. Such "place preserving" conversions would certainly qualify as a coercion, since the composition of two place preserving conversions is a place preserving conversion.
However, common sense would would more likely take the names of the generators into account: When mapping R[x,y] to R[y,x], one would rather map x to x and y to y, not the first generator x of R[x,y] to the first generator y of R[y,x].
Sage tries to balance common sense and generality. If two polynomial rings have the same generators (but potentially in a different order), then there is a name preserving coercion:
However, if a name preserving map is not possible, then there is no coercion.
Assume that we would use a place preserving map from P3 to P1 for coercion. Then, the composition with the name preserving coercion from P1 to P2 must be a coercion, too. But that composition is not name preserving and is thus different from the name preserving coercion from P3 to P2 that we already chose:
By the requested uniqueness of coercions, a place preserving coercion from P3 to P1 is thus impossible.
One may use the place preserving map from P3 to P1 explicitly as a conversion, but it would never be used implicitly by Sage.
Implementing conversion
We return to our example: Fraction fields. We have already seen that we could implement various conversions by simply providing the attribute "Element": We can convert from the base ring into the fraction field. However, we can not convert elements of a fraction field into elements of another fraction field, yet.
Readers familiar with Python may assume that the conversion is implemented by overriding the __call__ method of a parent. However, the default __call__ method should never be overridden.
Instead, one should implement a method called _element_constructor_, that accepts arguments to be converted, perhaps accepts optional arguments, and returns an element of the parent. The returned element should be an instance of the parent's element class.
We test whether the given argument is an element of a fraction field by testing the category of its parent. If it is, then we can use numerator and denominator. If it has no parent or the parent is no fraction field, then we simply hope that our element class can deal with the input.
Note that we return to the old name of the class (MyFrac, not MyFracUnique), because otherwise an infinite recursion would occur in the __classcall__ method. But uniqueness is still granted.
In addition to the conversion from the base ring and from pairs of base ring elements, we now also have a conversion from the rationals to our fraction field of ZZ:
Establishing a coercion
We have a conversion from the base ring and even from the rational field to P. But it is not known as a coercion:
We could use P.register_coercion during initialisation (see documentation of that method) for declaring that there is a coercion from a ring to its fraction field. A more flexible way is to provide a method _coerce_map_from_ (with leading and trailing underscore). It accepts a parent as argument. If it returns an actual map, then this map is used for coercion. Otherwise, if it returns something that evaluates to "True", then conversion is used for coercion.
Note that we need a special case for the rational field, since QQ.base() is not the ring of integers.
By the method above, a parent coercing into the base ring will also coerce into the fraction field, and a fraction field coerces into another fraction field if there is a coercion of the corresponding base rings. Now, we have:
We can no use coercion from ZZ['x'] and from QQ into P for arithmetic operations between the two rings:
Equality and element containment
Recall that in above, the test "1 in P" returned False. Let us repeat the test now:
Why is that?
The default element containment test "x in P" is based on the interplay of three building blocks: conversion, coercion and equality test.
- Clearly, if the conversion P(x) raises an error, then x can not be seen as an element of P. On the other hand, a conversion P(x) can in general do very nasty things. So, the fact that P(x) works does not mean that x is in P.
- If x.parent() is P, then the conversion P(x) will not change x (at least, that's the default). Hence, we will have x==P(x). But how can we have x==P(x) if x.parent() is not P?
- Sage uses coercion not only for arithmetic operations, but also for comparison. Hence, if there is a coercion between the parent of x and P, then it will be applied. If there is a coercion from x.parent() to P then x==P(x) reduces to P(x)==P(x). Otherwise, x==P(x) will evaluate as false.
That leads to the following default implementation of element containment testing:
"x in P" holds if and only if "x==P(x)" does not raise an error and evaluates as true
If the user is not happy with that behaviour, the "magical" Python method __contains__ can be overridden.
Coercion - the advanced parts
So far, we are able to add integers and rational numbers to elements of our new implementation of the fraction field of ZZ.
Surprisingly, we can even add a polynomial over the integers to an element of P, even though the the result lives in a new parent, namely in a polynomial ring over P:
That positive surprise may make us confident enough to try another, seemingly more easy example. There obviously is a coercion from the fraction field of ZZ to the fraction field of ZZ['x']. However, Sage does not know enough about our new implementation of fraction fields. Hence, it does not recognise the coercion:
The aim of this section is to explain why and how a new ring was constructed when adding and element of P to an integral polynomial, and how we can establish a coercion from P to Frac(ZZ['x']).
Most parents can be constructed from simpler pieces. For example, the polynomial ring in variables x and y over the rational field can be obtained from the ring of integers by first applying the fraction field construction, then constructing a polynomial ring with generator x, and then constructing a polynomial ring with generator y (or: constructing a bivariate ring after the fraction field construction).
These constructions are functorial: The fraction field is a functor from the category of unique factorisation domains to the category of fields, and the construction of a polynomial ring with generator x is a functor from the category of rings into itself.
The advanced parts of Sage's coercion model are based on these functors, which are referred to as construction functors. If a parent is obtained from a simpler parent by applying a construction functor, then it should reveal it by a method `construction()`:
Note that construction functors do not necessarily commute: The polynomial ring over the fraction field of the integers is not the same as the fraction field of the polynomial ring over the integers.
Now, let P1 and P2 be two parents that are obtained from the same parent R by applying two different construction functors F1, F2.
It is often possible to combine F1 and F2 to a new construction functor F3, such that F3(R) is a new parent P3 which both P1 and P2 coerce into. In analogy to a notion of category theory, P3 is called the pushout of P1 and P2; and similarly F3 is called the pushout of F1 and F2.
Obviously, both F1*F2 and F2*F1 are natural candidates for the pushout of F1 and F2. But the pushout must not depend on the order in which F1 and F2 are provided. Hence, there must be a consistent choice.
Any construction functor has an attribute `rank`, and the convention is that if F1.rank is smaller than F2.rank, then the pushout is F2*F1 (hence, F1 is applied first, since the multiplication is in functorial notation). We have
and thus the pushout is
regardless of the order in which F1 and F2 are provided. That is why the sum of a rational number and a polynomial over the integers is a polynomial over the rationals, and not an element of the fraction field of the polynomials over the integers.
However, only "elementary" construction functors have a rank:
So, what do we do if P1 and P2 are obtained from R by two chains of construction functors?
The two functor chains will be shuffled: If the rank of the next unused functor F1 of the first chain is smaller (or greater) than the rank of the next unused functor F2 of the second chain, then F1 (or F2) is applied, and the next functor in the first (or second) chain is considered. If the ranks of F1 and F2 coincide, then we need another idea that is explained below.
As an illustration, we first get us some functors and then see how chains of functors are shuffled.
When we apply F1, F3, F2 and F1 to the ring of integers, we obtain
When we apply F4, F5 and F1 to the ring of integers, we obtain
When we shuffle F1,F3,F2,F1 with F4,F5,F2 according to the ranks, we start with F4 (second chain), since F4.rank<F1.rank. Then we proceed with with the complete first chain, since F1.rank, F3.rank and F2.rank are all smaller than F5.rank. We finish with the remaining functors of the second chain, F5 and F2.
So, we expect that the pushout of the above parents is obtained by applying F4, F1, F3, F2, F1, F5 and F2 to the ring of integers. That is indeed the case:
There remains the case that the next unused functor F1 of the first chain has the same rank as the next unused functor F2 of the second chain. Sage's pushout constructions offers two ways to proceed:
- Construction functors have a method `commutes()`. If F1.commutes(F2) or F2.commutes(F1) return True, then it is guaranteed that it does not matter in which order F1 and F2 are applied to any given parent R. So, we apply both F1 and F2, in any order.
- Construction functors have a method `merge()` that either returns None or returns a construction functor. By default, F1.merge(F2) is F1 if F1==F2, and is None otherwise. If F1.merge(F2) returns a functor F3, then F3 is applied, and both F1 and F2 are discarded.
We remark that the `commutes` method exists, but it seems that so far nobody has implemented two functors of the same rank that commute, although some functors of different ranks do commute:
The `merge` method, however, plays an important role. Typically it is used to provide coercion between different implementations of the same algebraic structure: For example, F1(R) may be the dense implementation of a polynomial ring and and F2(R) a sparse implementation. Then, F1.merge(F2) should be a functor F3, such that F3(R) is the same algebraic structure as F1(R) and F2(R), in a default implementation.
Here, we have two implementations of fraction fields, namely the one that already existed in Sage, and the new implementation that is the main example of our tutorial. We are now creating a construction functor `MyFracFunctor`, and merge it with the usual fraction field functor in such a way that the new functor becomes the default.
Since functors will only be merged if their ranks coincide, our new functor must have the same rank as the usual fraction field construction functor, namely 5. It is a functor from the category of unique factorization domains to the category of fields.
Note that since sage-4.7, the application of a functor to an object of a category should be implemented using the method `_apply_functor`. Do not override the default __call__ method!
However, at the time of writing this tutorial, the main sage notebook server was still using sage-4.6. In that version, MyFracFunctor would return none, which is a bug fixed in trac ticket #8800. Hence, we use a little work-around.
We verify that our functor can really be used to construct our implementation of fraction fields, and that it can be merged with either itself or the usual fraction field constructor:
There remains to let our new fraction fields know about the new construction functor:
Due to merging, we have:
Note that merging of functors really occurs here: There is no coercion from QQ['x'] to ZZ['x'].
The Test Suites
We have already mentioned that the category framework does not only provide functionality but also a test framework. The aim of this last section is to show how one can add more tests.
Parents or elements that belong to a certain category must provide certain methods, in order to smoothly blend with the methods that already exist in Sage. The methods that ought to be provided are called "abstract methods", and they can be required or optional. Let us see what methods are needed for quotient fields and their elements:
Hence, the only required method (that is actually required for all parents that belong to the category of sets) is an element containment test. That's fine, because the base class `sage.structure.parent.Parent` provides a default containment test.
The elements have to fulfill more:
Hence, the elements may have Sage's single underscore arithmetic methods (actually any ring element should have them).
Then, there are test methods defined for the parent or element class of a category. Their names start with "_test_". They test, for example, whether a parent P actually is an instance of the parent class of the category of P. Or, if the definition of category defines certain properties such as commutativity, then that property is tested. Or the existence of required abstract methods is tested.
Here are the tests that form the test suite of quotient fields:
Since we have implemented all abstract methods, we are confident that the test suite runs without complaining. In fact, it does!
Let us see what tests are actually performed:
As one can see, tests are also performed on elements. There are methods that return one element or a list of some elements, relying on "typical" elements that can be found in most algebraic structures".
Unfortunately, the list of elements that is returned by the default method is of length one, and that single element could also be a bit more interesting.
The method an_element relies on a method _an_element_, so, we implement that. We also override the some_elements method.
Now, as we have more interesting elements, we may also add a test for the "factor" method. Recall that the method was inherited from the category, but it appears that it is not tested. The tests that form the test suites should be implemented as a parent or element method of a category (and in addition, each method should have a documentation with tests, but that's a different topic).
Normally, a test for a method defined by a category should be provided by the same category. Hence, since `factor()` is defined in the category of quotient fields, a test should be added there. But we won't change source code here and will instead create a sub-category.
Apparently, the product of the factors returned be `e.factor()` should be equal to `e`. For forming the product, we use the `prod()` method, that, no surprise, is inherited from another category.
When we want to create a sub-category, we need to provide a method `super_categories`, that returns a list of all immediate super categories (here: category of quotient fields); it should be a cached method, for efficiency. The parent and element methods of a category are provided as methods of a class `ParentMethods` and `Element Methods`, as follows:
We provide an instance of our quotient field implementation with that new category.
The new test is inherited from the category. Since an_element() is returning a complicated element, _test_factorisation is a serious test.
Last, we observe that the new test has automatically become part of the test suite. We remark that the existing test became more serious as well, thanks to an_element() returning something more interesting.