How to implement new algebraic structures in Sage #

Sage’s category and coercion framework #

The aim of this tutorial is to explain how one can benefit from Sage’s category framework and coercion model when implementing new algebraic structures. It is based on a worksheet created in 2011.

We illustrate the concepts of Sage’s category framework and coercion model by means of a detailed example, namely a toy implementation of fraction fields. The code is developed step by step, so that the reader can focus on one detail in each part of this tutorial. The complete code can be found in the appendix.

Outline #

Use existing base classes

For using Sage’s coercion system, it is essential to work with sub--classes of sage.structure.parent.Parent or sage.structure.element.Element, respectively. They provide default implementations of many “magical” double-underscore Python methods, which must not be overridden. Instead, the actual implementation should be in single underscore methods, such as _add_ or _mul_.
Turn your parent structure into an object of a category

Declare the category during initialisation-–Your parent structure will inherit further useful methods and consistency tests.
Provide your parent structure with an element class

Assign to it an attribute called Element-–The elements will inherit further useful methods from the category. In addition, some basic conversions will immediately work.
Implement further conversions

Never override a parent’s __call__ method! Provide the method _element_constructor_ instead.
Declare coercions

If a conversion happens to be a morphism, you may consider to turn it into a coercion. It will then implicitly be used in arithmetic operations.
Advanced coercion: Define construction functors for your parent structure

Sage will automatically create new parents for you when needed, by the so--called sage.categories.pushout.pushout() construction.
Run the automatic test suites

Each method should be documented and provide a doc test (we are not giving examples here). In addition, any method defined for the objects or elements of a category should be supported by a test method, that is executed when running the test suite.

Appendix: The complete code #

# Importing base classes, ...
import sage
from sage.rings.ring import Field
from sage.structure.element import FieldElement
from sage.categories.category import Category
# ... the UniqueRepresentation tool,
from sage.structure.unique_representation import UniqueRepresentation
# ... some categories, and ...
from sage.categories.fields import Fields
from sage.categories.quotient_fields import QuotientFields
from sage.categories.integral_domains import IntegralDomains
# construction functors
from sage.categories.pushout import ConstructionFunctor

# Fraction field elements
class MyElement(FieldElement):
    def __init__(self, parent, n, d=None):
        if parent is None:
            raise ValueError("The parent must be provided")
        B = parent.base()
        if d is None:
            # The default denominator is one
            d = B.one()
        # verify that both numerator and denominator belong to the base
        if n not in B or d not in B:
            raise ValueError("Numerator and denominator must be elements of %s"%B)
        # Numerator and denominator should not just be "in" B,
        # but should be defined as elements of B
        d = B(d)
        n = B(n)
        # the denominator must not be zero
        if d==0:
            raise ZeroDivisionError("The denominator must not be zero")
        # normalize the denominator: WLOG, it shall be non-negative.
        if d<0:
            self.n = -n
            self.d = -d
        else:
            self.n = n
            self.d = d
        FieldElement.__init__(self,parent)

    # Methods required by the category of fraction fields:
    def numerator(self):
        return self.n
    def denominator(self):
        return self.d

    # String representation (single underscore!)
    def _repr_(self):
        return "(%s):(%s)"%(self.n,self.d)

    # Comparison: We can assume that both arguments are coerced
    # into the same parent, which is a fraction field. Hence, we
    # are allowed to use the denominator() and numerator() methods
    # on the second argument.
    def _richcmp_(self, other, op):
        from sage.structure.richcmp import richcmp
        return richcmp(self.n*other.denominator(), other.numerator()*self.d, op)

    # Arithmetic methods, single underscore. We can assume that both
    # arguments are coerced into the same parent.
    # We return instances of self.__class__, because self.__class__ will
    # eventually be a sub-class of MyElement.
    def _add_(self, other):
        C = self.__class__
        D = self.d*other.denominator()
        return C(self.parent(), self.n*other.denominator()+self.d*other.numerator(),D)
    def _sub_(self, other):
        C = self.__class__
        D = self.d*other.denominator()
        return C(self.parent(), self.n*other.denominator()-self.d*other.numerator(),D)
    def _mul_(self, other):
        C = self.__class__
        return C(self.parent(), self.n*other.numerator(), self.d*other.denominator())
    def _div_(self, other):
        C = self.__class__
        return C(self.parent(), self.n*other.denominator(), self.d*other.numerator())

# Inheritance from UniqueRepresentation implements the unique parent
# behaviour. Moreover, it implements pickling (provided that Python
# succeeds to look up the class definition).
class MyFrac(UniqueRepresentation, Field):
    # Implement the category framework for elements, which also
    # makes some basic conversions work.
    Element = MyElement

    # Allow to pass to a different category, by an optional argument
    def __init__(self, base, category=None):
        # Fraction fields only exist for integral domains
        if base not in IntegralDomains():
            raise ValueError("%s is no integral domain" % base)
        # Implement the category framework for the parent
        Field.__init__(self, base, category=category or QuotientFields())

    # Single-underscore method for string representation
    def _repr_(self):
        return "NewFrac(%s)"%repr(self.base())

    # Two methods that are implicitly used in some tests
    def base_ring(self):
        return self.base().base_ring()
    def characteristic(self):
        return self.base().characteristic()

    # Implement conversions. Do not override __call__!
    def _element_constructor_(self, *args, **kwds):
        if len(args)!=1:
           return self.element_class(self, *args, **kwds)
        x = args[0]
        try:
            P = x.parent()
        except AttributeError:
            return self.element_class(self, x, **kwds)
        if P in QuotientFields() and P != self.base():
            return self.element_class(self, x.numerator(), x.denominator(), **kwds)
        return self.element_class(self, x, **kwds)

    # Implement coercion from the base and from fraction fields
    # over a ring that coerces into the base
    def _coerce_map_from_(self, S):
        if self.base().has_coerce_map_from(S):
            return True
        if S in QuotientFields():
            if self.base().has_coerce_map_from(S.base()):
                return True
            if hasattr(S,'ring_of_integers') and self.base().has_coerce_map_from(S.ring_of_integers()):
                return True
    # Tell how this parent was constructed, in order to enable pushout constructions
    def construction(self):
        return MyFracFunctor(), self.base()

    # return some elements of this parent
    def _an_element_(self):
        a = self.base().an_element()
        b = self.base_ring().an_element()
        if (a+b)!=0:
            return self(a)**2/(self(a+b)**3)
        if b != 0:
            return self(a)/self(b)**2
        return self(a)**2*self(b)**3
    def some_elements(self):
        return [self.an_element(),self(self.base().an_element()),self(self.base_ring().an_element())]


# A construction functor for our implementation of fraction fields
class MyFracFunctor(ConstructionFunctor):
    # The rank is the same for Sage's original fraction field functor
    rank = 5
    def __init__(self):
        # The fraction field construction is a functor
        # from the category of integral domains into the category of
        # fields
        # NOTE: We could actually narrow the codomain and use the
        # category QuotientFields()
        ConstructionFunctor.__init__(self, IntegralDomains(), Fields())
    # Applying the functor to an object. Do not override __call__!
    def _apply_functor(self, R):
        return MyFrac(R)
    # Note: To apply the functor to morphisms, implement
    #       _apply_functor_to_morphism

    # Make sure that arithmetic involving elements of Frac(R) and
    # MyFrac(R) works and yields elements of MyFrac(R)
    def merge(self, other):
        if isinstance(other, (type(self), sage.categories.pushout.FractionField)):
            return self

# A quotient field category with additional tests.
# Notes:
# - Category inherits from UniqueRepresentation. Hence, there
#   is only one category for given arguments.
# - Since QuotientFieldsWithTest is a singleton (there is only
#   one instance of this class), we could inherit from
#   sage.categories.category_singleton.Category_singleton
#   rather than from sage.categories.category.Category
class QuotientFieldsWithTest(Category):
    # Our category is a sub-category of the category of quotient fields,
    # by means of the following method.
    def super_categories(self):
        return [QuotientFields()]

    # Here, we could implement methods that are available for
    # all objects in this category.
    class ParentMethods:
        pass

    # Here, we add a new test that is available for all elements
    # of any object in this category.
    class ElementMethods:
        def _test_factorisation(self, **options):
            P = self.parent()
            # The methods prod() and factor() are inherited from
            # some other categories.
            assert self == P.prod([P(b)**e for b,e in self.factor()])

How to implement new algebraic structures in Sage #

Sage’s category and coercion framework #

Outline #

Base classes #

The parent#

The elements#

Features and limitations of the basic implementation#

Categories in Sage #

Why should one choose a category?#

How does the category framework work?#

Implementing the category framework for the parent#

Implementing the category framework for the elements#

What did happen behind the scenes to make this work?#

A first note on performance#

Coercion-–the basics #

Theoretical background#

Coercion is not just type conversion#

Not every conversion is a coercion#

The four axioms requested for coercions#

Implementing a conversion#

Establishing a coercion#

Equality and element containment#

Coercion-–the advanced parts #

The pushout of construction functors#

Shuffling composite construction functors#

Breaking the tie#

Establishing a default implementation#

A second note on performance#

The test suites of the category framework #

“Abstract” methods#

The `_test_...` methods#

Implementing a new category with additional tests#