Axiom

This survey will look at Axiom, a free and very powerful computer algebra system available from http://wiki.axiom-developer.org. It is a general purpose CAS useful for symbolic computation, research, and the development of new mathematical algorithms. Axiom is a general purpose CAS, so is similar in some ways to Maxima, covered in the last OSCAS column. Axiom, Maxima, and SAGE S] (to be covered in a future column), are the largest of the general-purpose open-source CAS's. Axiom can be more difficult to compile than Maxima on certain platforms, but it is available via the web interface AS].

Axiom's latest release (as of March 2007) is 3.0 beta.

History

Axiom has an interesting history. Axiom began as Scratchpad II, which was developed at IBM in Yorktown Heights, New York back in the early 1980's under the direction of Richard Jenks. (Scratchpad II is not to be confused with Scratchpad, developed in the 1970's, also at IBM and also under the direction of Richard Jenks. The name was merely re-used to simplify IBM paperwork.) The team of developers then were Barry Trager, Robert Sutor, and Stephen Watt; Tim Daly joined the team in the late 1980's. In the 1990's, Scratchpad II was sold to the NAG (Numerical Algorithms Group) in England and renamed Axiom. In 2001, NAG withdrew Axiom from the market, agreeing in 2002 to release it as free and open source software, distributed under a modified BSD licenseNote1]. This is primarily thanks to the efforts of Tim Daly and Mike Dewar of NAG. Actually, about a year before NAG released Axiom to Tim Daly as open source, they "released" Aldor to a group aldor.org headed by Steven Watt (the original IBM SPAD and Aldor lead developer, now at the University of Western Ontario)Note2]. Early names for Aldor were A# (at IBM) and Axiom-XL (at NAG). NAG created the legal trade name "Aldor". More about Aldor below.

http://sage.math.washington.edu/home/wdj/sigsam/jenks.png Richard Jenks, http://sage.math.washington.edu/home/wdj/sigsam/daly.png Tim Daly.

Language

In addition to its command-line interpreter, in some sense, Axiom has two languages, both of which are strongly and statically typedNote3]. The first one, SPAD, is processed by the Axiom compiler (which translates it in to Lisp - GCL to be precise), and is free and open source. The second one is Aldor. Aldor is available from Al], where under "Coming soon" you will find: "Aldor open source release." As far as I know, at the time of this writing (March, 2007), the rights for at least some of the Aldor compiler source code are held by the NAG.

The original motivation for Aldor was to provide an improved extension language SPAD for the Axiom computer algebra system. The Aldor compiler can be used to generate code which runs within the Axiom system, separately, or linked into other applications. When used as the library compiler for Axiom, Aldor (like SPAD) will translate to GCL, which is then compiled to produce object code. When used as a stand alone compiler, Aldor generates C code directly (which is compiled by a C compiler).

Perhaps it is only a matter of semantics, but the Axiom website says that Axiom has one language -- SPAD is version 1 and Aldor is version 2. In any case, at this time, Aldor is only available as a binary executable, and not as source code (except "by request").

These languages are specifically designed for mathematics. In the words of Bill Page: "One key point that sets Axiom apart from Maxima, Reduce, Mathematica and Maple is the design of the Axiom mathematical library. The SPAD language (and Aldor) was designed specifically to make it possible to write mathematical algorithms in a flexible but type-correct manner which today might be referred to as a polymorphic object-oriented paradigm, such as you might find in Haskell and to a lesser extent in Python and similar languages." Another difference with these other CAS's, as was emphasized by Martin Rubey, is that Aldor has a very well-defined semantics (see the Aldor compiler users guide). In his words: "the single most important bit about Axiom, namely that it has types, and types are (in SPAD: nearly, in Aldor: really) first class objects. Maybe the best way to illustrate the use of types is the constructor Fraction. Take any integral domain, for example, starting with Integer. Fraction Integer gives you the rationals; starting with Polynomial Integer, Fraction Polynomial Integer gives you rational functions." These properties of SPAD and/or Aldor are attractive to theoretical computer scientists investigating implementation techniques for various mathematical algorithms (see both LM] and the R] for examples).

This example, given to illustrate Aldor syntax, was given by Bill Page at a recent talk at the University of WashingtonNote4].

A prime number sieve to count primes <= n: 

#pile
#include "axiom.as"

import from Boolean, Integer, NonNegativeInteger
sieve(n: Integer): Integer  ==
  isprime: OneDimensionalArray Boolean := new(n::NonNegativeInteger, true)
  np:Integer := 0
  for p in 2..n | isprime p repeat
    np := np + 1
    for i in (p+p)..n by p repeat isprime i := false
  np

Axiom also contains an interpreter, implementing a subset of SPAD, by which the user interacts with the Axiom system on the command line.

Basics

A great deal of information about Axiom is available on its website. Another useful aspect of the Axiom website is the excellent webpage providing a comparison between CAS's: http://wiki.axiom-developer.org/RosettaStone

Active developers

In addition to Tim Daly (who, by the way, pays for the Axiom website out of his own pocket), presently, Axiom has several very active, very smart developers. The core active Axiom developers in alphabetical order are Christian Aistleitner (for Aldor), Tim Daly, Gabriel Dos Reis, Waldek Hebisch, Ralf Hemmecke, Bill Page, Martin Rubey, William Sit, and Gregory Vanuxem. This is leaving out a very long list or contributors and developers (such a list would be pages long and include a who's who of CAS pioneers) but these names appear to be the most active on the developers email list in the past 6 months. Tim Daly is the lead developer.

Capabilities

Axiom has the ability to manipulate symbolic numerical expressions, including differentiation, integration, Taylor series, Laplace transforms, ordinary differential equations, systems of linear equations, polynomials, and sets, lists, vectors, matrices, and tensors. It has a package for algebraic-geometric codes and function fields over finite fields, a package for Homology computations, and a package for computing with Lyndon words, to name a few. For a list of others, please see http://wiki.axiom-developer.org/AxiomContributions.

The Axiom library has an extensive collection of routines designed to implement algebraic routines for diverse areas of mathematics. Again, to quote from Bill Page: "The Axiom library implements a hierarchy of abstract data structure types, from simple Aggregates to Keyed Dictionaries and Lazy Streams, which collectively make SPAD a very high level programming language. This is important for the representation of mathematical objects and the Axiom library uses these to provide an even more extensive hierarchy of algebraic categories, from Sets to FiniteFields and Partial Differential Rings, etc." Axiom implements a very wide range of mathematical concepts in the library (over 1300 by one count). Moreover, for many of these mathematical objects, Scratchpad or Axiom was the first CAS where they were implemented (see for example, the book of Davenport D], which describes one pioneering effort.).

Here are a few simple examples: differentiation such as d(xx)/dx, limits such as Sum{j=1}infty j/2j, pi to 100 digits, power series, symbolic summations, and symbolic matrices. 

(1) -> D(x^x,x)
               x      x - 1
   (1)  log(x)x  + x x
                                                     Type: Expression Integer
(2) -> limit(sum(j/2^j,j=1..n),n=%plusInfinity)
   (2)  2
                        Type: Union(OrderedCompletion Expression Integer,...)

(3) -> limit(sum(1/3^j,j=0..n),n=%plusInfinity)
(3) ->
        3
   (3)  -
        2
                        Type: Union(OrderedCompletion Expression Integer,...)
(4) -> digits(100)
   (4)  20
                                                        Type: PositiveInteger
(5) -> %pi :: Float
   (5)
  3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 592307816
  4 0628620899 8628034825 342117068
                                                                  Type: Float
(6) -> series(x**x, x = 1)
   (6)
                          2   1        3   1        4    1        5
     1 + (x - 1) + (x - 1)  + - (x - 1)  + - (x - 1)  + -- (x - 1)
                              2            3            12
   +
      3        6    1         7    59         8    71         9
     -- (x - 1)  - --- (x - 1)  + ---- (x - 1)  - ---- (x - 1)
     40            120            2520            5040
   +
      131         10            11
     ----- (x - 1)   + O((x - 1)  )
     10080
                        Type: UnivariatePuiseuxSeries(Expression Integer,x,1)

(7) -> sum(cos((2*r-1)*%pi/(2*n+1)), r=0..5)


              9%pi          7%pi          5%pi          3%pi            %pi
   (7)  cos(------) + cos(------) + cos(------) + cos(------) + 2cos(------)
             2n + 1        2n + 1        2n + 1        2n + 1         2n + 1
                                                     Type: Expression Integer

(8) -> xx:= matrix([[a, b], [c, d]])
(8) ->
(8) ->
         +a  b+
   (8)  |    |
         +c  d+
                                              Type: Matrix Polynomial Integer
(9) -> determinant xx
(9) ->
(9) ->
   (9)  a d - b c
                                                     Type: Polynomial Integer

Many CAS's can do what is given above. To show the advantages of generic programming using types, consider the following matrix of complete symmetric functions, written in the basis of power sum symmetric functions: 

(10) -> m := matrix [[complete 1, complete 0],[complete 2, complete 1]]

        +     (1)        [] +
        |                   |
  (10)  |1       1   2      |
        |- (2) + - (1 )  (1)|
        +2       2          +
                            Type: Matrix SymmetricPolynomial Fraction Integer
(11) -> determinant m

          1       1   2
  (11)  - - (2) + - (1 )
          2       2
                                   Type: SymmetricPolynomial Fraction Integer

Note that Axiom uses the product in the ring of symmetric functions to compute the determinant. To check, by Jacobi-Trudi the result should coincide with the Schur function corresponding to the partition (1,1): 

(12) -> SFunction [1,1]

          1       1   2
  (12)  - - (2) + - (1 )
          2       2
                                   Type: SymmetricPolynomial Fraction Integer

Here are some ODEs that Axiom can solve: 

(10) -> y:= operator('y);
(10) ->
                                                          Type: BasicOperator
(11) -> solve(D(y(x), x) + y(x) * sin x/cos x - 1/cos x = 0, y, x)
   (11)  [particular= sin(x),basis= [cos(x)]]
Type: Union(Record(particular: Expression Integer,basis: List Expression Integer),...)

(12) -> solve(D(y(x), x, 2)+4*D(y(x), x)+4*y(x)-x*exp(-2*x) = 0, y, x)

                      3  - 2x
                     x %e               - 2x     - 2x
   (12)  [particular= --------,basis= [%e    ,x %e    ]]
                         6
Type: Union(Record(particular: Expression Integer,basis: List Expression Integer),...)

(13) -> solve(x*(1-x**2)*D(y(x), x) + (2*x**2 -1)*y(x) - x**3*y(x)**3 = 0, y, x)

             5         2     4     2
        (- 2x  + 4)y(x)  + 5x  - 5x
   (13)  ----------------------------
                        2
                   5y(x)
                                          Type: Union(Expression Integer,...)

Indeed, y = sin(x) does solve the first order linear ODE y' + tan(x)y = sec(x), as Axiom tells us in (11). Secondly, Axiom has no problem with the nasty, but linear second order, constant-coefficient ODE y"+4y'+4y = xe-2x (see (12)). But the last one, Bernoulli's non-linear equation x(1-x2 )y' + (2x2 - 1)y - x3 y3 = 0, is much harder to solve. (I was not able to solve Bernoulli's equation in Maxima, but according to L97], Macsyma can solve thisNote5].) The fact that Axiom had no problem doing this (see (13)) is a good illustration of it's unique computational firepower.

Martin Rubey R] has written a package GUESS which guesses formulas for a sequence given its first few terms. He was kind enough to send me some examples for this survey: 

(7) -> guessPRec [1,2,3,5,8,13]

   (7)
   [[function= [f(n): f(n + 2) - f(n + 1) - f(n)= 0,f(0)= 1,f(1)= 2],order= 0]]

(8) -> l := [1, 1, q+1, q**3+q*q+2*q+1, q**6+q**5+2*q**4+3*q**3+3*q*q+3*q+1, _
      q**10+q**9+2*q**8+3*q**7+5*q**6+5*q**5+7*q**4+7*q**3+6*q*q+4*q+1];

(9) -> guessADE(q)(l, maxPower==2).1.function

   (9)
   BRACKET
        n
      [x ]f(x):
                                                ,        ,,
          - x f(x)f(q x) + f(x) - 1= 0,f(0)= 1,f (0)= 1,f  (0)= 2q + 2

       ,
           ,,,       3     2
          f   (0)= 6q  + 6q  + 12q + 6

       ,
           (iv)        6      5      4      3      2
          f    (0)= 24q  + 24q  + 48q  + 72q  + 72q  + 72q + 24


(10) -> guess([0,1,3,9,33], [guessRat], [guessSum, guessProduct])

                            s  - 1
                     n - 1   5
                      --+   ++-++
   (10)  [[function=  >      | |    p  + 2,order= 0]]
                      --+    | |     4
                     s = 0  p = 0
                      5      4

There is currently no other package that can do this.

I can't end this paper without at least mentioning Axiom's ability to compute AG codes, thanks to the {\tt PAFF} packageNote6] by Gaetan Hache. (The curious reader is referred to the introduction of the CCA article J] for a very brief background on the mathematics of AG codes - error-correct block codes which one constructs in a certain way from algebraic curves over finite fields.) Gaetan Hache has written a very impressive array of routines implementing function fields over finite fields in Axiom. Consider the projective curve C over GF(2) given by X5 + Y2 Z3 + Y Z4 = 0. In H1], Hache shows how to use his package to compute a basis of the Riemann-Roch space L(D) for C, where D=10(P1 + P2 + P3) and P1 , P2 , P3 are the three places of degree 1 on C. In H2], he uses this curve over GF(24) to construct an error-correcting code over GF(16) with parameters [n,k,d]=[33,11,21]. The lengthy details, which perhaps deserve an article on their own, must be omitted for reasons of space. However, this is another good illustration of Axiom's unusual abilities.

In summary, Axiom has some impressive packages, an active group of talented developers, and a fascinating history. Axiom serves a very important and very useful role for certain very advanced mathematical programmers, due to srecial properties of its language. To find out more, please visit http://wiki.axiom-developer.org/.

Thanks

It is a pleasure to thank Bill Page, not only for his generous help with this article but also the \sage package {\tt axiom4sage}, which was used to compute some of the examples above. I also thank Martin Rubey for very detailed criticisms and suggestions, including many of the examples above. Stephen Watt kindly corrected some historical inaccuracies in an earlier version. Finally, I thank both Emil Volcheck and Tim Daly for their useful suggestions, and G\'aetan Hach\'e for kindly allowing me to quote from some private email correspondence. Of course, only I am responsible for any mistakes. If you have corrections or comments, please email me at (wdjoyner AT gmail DOT com).

References

Available at: http://portal.axiom-developer.org/public/book2.pdf.

Available at: http://www-rocq.inria.fr/codes/Gaetan.Hache/Axiom-BN/paffExempl

Available at: http://www-rocq.inria.fr/codes/Gaetan.Hache/Axiom-BN/paffExemplAGcode

Available: http://www.csd.uwo.ca/~moreno//Publications/MorenoMaza-Li-ICMS-06.ps

Available: http://kfe.fjfi.cvut.cz/~liska/ca/all.html.

Available at: http://portal.axiom-developer.org/refs/articles/axiom.pdf

Available at: http://front.math.ucdavis.edu/math.CO/0702086.

Available at: and [http://sage.math.washington.edu/sage/.

Footnotes

Such a license is open source, in the sense of OSI http://www.opensource.org/, and GPL compatible, in the sense of http://www.gnu.org/licenses/license-list.html\#SoftwareLicenses.

By "released", I mean that they allowed aldor.org to distribute the Aldor compiler in a certain mixture of source code and binaries. I don't mean to imply (because I don't know which parts of the source code is owned by who) that NAG transferred all copyrights of the Aldor source code to aldor.org.

I realize different people mean different things by these terms "strongly and statically typed" http://en.wikipedia.org/wiki/Strong_typing! Please see PT] for details.

Bill Page, "Introduction to the Axiom Library compiler for Python Programmers", at http://www.sagemath.org:9001/AxiomCompiler and http://sage.math.washington.edu/sage_days2_audio/.

In fact, L97] indicates that Macsyma can solve Bernoulli's equation explicitly, whereas Axiom's solution is implicit. Both types of solutions have their advantages.

Though there is no explicit distribution license for the PAFF package given in its documentation or code, in an email to the author dated 11/30/2006, Gaetan Hache said: "I have no problem to release it under GPL or an even less restrictive license such as the MIT one." Gaetan also points out: "in the examples there is an error: an argument is missing when PAFFFF is called -- for example, PAFFFF( arg1, arg2 ) should be replace by PAFFFF( arg1, arg2, BLQT)".

Axiom_as_an_OSCAS (last edited 2008-11-14 13:42:10 by localhost)