We finally come to the domain constructor. A few subtle differences between packages and domains turn up some interesting issues. We first discuss these differences then describe the resulting issues by illustrating a program for the QuadraticForm constructor. After a short example of an algebraic constructor, CliffordAlgebra, we show how you use domain constructors to build a database query facility.
Packages are special cases of domains. What is the difference between a package and a domain that is not a package? By definition, there is only one difference: a domain that is not a package has the symbol $ appearing somewhere among the types of its exported operations. The $ denotes ``this domain.'' If the $ appears before the -> in the type of a signature, it means the operation takes an element from the domain as an argument. If it appears after the ->, then the operation returns an element of the domain.
If no exported operations mention $, then evidently there is nothing of interest to do with the objects of the domain. You might then say that a package is a ``boring'' domain! But, as you saw in Chapter ugPackages, packages are a very useful notion indeed. The exported operations of a package depend solely on the parameters to the package constructor and other explicit domains.
To summarize, domain constructors are versatile structures that serve two distinct practical purposes: Those like Polynomial and List describe classes of computational objects; others, like SortPackage, describe packages of useful operations. As in the last chapter, we focus here on the first kind.
The syntax for defining a domain constructor is the same as for any function in Axiom:
As this definition usually extends over many lines, a expression is generally used instead. where
A recommended format for the definition of a domain is:
DomainForm : Exports == Implementation where
optional type declarations
Exports == [ Category Assertions] with
list of exported operations
Implementation == [ Add Domain] add
[Rep := Representation]
list of function definitions for exported operations
Note: The brackets [ ] here denote optionality.
A complete domain constructor definition for QuadraticForm is shown below. Interestingly, this little domain illustrates all the new concepts you need to learn.
A domain constructor can take any number and type of parameters. QuadraticForm takes a positive integer and a field as arguments. Like a package, a domain has a set of explicit exports and an implementation described by a capsule. Domain constructors are documented in the same way as package constructors.
Domain QuadraticForm(n, K), for a given positive integer and domain , explicitly exports three operations:
Compared with the corresponding syntax given for the definition of a package, you see that a domain constructor has three optional parts to its definition: Category Assertions, Add Domain, and Representation.
The Category Assertions part of your domain constructor definition lists those categories of which all domains created by the constructor are unconditionally members. The word ``unconditionally'' means that membership in a category does not depend on the values of the parameters to the domain constructor. This part thus defines the link between the domains and the category hierarchies given on the inside covers of this book. As described in ugCategoriesCorrectness it is this link that makes it possible for you to pass objects of the domains as arguments to other operations in Axiom.
Every QuadraticForm domain is declared to be unconditionally a member of category AbelianGroup. An abelian group is a collection of elements closed under addition. Every object x of an abelian group has an additive inverse y such that . The exports of an abelian group include , +, -, and scalar multiplication by an integer. After asserting that QuadraticForm domains are abelian groups, it is possible to pass quadratic forms to algorithms that only assume arguments to have these abelian group properties.
In ugCategoriesConditionals you saw that Fraction(R), a member of QuotientFieldCategory(R), is a member of OrderedSet if is a member of OrderedSet. Likewise, from the Exports part of the definition of ModMonic(R, S),
you see that ModMonic(R, S) is a member of Finite if is.
The Exports part of a domain definition is the same kind of expression that can appear to the right of an == in a category definition. If a domain constructor is unconditionally a member of two or more categories, a form is used. Join The Exports part of the definition of FlexibleArray(S) reads, for example:
Before looking at the Implementation part of QuadraticForm, let's try some examples.
Build a domain .
Define a matrix to be used to construct a quadratic form.
Construct the quadratic form. A package call $QF is necessary since there are other QuadraticForm domains.
Looks like a matrix. Try computing the number of rows. Axiom won't let you.
Create a direct product element . A package call is again necessary, but Axiom understands your list as denoting a vector.
Compute the product .
What is 3 times minus plus ?
The Browse facility of HyperDoc is useful for investigating the properties of domains, packages, and categories. From the main HyperDoc menu, move your mouse to Browse and click on the left mouse button. This brings up the Browse first page. Now, with your mouse pointer somewhere in this window, enter the string ``quadraticform'' into the input area (all lower case letters will do). Move your mouse to Constructors and click. Up comes a page describing QuadraticForm.
From here, click on Description. This gives you a page that includes a part labeled by `` Description:''. You also see the types for arguments and displayed as well as the fact that QuadraticForm returns an AbelianGroup. You can go and experiment a bit by selecting Field with your mouse. Eventually, use the ``UP'' button several times to return to the first page on QuadraticForm.
Select Operations to get a list of operations for QuadraticForm. You can select an operation by clicking on it to get an individual page with information about that operation. Or you can select the buttons along the bottom to see alternative views or get additional information on the operations. Then return to the page on QuadraticForm.
Select Cross Reference to get another menu. This menu has buttons for Parents, Ancestors, and others. Clicking on Parents, you see that QuadraticForm has one parent AbelianMonoid.
The Implementation part of an Axiom capsule for a domain constructor uses the special variable to Rep @ Rep identify the lower level data type used to represent the objects representation:of a domain of the domain. domain:representation The for quadratic forms is SquareMatrix(n, K). This means that all objects of the domain are required to be by matrices with elements from K.
The code for quadraticForm in Figure figquadform checks that the matrix is symmetric and then converts it to $, which means, as usual, ``this domain.'' Such explicit conversions conversion are generally required by the compiler. Aside from checking that the matrix is symmetric, the code for this function essentially does nothing. The m :: $ on line 28 coerces to a quadratic form. In fact, the quadratic form you created in step (3) of ugDomainsDemo is just the matrix you passed it in disguise! Without seeing this definition, you would not know that. Nor can you take advantage of this fact now that you do know! When we try in the next step of ugDomainsDemo to regard as a matrix by asking for nrows, the number of its rows, Axiom gives you an error message saying, in effect, ``Good try, but this won't work!''
The definition for the matrixmatrixQuadraticForm function could hardly be simpler: it just returns its argument after explicitly coercing its argument to a matrix. Since the argument is already a matrix, this coercion does no computation.
Within the context of a capsule, an object of $ is regarded both as a quadratic form and as a matrix.In case each of $ and have the same named operation available, the one from $ takes precedence. Thus, if you want the one from Rep, you must package call it using a $Rep suffix. This makes the definition of easy---it just calls the dotdotDirectProduct product from DirectProduct to perform the indicated operation.
To write functions that implement the operations of a domain, you want to choose the most computationally efficient data structure to represent the elements of your domain.
A classic problem in computer algebra is the optimal choice for an internal representation of polynomials. If you create a polynomial, say , how does Axiom hold this value internally? There are many ways. Axiom has nearly a dozen different representations of polynomials, one to suit almost any purpose. Algorithms for solving polynomial equations work most efficiently with polynomials represented one way, whereas those for factoring polynomials are most efficient using another. One often-used representation is a list of terms, each term consisting of exponent-coefficient records written in the order of decreasing exponents. For example, the polynomial is represented by the list .
What is the optimal data structure for a matrix? It depends on the application. For large sparse matrices, a linked-list structure of records holding only the non-zero elements may be optimal. If the elements can be defined by a simple formula , then a compiled function for may be optimal. Some programmers prefer to represent ordinary matrices as vectors of vectors. Others prefer to represent matrices by one big linear array where elements are accessed with linearly computable indexes.
While all these simultaneous structures tend to be confusing, Axiom provides a helpful organizational tool for such a purpose: categories. PolynomialCategory, for example, provides a uniform user interface across all polynomial types. Each kind of polynomial implements functions for all these operations, each in its own way. If you use only the top-level operations in PolynomialCategory you usually do not care what kind of polynomial implementation is used.
Within a given domain, however, you define (at most) one representation.You can make that representation a Union type, however. See ugTypesUnions for examples of unions. If you want to have multiple representations (that is, several domains, each with its own representation), use a category to describe the Exports, then define separate domains for each representation.
The capsule part of Implementation defines functions that implement the operations exported by the domain---usually only some of the operations. In our demo in ugDomainsDemo we asked for the value of . Where do the operations *, +, and - come from? There is no definition for them in the capsule!
The Implementation part of a definition can domain:add optionally specify an ``add-domain'' to the left of an add add (for QuadraticForm, defines SquareMatrix(n,K) is the add-domain). The meaning of an add-domain is simply this: if the capsule part of the Implementation does not supply a function for an operation, Axiom goes to the add-domain to find the function. So do , and (from QuadraticForm) come from SquareMatrix(n,K)?
In Chapter ugPackages we saw that categories can provide default implementations for their operations. How and when are they used? When Axiom finds that QuadraticForm(2, Fraction Integer) does not implement the operations *, +, and -, it goes to SquareMatrix(2,Fraction Integer) to find it. As it turns out, SquareMatrix(2, Fraction Integer) does not implement any of these operations!
What does Axiom do then? Here is its overall strategy. First, Axiom looks for a function in the capsule for the domain. If it is not there, Axiom looks in the add-domain for the operation. If that fails, Axiom searches the add-domain of the add-domain, and so on. If all those fail, it then searches the default packages for the categories of which the domain is a member. In the case of QuadraticForm, it searches AbelianGroup, then its parents, grandparents, and so on. If this fails, it then searches the default packages of the add-domain. Whenever a function is found, the search stops immediately and the function is returned. When all fails, the system calls error to report this unfortunate news to you. To find out the actual order of constructors searched for QuadraticForm, consult Browse: from the QuadraticForm, click on Cross Reference, then on Lineage.
Let's apply this search strategy for our example . The scalar multiplication comes first. Axiom finds a default implementation in AbelianGroup&. Remember from ugCategoriesDefaults that SemiGroup provides a default definition for by repeated squaring. AbelianGroup similarly provides a definition for by repeated doubling.
But the search of the defaults for QuadraticForm fails to find any + or * in the default packages for the ancestors of QuadraticForm. So it now searches among those for SquareMatrix. Category MatrixCategory, which provides a uniform interface for all matrix domains, is a grandparent of SquareMatrix and has a capsule defining many functions for matrices, including matrix addition, subtraction, and scalar multiplication. The default package MatrixCategory& is where the functions for and (from QuadraticForm) come from.
You can use Browse to discover where the operations for QuadraticForm are implemented. First, get the page describing QuadraticForm. With your mouse somewhere in this window, type a ``2'', press the Tab key, and then enter ``Fraction Integer'' to indicate that you want the domain QuadraticForm(2, Fraction Integer). Now click on Operations to get a table of operations and on * to get a page describing the * operation. Finally, click on implementation at the bottom.
Aside from the notion of where an operation is implemented, operation:origin a useful notion is the origin or ``home'' of an operation. When an operation (such as quadraticFormquadraticFormQuadraticForm) is explicitly exported by a domain (such as QuadraticForm), you can say that the origin of that operation is that domain. If an operation is not explicitly exported from a domain, it is inherited from, and has as origin, the (closest) category that explicitly exports it. The operations and (from AbelianMonoid) of QuadraticForm, for example, are inherited from AbelianMonoid. As it turns out, AbelianMonoid is the origin of virtually every + operation in Axiom!
Again, you can use Browse to discover the origins of operations. From the Browse page on QuadraticForm, click on Operations, then on origins at the bottom of the page.
The origin of the operation is the only place where on-line documentation is given. However, you can re-export an operation to give it special documentation. Suppose you have just invented the world's fastest algorithm for inverting matrices using a particular internal representation for matrices. If your matrix domain just declares that it exports MatrixCategory, it exports the inverse operation, but the documentation the user gets from Browse is the standard one from MatrixCategory. To give your version of inverse the attention it deserves, simply export the operation explicitly with new documentation. This redundancy gives inverse a new origin and tells Browse to present your new documentation.
In Axiom, a domain could be defined using only an add-domain and no capsule. Although we talk about rational numbers as quotients of integers, there is no type RationalNumber in Axiom. To create such a type, you could compile the following ``short-form'' definition:
The Exports part of this definition is missing and is taken to be equivalent to that of Fraction(Integer). Because of the add-domain philosophy, you get precisely what you want. The effect is to create a little stub of a domain. When a user asks to add two rational numbers, Axiom would ask RationalNumber for a function implementing this +. Since the domain has no capsule, the domain then immediately sends its request to Fraction (Integer).
The short form definition for domains is used to define such domains as MultivariatePolynomial: MultivariatePolynomial
Now that we have QuadraticForm available, let's put it to use. Given some quadratic form described by an by matrix over a field , the domain CliffordAlgebra(n, K, Q) defines a vector space of dimension over . This is an interesting domain since complex numbers, quaternions, exterior algebras and spin algebras are all examples of Clifford algebras.
The basic idea is this: the quadratic form defines a basis for the vector space , the direct product of with itself times. From this, the Clifford algebra generates a basis of elements given by all the possible products of the in order without duplicates, that is,
1, , , , , , , , and so on.
The algebra is defined by the relations
Now look at the snapshot of its definition given below. Lines 9-10 show part of the definitions of the Exports. A Clifford algebra over a field is asserted to be a ring, an algebra over , and a vector space over . Its explicit exports include which returns the -th unit element.
The Implementation part begins by defining a local variable to hold the list of all where runs over the unit vectors from 1 to the dimension . Another local variable is set to , computed once and for all. The representation for the domain is PrimitiveArray(K), which is a basic array of elements from domain . Line 18 defines as shorthand for the more lengthy expression , which computes a primitive array of length filled with 's from domain .
Lines 19-22 define the sum of two elements and straightforwardly. First, a new array of all 's is created, then filled with the sum of the corresponding elements. Indexing for primitive arrays starts at 0. The definition of the product of and first requires the definition of a local function addMonomProd. Axiom knows it is local since it is not an exported function. The types of all local functions must be declared.
We now turn to an entirely different kind of application, building a query language for a database.
Here is the practical problem to solve. The Browse facility of Axiom has a database for all operations and constructors which is stored on disk and accessed by HyperDoc. For our purposes here, we regard each line of this file as having eight fields: class, name, type, nargs, exposed, kind, origin, and condition. Here is an example entry:
In English, the entry means:
Our task is to create a little query language that allows us to get useful information from this database.
First we design a simple language for accessing information from the database. We have the following simple model in mind for its design. Think of the database as a box of index cards. There is only one search operation---it takes the name of a field and a predicate predicate (a boolean-valued function) defined on the fields of the index cards. When applied, the search operation goes through the entire box selecting only those index cards for which the predicate is true. The result of a search is a new box of index cards. This process can be repeated again and again.
The predicates all have a particularly simple form: symbol = pattern, where symbol designates one of the fields, and pattern is a ``search string''---a string that may contain a `` *'' as a wildcard. Wildcards match any substring, including the empty string. Thus the pattern `` "*ma*t'' matches `` "mat",'' doormat'' and `` smart''.
To illustrate how queries are given, we give you a sneak preview of the facility we are about to create.
Extract the database of all Axiom operations.
How many exposed three-argument map operations involving streams?
As usual, the arguments of elt ( .) associate to the left. The first elt produces the set of all operations with name map. The second elt produces the set of all map operations with three arguments. The third elt produces the set of all three-argument map operations having a type mentioning Stream.
Another thing we'd like to do is to extract one field from each of the index cards in the box and look at the result. Here is an example of that kind of request.
What constructors explicitly export a determinant operation?
The first elt produces the set of all index cards with name determinant. The second elt extracts the origin component from each index card. Each origin component is the name of a constructor which directly exports the operation represented by the index card. Extracting a component from each index card produces what we call a datalist. The third elt, sort, causes the datalist of origins to be sorted in alphabetic order. The fourth, unique, causes duplicates to be removed.
Before giving you a more extensive demo of this facility, we now build the necessary domains and packages to implement it. We will introduce a few of our minor conveniences.
We work from the top down. First, we define a database, our box of index cards, as an abstract datatype. For sake of illustration and generality, we assume that an index card is some type , and that a database is a box of objects of type . Here is the Axiom program defining the Database domain.
The domain constructor takes a parameter , which stands for the class of index cards. We describe an index card later. Here think of an index card as a string which has the eight fields mentioned above.
First we tell Axiom what operations we are going to require from index cards. We need an elt to extract the contents of a field (such as name and type) as a string. For example, returns a string that is the content of the field on the index card . We need to display an index card in two ways: display shows only the name and type of an operation; fullDisplay displays all fields. The display operations return no useful information and thus have return type Void.
Next we tell Axiom what operations the user can apply to the database. This part defines our little query language. The most important operation is db . field = pattern which returns a new database, consisting of all index cards of db such that the part of the index card is matched by the string pattern called . The expression field = pattern is an object of type QueryEquation (defined in the next section).
Another elt is needed to produce a DataList object. Operation + is to merge two databases together; - is used to subtract away common entries in a second database from an initial database. There are three display functions. The fullDisplay function has two versions: one that prints all the records, the other that prints only a fixed number of records. A coerce to OutputForm creates a display object.
The Implementation part of Database is straightforward.
The database is represented by a list of elements of (index cards). We leave the definition of the first elt operation (on line 4) until the next section. The second elt collects all the strings with field name key into a list. The display function and first fullDisplay function simply call the corresponding functions from . The second fullDisplay function provides an efficient way of printing out a portion of a large list. The + is defined by using the existing mergemergeList operation defined on lists, then removing duplicates from the result. The - operation requires writing a corresponding subtraction operation. A package MergeThing (not shown) provides this.
The coerce function converts the database to an OutputForm by computing the number of index cards. This is a good example of the independence of the representation of an Axiom object from how it presents itself to the user. We usually do not want to look at a database---but do care how many ``hits'' we get for a given query. So we define the output representation of a database to be simply the number of index cards our query finds.
The predicate for our search is given by an object of type QueryEquation. Axiom does not have such an object yet so we have to invent it.
Axiom converts an input expression of the form to . Our equations always have a symbol on the left and a string on the right. The Exports part thus specifies an operation equation to create a query equation, and variable and value to select the left- and right-hand sides. The Implementation part uses Record for a space-efficient representation of an equation.
Here is the missing definition for the elt function of Database in the last section:
Recall that a database is represented by a list. Line 4 simply runs over that list collecting all elements such that the pattern (that is, ) matches the selected field of the element.
Type DataList is a new type invented to hold the result of selecting one field from each of the index cards in the box. It is useful to make datalists extensions of lists---lists that have special elt operations defined on them for sorting and removing duplicates.
The Exports part asserts that datalists belong to the category ListAggregate. Therefore, you can use all the usual list operations on datalists, such as firstfirstList, restrestList, and concatconcatList. In addition, datalists have four explicit operations. Besides the three elt operations, there is a coerce operation that creates datalists from lists.
The Implementation part needs only to define four functions. All the rest are obtained from List(S).
An index card comes from a file as one long string. We define functions that extract substrings from the long string. Each field has a name that is passed as a second argument to elt.
We leave the Implementation part to the reader. All operations involve straightforward string manipulations.
We must not forget one important operation: one that builds the database in the first place! We'll name it getDatabase and put it in a package. This function is implemented by calling the Common Lisp function to get appropriate information from Browse. This operation takes a string indicating which lines you want from the database: `` o'' gives you all operation lines, and `` k'', all constructor lines. Similarly, `` c'', `` d'', and `` p'' give you all category, domain and package lines respectively.
We do not bother creating a special name for databases of index cards. Database (IndexCard) will do. Notice that we used the package OperationsQuery to create, in effect, a new kind of domain: Database(IndexCard).
To create the database facility, you put all these constructors into one file.You could use separate files, but we are putting them all together because, organizationally, that is the logical thing to do. At the top of the file put )abbrev commands, giving the constructor abbreviations you created.
With all this in alql.spad, for example, compile it using compile
and then load each of the constructors:
Our first set of queries give some statistics on constructors in the current Axiom system.
How many constructors does Axiom have?
Break this down into the number of categories, domains, and packages.
What are all the domain constructors that take no parameters?
How many constructors have ``Matrix'' in their name?
What are the names of those that are domains?
How many operations are there in the library?
Break this down into categories, domains, and packages.
The query language is helpful in getting information about a particular operation you might like to apply. While this information can be obtained with Browse, the use of the query database gives you data that you can manipulate in the workspace.
How many operations have ``eigen'' in the name?
What are their names?
Where do they come from?
The operations + and - are useful for constructing small databases and combining them. However, remember that the only matching you can do is string matching. Thus a pattern such as "*Matrix*" on the type field matches any type containing Matrix, MatrixCategory, SquareMatrix, and so on.
How many operations mention ``Matrix'' in their type?
How many operations come from constructors with ``Matrix'' in their name?
How many operations are in but not in ?
Display the operations that both mention ``Matrix'' in their type and come from a constructor having ``Matrix'' in their name.
How many operations involve matrices?
Display 4 of them.
How many distinct names of operations involving matrices are there?