On Jun 4, 2008, at 4:07 AM, Bill Page wrote: > Robert, > > Thanks for the elaboration. I hope that this follow-up is not too far > off topic and I don't want to distract you (or any of the Sage > developers) from your main tasks. I wrote this mostly as notes and > questions to myself - but if you or anyone else have some time or the > inclination to correct or comment as time permits, that would be > great.
I'm sure a lot of other people have similar questions, and it will be good to put it down in writing. > > On Tue, Jun 3, 2008 at 10:04 PM, Robert Bradshaw wrote: >> >> On Jun 3, 2008, at 4:50 PM, Bill Page wrote: >> >>> How does it [categories in Sage] relate to the >>> concept of "parent" - which seems equally ill-defined to me? >> >> A Parent is an Object in the category of Sets, though in the context >> of coercion one usually assumes one can some kind of arithmetic >> (binary operations) on their elements. >> ... >> On Jun 3, 2008, at 7:11 PM, David Harvey wrote: >> ... >>> Don't you mean to say something more like "a parent is an object >>> of a concrete category", i.e. a category C with a faithful functor >>> f : C -> Set, such that the "elements" (as understood by Sage) of >>> the parent P are exactly the elements of f(P)? > > Ok (and thanks also for the clarification, David). There are of course > two different uses of "object" here: 1) object of some category, 2) > Python object. All Python objects have a 'type', i.e. belong to some > Python class. > > So in Sage 3.0.2 I observe for example: > > sage: type(1) > <type 'sage.rings.integer.Integer'> > sage: parent(1) > Integer Ring > sage: type(parent(1)) > <type 'sage.rings.integer_ring.IntegerRing_class'> > sage: category(parent(1)) > Category of rings > sage: type(category(parent(1))) > <class 'sage.categories.category_types.Rings'> > > and > > sage: type(1.0) > <type 'sage.rings.real_mpfr.RealNumber'> > sage: parent(1.0) > Real Field with 53 bits of precision > sage: type(parent(1.0)) > <type 'sage.rings.real_mpfr.RealField'> > sage: category(parent(1.0)) > Category of fields > sage: type(category(parent(1.0))) > <class 'sage.categories.category_types.Fields'> > > These seem consistent to me, albeit rather complex. However I am not > sure I understand the following: > > sage: parent(IntegerRing()) > <type 'sage.rings.integer_ring.IntegerRing_class'> > sage: parent(RealField()) > <type 'sage.rings.real_mpfr.RealField'> > > Could you explain why the parent of an object of some category is a > type? David's explanation of this is right on. We need parent() to work in some sensible way on non-Elements (e.g. Python ints, objects from outside Sage) to be able do some kind of coercion reasoning on them. Python is a dynamically typed language, ever object has a type. > >> >>> What is the relationship to inheritance in Python? Is the intention >>> to give all mathematical objects defined in Sage some categorical >>> structure? What about categories themselves as mathematical >>> structures - e.g. a category is a kind of directed graph with >>> additional >>> structure? >> >> A big push of this model is to divorce the relationship between >> inheritance (which primarily has to do with implementation) and >> mathematical categorization. > > At first blush it still seems strange to me to distinguish between the > parent of an object and the type of an object. The instances of a type > are often considered elements. Is the invention of 'parent' in Sage > due to some inherent limitation of Python classes? Do you really want > to say more abstractly that a certain type *represents* a certain > parent? E.g. Does 'sage.rings.real_mpfr.RealNumber' represent > 'RealField()'? Can there be other representations of 'RealField()' in > Sage? How can I find out for example if 'sage.rings.integer.Integer' > represents 'IntegerRing()'? One should think of the type of an object as what specifies its implementation (including its internal representation). In this sense it is like a class in Java, C++, or any other programming language. (In Python there is a subtle (and mostly historical) difference between types and classes depending on whether or not it's written in C, but for the most part they can be used interchangeably). Python has multiple inheritance, but Cython does not (the C format of a compiled Python class is a C struct, so this is not so much a Cython limitation as a Python/C API limitation.) Most of the time there is a 1-to-1 correspondence between Parents and the types of its Elements. For example, and element of the Parent RR (= RealField(53) is represented by sage.rings.real_mpfr.RealNumber. If I do RR(3) I get back an object of type sage.rings.real_mpfr.RealNumber representing the floating point number 3 to 53 bits of precision, and it's Parent is RR. RealField (100) is a new Parent, whose elements are again of type sage.rings.real_mpfr.RealNumber but to 100 bits of precision. Sometimes, however, the same type is used for multiple parents. There are several integer mod types (depending on whether or not the modulus fits in a single word) and they are used for both generic Z/ nZ and prime-order finite fields. Thus we have sage: [type(mod(-1, 100^k)) for k in [2..5]] [<type 'sage.rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.integer_mod.IntegerMod_gmp'>] sage: [parent(mod(-1, 100^k)) for k in [2..5]] [Ring of integers modulo 10000, Ring of integers modulo 1000000, Ring of integers modulo 100000000, Ring of integers modulo 10000000000] On the other hand, some parents may have elements of several types. The "SymbolicRing" is one such example. sage: [type(a) for a in v] [<class 'sage.calculus.calculus.SymbolicConstant'>, <class 'sage.functions.constants.Pi'>, <class 'sage.calculus.calculus.SymbolicArithmetic'>, <class 'sage.calculus.calculus.SymbolicComposition'>] sage: [parent(a) for a in v] [Symbolic Ring, Symbolic Ring, Symbolic Ring, Symbolic Ring] > From my experience with Axiom I am sympathetic to the separation of > implementation and specification but in Axiom "domains" are both > parents and types. A domain can inherit it's implementation from > another domain (via add). A domain can also serve as the > representation for some other domain (via Rep). For example > IntegerMod(5) is the representation of PrimeField(5). IntegerMod(5) in > turn is represented by SingleInteger, etc. In Axiom, at the deepest > level all types are ultimately provided by Lisp. These types are not > really Axiom domains and so I suppose the situation is analogous to > Python types and Sage parents. This sounds like the correct analogy. In Sage as well elements of prime finite fields are the same type as elements of Z/nZ for composite n, but they have different parents. > Axiom categories on the other hand form a lattice. Domains belong to > categories by assertion or by virtue of the subdomain relationship. In > Axiom there is an operator named 'has' which provides the same > information as 'category' in Sage so that: > > x has y > > is just 'y == category(x)'. For example 'Float has Field' is > equivalent to: > > sage: Fields() == category(RealField()) > True > > Although in Axiom a domain may satisfy more than one category. Will > this be possible in Sage in the future? Categories in Sage aren't as fully developed as they could be, but they do form a lattice. sage: C = category(FiniteField(13)); C Category of fields sage: C.is_subcategory(Rings()) True One of the changes in this latest coercion push is to allow Parents to belong to several categories. > What information does Sage actually have about a given category? For > example, what does Sage know about the relationship between Rings() > and Fields()? E.g. functors? Only the bare minimum at this point. > None of this has much to do with "category theory" as such. Categories > in Axiom are only vaguely related to categories in Mathematics. So I > suppose from your description that categories in Sage will play a > similar role but will be more strongly related to the mathematical > concept? Yes. This will also be a place to put generic implementations of algorithms. For example, one has the category of Euclidian domains, where one can define a generic gcd algorithm that will then get attached (as a method) to every element of that category. >> This will allow categories to play a larger role (though work in that >> area can be done after the merge as it is not disruptive). For >> example, Z/nZ[x] is implemented the same whether or not p is >> a prime, but the category it lives in (and hence the methods one >> can do on it) vary. > > Are you suggesting that Z/pZ should be considered a field just because > p is prime? No, it might be expensive to test for primality. > sage: category(Zmod(7)) > Category of rings > > sage: Zmod(7).is_field() > True > > Perhaps an alternative would be to provide a coercion to some object > whose parent is in Fields()? The is_field method tests whether or not this specific instance happens to be a field, which is true in this case. But we do provide a coercion sage: F = GF(7) sage: F.coerce_map_from(Zmod(7)) Natural morphism: From: Ring of integers modulo 7 To: Finite Field of size 7 > >> As another example, matrix spaces are algebras iff they are square, >> but one doesn't want to have a special class for square matrices over >> <insert optimized type here>. > > I am not sure what you mean by "matrix spaces" as such but the > category of matrices does make sense to me. See for example: > > http://unapologetic.wordpress.com/2008/06/02/the-category-of- > matrices-i > > Maybe it is interesting because in this category the morphisms are > matrices and the objects are just the row and column dimensions - > non-negative integers. How would this fit into the category model in > Sage? > > There is a monoidal sub-category of square matrices. A MatrixSpace is a parent sage: M = matrix(QQ, 2); M [0 0] [0 0] sage: parent(M) Full MatrixSpace of 2 by 2 dense matrices over Rational Field It is a module (via scalar multiplication) over its basering (in the case above, the integers) and so (should) lie in the category of Q- modules. In the case of square matrices, it is actually an algebra over its basering, and its category is the category of Q-algebras. >> Generic algorithms can be put on the categories such >> that if g is in category C, and C has a method x, then g.x() will >> work. > > Do you mean 'category(parent(g))==C'? Yes. > How will such a generic method x > of C operate on g? Do you have some example coding that implements > this idea? Not at the moment. Say a and b have parent P in category C. One types a.gcd(b) Then, a does not have a method "gcd" it will try category(parent(a)).element_gcd(a,b) which will be a generic implementation of the euclidean algorithm (assuming C is a category supporting this). - Robert --~--~---------~--~----~------------~-------~--~----~ 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://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
