| Download

All published worksheets from http://sagenb.org

Project: sagenb.org published worksheets

Path: pub / 4201-4301 / 4229-Parents.sagews

Views: ¹⁶⁸⁷³³
Image: ubuntu2004

Coercion and Categories in Sage

David Roe

University of Washington

January 26, 2012

There are three levels of mathematical structures in Sage:

Parents -- modeling sets with some mathematical structure.
Elements -- elements of parents: frequently the subjects of our computations. Every element in Sage has a parent.
Categories -- modeled on the mathematical notion of a category, they also serve to collect code for objects (parents) in the category.

The primers on categories and coercion are good places to learn more.

Parents

Here are some examples of parents in Sage.

IntegerRing()

Integer Ring

RationalField()

Rational Field

C = ComplexField(200); C

Complex Field with 200 bits of precision

C.pi()

3.1415926535897932384626433832795028841971693993751058209749

k = GF(9,'a'); k

Finite Field in a of size 3^2

R = k['x']; R

Univariate Polynomial Ring in x over Finite Field in a of size 3^2

k[['y']]

Power Series Ring in y over Finite Field in a of size 3^2

FractionField(R)

Fraction Field of Univariate Polynomial Ring in x over Finite Field in a of size 3^2

NumberField(x^3 - 2,'c')

Number Field in c with defining polynomial x^3 - 2

MatrixSpace(RR,600,23)

Full MatrixSpace of 600 by 23 dense matrices over Real Field with 53 bits of precision

GL(4,ZZ)

General Linear Group of degree 4 over Integer Ring

SR

Symbolic Ring

isinstance(pari, Parent)

True

Native python types like ints, lists and strings don't have parents, but we'd like to reason with them as if they did. So we define the parent of such an object to just be its type.

parent('abc')

<type 'str'>

parent([1,2,3])

<type 'list'>

Note that for actual elements in Sage the type is distinct from the parent:

a = mod(3, 7); b = mod(3, 8)
print type(a)
print type(b)

<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>

print parent(a)
print parent(b)

Ring of integers modulo 7
Ring of integers modulo 8

Sometimes you're interested in computing with parents directly:

NumberField(x^5 + 3*x + 7,'c').class_group()

Class group of order 1 of Number Field in c with defining polynomial x^5 + 3*x + 7

GF(9,'a').characteristic()

3

But frequently your computations will require arithmetic with actual elements of these sets.

Elements

For a few kinds of elements there are ways to create them without first creating a parent.

a = 17; a

17

type(a)

<type 'sage.rings.integer.Integer'>

a.parent()

Integer Ring

b = 4/5; b

4/5

b.parent()

Rational Field

c = 54321 + O(5^5); c

1 + 4*5 + 2*5^2 + 4*5^3 + 5^4 + O(5^5)

c.parent()

5-adic Ring with capped relative precision 20

d = polygen(QQ); d.parent()

Univariate Polynomial Ring in x over Rational Field

I

i.parent()

Symbolic Ring

But the most common idiom in Sage is to first create a parent and then provide some data to the __call__ method of that parent in order to create elements.

R = QQ['x']; e = R([1,2,3,4]); e

4*x^3 + 3*x^2 + 2*x + 1

R.__call__([1,2,3,4])

4*x^3 + 3*x^2 + 2*x + 1

e.parent() is R

True

Behind the scenes the coercion model has entered the picture here. But the motivation for having a coercion system is more apparent in the other natural way to construct a polynomial:

x = R.gen()
f = 4*x^3 + 3*x^2 + 2*x + 1
f

4*x^3 + 3*x^2 + 2*x + 1

The primary aim of the coercion system is to allow arithmetic between elements of different parents: between R and the integer ring in the example above.

In these two examples of creating polynomials we've already seen the two types of maps appearing in the coercion system: conversions and coercions. Conversions are invoked when creating an element of a parent out of some data. They are not intended to be canonical, but instead should strive to work as frequently as possible, making non-canonical choices if necessary.

R('1 + x')

x + 1

Univariate Polynomial Ring in x over Rational Field

R(mod(3, 13)) + 40

43

CC((2,3))

2.00000000000000 + 3.00000000000000*I

CC(mod(2,3))

2.00000000000000

They can work on some elements of a single parent and not others:

Zmod(9)(4/5)

8

Zmod(9)(4/3)

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_330.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("Wm1vZCg5KSg0LzMp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/LA/LA5R72GVGf4twc05wSfazU+++TI/-Tmp-/tmpZwiUwU/___code___.py", line 3, in <module>
    exec compile(u'Zmod(_sage_const_9 )(_sage_const_4 /_sage_const_3 )' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "parent.pyx", line 988, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:7357)
  File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3324)
  File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3227)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/rings/finite_rings/integer_mod_ring.py", line 818, in _element_constructor_
    return integer_mod.IntegerMod(self, x)
  File "integer_mod.pyx", line 178, in sage.rings.finite_rings.integer_mod.IntegerMod (sage/rings/finite_rings/integer_mod.c:3138)
  File "integer_mod.pyx", line 2150, in sage.rings.finite_rings.integer_mod.IntegerMod_int.__init__ (sage/rings/finite_rings/integer_mod.c:17688)
  File "rational.pyx", line 2482, in sage.rings.rational.Rational.__mod__ (sage/rings/rational.c:18623)
  File "integer.pyx", line 5425, in sage.rings.integer.Integer.inverse_mod (sage/rings/integer.c:30817)
ZeroDivisionError: Inverse does not exist.

Coercions, on the other hand, should fit into a diagram of canonical homomorphisms. Frequently these homomorphisms are injections, but some are quotient maps instead. While conversions need to be explicitly invoked by the __call__ method of the parent, coercions are applied implicitly when doing arithmetic.

a = 2; b = 1/2
print parent(a)
print parent(b)
print a + b
print parent(a+b)

Integer Ring
Rational Field
5/2
Rational Field

Behind the scenes, both coercions and conversions are implemented as maps, or morphisms.

g = Zmod(9).coerce_map_from(ZZ); g

Natural morphism:
  From: Integer Ring
  To:   Ring of integers modulo 9

type(g)

<type 'sage.rings.finite_rings.integer_mod.Integer_to_IntegerMod'>

parent(g(44))

Ring of integers modulo 9

type(Zmod(9).coerce_map_from(Zmod(8)))

<type 'NoneType'>

h = R.convert_map_from(list); h

Conversion map:
  From: Set of Python objects of type 'list'
  To:   Univariate Polynomial Ring in x over Rational Field

type(h)

<type 'sage.structure.coerce_maps.DefaultConvertMap_unique'>

h([5,6,7,8])

8*x^3 + 7*x^2 + 6*x + 5

So suppose you multiply two elements $a$ and $b$ with parents $A$ and $B$ respectively. After checking to see if $A$ is in fact the same object as $B$ , one of the ways Sage allows arithmetic between different parents is to check to see if there's a coercion map from $A$ to $B$ or from $B$ to $A$ . But there are a number of cases where this strategy is not sufficient.

Actions

a = matrix([[1,2]]); b = matrix([[5],[7]]); A = parent(a); B = parent(b)
show(a)

\newcommand{\Bold}[1]{\mathbf{#1}}\left(

\begin{array}{rr} 1 & 2 \end{array}

\right)

show(b)

\newcommand{\Bold}[1]{\mathbf{#1}}\left(

\begin{array}{r} 5 \\ 7 \end{array}

\right)

a*b

[19]

b*a

[ 5 10]
[ 7 14]

There is no coercion from the parent of $a$ to the parent of $b$ or vice versa. Yet multiplication still succeeds. What is going on?

A.coerce_map_from(B)

B.coerce_map_from(A)

2*x

2*x

act = A.get_action(B); act

Left action by Full MatrixSpace of 1 by 2 dense matrices over Integer Ring on Full MatrixSpace of 2 by 1 dense matrices over Integer Ring

act2 = B.get_action(A); act2

Left action by Full MatrixSpace of 2 by 1 dense matrices over Integer Ring on Full MatrixSpace of 1 by 2 dense matrices over Integer Ring

act(a, b)

[19]

act(b, a)

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_352.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("YWN0KGIsIGEp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/LA/LA5R72GVGf4twc05wSfazU+++TI/-Tmp-/tmppfEyqD/___code___.py", line 2, in <module>
    exec compile(u'act(b, a)' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "action.pyx", line 255, in sage.categories.action.Action.__call__ (sage/categories/action.c:2937)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/matrix/matrix_space.py", line 451, in __call__
    return self.matrix(entries, copy=copy, coerce=coerce, rows=rows)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/matrix/matrix_space.py", line 1221, in matrix
    "a matrix in %s!" % (x.parent(), self))
ValueError: a matrix from Full MatrixSpace of 2 by 1 dense matrices over Integer Ring cannot be converted to a matrix in Full MatrixSpace of 1 by 2 dense matrices over Integer Ring!

act2(b, a)

[ 5 10]
[ 7 14]

For multiplication and division, the first thing Sage checks after checking whether two elements have the same parent is to see if an action exists.

x.__mul__??

File: /Users/roed/sage/sage-4.8.alpha2/devel/sage/sage/structure/element.pyx

Source Code (starting at line 1344):

def __mul__(left, right):
    """
    Top-level multiplication operator for ring elements.
    See extensive documentation at the top of element.pyx.

    AUTHOR:

    - Gonzalo Tornaria (2007-06-25) - write base-extending test cases and fix them

    TESTS:

    Here we test (scalar * vector) multiplication::

        sage: x, y = var('x, y')

        sage: parent(ZZ(1)*vector(ZZ,[1,2]))
        Ambient free module of rank 2 over the principal ideal domain Integer Ring
        sage: parent(QQ(1)*vector(ZZ,[1,2]))
        Vector space of dimension 2 over Rational Field
        sage: parent(ZZ(1)*vector(QQ,[1,2]))
        Vector space of dimension 2 over Rational Field
        sage: parent(QQ(1)*vector(QQ,[1,2]))
        Vector space of dimension 2 over Rational Field

        sage: parent(QQ(1)*vector(ZZ[x],[1,2]))
        Ambient free module of rank 2 over the principal ideal domain Univariate Polynomial Ring in x over Rational Field
        sage: parent(ZZ[x](1)*vector(QQ,[1,2]))
        Ambient free module of rank 2 over the principal ideal domain Univariate Polynomial Ring in x over Rational Field

        sage: parent(QQ(1)*vector(ZZ[x][y],[1,2]))
        Ambient free module of rank 2 over the integral domain Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
        sage: parent(ZZ[x][y](1)*vector(QQ,[1,2]))
        Ambient free module of rank 2 over the integral domain Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field

        sage: parent(QQ[x](1)*vector(ZZ[x][y],[1,2]))
        Ambient free module of rank 2 over the integral domain Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
        sage: parent(ZZ[x][y](1)*vector(QQ[x],[1,2]))
        Ambient free module of rank 2 over the integral domain Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field

        sage: parent(QQ[y](1)*vector(ZZ[x][y],[1,2]))
        Ambient free module of rank 2 over the integral domain Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
        sage: parent(ZZ[x][y](1)*vector(QQ[y],[1,2]))
        Ambient free module of rank 2 over the integral domain Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field

        sage: parent(ZZ[x](1)*vector(ZZ[y],[1,2]))
        Traceback (most recent call last):
        ...
        TypeError: unsupported operand parent(s) for '*': 'Univariate Polynomial Ring in x over Integer Ring' and 'Ambient free module of rank 2 over the integral domain Univariate Polynomial Ring in y over Integer Ring'
        sage: parent(ZZ[x](1)*vector(QQ[y],[1,2]))
        Traceback (most recent call last):
        ...
        TypeError: unsupported operand parent(s) for '*': 'Univariate Polynomial Ring in x over Integer Ring' and 'Ambient free module of rank 2 over the principal ideal domain Univariate Polynomial Ring in y over Rational Field'
        sage: parent(QQ[x](1)*vector(ZZ[y],[1,2]))
        Traceback (most recent call last):
        ...
        TypeError: unsupported operand parent(s) for '*': 'Univariate Polynomial Ring in x over Rational Field' and 'Ambient free module of rank 2 over the integral domain Univariate Polynomial Ring in y over Integer Ring'
        sage: parent(QQ[x](1)*vector(QQ[y],[1,2]))
        Traceback (most recent call last):
        ...
        TypeError: unsupported operand parent(s) for '*': 'Univariate Polynomial Ring in x over Rational Field' and 'Ambient free module of rank 2 over the principal ideal domain Univariate Polynomial Ring in y over Rational Field'

    Here we test (scalar * matrix) multiplication::

        sage: parent(ZZ(1)*matrix(ZZ,2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Integer Ring
        sage: parent(QQ(1)*matrix(ZZ,2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Rational Field
        sage: parent(ZZ(1)*matrix(QQ,2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Rational Field
        sage: parent(QQ(1)*matrix(QQ,2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Rational Field

        sage: parent(QQ(1)*matrix(ZZ[x],2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in x over Rational Field
        sage: parent(ZZ[x](1)*matrix(QQ,2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in x over Rational Field

        sage: parent(QQ(1)*matrix(ZZ[x][y],2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
        sage: parent(ZZ[x][y](1)*matrix(QQ,2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field

        sage: parent(QQ[x](1)*matrix(ZZ[x][y],2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
        sage: parent(ZZ[x][y](1)*matrix(QQ[x],2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field

        sage: parent(QQ[y](1)*matrix(ZZ[x][y],2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
        sage: parent(ZZ[x][y](1)*matrix(QQ[y],2,2,[1,2,3,4]))
        Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field

        sage: parent(ZZ[x](1)*matrix(ZZ[y],2,2,[1,2,3,4]))
        Traceback (most recent call last):
        ...
        TypeError: unsupported operand parent(s) for '*': 'Univariate Polynomial Ring in x over Integer Ring' and 'Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in y over Integer Ring'
        sage: parent(ZZ[x](1)*matrix(QQ[y],2,2,[1,2,3,4]))
        Traceback (most recent call last):
        ...
        TypeError: unsupported operand parent(s) for '*': 'Univariate Polynomial Ring in x over Integer Ring' and 'Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in y over Rational Field'
        sage: parent(QQ[x](1)*matrix(ZZ[y],2,2,[1,2,3,4]))
        Traceback (most recent call last):
        ...
        TypeError: unsupported operand parent(s) for '*': 'Univariate Polynomial Ring in x over Rational Field' and 'Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in y over Integer Ring'
        sage: parent(QQ[x](1)*matrix(QQ[y],2,2,[1,2,3,4]))
        Traceback (most recent call last):
        ...
        TypeError: unsupported operand parent(s) for '*': 'Univariate Polynomial Ring in x over Rational Field' and 'Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in y over Rational Field'

    """
    # Try fast pathway if they are both RingElements and the parents match.
    # (We know at least one of the arguments is a RingElement. So if their
    # types are *equal* (fast to check) then they are both RingElements.
    # Otherwise use the slower test via PY_TYPE_CHECK.)
    if have_same_parent(left, right):
        if  (<RefPyObject *>left).ob_refcnt < inplace_threshold:
            return (<RingElement>left)._imul_(<RingElement>right)
        else:
            return (<RingElement>left)._mul_(<RingElement>right)
    if PyInt_CheckExact(right):
        return (<ModuleElement>left)._mul_long(PyInt_AS_LONG(right))
    elif PyInt_CheckExact(left):
        return (<ModuleElement>right)._mul_long(PyInt_AS_LONG(left))
    return coercion_model.bin_op(left, right, mul)

cm = sage.structure.element.get_coercion_model()
cm.bin_op??

File: /Users/roed/sage/sage-4.8.alpha2/devel/sage/sage/structure/coerce.pyx

Source Code (starting at line 651):

cpdef bin_op(self, x, y, op):
    """
    Execute the operation op on x and y. It first looks for an action
    corresponding to op, and failing that, it tries to coerces x and y
    into the a common parent and calls op on them.

    If it cannot make sense of the operation, a TypeError is raised.

    INPUT:

    - ``x``  - the left operand

    - ``y``  - the right operand

    - ``op`` - a python function taking 2 arguments

      .. note::

         op is often an arithmetic operation, but need not be so.

    EXAMPLES::

        sage: cm = sage.structure.element.get_coercion_model()
        sage: cm.bin_op(1/2, 5, operator.mul)
        5/2

    The operator can be any callable::

        set Rational Field Integer Ring <function <lambda> at 0xc0b2270> None None
        (Rational Field, Rational Field)
        sage: R.<x> = ZZ['x']
        sage: cm.bin_op(x^2-1, x+1, gcd)
        x + 1

    Actions are detected and performed::

        sage: M = matrix(ZZ, 2, 2, range(4))
        sage: V = vector(ZZ, [5,7])
        sage: cm.bin_op(M, V, operator.mul)
        (7, 31)

    TESTS::

        sage: class Foo:
        ...      def __rmul__(self, left):
        ...          return 'hello'
        ...
        sage: H = Foo()
        sage: print int(3)*H
        hello
        sage: print Integer(3)*H
        hello
        sage: print H*3
        Traceback (most recent call last):
        ...
        TypeError: unsupported operand parent(s) for '*': '<type 'instance'>' and 'Integer Ring'

        sage: class Nonsense:
        ...       def __init__(self, s):
        ...           self.s = s
        ...       def __repr__(self):
        ...           return self.s
        ...       def __mul__(self, x):
        ...           return Nonsense(self.s + chr(x%256))
        ...       __add__ = __mul__
        ...       def __rmul__(self, x):
        ...           return Nonsense(chr(x%256) + self.s)
        ...       __radd__ = __rmul__
        ...
        sage: a = Nonsense('blahblah')
        sage: a*80
        blahblahP
        sage: 80*a
        Pblahblah
        sage: a+80
        blahblahP
        sage: 80+a
        Pblahblah

    """
    self._exceptions_cleared = False
    if (op is not sub) and (op is not isub):
        # Actions take preference over common-parent coercions.
        xp = parent_c(x)
        yp = parent_c(y)
        if xp is yp:
            return op(x,y)
        action = self.get_action(xp, yp, op)
        if action is not None:
            return (<Action>action)._call_(x, y)

    xy = None
    try:
        xy = self.canonical_coercion(x,y)
        return PyObject_CallObject(op, xy)
    except TypeError, err:
        if xy is not None:
            # The error was in calling, not coercing
            raise
        self._record_exception()

    if op is mul or op is imul:

        # elements may also act on non-elements
        # (e.g. sequences or parents)
        if not isinstance(y, Element) or not isinstance(x, Element):
            try:
                if hasattr(x, '_act_on_'):
                    res = x._act_on_(y, True)
                    if res is not None: return res
            except CoercionException:
                self._record_exception()

            try:
                if hasattr(x, '_acted_upon_'):
                    res = x._acted_upon_(y, True)
                    if res is not None: return res
            except CoercionException:
                self._record_exception()

            try:
                if hasattr(y, '_act_on_'):
                    res = y._act_on_(x, False)
                    if res is not None: return res
            except CoercionException:
                self._record_exception()

            try:
                if hasattr(y, '_acted_upon_'):
                    res = y._acted_upon_(x, False)
                    if res is not None: return res
            except CoercionException:
                self._record_exception()

    if not isinstance(y, Element):
        op_name = op.__name__
        if op_name[0] == 'i':
            op_name = op_name[1:]
        mul_method = getattr3(y, '__r%s__'%op_name, None)
        if mul_method is not None:
            res = mul_method(x)
            if res is not None and res is not NotImplemented:
                return res

    # We should really include the underlying error.
    # This causes so much headache.
    raise TypeError, arith_error_message(x,y,op)

The second way in which our strategy of coercing each way is not sufficient is when there is no coercion in either direction, but we really want the operation to be defined. Here's an example:

R = ZZ['x']; x = R.gen()
y = x + 1/2; y

x + 1/2

A = x.parent(); A

Univariate Polynomial Ring in x over Integer Ring

B = (1/2).parent(); B

Rational Field

C = y.parent(); C

Univariate Polynomial Ring in x over Rational Field

A.has_coerce_map_from(B)

False

B.has_coerce_map_from(A)

False

C.has_coerce_map_from(A)

True

C.has_coerce_map_from(B)

True

cm.canonical_coercion??

File: /Users/roed/sage/sage-4.8.alpha2/devel/sage/sage/structure/coerce.pyx

Source Code (starting at line 799):

cpdef canonical_coercion(self, x, y):
    r"""
    Given two elements x and y, with parents S and R respectively,
    find a common parent Z such that there are coercions
    `f: S \mapsto Z` and `g: R \mapsto Z` and return `f(x), g(y)`
    which will have the same parent.

    Raises a type error if no such Z can be found.

    EXAMPLES::

        sage: cm = sage.structure.element.get_coercion_model()
        sage: cm.canonical_coercion(mod(2, 10), 17)
        (2, 7)
        sage: x, y = cm.canonical_coercion(1/2, matrix(ZZ, 2, 2, range(4)))
        sage: x
        [1/2   0]
        [  0 1/2]
        sage: y
        [0 1]
        [2 3]
        sage: parent(x) is parent(y)
        True

    There is some support for non-Sage datatypes as well::

        sage: x, y = cm.canonical_coercion(int(5), 10)
        sage: type(x), type(y)
        (<type 'sage.rings.integer.Integer'>, <type 'sage.rings.integer.Integer'>)


        sage: x, y = cm.canonical_coercion(int(5), complex(3))
        sage: type(x), type(y)
        (<type 'complex'>, <type 'complex'>)

        sage: class MyClass:
        ...       def _sage_(self):
        ...           return 13
        sage: a, b = cm.canonical_coercion(MyClass(), 1/3)
        sage: a, b
        (13, 1/3)
        sage: type(a)
        <type 'sage.rings.rational.Rational'>

    We also make an exception for 0, even if $\ZZ$ does not map in::

        sage: canonical_coercion(vector([1, 2, 3]), 0)
        ((1, 2, 3), (0, 0, 0))
    """
    xp = parent_c(x)
    yp = parent_c(y)
    if xp is yp:
        return x,y

    cdef Element x_elt, y_elt
    coercions = self.coercion_maps(xp, yp)
    if coercions is not None:
        x_map, y_map = coercions
        if x_map is not None:
            x_elt = (<Map>x_map)._call_(x)
        else:
            x_elt = x
        if y_map is not None:
            y_elt = (<Map>y_map)._call_(y)
        else:
            y_elt = y
        if x_elt is None:
            raise RuntimeError, "BUG in map, returned None %s %s %s" % (x, type(x_map), x_map)
        elif y_elt is None:
            raise RuntimeError, "BUG in map, returned None %s %s %s" % (y, type(y_map), y_map)
        if x_elt._parent is y_elt._parent:
            # We must verify this as otherwise we are prone to
            # getting into an infinite loop in c, and the above
            # maps may be written by (imperfect) users.
            return x_elt,y_elt
        elif x_elt._parent == y_elt._parent:
            # TODO: Non-uniqueness of parents strikes again!
            # print parent_c(x_elt), " is not ", parent_c(y_elt)
            y_elt = parent_c(x_elt)(y_elt)
            if x_elt._parent is y_elt._parent:
                return x_elt,y_elt
        self._coercion_error(x, x_map, x_elt, y, y_map, y_elt)


    cdef bint x_numeric = PY_IS_NUMERIC(x)
    cdef bint y_numeric = PY_IS_NUMERIC(y)

    if x_numeric and y_numeric:
        x_rank = _native_coercion_ranks[type(x)]
        y_rank = _native_coercion_ranks[type(y)]
        ty = _native_coercion_ranks_inv[max(x_rank, y_rank)]
        x = ty(x)
        y = ty(y)
        return x, y

    # Now handle the native python + sage object cases
    # that were not taken care of above.
    elif x_numeric:
        try:
            sage_parent = py_scalar_parent(type(x))
            if sage_parent is None or sage_parent.has_coerce_map_from(yp):
                return x, x.__class__(y)
            else:
                return self.canonical_coercion(sage_parent(x), y)
        except (TypeError, ValueError):
            self._record_exception()

    elif y_numeric:
        try:
            sage_parent = py_scalar_parent(type(y))
            if sage_parent is None or sage_parent.has_coerce_map_from(xp):
                return y.__class__(x), y
            else:
                return self.canonical_coercion(x, sage_parent(y))
        except (TypeError, ValueError):
            self._record_exception()

    # See if the non-objects define a _sage_ method.
    if not PY_TYPE_CHECK(x, SageObject) or not PY_TYPE_CHECK(y, SageObject):
        try:
            x = x._sage_()
            y = y._sage_()
        except AttributeError:
            self._record_exception()
        else:
            return self.canonical_coercion(x, y)

    # Allow coercion of 0 even if no coercion from Z
    if is_Integer(x) and not x and not PY_TYPE_CHECK_EXACT(yp, type):
        try:
            return yp(0), y
        except:
            self._record_exception()

    if is_Integer(y) and not y and not PY_TYPE_CHECK_EXACT(xp, type):
        try:
            return x, xp(0)
        except:
            self._record_exception()

    raise TypeError, "no common canonical parent for objects with parents: '%s' and '%s'"%(xp, yp)

cm.coercion_maps??

File: /Users/roed/sage/sage-4.8.alpha2/devel/sage/sage/structure/coerce.pyx

Source Code (starting at line 942):

cpdef coercion_maps(self, R, S):
    r"""
    Give two parents R and S, return a pair of coercion maps
    `f: R \rightarrow Z` and `g: S \rightarrow Z` , if such a `Z`
    can be found.

    In the (common) case that `R=Z` or `S=Z` then ``None`` is returned
    for `f` or `g` respectively rather than constructing (and subsequently
    calling) the identity morphism.

    If no suitable `f, g` can be found, a single None is returned.
    This result is cached.

    EXAMPLES::

        sage: cm = sage.structure.element.get_coercion_model()
        sage: f, g = cm.coercion_maps(ZZ, QQ)
        sage: print f
        Natural morphism:
          From: Integer Ring
          To:   Rational Field
        sage: print g
        None

        sage: f, g = cm.coercion_maps(ZZ['x'], QQ)
        sage: print f
        Conversion map:
          From: Univariate Polynomial Ring in x over Integer Ring
          To:   Univariate Polynomial Ring in x over Rational Field
        sage: print g
        Polynomial base injection morphism:
          From: Rational Field
          To:   Univariate Polynomial Ring in x over Rational Field

        sage: cm.coercion_maps(QQ, GF(7)) == None
        True

    Note that to break symmetry, if there is a coercion map in both
    directions, the parent on the left is used::

        sage: V = QQ^3
        sage: W = V.__class__(QQ, 3)
        sage: V == W
        True
        sage: V is W
        False
        sage: cm = sage.structure.element.get_coercion_model()
        sage: cm.coercion_maps(V, W)
        (None,
         Call morphism:
          From: Vector space of dimension 3 over Rational Field
          To:   Vector space of dimension 3 over Rational Field)
        sage: cm.coercion_maps(W, V)
        (None,
         Call morphism:
          From: Vector space of dimension 3 over Rational Field
          To:   Vector space of dimension 3 over Rational Field)
        sage: v = V([1,2,3])
        sage: w = W([1,2,3])
        sage: parent(v+w) is V
        True
        sage: parent(w+v) is W
        True
    """
    try:
        return self._coercion_maps.get(R, S, None)
    except KeyError:
        homs = self.discover_coercion(R, S)
        if 0:
            # This breaks too many things that are going to change
            # in the new coercion model anyways.
            # COERCE TODO: Enable it then.
            homs = self.verify_coercion_maps(R, S, homs)
        else:
            if homs is not None:
                x_map, y_map = homs
                if x_map is not None and not isinstance(x_map, Map):
                    raise RuntimeError, "BUG in coercion model: coerce_map_from must return a Map"
                if y_map is not None and not isinstance(y_map, Map):
                    raise RuntimeError, "BUG in coercion model: coerce_map_from must return a Map"
        if homs is None:
            swap = None
        else:
            R_map, S_map = homs
            if R_map is None and PY_TYPE_CHECK(S, Parent) and (<Parent>S).has_coerce_map_from(R):
                swap = None, (<Parent>S).coerce_map_from(R)
            else:
                swap = S_map, R_map
        self._coercion_maps.set(R, S, None, homs)
        self._coercion_maps.set(S, R, None, swap)
    return homs

x.__mul__

cm.discover_coercion??

File: /Users/roed/sage/sage-4.8.alpha2/devel/sage/sage/structure/coerce.pyx

Source Code (starting at line 1101):

cpdef discover_coercion(self, R, S):
    """
    This actually implements the finding of coercion maps as described in
    the ``coercion_maps`` method.

    EXAMPLES::

        sage: cm = sage.structure.element.get_coercion_model()

    If R is S, then two identity morphisms suffice::

        sage: cm.discover_coercion(SR, SR)
        (None, None)

    If there is a coercion map either direction, use that::

        sage: cm.discover_coercion(ZZ, QQ)
        (Natural morphism:
          From: Integer Ring
          To:   Rational Field, None)
        sage: cm.discover_coercion(RR, QQ)
        (None,
         Generic map:
          From: Rational Field
          To:   Real Field with 53 bits of precision)

    Otherwise, try and compute an appropriate cover::

        sage: cm.discover_coercion(ZZ['x,y'], RDF)
        (Call morphism:
          From: Multivariate Polynomial Ring in x, y over Integer Ring
          To:   Multivariate Polynomial Ring in x, y over Real Double Field,
         Polynomial base injection morphism:
          From: Real Double Field
          To:   Multivariate Polynomial Ring in x, y over Real Double Field)

    Sometimes there is a reasonable "cover," but no canonical coercion::

        sage: sage.categories.pushout.pushout(QQ, QQ^3)
        Vector space of dimension 3 over Rational Field
        sage: print cm.discover_coercion(QQ, QQ^3)
        None
    """
    from sage.categories.homset import Hom
    if R is S:
        return None, None

    # See if there is a natural coercion from R to S
    if PY_TYPE_CHECK(R, Parent):
        mor = (<Parent>R).coerce_map_from(S)
        if mor is not None:
            return None, mor

    # See if there is a natural coercion from S to R
    if PY_TYPE_CHECK(S, Parent):
        mor = (<Parent>S).coerce_map_from(R)
        if mor is not None:
            return mor, None

    # Try base extending
    if PY_TYPE_CHECK(R, Parent) and PY_TYPE_CHECK(S, Parent):
        from sage.categories.pushout import pushout
        try:
            Z = pushout(R, S)
            coerce_R = Z.coerce_map_from(R)
            coerce_S = Z.coerce_map_from(S)
            if coerce_R is None:
                raise TypeError, "No coercion from %s to pushout %s" % (R, Z)
            if coerce_S is None:
                raise TypeError, "No coercion from %s to pushout %s" % (S, Z)
            return coerce_R, coerce_S
        except:
            self._record_exception()

    return None

print A
print B

Univariate Polynomial Ring in x over Integer Ring
Rational Field

cm.explain(A,B,operator.add)

Coercion on left operand via
    Conversion map:
      From: Univariate Polynomial Ring in x over Integer Ring
      To:   Univariate Polynomial Ring in x over Rational Field
Coercion on right operand via
    Polynomial base injection morphism:
      From: Rational Field
      To:   Univariate Polynomial Ring in x over Rational Field
Arithmetic performed after coercions.
Result lives in Univariate Polynomial Ring in x over Rational Field
Univariate Polynomial Ring in x over Rational Field

cm.explain(A,B,operator.mul)

Action discovered.
    Right scalar multiplication by Rational Field on Univariate Polynomial Ring in x over Integer Ring
Result lives in Univariate Polynomial Ring in x over Rational Field
Univariate Polynomial Ring in x over Rational Field

How does Sage know what $C$ to choose? The answer is in sage.categories.pushout and the construction method on parents.

A.construction()

(Poly[x], Integer Ring)

B.construction()

(FractionField, Integer Ring)

Qp(5).construction()

(Completion[5], Rational Field)

Sage traces back along these construction functors until it finds a common ancestor: since much arithmetic is actually being performed on rings and many common rings can be constructed from the integers by applying a sequence of functors, finding a common ancestor is frequently possible. Sage then uses a collection of heuristics to merge these constructions.

MatrixSpace(ZZ,2).construction()

(MatrixFunctor, Integer Ring)

matrix(A,[[x,x+1],[1,2]]) + 5

[x + 5 x + 1]
[    1     7]

sage.categories.pushout.pushout_lattice??

File: /Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/pushout.py

Source Code (starting at line 3097):

def pushout_lattice(R, S):
    r"""
    Given a pair of Objects $R$ and $S$, try and construct a
    reasonable object $Y$ and return maps such that
    canonically $R \leftarrow Y \rightarrow S$.

    ALGORITHM:

    This is based on the model that arose from much discussion at Sage Days 4.
    Going up the tower of constructions of $R$ and $S$ (e.g. the reals
    come from the rationals come from the integers) try and find a
    common parent, and then try and fill in a lattice with these
    two towers as sides with the top as the common ancestor and
    the bottom will be the desired ring.

    See the code for a specific worked-out example.

    EXAMPLES::

        sage: from sage.categories.pushout import pushout_lattice
        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
        sage: A.codomain()
        Fraction Field of Univariate Polynomial Ring in x over 7-adic Field with capped relative precision 20
        sage: A.codomain() is B.codomain()
        True
        sage: A, B = pushout_lattice(ZZ, MatrixSpace(ZZ[['x']], 3, 3))
        sage: B
        Identity endomorphism of Full MatrixSpace of 3 by 3 dense matrices over Power Series Ring in x over Integer Ring

    AUTHOR:

    - Robert Bradshaw

    """
    R_tower = construction_tower(R)
    S_tower = construction_tower(S)
    Rs = [c[1] for c in R_tower]
    Ss = [c[1] for c in S_tower]

    # look for common ancestor
    start = None
    for Z in Rs:
        if Z in Ss:
            start = Z
    if start is None:
        # Should I test for a map between the tops of the towers?
        # Or, if they're both not ZZ, is it hopeless?
        return None

    # truncate at common ancestor
    R_tower = list(reversed(R_tower[:Rs.index(start)+1]))
    S_tower = list(reversed(S_tower[:Ss.index(start)+1]))
    Rs = [c[1] for c in R_tower] # the list of objects
    Ss = [c[1] for c in S_tower]
    Rc = [c[0] for c in R_tower] # the list of functors
    Sc = [c[0] for c in S_tower]

    # Here we try and construct a 2-dimensional lattice as follows.
    # Suppose our towers are Z -> Q -> Qp = R and Z -> Z[t] -> Frac(Z[t]) = S
    lattice = {}
    # First we fill in the sides
    #
    #         Z
    #       /   \
    #      Q    Z[t]
    #    /         \
    #   Qp       Frac(Z[t])
    #
    for i in range(len(Rs)):
        lattice[i,0] = Rs[i]
    for j in range(len(Ss)):
        lattice[0,j] = Ss[j]

    # Now we attempt to fill in the center, one (diagonal) row at a time,
    # one commuting square at a time.
    #
    #          Z
    #       /    \
    #      Q     Z[t]
    #    /   \  /    \
    #   Qp   Q[t]   Frac(Z[t])
    #    \   /
    #    Qp[t]
    #
    # There is always exactly one "correct" path/order in which to apply operations
    # from the top to the bottom. In our example, this is down the far left side.
    # We keep track of which that is by clearing out Rc and Sc as we go along.
    #
    # Note that when applying the functors in the correct order, base extension
    # is not needed (though it may occur in the resulting morphisms).
    #
    for i in range(len(Rc)-1):
        for j in range(len(Sc)-1):
            try:
                if lattice[i,j+1] == lattice[i+1,j]:
                    # In this case we have R <- S -> R
                    # We don't want to perform the operation twice
                    # and all subsequent squares will come from objects
                    # where the operation was already performed (either
                    # to the left or right)
                    Rc[i] = Sc[j] = None # IdentityConstructionFunctor()
                    lattice[i+1,j+1] = lattice[i,j+1]
                elif Rc[i] is None and Sc[j] is None:
                    lattice[i+1,j+1] = lattice[i,j+1]
                elif Rc[i] is None:
                    lattice[i+1,j+1] = Sc[j](lattice[i+1,j])
                elif Sc[j] is None:
                    lattice[i+1,j+1] = Rc[i](lattice[i,j+1])
                else:
                    # For now, we just look at the rank.
                    # TODO: be more sophisticated and query the functors themselves
                    if Rc[i].rank < Sc[j].rank:
                        lattice[i+1,j+1] = Sc[j](lattice[i+1,j])
                        Rc[i] = None # force us to use pre-applied Rc[i]
                    else:
                        lattice[i+1,j+1] = Rc[i](lattice[i,j+1])
                        Sc[j] = None # force us to use pre-applied Sc[i]
            except (AttributeError, NameError):
                # print i, j
                # pp(lattice)
                for i in range(100):
                    for j in range(100):
                        try:
                            R = lattice[i,j]
                            print i, j, R
                        except KeyError:
                            break
                raise CoercionException, "%s does not support %s" % (lattice[i,j], 'F')

    # If we are successful, we should have something that looks like this.
    #
    #          Z
    #       /    \
    #      Q     Z[t]
    #    /   \  /    \
    #   Qp   Q[t]   Frac(Z[t])
    #    \   /  \    /
    #    Qp[t]  Frac(Q[t])
    #      \      /
    #     Frac(Qp[t])
    #
    R_loc = len(Rs)-1
    S_loc = len(Ss)-1

    # Find the composition coercion morphisms along the bottom left...
    if S_loc > 0:
        R_map = lattice[R_loc,1].coerce_map_from(R)
        for i in range(1, S_loc):
            map = lattice[R_loc, i+1].coerce_map_from(lattice[R_loc, i]) # The functor used is implicit here, should it be?
            R_map = map * R_map
    else:
        R_map = R.coerce_map_from(R) # id

    # ... and bottom right
    if R_loc > 0:
        S_map = lattice[1, S_loc].coerce_map_from(S)
        for i in range(1, R_loc):
            map = lattice[i+1, S_loc].coerce_map_from(lattice[i, S_loc])
            S_map = map * S_map
    else:
        S_map = S.coerce_map_from(S) # id

    return R_map, S_map

So in summary, Sage tries the following steps in order to execute an arithmetic operation.

Check to see if the elements have the same parent. If so, call the _mul_, _add_, etc method defined in the class of the element.
Check to see if there's an appropriate action by one parent on the other. If so, apply the action.
Check to see if there's a coercion in either direction.
Try to create a pushout to which both parents coerce using the construction methods on the parents. If appropriate coercions are detected, apply them to the two elements and do arithmetic in the "common" parent.

In order to make all of this fast, the coercions and actions that are discovered are cached. So while the first instance of arithmetic between different parents can be slow, later arithmetic will be much faster. And if the default coercion maps created are too slow for you, you can implement your own morphisms in Cython and use them (the coercion from ZZ to Zmod(N) uses this feature).

Categories

Categories in Sage are modeled on the mathematical concept of a category and one of their purposes is to allow users to model such objects in Sage. For example, you might want to know if a category is abelian, has an initial or terminal object, is closed under inverse limits....

But they also serve as a place to put code that should apply to any object in that category.

Every parent in Sage has a category.

C = ZZ.category()
C

Category of euclidean domains

Category of euclidean domains

a = mod(3,9)
b = 44
timeit("c = a + b")

625 loops, best of 3: 741 ns per loop

cm.reset_cache()

timeit("c = a + b",number=1,repeat=1)

1 loops, best of 1: 19.1 µs per loop

Category of euclidean domains

C.super_categories()

[Category of principal ideal domains]

C.all_super_categories()

[Category of euclidean domains, Category of principal ideal domains, Category of unique factorization domains, Category of gcd domains, Category of integral domains, Category of commutative rings, Category of domains, Category of rings, Category of rngs, Category of commutative additive groups, Category of semirings, Category of commutative additive monoids, Category of commutative additive semigroups, Category of additive magmas, Category of monoids, Category of semigroups, Category of magmas, Category of sets, Category of sets with partial maps, Category of objects]

G = C.category_graph();
G.plot(layout='spring', talk=True)

D = Modules(ZZ); D

Category of modules over Integer Ring

D.is_abelian()

True

Modules(QQ)

Category of vector spaces over Rational Field

Categories include information about what functions need to be implemented by parents in that category and elements of those parents.

from sage.misc.abstract_method import abstract_methods_of_class
abstract_methods_of_class(FiniteSemigroups().element_class)

{'required': [], 'optional': ['_mul_']}

abstract_methods_of_class(FiniteSemigroups().parent_class)

{'required': ['__contains__'], 'optional': []}

If you write a new parent, Sage has a testing framework to check whether it implements these required methods, and implements them correctly.

S = FiniteSemigroups().example(alphabet=('a', 'b'))
S

An example of a finite semigroup: the left regular band generated by ('a', 'b')

TestSuite(S).run(verbose=True)

running ._test_an_element() . . . pass
running ._test_associativity() . . . pass
running ._test_category() . . . pass
running ._test_elements() . . .
  Running the test suite of self.an_element()
  running ._test_category() . . . pass
  running ._test_eq() . . . pass
  running ._test_not_implemented_methods() . . . pass
  running ._test_pickling() . . . pass
  pass
running ._test_elements_eq() . . . pass
running ._test_enumerated_set_contains() . . . pass
running ._test_enumerated_set_iter_cardinality() . . . pass
running ._test_enumerated_set_iter_list() . . . pass
running ._test_eq() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass
running ._test_some_elements() . . . pass

class WrongSemigroup(Parent):
    def __init__(self):
        Parent.__init__(self, category=FiniteSemigroups())

W = WrongSemigroup()
TestSuite(W).run(verbose=True)

running ._test_an_element() . . . fail

Traceback (most recent call last):
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
    test_method(tester = tester)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/sets_cat.py", line 401, in _test_an_element
    an_element = self.an_element()
  File "parent.pyx", line 2347, in sage.structure.parent.Parent.an_element (sage/structure/parent.c:16498)
  File "parent.pyx", line 2373, in sage.structure.parent.Parent.an_element (sage/structure/parent.c:16442)
  File "parent.pyx", line 2441, in sage.structure.parent.Parent._an_element_ (sage/structure/parent.c:17033)
NotImplementedError: please implement _an_element_ for <class '__main__.WrongSemigroup_with_category'>
------------------------------------------------------------
running ._test_associativity() . . . fail
Traceback (most recent call last):
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
    test_method(tester = tester)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/semigroups.py", line 116, in _test_associativity
    for x in tester.some_elements():
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/finite_semigroups.py", line 144, in __iter__
    return TransitiveIdeal(self.succ_generators(side = "right"), self.semigroup_generators()).__iter__()
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/finite_semigroups.py", line 128, in succ_generators
    generators = self.semigroup_generators()
  File "parent.pyx", line 811, in sage.structure.parent.Parent.__getattr__ (sage/structure/parent.c:6279)
  File "parent.pyx", line 323, in sage.structure.parent.getattr_from_other_class (sage/structure/parent.c:3164)
AttributeError: 'WrongSemigroup_with_category' object has no attribute 'semigroup_generators'
------------------------------------------------------------
running ._test_category() . . . pass
running ._test_elements() . . . fail
Traceback (most recent call last):
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
    test_method(tester = tester)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/sets_cat.py", line 464, in _test_elements
    an_element = self.an_element()
  File "parent.pyx", line 2347, in sage.structure.parent.Parent.an_element (sage/structure/parent.c:16498)
  File "parent.pyx", line 2373, in sage.structure.parent.Parent.an_element (sage/structure/parent.c:16442)
  File "parent.pyx", line 2441, in sage.structure.parent.Parent._an_element_ (sage/structure/parent.c:17033)
NotImplementedError: please implement _an_element_ for <class '__main__.WrongSemigroup_with_category'>
------------------------------------------------------------
running ._test_elements_eq() . . . fail
Traceback (most recent call last):
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
    test_method(tester = tester)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/sets_cat.py", line 551, in _test_elements_eq
    elements = list(self.some_elements())+[None, 0]
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/finite_semigroups.py", line 144, in __iter__
    return TransitiveIdeal(self.succ_generators(side = "right"), self.semigroup_generators()).__iter__()
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/finite_semigroups.py", line 128, in succ_generators
    generators = self.semigroup_generators()
  File "parent.pyx", line 811, in sage.structure.parent.Parent.__getattr__ (sage/structure/parent.c:6279)
  File "parent.pyx", line 323, in sage.structure.parent.getattr_from_other_class (sage/structure/parent.c:3164)
AttributeError: 'WrongSemigroup_with_category' object has no attribute 'semigroup_generators'
------------------------------------------------------------
running ._test_enumerated_set_contains() . . . fail
Traceback (most recent call last):
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
    test_method(tester = tester)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/enumerated_sets.py", line 581, in _test_enumerated_set_contains
    for w in self:
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/finite_semigroups.py", line 144, in __iter__
    return TransitiveIdeal(self.succ_generators(side = "right"), self.semigroup_generators()).__iter__()
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/finite_semigroups.py", line 128, in succ_generators
    generators = self.semigroup_generators()
  File "parent.pyx", line 811, in sage.structure.parent.Parent.__getattr__ (sage/structure/parent.c:6279)
  File "parent.pyx", line 323, in sage.structure.parent.getattr_from_other_class (sage/structure/parent.c:3164)
AttributeError: 'WrongSemigroup_with_category' object has no attribute 'semigroup_generators'
------------------------------------------------------------
running ._test_enumerated_set_iter_cardinality() . . . pass
running ._test_enumerated_set_iter_list() . . . pass
running ._test_eq() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . fail
Traceback (most recent call last):
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
    test_method(tester = tester)
  File "sage_object.pyx", line 396, in sage.structure.sage_object.SageObject._test_pickling (sage/structure/sage_object.c:3212)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python/unittest.py", line 350, in failUnlessEqual
    (msg or '%r != %r' % (first, second))
AssertionError: <class '__main__.WrongSemigroup_with_category'> != <class '__main__.WrongSemigroup_with_category'>
------------------------------------------------------------
running ._test_some_elements() . . . fail
Traceback (most recent call last):
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
    test_method(tester = tester)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/sets_cat.py", line 643, in _test_some_elements
    for x in elements:
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/finite_semigroups.py", line 144, in __iter__
    return TransitiveIdeal(self.succ_generators(side = "right"), self.semigroup_generators()).__iter__()
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/categories/finite_semigroups.py", line 128, in succ_generators
    generators = self.semigroup_generators()
  File "parent.pyx", line 811, in sage.structure.parent.Parent.__getattr__ (sage/structure/parent.c:6279)
  File "parent.pyx", line 323, in sage.structure.parent.getattr_from_other_class (sage/structure/parent.c:3164)
AttributeError: 'WrongSemigroup_with_category' object has no attribute 'semigroup_generators'
------------------------------------------------------------
The following tests failed: _test_an_element, _test_associativity, _test_elements, _test_elements_eq, _test_enumerated_set_contains, _test_pickling, _test_some_elements

So suppose you want to implement a new parent in Sage. You need to define a class for the parents, a class for the elements, and choose a category. We'll use the example of localization from the coercion primer.

PrincipalIdealDomain

class Localization(Ring):
   def __init__(self, primes):
       """
       Localization of `\ZZ` away from primes.
       """
       Ring.__init__(self, base=ZZ., category=PrincipalIdealDomains())
       self._primes = primes
       self._populate_coercion_lists_()

   def _repr_(self):
       """
       How to print self.
       """
       return "%s localized at %s" % (self.base(), self._primes)

   def _element_constructor_(self, x):
       """
       Make sure x is a valid member of self, and return the constructed element.
       """
       if isinstance(x, LocalizationElement):
           x = x._value
       else:
           x = QQ(x)
       for p, e in x.denominator().factor():
           if p not in self._primes:
               raise ValueError, "Not integral at %s" % p
       return LocalizationElement(self, x)

   def _coerce_map_from_(self, S):
       """
       The only things that coerce into this ring are:

       - the integer ring

       - other localizations away from fewer primes
       """
       if S is ZZ:
           return True
       elif isinstance(S, Localization):
           return all(p in self._primes for p in S._primes)


class LocalizationElement(RingElement):

    def __init__(self, parent, x):
        RingElement.__init__(self, parent)
        self._value = x


    # We're just printing out this way to make it easy to see what's going on in the examples.

    def _repr_(self):
        return "LocalElt(%s)" % self._value
       
    def __cmp__(self, other):
        return cmp(self._value, other._value)

    # Now define addition, subtraction, and multiplication of elements.
    # Note that left and right always have the same parent.

    def _add_(left, right):
        return LocalizationElement(left.parent(), left._value + right._value)

    def _sub_(left, right):
        return LocalizationElement(left.parent(), left._value - right._value)

    def _mul_(left, right):
        return LocalizationElement(left.parent(), left._value * right._value)

    # The basering was set to ZZ, so c is guaranteed to be in ZZ

    def _rmul_(self, c):
        return LocalizationElement(self.parent(), c * self._value)

    def _lmul_(self, c):
        return LocalizationElement(self.parent(), self._value * c)

Traceback (most recent call last):           self._primes = primes
  File "", line 1, in <module>
    
  File "/private/var/folders/LA/LA5R72GVGf4twc05wSfazU+++TI/-Tmp-/tmpfG0KU_/___code___.py", line 7
    Ring.__init__(self, base=ZZ., category=PrincipalIdealDomains())
                                ^
SyntaxError: invalid syntax

R = Localization([2,7]); R

Integer Ring localized at [2, 7]

R.category()

Category of principal ideal domains

TestSuite(R).run()

Failure in _test_category:
  

Traceback (most recent call last):
    File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
      test_method(tester = tester)
    File "element.pyx", line 498, in sage.structure.element.Element._test_category (sage/structure/element.c:3984)
    File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python/unittest.py", line 325, in failUnless
      if not expr: raise self.failureException, msg
  AssertionError
  ------------------------------------------------------------
  The following tests failed: _test_category
Failure in _test_elements
Failure in _test_pickling:
Traceback (most recent call last):
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
    test_method(tester = tester)
  File "sage_object.pyx", line 396, in sage.structure.sage_object.SageObject._test_pickling (sage/structure/sage_object.c:3212)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python/unittest.py", line 350, in failUnlessEqual
    (msg or '%r != %r' % (first, second))
AssertionError: Integer Ring localized at [2, 7] != Integer Ring localized at [2, 7]
------------------------------------------------------------
The following tests failed: _test_elements, _test_pickling

TestSuite(R(77)).run()

Failure in _test_category:

Traceback (most recent call last):
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
    test_method(tester = tester)
  File "element.pyx", line 498, in sage.structure.element.Element._test_category (sage/structure/element.c:3984)
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python/unittest.py", line 325, in failUnless
    if not expr: raise self.failureException, msg
AssertionError
------------------------------------------------------------
The following tests failed: _test_category

class Localization2(Ring):
    def __init__(self, primes):
        r"""
        Localization of `\ZZ` away from primes.
        """
        Ring.__init__(self, base=ZZ, category=PrincipalIdealDomains())
        self._primes = primes
        self._populate_coercion_lists_([ZZ])

    def _repr_(self):
        """
        How to print self.
        """
        return "%s localized at %s" % (self.base(), self._primes)

    def _coerce_map_from_(self, S):
        """
        The only things that coerce into this ring are:

        - the integer ring

        - other localizations away from fewer primes
        """
        if S is ZZ:
            return True
        elif isinstance(S, Localization):
            return all(p in self._primes for p in S._primes)

    class Element(sage.structure.element.Element):
        def __init__(self, x, parent):
            x = QQ(x)
            for p, e in x.denominator().factor():
                if p not in parent._primes:
                    raise ValueError, "Not integral at %s" % p
            sage.structure.element.Element.__init__(self, parent)
            self._value = x

        # We're just printing out this way to make it easy to see what's going on in the examples.

        def _repr_(self):
            return "LocalElt(%s)" % self._value
       
        def __cmp__(self, other):
            return cmp(self._value, other._value)

        # Now define addition, subtraction, and multiplication of elements.
        # Note that left and right always have the same parent.

        def _add_(left, right):
            return Element(left.parent(), left._value + right._value)

        def _sub_(left, right):
            return Element(left.parent(), left._value - right._value)

        def _mul_(left, right):
            return Element(left.parent(), left._value * right._value)

        # The basering was set to ZZ, so c is guaranteed to be in ZZ

        def _rmul_(self, c):
            return Element(self.parent(), c * self._value)

        def _lmul_(self, c):
            return Element(self.parent(), self._value * c)

S = Localization2([3,17])

S(77/9)

LocalElt(77/9)

TestSuite(S(77/9)).run()

Failure in _test_pickling:

Traceback (most recent call last):
  File "/Users/roed/sage/sage-4.8.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
    test_method(tester = tester)
  File "sage_object.pyx", line 396, in sage.structure.sage_object.SageObject._test_pickling (sage/structure/sage_object.c:3193)
  File "sage_object.pyx", line 875, in sage.structure.sage_object.dumps (sage/structure/sage_object.c:8689)
  File "sage_object.pyx", line 217, in sage.structure.sage_object.SageObject.dumps (sage/structure/sage_object.c:2299)
PicklingError: Can't pickle <class '__main__.Element'>: attribute lookup __main__.Element failed
------------------------------------------------------------
The following tests failed: _test_pickling

S(77)._test_pickling()

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_282.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("Uyg3NykuX3Rlc3RfcGlja2xpbmcoKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/LA/LA5R72GVGf4twc05wSfazU+++TI/-Tmp-/tmpMTSivF/___code___.py", line 3, in <module>
    exec compile(u'S(_sage_const_77 )._test_pickling()' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "sage_object.pyx", line 396, in sage.structure.sage_object.SageObject._test_pickling (sage/structure/sage_object.c:3193)
  File "sage_object.pyx", line 875, in sage.structure.sage_object.dumps (sage/structure/sage_object.c:8689)
  File "sage_object.pyx", line 217, in sage.structure.sage_object.SageObject.dumps (sage/structure/sage_object.c:2299)
cPickle.PicklingError: Can't pickle <class '__main__.Element'>: attribute lookup __main__.Element failed

type(S(77))

<class '__main__.LocalizationElement'>

isinstance(R(77),R.category().element_class)

False