{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "from IPython.core.interactiveshell import InteractiveShell\n", "InteractiveShell.ast_node_interactivity = \"all\"\n", "%display default" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "$$\n", "\\def\\CC{\\bf C}\n", "\\def\\QQ{\\bf Q}\n", "\\def\\RR{\\bf R}\n", "\\def\\ZZ{\\bf Z}\n", "\\def\\NN{\\bf N}\n", "$$\n", "# How to implement new algebraic structures in Sage: Categories and coercion\n", "\n", "> *Simon King* *Friedrich-Schiller-Universität Jena* *E-mail: simon dot king at uni hyphen jena dot de* *© 2019*\n", "\n", "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.\n", "\n", "As an illustration, we implement fraction fields.\n", "\n", "## Outline\n", "\n", "#### Use existing base classes\n", "\n", "
There are sub-classes of sage.structure.parent.Parent resp. of sage.structure.element.Element that will help you a lot. Inheriting from these classes is essential for using Sage's coercion system.
\n", "\n", "Arithmetic operations should be implemented by *single underscore* methods, such as _add_, _mul_.
\n", "\n", "#### Turn your parent structure into an object of a category\n", "\n", "Declare the category during initialisation - Your parent structure will inherit further useful methods and consistency tests.
\n", "\n", "#### Provide your parent structure with an element class\n", "\n", "Assign to it an attribute called \"Element\" - The elements will inherit further useful methods from the category.
\n", "\n", "In addition, some basic conversions will immediately work.
\n", "\n", "#### Implement further conversions\n", "\n", "Never override a parent's __call__ method! Provide _element_constructor_ instead.
\n", "\n", "#### Declare coercions\n", "\n", "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.
\n", "\n", "#### Advanced coercion: Define construction functors for your parent structure\n", "\n", "Sage will automatically create new parents for you when needed, by some kind of \"pushout\" construction.
\n", "\n", "#### Run the automatic test suites\n", "\n", "Each method should be documented and provide a doc test (we are not giving examples here). In addition, any method defined for a category should be supported by a test method that is executed when running the test suite.
\n", "\n", "## Base classes\n", "\n", "In Sage, a \"Parent\" is an object of a category and contains elements.\n", "\n", "Parents should inherit from $sage.structure.parent.Parent$ and their elements from $sage.structure.element.Element$.\n", "\n", "Sage provides appropriate sub-classes of Parent and Element for a variety of more concrete algebraic structures, such as groups, rings, or fields, and of their elements.\n", "\n", "### The parent\n", "\n", "We want to implement a field, and we should thus start with the base class `sage.rings.field.Field`." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "from sage.rings.ring import Field" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "Let us compare the methods provided by that class with the methods provided by a general parent:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['__fraction_field',\n", " '__ideal_monoid',\n", " '__iter__',\n", " '__len__',\n", " '__pow__',\n", " '__rpow__',\n", " '__rtruediv__',\n", " '__rxor__',\n", " '__truediv__',\n", " '__xor__',\n", " '_an_element_impl',\n", " '_coerce_',\n", " '_coerce_c',\n", " '_coerce_impl',\n", " '_coerce_try',\n", " '_default_category',\n", " '_gens',\n", " '_ideal_class_',\n", " '_latex_names',\n", " '_list',\n", " '_one_element',\n", " '_pseudo_fraction_field',\n", " '_random_nonzero_element',\n", " '_unit_ideal',\n", " '_zero_element',\n", " '_zero_ideal',\n", " 'algebraic_closure',\n", " 'base_extend',\n", " 'class_group',\n", " 'coerce_map_from_c',\n", " 'content',\n", " 'derivation',\n", " 'derivation_module',\n", " 'divides',\n", " 'epsilon',\n", " 'extension',\n", " 'fraction_field',\n", " 'frobenius_endomorphism',\n", " 'gcd',\n", " 'gen',\n", " 'gens',\n", " 'has_coerce_map_from_c',\n", " 'ideal',\n", " 'ideal_monoid',\n", " 'integral_closure',\n", " 'is_commutative',\n", " 'is_field',\n", " 'is_integral_domain',\n", " 'is_integrally_closed',\n", " 'is_noetherian',\n", " 'is_prime_field',\n", " 'is_ring',\n", " 'is_subring',\n", " 'krull_dimension',\n", " 'ngens',\n", " 'one',\n", " 'order',\n", " 'prime_subfield',\n", " 'principal_ideal',\n", " 'quo',\n", " 'quotient',\n", " 'quotient_ring',\n", " 'random_element',\n", " 'unit_ideal',\n", " 'zero',\n", " 'zero_ideal',\n", " 'zeta',\n", " 'zeta_order']" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[p for p in dir(Field) if p not in dir(Parent)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Any ring in Sage has a **base** and a **base ring**.\n", "\n", "The \"usual\" fraction field of a ring R has the base R and the base ring R.base\\_ring() - we'll do the same:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(Univariate Polynomial Ring in x over Rational Field, Rational Field)" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Frac(QQ['x']).base(), Frac(QQ['x']).base_ring()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Declaring the base of a field\n", "Easy. Just pass it as an argument." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Univariate Polynomial Ring in x over Integer Ring" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Field(ZZ['x']).base()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Python uses double-underscore methods for arithemetic methods and string representations. Sage's base classes often have a default implementation.\n", "\n", "Hence, **implement SINGLE underscore methods \\_repr\\_, and similarly \\_add\\_, \\_mul\\_ etc.**\n", "\n", "You may consider to **make your parent \"unique\"** (parents should only evaluate equal if they are identical)\n", "\n", "Here, we also want to test whether the base is an integral domain (this is another use case of categories).\n", "\n", "Last, we add a base\\_ring method (as mentioned above) and a method that returns the characteristic of the field." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "class MyFrac(UniqueRepresentation, Field):\n", " def __init__(self, base):\n", " if base not in IntegralDomains():\n", " raise ValueError(\"%s is no integral domain\" % base)\n", " Field.__init__(self, base)\n", " def _repr_(self):\n", " return \"NewFrac(%s)\"%repr(self.base())\n", " def base_ring(self):\n", " return self.base().base_ring()\n", " def characteristic(self):\n", " return self.base().characteristic()" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "NewFrac(Univariate Polynomial Ring in x over Integer Ring)" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MyFrac(ZZ['x'])" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "ename": "ValueError", "evalue": "Ring of integers modulo 15 is no integral domain", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mValueError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\"x in P\" holds if and only if \"x==P(x)\" does not raise an error and evaluates as true
\n", "\n", "If the user is not happy with that behaviour, the \"magical\" Python method \\_\\_contains\\_\\_ can be overridden.\n", "\n", "## Coercion - the advanced parts\n", "\n", "So far, we are able to add integers and rational numbers to elements of our new implementation of the fraction field of ZZ." ] }, { "cell_type": "code", "execution_count": 68, "metadata": {}, "outputs": [], "source": [ "P = MyFrac(ZZ)" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(13):(6)" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1/2+P(2,3)+1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Surprisingly, we can even add a polynomial over the integers to an element of P, even though the **result lives in a new parent**, namely in a polynomial ring over P:" ] }, { "cell_type": "code", "execution_count": 70, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1):(1)*x + (1):(2)" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P(1/2) + ZZ['x'].gen()\n", "(P(1/2) + ZZ['x'].gen()).parent() is P['x']" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the next, seemingly more easy example, there \"obviously\" is a coercion from the fraction field of ZZ to the fraction field of ZZ\\[x\\].\n", "\n", "However, Sage does not know enough about our new implementation of fraction fields. Hence, it does not recognise the coercion:" ] }, { "cell_type": "code", "execution_count": 71, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Frac(ZZ['x']).has_coerce_map_from(P)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### How / why was the new ring was constructed above? How can we establish a coercion from P to Frac(ZZ\\[x\\]) ?\n", "\n", "Most parents can be constructed from simpler pieces. Parents are supposed to tell how they can be constructed:" ] }, { "cell_type": "code", "execution_count": 72, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(Poly[x], Rational Field)" ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(FractionField, Integer Ring)" ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Poly,R = QQ['x'].construction()\n", "Poly,R\n", "Fract,R = QQ.construction()\n", "Fract,R" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first return value is a *ConstructionFunctor* that yields the parent when applied to the second return value.\n", "Indeed, we have functors\n", "\n", "* Fract: IntegralDomains() $\\to$ FractionFields()\n", "* Poly\\[x\\]: Rings() $\\to$ Rings()\n", "\n", "In particular, the construction functors can be composed:" ] }, { "cell_type": "code", "execution_count": 73, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Poly(QQ) is QQ['x']\n", "Poly(ZZ) is ZZ['x']\n", "Poly(P) is P['x']" ] }, { "cell_type": "code", "execution_count": 74, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Poly[x](FractionField(...))" ] }, "execution_count": 74, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Poly*Fract" ] }, { "cell_type": "code", "execution_count": 75, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(Poly*Fract)(ZZ) is QQ['x']" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In addition, for a *ConstructionFunctor* it is assumed that there is a coercion from input to output:" ] }, { "cell_type": "code", "execution_count": 76, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Composite map:\n", " From: Integer Ring\n", " To: Univariate Polynomial Ring in x over Rational Field\n", " Defn: Natural morphism:\n", " From: Integer Ring\n", " To: Rational Field\n", " then\n", " Polynomial base injection morphism:\n", " From: Rational Field\n", " To: Univariate Polynomial Ring in x over Rational Field" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "((Poly*Fract)(ZZ))._coerce_map_from_(ZZ)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Construction functors do not necessarily commute:" ] }, { "cell_type": "code", "execution_count": 77, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Fraction Field of Univariate Polynomial Ring in x over Integer Ring" ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "Univariate Polynomial Ring in x over Rational Field" ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(Fract*Poly)(ZZ)\n", "(Poly*Fract)(ZZ)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Given:\n", "\n", "We have parents P1, P2, R and construction functors F1, F2, such that\n", "P1 = F1(R) and P2 = F2(R)
\n", "\n", "#### Wanted:\n", "\n", "Find new construction functor F3, such that both P1 and P2 coerce into P3=F3(R).
\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": 78, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Univariate Polynomial Ring in x over Rational Field" ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sage.categories.pushout import pushout\n", "pushout(Fract(ZZ),Poly(ZZ))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "F1\\*F2 and F2\\*F1 are natural candidates for the pushout of F1 and F2. However, the result must not depend on the order\n", "\n", "$\\Rightarrow$ We need a consistent choice of order: \"indecomposable\" construction functors have a **rank**.\n", "\n", "If F1.rank is smaller thanF2.rank, then the pushout is F2\\*F1 (hence, F1 is applied first).\n", "\n", "We have" ] }, { "cell_type": "code", "execution_count": 79, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(5, 9)" ] }, "execution_count": 79, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Fract.rank, Poly.rank" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "and thus the pushout is" ] }, { "cell_type": "code", "execution_count": 80, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(Poly[x](FractionField(...)), Poly[x](FractionField(...)))" ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Fract.pushout(Poly), Poly.pushout(Fract)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is why the example above has worked.\n", "\n", "However, only \"elementary\" construction functors have a rank:" ] }, { "cell_type": "code", "execution_count": 81, "metadata": {}, "outputs": [ { "ename": "AttributeError", "evalue": "'CompositeConstructionFunctor' object has no attribute 'rank'", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mAttributeError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m