Edit detail for Tuples Products And Records revision 2 of 2

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:

(1) -> )expose Product

   Product is now explicitly exposed in frame initial 
makeprod(1,1.1)

   There are no library operations named makeprod 
      Use HyperDoc Browse or issue
                              )what op makeprod
      to learn if there is any operation containing " makeprod " in its
      name.

   Cannot find a definition or applicable library operation named 
      makeprod with argument type(s) 
                               PositiveInteger
                                    Float

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

SandBoxDirectProduct

So, a tuple is not an element of Product (it is a Cartesian product in a loose mathematical sense: Tuple S is actually the infinite union of DirectProduct(n,S) over all n.

William

Tuple is more like DirectProduct since the entries must come from the same domain.

The domain Tuple and the use of tuple in Axiom seems to be a little confused. See page 1100 of Book:

  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 (Integer,Float)->Float as a mapping Product(Integer,Float)->Float and it certainly isn't the mapping Tuple Any -> Float, but elsewhere in Axiom the notion of a function as a mapping is very important.

What I want is for Product to be generalized to an 'n'-ary Cartesian Product and then instead of expressions like:

T1:=(1,1.1)

(1)

f:(Integer,Float)->Float

being interpreted as Tuples, I think such tuples should be 'Products':

makeprod(1,1.1)$Product(Integer,Float)

   The function makeprod is not implemented in Product(Integer,Float) .

Tuple S is actually the infinite union of DirectProduct(n,S) over all n.

What you describe sounds more like InfiniteTuple - another interesting but undocumented domain.

Bill Page wrote:

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.

Documenting the algebra code of Axiom is a very big project itself. I agree that the Appendices are not that helpful.

Tuple is more like DirectProduct since the entries must come from the same domain.

The domain Tuple and the use of tuple in Axiom seems to be a little confused. See page 1100 of Book:

  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 (Integer,Float)->Float as a mapping Product(Integer,Float)->Float and it certainly isn't the mapping Tuple Any -> Float, but elsewhere in Axiom the notion of a function as a mapping is very important.

There is a subtle distinction. Tuples have no bounding parenthesis or brackets or structures. It is simply a "list" in raw enumerated form. It is convenient because it is a true list, where as a List object is a single object, not a "list". This distinction is important in the notion of arity of operators (and OOP).

What I want is for Product to be generalized to an 'n'-ary Cartesian Product and then instead of expressions like:

fricas

T1:=(1,1.1)

(2)

Type: Tuple(Float)

fricas

f:(Integer,Float)->Float

Type: Void

being interpreted as Tuples, I think such tuples should be Products:

fricas

(1,1.1)$Product(Integer,Float)

   The function Tuple is not implemented in Product(Integer,Float) .

William

William Sit wrote:

Tuple S is actually the infinite union of DirectProduct(n,S) over all n.

What you describe sounds more like InfiniteTuple - another interesting but undocumented domain.

No. InfiniteTuple is more like Stream. It is conceptually infinite in length. A construct analogous to Tuple S is Matrix(R), which can have arbitary but finite dimensions. Matrix(R) is conceptually the union of Matrix(m,n,R) over all m and n. An object in Tuple S has arbitrary but finite length.

William

I think such tuples should be Products ...

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 ..."

)show Mapping

   Mapping(T, S, ...)
      Mapping takes any number of arguments of the form:
         T, a domain of category SetCategory
         S, a domain of category SetCategory
         ...
      Mapping(T, S, ...) denotes the class of objects which are 
      mappings from a source domain (S, ...) into a target domain T.
      The Mapping constructor can take any number of arguments. All 
      but the first argument is regarded as part of a source tuple 
      for the mapping. For example, Mapping(T, A, B) denotes the 
      class of mappings from (A, B) into T.
      This constructor is a primitive in FriCAS. For more 
      information, use the HyperDoc Browser.
Mapping(String,INT,Float)

(3)

From a mathematical point of view clearly the idea that

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 Record and the domain Record is a primitive in Axiom. So my proposal above amounts to stating, for example, that:

f1:Record(a:INT,b:FLOAT)->FLOAT

f1(arg)==arg.b+arg.a

f1[1,1.1]

Compiling function f1 with type Record(a: Integer,b: Float) -> Float

(4)

should be viewed as equivalent to

f2:(INT,FLOAT)->FLOAT

f2(a,b)==a+b

f2(1,1.1)

Compiling function f2 with type (Integer, Float) -> Float

(5)

And in fact after a simple optimization, the compiler should be able to produce equivalent internal lisp code.

From 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:

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.

(Disclaimer: my earlier response above is not directly to your new comment. See previous post. 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.)

In most mathematics I know, products, if they exist, are formed from objects of the same category. If f:A x B -> C is a mapping, where A, B are from the same category, we may sometimes let D = A x B and identify f as f:D -> C. Let me rename this to: g:D -> C.

However, there is this subtle distinction in the way we give the definition of f and g. In the first case, we would write f(a,b) = c, where as in the second case, we would write g(d) = c, with d = (a,b). The two are not equivalent as mappings: f is binary and g is unary. To define c to be a+b in both cases, say, it is straight forward in the first case f(a,b)=a+b. In the second case, there is necessarily a composition with two projection maps p:D ->A and q:D -> B where p(d)=a, and q(d) = b. The true definition of g is: g(d) = p(d)+q(d). If the target C is more involved, say C is D² and f is meant to be the diagonal map D -> D² then the g -form would be more preferrable: g(d) = (d,d).

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:

(code snipped, see above)

And in fact after a simple optimization, the compiler should be able to produce equivalent internal lisp code.

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 sometimes treat it as one object and sometimes not. In your example, f1 has arity one (requiring two projection maps), and f2 has arity two. In general, the compiler reads in a list of arguments for a function and then parses it. I don't see much optimization (the parser needs to work one level deeper to parse the content of the record,and there is no way the generated code can be simplified to remove this level because the arities are different).

In the second form, you explicitly tell the compiler that f2 requires two objects as inputs. In the first, only one. In terms of data structure, Axiom must view arg as a Record object (note your use of square brackets). In your scenario, you seem to suggest that the compiler automatically changes the arity of f1 to the length of the record. If so, I think this will only confuse users, even if that change is restricted to Records appearing as function signatures.

There is also another problem with your automatic translation. 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.

Please note also that Axiom hides the data representation of objects from code external to the object constructors. So sometimes these projections are not available (for Product and domains of DirectProductCategory, they should be, and are).

William

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 is precisely the issue with which I am concerned.

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 (A,B) in the Mapping (A,B)->C, does in fact denote a single object, not two objects. It is clear that when we write f(a,b) == a+b in the definition of the function f:(A,B)-> C, that a and b denote composition with the necessary projections - that is precisely what we mean when we say that a and b are "formal parameters" of the function.

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 1..n. In Records these "tags" are given names. In both cases these are formally just different names for projections from a product. In Axiom the fields of a Record are also given in an order that allows for example the assignment:

R:Record(a:Integer,b:Float):=[1,1.1]

(6)

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.

See [Axiom Colloquium]? about long discussions.

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 is precisely the issue with which I am concerned.

No one is saying that mathematically (A,B) is not A x B. THEY ARE! Here, A x B is only a mathematical notation for (A,B). There is no Axiom domain with that notation. Mapping(C,A x B) has no meaning in Axiom. That was the reason I said this is not the issue here. I'll refrain from using this notation when discussing Axiom, since it only confuses the issues. The Cartesian product in Axiom is either (A,B) or Product(A,B), the latter is what I should have denoted as D.

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.

I disagree strongly with your analysis. These two things are formally identical. No "subtle distinction" is necessary or relevant.

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 Mapping(C,A,B) and Mapping(C,D) when D is treated as an entity in itself (that is, when you start writing Product(A,B) in Axiom for (A,B), "wrapping" the components).

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 (A,B) in the Mapping (A,B)->C, does in fact denote a single object, not two objects. It is clear that when we write f(a,b) == a+b in the definition of the function f:(A,B)->C, that a and b denote composition with the necessary projections - that is precisely what we mean when we say that a and b are "formal parameters" of the function.

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 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: f:(A1,A2,...,Am)->C is a function with m inputs. According to my understanding of the previous quote, you consider (A1,A2, ..., Am) as one object, living in some Cartesian product, and yet, you also consider that, in f(a1, a2, ..., am), the a1, a2, ..., am are "formal parameters" and the arity is the size of the product, namely m. This is a syntactic definition and I don't think it is different from mine (if I ever gave one).

I would like to point out, however, that the domains A1, A2, ..., Am are considered atomic in this counting: that is, we do not look inside each component, to see how they are constructed. This is how I understand the word "formal" as in "formal parameter". So arity is the number of formal parameters. If A1 turns out to be a Cartesian product of three domains, we do not view A1 as contributing 3 to the arity of f. Perhaps you do not agree with this. I'll discuss later the consequence of not viewing the components as anything other than atomic as far as arity goes.

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: a and b are "formal parameters" of the function f(a,b)=a+b. The number of formal parameters is precisely the arity of the function. As long as a and b are supplied in the form of parameters to a function, they are counted towards the arity of the function. You think the composition with the projection is implied and view (A,B) as "a single object". To me, (A,B) definitely denotes two objects: it is spelled out loud and clear. I am not disagreeing with your interpretation that (A,B) is identical to the (mathematical) Cartesian product A x B and by its notation, A x B, just like (A,B) indicates two objects are involved. But when you encapsulate the cartesian product by giving it the first class status as a new domain, by denoting it as Product(A,B) or more appropriately, as I did, as D, that is when it becomes one object. This process of encapsulation is not trivial, and hides A, B from the domain despite their appearances in Product(A,B). This is much more than the mathematical sentence "Let D be A x B." Encapsulation is where one starts going into the realm of computer science. This is where the "subtle distinction" originates. When we write g:D->C, the arity of g is one because D now becomes atomic.

Let's look at another example regarding atomicity of parameters. If I write a mapping in Axiom, f:Complex Integer->Float, would you say f has arity two just because a Gaussian integer may be represented by two integers? In Axiom and object oriented languages, I would consider f having only one input, not two. I am not supposed to look inside what the data representation of a Complex Integer is (indeed, I should not need to know; I may need to know about the real and imaginary parts, but the data representation, or inputs if you will, could be very different). Of course, if you write the domain of f in terms of these parts, a and b, of a Gaussian integer a+b i, it would have arity two and the signature would then be: f:Integer x Integer->Float. You do lose the identity of the domain Complex Integer. For illustration, I could also have represented a+b i by x,y,z, where x is gcd(a,b), y = a/x, and z = b/x, using three integers (by the way, this would also be a possible data representation of the Cartesian product Integer x Integer). Would you then say f now has three inputs and arity 3?

There are many mathematical objects that are data-represented using products of sets, but the arity of a function is the number of formal arguments, not what the data representation of the domain of the function is. Arity is an important notion even in mathematics (recall the chain rule for several variables). There is some slight difference in usage though. In computer languages, the number of arguments is sometimes not fixed; known as variable arity, it in fact, amounts to one list of arguments. In Axiom, I would much prefer to call a function with source List ANY as having arity one. Take a harder example, if I write a mapping p:POLY INT->NNI, what is the arity of p? Are you going to say it is the number of coefficients, which depends on the degree of the given polynomial and hence has variable arity?

So getting back to my "subtle distinction": in g:D->C, where D is Product(A,B), the arity of g is one; in f:(A,B)->C, the arity of f is two. It is the formal way the function is declared that determines the arity, and the mathematical equivalences among D, (A,B), and the mathematical object A x B does not necessarily preserve arity. 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). The formal use of the symbol D in declaring f signifies an encapsulation.

(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::

GroebnerPackage(Dom,Expon,VarSet,Dpol)

where Dom, Expon and VarSet are all duplicated because they are encapsulated in Dpol, which is a domain of POLYCAT(Dom,Expon,VarSet). Currently, there is no other way to extract the parameter domains from domain constructors. But this is another story. (My wish list includes each domain constructor freeing the encapsulated parameter domains).

Arity may change when one makes substitutions (which is composition)! So substituting (A,B) by D or the other way around are both compositions with an isomorphism (note). The map g is the composition of h:D->(A,B) with f:(A,B)->C. The signature of the composite f o h is not the same as the original map f and the arity of the composite need not be the same, and is not the same in this case. (Of course, h is not allowed in Axiom, the source of all these discussions! but perfectly ok mathematically for many-to-many functions.)

(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 D as just another Cartesian product of A and B and by universal property is isomorphic to (A,B). In an object oriented language like Axiom, new objects must not be thought of as just the sum of its parts, which should be hidden, but available when needed. Polynomials would be a good example. But D with the representation (x,y,z) given above is simpler and we can indeed have an isomorphism between h:D->(A,B) defined by h(d) = (d.x * d.y, d.x * d.z).

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 Mapping(Y,X) as would require wrapping on both source and targets for all mappings and turn these multi-inputs and multi-outputs into cartesian products. It makes no sense to encapsulate objects from unrelated domains just because they happen to be the argument types of some function; especially the only reason is to satisfy an idealistic mathematical view point. Currently, in Axiom, you already noticed that we cannot define mappings like h:D->(A,B) and that we are required to wrap the target into a Record(a:A,b:B) (in effect encapsulating the pair (A,B) into a new domain). A function calling h will have to unwrap this Record on receiving the output. Are you suggesting to require the same on the source side as well? I think that would be counter-productive.

Once the source and target components are encapsulated into X and Y, then X and Y would require data-structures. So the question is, why should the data-structures be the "canonical" cartesian product structure? How does a user tell the compiler that it should operate one way (apply projection maps to A, and B) for maps like (A,B)->C which, in the new world order, would be given a signature Product(A,B)->C but behaving like (A,B)->C, and another way (don't apply projection maps to A,B) for other maps like MyProduct(A,B)->C where MyProduct(_, _) uses a different data structure and does not behave like (A,B)->C? The only way I can think of is to treat both as having arity one, because a calling function will not need to know how the maps are coded, and just pass one object to the map in each case.

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 1..n. In Records these "tags" are given names. In both cases these are formally just different names for projections from a product. In Axiom the fields of a Record are also given in an order that allows for example the assignment:

fricas

R:Record(a:Integer,b:Float):=[1,1.1]

(7)

Type: Record(a: Integer,b: Float)

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 Record object: we can rearrange the order of the fields without conceptually changing the object itself (a simple idea that is the live and blood of all data-bases). It is just a different view of the data. You cannot do that to a tuple. Changing the order in printing out the components is changing the result. Records are conceptually convenient at the user level, but less efficient because of the extra behind the scene translations and tracking of the fields. So why would you suggest to use Record instead of tuples in functions (note), where they are not needed? What would be the point of tagging the fields, only to go through the items in the record in the order the items are laid out?

(note) tuples in function is not quite the same as Tuple S, the domain constructor. The former is heterogeneous.

Moreover, if I am using Record(a:Integer,b:Float) as the internal representation of a domain called Foo, I would provide the projection maps to the users. Now I may change the representation to Record(b:Float,a:Integer,c:Boolean) at any time without notification (for some valid reason, say, because I want to add a status field c and then regroup the record). Your construct R:Foo:=(1,1.1) would become invalid because you are relying heavily on the kindness of the Interpreter to use the inherent order. A code that runs like

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

Sorry these discussions get longer and longer.

On the contrary, that is one of the purposes of this web site. I will expand on that point in the [Axiom Colloquium]?.

Let's hope we can come to some understanding.

Yes, I think so. Afterall, mathematics is an objective science. But sometimes this does required considerable effort and patience. :)

Mapping(C,A x B) has no meaning in Axiom.

But I have already written the equivalent:

f:Mapping(STRING, Product(INT,FLOAT))

and this has a clear meaning in Axiom. Using names like

C:=STRING

(8)

D:=Product(INT,FLOAT)

(9)

f:D->C

makes no difference. My view is that

f:Mapping(STRING,INT,FLOAT)

should 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, f:Complex Integer->Float, would you say f has arity two just because a Gaussian integer may be represented by two integers?

No. I think the product (A,B) in the signature of a function (mapping) such as f:(A,B)->C plays a more fundamental role in the semantics of the Axiom programming language than derived domains such Complex Integer. That is why the domain Record is considered a "primative". These are the basic types of things that we need to define more complex things.

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.

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 D for Product(A,B) to emphasize that in Product(A,B), A and B are no longer by default available because they have been encapsulated (encapsulation need neither necessarily hide nor not hide information). But the distinction is that Product(A,B) is not the same as (A,B) computationally, as it is currently in Axiom, and no amount of mathematical identifying each to A x B is going to erase the distinction. This is computation, not mathematics! In symbolic computation, many concepts in mathematics split into computational branches because of different applications of the same mathematical domain. Sparse matrices versus dense matrices is an example.

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 differentiate(p) when p is a polynomial, no matter what domain in POLYCAT p comes from. I think that is what distinguishes Axiom from M&M.

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).

To me, when applied to Axiom this is wrong! wrong! wrong! :) We do not need this kind of distinction.

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, f:Complex Integer->Float, would you say f has arity two just because a Gaussian integer may be represented by two integers?

No. I think the product (A,B) in the signature of a function (mapping) such as f:(A,B)->C plays a more fundamental role in the semantics of the Axiom programming language than derived domains such Complex Integer. That is why the domain Record is considered a "primative". These are the basic types of things that we need to define more complex things.

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 Record.

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.

I can't agree that you can equate a tuple (a,b) with an object of type Product(A,B) because such equating does not generalize. In your mindset, Product(A,B) is (A,B). Just because a tuple (a,b) is one way, even the canonical way, to represent objects of Product(A,B) does not give it the right to be the only way. There are other ways and other uses of Product(A,B). The design of the domain Product(A,B) need not be dominated by the two projection maps. There are also more complicated tuples if every domain is unwrapped to the basics like integers. If you identify Product(A,B) with (A,B), so there is no wrap and unwrap, then why not just use (A,B)? Is it just because you rather rename (A,B) as Product(A,B) in function declarations? (That would be syntactic sugar if the current Product is removed or renamed)

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.

Care to elaborate? I fail to follow your logic. You on the one hand want Product(A,B) not to encapsulate A and B (by identifying it as (A,B)) and on the other hand want to encapsulate all parameters? Even though encapsulation wraps data into a structure, its use goes far beyond just that. One main programming design is careful planning for information hiding that encapsulation facilitates (but not necessarily always). Needlessly encapsulating the set of parameters of every function only creates needless coercions.

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

Precisely because of the special role that products play in the concept of a cartesian closed category.

So, use tuples. Is CCC the only kind of categories in symbolic computation?

William

Product(A,B) is not the same as (A,B) computationally, as it is currently in Axiom.

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 (A,B) where A and B are domains should not denote this product.

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:

)di op curryLeft

There is one exposed function called curryLeft :
   [1] (((D3, D4) -> D5),D3) -> (D4 -> D5) from MappingPackage3(D3,D4,
            D5)
            if D3 has SETCAT and D4 has SETCAT and D5 has SETCAT

)di op curryRight

There is one exposed function called curryRight :
   [1] (((D4, D3) -> D5),D3) -> (D4 -> D5) from MappingPackage3(D4,D3,
            D5)
            if D4 has SETCAT and D3 has SETCAT and D5 has SETCAT

What we need is are the functions:

)set functions compile on

leftCurry:((INT,INT)->INT)->(INT->(INT->INT))

leftCurry(f)== x+->(y+->f(x,y))

rightCurry:((INT,INT)->INT)->(INT->(INT->INT))

rightCurry(f)== y+->(x+->f(x,y))

The option )set functions compile on is required for the Axiom interpreter to able to successfully compile this function. See #156

plus:(INT,INT)->INT

plus(x,y) == x+y

curryPlus:=leftCurry(plus)

Compiling function plus with type (Integer, Integer) -> Integer

Compiling function leftCurry with type ((Integer, Integer) -> 
      Integer) -> (Integer -> (Integer -> Integer))

(10)

curryPlus1:=curryPlus(1)

(11)

curryPlus1(2)

(12)

See [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:

Limit_(category_theory)

Consider the two ways of coding ... f, g

Using the Record constructor in Axiom this function can be written as:

h:Record(a:INT,b:INT)->INT

h(parameter) == parameter.a + parameter.b

h[1,2]

Compiling function h with type Record(a: Integer,b: Integer) -> 
      Integer

(13)

which is almost as convenient as your definition of g. Syntactically, the name parameter could be eliminated for brevity. There is no reason that the compiler should produce less efficient code for this notation.

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" :)

William Sit wrote:

Product(A,B) is not the same as (A,B) computationally, as it is currently in Axiom.

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.

If we are really only talking about what Axiom should have used as notation for multiple inputs, then I think A x B would be the best. It would be trivial to implement this syntactic sugar.

The mathematical concept of product is straight-forward and there is no reason why (A,B) where A and B are domains should not denote this product.

Exactly, so why are you still insisting on calling it Product(A,B)?

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 (A,B) vs Record other than wrapping? Product(A,B) is more complicated precisely because it is to be used for other (higher level) applications, where as (A,B) need be only the vanilla Cartesian product.

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.

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 without recursing into A, B, C? I have no objection with that. I don't see your reason for insisting on writing (A,B,C) as Product(A,B,C) and STILL interpreting it the same way as (A,B,C). I guess you just don't like the notation (A,B,C) for Cartesian product. You have every right to prefer your notation, but I like to hear other people's opinion.

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:

http://en.wikipedia.org/wiki/Limit_(category_theory)

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 external interfaces for the projection maps in a Cartesian product -- which is why it is encapsulated (to faciliate the information hiding, for example A may be your Social Security Number and B your bank account password) into something else we called Product(A,B). The projections maps can be available internal to the package. (Of course, currently, Product(A,B) does export projection maps, but my point is: once packaged, Product(A,B) is not the same as (A,B) computationally because it may serve other purposes, and whether it remains vanilla Cartesian product or or not is not the issue). If you do not like the name Product to be used or associated with this new package, fine. But we are not arguing about just naming conventions, I hope (that would be endless discussion because there are many names we don't like).

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,b:INT)->INT

   Compiled code for h has been cleared.

Type: Void

fricas

h(parameter) == parameter.a + parameter.b

   1 old definition(s) deleted for function or rule h

Type: Void

fricas

h[1,2]

fricas

Compiling function h with type Record(a: Integer,b: Integer) -> 
      Integer

(14)

Type: PositiveInteger?

which is almost as convenient as your definition of g. Syntactically, the name parameter could be eliminated for brevity. There is no reason that the compiler should produce less efficient code for this notation.

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

Bill Page wrote:

there is no reason why (A,B) where A and B are domains should not denote this product.

Exactly, so why are you still insisting on calling it Product(A,B)?

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) in the mapping f:(A,B)->C to be such a product, complete with it's projections. I don't want Mapping(C,A,B). I want it to be Mapping(C,(A,B)) where (A,B) denotes this product. If you prefer the notation Mapping(C,A x B) then that is fine with me also. This is not an issue of "syntactic sugar". That's why I say that the notation Mapping(C,Record(a:A,b:B)) is also acceptible - it just provides specific names for the projections.

(A,B) need be only the vanilla Cartesian product.

I agree. That is exactly what I am trying to say.

Would you say that

f:DirectProduct?(5, INT)->INT

has arity 5 then?

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 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. 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! :)

But the arity of is one, not two, despite your use of , which is really parsed as in Axiom.

If we agreed to call Record(a:A,b:B) Axiom's equivalent of the type of categorical product that I am looking for, then I would say that the arity of is equal to the size of the Record object. It is the number of prjection maps. I agree that is parsed like . In fact, the best I can determine in this context '[1,2]?' it is really:

construct(1,2)$Record(a:INT,b:INT)

(15)

)show Record(a:INT,b:INT)

 Record(a: Integer,b: Integer) is a domain constructor.
 7 Names for 9 Operations in this Domain.
------------------------------- Operations --------------------------------

 ?=? : (%, %) -> Boolean               coerce : % -> OutputForm
 copy : % -> %                         elt : (%, a) -> Integer
 elt : (%, b) -> Integer               ?~=? : (%, %) -> Boolean
 construct : (Integer, Integer) -> %
 setelt! : (%, a, Integer) -> Integer
 setelt! : (%, b, Integer) -> Integer

but construct seems to be treated in a rather special way by the interpreter since when I try to add a construct function to the Product domain, Axiom aborts.

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.

Yes, we are finally agreeing on something. Use '(A,B,C, ...)" for vanilla cartesian product and use Mapping(D, (A,B)) instead of 'Mapping(D,A,B)'; and better still allow Mapping((C,D),(A,B)).

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 CartesianProductCategory(L: List Domains), the projections should be exported, there is no requirement that they must be implemented. (That is the general situation currently in Axiom). To hide info, it is possible that the projections are only implemented as local functions in the domain. Whether you want to consider that as acceptable in Axiom is subject to further discussion, but mathematically, the domain remains a Cartesian product.

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 Mapping is syntactic sugar. You want to use an exponential notation and yet you want to count arity as the dimension of the cartesian product, but to count arity as the number of inputs in any other. So :

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