On Jun 4, 2008, at 7:35 PM, Bill Page wrote: > On Wed, Jun 4, 2008 at 1:54 PM, Robert Bradshaw wrote: >> >> On Jun 4, 2008, at 4:07 AM, Bill Page wrote: >> ... >>> >>> 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. > > So is this essentially an admission that the concept of 'parent' is > superfluous and could have in fact been implemented just at Python > 'type'?
Not at all. It is the realization that not all Python objects will have a Parent (e.g. the builtin objects, objects from other libraries, Sage Parents, etc.) but they will have a type, which is a much weaker notion but can be reasoned with a bit (e.g. the builtin Python 'int' type coerces nicely into the IntegerRing). > I am not sure that I would actually advocate this now, but for > argument's sake: Why not do it this way all of the time? Python > classes all end up as (potential) parents. Types are all about the implementations of things, they synonymous with the "classes" of Object Oriented programming, and are insufficient (and the wrong vehicle) to carry deeper mathematical structure. For example, an element of Z/5Z and an element of Z/7Z have the same type (i.e. they're instances of the same class, with the same methods, internal representation, etc), but not the same parent (which is data). > I think that this more or > less is what at least some Magma developers had in mind. E.g. We read > in the preface to the Magma HTML Help Document: > > http://magma.maths.usyd.edu.au/magma/htmlhelp/preface.htm > > "Every object created during the course of a computation is associated > with a unique parent algebraic structure. The type of an object is > then simply its parent structure." William Stein adequately addressed this point. > >> ... >> 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.) >> > > The lack of multiple inheritance in Cython seems to be a major design > obstacle. Although a C struct is not a real class, it is not clear to > me why this is not adequate in compiled code. Wouldn't it be > sufficient to merge (flatten) the components of the multiple ancesters > into one struct? If not (e.g. if it is necessary to retain some > knowledge of their origins), why not provide nested structs? But I > suppose that this is quite off-topic... The exact details of why this isn't as easy as it seems are quite technical, and off-topic. The short answer is that with a major re- design of Cython multiple inheritance could be supported at the cost of an extra indirection (even on non-multiply inherited types) on ever C member/method lookup. (This is done in C++, but it would be even more complicated to deal with the way Python handles extension types). One of the primary reasons for Cython is speed, which is not worth sacrificing for this feature. > >> 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] >> > > Hmmm... what I think I see here is multiple Python types (_int, > _int64, _gmp) being used for the *same* parent, i.e. "Ring of integers > modulo n" (for some parameter n). As stated before, there are 4 distinct parents here (incidentally instances of the "IntegerMod_Ring" class). > Simple inheritance should make this easy, no? What can be inherited is inherited from a common IntegerMod_abstract class. Subclassing is used where methods can be overridden to be faster (e.g. arithmetic can be made much faster if the data is a C int, rather than an arbitrary-length mpz_t integer type). > >> On the other hand, some parents may have elements of several >> types. The "SymbolicRing" is one such example. sage: v = [SR(1), pi, x+1, sin(x)] # I forgot this important input line in my 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] >> > > "SymbolicRing" is another thing that worries me a little. Exactly what > (mathematically) is a symbolic ring? E.g. Why is it a ring and not a > field? Operations like 'sin(sin(sin(x))).parent()' doesn't look much > like a ring to me. Probably most other computer algebra systems would > just call this an "expression tree" or AST or something like that. Most symbolic systems (Magma and Axiom excluded) have very little notion of algebras, rings, modules, etc.--virtually everything is an expression or list of expressions. SymbolicRing is a way to fit these abstract "expression trees" into a larger framework of Sage. It not only keeps engineers and calculus students happy, it keeps me happy when just want to sit down and "solve for x" or compute a symbolic integral. It's also a statement that rigor should not get in the way of usability (an important component of being a viable alternative to the M's). > Why do we need different types (sub-classes)? > >>> 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. >> ... >> 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. >> > > To the best of my knowledge, the formal concept of "representation" in > a computer algebra systems is unique to Axiom. Each domain has a > specified 'Rep'consisting of some domain expression. E.g. > > Rep == Integer > > or > > Rep == Union(Record(car:%, cdr:%), "nil") > > % stands for "this domain", so this definition amounts to some > recursive structure. Of course recursively defined classes are also > possible in Python but they require much more discipline on the part > of the programmer. > > Now there are two operators 'rep' and 'per' that provide coercion to > and from Rep. So we might say for example that some operation * in > this domain is implemented by * from Rep: > > x * y == per( rep(x) * rep(y) ) > > The trouble is: I don't see anything here that could be called a > "parent". Or perhaps, they are all "parents" except for those initial > domains for which we never explicitly specify a Rep. Nope, nothing I see here could reasonably be called a Parent. Is there an object that formally represents "the ring of integers" that one could pass to a function? > >> >> 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 >> > > Ah, I think that is very useful. Does the "Category of fields" inherit > any generic operations from "Rings()"? Very little, because up 'till now there wasn't an easy way to use them. But this is the plan. > >> One of the changes in this latest coercion push is to allow Parents >> to belong to several categories. >> > > That sounds good. So does this mean that the 'category' method now > returns a list? There are two methods, category (returning the first cat in the list) and categories (returning the whole list). The set of categories is an ordered list, and things are attempted in the first category (and its supercategories) before moving on to the next. Most objects, of course, will belong to one category (not including its super categories). > >> ... 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. >> ... >>> >>> 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 >> > > Excellent. But, hmm... this is supposed to be a morphism in some > category. What category? sage: mor = F.coerce_map_from(Zmod(7)) sage: parent(mor) Set of Homomorphisms from Ring of integers modulo 7 to Finite Field of size 7 sage: parent(mor).homset_category() Category of rings (The reason we have to ask for "homset_category" is because the category of a homset is (generically at least) Sets. > sage: category(Zmod(7)) > Category of rings > sage: category(FiniteField(7)) > Category of fields > sage: category(FiniteField(7)).is_subcategory(category(Zmod(7))) > True > ------ > > Ok, good. We just need the injection. > >>> ... >>> 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? >>> ... >> >> 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. > > Ok, it is an object in some category. Maybe a good name would be the > category "VectorSpace"? (Q-modules is ok). Yeah, Q is a field after all. > What makes them a MatrixSpace? It's just a term used for the set of all matrices of a specified dimension and basering. > >> In the case of square matrices, it is actually an algebra >> over its basering, and its category is the category of Q-algebras. >> > > Anyway, I suppose this taxonomy is not such a big deal. One only needs > to learn the language - of course it has turned out in Axiom that this > is not that simple a problem - hence interactive tools for querying > and navigating the domain and category hierarchies (hyperdoc). Yeah. Introspection is important for something like this. > >> ... > > Thanks for continuing the discussion. No problem. I am hopeful that this discussion is useful for more than just you and I. - 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 -~----------~----~----~----~------~----~------~--~---
