15709
Comment:

← Revision 27 as of 20170203 19:57:11 ⇥
21490

Deletions are marked like this.  Additions are marked like this. 
Line 1:  Line 1: 
<<TableOfContents>> 

Line 5:  Line 8: 
''The primary goal of the coercion is to be able to transparently do arithmetic, comparisons, etc. between elements of distinct sets.'' As a concrete example, when one writes $1 + 1/2$ one wants to perform arithmetic on the operands as rational numbers, despite the left being an integer. This makes sense given the obvious and natural inclusion of the integers into the rational numbers. The goal of the coercion system is to facilitate this (and more complicated arithmetic) without having to explicitly map everything over into the same domain, and at the same time being strict enough to not resolve ambiguity or accept nonsense. Here are some examples 
''The primary goal of coercion is to be able to transparently do arithmetic, comparisons, etc. between elements of distinct sets.'' As a concrete example, when one writes $1 + 1/2$ one wants to perform arithmetic on the operands as rational numbers, despite the left being an integer. This makes sense given the obvious and natural inclusion of the integers into the rational numbers. The goal of the coercion system is to facilitate this (and more complicated arithmetic) without having to explicitly map everything over into the same domain, and at the same time being strict enough to not resolve ambiguity or accept nonsense. Here are some examples: 
Line 23:  Line 26: 
Assume we want to do $a + b$ with $a \in R$ and $b \in S$  
Line 33:  Line 35: 
Parents objects in concrete categories, and Elements are their members. Parents are firstclass objects. Most things Sage either are parents or have a parent. Whenever one sees the word ''Parent'' one can think ''Set''. Here are some examples:  Parents are objects in concrete categories, and Elements are their members. Parents are firstclass objects. Most things in Sage are either parents or have a parent. Typically whenever one sees the word ''Parent'' one can think ''Set''. Here are some examples: 
Line 84:  Line 87: 
In fact, under the hood, a special parent "The set of all Python objects of type T" is used in these cases.  In fact, under the hood, a special kind of parent "The set of all Python objects of type T" is used in these cases. 
Line 116:  Line 119: 
sage: GF(71)(1/5) 57 sage: ZZ(1/2) ... TypeError: no conversion of this rational to integer 

Line 123:  Line 131: 
sage: ZZ(GF(5)(14)) 4 

Line 131:  Line 141: 
On the other hand, Sage has the notion of a '''coercion''' which is a canonical morphism (occasionally up to a conventional choice made by developers) between parents. A coercion from one parent to another '''must''' be defined on the whole domain, and always succeeds. As it may be invoked implicitly, is should be obvious and natural (in both the mathematically rigorous and colloquial sense of the word). Up to inescapable rounding issues that arise with inexact representations, these coercion morphisms should all commute. They is can be discovered via the {{{has_coerce_map_from}}} method, and if needed explicitly invoked with the {{{coerce}}} method. 
On the other hand, Sage has the notion of a '''coercion''', which is a canonical morphism (occasionally up to a conventional choice made by developers) between parents. A coercion from one parent to another '''must''' be defined on the whole domain, and always succeeds. As it may be invoked implicitly, it should be obvious and natural (in both the mathematically rigorous and colloquial sense of the word). Up to inescapable rounding issues that arise with inexact representations, these coercion morphisms should all commute. They can be discovered via the {{{has_coerce_map_from}}} method, and if needed explicitly invoked with the {{{coerce}}} method. 
Line 151:  Line 161: 
TypeError: no cannonical coercion from Rational Field to Univariate Polynomial Ring in x over Integer Ring }}} == Basic Rules == Suppose we want to add two element, a and b, whose parents are R and S respectively. When we type {{{a+b}}} then 1. If R {{{is}}} S, call a._add_(b) 1. If there is a coercion $\phi: S \rightarrow R$, call a._add_($\phi$(b)) 1. If there is a coercion $\phi: R \rightarrow S$, call $\phi$(a)._add_(b) 1. Look for $T$ such that there is a coercion $\phi_S: S \rightarrow Z$ and $\phi_R: R \rightarrow Z$, call $\phi$(a)._add_($\phi$(b)) 
TypeError: no canonical coercion from Rational Field to Univariate Polynomial Ring in x over Integer Ring }}} == Basic Arithmetic Rules == Suppose we want to add two element, a and b, whose parents are A and B respectively. When we type {{{a+b}}} then 1. If A {{{is}}} B, call a._add_(b) 1. If there is a coercion $\phi: B \rightarrow A$, call a._add_($\phi$(b)) 1. If there is a coercion $\phi: A \rightarrow B$, call $\phi$(a)._add_(b) 1. Look for $Z$ such that there is a coercion $\phi_A: A \rightarrow Z$ and $\phi_B: B \rightarrow Z$, call $\phi_A$(a)._add_($\phi_B$(b)) The same rules are used for subtraction, multiplication, and division. This logic is embedded in a coercion model object, which can be obtained and queried. 
Line 170:  Line 182: 
sage: cm.bin_op(77, 9, gcd) 1 
<sage.structure.coerce.CoercionModel_cache_maps object at 0x2f65960> 
Line 180:  Line 191: 
Line 194:  Line 206: 
There are also '''actions'''.  The coercion model can be used directly for any binary operation (callable taking two arguments). {{{ sage: cm.bin_op(77, 9, gcd) 1 }}} There are also '''actions''' in the sense that a field $K$ acts on a module over $K$, or a permutation group acts on a set. These are discovered between steps 1 and 2 above. 
Line 231:  Line 249: 
Special methods to implement: * Arithmetic on elements{{{_add_, _sub_, _mul_, _div_}}} 
=== Methods to implement === * Arithmetic on Elements{{{_add_, _sub_, _mul_, _div_}}} 
Line 236:  Line 254: 
both operands are ``guaranteed`` to have the same Parent at this point.  both operands are ''guaranteed'' to have the same Parent at this point. 
Line 246:  Line 264: 
There is a utility function {{{Parent._coerce_map_via}}} which makes it easy to specify coercions to self via a list of basecases. 

Line 250:  Line 266: 
Suppose one wants R to act on S. Some examples of this could be $R = \QQ, S = \QQ[x]$ or $R = Gal(S/\QQ)$ where $S$ is a number field.  Suppose one wants R to act on S. Some examples of this could be $R = \mathbb{Q}, S = \mathbb{Q}[x]$ or $R = Gal(S/\mathbb{Q})$ where $S$ is a number field. 
Line 255:  Line 271: 
The argument to {{{_rmul_}}} and {{{_lmul_}}} are ``guaranteed`` to be Elements of the base of $S$ (with coercion happening beforehand if necessary).  The argument to {{{_rmul_}}} and {{{_lmul_}}} are ''guaranteed'' to be Elements of the base of $S$ (with coercion happening beforehand if necessary). 
Line 258:  Line 274: 
There is no constraint on the type or parents of objects passed to these methods, raise a {{{TypeError}}} or {{{ValueError}}}  There is no constraint on the type or parents of objects passed to these methods; raise a {{{TypeError}}} or {{{ValueError}}} 
Line 260:  Line 276: 
* If $R$ acts on $S$ ``or`` $S$ acts on $R$, one may override {{{R._get_action_}}} to return an actual {{{Action}}} object to be used. 
'''Important''' Due to potential confusion, it has been decided to rename these to {{{_act_on_}}} and {{{_acted_upon_}}} * If either $R$ acts on $S$ ``or`` $S$ acts on $R$, one may implement {{{R._get_action_}}} to return an actual {{{Action}}} object to be used. 
Line 264:  Line 281: 
* Element conversion/construction for Parents {{{_element_constructor_}}} ''not'' {{{__call__}}} The {{{Parent.__call__}}} method dispatches to {{{_element_constructor_}}}. When someone writes R(x, foo=y), 
* Element conversion/construction for Parents: use {{{_element_constructor_}}} ''not'' {{{__call__}}} The {{{Parent.__call__}}} method dispatches to {{{_element_constructor_}}}. When someone writes R(x, ...), 
Line 270:  Line 287: 
Parents may also call {{{self._populate_coercion_lists_}}} method in their {{{__init__}}} functions to pass any callable for use instead of {{{_element_constructor_}}}, provide a list of Parents with coercions to self (as an alternative to implementing {{{_coerce_map_from_}}}), provide special construction methods (like {{{_integer_}}} for ZZ), etc. This also allows one to specify a single coercion embedding ''out'' of self (whereas the rest of the coercion functions all specify maps ''into'' self). There is extensive documentation in the docstring of that method. Sometimes a '''[[/examples  simple example ]]''' is worth a thousand words. === What is provided === 
Parents may also call the {{{self._populate_coercion_lists_}}} method in their {{{__init__}}} functions to pass any callable for use instead of {{{_element_constructor_}}}, provide a list of Parents with coercions to self (as an alternative to implementing {{{_coerce_map_from_}}}), provide special construction methods (like {{{_integer_}}} for ZZ), etc. This also allows one to specify a single coercion embedding ''out'' of self (whereas the rest of the coercion functions all specify maps ''into'' self). There is extensive documentation in the docstring of the {{{_populate_coercion_lists_}}} method. === Example === Sometimes a '''[[/example  simple example ]]''' is worth a thousand words. === Provided Methods === 
Line 279:  Line 297: 
This provides a consistent interface for element construction. Let R be a Parent and assume the user types R(x), where s has parent X.  This provides a consistent interface for element construction. In particular, it makes sure that conversion always gives the same result as coercion, if a coercion exists. (This used to be violated for some Rings in Sage as the code for conversion and coercion got edited separately.) Let R be a Parent and assume the user types R(x), where x has parent X. 
Line 292:  Line 310: 
(*) Unless there is a "copy" keyword like R(x, copy=False) (**) Technically, a generic morphism is created from X to R, which may use magic methods like {{{_integer_}}} or other data provided by {{{_populate_coercion_lists_}}}. 
(*) Unless there is a "copy" keyword like R(x, copy=False) (**) Technically, a generic morphism is created from X to R, which may use magic methods like {{{_integer_}}} or other data provided by {{{_populate_coercion_lists_}}}. * {{{coerce}}} Coerces elements into self, raising a type error if there is no coercion map. 
Line 320:  Line 341: 
sage: QQ.construction() (FractionField, Integer Ring) sage: ZZ.construction() # None 

Line 322:  Line 347: 
sage: c, R = RR.construction()  
Line 325:  Line 349: 
sage: c, R = RR.construction()  
Line 330:  Line 355: 
sage: QQ.construction() (FractionField, Integer Ring) sage: ZZ.construction() 

Line 344:  Line 366: 
Given a Parent R and S, such that there is no coercion either from R to S or from S to R, one can find a common Z with coercions $R \rightarrow Z$ and $S \rightarrow Z$ by considering the sequence of construction functors to get from a common ancestor to both R and S.  Given Parents R and S, such that there is no coercion either from R to S or from S to R, one can find a common Z with coercions $R \rightarrow Z$ and $S \rightarrow Z$ by considering the sequence of construction functors to get from a common ancestor to both R and S. 
Line 358:  Line 380: 
The common ancestor is $Z$ and our options for Z are $\Frac(\Z[x])$ or $\Frac(Z)[x]$. In Sage we choose the later, treating the fraction field functor as binding "more tightly" than the polynomial functor, as most people agree that $\Q[x]$ is the more natural choice. The same procedure is applied to more complicated Parents, returning a new Parent if one can be unambiguously determined. {{{ sage: sage.categories.pushout.pushout(Frac(ZZ['x,y,z']), QQ['t,u,x']) Fraction Field of Multivariate Polynomial Ring in t, u, x, y, z over Rational Field }}} 
The common ancestor is $\mathbb{Z}$ and our options for Z are $Frac(\mathbb{Z}[x])$ or $Frac(\mathbb{Z})[x]$. In Sage we choose the later, treating the fraction field functor as binding "more tightly" than the polynomial functor, as most people agree that $\mathbb{Q}[x]$ is the more natural choice. The same procedure is applied to more complicated Parents, returning a new Parent if one can be unambiguously determined. {{{ sage: sage.categories.pushout.pushout(Frac(ZZ['x,y,z']), QQ['z, t']) Fraction Field of Multivariate Polynomial Ring in x, y, z, t over Rational Field }}} = Coercion Example = Here is a minimal example of setting up a simple Ring that handles coercion. (It is easy to imagine much more sophisticated and powerful localizations, but that would obscure the main points being made here.) {{{ class Localization(Ring): def __init__(self, primes): """ Localization of $\Z$ away from primes. """ Ring.__init__(self, base=ZZ) 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._x 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 # 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) That's all there is to it. Now we can test it out: sage: R = Localization([2]); R Integer Ring localized at [2] sage: R(1) LocalElt(1) sage: R(1/2) LocalElt(1/2) sage: R(1/3) Traceback (most recent call last): ... ValueError: Not integral at 3 sage: R.coerce(1) LocalElt(1) sage: R.coerce(1/4) Traceback (click to the left for traceback) ... TypeError: no cannonical coercion from Rational Field to Integer Ring localized at [2] sage: R(1/2) + R(3/4) LocalElt(5/4) sage: R(1/2) + 5 LocalElt(11/2) sage: 5 + R(1/2) LocalElt(11/2) sage: R(1/2) + 1/7 Traceback (most recent call last): ... TypeError: unsupported operand parent(s) for '+': 'Integer Ring localized at [2]' and 'Rational Field' sage: R(3/4) * 7 LocalElt(21/4) sage: R.get_action(ZZ) Right scalar multiplication by Integer Ring on Integer Ring localized at [2] sage: cm = sage.structure.element.get_coercion_model() sage: cm.explain(R, ZZ, operator.add) Coercion on right operand via Conversion map: From: Integer Ring To: Integer Ring localized at [2] Arithmetic performed after coercions. Result lives in Integer Ring localized at [2] Integer Ring localized at [2] sage: cm.explain(R, ZZ, operator.mul) Action discovered. Right scalar multiplication by Integer Ring on Integer Ring localized at [2] Result lives in Integer Ring localized at [2] Integer Ring localized at [2] sage: R6 = Localization([2,3]); R6 Integer Ring localized at [2, 3] sage: R6(1/3)  R(1/2) LocalElt(1/6) sage: parent(R6(1/3)  R(1/2)) Integer Ring localized at [2, 3] sage: R.has_coerce_map_from(ZZ) True sage: R.coerce_map_from(ZZ) Conversion map: From: Integer Ring To: Integer Ring localized at [2] sage: R6.coerce_map_from(R) Conversion map: From: Integer Ring localized at [2] To: Integer Ring localized at [2, 3] sage: R6.coerce(R(1/2)) LocalElt(1/2) sage: cm.explain(R, R6, operator.mul) Coercion on left operand via Conversion map: From: Integer Ring localized at [2] To: Integer Ring localized at [2, 3] Arithmetic performed after coercions. Result lives in Integer Ring localized at [2, 3] Integer Ring localized at [2, 3] }}} 
Contents
Preliminaries
What is coercion all about?
The primary goal of coercion is to be able to transparently do arithmetic, comparisons, etc. between elements of distinct sets.
As a concrete example, when one writes 1 + 1/2 one wants to perform arithmetic on the operands as rational numbers, despite the left being an integer. This makes sense given the obvious and natural inclusion of the integers into the rational numbers. The goal of the coercion system is to facilitate this (and more complicated arithmetic) without having to explicitly map everything over into the same domain, and at the same time being strict enough to not resolve ambiguity or accept nonsense. Here are some examples:
sage: 1 + 1/2 3/2 sage: R.<x,y> = ZZ[] sage: R Multivariate Polynomial Ring in x, y over Integer Ring sage: parent(x) Multivariate Polynomial Ring in x, y over Integer Ring sage: parent(1/3) Rational Field sage: x+1/3 x + 1/3 sage: parent(x+1/3) Multivariate Polynomial Ring in x, y over Rational Field sage: GF(5)(1) + CC(I) Traceback (most recent call last): ... TypeError: unsupported operand parent(s) for '+': 'Finite Field of size 5' and 'Complex Field with 53 bits of precision'
Parents and Elements
Parents are objects in concrete categories, and Elements are their members. Parents are firstclass objects. Most things in Sage are either parents or have a parent. Typically whenever one sees the word Parent one can think Set. Here are some examples:
sage: parent(1) Integer Ring sage: parent(1) is ZZ True sage: ZZ Integer Ring sage: parent(1.50000000000000000000000000000000000) Real Field with 123 bits of precision sage: parent(x) Symbolic Ring sage: x^sin(x) x^sin(x) sage: R.<t> = Qp(5)[] sage: f = t^35; f (1 + O(5^20))*t^3 + (4*5 + 4*5^2 + 4*5^3 + 4*5^4 + 4*5^5 + 4*5^6 + 4*5^7 + 4*5^8 + 4*5^9 + 4*5^10 + 4*5^11 + 4*5^12 + 4*5^13 + 4*5^14 + 4*5^15 + 4*5^16 + 4*5^17 + 4*5^18 + 4*5^19 + 4*5^20 + O(5^21)) sage: parent(f) Univariate Polynomial Ring in t over 5adic Field with capped relative precision 20 sage: f = EllipticCurve('37a').lseries().taylor_series(10); f 0.997997869801216 + 0.00140712894524925*z  0.000498127610960097*z^2 + 0.000118835596665956*z^3  0.0000215906522442707*z^4 + (3.20363155418419e6)*z^5 + O(z^6) sage: parent(f) Power Series Ring in z over Complex Field with 53 bits of precision
There is an important distinction between Parents and types
sage: a = GF(5).random_element() sage: b = GF(7).random_element() sage: type(a) <type 'sage.rings.integer_mod.IntegerMod_int'> sage: type(b) <type 'sage.rings.integer_mod.IntegerMod_int'> sage: type(a) == type(b) True sage: parent(a) Finite Field of size 5 sage: parent(a) == parent(b) False
However, nonsage objects don't really have parents, but we still want to be able to reason with them, so their type is used instead.
sage: a = int(10) sage: parent(a) <type 'int'>
In fact, under the hood, a special kind of parent "The set of all Python objects of type T" is used in these cases.
Note that parents are not always as tight as possible.
sage: parent(1/2) Rational Field sage: parent(2/1) Rational Field
Maps between Parents
Many parents come with maps to and from other parents.
Sage makes a distinction between being able to convert between various parents, and coerce between them. Conversion is explicit and tries to make sense of an object in the target domain if at all possible. It is invoked by calling
sage: ZZ(5) 5 sage: ZZ(10/5) 2 sage: QQ(10) 10 sage: parent(QQ(10)) Rational Field sage: a = GF(5)(2); a 2 sage: parent(a) Finite Field of size 5 sage: parent(ZZ(a)) Integer Ring sage: GF(71)(1/5) 57 sage: ZZ(1/2) ... TypeError: no conversion of this rational to integer
Conversions need not be canonical (they may for example involve a choice of lift) or even make sense mathematically (e.g. constructions of some kind).
sage: ZZ("123") 123 sage: ZZ(GF(5)(14)) 4 sage: ZZ['x']([4,3,2,1]) x^3 + 2*x^2 + 3*x + 4 sage: a = Qp(5, 10)(1/3); a 2 + 3*5 + 5^2 + 3*5^3 + 5^4 + 3*5^5 + 5^6 + 3*5^7 + 5^8 + 3*5^9 + O(5^10) sage: ZZ(a) 6510417
On the other hand, Sage has the notion of a coercion, which is a canonical morphism (occasionally up to a conventional choice made by developers) between parents. A coercion from one parent to another must be defined on the whole domain, and always succeeds. As it may be invoked implicitly, it should be obvious and natural (in both the mathematically rigorous and colloquial sense of the word). Up to inescapable rounding issues that arise with inexact representations, these coercion morphisms should all commute.
They can be discovered via the has_coerce_map_from method, and if needed explicitly invoked with the coerce method.
sage: QQ.has_coerce_map_from(ZZ) True sage: QQ.has_coerce_map_from(RR) False sage: ZZ['x'].has_coerce_map_from(QQ) False sage: ZZ['x'].has_coerce_map_from(ZZ) True sage: ZZ['x'].coerce(5) 5 sage: ZZ['x'].coerce(5).parent() Univariate Polynomial Ring in x over Integer Ring sage: ZZ['x'].coerce(5/1) Traceback (most recent call last): ... TypeError: no canonical coercion from Rational Field to Univariate Polynomial Ring in x over Integer Ring
Basic Arithmetic Rules
Suppose we want to add two element, a and b, whose parents are A and B respectively. When we type a+b then
If A is B, call a._add_(b)
If there is a coercion \phi: B \rightarrow A, call a._add_(\phi(b))
If there is a coercion \phi: A \rightarrow B, call \phi(a)._add_(b)
Look for Z such that there is a coercion \phi_A: A \rightarrow Z and \phi_B: B \rightarrow Z, call \phi_A(a)._add_(\phi_B(b))
The same rules are used for subtraction, multiplication, and division. This logic is embedded in a coercion model object, which can be obtained and queried.
sage: parent(1 + 1/2) Rational Field sage: cm = sage.structure.element.get_coercion_model() <sage.structure.coerce.CoercionModel_cache_maps object at 0x2f65960> sage: cm.explain(ZZ, QQ) Coercion on left operand via Natural morphism: From: Integer Ring To: Rational Field Arithmetic performed after coercions. Result lives in Rational Field Rational Field sage: cm.explain(ZZ['x','y'], QQ['x']) Coercion on left operand via Call morphism: From: Multivariate Polynomial Ring in x, y over Integer Ring To: Multivariate Polynomial Ring in x, y over Rational Field Coercion on right operand via Call morphism: From: Univariate Polynomial Ring in x over Rational Field To: Multivariate Polynomial Ring in x, y over Rational Field Arithmetic performed after coercions. Result lives in Multivariate Polynomial Ring in x, y over Rational Field Multivariate Polynomial Ring in x, y over Rational Field
The coercion model can be used directly for any binary operation (callable taking two arguments).
sage: cm.bin_op(77, 9, gcd) 1
There are also actions in the sense that a field K acts on a module over K, or a permutation group acts on a set. These are discovered between steps 1 and 2 above.
sage: cm.explain(ZZ['x'], ZZ, operator.mul) Action discovered. Right scalar multiplication by Integer Ring on Univariate Polynomial Ring in x over Integer Ring Result lives in Univariate Polynomial Ring in x over Integer Ring Univariate Polynomial Ring in x over Integer Ring sage: cm.explain(ZZ['x'], ZZ, operator.div) Action discovered. Right inverse action by Rational Field on Univariate Polynomial Ring in x over Integer Ring with precomposition on right by Natural morphism: From: Integer Ring To: Rational Field Result lives in Univariate Polynomial Ring in x over Rational Field Univariate Polynomial Ring in x over Rational Field sage: f = QQ.coerce_map_from(ZZ) sage: f(3).parent() Rational Field sage: QQ.coerce_map_from(int) Native morphism: From: Set of Python objects of type 'int' To: Rational Field sage: QQ.has_coerce_map_from(RR) False sage: QQ['x'].get_action(QQ) Right scalar multiplication by Rational Field on Univariate Polynomial Ring in x over Rational Field sage: (QQ^2).get_action(QQ) Right scalar multiplication by Rational Field on Vector space of dimension 2 over Rational Field sage: QQ['x'].get_action(RR) Right scalar multiplication by Real Field with 53 bits of precision on Univariate Polynomial Ring in x over Rational Field
How to Implement
Methods to implement
Arithmetic on Elements_add_, _sub_, _mul_, _div_
This is where the binary arithmetic operators should be implemented. Unlike Python's __add__, both operands are guaranteed to have the same Parent at this point.
Coercion for Parents _coerce_map_from_
Given two parents R and S, R._coerce_map_from_(S) is called to determine if there is a coercion \phi: S \rightarrow R. Note that the function is called on the potential codomain. To indicate that there is no coercion from S to R (self), return False or None. This is the default behavior. If there is a coercion, return True (in which case an morphism using R._element_constructor_ will be created) or an actual Morphism object with S as the domain and R as the codomain.
Actions for Parents _get_action_ or _rmul_, _lmul_, _r_action_, _l_action_
Suppose one wants R to act on S. Some examples of this could be R = \mathbb{Q}, S = \mathbb{Q}[x] or R = Gal(S/\mathbb{Q}) where S is a number field. There are several ways to implement this:
If R is the base of S (as in the first example), simply implement _rmul_ and/or _lmul_ on the Elements of S.
In this case r * s gets handled as s._rmul_(r) and s * r as s._lmul_(r). The argument to _rmul_ and _lmul_ are guaranteed to be Elements of the base of S (with coercion happening beforehand if necessary).
If R acts on S, one can alternatively define the methods _r_action_ and/or _l_action_ on the Elements of R.
There is no constraint on the type or parents of objects passed to these methods; raise a TypeError or ValueError if the wrong kind of object is passed in to indicate the action is not appropriate here. Important Due to potential confusion, it has been decided to rename these to _act_on_ and _acted_upon_
If either R acts on S or S acts on R, one may implement R._get_action_ to return an actual Action object to be used.
 This is how nonmultiplicative actions must be implemented, and is the most powerful (and completed) way to do things.
Element conversion/construction for Parents: use _element_constructor_ not __call__
The Parent.__call__ method dispatches to _element_constructor_. When someone writes R(x, ...), this is the method that eventually gets called in most cases. See the documentation on the __call__ method below.
Parents may also call the self._populate_coercion_lists_ method in their __init__ functions to pass any callable for use instead of _element_constructor_, provide a list of Parents with coercions to self (as an alternative to implementing _coerce_map_from_), provide special construction methods (like _integer_ for ZZ), etc. This also allows one to specify a single coercion embedding out of self (whereas the rest of the coercion functions all specify maps into self). There is extensive documentation in the docstring of the _populate_coercion_lists_ method.
Example
Sometimes a simple example is worth a thousand words.
Provided Methods
__call__
 This provides a consistent interface for element construction. In particular, it makes sure that conversion always gives the same result as coercion, if a coercion exists. (This used to be violated for some Rings in Sage as the code for conversion and coercion got edited separately.) Let R be a Parent and assume the user types R(x), where x has parent X. Roughly speaking, the following occurs:
If X is R, return x (*)
If there is a coercion f: X \rightarrow R, return f(x)
If there is a coercion f: R \rightarrow X, try to return {f^{1}}(x)
Return R._element_constructor_(x) (**)
 (*) Unless there is a "copy" keyword like R(x, copy=False)
(**) Technically, a generic morphism is created from X to R, which may use magic methods like _integer_ or other data provided by _populate_coercion_lists_.
 This provides a consistent interface for element construction. In particular, it makes sure that conversion always gives the same result as coercion, if a coercion exists. (This used to be violated for some Rings in Sage as the code for conversion and coercion got edited separately.) Let R be a Parent and assume the user types R(x), where x has parent X. Roughly speaking, the following occurs:
coerce
 Coerces elements into self, raising a type error if there is no coercion map.
coerce_map_from, convert_map_from
Returns an actual Morphism object to coerce/convert from another Parent to self. Barring direct construction of elements of R, R.convert_map_from(S) will provide a callable Python object which is the fastest way to convert elements of S to elements of R. From Cython, it can be invoked via the cdef _call_ method.
has_coerce_map_from
Returns True or False depending on whether or not there is a coercion. R.has_coerce_map_from(S) is shorthand for R.coerce_map_from(S) is not None
get_action
This will unwind all the _rmul_, _lmul_, _r_action_, _l_action_, ... methods to provide an actual Action object, if one exists.
Discovering new parents
New parents are discovered using an algorithm in sage/category/pushout.py. The fundamental idea is that most Parents in Sage are constructed from simpler objects via various functors. These are accessed via the construction method, which returns a (simpler) Parent along with a functor with which one can create self.
sage: CC.construction() (AlgebraicClosureFunctor, Real Field with 53 bits of precision) sage: RR.construction() (CompletionFunctor, Rational Field) sage: QQ.construction() (FractionField, Integer Ring) sage: ZZ.construction() # None sage: Qp(5).construction() (CompletionFunctor, Rational Field) sage: QQ.completion(5, 100) 5adic Field with capped relative precision 100 sage: c, R = RR.construction() sage: a = CC.construction()[0] sage: a.commutes(c) False sage: RR == c(QQ) True sage: sage.categories.pushout.construction_tower(Frac(CDF['x'])) [(None, Fraction Field of Univariate Polynomial Ring in x over Complex Double Field), (FractionField, Univariate Polynomial Ring in x over Complex Double Field), (Poly[x], Complex Double Field), (AlgebraicClosureFunctor, Real Double Field), (CompletionFunctor, Rational Field), (FractionField, Integer Ring)]
Given Parents R and S, such that there is no coercion either from R to S or from S to R, one can find a common Z with coercions R \rightarrow Z and S \rightarrow Z by considering the sequence of construction functors to get from a common ancestor to both R and S. We then use a heuristic algorithm to interleave these constructors in an attempt to arrive at a suitable Z (if one exists). For example:
sage: ZZ['x'].construction() (Poly[x], Integer Ring) sage: QQ.construction() (FractionField, Integer Ring) sage: sage.categories.pushout.pushout(ZZ['x'], QQ) Univariate Polynomial Ring in x over Rational Field sage: sage.categories.pushout.pushout(ZZ['x'], QQ).construction() (Poly[x], Rational Field)
The common ancestor is \mathbb{Z} and our options for Z are Frac(\mathbb{Z}[x]) or Frac(\mathbb{Z})[x]. In Sage we choose the later, treating the fraction field functor as binding "more tightly" than the polynomial functor, as most people agree that \mathbb{Q}[x] is the more natural choice. The same procedure is applied to more complicated Parents, returning a new Parent if one can be unambiguously determined.
sage: sage.categories.pushout.pushout(Frac(ZZ['x,y,z']), QQ['z, t']) Fraction Field of Multivariate Polynomial Ring in x, y, z, t over Rational Field
Coercion Example
Here is a minimal example of setting up a simple Ring that handles coercion. (It is easy to imagine much more sophisticated and powerful localizations, but that would obscure the main points being made here.)
class Localization(Ring): def __init__(self, primes): """ Localization of $\Z$ away from primes. """ Ring.__init__(self, base=ZZ) 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._x 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 # 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) That's all there is to it. Now we can test it out: sage: R = Localization([2]); R Integer Ring localized at [2] sage: R(1) LocalElt(1) sage: R(1/2) LocalElt(1/2) sage: R(1/3) Traceback (most recent call last): ... ValueError: Not integral at 3 sage: R.coerce(1) LocalElt(1) sage: R.coerce(1/4) Traceback (click to the left for traceback) ... TypeError: no cannonical coercion from Rational Field to Integer Ring localized at [2] sage: R(1/2) + R(3/4) LocalElt(5/4) sage: R(1/2) + 5 LocalElt(11/2) sage: 5 + R(1/2) LocalElt(11/2) sage: R(1/2) + 1/7 Traceback (most recent call last): ... TypeError: unsupported operand parent(s) for '+': 'Integer Ring localized at [2]' and 'Rational Field' sage: R(3/4) * 7 LocalElt(21/4) sage: R.get_action(ZZ) Right scalar multiplication by Integer Ring on Integer Ring localized at [2] sage: cm = sage.structure.element.get_coercion_model() sage: cm.explain(R, ZZ, operator.add) Coercion on right operand via Conversion map: From: Integer Ring To: Integer Ring localized at [2] Arithmetic performed after coercions. Result lives in Integer Ring localized at [2] Integer Ring localized at [2] sage: cm.explain(R, ZZ, operator.mul) Action discovered. Right scalar multiplication by Integer Ring on Integer Ring localized at [2] Result lives in Integer Ring localized at [2] Integer Ring localized at [2] sage: R6 = Localization([2,3]); R6 Integer Ring localized at [2, 3] sage: R6(1/3)  R(1/2) LocalElt(1/6) sage: parent(R6(1/3)  R(1/2)) Integer Ring localized at [2, 3] sage: R.has_coerce_map_from(ZZ) True sage: R.coerce_map_from(ZZ) Conversion map: From: Integer Ring To: Integer Ring localized at [2] sage: R6.coerce_map_from(R) Conversion map: From: Integer Ring localized at [2] To: Integer Ring localized at [2, 3] sage: R6.coerce(R(1/2)) LocalElt(1/2) sage: cm.explain(R, R6, operator.mul) Coercion on left operand via Conversion map: From: Integer Ring localized at [2] To: Integer Ring localized at [2, 3] Arithmetic performed after coercions. Result lives in Integer Ring localized at [2, 3] Integer Ring localized at [2, 3]