This chapter unravels the mysteries of categories---what category they are, how they are related to domains and packages, category:constructor how they are defined in Axiom, and how you can extend the constructor:category system to include new categories of your own.
We assume that you have read the introductory material on domains and categories in ugTypesBasicDomainCons . There you learned that the notion of packages covered in the previous chapter are special cases of domains. While this is in fact the case, it is useful here to regard domains as distinct from packages.
Think of a domain as a datatype, a collection of objects (the objects of the domain). From your ``sneak preview'' in the previous chapter, you might conclude that categories are simply named clusters of operations exported by domains. As it turns out, categories have a much deeper meaning. Categories are fundamental to the design of Axiom. They control the interactions between domains and algorithmic packages, and, in fact, between all the components of Axiom.
Categories form hierarchies as shown on the inside cover pages of this book. The inside front-cover pages illustrate the basic algebraic hierarchy of the Axiom programming language. The inside back-cover pages show the hierarchy for data structures.
Think of the category structures of Axiom as a foundation for a city on which superstructures (domains) are built. The algebraic hierarchy, for example, serves as a foundation for constructive mathematical algorithms embedded in the domains of Axiom. Once in place, domains can be constructed, either independently or from one another.
Superstructures are built for quality---domains are compiled into machine code for run-time efficiency. You can extend the foundation in directions beyond the space directly beneath the superstructures, then extend selected superstructures to cover the space. Because of the compilation strategy, changing components of the foundation generally means that the existing superstructures (domains) built on the changed parts of the foundation (categories) have to be rebuilt---that is, recompiled.
Before delving into some of the interesting facts about categories, let's see how you define them in Axiom.
A category is defined by a function with exactly the same format as category:definition any other function in Axiom.
The definition of a category has the syntax:
CategoryForm : Category == Extensions [ with Exports ]
The brackets [ ] here indicate optionality.
The first example of a category definition is SetCategory, the most basic of the algebraic categories in Axiom. SetCategory
The definition starts off with the name of the category (SetCategory); this is always in column one in the source file. All parts of a category definition are then indented with respect to this indentation first line.
In Chapter ugTypes , we talked about Ring as denoting the class of all domains that are rings, in short, the class of all rings. While this is the usual naming convention in Axiom, it is also common to use the word ``Category'' at the end of a category name for clarity. The interpretation of the name SetCategory is, then, ``the category of all domains that are (mathematical) sets.''
The name SetCategory is followed in the definition by its formal parameters enclosed in parentheses (). Here there are no parameters. As required, the type of the result of this category function is the distinguished name Category.
Then comes the ==. As usual, what appears to the right of the == is a definition, here, a category definition. A category definition always has two parts separated by the reserved word with . Debugging hint: it is very easy to forget the !
The first part tells what categories the category extends. Here, the category extends two categories: Type, the category of all domains, and CoercibleTo(OutputForm). CoercibleTo(OutputForm) can also be written (and is written in the definition above) without parentheses. The operation is a system-defined operation that Join forms a single category from two or more other categories.
Every category other than Type is an extension of some other category. If, for example, SetCategory extended only the category Type, the definition here would read ``Type with ...''. In fact, the Type is optional in this line; ``with ...'' suffices.
To the right of the is a list of with all the exports of the category. Each exported operation has a name and a type expressed by a declaration of the form ``name: type''.
Categories can export symbols, as well as 0 and 1 which denote domain constants.The numbers 0 and 1 are operation names in Axiom. In the current implementation, all other exports are operations with types expressed as mappings with the syntax
source -> target
The category SetCategory has a single export: the operation whose type is given by the mapping ($, $) -> Boolean. The $ in a mapping type always means ``the domain.'' Thus the operation takes two arguments from the domain and returns a value of type Boolean.
The source part of the mapping here is given by a tuple tuple consisting of two or more types separated by commas and enclosed in parentheses. If an operation takes only one argument, you can drop the parentheses around the source type. If the mapping has no arguments, the source part of the mapping is either left blank or written as (). Here are examples of formats of various operations with some contrived names.
The definition of SetCategory above is missing an important component: its library documentation. documentation Here is its definition, complete with documentation.
Documentary comments are an important part of constructor definitions. Documentation is given both for the category itself and for each export. A description for the category precedes the code. Each line of the description begins in column one with ++. The description starts with the word Description:.Other information such as the author's name, date of creation, and so on, can go in this area as well but are currently ignored by Axiom. All lines of the description following the initial line are indented by the same amount.
Surround the name of any constructor (with or without parameters) with an {\bf }. Similarly, surround an operator name with {\tt }, an Axiom operation with {\bf }, and a variable or Axiom expression with $$. Library documentation is given in a TeX-like language so that it can be used both for hard-copy and for Browse. These different wrappings cause operations and types to have mouse-active buttons in Browse. For hard-copy output, wrapped expressions appear in a different font. The above documentation appears in hard-copy as:
SetCategory is the basic category for describing a collection of elements with = (equality) and a coerce to OutputForm.
and
tests if and are equal.
For our purposes in this chapter, we omit the documentation from further category descriptions.
A second example of a category is SemiGroup, defined by: SemiGroup
This definition is as simple as that for SetCategory, except that there are two exported operations. Multiple exported operations are written as a pile, that is, they all begin in the same column. Here you see that the category mentions another type, PositiveInteger, in a signature. Any domain can be used in a signature.
Since categories extend one another, they form hierarchies. Each category other than Type has one or more parents given by the one or more categories mentioned before the part of the definition. SemiGroup extends SetCategory and SetCategory extends both Type and CoercibleTo (OutputForm). Since CoercibleTo (OutputForm) also extends Type, the mention of Type in the definition is unnecessary but included for emphasis.
We say a category designates a class of domains. What class of domains? category:membership That is, how does Axiom know what domains belong to what categories? The simple answer to this basic question is key to the design of Axiom:
Domains belong to categories by assertion.
When a domain is defined, it is asserted to belong to one or more categories. Suppose, for example, that an author of domain String wishes to use the binary operator to denote concatenation. Thus would produce the string . Actually, concatenation of strings in Axiom is done by juxtaposition or by using the operation concatconcatString. The expression produces the string . The author of String could then assert that String is a member of SemiGroup. According to our definition of SemiGroup, strings would then also have the operation defined automatically. Then would produce a string of eight dashes . Since String is a member of SemiGroup, it also is a member of SetCategory and thus has an operation for testing that two strings are equal.
Now turn to the algebraic category hierarchy inside the front cover of this book. Any domain that is a member of a category extending SemiGroup is a member of SemiGroup (that is, it is a semigroup). In particular, any domain asserted to be a Ring is a semigroup since Ring extends Monoid, that, in turn, extends SemiGroup. The definition of Integer in Axiom asserts that Integer is a member of category IntegerNumberSystem, that, in turn, asserts that it is a member of EuclideanDomain. Now EuclideanDomain extends PrincipalIdealDomain and so on. If you trace up the hierarchy, you see that EuclideanDomain extends Ring, and, therefore, SemiGroup. Thus Integer is a semigroup and also exports the operations and .
We actually omitted the last category:defaults part of the definition of default definitions SemiGroup in ugCategoriesHier . Here now is its complete Axiom definition.
The part at the end is used to give ``default definitions'' for add exported operations. Once you have a multiplication operation , you can define exponentiation for positive integer exponents using repeated multiplication:
This definition for is called a default definition. In general, a category can give default definitions for any operation it exports. Since SemiGroup and all its category descendants in the hierarchy export , any descendant category may redefine as well.
A domain of category SemiGroup (such as Integer) may or may not choose to define its own operation. If it does not, a default definition that is closest (in a ``tree-distance'' sense of the hierarchy) to the domain is chosen.
The part of the category definition following an operation is a capsule, as discussed in the previous chapter. The line
references the package RepeatedSquaring($), that is, the package RepeatedSquaring that takes ``this domain'' as its parameter. For example, if the semigroup Polynomial (Integer) does not define its own exponentiation operation, the definition used may come from the package RepeatedSquaring (Polynomial (Integer)). The next line gives the definition in terms of expt from that package.
The default definitions are collected to form a ``default package'' for the category. The name of the package is the same as the category but with an ampersand (&) added at the end. A default package always takes an additional argument relative to the category. Here is the definition of the default package SemiGroup& as automatically generated by Axiom from the above definition of SemiGroup.
In the previous section you saw the complete Axiom program defining axiom SemiGroup. According to this definition semigroups are sets with the operations * and **. SemiGroup
You might ask: ``Aside from the notion of default packages, isn't a category just a macro, that is, a shorthand equivalent to the two operations and with their types?'' If a category were a macro, every time you saw the word SemiGroup, you would rewrite it by its list of exported operations. Furthermore, every time you saw the exported operations of SemiGroup among the exports of a constructor, you could conclude that the constructor exported SemiGroup.
A category is not a macro and here is why. The definition for SemiGroup has documentation that states:
Category SemiGroup denotes the class of all multiplicative semigroups, that is, a set with an associative operation .
Axioms:
associative("*" : ($,$)->$) -- (x*y)*z = x*(y*z)
According to the author's remarks, the mere exporting of an operation named and is not enough to qualify the domain as a SemiGroup. In fact, a domain can be a semigroup only if it explicitly exports a and a satisfying the associativity axiom.
In general, a category name implies a set of axioms, even mathematical theorems. There are numerous axioms from Ring, for example, that are well-understood from the literature. No attempt is made to list them all. Nonetheless, all such mathematical facts are implicit by the use of the name Ring.
While such statements are only comments, correctness Axiom can enforce their intention simply by shifting the burden of responsibility onto the author of a domain. A domain belongs to category only if the author asserts that the domain belongs to Ring or to a category that extends Ring.
This principle of assertion is important for large user-extendable systems. Axiom has a large library of operations offering facilities in many areas. Names such as norm and product, for example, have diverse meanings in diverse contexts. An inescapable hindrance to users would be to force those who wish to extend Axiom to always invent new names for operations. I don't think disambiguate is really a word, though I like it Axiom allows you to reuse names, and then use context to disambiguate one from another.
Here is another example of why this is important. Some languages, such as APL, APL denote the Boolean constants true and false by the integers and . You may want to let infix operators and serve as the logical operators or and and, respectively. But note this: Boolean is not a ring. The inverse axiom for Ring states:
Every element has an additive inverse such that .
Boolean is not a ring since true has no inverse---there is no inverse element such that (in terms of booleans, (true or a) = false). Nonetheless, Axiom could easily and correctly implement Boolean this way. Boolean simply would not assert that it is of category Ring. Thus the ``+'' for Boolean values is not confused with the one for Ring. Since the Polynomial constructor requires its argument to be a ring, Axiom would then refuse to build the domain Polynomial(Boolean). Also, Axiom would refuse to wrongfully apply algorithms to Boolean elements that presume that the ring axioms for ``+'' hold.
Most axioms are not computationally useful. Those that are can be explicitly expressed by what Axiom calls an attribute. The attribute commutative("*"), for example, is used to assert that a domain has commutative multiplication. Its definition is given by its documentation:
A domain has commutative("*") if it has an operation "*": (R,R)->R such that .
Just as you can test whether a domain has the category Ring, you can test that a domain has a given attribute.
Do polynomials over the integers have commutative multiplication?
Do matrices over the integers have commutative multiplication?
Attributes are used to conditionally export and define operations for a domain (see ugDomainsAssertions ). Attributes can also be asserted in a category definition.
After mentioning category Ring many times in this book, it is high time that we show you its definition: Ring
There are only two new things here. First, look at the $$ on the last line. This is not a typographic error! The first $ says that the is to come from some domain. The second $ says that the domain is ``this domain.'' If $ is Fraction(Integer), this line reads coerce(n) == n * 1$Fraction(Integer).
The second new thing is the presence of attribute `` ''. Axiom can always distinguish an attribute from an operation. An operation has a name and a type. An attribute has no type. The attribute unitsKnown asserts a rather subtle mathematical fact that is normally taken for granted when working with rings.With this axiom, the units of a domain are the set of elements that each have a multiplicative inverse in the domain. Thus and are units in domain Integer. Also, for Fraction Integer, the domain of rational numbers, all non-zero elements are units. Because programs can test for this attribute, Axiom can correctly handle rather more complicated mathematical structures (ones that are similar to rings but do not have this attribute).
Like domain constructors, category constructors can also have parameters. For example, category MatrixCategory is a parameterized category for defining matrices over a ring so that the matrix domains can have different representations and indexing schemes. Its definition has the form:
The category extends TwoDimensionalArrayCategory with the same arguments. You cannot find TwoDimensionalArrayCategory in the algebraic hierarchy listing. Rather, it is a member of the data structure hierarchy, given inside the back cover of this book. In particular, TwoDimensionalArrayCategory is an extension of HomogeneousAggregate since its elements are all one type.
The domain Matrix(R), the class of matrices with coefficients from domain , asserts that it is a member of category MatrixCategory(R, Vector(R), Vector(R)). The parameters of a category must also have types. The first parameter to MatrixCategory is required to be a ring. The second and third are required to be domains of category FiniteLinearAggregate(R). This is another extension of HomogeneousAggregate that you can see in the data structure hierarchy. In practice, examples of categories having parameters other than domains are rare.
Adding the declarations for parameters to the definition for MatrixCategory, we have:
As categories have parameters, the actual operations exported by a conditional category can depend on these parameters. As an example, the operation determinantdeterminantMatrixCategory from category MatrixCategory is only exported when the underlying domain has commutative multiplication:
Conditionals can also define conditional extensions of a category. Here is a portion of the definition of QuotientFieldCategory: QuotientFieldCategory
Think of category QuotientFieldCategory(R) as denoting the domain Fraction(R), the class of all fractions of the form for elements of . The first conditional means in English: ``If the elements of are totally ordered ( is an OrderedSet), then so are the fractions ''. Fraction
The second conditional is used to conditionally export an operation ceiling which returns the smallest integer greater than or equal to its argument. Clearly, ``ceiling'' makes sense for integers but not for polynomials and other algebraic structures. Because of this conditional, the domain Fraction(Integer) exports an operation ceiling: Fraction Integer->Integer, but Fraction Polynomial Integer does not.
Conditionals can also appear in the default definitions for the operations of a category. For example, a default definition for ceilingceilingField within the part following the reads:
Here the predicate used is identical to the predicate in the Exports part. This need not be the case. See ugPackagesConds for a more complicated example.
The part of a category to the right of a with is also regarded as a category---an ``anonymous category.'' Thus you have already seen a category definition category:anonymous in Chapter ugPackages . The Exports part of the package DrawComplex (ugPackagesAbstract ) is an anonymous category. This is not necessary. We could, instead, give this category a name:
and then define DrawComplex by:
There is no reason, however, to give this list of exports a name since no other domain or package exports it. In fact, it is rare for a package to export a named category. As you will see in the next chapter, however, it is very common for the definition of domains to mention one or more category before the with. with