>
> Interestingly enough, William and I were just talking about the
> coercion model today. The issue came up when deciding how to apply
> the sqrt() operator to, say, the rational number 2. Currently it
> returns a decimal approximation, and as of 2.5 it returns an element
> of the symbolic expressions ring. Both have serious drawbacks.
> Ideally one would get something in a number field, but then the issue
> comes up how to handle all the coercions.
A couple of points on square root. First, sqrt() and square_root() can have
different behavior. I think there are three possible behaviours one might
want:
1. Return a real approximation. The main plus on this option is that this
is what many users will want if they ask for sqrt(2).
2. Return an element of a quadratic extension. We can then have one of the
completions (or one of the pair of complex embeddings) be distinguished.
This just means that there's an automatic coercion from QQ[sqrt(2)] to RR
given by choosing the positive square root. While not really canonical
mathematically, it's sufficiently standard that we should put it in. Users
who want the other embedding will be able to get it fairly easily.
3. Return an integer (or rational) if n is a perfect square or throw and
error otherwise. This kind of behavior currently exists for finite fields
for example.
My inclination would be to have sqrt do the first, and square_root the
second. Since 2 makes sense for pretty much every integral domain (return x
in the ring R[x]/(x^2 - a) if a does not have a square root in R), maybe
have square_root do that, and sqrt() return an element of an algebraic
completion for fields, and have behavior 3 for rings?
Essentially, what we came up with is that (extra) implicit coercion
> morphisms could be specified at ring (object) creation time, which
> would be extra data attached to that specific ring, and the coercion
> model would detect and use those.
I think I like using commutative diagrams better.
Also, one could implement a
> ambient_parent() method who would (if possible) return a new parent
> together with injections from each of the original rings. The lattice
> of number fields stuff would be used here.
Yeah: an ambient_parent method could make sense in a CoercionEnvironment
(the minimal element among things mapped to from both, if such exists, or
error if there this element doesn't exist or is not unique).
I like the idea of being able to use python contexts. I don't know
> how efficient one could make it though.
In terms of efficiency, for elements with the same parent, there will be no
performance hit. After that, I don't think a context would slow stuff down
much if you did it right.
I think the inner context
> would take precedence.
Agreed.
I really like the idea of having a commutative
> diagram graph too. How would it get created? Would every ring, on
> creation time, try and update the commutative diagram to include
> itself? The more I think about it, the more having the (cached)
> has_coerce_map_from() function return an actual homomorphism (or
> None) seems to make sense. Thus one would traverse the graph only once.
Yeah, I was thinking that too.
I'd like to center the discussion on categories for a bit. Since implicit
coercion maps are supposed to be morphisms, they properly have a category
attached to them. So really, we should be asking:
If R and S are objects of a category C, we want to pick a distinguished
element of $Hom_C(R, S)$. So, given two parents R and S, we choose a
category C with a forgetful functor to the category of parents and return a
morphism in $Hom_C(R, S)$. So how do we implement CoercionEnvironments?
Every parent object implements a function called _coercion_categories()
which returns a list of categories that parent belongs to. It doesn't have
to be all categories that that parent belongs to (clearly), but these
categories will be the only ones considered by the coercion code. The
default implementation is to just return the category of Parents (is this
the same category as the category Sets? I'm not sure...), and every
implementation should return Parents as one of the members of the list.
By a descendant of a category C I mean a category D such that there is a
forgetful functor from D to C. By an entry point of a commutative diagram L
in a category D I mean a morphism f in Hom_C(A, B) where B is an object in L
and D is a descendant of C. Exit point is defined analogously. By an
extended commutative diagram I mean a commutative diagram with a list of
entry and exit points.
Each CoercionEnvironment has the following fields:
* an enclosing environment "encl" (another CoercionEnvironment)
* a dictionary "diagrams", with keys some collection of categories, and
diagrams[cat] an extended commutative diagram in the category cat.
* a dictionary "coerce_maps" so that we don't have to find coercion maps
more than once.
and a function find_coerce_map(R, S) that does the following: (note that
the code below doesn't correctly handle cycles in diagrams)
def find_coerce_map(self, R, S):
"""
Returns a coercion morphism from R to S, or None if none exists in the
current environment.
Tests first to see if R and S are already cached in the dictionary of
known maps.
Next, checks to see if R and S both belong to one of the diagrams and
there's a path between them. If this is true for only one of the diagrams,
returns that map. If true for more than one, raises an error.
Next, checks to see if R belongs to a diagram with exit points and S to
a diagram with entry points. If so, recursively tries to find a coercion
map from the codomain of an exit point of a diagram to which R belongs to
the domain of an entry point of a diagram to which S belongs.
Finally, checks to see if there is an enclosing environment, and if
there is a coercion map in the enclosing environment.
"""
if self.coerce_maps.has_key((R, S)):
return self.coerce_maps [(R, S)]
f = None
for cat in intersection(R._coercion_categories(),
S._coercion_categories):
if self.diagrams.has_key(cat) and R in self.diagrams[cat] and S in
self.diagrams[cat]:
path = self.diagrams[cat].path(R, S)
if path is not None:
if f is None:
f = path.compose()
else:
raise ValueError, "more than one coercion map found"
if f is None:
for diag1 in self.diagrams.values() if R in diag1:
for diag2 in self.diagrams.values() if S in diag2:
for g in diag1.exit_points() if g.domain() is not R:
pathR = diag1.path(R, g.domain())
if pathR is not None:
for h in diag2.entry_points() if h.codomain() is
not S:
pathS = diag2.path(h.codomain(), S)
if pathS is not None:
e = self.find_coerce_map(g.codomain(),
h.domain())
if e is not None:
if f is None:
f = pathS.compose() * h * e * g *
pathR.compose()
else:
raise ValueError, "more than one
coercion map found"
if f is None and self.encl is not None:
f = self.encl.find_coerce_map(R, S)
self.coerce_maps[(R, S)] = f
return f
Suggestions are welcome (especially thoughts on the giant nested for loops).
As an example, in the default environment, the diagrams[Rings] diagram would
include the ring morphism from ZZ to QQ sending 1 to 1. Whenever you create
a polynomial ring over a ring R it would add a morphism from R to the
polynomial ring embedding R as constant polynomials. Whenever you create a
quotient ring it would add a morphism to the default diagram. Etc.
When you create a finite field of prime order, diagrams[FiniteFields] will
add an entry point from ZZ to the prime field. diagrams[FiniteFields] will
then build a lattice of compatibly embedded fields as you create new
extension fields of that prime field. Note that the diagrams can be
disjoint unions of other diagrams (in practice one might use a list of
diagrams instead...). I don't know yet how to make weakrefs work with this
whole scheme.
David
On 4/26/07, Robert Bradshaw <[EMAIL PROTECTED]> wrote:
>
>
> Interestingly enough, William and I were just talking about the
> coercion model today. The issue came up when deciding how to apply
> the sqrt() operator to, say, the rational number 2. Currently it
> returns a decimal approximation, and as of 2.5 it returns an element
> of the symbolic expressions ring. Both have serious drawbacks.
> Ideally one would get something in a number field, but then the issue
> comes up how to handle all the coercions.
>
> Essentially, what we came up with is that (extra) implicit coercion
> morphisms could be specified at ring (object) creation time, which
> would be extra data attached to that specific ring, and the coercion
> model would detect and use those. Also, one could implement a
> ambient_parent() method who would (if possible) return a new parent
> together with injections from each of the original rings. The lattice
> of number fields stuff would be used here.
>
> I like the idea of being able to use python contexts. I don't know
> how efficient one could make it though. I think the inner context
> would take precedence. I really like the idea of having a commutative
> diagram graph too. How would it get created? Would every ring, on
> creation time, try and update the commutative diagram to include
> itself? The more I think about it, the more having the (cached)
> has_coerce_map_from() function return an actual homomorphism (or
> None) seems to make sense. Thus one would traverse the graph only once.
>
> - Robert
>
> On Apr 26, 2007, at 5:55 PM, David Roe wrote:
>
> > In the course of thinking about coercion for p-adic rings, fields
> > and extensions, I've had some ideas about a different kind of
> > coercion model to use for SAGE. It would fit into the existing
> > coercion model, though I can see it motivating changes to the
> > existing model.
> >
> > SAGE currently does quite well when coercing between different
> > basic rings (Integers to Rationals for example). Each ring R
> > implements a _coerce_impl function that takes an element of another
> > ring S and either returns an element of R or raises an error if
> > that element cannot be coerced into R. When there is a canonical
> > morphism from S to R, this is fine. But if there is no such
> > canonical morphism from S to R, you have to either use the syntax R
> > (x), in which case it picks a default map (which may or may not be
> > a ring morphism), or you have to define a ring morphism f: S ---> R
> > and apply it explicitly. This last option gets to be quite
> > inconvenient when working with towers of extensions, or even worse,
> > with extensions that are not explicitly defined as relative
> > extensions of each other (currently SAGE cannot automatically
> > coerce from GF(19^2) to GF(19^4)). Part of the issue is existence
> > of automorphisms. Magma has a solution for finite fields that I
> > think we can extend to an automatic coercion system that works more
> > broadly (Bosma, Cannon and Steele. Lattices of Compatibly Embedded
> > Finite Fields. J. of Symbolic Comp. Volume 24, Issue 3-4).
> >
> > SAGE would define a commutative diagram class. One could implement
> > this as an extension of a Graph, where vertices are labeled by
> > Rings (or Groups, Algebras, etc), and the edges are labelled by
> > morphisms in the appropriate category. I think one should also
> > allow sections of injections and surjections. In order to coerce
> > between two rings that both lie in the diagram, one just finds a
> > path from one to the other, and applies the morphisms in succession.
> >
> > There are a couple of nice benefits of this approach. First, one
> > can apply the methods of "Lattices of Compatibly Embedded Finite
> > Fields" to automatically grow a global coercion environment so that
> > if a user does the following:
> > sage: K.<a> = GF(19^2)
> > sage: L.<b> = GF(19^4)
> > sage: c = a + b
> > sage: c.parent()
> > Finite Field in b of size 19^4,
> > things work appropriately.
> >
> > One might even allow adding elements where neither field embeds
> > into the other, but there is a default field containing both (when
> > both are Galois extensions of a third field, for example).
> > sage: K.<a> = GF(19^6)
> > sage: L.<b> = GF(19^4)
> > sage: c = a + b
> > sage: c.parent()
> > Finite Field in ? of size 19^12.
> >
> > There are other benefits of such a coercion model: one can use
> > Python's with syntax to allow user defined coercion environments.
> > The user creates a bunch of rings. Some are defined as extensions
> > or subfields of others, yielding some a priori injections and
> > sections of injections. The user can then define some morphisms
> > between them, and package all of this data into a "coercion
> > environment" (a layer on top of a commutative diagram). For
> > example, one could do the following:
> > sage: S.<x> = QQ[]
> > sage: R.<y> = QQ[]
> > sage: f = S.hom([y^2], R)
> > sage: E = CoercionEnvironment([R, S], [f])
> > sage: with E:
> > ... z = x + y
> > ... w = z - x^2
> > ...
> > sage: w
> > y + y^2 - y^4
> > sage: w.parent()
> > Univariate Polynomial Ring in y over Rational Field
> >
> > A question remains with what to do with coercions from outside the
> > coercion environment to inside, or vice versa. Obviously, the
> > answer can differe depending on which diagram's morphisms one
> > uses. One solution would be to say that in these cases one uses
> > the outer coercion environment (ie the default global one and not E
> > in the example above). Yet there are times when it's convenient to
> > be able to use mixed environments: for example, when coercing a
> > constant polynomial over ZZ into a number field (or a constant
> > polynomial over one number field into another number field in a
> > coercion diagram). Another idea I've had is the notion of an entry
> > point. If your diagram has an initial object (S in the diagram
> > above), then one first tries to coerce in the outer environment.
> > If this fails, one tries to coerce to the initial object in the
> > outer environment, and from the initial object to your desired
> > ring. One can similarly define the notion of exit points with
> > terminal objects. I don't know what to do if there are multiple
> > initial or terminal objects (check them in an order given at
> > creation time?).
> >
> > Should CoercionEnvironments be mutable or immutable? (I'm leaning
> > toward immutable, but if someone has a good reason otherwise...)
> >
> > Another unresolved issue for me is how __call__ and _coerce_ should
> > behave differently in a coercion environment. Should __call__ only
> > exist at the top, global level of coercion, possibly using _coerce_
> > from user defined coercion environments to fill in gaps? Should
> > the default choices of embeddings for finite fields and unramified
> > p-adic extensions use call or coerce syntax?
> >
> > How can we make all of this fast and memory-friendly? I think the
> > category theory code will need some revision. In particular, there
> > need to be special cases of morphisms that are fast (finite field
> > morphisms, number field morphisms, polynomial ring morphisms,
> > etc). The field morphisms would probably be implemented as
> > matrices over a ground field (often a prime field, but not
> > necessarily).
> >
> > Please let me know what you think of all of this, and if you have
> > ideas/suggestions/etc. I have a few spin-off things that I've been
> > thinking about that I'll write follow-up e-mails for.
> >
> > David
> >
> > >
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
