The AssociationList constructor provides a general structure for associative storage. This type provides association lists in which data objects can be saved according to keys of any type. For a given association list, specific types must be chosen for the keys and entries. You can think of the representation of an association list as a list of records with key and entry fields.
Association lists are a form of table and so most of the operations available for Table are also available for AssociationList. They can also be viewed as lists and can be manipulated accordingly.
This is a Record type with age and gender fields.
In this expression, al is declared to be an association list whose keys are strings and whose entries are the above records.
The tabletableAssociationList operation is used to create an empty association list.
You can use assignment syntax to add things to the association list.
Perhaps we should have included a species field.
Now look at what is in the association list. Note that the last-added (key, entry) pair is at the beginning of the list.
You can reset the entry for an existing key.
Use deletedeleteAssociationList to destructively remove an element of the association list. Use deletedeleteAssociationList to return a copy of the association list with the element deleted. The second argument is the index of the element to delete.
For more information about tables, see TableXmpPage . For more information about lists, see ListXmpPage .
BalancedBinaryTrees(S) is the domain of balanced binary trees with elements of type S at the nodes. A binary tree is either empty or else consists of a node having a value and two branches, each branch a binary tree. A balanced binary tree is one that is balanced with respect its leaves. One with leaves is perfectly ``balanced'': the tree has minimum depth, and the left and right branch of every interior node is identical in shape.
Balanced binary trees are useful in algebraic computation for so-called ``divide-and-conquer'' algorithms. Conceptually, the data for a problem is initially placed at the root of the tree. The original data is then split into two subproblems, one for each subtree. And so on. Eventually, the problem is solved at the leaves of the tree. A solution to the original problem is obtained by some mechanism that can reassemble the pieces. In fact, an implementation of the Chinese Remainder Algorithm using balanced binary trees was first proposed by David Y. Y. Yun at the IBM T. J. Watson Research Center in Yorktown Heights, New York, in 1978. It served as the prototype for polymorphic algorithms in Axiom.
In what follows, rather than perform a series of computations with a single expression, the expression is reduced modulo a number of integer primes, a computation is done with modular arithmetic for each prime, and the Chinese Remainder Algorithm is used to obtain the answer to the original problem. We illustrate this principle with the computation of .
A list of moduli.
The expression modTree(n, lm) creates a balanced binary tree with leaf values n mod m for each modulus m in lm.
Operation modTree does this using operations on balanced binary trees. We trace its steps. Create a balanced binary tree t of zeros with four leaves.
The leaves of the tree are set to the individual moduli.
Use mapUp! to do a bottom-up traversal of t, setting each interior node to the product of the values at the nodes of its children.
The value at the node of every subtree is the product of the moduli of the leaves of the subtree.
Operation mapDown!(t,a,fn) replaces the value v at each node of t by fn(a,v).
The operation leaves returns the leaves of the resulting tree. In this case, it returns the list of 12 mod m for each modulus m.
Compute the square of the images of 12 modulo each m.
Call the Chinese Remainder Algorithm to get the answer for .
A basic operator is an object that can be symbolically applied to a list of arguments from a set, the result being a kernel over that set or an expression. In addition to this section, please see ExpressionXmpPage and KernelXmpPage for additional information and examples.
You create an object of type BasicOperator by using the operatoroperatorBasicOperator operation. This first form of this operation has one argument and it must be a symbol. The symbol should be quoted in case the name has been used as an identifier to which a value has been assigned.
A frequent application of BasicOperator is the creation of an operator to represent the unknown function when solving a differential equation.
Let y be the unknown function in terms of x.
This is how you enter the equation y'' + y' + y = 0.
To solve the above equation, enter this.
Use the single argument form of operatoroperatorBasicOperator (as above) when you intend to use the operator to create functional expressions with an arbitrary number of arguments
Nary means an arbitrary number of arguments can be used in the functional expressions.
Use the two-argument form when you want to restrict the number of arguments in the functional expressions created with the operator.
This operator can only be used to create functional expressions with one argument.
Use arityarityBasicOperator to learn the number of arguments that can be used. It returns "false" if the operator is nary.
Use namenameBasicOperator to learn the name of an operator.
Use is?is?BasicOperator to learn if an operator has a particular name.
You can also use a string as the name to be tested against.
You can attached named properties to an operator. These are rarely used at the top-level of the Axiom interactive environment but are used with Axiom library source code.
By default, an operator has no properties.
The interface for setting and getting properties is somewhat awkward because the property values are stored as values of type None.
Attach a property by using setPropertysetPropertyBasicOperator.
We know the property value has type String.
Use deleteProperty!deleteProperty!BasicOperator to destructively remove a property.
All rational numbers have repeating binary expansions. Operations to access the individual bits of a binary expansion can be obtained by converting the value to RadixExpansion(2). More examples of expansions are available in DecimalExpansionXmpPage , HexadecimalExpansionXmpPage , and RadixExpansionXmpPage .
The expansion (of type BinaryExpansion) of a rational number is returned by the binarybinaryBinaryExpansion operation.
Arithmetic is exact.
The period of the expansion can be short or long ...
or very long.
These numbers are bona fide algebraic objects.
BinarySearchTree(R) is the domain of binary trees with elements of type R, ordered across the nodes of the tree. A non-empty binary search tree has a value of type R, and right and left binary search subtrees. If a subtree is empty, it is displayed as a period (``.'').
Define a list of values to be placed across the tree. The resulting tree has 8 at the root; all other elements are in the left subtree.
A convenient way to create a binary search tree is to apply the operation binarySearchTree to a list of elements.
Another approach is to first create an empty binary search tree of integers.
Insert the value 8. This establishes 8 as the root of the binary search tree. Values inserted later that are less than 8 get stored in the left subtree, others in the right subtree.
Insert the value 3. This number becomes the root of the left subtree of t1. For optimal retrieval, it is thus important to insert the middle elements first.
We go back to the original tree t. The leaves of the binary search tree are those which have empty left and right subtrees.
The operation split(k,t) returns a record containing the two subtrees: one with all elements ``less'' than k, another with elements ``greater'' than k.
Define insertRoot to insert new elements by creating a new node.
The new node puts the inserted value between its ``less'' tree and ``greater'' tree.
Function buildFromRoot builds a binary search tree from a list of elements ls and the empty tree emptybst.
Apply this to the reverse of the list lv.
Have Axiom check that these are equal.
The CardinalNumber domain can be used for values indicating the cardinality of sets, both finite and infinite. For example, the dimensiondimensionVectorSpace operation in the category VectorSpace returns a cardinal number.
The non-negative integers have a natural construction as cardinals
The fact that 0 acts as a zero for the multiplication of cardinals is equivalent to the axiom of choice.
Cardinal numbers can be created by conversion from non-negative integers.
They can also be obtained as the named cardinal Aleph(n).
The finite?finite?CardinalNumber operation tests whether a value is a finite cardinal, that is, a non-negative integer.
Similarly, the countable?countable?CardinalNumber operation determines whether a value is a countable cardinal, that is, finite or Aleph(0).
Arithmetic operations are defined on cardinal numbers as follows: If x = #X and y = #Y then
Here are some arithmetic examples.
Subtraction is a partial operation: it is not defined when subtracting a larger cardinal from a smaller one, nor when subtracting two equal infinite cardinals.
The generalized continuum hypothesis asserts that
and is independent of the axioms of set theory. Goedel, The consistency of the continuum hypothesis, Ann. Math. Studies, Princeton Univ. Press, 1940.
The CardinalNumber domain provides an operation to assert whether the hypothesis is to be assumed.
When the generalized continuum hypothesis is assumed, exponentiation to a transfinite power is allowed.
Three commonly encountered cardinal numbers are
In this domain, these values are obtained under the generalized continuum hypothesis in this way.
CartesianTensor(i0,dim,R) provides Cartesian tensors with components belonging to a commutative ring R. Tensors can be described as a generalization of vectors and matrices. This gives a concise tensor algebra for multilinear objects supported by the CartesianTensor domain. You can form the inner or outer product of any two tensors and you can add or subtract tensors with the same number of components. Additionally, various forms of traces and transpositions are useful.
The CartesianTensor constructor allows you to specify the minimum index for subscripting. In what follows we discuss in detail how to manipulate tensors.
Here we construct the domain of Cartesian tensors of dimension 2 over the integers, with indices starting at 1.
Scalars can be converted to tensors of rank zero.
Vectors (mathematical direct products, rather than one dimensional array structures) can be converted to tensors of rank one.
Matrices can be converted to tensors of rank two.
In general, a tensor of rank k can be formed by making a list of rank k-1 tensors or, alternatively, a k-deep nested list of lists.
Given two tensors of rank k1 and k2, the outer productproductCartesianTensor forms a new tensor of rank k1+k2. Here
The inner product (contractcontractCartesianTensor) forms a tensor of rank k1+k2-2. This product generalizes the vector dot product and matrix-vector product by summing component products along two indices.
Here we sum along the second index of and the first index of . Here
The multiplication operator * is scalar multiplication or an inner product depending on the ranks of the arguments.
If either argument is rank zero it is treated as scalar multiplication. Otherwise, a*b is the inner product summing the last index of a with the first index of b.
This definition is consistent with the inner product on matrices and vectors.
For tensors of low rank (that is, four or less), components can be selected by applying the tensor to its indices.
A general indexing mechanism is provided for a list of indices.
The general mechanism works for tensors of arbitrary rank, but is somewhat less efficient since the intermediate index list must be created.
A ``contraction'' between two tensors is an inner product, as we have seen above. You can also contract a pair of indices of a single tensor. This corresponds to a ``trace'' in linear algebra. The expression contract(t,k1,k2) forms a new tensor by summing the diagonal given by indices in position k1 and k2.
This is the tensor given by
Since Tmn is the outer product of matrix m and matrix n, the above is equivalent to this.
In this and the next few examples, we show all possible contractions of Tmn and their matrix algebra equivalents.
You can exchange any desired pair of indices using the transposetransposeCartesianTensor operation.
Here the indices in positions one and three are exchanged, that is,
If no indices are specified, the first and last index are exchanged.
This is consistent with the matrix transpose.
If a more complicated reordering of the indices is required, then the reindexreindexCartesianTensor operation can be used. This operation allows the indices to be arbitrarily permuted.
This defines
Tensors of equal rank can be added or subtracted so arithmetic expressions can be used to produce new tensors.
Two specific tensors have properties which depend only on the dimension.
The Kronecker delta satisfies
This can be used to reindex via contraction.
The Levi Civita symbol determines the sign of a permutation of indices.
Here we have:
This property can be used to form determinants.
GradedModule(R,E) denotes ``E-graded R-module'', that is, a collection of R-modules indexed by an abelian monoid E. An element g of G[s] for some specific s in E is said to be an element of G with degreedegreeGradedModule s. Sums are defined in each module G[s] so two elements of G can be added if they have the same degree. Morphisms can be defined and composed by degree to give the mathematical category of graded modules.
GradedAlgebra(R,E) denotes ``E-graded R-algebra.'' A graded algebra is a graded module together with a degree preserving R-bilinear map, called the productproductGradedAlgebra.
The domain CartesianTensor(i0, dim, R) belongs to the category GradedAlgebra(R, NonNegativeInteger). The non-negative integer degreedegreeGradedAlgebra is the tensor rank and the graded algebra productproductGradedAlgebra is the tensor outer product. The graded module addition captures the notion that only tensors of equal rank can be added.
If V is a vector space of dimension dim over R, then the tensor module T[k](V) is defined as
where * denotes the R-module tensor productproductGradedAlgebra. CartesianTensor(i0,dim,R) is the graded algebra in which the degree k module is T[k](V).
It should be noted here that often tensors are used in the context of tensor-valued manifold maps. This leads to the notion of covariant and contravariant bases with tensor component functions transforming in specific ways under a change of coordinates on the manifold. This is no more directly supported by the CartesianTensor domain than it is by the Vector domain. However, it is possible to have the components implicitly represent component maps by choosing a polynomial or expression type for the components. In this case, it is up to the user to satisfy any constraints which arise on the basis of this interpretation.
The members of the domain Character are values representing letters, numerals and other text elements. For more information on related topics, see CharacterClassXmpPage and StringXmpPage .
Characters can be obtained using String notation.
Certain characters are available by name. This is the blank character.
This is the quote that is used in strings.
This is the escape character that allows quotes and other characters within strings.
Characters are represented as integers in a machine-dependent way. The integer value can be obtained using the ordordCharacter operation. It is always true that char(ord c) = c and ord(char i) = i, provided that i is in the range 0..size()$Character-1.
The lowerCaselowerCaseCharacter operation converts an upper case letter to the corresponding lower case letter. If the argument is not an upper case letter, then it is returned unchanged.
Likewise, the upperCaseupperCaseCharacter operation converts lower case letters to upper case.
A number of tests are available to determine whether characters belong to certain families.
The CharacterClass domain allows classes of characters to be defined and manipulated efficiently. Character classes can be created by giving either a string or a list of characters.
A number of character classes are predefined for convenience.
You can quickly test whether a character belongs to a class.
Classes have the usual set operations because the CharacterClass domain belongs to the category FiniteSetAggregate(Character).
You can modify character classes by adding or removing characters.
For more information on related topics, see CharacterXmpPage and StringXmpPage .
CliffordAlgebra(n,K,Q) defines a vector space of dimension over the field with a given quadratic form Q. If is a basis for then
is a basis for the Clifford algebra. The algebra is defined by the relations
Examples of Clifford Algebras are gaussians (complex numbers), quaternions, exterior algebras and spin algebras.
This is the field over which we will work, rational functions with integer coefficients.
We use this matrix for the quadratic form.
We get complex arithmetic by using this domain.
Here is i, the usual square root of -1.
Here are some examples of the arithmetic.
See ComplexXmpPage for examples of Axiom's constructor implementing complex numbers.
This is the field over which we will work, rational functions with integer coefficients.
We use this matrix for the quadratic form.
The resulting domain is the quaternions.
We use Hamilton's notation for i,j,k.
See QuaternionXmpPage for examples of Axiom's constructor implementing quaternions.
This is the field over which we will work, rational functions with integer coefficients.
If we chose the three by three zero quadratic form, we obtain the exterior algebra on e(1),e(2),e(3).
This is a three dimensional vector algebra. We define i, j, k as the unit vectors.
Now it is possible to do arithmetic.
On an n space, a grade p form has a dual n-p form. In particular, in three space the dual of a grade two element identifies e1*e2->e3, e2*e3->e1, e3*e1->e2.
The vector cross product is then given by this.
In this section we will work over the field of rational numbers.
We define the quadratic form to be the Minkowski space-time metric.
We obtain the Dirac spin algebra used in Relativistic Quantum Field Theory.
The usual notation for the basis is with a superscript. For Axiom input we will use gam(i):
There are various contraction identities of the form
where a sum over l and t is implied.
Verify this identity for particular values of m,n,r,s.
The Complex constructor implements complex objects over a commutative ring R. Typically, the ring R is Integer, Fraction Integer, Float or DoubleFloat. R can also be a symbolic type, like Polynomial Integer. For more information about the numerical and graphical aspects of complex numbers, see ugProblemNumeric .
Complex objects are created by the complexcomplexComplex operation.
The standard arithmetic operations are available.
If R is a field, you can also divide the complex objects.
Use a conversion (ugTypesConvertPage in Section ugTypesConvertNumber ) to view the last object as a fraction of complex integers.
The predefined macro %i is defined to be complex(0,1).
You can also compute the conjugateconjugateComplex and normnormComplex of a complex number.
The realrealComplex and imagimagComplex operations are provided to extract the real and imaginary parts, respectively.
The domain Complex Integer is also called the Gaussian integers. If R is the integers (or, more generally, a EuclideanDomain), you can compute greatest common divisors.
You can also compute least common multiples.
You can factorfactorComplex Gaussian integers.
Continued fractions have been a fascinating and useful tool in mathematics for well over three hundred years. Axiom implements continued fractions for fractions of any Euclidean domain. In practice, this usually means rational numbers. In this section we demonstrate some of the operations available for manipulating both finite and infinite continued fractions. It may be helpful if you review StreamXmpPage to remind yourself of some of the operations with streams.
The ContinuedFraction domain is a field and therefore you can add, subtract, multiply and divide the fractions.
The continuedFractioncontinuedFractionContinuedFraction operation converts its fractional argument to a continued fraction.
This display is a compact form of the bulkier
You can write any rational number in a similar form. The fraction will be finite and you can always take the ``numerators'' to be 1. That is, any rational number can be written as a simple, finite continued fraction of the form
The are called partial quotients and the operation partialQuotientspartialQuotientsContinuedFraction creates a stream of them.
By considering more and more of the fraction, you get the convergentsconvergentsContinuedFraction. For example, the first convergent is , the second is and so on.
Since this is a finite continued fraction, the last convergent is the original rational number, in reduced form. The result of approximantsapproximantsContinuedFraction is always an infinite stream, though it may just repeat the ``last'' value.
Inverting c only changes the partial quotients of its fraction by inserting a 0 at the beginning of the list.
Do this to recover the original continued fraction from this list of partial quotients. The three-argument form of the continuedFractioncontinuedFractionContinuedFraction operation takes an element which is the whole part of the fraction, a stream of elements which are the numerators of the fraction, and a stream of elements which are the denominators of the fraction.
The streams need not be finite for continuedFractioncontinuedFractionContinuedFraction. Can you guess which irrational number has the following continued fraction? See the end of this section for the answer.
In 1737 Euler discovered the infinite continued fraction expansion
We use this expansion to compute rational and floating point approximations of e. For this and other interesting expansions, see C. D. Olds, Continued Fractions, New Mathematical Library, (New York: Random House, 1963), pp. 134--139.
By looking at the above expansion, we see that the whole part is 0 and the numerators are all equal to 1. This constructs the stream of denominators.
Therefore this is the continued fraction expansion for .
These are the rational number convergents.
You can get rational convergents for e by multiplying by 2 and adding 1.
You can also compute the floating point approximations to these convergents.
Compare this to the value of e computed by the expexpFloat operation in Float.
In about 1658, Lord Brouncker established the following expansion for ,
Let's use this expansion to compute rational and floating point approximations for .
As you can see, the values are converging to , but not very quickly.
You need not restrict yourself to continued fractions of integers. Here is an expansion for a quotient of Gaussian integers.
This is an expansion for a quotient of polynomials in one variable with rational number coefficients.
To conclude this section, we give you evidence that
is the expansion of .