

<h2>Parents and Elements: History and Motivation for the Sage Coercion Model</h2>
<p>In Sage (like in Magma), most objects are either <strong>elements </strong>or <strong>parents</strong>. Think of a "parent" as a set.&nbsp;</p>
<p>This Parent/Element idea is a powerful algebraic approach to implementing mathematical objects on a computer, which does not exist in Mathematica, Maple, PARI, Maxima, and many other math software platforms.&nbsp;</p>

{{{id=11|

///
}}}

<p>I learned about this approach from using Magma:</p>

{{{id=8|
%magma
R<x> := PolynomialRing(Integers());
print Parent(x);
///
Univariate Polynomial Ring in x over Integer Ring
}}}

<p>In Sage:</p>

{{{id=10|
R.<x> = ZZ[]
parent(x)
///
Univariate Polynomial Ring in x over Integer Ring
}}}

{{{id=14|
x.parent()
///
Univariate Polynomial Ring in x over Integer Ring
}}}

<p>Type <strong>Parent </strong>and press tab. &nbsp;Also type <strong>Parent?</strong></p>

{{{id=16|

///
}}}

{{{id=18|
isinstance(ZZ, Parent)
///
True
}}}

{{{id=19|
isinstance(2, Parent)
///
False
}}}

{{{id=20|

///
}}}

{{{id=15|

///
}}}

{{{id=21|

///
}}}

<p>Automatic Coercions:</p>
<p><em>"The primary goal of coercion is to be able to transparently do arithmetic, comparisons, etc. between elements of distinct parents."</em></p>
<p>When I used to try to get people to use Magma, perhaps the number one complaint I heard about Magma was that doing arithmetic with objects having distinct parents was difficult and frustrating.</p>
<p>For the <strong>first year</strong>, in Sage, there was a very simple coercion system:</p>
<ul>
<li>If you try to compute a + b or a * b, first somehow put b into the parent of a, then do the arithmetic.</li>
</ul>
<p>That seriously sucked. &nbsp;E.g.,&nbsp;</p>
<p>&nbsp;&nbsp; &nbsp;<strong>Mod(2,7) + 6</strong></p>
<p>was completely different than</p>
<p>&nbsp;&nbsp; &nbsp;<strong>6 + Mod(2,7)</strong>!</p>
<p>The first was Mod(1,7), and the second was the integer 8. &nbsp; This makes understanding code difficult and unpredictable.</p>
<p>So I rewrote coercion to be a bit better (this was a really painful rewrite, which resulted in me limping for 6 months...):</p>
<ul>
<li>If you try to compute a + b (or a*b), check for a "<strong>canonical coercions"</strong> from the parent of a into b, or failing that, from the parent of b into a. &nbsp;If there aren't any raise an error. &nbsp;If there is one, use it. &nbsp;There won't be both unless there is some canonical isomorphism.&nbsp;</li>
<li>There are some axioms about what a canonical coercion is. &nbsp;At least it is homomorphism.&nbsp;</li>
</ul>
<p>Then we decided that there is a canonical homomorphism $\ZZ \to \ZZ/7\ZZ$, but there is not one $\ZZ/7\ZZ\to \ZZ$ since there is no nontrivial ring homomorphism in this direction, hence the above makes sense in either order. &nbsp;</p>
<p>One implication of this new model was that parent objects have to be immutable, i.e., you can't fundamentally change them after you make them. &nbsp;This is why in Sage you must specify the name of the generator of a polynomial ring at creation time, and can't change it. &nbsp;In Magma, it is typical to specify the name only later if you want.</p>
<p>Objects must be immutable because the canonical maps between them depend on the objects themselves, and we don't want them to just change left and right at runtime.&nbsp;</p>

{{{id=29|
%magma
R := PolynomialRing(RationalField(), 2);
f := R.1^3 + 3*R.2^3 - 4/5;
print f;
///
$.1^3 + 3*$.2^3 - 4/5
[
$.1,
$.2
]
}}}

{{{id=28|
%magma
AssignNames(~R, ["x", "y"]);
print f;
[R.1, R.2]
///
x^3 + 3*y^3 - 4/5
[
x,
y
]
}}}

{{{id=33|
%magma
AssignNames(~R, ["z", "w"]);
print f;
///
z^3 + 3*w^3 - 4/5
}}}

{{{id=31|
R = PolynomialRing(QQ)
///
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_36.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("UiA9IFBvbHlub21pYWxSaW5nKFFRKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmp5tzEoj/___code___.py", line 2, in <module>
    exec compile(u'R = PolynomialRing(QQ)' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/Users/wstein/purple/install/psage-10.10.26/local/lib/python2.6/site-packages/sage/rings/polynomial/polynomial_ring_constructor.py", line 322, in PolynomialRing
    raise TypeError, "You must specify the names of the variables."
TypeError: You must specify the names of the variables.
}}}

{{{id=32|
R.<x,y> = PolynomialRing(QQ)
f = x^3 + 3*y^3 - 4/5; f
///
x^3 + 3*y^3 - 4/5
}}}

<p>Note: In Sage, you can can use a <strong>with block</strong> to temporarily change the names if you <strong><em>really</em></strong> need to for some reason. &nbsp;This is allowed since at the end of the with block the names are guaranteed to be changed back.</p>

{{{id=36|
with localvars(R, ['z','w']):
    print f
print "back?", f    
///
z^3 + 3*w^3 - 4/5
back? x^3 + 3*y^3 - 4/5
}}}

{{{id=34|

///
}}}

{{{id=24|

///
}}}

<p>But this new model had a major problem too, e.g.,&nbsp;if x in $\ZZ[x]$ then $x + 1/2$ would FAILS! &nbsp; This is because 1/2 does not coerce into $\ZZ[x]$ (the parent of $x$), and $x$ does not coerce into $\QQ$ (the parent of $1/2$).&nbsp;</p>
<p>&nbsp;</p>
<p>Maybe the implementors of Magma have the answers? &nbsp;Evidently not.&nbsp;</p>

{{{id=5|
%magma
R<x> := PolynomialRing(Integers());
x + 1/2;
///
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_48.py", line 10, in <module>
    exec compile(u"print _support_.syseval(magma, u'R<x> := PolynomialRing(Integers());\\nx + 1/2;', __SAGE_TMP_DIR__)" + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/Users/wstein/purple/install/psage-10.10.26/devel/sagenb-main/sagenb/misc/support.py", line 473, in syseval
    return system.eval(cmd, sage_globals, locals = sage_globals)
  File "/Users/wstein/purple/install/psage-10.10.26/local/lib/python2.6/site-packages/sage/interfaces/magma.py", line 523, in eval
    raise RuntimeError, "Error evaluating Magma code.\nIN:%s\nOUT:%s"%(x, ans)
RuntimeError: Error evaluating Magma code.
IN:R<x> := PolynomialRing(Integers());
x + 1/2;
OUT:

>> x + 1/2;
     ^
Runtime error in '+': Bad argument types
Argument types given: RngUPolElt[RngInt], FldRatElt
}}}

{{{id=26|

///
}}}

<p>Robert Bradshaw did though, and now it is in Sage:</p>

{{{id=4|
R.<x> = ZZ[]
x + 1/2
///
x + 1/2
}}}

{{{id=3|

///
}}}

<p>His new design is (for the most part) what Sage actually uses now.</p>
<p>He launched an effort in 2008 (see the <a href="http://wiki.sagemath.org/dev1">Dev Days 1 Wiki</a>) to implement a rewrite of the coercion model to his new design. &nbsp;This ended up swallowing up half the development effort at the workshop, and was a massive amount of work, since <em><strong>every</strong></em> parent structure and element had to have some modifications made to it.&nbsp;</p>
<p>This meant people changing a lot of code all over Sage that they didn't necessarily understand, and crossing their fingers that the doctest test suite would catch their mistakes. &nbsp; &nbsp;This was SCARY. &nbsp; After much work, none of this went into Sage. &nbsp;It was just way too risky. &nbsp;This failure temporarily (!) burned out some developers.&nbsp;</p>
<p>Robert Bradshaw, on the other hand, persisted and came up with a new approach that involved migrating Sage code gradually. &nbsp;I.e., he made it so that the old coercion model was still fully supported simultaneously with the new one, then he migrated a couple of parent structures, and got the code into Sage. &nbsp; I'm sure not everything is migrated, even today. &nbsp;There are two points to what he did:</p>
<ol>
<li>He extended the rules so x + 1/2 works, i.e., the result of a+b need not live in the parent of a or the parent of b.</li>
<li>He made implementing coercion much more top down: simply implement various methods in a class that derives from Parent. &nbsp;This meant that instead of coercion being rules and conventions that people have to understand and implement in their own code all over Sage, they just implement a small amount of code and the rules (and benefits) are all enforced automatically.&nbsp;</li>
</ol>

{{{id=2|

///
}}}

<h2>The Coercion Model</h2>
<p>The coercion model is explained here: <a href="http://sagemath.org/doc/reference/coercion.html">http://sagemath.org/doc/reference/coercion.html</a></p>
<p>&nbsp;</p>

{{{id=41|
cm = sage.structure.element.get_coercion_model()
cm.explain(Mod(2,7), 6)
///
Coercion on right operand via
    Natural morphism:
      From: Integer Ring
      To:   Ring of integers modulo 7
Arithmetic performed after coercions.
Result lives in Ring of integers modulo 7
Ring of integers modulo 7
}}}

{{{id=39|
R.<x> = ZZ[]
cm.explain(x, 1/2)
///
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
}}}

{{{id=40|
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
}}}

{{{id=42|
R.<x> = ZZ[]
cm.bin_op(77/1, 14*x, gcd)
///
1
}}}

{{{id=43|
QQ.coerce_map_from(int)
///
Native morphism:
  From: Set of Python objects of type 'int'
  To:   Rational Field
}}}

{{{id=47|

///
}}}

<h2>How to Use the Coercion Model When Creating Your Own New Parents/Elements</h2>

{{{id=49|
class Localization(Ring):
   def __init__(self, primes):
       """
       Localization of `\ZZ` 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._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)
///
}}}

{{{id=46|
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)
///
}}}

{{{id=50|
R = Localization([2]); R
///
Integer Ring localized at [2]
}}}

{{{id=51|
R(1)
///
LocalElt(1)
}}}

{{{id=52|
R(1/2)
///
LocalElt(1/2)
}}}

{{{id=53|
R(1/3)
///
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_78.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("UigxLzMp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmphvQfek/___code___.py", line 3, in <module>
    exec compile(u'R(_sage_const_1 /_sage_const_3 )' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "parent.pyx", line 882, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:6462)
  File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3118)
  File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3021)
  File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmpx_pv62/___code___.py", line 27, in _element_constructor_
    raise ValueError, "Not integral at %s" % p
ValueError: Not integral at 3
}}}

{{{id=54|
R.coerce(1)
///
LocalElt(1)
}}}

{{{id=55|
R.coerce(1/4)
///
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_80.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("Ui5jb2VyY2UoMS80KQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmpKJsx0D/___code___.py", line 3, in <module>
    exec compile(u'R.coerce(_sage_const_1 /_sage_const_4 )' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "parent.pyx", line 961, in sage.structure.parent.Parent.coerce (sage/structure/parent.c:7136)
  File "parent.pyx", line 988, in sage.structure.parent.Parent.coerce (sage/structure/parent.c:7084)
TypeError: no canonical coercion from Rational Field to Integer Ring localized at [2]
}}}

{{{id=56|
R(1/2) + R(3/4)
///
LocalElt(5/4)
}}}

{{{id=57|
R(1/2) + 5
///
LocalElt(11/2)
}}}

{{{id=58|
5 + R(1/2)
///
LocalElt(11/2)
}}}

{{{id=59|
R(1/2) + 1/7
///
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_100.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("UigxLzIpICsgMS83"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/7y/7y-O1iZOGTmMUMnLq7otq++++TI/-Tmp-/tmpTGIMsc/___code___.py", line 3, in <module>
    exec compile(u'R(_sage_const_1 /_sage_const_2 ) + _sage_const_1 /_sage_const_7 ' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "element.pyx", line 1274, in sage.structure.element.RingElement.__add__ (sage/structure/element.c:10853)
  File "coerce.pyx", line 765, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6995)
TypeError: unsupported operand parent(s) for '+': 'Integer Ring localized at [2]' and 'Rational Field'
}}}

{{{id=60|
R(3/4) * 7
///
LocalElt(21/4)
}}}

{{{id=61|
R.get_action(ZZ)
///
Right scalar multiplication by Integer Ring on Integer Ring localized at [2]
}}}

{{{id=62|
cm = sage.structure.element.get_coercion_model()
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]
}}}

{{{id=63|
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]
}}}

{{{id=64|
R6 = Localization([2,3]); R6
///
Integer Ring localized at [2, 3]
}}}

{{{id=65|
R6(1/3) - R(1/2)
///
LocalElt(-1/6)
}}}

{{{id=66|
parent(R6(1/3) - R(1/2))
///
Integer Ring localized at [2, 3]
}}}

{{{id=67|
R.has_coerce_map_from(ZZ)
///
True
}}}

{{{id=68|
R.coerce_map_from(ZZ)
///
Conversion map:
  From: Integer Ring
  To:   Integer Ring localized at [2]
}}}

{{{id=69|
R6.coerce_map_from(R)
///
Conversion map:
  From: Integer Ring localized at [2]
  To:   Integer Ring localized at [2, 3]
}}}

{{{id=70|
R6.coerce(R(1/2))
///
LocalElt(1/2)
}}}

{{{id=45|
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]
}}}

{{{id=44|

///
}}}