{ "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\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mMyFrac\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mIntegers\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m15\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.pyx\u001b[0m in \u001b[0;36msage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1741)\u001b[1;34m()\u001b[0m\n\u001b[0;32m 333\u001b[0m \"\"\"\n\u001b[0;32m 334\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mcls\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mclasscall\u001b[0m \u001b[1;32mis\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mNone\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 335\u001b[1;33m \u001b[1;32mreturn\u001b[0m \u001b[0mcls\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mclasscall\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mcls\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m*\u001b[0m\u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0mkwds\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 336\u001b[0m \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 337\u001b[0m \u001b[1;31m# Fast version of type.__call__(cls, *args, **kwds)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/misc/cachefunc.pyx\u001b[0m in \u001b[0;36msage.misc.cachefunc.CachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:6017)\u001b[1;34m()\u001b[0m\n\u001b[0;32m 1000\u001b[0m \u001b[1;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mcache\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mk\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 1001\u001b[0m \u001b[1;32mexcept\u001b[0m \u001b[0mKeyError\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m-> 1002\u001b[1;33m \u001b[0mw\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mf\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m*\u001b[0m\u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0mkwds\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 1003\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mcache\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mk\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mw\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 1004\u001b[0m \u001b[1;32mreturn\u001b[0m \u001b[0mw\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/structure/unique_representation.pyc\u001b[0m in \u001b[0;36m__classcall__\u001b[1;34m(cls, *args, **options)\u001b[0m\n\u001b[0;32m 1025\u001b[0m \u001b[0mTrue\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 1026\u001b[0m \"\"\"\n\u001b[1;32m-> 1027\u001b[1;33m \u001b[0minstance\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mtypecall\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mcls\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m*\u001b[0m\u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0moptions\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 1028\u001b[0m \u001b[1;32massert\u001b[0m \u001b[0misinstance\u001b[0m\u001b[1;33m(\u001b[0m \u001b[0minstance\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mcls\u001b[0m \u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 1029\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0minstance\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m__class__\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m__reduce__\u001b[0m \u001b[1;33m==\u001b[0m \u001b[0mCachedRepresentation\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m__reduce__\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.pyx\u001b[0m in \u001b[0;36msage.misc.classcall_metaclass.typecall (build/cythonized/sage/misc/classcall_metaclass.c:2191)\u001b[1;34m()\u001b[0m\n\u001b[0;32m 504\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mArgument\u001b[0m \u001b[1;34m'cls'\u001b[0m \u001b[0mhas\u001b[0m \u001b[0mincorrect\u001b[0m \u001b[0mtype\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mexpected\u001b[0m \u001b[0mtype\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mgot\u001b[0m \u001b[0mclassobj\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 505\u001b[0m \"\"\"\n\u001b[1;32m--> 506\u001b[1;33m \u001b[1;32mreturn\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;33m<\u001b[0m\u001b[0mPyTypeObject\u001b[0m\u001b[1;33m*\u001b[0m\u001b[1;33m>\u001b[0m\u001b[0mtype\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mtp_call\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mcls\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mkwds\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 507\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 508\u001b[0m \u001b[1;31m# Class for timing::\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m\u001b[0m in \u001b[0;36m__init__\u001b[1;34m(self, base)\u001b[0m\n\u001b[0;32m 2\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0m__init__\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mbase\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 3\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mbase\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mIntegralDomains\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 4\u001b[1;33m \u001b[1;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"%s is no integral domain\"\u001b[0m \u001b[1;33m%\u001b[0m \u001b[0mbase\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 5\u001b[0m \u001b[0mField\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m__init__\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mbase\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 6\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0m_repr_\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mValueError\u001b[0m: Ring of integers modulo 15 is no integral domain" ] } ], "source": [ "MyFrac(Integers(15))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that UniqueRepresentation automatically provides pickling, at least to some extent." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "loads(dumps(MyFrac(ZZ))) is MyFrac(ZZ)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### The elements\n", "\n", "We use the base class sage.structure.element.FieldElement. Note that field elements do not require that their parent is a field:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Generic element of a structure" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sage.structure.element import FieldElement\n", "FieldElement(ZZ)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Implementation idea**\n", "\n", "* A fraction field element should have numerator and denominator in the base ring.
\n", " *Caveat:* We have numerator/denominator *methods* in Sage, while Python says it should be *properties*\n", "\n", "* The denominator must not be zero - by default, the denominator is one.\n", "\n", "* String representation via \\_repr\\_. **Do not override the default double underscore \\_\\_repr\\_\\_!**\n", "\n", "* Arithmetic via \\_add\\_, \\_mul\\_. **Do not override the default double underscore \\_\\_add\\_\\_, \\_\\_mul\\_\\_!**
Otherwise, you won't have coercion.\n", "\n", "In the single underscore methods and in \\_\\_cmp\\_\\_, you can always assume that **both arguments belong to the same parent**.\n", "\n", "Note the use of self.\\_\\_class\\_\\_ in the arithmetic methods. This is important, as later we will in fact work with *sub-classes* of MyElement. In order to make this notebook Python 3 compliant, we implement rich comparison." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "from sage.structure.richcmp import richcmp" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "class MyElement(FieldElement):\n", " def __init__(self, parent, n, d = None):\n", " B = parent.base()\n", " if d is None:\n", " d = B.one()\n", " if n not in B or d not in B:\n", " raise ValueError(\"Numerator and denominator must be elements of %s\"%B)\n", " # Numerator and denominator should not just be \"in\" B,\n", " # but should be defined as elements of B\n", " d = B(d)\n", " n = B(n)\n", " if d==0:\n", " raise ZeroDivisionError(\"The denominator must not be zero\")\n", " if d<0:\n", " self.n = -n\n", " self.d = -d\n", " else:\n", " self.n = n\n", " self.d = d\n", " FieldElement.__init__(self,parent)\n", " def numerator(self):\n", " return self.n\n", " def denominator(self):\n", " return self.d\n", " def _repr_(self):\n", " return \"(%s):(%s)\"%(self.n,self.d)\n", " def _richcmp_(self, other, op):\n", " return richcmp(self.n*other.denominator(), other.numerator()*self.d, op)\n", " def _add_(self, other):\n", " C = self.__class__\n", " D = self.d*other.denominator()\n", " return C(self.parent(), self.n*other.denominator()+self.d*other.numerator(), D)\n", " def _sub_(self, other):\n", " C = self.__class__\n", " D = self.d*other.denominator()\n", " return C(self.parent(), self.n*other.denominator()-self.d*other.numerator(),D)\n", " def _mul_(self, other):\n", " C = self.__class__\n", " return C(self.parent(), self.n*other.numerator(), self.d*other.denominator())\n", " def _div_(self, other):\n", " C = self.__class__\n", " return C(self.parent(), self.n*other.denominator(), self.d*other.numerator())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Thanks to the single underscore methods, some basic arithmetics works, **if** we stay inside our parent structure:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "P = MyFrac(ZZ)\n", "a = MyElement(P, 3,4)\n", "b = MyElement(P, 1,2)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "((10):(8), (2):(8), (3):(8), (6):(4))" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a+b, a-b, a*b, a/b" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a-b == MyElement(P, 1,4)\n", "a-b < a*b" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We didn't implement exponentiation - but it just works:" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(27):(64)" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a**3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There is a default implementation of element tests. We can already do" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a in P" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "since a is defined as an element of P.\n", "\n", "But we can not verify yet that the integers are contained in the fraction field of the ring of integers:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "ename": "NotImplementedError", "evalue": "cannot construct elements of NewFrac(Integer Ring)", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mP\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/structure/parent.pyx\u001b[0m in \u001b[0;36msage.structure.parent.Parent.__contains__ (build/cythonized/sage/structure/parent.c:9863)\u001b[1;34m()\u001b[0m\n\u001b[0;32m 1090\u001b[0m \u001b[1;32mreturn\u001b[0m \u001b[0mTrue\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 1091\u001b[0m \u001b[1;32mtry\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m-> 1092\u001b[1;33m \u001b[0mx2\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 1093\u001b[0m \u001b[0mEQ\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mx2\u001b[0m \u001b[1;33m==\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 1094\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mEQ\u001b[0m \u001b[1;32mis\u001b[0m \u001b[0mTrue\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/structure/parent.pyx\u001b[0m in \u001b[0;36msage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:8952)\u001b[1;34m()\u001b[0m\n\u001b[0;32m 879\u001b[0m \"\"\"\n\u001b[0;32m 880\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_element_constructor\u001b[0m \u001b[1;32mis\u001b[0m \u001b[0mNone\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 881\u001b[1;33m \u001b[1;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mf\u001b[0m\u001b[1;34m\"cannot construct elements of {self}\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 882\u001b[0m \u001b[0mcdef\u001b[0m \u001b[0mPy_ssize_t\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 883\u001b[0m \u001b[0mcdef\u001b[0m \u001b[0mR\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mparent\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mNotImplementedError\u001b[0m: cannot construct elements of NewFrac(Integer Ring)" ] } ], "source": [ "1 in P" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Unfortunately the error message isn't exactly helpful. Anyway, we will implement that later.\n", "\n", "## Chosing a category\n", "\n", "Sometimes the base classes do not reflect the mathematics:\n", "\n", "The set of $m\\times n$ matrices over a field forms, in general, not more than a vector space. Hence, they are not implemented on top of sage.rings.ring.Ring.\n", "\n", "However, if $m=n$ then the matrix space is an algebra, thus, in particular is a ring. From the point of view of Python classes, both are the same:" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MS1 = MatrixSpace(QQ,2,3)\n", "isinstance(MS1, Ring)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MS2 = MatrixSpace(QQ,2)\n", "isinstance(MS2, Ring)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Sage's category framework can differentiate the two cases:" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Category of rings" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Rings()" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MS1 in Rings()" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MS2 in Rings()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Surprisingly, MS2 has *more* methods than MS1:" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "81" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import inspect\n", "len([s for s in dir(MS1) if inspect.ismethod(getattr(MS1,s,None))])" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "119" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len([s for s in dir(MS2) if inspect.ismethod(getattr(MS2,s,None))])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the past, it used to be the case that the classes of MS1 and MS2 are the same. This has changed:" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MS1.__class__ is MS2.__class__" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Category of fields" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.category()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "However, we will choose a smaller category, namely the category of quotient fields.\n", "\n", "### Why should one choose a category?\n", "\n", "One can provide default **methods** ***for all objects*** of a category , and ***for all elements*** of such objects. Hence:\n", "\n", "* It is an alternative way of inheriting useful stuff.\n", "\n", "* It does not rely on implementation details, but on mathematical concepts.\n", "\n", "* In addition, the categories define **test suites** for their objects and elements. Hence, one also gets basic sanity tests for free.\n", "\n", "How does this so-called *category framework* work?\n", "\n", "* Abstract base classes for the objects (\"parent\\_class\") and the elements of objects (\"element\\_class\") are provided by attributes of the category.\n", "\n", "* At initialisation of a parent, the class of the parent is *dynamically changed* into a sub-class of the category's parent class.\n", "\n", "* The parent is also provided with a sub-class of the category's element class (see below).\n", "\n", "Dynamic change of classes does not work in Cython. Nevertheless, method inheritance still works, by virtue of a \\_\\_getattr\\_\\_ method.\n", "\n", "**$\\Rightarrow$ It is strongly recommended to use the category framework both in Python and in Cython.**\n", "\n", "Let us see whether there is any gain in chosing the category of quotient fields instead of the category of fields:" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "QuotientFields().parent_class\n", "QuotientFields().element_class" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[]" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[p for p in dir(QuotientFields().parent_class) if p not in dir(Fields().parent_class)]" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['_derivative',\n", " 'denominator',\n", " 'derivative',\n", " 'numerator',\n", " 'partial_fraction_decomposition']" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[p for p in dir(QuotientFields().element_class) if p not in dir(Fields().element_class)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So, there is no immediate gain for the parent, but there useful default implementations of methods for the elements.\n", "\n", "### Category framework for the parent\n", "\n", "Declare the correct category by an optional argument of the field constructor:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from sage.categories.quotient_fields import QuotientFields\n", "Category.join([QuotientFields(), FiniteSets()])" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "class MyFrac(MyFrac):\n", " def __init__(self, base, category=None):\n", " if base not in IntegralDomains():\n", " raise ValueError(\"%s is no integral domain\"%base)\n", " Field.__init__(self, base, \n", " category=Category.join([category, QuotientFields()]) if category else QuotientFields())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "When constructing instances of MyFrac, their class is dynamically changed into a new class MyFrac\\_with\\_category.\n", "\n", "It is a common sub-class of MyFrac and of the category's parent class." ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "Category of quotient fields" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P = MyFrac(ZZ)\n", "type(P)\n", "P.category()\n", "isinstance(P,MyFrac)\n", "isinstance(P,QuotientFields().parent_class)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "P inherits additional methods:\n", "\n", "The base class `Field` does not have a method `sum`. But P inherits such method from the category of commutative additive monoids" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'sage.categories.additive_monoids'" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.sum.__module__" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "However, it does not work, yet, because it relies on some other stuff that we will implement later:" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "ename": "NotImplementedError", "evalue": "cannot construct elements of NewFrac(Integer Ring)", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[0;32m 2\u001b[0m \u001b[0mb\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mMyElement\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mP\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 3\u001b[0m \u001b[0mc\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mMyElement\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mP\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m-\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 4\u001b[1;33m \u001b[0mP\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0msum\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mc\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/categories/additive_monoids.pyc\u001b[0m in \u001b[0;36msum\u001b[1;34m(self, args)\u001b[0m\n\u001b[0;32m 69\u001b[0m \u001b[0mTrue\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 70\u001b[0m \"\"\"\n\u001b[1;32m---> 71\u001b[1;33m \u001b[1;32mreturn\u001b[0m \u001b[0msum\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mzero\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 72\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 73\u001b[0m \u001b[1;32mclass\u001b[0m \u001b[0mHomsets\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mHomsetsCategory\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/rings/ring.pyx\u001b[0m in \u001b[0;36msage.rings.ring.Ring.zero (build/cythonized/sage/rings/ring.c:7330)\u001b[1;34m()\u001b[0m\n\u001b[0;32m 727\u001b[0m \"\"\"\n\u001b[0;32m 728\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_zero_element\u001b[0m \u001b[1;32mis\u001b[0m \u001b[0mNone\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 729\u001b[1;33m \u001b[0mx\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 730\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_zero_element\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 731\u001b[0m \u001b[1;32mreturn\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/structure/parent.pyx\u001b[0m in \u001b[0;36msage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:8952)\u001b[1;34m()\u001b[0m\n\u001b[0;32m 879\u001b[0m \"\"\"\n\u001b[0;32m 880\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_element_constructor\u001b[0m \u001b[1;32mis\u001b[0m \u001b[0mNone\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 881\u001b[1;33m \u001b[1;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mf\u001b[0m\u001b[1;34m\"cannot construct elements of {self}\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 882\u001b[0m \u001b[0mcdef\u001b[0m \u001b[0mPy_ssize_t\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 883\u001b[0m \u001b[0mcdef\u001b[0m \u001b[0mR\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mparent\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mNotImplementedError\u001b[0m: cannot construct elements of NewFrac(Integer Ring)" ] } ], "source": [ "a = MyElement(P, 3,4)\n", "b = MyElement(P, 1,2)\n", "c = MyElement(P, -1,2)\n", "P.sum([a,b,c])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Category framework for the elements\n", "\n", "Again, the class is dynamically changed into a sub-class of the element class of a category (Cython mimmicks that by a `__getattr__` method)\n", "\n", "However, the category framework is invoked in a different way for elements than for parents.\n", "\n", "* Provide the parent P (or its class) with an attribute \"**P.Element**\", whose value is a class.\n", "\n", "* The parent\\**automatically*\\* obtains an attribute \"**P.element\\_class**\", that subclasses both P.Element with P.category().element\\_class.\n", "\n", "**For providing our fraction fields with their own element classes, we just need to add a single line to our class:**" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [], "source": [ "class MyFrac(MyFrac):\n", " Element = MyElement" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That little change means:\n", "\n", "* We can now create elements by simply calling the parent\n", "* We can suddenly use a method zero\\_element\n", "* The \"sum\" method works" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "((1):(1), (2):(3))" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P = MyFrac(ZZ)\n", "P(1), P(2,3)" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0):(1)" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.zero()" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a = MyElement(P, 9,4)\n", "b = MyElement(P, 1,2)\n", "c = MyElement(P, -1,2)\n", "type(P.sum([a,b,c]))" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(sum([a,b,c]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### How did that happen?\n", "\n", "We provided \"P.Element\", and thus benefit from the lazy attribute \"P.element\\_class\".\n", "\n", "It provides another dynamic class, a sub-class of both MyElement and of `P.category().element_class` :" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.__class__.element_class" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.element_class\n", "type(P.element_class)" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "issubclass(P.element_class, MyElement)\n", "issubclass(P.element_class,P.category().element_class)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The **default \\_\\_call\\_\\_ method** of P passes the arguments to P.element\\_class, adding the argument \"parent=P\".\n", "\n", "In particular, elements obtained by calling P are instances of that new automatically created class." ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(P(2,3))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note: For that reason, we used `self.__class__` in the arithmetic methods of MyElement.\n", "\n", "`P.zero_element()` merely does `P(0)` and thus returns an instance of `P.element_class`. Since `P.sum([...])` starts with `P.zero_element()`, we have:" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "False" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(a)\n", "isinstance(a,P.element_class)\n", "type(P.sum([a,b,c]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The method **factor()** inherited from P.category().element\\_class (see above) simply works:" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(9):(4)" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "2^-2 * 3^2" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "2^-1 * 3" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a\n", "a.factor()\n", "P(6,4).factor()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That's surprising: The element \"a\" is just an instance of MyElement, not of P.element\\_class, and its class does not know about the factor method.\n", "\n", "In fact, we see the above-mentioned \\_\\_getattr\\_\\_ at work." ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hasattr(type(a), 'factor')\n", "hasattr(P.element_class, 'factor')\n", "hasattr(a, 'factor')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Need for speed\n", "\n", "The category framework is sometimes blamed for speed regressions (see \\#9138 versus \\#11900).\n", "\n", "But if categories are **used properly, it is fast**:" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1000 loops, best of 3: 615 ns per loop" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('a.factor',number=1000)\n", "type(a) # Here, the category framework is NOT properly used" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a2 = P(9,4) # Here, it IS properly used\n", "a2 == a" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1000 loops, best of 3: 211 ns per loop" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit('a2.factor',number=1000); type(a2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So, *don't be afraid of using categories...*\n", "\n", "## Coercion - the basics\n", "\n", "> *Coercion is involved if one wants to be able to do arithmetic, comparisons, etc. between elements of distinct parents.*\n", "\n", "### Theoretical background\n", "\n", "#### Dissociation from *type conversion*\n", "\n", "* In C: \"coercion\" means \"automatic type conversion\".\n", "* In Sage: **Coercion is not about a change of types, but about a change of parents.**\n", "\n", "Elements of the same type may have very different parents, such as here:" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [], "source": [ "P1 = QQ['v,w']; P2 = ZZ['w,v']" ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "False" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(P1.gen()) == type(P2.gen())\n", "P1 == P2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "P2 naturally is a sub-ring of P1. So, it makes sense to be able to add elements of the two rings - the result should then live in P1:" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(P1.gen()+P2.gen()).parent() is P1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.\n", "\n", "#### Coercion versus conversion\n", "\n", "A coercion happens implicitly, without being explicitly requested by the user.\n", "\n", "Hence, coercion must be based on mathematical rigour.\n", "\n", "##### 1. A coercion is a map, a conversion may be a *partial* map\n", "\n", "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. So, that must not be a coercion.\n", "\n", "Hence, coercion maps are defined on the level of parents, and they can be requested with the following methods:" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P1.has_coerce_map_from(P2)" ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Coercion map:\n", " From: Multivariate Polynomial Ring in w, v over Integer Ring\n", " To: Multivariate Polynomial Ring in v, w over Rational Field" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P1.coerce_map_from(P2)" ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P2.has_coerce_map_from(P1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### 2. A coercion is a morphism, i.e., structure preserving\n", "\n", "Any real number can be converted to an integer, namely by rounding. However, such a conversion is not useful in arithmetic operations:" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "int(1.6)+int(2.7) == int(1.6+2.7)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It depends on the parents which structure is to be preserved. For example, the coercion from the integers into the rational field is a homomorphism of euclidean domains:" ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Category of homsets of euclidean domains and metric spaces" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "QQ.coerce_map_from(ZZ).category()" ] }, { "cell_type": "code", "execution_count": 58, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Join of Category of euclidean domains and Category of infinite sets and Category of metric spaces" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "QQ.coerce_map_from(ZZ).category_for()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### 3. If a coercion exists, it has to be unique\n", "\n", "In addition, if there is a coercion from P1 to P2 and x is an element of P1, then the conversion P2(x) has to coincide with the coercion of x into P2.\n", "\n", "##### 4. Coercions can be composed\n", "\n", "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.\n", "\n", "##### 5. The identity is a coercion\n", "\n", "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.\n", "\n", "### Implementing conversion\n", "\n", "We implement some conversions into our fraction fields by simply providing the attribute \"Element\".\n", "\n", "However, we can not convert elements of a fraction field into elements of another fraction field, yet:" ] }, { "cell_type": "code", "execution_count": 59, "metadata": {}, "outputs": [ { "ename": "ValueError", "evalue": "Numerator and denominator must be elements of Integer Ring", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mValueError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mP\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m/\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/structure/parent.pyx\u001b[0m in \u001b[0;36msage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9197)\u001b[1;34m()\u001b[0m\n\u001b[0;32m 898\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mmor\u001b[0m \u001b[1;32mis\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mNone\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 899\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mno_extra_args\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 900\u001b[1;33m \u001b[1;32mreturn\u001b[0m \u001b[0mmor\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_call_\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 901\u001b[0m \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 902\u001b[0m \u001b[1;32mreturn\u001b[0m \u001b[0mmor\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_call_with_args\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mkwds\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/structure/coerce_maps.pyx\u001b[0m in \u001b[0;36msage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4556)\u001b[1;34m()\u001b[0m\n\u001b[0;32m 160\u001b[0m \u001b[1;32mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mtype\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mC\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mC\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 161\u001b[0m \u001b[1;32mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mtype\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mC\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_element_constructor\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mC\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_element_constructor\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 162\u001b[1;33m \u001b[1;32mraise\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 163\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 164\u001b[0m \u001b[0mcpdef\u001b[0m \u001b[0mElement\u001b[0m \u001b[0m_call_with_args\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0margs\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mkwds\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;33m{\u001b[0m\u001b[1;33m}\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/structure/coerce_maps.pyx\u001b[0m in \u001b[0;36msage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4448)\u001b[1;34m()\u001b[0m\n\u001b[0;32m 155\u001b[0m \u001b[0mcdef\u001b[0m \u001b[0mParent\u001b[0m \u001b[0mC\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_codomain\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 156\u001b[0m \u001b[1;32mtry\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 157\u001b[1;33m \u001b[1;32mreturn\u001b[0m \u001b[0mC\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_element_constructor\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 158\u001b[0m \u001b[1;32mexcept\u001b[0m \u001b[0mException\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 159\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mprint_warnings\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/categories/sets_cat.pyc\u001b[0m in \u001b[0;36m_element_constructor_from_element_class\u001b[1;34m(self, *args, **keywords)\u001b[0m\n\u001b[0;32m 992\u001b[0m \u001b[1;33m<\u001b[0m\u001b[1;32mclass\u001b[0m \u001b[1;34m'sage.categories.examples.sets_cat.PrimeNumbers_Inherits_with_category.element_class'\u001b[0m\u001b[1;33m>\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 993\u001b[0m \"\"\"\n\u001b[1;32m--> 994\u001b[1;33m \u001b[1;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0melement_class\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m*\u001b[0m\u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0mkeywords\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 995\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 996\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mis_parent_of\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0melement\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;32m\u001b[0m in \u001b[0;36m__init__\u001b[1;34m(self, parent, n, d)\u001b[0m\n\u001b[0;32m 5\u001b[0m \u001b[0md\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mB\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mone\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 6\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mB\u001b[0m \u001b[1;32mor\u001b[0m \u001b[0md\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mB\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m \u001b[1;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"Numerator and denominator must be elements of %s\"\u001b[0m\u001b[1;33m%\u001b[0m\u001b[0mB\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 8\u001b[0m \u001b[1;31m# Numerator and denominator should not just be \"in\" B,\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 9\u001b[0m \u001b[1;31m# but should be defined as elements of B\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mValueError\u001b[0m: Numerator and denominator must be elements of Integer Ring" ] } ], "source": [ "P(2/3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For implementing a conversion, **the default \\_\\_call\\_\\_ method should (almost) never be overridden.**Again, some old parents violate that rule - please help to refactor them!\n", "\n", "Instead, **implement the method \\_element\\_constructor\\_**, that should return an instance of the parent's element class." ] }, { "cell_type": "code", "execution_count": 60, "metadata": {}, "outputs": [], "source": [ "class MyFrac(MyFrac):\n", " def _element_constructor_(self, *args,**kwds):\n", " if len(args)!=1:\n", " return self.element_class(self, *args, **kwds)\n", " x = args[0]\n", " try:\n", " P = x.parent()\n", " except AttributeError:\n", " return self.element_class(self, x, **kwds)\n", " if P in QuotientFields() and P != self.base():\n", " return self.element_class(self, x.numerator(), x.denominator(), **kwds)\n", " return self.element_class(self, x, **kwds)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 61, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "((2):(1), (2):(3), (3):(4))" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P = MyFrac(ZZ)\n", "P(2), P(2,3), P(3/4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Recall that above, the test \"1 in P\" failed with an error. Since we can now convert the integer 1 into P, the error has vanished. But there is still a negative outcome:" ] }, { "cell_type": "code", "execution_count": 62, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 in P" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The technical reason: We have a conversion P(1) of 1 into P, but this is not a coercion." ] }, { "cell_type": "code", "execution_count": 63, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "False" ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.has_coerce_map_from(ZZ)\n", "P.has_coerce_map_from(QQ)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Establishing a coercion\n", "\n", "- We *could* use P.register\\_coercion during initialisation (see documentation of that method).\n", "- More flexible: Provide a method \\_coerce\\_map\\_from\\_\n", "\n", "\\_coerce\\_map\\_from\\_ accepts a parent as argument. If it returns \"True\", then conversion is used for coercion (but it may return an actual map).\n", "\n", "Note that we need a special case for the rational field, since QQ.base() is not the ring of integers." ] }, { "cell_type": "code", "execution_count": 64, "metadata": {}, "outputs": [], "source": [ "class MyFrac(MyFrac):\n", " def _coerce_map_from_(self, S):\n", " if self.base().has_coerce_map_from(S):\n", " return True\n", " if S in QuotientFields():\n", " if self.base().has_coerce_map_from(S.base()):\n", " return True\n", " if hasattr(S,'ring_of_integers') and self.base().has_coerce_map_from(S.ring_of_integers()):\n", " return True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 65, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P = MyFrac(QQ['x'])\n", "P.has_coerce_map_from(ZZ['x'])\n", "P.has_coerce_map_from(Frac(ZZ['x']))\n", "P.has_coerce_map_from(QQ)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can now use coercion from ZZ\\['x'\\] and from QQ into P for arithmetic operations between the two rings:" ] }, { "cell_type": "code", "execution_count": 66, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(4*x + 11):(4)" ] }, "execution_count": 66, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 66, "metadata": {}, "output_type": "execute_result" } ], "source": [ "3/4+P(2)+ZZ['x'].gen()\n", "(P(2)+ZZ['x'].gen()).parent() is P" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Equality and element containment\n", "\n", "Recall that above, the test \"1 in P\" had a negative outcome. Let us repeat the test now:" ] }, { "cell_type": "code", "execution_count": 67, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 67, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 in P" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Why is that?\n", "\n", "The default element containment test \"x in P\" is based on the interplay of three building blocks: conversion, coercion and equality test.\n", "\n", "1. 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.\n", "2. 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).\n", "3. 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.\n", "\n", "That leads to the following **default implementation of element containment testing**:\n", "\n", "

\"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\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;33m(\u001b[0m\u001b[0mFract\u001b[0m\u001b[1;33m*\u001b[0m\u001b[0mPoly\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mrank\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;31mAttributeError\u001b[0m: 'CompositeConstructionFunctor' object has no attribute 'rank'" ] } ], "source": [ "(Fract*Poly).rank" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**What do we do with two *chains* of construction functors?**\n", "\n", "Shuffle the functors from the two chains (F1,F2,...) and (G1,G2,...):\n", "\n", "* If F1.rank < G1.rank: Apply F1, and proceed with (F2,F3,...) and (G1,G2,...).\n", "* If F1.rank > G1.rank: Apply G1, and proceed with (F1,F2,...) and (G2,G3,...).\n", "* If F1.rank == G1.rank, then we need other techniques (see below).\n", "\n", "As an illustration, we first get us some functors and then see how chains of functors are shuffled." ] }, { "cell_type": "code", "execution_count": 82, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "AlgebraicClosureFunctor" ] }, "execution_count": 82, "metadata": {}, "output_type": "execute_result" } ], "source": [ "AlgClos, R = CC.construction(); AlgClos" ] }, { "cell_type": "code", "execution_count": 83, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Completion[+Infinity, prec=53]" ] }, "execution_count": 83, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Compl, R = RR.construction(); Compl" ] }, { "cell_type": "code", "execution_count": 84, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "MatrixFunctor" ] }, "execution_count": 84, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Matr, R = (MatrixSpace(ZZ,3)).construction(); Matr" ] }, { "cell_type": "code", "execution_count": 85, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(3, 4, 5, 9, 10)" ] }, "execution_count": 85, "metadata": {}, "output_type": "execute_result" } ], "source": [ "AlgClos.rank, Compl.rank, Fract.rank, Poly.rank, Matr.rank" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "When we apply Fract, AlgClos, Poly and Fract to the ring of integers, we obtain" ] }, { "cell_type": "code", "execution_count": 86, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Fraction Field of Univariate Polynomial Ring in x over Algebraic Field" ] }, "execution_count": 86, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(Fract*Poly*AlgClos*Fract)(ZZ)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "When we apply Compl, Matr and Poly to the ring of integers, we obtain" ] }, { "cell_type": "code", "execution_count": 87, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Univariate Polynomial Ring in x over Full MatrixSpace of 3 by 3 dense matrices over Integer Ring" ] }, "execution_count": 87, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(Poly*Matr*Compl)(ZZ)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Applying the shuffling procedure yields" ] }, { "cell_type": "code", "execution_count": 88, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Univariate Polynomial Ring in x over Full MatrixSpace of 3 by 3 dense matrices over Fraction Field of Univariate Polynomial Ring in x over Algebraic Field" ] }, "execution_count": 88, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(Poly*Matr*Fract*Poly*AlgClos*Fract*Compl)(ZZ)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "and this is indeed equal to the pushout found by Sage:" ] }, { "cell_type": "code", "execution_count": 89, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Univariate Polynomial Ring in x over Full MatrixSpace of 3 by 3 dense matrices over Fraction Field of Univariate Polynomial Ring in x over Algebraic Field" ] }, "execution_count": 89, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pushout((Fract*Poly*AlgClos*Fract)(ZZ), (Poly*Matr*Compl)(ZZ))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### The case F1.rank==G1.rank\n", "\n", "Sage's pushout constructions offers two ways to proceed:\n", "\n", "1. Construction functors have a method `merge()` that either returns None or returns a construction functor. If either F1.merge(G1) or G1.merge(F1) return a functor H1, then apply H1 and proceed with (F2,F3,...) and (G2,G3,...).\n", "2. Construction functors have a method `commutes()`. If F1.commutes(G1) or G1.commutes(F1) returns True, then apply both F1 and G1 in any order, and proceed with (F2,F3,...) and (G2,G3,...).\n", "\n", "By default, F1.merge(G1) returns F1 if F1==G1, and returns None otherwise.\n", "\n", "The `commutes()` method exists, but it seems that so far nobody has implemented two functors of the same rank that commute.\n", "\n", "### A use case of ` merge()`\n", "\n", "#### Provide coercion between different implementations of the same algebraic structure\n", "\n", "If F1(P) and F2(P) are different implementations of the same thing, then F1.merge(F2)(P) should be the default implementation of that thing.\n", "\n", "Here:\n", "\n", "- Implement an alternative to the \"usual\" fraction field functor, having the same rank, but returning our new implementation.\n", "- Make our new implementation the default, by providing a merge method.\n", "\n", "Remark:\n", "\n", "- **Do not override the default \\_\\_call\\_\\_ method** -- implement `_apply_functor` instead.\n", "- Declare **domain** and **codomain** of the functor." ] }, { "cell_type": "code", "execution_count": 90, "metadata": {}, "outputs": [], "source": [ "from sage.categories.pushout import ConstructionFunctor\n", "class MyFracFunctor(ConstructionFunctor):\n", " rank = 5\n", " def __init__(self):\n", " ConstructionFunctor.__init__(self, IntegralDomains(), Fields())\n", " def _apply_functor(self, R):\n", " return MyFrac(R)\n", " def merge(self, other):\n", " if isinstance(other, (type(self), sage.categories.pushout.FractionField)):\n", " return self" ] }, { "cell_type": "code", "execution_count": 91, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "MyFracFunctor" ] }, "execution_count": 91, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MyFracFunctor()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 92, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "NewFrac(Integer Ring)" ] }, "execution_count": 92, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MyFracFunctor()(ZZ)" ] }, { "cell_type": "code", "execution_count": 93, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "MyFracFunctor" ] }, "execution_count": 93, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MyFracFunctor().merge(MyFracFunctor())" ] }, { "cell_type": "code", "execution_count": 94, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "MyFracFunctor" ] }, "execution_count": 94, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MyFracFunctor().merge(Fract)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There remains to let our new fraction fields know about the new construction functor:" ] }, { "cell_type": "code", "execution_count": 95, "metadata": {}, "outputs": [], "source": [ "class MyFrac(MyFrac):\n", " def construction(self):\n", " return MyFracFunctor(), self.base()" ] }, { "cell_type": "code", "execution_count": 96, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(MyFracFunctor, Univariate Polynomial Ring in x over Integer Ring)" ] }, "execution_count": 96, "metadata": {}, "output_type": "execute_result" } ], "source": [ "MyFrac(ZZ['x']).construction()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Due to merging, we have:" ] }, { "cell_type": "code", "execution_count": 97, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "NewFrac(Univariate Polynomial Ring in x over Rational Field)" ] }, "execution_count": 97, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pushout(MyFrac(ZZ['x']), Frac(QQ['x']))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that merging of functors really occurs here: There is no coercion from QQ\\['x'\\] to ZZ\\['x'\\].\n", "\n", "## The Test Suites\n", "\n", "The category framework does not only provide functionality but also a test framework.\n", "\n", "### \"Abstract\" methods\n", "\n", "A category can require/suggest certain parent or element methods, that the user must/should implement. This is in order to smoothly blend with the methods that already exist in Sage.\n", "\n", "The methods that ought to be provided are called \"abstract methods\". Let us see what methods are needed for quotient fields and their elements:" ] }, { "cell_type": "code", "execution_count": 98, "metadata": {}, "outputs": [], "source": [ "from sage.misc.abstract_method import abstract_methods_of_class" ] }, { "cell_type": "code", "execution_count": 99, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'optional': [], 'required': ['__contains__']}" ] }, "execution_count": 99, "metadata": {}, "output_type": "execute_result" } ], "source": [ "abstract_methods_of_class(QuotientFields().parent_class)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.\n", "\n", "The elements have to provide more:" ] }, { "cell_type": "code", "execution_count": 100, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'optional': ['_add_', '_mul_'],\n", " 'required': ['__nonzero__', 'denominator', 'numerator']}" ] }, "execution_count": 100, "metadata": {}, "output_type": "execute_result" } ], "source": [ "abstract_methods_of_class(QuotientFields().element_class)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Hence, the elements must provide `denominator()` and `numerator()` methods, may provide Sage's single underscore arithmetic methods (actually any ring element *should* provide them).\n", "\n", "#### \\_test\\_... methods\n", "\n", "If a parent or element method's name start with \"\\_test\\_\", it gives rise to a test in the automatic test suite.\n", "\n", "For example, it is tested\n", "\n", "- whether a parent P actually is an instance of the parent class of the category of P,\n", "- whether the user hase implemented the required abstract methods,\n", "- whether some defining structural properties (e.g., commutativity) hold.\n", "\n", "Here are the tests that form the test suite of quotient fields:" ] }, { "cell_type": "code", "execution_count": 101, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['_test_additive_associativity',\n", " '_test_an_element',\n", " '_test_associativity',\n", " '_test_cardinality',\n", " '_test_characteristic',\n", " '_test_characteristic_fields',\n", " '_test_distributivity',\n", " '_test_divides',\n", " '_test_elements',\n", " '_test_elements_eq_reflexive',\n", " '_test_elements_eq_symmetric',\n", " '_test_elements_eq_transitive',\n", " '_test_elements_neq',\n", " '_test_euclidean_degree',\n", " '_test_fraction_field',\n", " '_test_gcd_vs_xgcd',\n", " '_test_one',\n", " '_test_prod',\n", " '_test_quo_rem',\n", " '_test_some_elements',\n", " '_test_zero',\n", " '_test_zero_divisors']" ] }, "execution_count": 101, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[t for t in dir(QuotientFields().parent_class) if t.startswith('_test_')]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Since we have implemented all abstract methods, we are confident that the test suite runs without complaining. In fact, it does!" ] }, { "cell_type": "code", "execution_count": 102, "metadata": {}, "outputs": [], "source": [ "P = MyFrac(ZZ['x'])" ] }, { "cell_type": "code", "execution_count": 103, "metadata": {}, "outputs": [], "source": [ "TestSuite(P).run()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us see what tests are actually performed:" ] }, { "cell_type": "code", "execution_count": 104, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "running ._test_additive_associativity() . . . pass\n", "running ._test_an_element() . . . pass\n", "running ._test_associativity() . . . pass\n", "running ._test_cardinality() . . . pass\n", "running ._test_category() . . . pass\n", "running ._test_characteristic() . . . pass\n", "running ._test_characteristic_fields() . . . pass\n", "running ._test_distributivity() . . . pass\n", "running ._test_divides() . . . pass\n", "running ._test_elements() . . .\n", " Running the test suite of self.an_element()\n", " running ._test_category() . . . pass\n", " running ._test_eq() . . . pass\n", " running ._test_new() . . . pass\n", " running ._test_nonzero_equal() . . . pass\n", " running ._test_not_implemented_methods() . . . pass\n", " running ._test_pickling() . . . pass\n", " pass\n", "running ._test_elements_eq_reflexive() . . . pass\n", "running ._test_elements_eq_symmetric() . . . pass\n", "running ._test_elements_eq_transitive() . . . pass\n", "running ._test_elements_neq() . . . pass\n", "running ._test_eq() . . . pass\n", "running ._test_euclidean_degree() . . . pass\n", "running ._test_fraction_field() . . . pass\n", "running ._test_gcd_vs_xgcd() . . . pass\n", "running ._test_new() . . . pass\n", "running ._test_not_implemented_methods() . . . pass\n", "running ._test_one() . . . pass\n", "running ._test_pickling() . . . pass\n", "running ._test_prod() . . . pass\n", "running ._test_quo_rem() . . . pass\n", "running ._test_some_elements() . . . pass\n", "running ._test_zero() . . . pass\n", "running ._test_zero_divisors() . . . pass\n" ] } ], "source": [ "TestSuite(P).run(verbose=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": 105, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(2):(1)" ] }, "execution_count": 105, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[(2):(1)]" ] }, "execution_count": 105, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.an_element(); P.some_elements()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.\n", "\n", "The method an\\_element relies on a method \\_an\\_element\\_, so, we implement that. We also override the some\\_elements method." ] }, { "cell_type": "code", "execution_count": 106, "metadata": {}, "outputs": [], "source": [ "class MyFrac(MyFrac):\n", " def _an_element_(self):\n", " a = self.base().an_element()\n", " b = self.base_ring().an_element()\n", " if (a+b)!=0:\n", " return self(a)**2/(self(a+b)**3)\n", " if b != 0:\n", " return self(a)/self(b)**2\n", " return self(a)**2*self(b)**3\n", " def some_elements(self):\n", " return [self.an_element(),self(self.base().an_element()),self(self.base_ring().an_element())]" ] }, { "cell_type": "code", "execution_count": 107, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x^2):(x^3 + 3*x^2 + 3*x + 1)" ] }, "execution_count": 107, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[(x^2):(x^3 + 3*x^2 + 3*x + 1), (x):(1), (1):(1)]" ] }, "execution_count": 107, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P = MyFrac(ZZ['x'])\n", "P.an_element(); P.some_elements()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.\n", "\n", "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.\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": 108, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'sage.categories.monoids'" ] }, "execution_count": 108, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.prod.__module__" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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). The parent and element methods of a category are provided as methods of a class `ParentMethods` and `ElementMethods`, as follows:" ] }, { "cell_type": "code", "execution_count": 109, "metadata": {}, "outputs": [], "source": [ "from sage.categories.category import Category\n", "class QuotientFieldsWithTest(Category): # do *not* inherit from QuotientFields, but ...\n", " def super_categories(self):\n", " return [QuotientFields()] # ... declare QuotientFields as a super category!\n", " class ParentMethods:\n", " pass\n", " class ElementMethods:\n", " def _test_factorisation(self, **options):\n", " P = self.parent()\n", " assert self == P.prod([P(b)**e for b,e in self.factor()])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We provide an instance of our quotient field implementation with that new category. Note that categories have a default \\_repr\\_ method, that guesses a good string representation from the name of the class: QuotientFieldsWithTest becomes \"quotient fields with test\"." ] }, { "cell_type": "code", "execution_count": 110, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Category of quotient fields with test" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P = MyFrac(ZZ['x'], category=QuotientFieldsWithTest())\n", "P.category()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The new test is inherited from the category. Since an\\_element() is returning a complicated element, \\_test\\_factorisation is a serious test." ] }, { "cell_type": "code", "execution_count": 111, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 111, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.an_element()._test_factorisation" ] }, { "cell_type": "code", "execution_count": 112, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x + 1)^-3 * x^2" ] }, "execution_count": 112, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.an_element().factor()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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, by an\\_element() returning something more interesting." ] }, { "cell_type": "code", "execution_count": 113, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "running ._test_additive_associativity() . . . pass\n", "running ._test_an_element() . . . pass\n", "running ._test_associativity() . . . pass\n", "running ._test_cardinality() . . . pass\n", "running ._test_category() . . . pass\n", "running ._test_characteristic() . . . pass\n", "running ._test_characteristic_fields() . . . pass\n", "running ._test_distributivity() . . . pass\n", "running ._test_divides() . . . pass\n", "running ._test_elements() . . .\n", " Running the test suite of self.an_element()\n", " running ._test_category() . . . pass\n", " running ._test_eq() . . . pass\n", " running ._test_factorisation() . . . pass\n", " running ._test_new() . . . pass\n", " running ._test_nonzero_equal() . . . pass\n", " running ._test_not_implemented_methods() . . . pass\n", " running ._test_pickling() . . . pass\n", " pass\n", "running ._test_elements_eq_reflexive() . . . pass\n", "running ._test_elements_eq_symmetric() . . . pass\n", "running ._test_elements_eq_transitive() . . . pass\n", "running ._test_elements_neq() . . . pass\n", "running ._test_eq() . . . pass\n", "running ._test_euclidean_degree() . . . pass\n", "running ._test_fraction_field() . . . pass\n", "running ._test_gcd_vs_xgcd() . . . pass\n", "running ._test_new() . . . pass\n", "running ._test_not_implemented_methods() . . . pass\n", "running ._test_one() . . . pass\n", "running ._test_pickling() . . . pass\n", "running ._test_prod() . . . pass\n", "running ._test_quo_rem() . . . pass\n", "running ._test_some_elements() . . . pass\n", "running ._test_zero() . . . pass\n", "running ._test_zero_divisors() . . . pass\n" ] } ], "source": [ "TestSuite(P).run(verbose=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 8.9.beta3", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.15" } }, "nbformat": 4, "nbformat_minor": 2 }