0 Introduction to Axiom
0.1 Introduction to Axiom
Welcome to the world of Axiom. We call Axiom a scientific computation system: a self-contained toolbox designed to meet your scientific programming needs, from symbolics, to numerics, to graphics.
This introduction is a quick overview of what Axiom offers.
0.1.1 Symbolic Computation
Axiom provides a wide range of simple commands for symbolic mathematical problem solving. Do you need to solve an equation, to expand a series, or to obtain an integral? If so, just ask Axiom to do it.
Given we would enter this into Axiom as:
which would give the result:
Axiom provides state-of-the-art algebraic machinery to handle your most advanced symbolic problems. For example, Axiom's integrator gives you the answer when an answer exists. If one does not, it provides a proof that there is no answer. Integration is just one of a multitude of symbolic operations that Axiom provides.
0.1.2 Numeric Computation
Axiom has a numerical library that includes operations for linear algebra, solution of equations, and special functions. For many of these operations, you can select any number of floating point digits to be carried out in the computation.
Solve to 49 digits of accuracy. First we need to change the default output length of numbers:
and then we execute the command:
The output of a computation can be converted to FORTRAN to be used in a later numerical computation. Besides floating point numbers, Axiom provides literally dozens of kinds of numbers to compute with. These range from various kinds of integers, to fractions, complex numbers, quaternions, continued fractions, and to numbers represented with an arbitrary base.
What is to the -th power in base ?
returns:
FMM3O955CSEIV0ILKH820CN3I7PICQU0OQMDOFV6TP000000000000000000
The AXIOM numerical library can be enhanced with a substantial number of functions from the NAG library of numerical and statistical algorithms. These functions will provide coverage of a wide range of areas including roots of functions, Fourier transforms, quadrature, differential equations, data approximation, non-linear optimization, linear algebra, basic statistics, step-wise regression, analysis of variance, time series analysis, mathematical programming, and special functions. Contact the Numerical Algorithms Group Limited, Oxford, England.
0.1.3 Graphics
You may often want to visualize a symbolic formula or draw a graph from a set of numerical values. To do this, you can call upon the Axiom graphics capability.
Draw for .
Graphs in Axiom are interactive objects you can manipulate with your mouse. Just click on the graph, and a control panel pops up. Using this mouse and the control panel, you can translate, rotate, zoom, change the coloring, lighting, shading, and perspective on the picture. You can also generate a PostScript copy of your graph to produce hard-copy output.
0.1.4 HyperDoc
HyperDoc presents you windows on the world of Axiom, offering on-line help, examples, tutorials, a browser, and reference material. HyperDoc gives you on-line access to this document in a ``hypertext'' format. Words that appear in a different font (for example, Matrix, factor, and category) are generally mouse-active; if you click on one with your mouse, HyperDoc shows you a new window for that word.
As another example of a HyperDoc facility, suppose that you want to compute the roots of to 49 digits (as in our previous example) and you don't know how to tell Axiom to do this. The ``basic command'' facility of HyperDoc leads the way. Through the series of HyperDoc windows shown in Figure fig-intro-br and the specified mouse clicks, you and HyperDoc generate the correct command to issue to compute the answer.
0.1.5 Interactive Programming
Axiom's interactive programming language lets you define your own functions. A simple example of a user-defined function is one that computes the successive Legendre polynomials. Axiom lets you define these polynomials in a piece-wise way.
The first Legendre polynomial.
The second Legendre polynomial.
The -th Legendre polynomial for .
In addition to letting you define simple functions like this, the interactive language can be used to create entire application packages. All the graphs in the Axiom images section were created by programs written in the interactive language.
The above definitions for do no computation---they simply tell Axiom how to compute for some positive integer .
To actually get a value of a Legendre polynomial, you ask for it. Legendre polynomials
What is the tenth Legendre polynomial?
Compiling function p with type Integer -> Polynomial Fraction
Integer
Compiling function p as a recurrence relation.
Axiom applies the above pieces for to obtain the value of . But it does more: it creates an optimized, compiled function for . The function is formed by putting the pieces together into a single piece of code. By compiled, we mean that the function is translated into basic machine-code. By optimized, we mean that certain transformations are performed on that code to make it run faster. For , Axiom actually translates the original definition that is recursive (one that calls itself) to one that is iterative (one that consists of a simple loop).
What is the coefficient of in ?
In general, a user function is type-analyzed and compiled on first use. Later, if you use it with a different kind of object, the function is recompiled if necessary.
0.1.6 Data Structures
A variety of data structures are available for interactive use. These include strings, lists, vectors, sets, multisets, and hash tables. A particularly useful structure for interactive use is the infinite stream:
Create the infinite stream of derivatives of Legendre polynomials.
Streams display only a few of their initial elements. Otherwise, they are ``lazy'': they only compute elements when you ask for them.
Data structures are an important component for building application software. Advanced users can represent data for applications in optimal fashion. In all, Axiom offers over forty kinds of aggregate data structures, ranging from mutable structures (such as cyclic lists and flexible arrays) to storage efficient structures (such as bit vectors). As an example, streams are used as the internal data structure for power series.
What is the series expansion of about ?
Series and streams make no attempt to compute all their elements! Rather, they stand ready to deliver elements on demand.
What is the coefficient of the -th term of this series?
0.1.7 Mathematical Structures
Axiom also has many kinds of mathematical structures. These range from simple ones (like polynomials and matrices) to more esoteric ones (like ideals and Clifford algebras). Most structures allow the construction of arbitrarily complicated ``types.''
Even a simple input expression can result in a type with several levels.
The Axiom interpreter builds types in response to user input. Often, the type of the result is changed in order to be applicable to an operation.
The inverse operation requires that elements of the above matrices are fractions.
0.1.8 Pattern Matching
A convenient facility for symbolic computation is ``pattern matching.'' Suppose you have a trigonometric expression and you want to transform it to some equivalent form. Use a command to describe the transformation rules you rule need. Then give the rules a name and apply that name as a function to your trigonometric expression.
Introduce two rewrite rules.
{sin(y + x) == cos(x)sin(y) + cos(y)sin(x),
cos(y + x) == - sin(x)sin(y) + cos(x)cos(y),
sin(2x) == 2cos(x)sin(x),
2 2
cos(2x) == - sin(x) + cos(x) }
Apply the rules to a simple trigonometric expression.
Using input files, you can create your own library of transformation rules relevant to your applications, then selectively apply the rules you need.
0.1.9 Polymorphic Algorithms
All components of the Axiom algebra library are written in the Axiom library language. This language is similar to the interactive language except for protocols that authors are obliged to follow. The library language permits you to write ``polymorphic algorithms,'' algorithms defined to work in their most natural settings and over a variety of types.
Define a system of polynomial equations .
Solve the system using rational number arithmetic and 30 digits of accuracy.
Solve with the solutions expressed in radicals.
While these solutions look very different, the results were produced by the same internal algorithm! The internal algorithm actually works with equations over any ``field.'' Examples of fields are the rational numbers, floating point numbers, rational functions, power series, and general expressions involving radicals.
0.1.10 Extensibility
Users and system developers alike can augment the Axiom library, all using one common language. Library code, like interpreter code, is compiled into machine binary code for run-time efficiency.
Using this language, you can create new computational types and new algorithmic packages. All library code is polymorphic, described in terms of a database of algebraic properties. By following the language protocols, there is an automatic, guaranteed interaction between your code and that of colleagues and system implementers.
0.2 A Technical Introduction
Axiom has both an interactive language for user interactions and a programming language for building library modules. Like Modula 2, Modula 2 PASCAL, PASCAL FORTRAN, FORTRAN and Ada, Ada the programming language emphasizes strict type-checking. Unlike these languages, types in Axiom are dynamic objects: they are created at run-time in response to user commands.
Here is the idea of the Axiom programming language in a nutshell. Axiom types range from algebraic ones (like polynomials, matrices, and power series) to data structures (like lists, dictionaries, and input files). Types combine in any meaningful way. You can build polynomials of matrices, matrices of polynomials of power series, hash tables with symbolic keys and rational function entries, and so on.
Categories define algebraic properties to ensure mathematical correctness. They ensure, for example, that matrices of polynomials are OK, but matrices of input files are not. Through categories, programs can discover that polynomials of continued fractions have a commutative multiplication whereas polynomials of matrices do not.
Categories allow algorithms to be defined in their most natural setting. For example, an algorithm can be defined to solve polynomial equations over any field. Likewise a greatest common divisor can compute the ``gcd'' of two elements from any Euclidean domain. Categories foil attempts to compute meaningless ``gcds'', for example, of two hashtables. Categories also enable algorithms to be compiled into machine code that can be run with arbitrary types.
The Axiom interactive language is oriented towards ease-of-use. The Axiom interpreter uses type-inferencing to deduce the type of an object from user input. Type declarations can generally be omitted for common types in the interactive language.
So much for the nutshell. Here are these basic ideas described by ten design principles:
0.2.1 Types are Defined by Abstract Datatype Programs
Basic types are called domains of computation, or, simply, domains. domain Domains are defined by Axiom programs of the form:
Name(...): Exports == Implementation
Each domain has a capitalized Name that is used to refer to the class of its members. For example, Integer denotes ``the class of integers,'' Float, ``the class of floating point numbers,'' and String, ``the class of strings.''
The ``...'' part following Name lists zero or more parameters to the constructor. Some basic ones like Integer take no parameters. Others, like Matrix, Polynomial and List, take a single parameter that again must be a domain. For example, Matrix(Integer) denotes ``matrices over the integers,'' Polynomial (Float) denotes ``polynomial with floating point coefficients,'' and List (Matrix (Polynomial (Integer))) denotes ``lists of matrices of polynomials over the integers.'' There is no restriction on the number or type of parameters of a domain constructor.
SquareMatrix(2,Integer) is an example of a domain constructor that accepts both a particular data value as well as an integer. In this case the number 2 specifies the number of rows and columns the square matrix will contain. Elements of the matricies are integers.
The Exports part specifies operations for creating and manipulating objects of the domain. For example, type Integer exports constants and , and operations +, -, and *. While these operations are common, others such as odd?odd?Integer and bit?bit?Integer are not. In addition the Exports section can contain symbols that represent properties that can be tested. For example, the Category EntireRing has the symbol noZeroDivisors which asserts that if a product is zero then one of the factors must be zero.
The Implementation part defines functions that implement the exported operations of the domain. These functions are frequently described in terms of another lower-level domain used to represent the objects of the domain. Thus the operation of adding two vectors of real numbers can be described and implemented using the addition operation from Float.
0.2.2 The Type of Basic Objects is a Domain or Subdomain
Every Axiom object belongs to a unique domain. The domain of an object is also called its type. Thus the integer has type Integer and the string "daniel" has type String.
The type of an object, however, is not unique. The type of integer is not only Integer but NonNegativeInteger, PositiveInteger, and possibly, in general, any other ``subdomain'' of the domain Integer. A subdomain subdomain is a domain with a ``membership predicate''. PositiveInteger is a subdomain of Integer with the predicate ``is the integer ?''.
Subdomains with names are defined by abstract datatype programs similar to those for domains. The Export part of a subdomain, however, must list a subset of the exports of the domain. The Implementation part optionally gives special definitions for subdomain objects.
0.2.3 Domains Have Types Called Categories
Domain and subdomains in Axiom are themselves objects that have types. The type of a domain or subdomain is called a category. category Categories are described by programs of the form:
Name(...): Category == Exports
The type of every category is the distinguished symbol Category. The category Name is used to designate the class of domains of that type. For example, category Ring designates the class of all rings. Like domains, categories can take zero or more parameters as indicated by the ``...'' part following Name. Two examples are Module(R) and MatrixCategory(R,Row,Col).
The Exports part defines a set of operations. For example, Ring exports the operations 0, 1, +, -, and *. Many algebraic domains such as Integer and Polynomial (Float) are rings. String and List (R) (for any domain ) are not.
Categories serve to ensure the type-correctness. The definition of matrices states Matrix(R: Ring) requiring its single parameter to be a ring. Thus a ``matrix of polynomials'' is allowed, but ``matrix of lists'' is not.
Categories say nothing about representation. Domains, which are instances of category types, specify representations.
0.2.4 Operations Can Refer To Abstract Types
All operations have prescribed source and target types. Types can be denoted by symbols that stand for domains, called ``symbolic domains.'' The following lines of Axiom code use a symbolic domain :
R: Ring
power: (R, NonNegativeInteger): R -> R
power(x, n) == x ** n
Line 1 declares the symbol to be a ring. Line 2 declares the type of in terms of . From the definition on line 3, produces 9 for and Integer. Also, produces for and Float. however fails since has type String which is not a ring.
Using symbolic domains, algorithms can be defined in their most natural or general setting.
0.2.5 Categories Form Hierarchies
Categories form hierarchies (technically, directed-acyclic graphs). A simplified hierarchical world of algebraic categories is shown below. At the top of this world is SetCategory, the class of algebraic sets. The notions of parents, ancestors, and descendants is clear. Thus ordered sets (domains of category OrderedSet) and rings are also algebraic sets. Likewise, fields and integral domains are rings and algebraic sets. However fields and integral domains are not ordered sets.
SetCategory +---- Ring ---- IntegralDomain ---- Field
|
+---- Finite ---+
| \
+---- OrderedSet -----+ OrderedFinite
Figure 1. A simplified category hierarchy.
0.2.6 Domains Belong to Categories by Assertion
A category designates a class of domains. Which domains? You might think that Ring designates the class of all domains that export , , +, -, and *. But this is not so. Each domain must assert which categories it belongs to.
The Export part of the definition for Integer reads, for example:
Join(OrderedSet, IntegralDomain, ...) with ...
This definition asserts that Integer is both an ordered set and an integral domain. In fact, Integer does not explicitly export constants and and operations +, - and * at all: it inherits them all from ! Since IntegralDomain is a descendant of , Integer is therefore also a ring.
Assertions can be conditional. For example, Complex(R) defines its exports by:
Ring with ... if R has Field then Field ...
Thus Complex(Float) is a field but Complex(Integer) is not since Integer is not a field.
You may wonder: ``Why not simply let the set of operations determine whether a domain belongs to a given category?''. Axiom allows operation names (for example, norm) to have very different meanings in different contexts. The meaning of an operation in Axiom is determined by context. By associating operations with categories, operation names can be reused whenever appropriate or convenient to do so. As a simple example, the operation < might be used to denote lexicographic-comparison in an algorithm. However, it is wrong to use the same < with this definition of absolute-value: Such a definition for abs in Axiom is protected by context: argument is required to be a member of a domain of category OrderedSet.
0.2.7 Packages Are Clusters of Polymorphic Operations
In Axiom, facilities for symbolic integration, solution of equations, and the like are placed in ``packages''. A package package is a special kind of domain: one whose exported operations depend solely on the parameters of the constructor and/or explicit domains. Packages, unlike Domains, do not specify the representation.
If you want to use Axiom, for example, to define some algorithms for solving equations of polynomials over an arbitrary field , you can do so with a package of the form:
MySolve(F: Field): Exports == Implementation
where Exports specifies the solve operations you wish to export from the domain and the Implementation defines functions for implementing your algorithms. Once Axiom has compiled your package, your algorithms can then be used for any F: floating-point numbers, rational numbers, complex rational functions, and power series, to name a few.
0.2.8 The Interpreter Builds Domains Dynamically
The Axiom interpreter reads user input then builds whatever types it needs to perform the indicated computations. For example, to create the matrix using the command:
the interpreter first loads the modules Matrix, Polynomial, Fraction, and Integer from the library, then builds the domain tower ``matrices of polynomials of rational numbers (i.e. fractions of integers)''.
You can watch the loading process by first typing
In addition to the named domains above many additional domains and categories are loaded. Most systems are preloaded with such common types. For efficiency reasons the most common domains are preloaded but most (there are more than 1100 domains, categories, and packages) are not. Once these domains are loaded they are immediately available to the interpreter.
Once a domain tower is built, it contains all the operations specific to the type. Computation proceeds by calling operations that exist in the tower. For example, suppose that the user asks to square the above matrix. To do this, the function * from Matrix is passed the matrix to compute . The function is also passed an environment containing that, in this case, is Polynomial (Fraction (Integer)). This results in the successive calling of the * operations from Polynomial, then from Fraction, and then finally from Integer.
Categories play a policing role in the building of domains. Because the argument of Matrix is required to be a Ring, Axiom will not build nonsensical types such as ``matrices of input files''.
0.2.9 Axiom Code is Compiled
Axiom programs are statically compiled to machine code, then placed into library modules. Categories provide an important role in obtaining efficient object code by enabling:
- static type-checking at compile time;
- fast linkage to operations in domain-valued parameters;
- optimization techniques to be used for partially specified types (operations for ``vectors of '', for instance, can be open-coded even though R is unknown).
0.2.10 Axiom is Extensible
Users and system implementers alike use the Axiom language to add facilities to the Axiom library. The entire Axiom library is in fact written in the Axiom source code and available for user modification and/or extension.
Axiom's use of abstract datatypes clearly separates the exports of a domain (what operations are defined) from its implementation (how the objects are represented and operations are defined). Users of a domain can thus only create and manipulate objects through these exported operations. This allows implementers to ``remove and replace'' parts of the library safely by newly upgraded (and, we hope, correct) implementations without consequence to its users.
Categories protect names by context, making the same names available for use in other contexts. Categories also provide for code-economy. Algorithms can be parameterized categorically to characterize their correct and most general context. Once compiled, the same machine code is applicable in all such contexts.
Finally, Axiom provides an automatic, guaranteed interaction between new and old code. For example:
- if you write a new algorithm that requires a parameter to be a field, then your algorithm will work automatically with every field defined in the system; past, present, or future.
- if you introduce a new domain constructor that produces a field, then the objects of that domain can be used as parameters to any algorithm using field objects defined in the system; past, present, or future.
These are the key ideas. For further information, we particularly recommend your reading chapters 11, 12, and 13, where these ideas are explained in greater detail.
0.3 Using Axiom as a Pocket Calculator
At the simplest level Axiom can be used as a pocket calculator where expressions involving numbers and operators are entered directly in infix notation. In this sense the more advanced features of the calculator can be regarded as operators (e.g sin, cos, etc).
0.3.1 Basic Arithmetic
An example of this might be to calculate the cosine of 2.45 (in radians). To do this one would type:
Before proceeding any further it would be best to explain the previous three lines. Firstly the text ``(1) -> '' is part of the prompt that the Axiom system provides when in interactive mode. The full prompt has other text preceding this but it is not relevant here. The number in parenthesis is the step number of the input which may be used to refer to the results of previous calculations. The step number appears at the start of the second line to tell you which step the result belongs to. Since the interpreter probably loaded numberous libraries to calculate the result given above and listed each one in the prcess, there could easily be several pages of text between your input and the answer.
The last line contains the type of the result. The type Float is used to represent real numbers of arbitrary size and precision (where the user is able to define how big arbitrary is -- the default is 20 digits but can be as large as your computer system can handle). The type of the result can help track down mistakes in your input if you don't get the answer you expected.
Other arithmetic operations such as addition, subtraction, and multiplication behave as expected:
but integer division isn't quite so obvious. For example, if one types:
a fractional result is obtained. The function used to display fractions attempts to produce the most readable answer. In the example:
the result is stored as the fraction 2/1 but is displayed as the integer 2. This fraction could be converted to type Integer with no loss of informatin but Axiom will not do so automatically.
0.3.2 Type Conversion
To obtain the floating point value of a fraction one must convert ( conversions are applied by the user and coercions are applied automatically by the interpreter) the result to type Float using the ``::'' operator as follows:
Although Axiom can convert this back to a fraction it might not be the same fraction you started with as due to rounding errors. For example, the following conversion appears to be without error but others might not:
where ``%'' represents the previous result (not the calculation).
Although Axiom has the ability to work with floating-point numbers to a very high precision it must be remembered that calculations with these numbers are not exact. Since Axiom is a computer algebra package and not a numerical solutions package this should not create too many problems. The idea is that the user should use Axiom to do all the necessary symbolic manipulation and only at the end should actual numerical results be extracted.
If you bear in mind that Axiom appears to store expressions just as you have typed them and does not perform any evalutation of them unless forced to then programming in the system will be much easier. It means that anything you ask Axiom to do (within reason) will be carried with complete accuracy.
In the previous examples the ``::'' operator was used to convert values from one type to another. This type conversion is not possible for all values. For instance, it is not possible to convert the number 3.4 to an integer type since it can't be represented as an integer. The number 4.0 can be converted to an integer type since it has no fractional part.
Conversion from floating point values to integers is performed using the functions round and truncate. The first of these rounds a floating point number to the nearest integer while the other truncates (i.e. removes the fractional part). Both functions return the result as a floating point number. To extract the fractional part of a floating point number use the function fractionPart but note that the sign of the result depends on the sign of the argument. Axiom obtains the fractional partof using :
0.3.3 Useful Functions
To obtain the absolute value of a number the abs function can be used. This takes a single argument which is usually an integer or a floating point value but doesn't necessarily have to be. The sign of a value can be obtained via the sign function which rturns , , or depending on the sign of the argument.
Tests on values can be done using various functions which are generally more efficient than using relational operators such as particularly if the value is a matrix. Examples of some of these functions are:
Some other functions that are quite useful for manipulating numerical values are:
sin(x) Sine of x
cos(x) Cosine of x
tan(x) Tangent of x
asin(x) Arcsin of x
acos(x) Arccos of x
atan(x) Arctangent of x
gcd(x,y) Greatest common divisor of x and y
lcm(x,y) Lowest common multiple of x and y
max(x,y) Maximum of x and y
min(x,y) Minimum of x and y
factorial(x) Factorial of x
factor(x) Prime factors of x
divide(x,y) Quotient and remainder of x/y
Some simple infix and prefix operators:
+ Addition - Subtraction
- Numerical Negation ~ Logical Negation
/ Conjunction (AND) \/ Disjunction (OR)
and Logical AND (/\) or Logical OR (\/)
not Logical Negation ** Exponentiation
* Multiplication / Division
quo Quotient rem Remainder
< less than > greater than
<= less than or equal >= greater than or equal
Some useful Axiom macros:
%i The square root of -1
%e The base of the natural logarithm
%pi Pi
%infinity Infinity
%plusInfinity Positive Infinity
%minusInfinity Negative Infinity
0.4 Using Axiom as a Symbolic Calculator
In the previous section all the examples involved numbers and simple functions. Also none of the expressions entered were assigned to anything. In this section we will move on to simple algebra (i.e. expressions involving symbols and other features available on more sophisticated calculators).
0.4.1 Expressions Involving Symbols
Expressions involving symbols are entered just as they are written down, for example:
where the assignment operator ``:='' represents immediate assignment. Later it will be seen that this form of assignment is not always desirable and the use of the delayed assignment operator ``=='' will be introduced. The type of the result is Polynomial Integer which is used to represent polynomials with integer coefficients. Some other examples along similar lines are:
Given that we can define expressions involving symbols, how do we actually compute the result when the symbols are assigned values? The answer is to use the eval function which takes an expression as its first argument followed by a list of assignments. For example, to evaluate the expressions XDummy and {xyDummy} resulting from their respective assignments above we type:
0.4.2 Complex Numbers
For many scientific calculations real numbers aren't sufficient and support for complex numbers is also required. Complex numbers are handled in an intuitive manner and Axiom, which uses the %i macro to represent the square root of . Thus expressions involving complex numbers are entered just like other expressions.
The real and imaginary parts of a complex number can be extracted using the real and imag functions and the complex conjugate of a number can be obtained using conjugate:
The function factor can also be applied to complex numbers but the results aren't quite so obvious as for factoring integer:
0.4.3 Number Representations
By default all numerical results are displayed in decimal with real numbers shown to 20 significant figures. If the integer part of a number is longer than 20 digits then nothing after the decimal point is shown and the integer part is given in full. To alter the number of digits shown the function digits can be called. The result returned by this function is the previous setting. For example, to find the value of to 40 digits we type:
As can be seen in the example above, there is a gap after every ten digits. This can be changed using the outputSpacing function where the argument is the number of digits to be displayed before a space is inserted. If no spaces are desired then use the value . Two other functions controlling the appearance of real numbers are outputFloating and outputFixed. The former causes Axiom to display floating-point values in exponent notation and the latter causes it to use fixed-point notation. For example:
Note that the semicolon ``;'' in the examples above allows several expressions to be entered on one line. The result of the last expression is displayed. remember also that the percent symbol ``%'' is used to represent the result of a previous calculation.
To display rational numbers in a base other than 10 the function radix is used. The first argument of this function is the expression to be displayed and the second is the base to be used.
Rational numbers can be represented as a repeated decimal expansion using the decimal function or as a continued fraction using continuedFraction. Any attempt to call these functions with irrational values will fail.
Finally, partial fractions in compact and expanded form are available via the functions partialFraction and padicFraction respectively. The former takes two arguments, the first being the numerator of the fraction and the second being the denominator. The latter function takes a fraction and expands it further while the function compactFraction does the reverse:
To extract parts of a partial fraction the function nthFractionalTerm is available and returns a partial fraction of one term. To decompose this further the numerator can be obtained using firstNumer and the denominator with firstDenom. The whole part of a partial fraction can be retrieved using wholePart and the number of fractional parts can be found using the function numberOf FractionalTerms:
0.4.4 Modular Arithmetic
By using the type constructor PrimeField it is possible to do arithmetic modulo some prime number. For example, arithmetic module can be performed as follows:
The first example should be read as:
Let be of type PrimeField(7) and assign to it the value
Note that it is only possible to invert non-zero values if the arithmetic is performed modulo a prime number. Thus arithmetic modulo a non-prime integer is possible but the reciprocal operation is undefined and will generate an error. Attempting to use the PrimeField type constructor with a non-prime argument will generate an error. An example of non-prime modulo arithmetic is:
Note that polynomials can be constructed in a similar way:
0.5 General Points about Axiom
0.5.1 Computation Without Output
It is sometimes desirable to enter an expression and prevent Axiom from displaying the result. To do this the expression should be terminated with a semicolon ``;''. In a previous section it was mentioned that a set of expressions separated by semicolons would be evaluated and the result of the last one displayed. Thus if a single expression is followed by a semicolon no output will be produced (except for its type):
0.5.2 Accessing Earlier Results
The ``%'' macro represents the result of the previous computation. The ``%%'' macro is available which takes a single integer argument. If the argument is positive then it refers to the step number of the calculation where the numbering begins from one and can be seen at the end of each prompt (the number in parentheses). If the argument is negative then it refers to previous results counting backwards from the last result. That is, ``%%(-1)'' is the same as ``%''. The value of ``%%(0)'' is not defined and will generate an error if requested.
0.5.3 Splitting Expressions Over Several Lines
Although Axiom will quite happily accept expressions that are longer than the width of the screen (just keep typing without pressing the Return key) it is often preferable to split the expression being entered at a point where it would result in more readable input. To do this the underscore ``_'' symbol is placed before the break point and then the Return key is pressed. The rest of the expression is typed on the next line, can be preceeded by any number of whitespace chars, for example:
2_
+_
3
The underscore symbol is an escape character and its presence alters the meaning of the characters that follow it. As mentions above whitespace following an underscore is ignored (the Return key generates a whitespace character). Any other character following an underscore loses whatever special meaning it may have had. Thus one can create the identifier ``a+b'' by typing ``a_+b'' although this might lead to confusions. Also note the result of the following example:
0.5.4 Comments and Descriptions
Comments and descriptions are really only of use in files of Axiom code but can be used when the output of an interactive session is being spooled to a file (via the system command )spool). A comment begins with two dashes ``- -'' and continues until the end of the line. Multi-line comments are only possible if each individual line begins with two dashes.
Descriptions are the same as comments except that the Axiom compiler will include them in the object files produced and make them availabe to the end user for documentation purposes.
A description is placed before a calculation begins with three ``+++'' signs and a description placed after a calculation begins with two plus symbols ``+''. The so-called ``plus plus'' comments are used within the algebra files and are processed by the compiler to add to the documentation. The so-called ``minus minus'' comments are ignored everywhere.
0.5.5 Control of Result Types
In earlier sections the type of an expression was converted to another via the ``::'' operator. However, this is not the only method for converting between types and two other operators need to be introduced and explained.
The first operator is ``$'' and is used to specify the package to be used to calculate the result. Thus:
tells Axiom to use the ``/'' operator from the Float package to evaluate the expression . This does not necessarily mean that the result will be of the same type as the domain from which the operator was taken. In the following example the sign operator is taken from the Float package but the result is of type Integer.
The other operator is ``@'' which is used to tell Axiom what the desired type of the result of the calculation is. In most situations all three operators yield the same results but the example below should help distinguish them.
An expression involving @ String actually evaluated to one of
type PositiveInteger . Perhaps you should use :: String .
The function + is not implemented in String .
If an expression X is converted using one of the three operators to type T the interpretations are:
:: means explicitly convert X to type T if possible.
$ means use the available operators for type T to compute X.
@ means choose operators to compute X so that the result is of type T.
0.6 Data Structures in Axiom
This chapter is an overview of some of the data structures provided by Axiom.
0.6.1 Lists
The Axiom List type constructor is used to create homogenous lists of finite size. The notation for lists and the names of the functions that operate over them are similar to those found in functional languages such as ML.
Lists can be created by placing a comma separated list of values inside square brackets or if a list with just one element is desired then the function list is available:
The function append takes two lists as arguments and returns the list consisting of the second argument appended to the first. A single element can be added to the front of a list using cons:
Lists are accessed sequentially so if Axiom is asked for the value of the twentieth element in the list it will move from the start of the list over nineteen elements before it reaches the desired element. Each element of a list is stored as a node consisting of the value of the element and a pointer to the rest of the list. As a result the two main operations on a list are called first and rest. Both of these functions take a second optional argument which specifies the length of the first part of the list:
Other functions are empty? which tests to see if a list contains no elements, member? which tests to see if the first argument is a member of the second, reverse which reverses the order of the list, sort which sorts a list, and removeDuplicates which removes any duplicates. The length of a list can be obtained using the `` #'' operator.
Lists in Axiom are mutable and so their contents (the elements and the links) can be modified in place. Functions that operator over lists in this way have names ending in the symbol ``!''. For example, concat! takes two lists as arguments and appends the second argument to the first (except when the first argument is an empty list) and setrest! changes the link emanating from the first argument to point to the second argument:
From this it can be seen that the lists returned by first and rest are pointers to the original list and not a copy. Thus great care must be taken when dealing with lists in Axiom.
Although the nth element of the list l can be obtained by applying the first function to applications of rest to l, Axiom provides a more useful access method in the form of the ``.'' operator:
The operation u.i is referred to as indexing into u or elting into u. The latter term comes from the elt function which is used to extract elements (the first element of the list is at index ).
If a list has no cycles then any attempt to access an element beyond the end of the list will generate an error. However, in the example above there was a cycle starting at the third element so the access to the sixth element wrapped around to give the third element. Since lists are mutable it is possible to modify elements directly:
Other list operations are:
Note that using the `` #'' operator on a list with cycles causes Axiom to enter an infinite loop.
Note that any operation on a list L that returns a list will, in general, be such that any changes to will have the side-effect of altering L. For example:
Thus the only save way of copying lists is to copy each element from one to another and not use the assignment operator:
In the previous example a new way of constructing lists was given. This is a powerful method which gives the reader more information about the contents of the list than before and which is extremely flexible. The example
should be read as
``Using the expression i, generate each element of the list by iterating the symbol i over the range of integers [1,10]''
To generate the list of the squares of the first ten elements we just use:
For more complex lists we can apply a condition to the elements that are to be placed into the list to obtain a list of even numbers between 0 and 11:
This example should be read as:
``Using the expression i, generate each element of the list by iterating the symbol i over the range of integers [1,10] such that i is even''
The following achieves the same result:
0.6.2 Segmented Lists
A segmented list is one in which some of the elements are ranges of values. The expand function converts lists of this type into ordinary lists:
If the upper bound of a segment is omitted then a different type of segmented list is obtained and expanding it will produce a stream (which will be considered in the next section):
0.6.3 Streams
Streams are infinite lists which have the ability to calculate the next element should it be required. For example, a stream of positive integers and a list of prime numbers can be generated by:
In each case the first few elements of the stream are calculated for display purposes but the rest of the stream remains unevaluated. The value of items in a stream are only calculated when they are needed which gives rise to their alternative name of ``lazy lists''.
Another method of creating streams is to use the generate(f,a) function. This applies its first argument repeatedly onto its second to produce the stream . Given that the function nextPrime returns the lowest prime number greater than its argument we can generate a stream of primes as follows:
As a longer example a stream of Fibonacci numbers will be computed. The Fibonacci numbers start at and each following number is the addition of the two numbers that precede it so the Fibonacci sequence is: .
Since the generation of any Fibonacci number only relies on knowing the previous two numbers we can look at the series through a window of two elements. To create the series the window is placed at the start over the values and their sum obtained. The window is now shifted to the right by one position and the sum placed into the empty slot of the window; the process is then repeated. To implement this we require a function that takes a list of two elements (the current view of the window), adds them, and outputs the new window. The result is the function :
Thus it can be seen that repeatedly applying win to the results of the previous invocation each element of the series is obtained. Clearly win is an ideal function to construct streams using the generate function:
This isn't quite what is wanted -- we need to extract the first element of each list and place that in our series:
Obtaining the 200th Fibonacci number is trivial:
One other function of interest is complete which expands a finite stream derived from an infinite one (and thus was still stored as an infinite stream) to form a finite stream.
0.6.4 Arrays, Vectors, Strings, and Bits
The simplest array data structure is the one-dimensional array which can be obtained by applying the oneDimensionalArray function to a list:
One-dimensional array are homogenous (all elements must have the same type) and mutable (elements can be changed) like lists but unlike lists they are constant in size and have uniform access times (it is just as quick to read the last element of a one-dimensional array as it is to read the first; this is not true for lists).
Since these arrays are mutable all the warnings that apply to lists apply to arrays. That is, it is possible to modify an element in a copy of an array and change the original:
Note that because these arrays are of fixed size the concat! function cannot be applied to them without generating an error. If arrays of this type are required use the FlexibleArray constructor.
One-dimensional arrays can be created using new which specifies the size of the array and the initial value for each of the elements. Other operations that can be applied to one-dimensional arrays are map! which applies a mapping onto each element, swap! which swaps two elements and copyInto!(a,b,c) which copies the array b onto a starting at position c.
(note that ARRAY1 is an abbreviation for the type OneDimensionalArray.) Other types based on one-dimensional arrays are Vector, String, and Bits.
A vector is similar to a one-dimensional array except that if its components belong to a ring then arithmetic operations are provided.
0.6.5 Flexible Arrays
Flexible arrays are designed to provide the efficiency of one-dimensional arrays while retaining the flexibility of lists. They are implemented by allocating a fixed block of storage for the array. If the array needs to be expanded then a larger block of storage is allocated and the contents of the old block are copied into the new one.
There are several operations that can be applied to this type, most of which modify the array in place. As a result these functions all have names ending in ``!''. The physicalLength returns the actual length of the array as stored in memory while the physicalLength! allows this value to be changed by the user.
There are several things to point out concerning these examples. First, although flexible arrays are mutable, making copies of these arrays creates separate entities. This can be seen by the fact that the modification of element b.2 above did not alter a. Second, the merge! function can take an extra argument before the two arrays are merged. The argument is a comparison function and defaults to ``<='' if omitted. Lastly, shrinkable tells the system whether or not to let flexible arrays contract when elements are deleted from them. An explicit package reference must be given as in the example above.
0.7 Functions, Choices, and Loops
By now the reader should be able to construct simple one-line expressions involving variables and different data structures. This section builds on this knowledge and shows how to use iteration, make choices, and build functions in Axiom. At the moment it is assumed that the reader has a rough idea of how types are specified and constructed so that they can follow the examples given.
From this point on most examples will be taken from input files.
0.7.1 Reading Code from a File
Input files contain code that will be fed to the command prompt. The primary different between the command line and an input file is that indentation matters. In an input file you can specify ``piles'' of code by using indentation.
The names of all input files in Axiom should end in ``.input'' otherwise Axiom will refuse to read them.
If an input file is named foo.input you can feed the contents of the file to the command prompt (as though you typed them) by writing: )read foo.input.
It is good practice to start each input file with the )clear all command so that all functions and variables in the current environment are erased.
0.7.2 Blocks
The Axiom constructs that provide looping, choices, and user-defined functions all rely on the notion of blocks. A block is a sequence of expressions which are evaluated in the order that they appear except when it is modified by control expressions such as loops. To leave a block prematurely use an expression of the form: BoolExpr=>Expr where BoolExpr is any Axiom expression that has type Boolean. The value and type of Expr determines the value and type returned by the block.
If blocks are entered at the keyboard (as opposed to reading them from a text file) then there is only one way of creating them. The syntax is:
In an input file a block can be constructed as above or by placing all the statements at the same indentation level. When indentation is used to indicate program structure the block is called a pile. As an example of a simple block a list of three integers can be constructed using parentheses:
Doing the same thing using piles in an input file you could type:
L :=
a:=4
b:=1
c:=9
[a,b,c]
Since blocks have a type and a value they can be used as arguments to functions or as part of other expressions. It should be pointed out that the following example is not recommended practice but helps to illustrate the idea of blocks and their ability to return values:
sqrt(4.0 +
a:=3.0
b:=1.0
c:=a + b
c
)
Note that indentation is extremely important. If the example above had the pile starting at ``a:='' moved left by two spaces so that the ``a'' was under the ``('' of the first line then the interpreter would signal an error. Furthermore if the closing parenthesis ``)'' is moved up to give
sqrt(4.0 +
a:=3.0
b:=1.0
c:=a + b
c)
Line 1: sqrt(4.0 +
....A
Error A: Missing mate.
Line 2: a:=3.0
Line 3: b:=1.0
Line 4: c:=a + b
Line 5: c)
.........AB
Error A: (from A up to B) Ignored.
Error B: Improper syntax.
Error B: syntax error at top level
Error B: Possibly missing a )
5 error(s) parsing
then the parser will generate errors. If the parenthesis is shifted right by several spaces so that it is in line with the ``c'' thus:
sqrt(4.0 +
a:=3.0
b:=1.0
c:=a + b
c
)
Line 1: sqrt(4.0 +
....A
Error A: Missing mate.
Line 2: a:=3.0
Line 3: b:=1.0
Line 4: c:=a + b
Line 5: c
Line 6: )
.........A
Error A: (from A up to A) Ignored.
Error A: Improper syntax.
Error A: syntax error at top level
Error A: Possibly missing a )
5 error(s) parsing
a similar error will be raised. Finally, the ``)'' must be indented by at least one space relative to the sqrt thus:
sqrt(4.0 +
a:=3.0
b:=1.0
c:=a + b
c
)
or an error will be generated.
It can be seen that great care needs to be taken when constructing input files consisting of piles of expressions. It would seem prudent to add one pile at a time and check if it is acceptable before adding more, particularly if piles are nested. However, it should be pointed out that the use of piles as values for functions is not very readable and so perhaps the delicate nature of their interpretation should deter programmers from using them in these situations. Using piles should really be restricted to constructing functions, etc. and a small amount of rewriting can remove the need to use them as arguments. For example, the previous block could easily be implemented as:
a:=3.0
b:=1.0
c:=a + b
sqrt(4.0 + c)
a:=3.0
b:=1.0
c:=a + b
sqrt(4.0 + c)
which achieves the same result and is easier to understand. Note that this is still a pile but it is not as fragile as the previous version.
0.7.3 Functions
Definitions of functions in Axiom are quite simple providing two things are observed. First, the type of the function must either be completely specified or completely unspecified. Second, the body of the function is assigned to the function identifier using the delayed assignment operator ``==''.
To specify the type of something the ``:'' operator is used. Thus to define a variable x to be of type Fraction Integer we enter:
For functions the method is the same except that the arguments are placed in parentheses and the return type is placed after the symbol ``->''. Some examples of function definitions taking zero, one, two, or three arguments and returning a list of integers are:
Now the actual function definitions might be:
with some invocations of these functions:
Compiling function f with type () -> List Integer
Compiling function g with type Integer -> List Integer
Compiling function h with type (Integer,Integer) -> List Integer
Compiling function k with type (Integer,Integer,Integer) -> List
Integer
The value returned by a function is either the value of the last expression evaluated or the result of a return statement. For example, the following are effectively the same:
Note that a block (pile) is assigned to the function identifier p and thus all the rules about blocks apply to function definitions. Also there was only one argument so the parenthese are not needed.
This is basically all that one needs to know about defining functions in Axiom -- first specify the complete type and then assign a block to the function name. The rest of this section is concerned with defining more complex blocks than those in this section and as a result function definitions will crop up continually particularly since they are a good way of testing examples. Since the block structure is more complex we will use the pile notation and thus have to use input files to read the piles.
0.7.4 Choices
Apart from the ``=>'' operator that allows a block to exit before the end Axiom provides the standard if-then-else construct. The general syntax is:
if BooleanExpr then Expr1 else Expr2
where ``else Expr2'' can be omitted. If the expression BooleanExpr evaluates to true then Expr1 is executed otherwise Expr2 (if present) will be executed. An example of piles and if-then-else is: (read from an input file)
h := 2.0
if h > 3.1 then
1.0
else
z:= cos(h)
max(x,0.5)
h := 2.0
if h > 3.1 then
1.0
else
z:= cos(h)
max(x,0.5)
Note the indentation -- the ``else'' must be indented relative to the ``if'' otherwise it will generate an error (Axiom will think there are two piles, the second one beginning with ``else'').
Any expression that has type Boolean can be used as BooleanExpr and the most common will be those involving the relational operators `` '', `` '', and ``=''. Usually the type of an expression involving the equality operator ``='' will be Boolean but in those situations when it isn't you may need to use the ``@'' operator to ensure that it is.
0.7.5 Loops
Loops in Axiom are regarded as expressions containing another expression called the loop body. The loop body is executed zero or more times depending on the kind of loop. Loops can be nested to any depth.
0.7.5.1 The repeat loop
The simplest kind of loop provided by Axiom is the repeat loop. The general syntax of this is:
This will cause Axiom to execute loopBody repeatedly until either a break or return statement is encountered. If loopBody contains neither of these statements then it will loop forever. The following piece of code will display the numbers from to :
i:=1
repeat
if i > 4 then break
output(i)
i:=i+1
i:=1
repeat
if i > 4 then break
output(i)
i:=i+1
1
2
3
4
It was mentioned that loops will only be left when either a break or return statement is encountered so why can't one use the ``=>'' operator? The reason is that the ``=>'' operator tells Axiom to leave the current block whereas break leaves the current loop. The return statement leave the current function.
To skip the rest of a loop body and continue the next iteration of the loop use the iterate statement (the -- starts a comment in Axiom)
i := 0
repeat
i := i + 1
if i > 6 then break
-- Return to start if i is odd
if odd?(i) then iterate
output(i)
i := 0
repeat
i := i + 1
if i > 6 then break
-- Return to start if i is odd
if odd?(i) then iterate
output(i)
2
4
6
0.7.5.2 The while loop
The while statement extends the basic repeat loop to place the control of leaving the loop at the start rather than have it buried in the middle. Since the body of the loop is still part of a repeat loop, break and ``=>'' work in the same way as in the previous section. The general syntax of a while loop is:
while BoolExpr repeat loopBody
As before, BoolExpr must be an expression of type Boolean. Before the body of the loop is executed BoolExpr is tested. If it evaluates to true then the loop body is entered otherwise the loop is terminated. Multiple conditions can be applied using the logical operators such as and or by using several while statements before the repeat.
x:=1
y:=1
while x < 4 and y < 10 repeat
output [x,y]
x := x + 1
y := y + 2
x:=1
y:=1
while x < 4 and y < 10 repeat
output [x,y]
x := x + 1
y := y + 2
[1,1]
[2,3]
[3,5]
x:=1
y:=1
while x < 4 while y < 10 repeat
output [x,y]
x := x + 1
y := y + 2
x:=1
y:=1
while x < 4 while y < 10 repeat
output [x,y]
x := x + 1
y := y + 2
[1,1]
[2,3]
[3,5]
Note that the last example using two while statements is not a nested loop but the following one is:
x:=1
y:=1
while x < 4 repeat
while y < 10 repeat
output [x,y]
x := x + 1
y := y + 2
x:=1
y:=1
while x < 4 repeat
while y < 10 repeat
output [x,y]
x := x + 1
y := y + 2
[1,1]
[2,3]
[3,5]
[4,7]
[5,9]
Suppose we that, given a matrix of arbitrary size, find the position and value of the first negative element by examining the matrix in row-major order:
m := matrix [ [ 21, 37, 53, 14 ],_
[ 8, 22,-24, 16 ],_
[ 2, 10, 15, 14 ],_
[ 26, 33, 55,-13 ] ]
lastrow := nrows(m)
lastcol := ncols(m)
r := 1
while r <= lastrow repeat
c := 1 -- Index of first column
while c <= lastcol repeat
if elt(m,r,c) < 0 then
output [r,c,elt(m,r,c)]
r := lastrow
break -- Don't look any further
c := c + 1
r := r + 1
m := matrix [ [ 21, 37, 53, 14 ],_
[ 8, 22,-24, 16 ],_
[ 2, 10, 15, 14 ],_
[ 26, 33, 55,-13 ] ]
lastrow := nrows(m)
lastcol := ncols(m)
r := 1
while r <= lastrow repeat
c := 1 -- Index of first column
while c <= lastcol repeat
if elt(m,r,c) < 0 then
output [r,c,elt(m,r,c)]
r := lastrow
break -- Don't look any further
c := c + 1
r := r + 1
[2,3,- 24]
0.7.5.3 The for loop
The last loop statement of interest is the for loop. There are two ways of creating a for loop. The first way uses either a list or a segment:
for var in seg repeat loopBody
for var in list repeat loopBody
where var is an index variable which is iterated over the values in seg or list. The value seg is a segment such as or and list is a list of some type. For example:
for i in 1..10 repeat
~prime?(i) => iterate
output(i)
2
3
5
7
for w in ["This", "is", "your", "life!"] repeat
output(w)
for w in ["This", "is", "your", "life!"] repeat
output(w)
This
is
your
life!
The second form of the for loop syntax includes a `` such that'' clause which must be of type Boolean:
for var in seg | BoolExpr repeat loopBody
for var in list | BoolExpr repeat loopBody
Some examples are:
for i in 1..10 | prime?(i) repeat
output(i)
2
3
5
7
for i in [1,2,3,4,5,6,7,8,9,10] | prime?(i) repeat
output(i)
2
3
5
7
You can also use a while clause:
for i in 1.. while i < 7 repeat
if even?(i) then output(i)
2
4
6
Using the `` such that'' clause makes this appear simpler:
for i in 1.. | even?(i) while i < 7 repeat
output(i)
2
4
6
You can use multiple for clauses to iterate over several sequences in parallel:
for a in 1..4 for b in 5..8 repeat
output [a,b]
[1,5]
[2,6]
[3,7]
[4,8]
As a general point it should be noted that any symbols referred to in the `` such that'' and while clauses must be pre-defined. This either means that the symbols must have been defined in an outer level (e.g. in an enclosing loop) or in a for clause appearing before the `` such that'' or while. For example:
for a in 1..4 repeat
for b in 7..9 | prime?(a+b) repeat
output [a,b,a+b]
[2,9,11]
[3,8,11]
[4,7,11]
[4,9,13]
Finally, the for statement has a by clause to specify the step size. This makes it possible to iterate over the segment in reverse order:
for a in 1..4 for b in 8..5 by -1 repeat
output [a,b]
[1,8]
[2,7]
[3,6]
[4,5]
Note that without the ``by -1'' the segment 8..5 is empty so there is nothing to iterate over and the loop exits immediately.