On Fri Jul 1 14:47:12 -0500 2005 Bill Page wrote: I think the concept of a tuple and Cartesian Product should be related, i.e. a tuple is an element of a Cartesian Product: fricas )expose Product Type: Voidfricas f:Product(INT, Type: Void`Product` can be looked up in hyperdoc. It is listed in Appendix C (p. 613 of Axiom (paper) Book; p. 1028 of eBook). `Tuple` is more like `DirectProduct` since the entries must come from the same domain. However, `Product` constructs only Cartesian product of two domains; `DirectProduct` requires a dimension parameter; whereas `Tuple` does not (arbitrary length). Also `Tuple` is only a linear aggregate (or `PRIMARR` ) and has no algebraic structure. Direct product exists in many categories.
So, a tuple is not an element of William I think a domain such as`Product` deserves (much) more documentation
then just to be listed in Appendix C! Of course that is also true of
many other domains in Axiom. It worries me that a 1000+ page book is
not nearly enough to properly document more than a small number of
Axiom's mathematical constructs. How big of a book do we need? Is the
idea of a "book" adequate at all? In fact Appendix C seems to be of
very little value to me.
The domain tuple an expression of two or more other expressions separated by commas, for example, 4,7,11. Tuples are also used for multiple arguments both for applications (for example, f (x,y)) and in signatures (for example, (Integer, Integer)−> Integer). A tuple is not a data structure, rather a syntax mechanism for grouping expressions. This implies that we should not think of a function with
a signature like What I want is for fricas T1:=(1,
Type: Tuple(Float)fricas f:(Integer, Type: Voidbeing interpreted as fricas makeprod(1, Type: Void
What you describe sounds more like Bill Page wrote: ```
I think a domain such as
```
Documenting the algebra code of Axiom is a very big project itself. I agree that the Appendices are not that helpful.
There is a subtle distinction. What I want is forI don't agree. When one wraps up something into a single object, it is inconvenient to look at the parts without unwrapping. (May be some optical technology can? :-) Here in `f` you must take an integer and a float, wrap them up
into a product, and then unwrap it to compute the resulting float. For objects
that are complicated, there is of course a role to wrap up the pieces before
shipping. (Ever think of zipping if you are sending just two small files?)
William Bill Page wrote:William Sit wrote: No. William Bill Page wrote:```
I think such tuples should be
```
From page 246 of the Axiom book: "The type of a function is always a mapping of the form Source -> Target where Source and Target are types." and from page 1085: "Domains Mapping, Record, and Union are primitive domains. All other domains are written in the Axiom programming language ..." fricas )show Mapping
Type: TypeFrom a mathematical point of view clearly the idea that `Mapping(T, A, B)` denotes the class of mappings from `(A, B)`
into `T` implies that `(A,B)` denotes some kind of set, i.e.
the `Product(A,B)` .
William Sit wrote: I don't agree. When one wraps up something into a single object, it is inconvenient to look at the parts without unwrapping. But Cartesian Product is implemented as a fricas f1:Record(a:INT, Type: Voidfricas f1(arg)==arg.b+arg.a Type: Voidfricas f1[1, fricas Compiling function f1 with type Record(a: Integer,
Type: Floatshould be viewed as equivalent to fricas f2:(INT, Type: Voidfricas f2(a, Type: Voidfricas f2(1, fricas Compiling function f2 with type (Integer,
Type: FloatAnd in fact after a simple optimization, the compiler should be able to produce equivalent internal lisp code. #187 trouble with tuples functions are objectsof type Mapping --William Sit, Mon, 04 Jul 2005 08:19:49 -0500 replyFrom a mathematical point of view clearly the idea that William Sit wrote:William Sit wrote: (Disclaimer: my earlier response above is not directly to your new comment. See
previous post. I agree that the Cartesian product of In most mathematics I know, products, if they exist, are formed from objects of
the same category. If However, there is this subtle distinction in the way we give the definition
of In short, Axiom imitates closely mathematics and gives us both ways to define mappings. When the data structure is complicated, a Record is preferred. In mathematics, we have been trained to be sloppy with details that have been seen too often already, so as to contemplate at newer and more abstract levels. We tend to see things as the same via isomorphisms. Now, we are forced to think about all the details again in using Axiom. That is the main hurdle and a steep "relearning" curve. Perhaps in 2032 (I'm not going to let this be a sliding window of 30 years!), computer algebra can be smart enough to incorporate all theorems (isomorphisms included) from a self-generated data-base and we don't have to "relearn" what is in our subconsciousness. But Cartesian Product is implemented as a Record and the domain Record is a primative in Axiom. So my proposal above amounts to stating, for example, that: Axiom is a strongly typed language with object oriented roots. A Record, even if
it is a primary domain, is a single object. You cannot have the compiler
In the second form, you There is also another problem with your automatic translation. In a record, the
Please note also that Axiom William William Sit wrote:I agree that the Cartesian product of A, B is implied in the notion of Mapping(T,A,B). But that is not the issue here. ??? But that products, if they exist, are formed from objects of the same category Yes, I agree. I think program semantics must be expressed in some "cartesian closed" category. See http://en.wikipedia.org/wiki/Cartesian_closed_category In the case of Axiom I think that it is highly significant that "The category Cat of all small categories (with functors as morphisms) is cartesian closed;". And the choice of Mapping, Record and Union as primatives in Axiom directly supports this notion. The two are not equivalent as mappings: f is binary and g is unary. I disagree strongly with your analysis. These two things are formally identical. No "subtle distinction" is necessary or relevant. A Record, even if it is a primary domain, is a single object. You cannot have the compiler sometimes treat it as one object and sometimes not. I agree. My point is that the expression Your definition of "arity" is wrong. A function with multiple inputs is necessarily defined over a product and has an "arity" equal to the size of that product. I think Axiom's definition of Mapping is wrong to admit more than two arguments (mapping should be semantically equivalent to exponentiation in a cartesian closed category). It is confusing and unnecessarily complicated from a mathematical point of view to define Mapping(C,A,B) as different from Mapping(C,Product(A,B)). It makes a vacuous distinction where none is necessary. In a record, the order of the items is not important (conceptually speaking), each field is tagged by an identifier. In a tuple, the physical order is important and items are not tagged. That is not true. As long as we admit a Tuple as a domain and not
"just a syntactic construct" (what ever that might mean), in a Tuple
the "fields" are simply tagged by their order - or better: indexed
by fricas R:Record(a:Integer,
Type: Record(a: Integer,From William Sit Tues Jul 5 12:29:00 -5:00 2005 PS. Sorry these discussions get longer and longer. I know you are not shy about long discussions. Let's hope we can come to some understanding.
William Sit wrote:I agree that the Cartesian product of A, B is implied in the notion of Mapping(T,A,B). But that is not the issue here. Bill Page wrote: ??? But that No one is saying that http://en.wikipedia.org/wiki/Cartesian_closed_category Thanks for the pointer. Always nice to learn new jargon. The two are not equivalent as mappings: f is binary and g is unary. We don't agree then (even though I don't know what you mean by
"formally identical"). The distinction is both subtle and still very
relevant! The distinction is between A Record, even if it is a primary domain, is a single object. You cannot have the compiler sometimes treat it as one object and sometimes not. I see, this is what we are talking about: how to count arguments.
That depends on what you meant by "multiple inputs". We cannot
discuss about arity unless we first agree to allow the notation for
many-to-one functions: I would like to point out, however, that the domains More specifically, your definition above first wraps the multiple inputs (the "many") as a product and then unwraps it to count the dimension. The number of inputs never changes in the process and is the arity. Notice you said this: Let's look at another example regarding atomicity of parameters. If I
write a mapping in Axiom, There are many mathematical objects that are data-represented using
products of sets, but the arity of a function is the number of
So getting back to my "subtle distinction": in (aside) In fact, in many Axiom constructors, to get around this encapsulation, extra parameters are necessary, for example, in Groebner basis package, the calling convention is::
where Arity may change when one makes substitutions (which is composition)!
So substituting (note) Here the map is of course the identity map. But it is not
instructive to think that way. Rather, because we deliberately give
the Cartesian product a new identity, not as made up of two component
parts, but as a new object. It may be helpful to think of I think Axiom's definition of Mapping is wrong to admit more than two arguments (mapping should be semantically equivalent to exponentiation in a cartesian closed category). It is confusing and unnecessarily complicated from a mathematical point of view to define Mapping(C,A,B) as different from Mapping(C,Product(A,B)). It makes a vacuous distinction where none is necessary. On the contrary. It is the idealistic mathematical view which
identifies the two that creates "vacuous" wraps and unwraps "where
none is necessary". Indeed, I would have preferred mapping to be
many-to-many so that this wrapping and unwrapping are unnecessary both
on the source and target sides. I have argued that it is convenient
not to have to wrap cartesian products with few components. Your
correct but pedantic mathematical view of Once the source and target components are encapsulated into In a record, the order of the items is not important (conceptually speaking), each field is tagged by an identifier. In a tuple, the physical order is important and items are not tagged. I'll grant you that, any data structure has an inherent order. But we
must not confuse that order with what we are trying to model. Records
have fields and tuples do not. Fields are directly addressable and to
the user, orderless. There is no restriction on how we may print a
(note) tuples in function is not quite the same as Moreover, if I am using r:=new()$Foo r.a:=5 r.b:=1.1 r would nonetheless be unaffected (except in the print out order of the two fields and an additional status field). William functional-categorical programming versus object-oriented programming --billpage, Tue, 05 Jul 2005 16:14:12 -0500 replySorry these discussions get longer and longer. On the contrary, that Let's hope we can come to some understanding. Yes, I think so. Afterall, mathematics is an Mapping(C,A x B) has no meaning in Axiom. But I have already written the equivalent: fricas f:Mapping(STRING, Type: Voidand this has a clear meaning in Axiom. Using names like fricas C:=STRING
Type: Typefricas D:=Product(INT,
Type: Typefricas f:D->C Type: Voidmakes no difference. My view is that fricas f:Mapping(STRING, Type: Voidshould have the same meaning as the previous expression. The fact that is doesn't seems unnecessary and confusing. About Cartesian closed categories: Always nice to learn new jargon. But the concept of a [Cartesian Closed Category]? is much more important than mere jargon! It provides the categorical basis for typed lambda calculus and thus essentially all of the theory of computation, modern functional programming and languages such as OCAML. Encapsulation is where one starts going into the realm of computer science. This is where the "subtle distinction" originates. In the context of Axiom I strongly object to creating such "subtle distinctions". Axiom is intended to be a system for doing mathematics with a computer. I think the programming language in which we express mathematical algorithms should be a close as possible to the actual mathematics. This is one of the things that distinquishes Axiom from other "engineering- oriented" computer algebra systems like Maple and Mathematica. In mathematics, there is but one Cartesian product of A and B. In computing, there are two, a raw version (A,B) and an encapsulated version Product(A,B). To me, when applied to Axiom this is wrong! wrong! wrong! :) We do not need this kind of distinction. ```
If I write a mapping in Axiom,
```
No. I think the product It is the idealistic mathematical view which identifies the two that creates "vacuous" wraps and unwraps "where none is necessary". No. There are no unnecessary "wraps and unwraps". This is just normal paramater passing. The compiler only needs to do what is usually necessary to pass, for example the tuple (a,b) i.e. object of type Product(A,B), to the body of the function by pushing the values of the projections onto the stack. It makes no sense to encapsulate objects from unrelated domains just because they happen to be the argument types of some function. I disagree. This makes perfectly good sense in the context of the cartesian closed category CAT of small categories. I think this the foundation on which all of Axiom's algebra and it's programming language should be based. why should the data-structures be the "canonical" cartesian product structure Precisely because of the special role that products play in the concept of a cartesian closed category. From: wyscc Wed Jul 6 00:49:00 -5:00 2005 billpage wrote: makes no difference. My view is that (code snipped) should have the same meaning as the previous expression. Of course you are correct here, but you are still missing my point. I was using But the concept of a [Cartesian Closed Category]? is much more important than mere jargon! I was half-joking. I went and read the articles (about currying, for example) until I had to stop! But a first step is always getting familiar with the jargon. There are relatively few ideas but lots of jargon for the same thing. So currying is nothing but specialization, something mathematicians have used to turn say group multiplication into the group acting on itself. At the end of the day, one still has to write the binary multiplication routine to compute. In the context of Axiom I strongly object to creating such "subtle distinctions". Axiom is intended to be a system for doing mathematics with a computer. The distinction is really not "subtle" but a key one for object oriented programming (of course I didn't realize this earlier since I was, and still am, just exploring along with you). Unfortunately, this seems unavoidable in computing. In order to be able to speak of a polynomial, say, as an abstract mathematical object (so we can differentiate, integrate, etc) in as general a fashion as possible (meaning allowing different data representation, for one, but ignoring these at the same time), we have to omit mentioning the details until we need them for computation. So we can say We are (and certainly Axiom is) very far away from your ideal of "doing mathematics" using a computer. We can't really do "symbolic computation" the way a human mind can. Consider how a computer can interpret what mathematicians call ... (ellipsis) and compute with it. If you know any language that can handle that (and I don't mean just sums or products but something iterated in general, like iterated integrals with ellipsis between two integral signs), I would be very interested. In mathematics, there is but one Cartesian product of A and B. In computing, there are two, a raw version (A,B) and an encapsulated version Product(A,B). May be not for simple constructs like the Cartesian product (even though there is still a role for encapsulation). How about there is just one polynomial ring in several variables over say the integers, but Axiom has DMP, HDMP, GDMP, SMP, and POLY? What would be the single implementation of the polynomial ring be? If I write a mapping in Axiom, No quarrel with that, but where do you draw the line? When does a domain become "derived enough" to count as one object one parameter? You did not answer my question on arity. I already commented on the role of It is the idealistic mathematical view which identifies the two that creates "vacuous" wraps and unwraps "where none is necessary". I can't agree that you can equate a tuple It makes no sense to encapsulate objects from unrelated domains just because they happen to be the argument types of some function. Care to elaborate? I fail to follow your logic. You on the one hand want Consider the two ways of coding g:(INT,INT)->INT g(a,b)==a+b g(1,2) f:Product(INT,INT)->INT f(z)==(selectfirst z)+selectsecond(z) f(makeprod(1,2)) Which is more convenient?
why should the data-structures be the "canonical" cartesian product structure So, use tuples. Is CCC the only kind of categories in symbolic computation? William William Sit wrote:
Yes, I agree that is true in Axiom as it is now. But I am thinking about
how Axiom should be not how it is. The mathematical concept of product
is straight-forward and there is no reason why The derived domain Product, as it is defined now in Axiom is rather more complicated than what one needs for defining a Mapping for a function with more than one input. The domain Tuple on the other hand is too restricted. Axiom's built-in primitive domain Record is just about right. So currying is nothing but specialization ... No, specialization is not equivalent to currying. The result of currying is a higher-order function. Specialization is applying that function to a specific argument. See for example: http://en.wikipedia.org/wiki/Currying Unfortunating the funtions called curryLeft and curryRight are actually specializations: fricas )di op curryLeft fricas )di op curryRight What we need is are the functions: fricas )set functions compile on Type: Voidfricas leftCurry(f)== x+->(y+->f(x, Type: Voidfricas rightCurry:((INT, Type: Voidfricas rightCurry(f)== y+->(x+->f(x, Type: VoidThe option fricas plus:(INT, Type: Voidfricas plus(x, Type: Voidfricas curryPlus:=leftCurry(plus) fricas Compiling function plus with type (Integer, fricas Compiling function leftCurry with type ((Integer,
Type: (Integer -> (Integer -> Integer))fricas curryPlus1:=curryPlus(1)
Type: (Integer -> Integer)fricas curryPlus1(2)
Type: PositiveIntegerSee [SandBox Curry]? for an attempt to define left and right Curry as an Axiom library functions. using a computer. We can't really do "symbolic computation" the way a human mind can. I do not know anything of an algorithmic nature that a human mind does which cannot in principle be done on computer. As I understand it dealing with " ... (ellipsis)" is one of the purposes of the construct called Streams in Axiom. You did not answer my question on arity. Do you mean the question of the arity of, for example the following function: f:Product(A,Product(B,C))->D My answer (assuming that you accept the notion of Product as a primitive domain) would be that this function has "arity" of 3 since in a Cartesian closed category (CCC) we have: Product(A,Product(B,C)) = Product(Product(A,B),C) = Product(A,B,C) Axiom actually takes the domain Record as primitive rather than Product. The equivalence of constructs such as: Record(a:A,b:Record(a:B,b:C)) = Record(a:Record(a:A,b:B),b:C) = Record(a:A,b:B,c:C) is a little less obvious but natural coercions (isomorphisms) could be provided which make the question of arity clear in this case as well. The design of the domain Product(A,B) need not be dominated by the two projection maps. That is not true. The very nature of what we mean by product is defined in terms of these projection maps. The product is what is known as a type of limit in category theory. It is defined by a universal property which makes the product and it's projection maps unique amoung all other such objects and maps. See for example: Consider the two ways of coding ... f, g Using the Record constructor in Axiom this function can be written as: fricas h:Record(a:INT, Type: Voidfricas h(parameter) == parameter.a + parameter.b Type: Voidfricas h[1, fricas Compiling function h with type Record(a: Integer,
Type: PositiveIntegerwhich is almost as convenient as your definition of Is CCC the only kind of categories in symbolic computation? That is a long story that I plan to continue here [Cartesian Closed Category]?. But very briefly one answer to your question could be: CCC is the smallest and simplist kind of category in which we should expect to be able to do all the symbolic computation that is possible on a computer. The reason why we can say this with some certainty has to do with the relation between CCC and the simple-typed lambda calculus. Lambda calculus is the smallest and simplist programming language which can be shown to be computation universal, i.e. in which we can prove that it is possible to express all computable functions, the partial recursive functions or equivalently to simulate a Turing machine. (Cf. previous reference to CCC for all this "jargon" :) Bill Page wrote:William Sit wrote: If we are really only talking about what Axiom The mathematical concept of product is straight-forward and there is no reason why Exactly, so why are you still insisting on calling it The derived domain Product, as it is defined now in Axiom is rather more complicated than what one needs for defining a Mapping for a function with more than one input. The domain Tuple on the other hand is too restricted. Axiom's built-in primitive domain Record is just about right. What difference does it make to use You did not answer my question on arity. Would you say that f:DirectProduct?(5, INT)->INT has arity 5 then? And to do so recursively? Give me a break. What is wrong with f:(A,B,C)->D having arity 3 The design of the domain Product(A,B) need not be dominated by the two projection maps. Bill, I fully know how a product is defined categorically (I took such a course
with Eilenberg and kept a copy of Mitchell's text at arm's length). What I am
saying is, for the purpose of computing, it is reasonable, and perhaps even
desirable under suitable environments, NOT to implement an Consider the two ways of coding ... f, g But the arity of h is one, not two, despite your use of h[1,2]?, which is really parsed as h([1,2]?) in Axiom. William William Sit wrote:Bill Page wrote:there is no reason why (A,B) where A and B are domains should not denote this product. I am sorry. I must have mislead you somehow into thinking that I was concerned with the name or the specific Axiom domain called Product. I am not. All I want is something that is semantically just the Cartesian product
or better: the product in some category such as CCC. I want the expression
(A,B) need be only the vanilla Cartesian product. I agree. That is exactly what I am trying to say. Would you say that No. The only thing to the left of the that has arity more than 1 is whatever we decide represents the "the vanilla Cartesian product". Arity is just the size of that product. Of course we have to admit n-ary products where n is some non-negative integer. denotes the "terminal" object (the identity for the product constructor) and denotes just the object . I am not sure what you mean by not implementing: external interfaces for the projection maps in a Cartesian product To me, a product is But the arity of is one, not two, despite your use of , which is really parsed as in Axiom.
fricas construct(1,
Type: Record(a: Integer,fricas )show Record(a:INT, but Otherwise "arity" as you have been describing it, is a peculiar thing in Axiom. It is the number of inputs to the Mapping constructor minus 1. In my case I want the function Mapping constructor to be the exponential object in a CCC and of course that has exactly two inputs. Hi Bill:Yes, we are finally agreeing on something. Use '(A,B,C, ...)" for vanilla cartesian product and use I am not sure what you mean by not implementing: external interfaces for the projection maps in a Cartesian product To me, a product is defined by it's projections. You can hide other details of the implementation of a product if you wish, but not the projections. If you did, then it is mathematically speaking no longer a product. While it is true that in any specification of a I think we agree that the "vanilla Cartesian product" (A,B) necessarily has projections, right? That is all I want. I am not arguing against encapsulation or information hiding in the case of the representations of other constructed domains. So I think that we agree! :) Agreed. Otherwise "arity" as you have been describing it, is a peculiar thing in Axiom. It is the number of inputs to the Mapping constructor minus 1. In my case I want the function Mapping constructor to be the exponential object in a CCC and of course that has exactly two inputs. That is why I said your proposal to change the notation in arity of Mapping(D,(A,B)) is two. arity of Mapping(D, (A,B,C)) is three. arity of Mapping(D,((A,B),C)) is three? (I would say two) arity of Mapping(D, Record(a:A, b:B)) is two? (I would say one) arity of Mapping(D, (Record(a:A, b:B))) is two? (I would say one) arity of Mapping(D, DirectProduct(5,A)) causes a syntax error, or considered same as: Mapping(D, (DirectProduct(5,A))) and has arity one. arity of Mapping(D, (DirectProduct(5,A), (A,B)) is three? (I would say two) arity of Mapping(D, ((A,B), Record(a:A, b:B)) is two? three? four? (I would say two) If we do not agree, then it shows such conventions are very confusing. In that case, perhaps you can give a precise syntax and definition of arity that covers all the above cases? William |

Tuple, Product, Direct Product--wyscc, Fri, 01 Jul 2005 19:50:38 -0500 reply