\documentclass{book} %\usepackage{axiom} \usepackage{graphicx} % struggle with latex figure-floating behavior \renewcommand\floatpagefraction{.9} \renewcommand\topfraction{.9} \renewcommand\bottomfraction{.9} \renewcommand\textfraction{.1} \setcounter{totalnumber}{50} \setcounter{topnumber}{50} \setcounter{bottomnumber}{50} % spadcommands are the actual text that you type at the axiom prompt \newcommand{\spadcommand}[1]% {\begin{flushleft}{\tt #1}\end{flushleft}\vskip .1cm } % spadgraph are the actual text that you type at the axiom prompt for draw \newcommand{\spadgraph}[1]% {\begin{flushleft}{\tt #1}\end{flushleft}\vskip .1cm } % returnType is the type signature returned by the axiom interpreter \newcommand{\returnType}[1]% {\begin{flushright}{\tt #1}\end{flushright}\vskip .1cm} % spadsig gives the standard -> notation for signatures \newcommand{\spadsig}[2]{{\sf #1 $\rightarrow$ #2}} % The book begins with some introductory material that is not really % listed as a chapter. This creates a header similar to \chapter. \newcommand{\pseudoChapter}[1]% {\vskip .5in \noindent {\Large{\bf #1}}\vskip .5in} % The book begins with some introductory material that is not really % listed as a section. This creates a header similar to \section. \newcommand{\pseudoSection}[1]% {\vskip .25in \noindent {\large{\bf #1}}\vskip .25in} % spadofFrom records the operation in the index and the domain in the index \newcommand{\spadopFrom}[2]{\index{library!operations!#1 @\begingroup \string\tt{} #1 \endgroup}\index{#2}``{\tt #1}''} % spadfunFrom records the function name and domain in the index \newcommand{\spadfunFrom}[2]{{\bf #1}\index{#1 @\begingroup \string\bf{} #1 \endgroup}\index{#2}} % special meanings for math characters \newcommand{\N}{\mbox{\bbold N}} \newcommand{\Natural}{\mbox{\bbold N}} \newcommand{\Z}{\mbox{\bbold Z}} \newcommand{\Integer}{\mbox{\bbold Z}} \newcommand{\Rational}{\mbox{\bbold Q}} \newcommand{\Q}{\mbox{\bbold Q}} \newcommand{\Complex}{\mbox{\bbold C}} \newcommand{\C}{{\mathcal C}} \newcommand{\Real}{\mbox{\bbold R}} \newcommand{\F}{{\mathcal F}} \newcommand{\R}{{\mathcal R}} % draw a box around a text block \newcommand\boxed[2]{% \begin{center} \begin{tabular}{|c|} \hline \begin{minipage}{#1} \normalsize {#2} \end{minipage}\\ \hline \end{tabular} \end{center}} \newcommand{\optArg}[1]{{{\tt [}{#1}{\tt ]}}} \newcommand{\argDef}[1]{{\tt ({#1})}} \newcommand{\funSyntax}[2]{{\bf #1}{\tt ({\small\it{#2}})}} \newcommand{\funArgs}[1]{{\tt ({\small\it {#1}})}\newline} \newcommand{\condata}[4]{{\bf #1} {\bf #2} {\bf #3} {\bf #4}} \def\glossaryTerm#1{{\bf #1}\index{#1}} \def\glossaryTermNoIndex#1{{\bf #1}} \def\glossarySyntaxTerm#1{{\tt #1}\index{#1}} \long\def\ourGloss#1#2{\par\pagebreak[3]{#1}\newline{#2}} \def\csch{\mathop{\rm csch}\nolimits} \def\erf{\mathop{\rm erf}\nolimits} \def\zag#1#2{ {{\hfill \left. {#1} \right|} \over {\left| {#2} \right. \hfill} } } % these bitmaps are used by HyperDoc \newdimen\commentWidth \commentWidth=11pc \newdimen\colGutterWidth \colGutterWidth=1pc \newdimen\baseLeftSkip \baseLeftSkip=\commentWidth \advance\baseLeftSkip by \colGutterWidth \newcommand\ExitBitmap{{\setlength{\unitlength}{0.01in}\begin{picture}(50,16)(0,0)\special{psfile=ps/exit.ps}\end{picture}}} \newcommand\ReturnBitmap{{\setlength{\unitlength}{0.01in}\begin{picture}(50,16)(0,0)\special{psfile=ps/home.ps}\end{picture}}} \newcommand\HelpBitmap{{\setlength{\unitlength}{0.01in}\begin{picture}(50,16)(0,0)\special{psfile=ps/help.ps}\end{picture}}} \newcommand\UpBitmap{{\setlength{\unitlength}{0.01in}\begin{picture}(50,16)(0,0)\special{psfile=ps/up.ps}\end{picture}}} \newcommand{\tpd}[5]{{\setlength{\unitlength}{0.01in}\begin{picture}(#1,#2)(#3,#4)\special{psfile=#5}\end{picture}}} \begin{document} \begin{titlepage} \center{\includegraphics{ps/axiomFront.ps}} \vskip 0.1in \includegraphics{ps/bluebayou.ps}\\ \vskip 0.1in {\Huge{The 30 Year Horizon}} \vskip 0.1in $$ \begin{array}{lll} Manuel\ Bronstein & William\ Burge & Timothy\ Daly \\ James\ Davenport & Michael\ Dewar & Martin\ Dunstan \\ Albrecht\ Fortenbacher & Patrizia\ Gianni & Johannes\ Grabmeier \\ Jocelyn\ Guidry & Richard\ Jenks & Larry\ Lambe \\ Michael\ Monagan & Scott\ Morrison & William\ Sit \\ Jonathan\ Steinbach & Robert\ Sutor & Barry\ Trager \\ Stephen\ Watt & Jim\ Wen & Clifton\ Williamson \end{array} $$ \center{\large{VOLUME 2: PROGRAMMING}} \end{titlepage} \pagenumbering{roman} \begin{verbatim} The Blue Bayou image Copyright (c) 2004 Jocelyn Guidry Portions Copyright (c) 2004 Martin Dunstan Portions Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. All rights reserved. This book and the Axiom software is licensed as follows: Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: - Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. - Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. - Neither the name of The Numerical ALgorithms Group Ltd. nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. \end{verbatim} \tableofcontents \vfill \eject \setlength{\parindent}{0em} \setlength{\parskip}{1ex} {\Large{\bf New Foreword}} \vskip .25in On October 1, 2001 Axiom was withdrawn from the market and ended life as a commercial product. On September 3, 2002 Axiom was released under the Modified BSD license, including this document. On August 27, 2003 Axiom was released as free and open source software available for download from the Free Software Foundation's website, Savannah. Work on Axiom has had the generous support of the Center for Algorithms and Interactive Scientific Computation (CAISS) at City College of New York. Special thanks go to Dr. Gilbert Baumslag for his support of the long term goal. The online version of this documentation is roughly 1000 pages. In order to make printed versions we've broken it up into three volumes. The first volume is tutorial in nature. The second volume is for programmers. The third volume is reference material. We've also added a fourth volume for developers. All of these changes represent an experiment in print-on-demand delivery of documentation. Time will tell whether the experiment succeeded. Axiom has been in existence for over thirty years. It is estimated to contain about three hundred man-years of research and has, as of September 3, 2003, 143 people listed in the credits. All of these people have contributed directly or indirectly to making Axiom available. Axiom is being passed to the next generation. I'm looking forward to future milestones. With that in mind I've introduced the theme of the ``30 year horizon''. We must invent the tools that support the Computational Mathematician working 30 years from now. How will research be done when every bit of mathematical knowledge is online and instantly available? What happens when we scale Axiom by a factor of 100, giving us 1.1 million domains? How can we integrate theory with code? How will we integrate theorems and proofs of the mathematics with space-time complexity proofs and running code? What visualization tools are needed? How do we support the conceptual structures and semantics of mathematics in effective ways? How do we support results from the sciences? How do we teach the next generation to be effective Computational Mathematicians? The ``30 year horizon'' is much nearer than it appears. \vskip .25in %\noindent Tim Daly\\ CAISS, City College of New York\\ November 10, 2003 ((iHy)) \vfill \eject \pagenumbering{arabic} \pseudoChapter{Introduction to Axiom} \label{ugNewIntro} \section{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. \subsection{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 $$\int\left({{1\over{(x^3 \ {(a+b x)}^{1/3})}}}\right)dx$$ we would enter this into Axiom as: \spadcommand{integrate(1/(x**3 * (a+b*x)**(1/3)),x)} which would give the result: $$ {\left( \begin{array}{@{}l} \displaystyle -{2 \ {b^2}\ {x^2}\ {\sqrt{3}}\ {\log \left({{{\root{3}\of{a}}\ {{\root{3}\of{{b \ x}+ a}}^2}}+{{{\root{3}\of{a}}^2}\ {\root{3}\of{{b \ x}+ a}}}+ a}\right)}}+ \\ \\ \displaystyle {4 \ {b^2}\ {x^2}\ {\sqrt{3}}\ {\log \left({{{{\root{3}\of{a}}^ 2}\ {\root{3}\of{{b \ x}+ a}}}- a}\right)}}+ \\ \\ \displaystyle {{12}\ {b^2}\ {x^2}\ {\arctan \left({{{2 \ {\sqrt{3}}\ {{\root{3}\of{a}}^ 2}\ {\root{3}\of{{b \ x}+ a}}}+{a \ {\sqrt{3}}}}\over{3 \ a}}\right)}}+ \\ \\ \displaystyle {{\left({{12}\ b \ x}-{9 \ a}\right)}\ {\sqrt{3}}\ {\root{3}\of{a}}\ {{\root{3}\of{{b \ x}+ a}}^2}} \end{array} \right)}\over{{18}\ {a^2}\ {x^2}\ {\sqrt{3}}\ {\root{3}\of{a}}} $$ \returnType{Type: Union(Expression Integer,...)} 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. \subsection{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 $x^{49}-49x^4+9$ to 49 digits of accuracy. First we need to change the default output length of numbers: \spadcommand{digits(49)} and then we execute the command: \spadcommand{solve(x**49-49*x**4+9 = 0,1.e-49)} $$ \begin{array}{@{}l} \displaystyle \left[{x = -{0.6546536706904271136718122105095984761851224331 556}}, \right. \\ \\ \displaystyle \left.{x ={1.086921395653859508493939035954893289009213388763}}, \right. \\ \\ \displaystyle \left.{x ={0.654653670725527173969468606613676483536148760766 1}}\right] \end{array} $$ \returnType{Type: List Equation Polynomial Float} 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 $10$ to the $90$-th power in base $32$? \spadcommand{radix(10**90,32)} returns: %\noindent {\tt FMM3O955CSEIV0ILKH820CN3I7PICQU0OQMDOFV6TP000000000000000000 } \returnType{Type: RadixExpansion 32} 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. \subsection{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 $J_0(\sqrt{x^2+y^2})$ for $-20 \leq x,y \leq 20$. \spadcommand{draw(5*besselJ(0,sqrt(x**2+y**2)), x=-20..20, y=-20..20)} \begin{figure}[htbp] \includegraphics[bbllx=1, bblly=39, bburx=298, bbury=290]{ps/bessintr.ps} \caption{$J_0(\sqrt{x^2+y^2})$ for $-20 \leq x,y \leq 20$} \label{tpdhere} \end{figure} 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. \subsection{HyperDoc} \begin{figure}[htbp] \includegraphics[bbllx=1, bblly=1, bburx=298, bbury=290]{ps/h-root.ps} \caption{Hyperdoc opening menu} \label{fig-intro-br} \end{figure} 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, {\tt Matrix}, {\bf factor}, and {\it 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 $x^{49} - 49x^4 + 9$ 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 \ref{fig-intro-br} on page~\pageref{fig-intro-br} and the specified mouse clicks, you and HyperDoc generate the correct command to issue to compute the answer. \subsection{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. \spadcommand{p(0) == 1} \returnType{Type: Void} The second Legendre polynomial. \spadcommand{p(1) == x} \returnType{Type: Void} The $n$-th Legendre polynomial for $(n > 1)$. \spadcommand{p(n) == ((2*n-1)*x*p(n-1) - (n-1) * p(n-2))/n} \returnType{Type: Void} 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 $p$ do no computation---they simply tell Axiom how to compute $p(k)$ for some positive integer $k$. To actually get a value of a Legendre polynomial, you ask for it. \index{Legendre polynomials} What is the tenth Legendre polynomial? \spadcommand{p(10)} \begin{verbatim} Compiling function p with type Integer -> Polynomial Fraction Integer Compiling function p as a recurrence relation. \end{verbatim} $$ {{{46189} \over {256}} \ {x \sp {10}}} -{{{109395} \over {256}} \ {x \sp 8}}+{{{45045} \over {128}} \ {x \sp 6}} -{{{15015} \over {128}} \ {x \sp 4}}+{{{3465} \over {256}} \ {x \sp 2}} -{{63} \over {256}} $$ \returnType{Type: Polynomial Fraction Integer} Axiom applies the above pieces for $p$ to obtain the value of $p(10)$. But it does more: it creates an optimized, compiled function for $p$. The function is formed by putting the pieces together into a single piece of code. By {\it compiled}, we mean that the function is translated into basic machine-code. By {\it optimized}, we mean that certain transformations are performed on that code to make it run faster. For $p$, 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 $x^{90}$ in $p(90)$? \spadcommand{coefficient(p(90),x,90)} $$ {5688265542052017822223458237426581853561497449095175} \over {77371252455336267181195264} $$ \returnType{Type: Polynomial Fraction Integer} 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. \subsection{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. \spadcommand{[D(p(i),x) for i in 1..]} $$ \begin{array}{@{}l} \displaystyle \left[ 1, {3 \ x}, {{{{15}\over 2}\ {x^2}}-{3 \over 2}}, {{{{35}\over 2}\ {x^3}}-{{{15}\over 2}\ x}}, {{{{315}\over 8}\ {x^4}}-{{{105}\over 4}\ {x^2}}+{{15}\over 8}}, \right. \\ \\ \displaystyle \left.{{{{693}\over 8}\ {x^5}}-{{{315}\over 4}\ {x^3}}+{{{105}\over 8}\ x}}, {{{{3003}\over{16}}\ {x^6}}-{{{3465}\over{16}}\ {x^ 4}}+{{{945}\over{16}}\ {x^2}}-{{35}\over{16}}}, \right. \\ \\ \displaystyle \left.{{{{6435}\over{16}}\ {x^7}}-{{{9009}\over{16}}\ {x^5}}+ {{{3465}\over{16}}\ {x^3}}-{{{315}\over{16}}\ x}}, \right. \\ \\ \displaystyle \left.{{{{109395}\over{128}}\ {x^8}}-{{{45045}\over{32}}\ {x^ 6}}+{{{45045}\over{64}}\ {x^4}}-{{{3465}\over{32}}\ {x^2}}+{{3 15}\over{128}}}, \right. \\ \\ \displaystyle \left.{{{{230945}\over{128}}\ {x^9}}-{{{109395}\over{32}}\ {x^ 7}}+{{{135135}\over{64}}\ {x^5}}-{{{15015}\over{32}}\ {x^3}}+ {{{3465}\over{128}}\ x}}, \ldots \right] \end{array} $$ \returnType{Type: Stream Polynomial Fraction Integer} 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 $\log(\cot(x))$ about $x=\pi/2$? %NOTE: The book has a different answer (see p6) \spadcommand{series(log(cot(x)),x = \%pi/2)} $$ \begin{array}{@{}l} \displaystyle {\log \left({{-{2 \ x}+ \pi}\over 2}\right)}+ {{1 \over 3}\ {{\left(x -{\pi \over 2}\right)}^2}}+ {{7 \over{90}}\ {{\left(x -{\pi \over 2}\right)}^4}}+ {{{62}\over{2835}}\ {{\left(x -{\pi \over 2}\right)}^6}}+ \\ \\ \displaystyle {{{127}\over{18900}}\ {{\left(x -{\pi \over 2}\right)}^8}}+ {{{146}\over{66825}}\ {{\left(x -{\pi \over 2}\right)}^{10}}}+ {O \left({{\left(x -{\pi \over 2}\right)}^{11}}\right)} \end{array} $$ \returnType{Type: GeneralUnivariatePowerSeries(Expression Integer,x,pi/2)} Series and streams make no attempt to compute {\it all} their elements! Rather, they stand ready to deliver elements on demand. What is the coefficient of the $50$-th term of this series? \spadcommand{coefficient(\%,50)} $$ {44590788901016030052447242300856550965644} \over {7131469286438669111584090881309360354581359130859375} $$ \returnType{Type: Expression Integer} \subsection{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. \spadcommand{matrix [ [x + \%i,0], [1,-2] ]} $$ \left[ \begin{array}{cc} {x+i} & 0 \\ 1 & -2 \end{array} \right] $$ \returnType{Type: Matrix Polynomial Complex Integer} 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. \spadcommand{inverse(\%)} $$ \left[ \begin{array}{cc} {1 \over {x+i}} & 0 \\ {1 \over {{2 \ x}+{2 \ i}}} & -{1 \over 2} \end{array} \right] $$ \returnType{Type: Union(Matrix Fraction Polynomial Complex Integer,...)} \subsection{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 $rule$ command to describe the transformation rules you \index{rule} need. Then give the rules a name and apply that name as a function to your trigonometric expression. Introduce two rewrite rules. \spadcommand{sinCosExpandRules := rule\\ \ \ sin(x+y) == sin(x)*cos(y) + sin(y)*cos(x)\\ \ \ cos(x+y) == cos(x)*cos(y) - sin(x)*sin(y)\\ \ \ sin(2*x) == 2*sin(x)*cos(x)\\ \ \ cos(2*x) == cos(x)**2 - sin(x)**2 } \begin{verbatim} {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) } \end{verbatim} \returnType{Type: Ruleset(Integer,Integer,Expression Integer)} Apply the rules to a simple trigonometric expression. \spadcommand{sinCosExpandRules(sin(a+2*b+c))} $$ \begin{array}{@{}l} \displaystyle {{\left(-{{\cos \left({a}\right)}\ {{\sin \left({b}\right)}^2}}- {2 \ {\cos \left({b}\right)}\ {\sin \left({a}\right)}\ {\sin \left({b}\right)}}+{{\cos \left({a}\right)}\ {{\cos \left({b}\right)}^ 2}}\right)}\ {\sin \left({c}\right)}}- \\ \\ \displaystyle {{\cos \left({c}\right)}\ {\sin \left({a}\right)}\ {{\sin \left({b}\right)}^ 2}}+{2 \ {\cos \left({a}\right)}\ {\cos \left({b}\right)}\ {\cos \left({c}\right)}\ {\sin \left({b}\right)}}+ \\ \\ \displaystyle {{{\cos \left({b}\right)}^2}\ {\cos \left({c}\right)}\ {\sin \left({a}\right)}} \end{array} $$ \returnType{Type: Expression Integer} Using input files, you can create your own library of transformation rules relevant to your applications, then selectively apply the rules you need. \subsection{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 $S$. \spadcommand{S := [3*x**3 + y + 1 = 0,y**2 = 4]} $$ \left[ {{y+{3 \ {x \sp 3}}+1}=0}, {{y \sp 2}=4} \right] $$ \returnType{Type: List Equation Polynomial Integer} Solve the system $S$ using rational number arithmetic and 30 digits of accuracy. \spadcommand{solve(S,1/10**30)} $$ \left[ {\left[ {y=-2}, {x={{1757879671211184245283070414507} \over {2535301200456458802993406410752}}} \right]}, {\left[ {y=2}, {x=-1} \right]} \right] $$ \returnType{Type: List List Equation Polynomial Fraction Integer} Solve $S$ with the solutions expressed in radicals. \spadcommand{radicalSolve(S)} $$ \begin{array}{@{}l} \displaystyle \left[{\left[{y = 2}, {x = - 1}\right]}, {\left[{y = 2}, {x ={{-{\sqrt{- 3}}+ 1}\over 2}}\right]}, \right. \\ \\ \displaystyle \left.{\left[{y = 2}, {x ={{{\sqrt{- 3}}+ 1}\over 2}}\right]}, {\left[{y = - 2}, {x ={1 \over{\root{3}\of{3}}}}\right]}, \right. \\ \\ \displaystyle \left.{\left[{y = - 2}, {x ={{{{\sqrt{- 1}}\ {\sqrt{3}}}- 1}\over{2 \ {\root{3}\of{3}}}}}\right]}, {\left[{y = - 2}, {x ={{-{{\sqrt{- 1}}\ {\sqrt{3}}}- 1}\over{2 \ {\root{3}\of{3}}}}}\right]}\right] \end{array} $$ \returnType{Type: List List Equation Expression Integer} 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. \subsection{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. \vfill\eject \pseudoChapter{A Technical Introduction} \label{ugTechIntro} Axiom has both an {\it interactive language} for user interactions and a {\it programming language} for building library modules. Like Modula 2, \index{Modula 2} PASCAL, \index{PASCAL} FORTRAN, \index{FORTRAN} and Ada, \index{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. {\it 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 {\it any} field. Likewise a greatest common divisor can compute the ``gcd'' of two elements from {\it 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: \subsection{Types are Defined by Abstract Datatype Programs} Basic types are called {\it domains of computation}, or, simply, {\it domains.} \index{domain} Domains are defined by Axiom programs of the form: \begin{verbatim} Name(...): Exports == Implementation \end{verbatim} Each domain has a capitalized {\tt Name} that is used to refer to the class of its members. For example, {\tt Integer} denotes ``the class of integers,'' {\tt Float}, ``the class of floating point numbers,'' and {\tt String}, ``the class of strings.'' The ``{\tt ...}'' part following {\tt Name} lists zero or more parameters to the constructor. Some basic ones like {\tt Integer} take no parameters. Others, like {\tt Matrix}, {\tt Polynomial} and {\tt List}, take a single parameter that again must be a domain. For example, {\tt Matrix(Integer)} denotes ``matrices over the integers,'' {\tt Polynomial (Float)} denotes ``polynomial with floating point coefficients,'' and {\tt 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 {\tt Exports} part specifies operations for creating and manipulating objects of the domain. For example, type {\tt Integer} exports constants $0$ and $1$, and operations \spadopFrom{+}{Integer}, \spadopFrom{-}{Integer}, and \spadopFrom{*}{Integer}. While these operations are common, others such as \spadfunFrom{odd?}{Integer} and \spadfunFrom{bit?}{Integer} are not. In addition the Exports section can contain symbols that represent properties that can be tested. For example, the Category {\tt EntireRing} has the symbol {\tt noZeroDivisors} which asserts that if a product is zero then one of the factors must be zero. The {\tt 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 {\tt Float}. \subsection{The Type of Basic Objects is a Domain or Subdomain} Every Axiom object belongs to a {\it unique} domain. The domain of an object is also called its {\it type.} Thus the integer $7$ has type {\tt Integer} and the string {\tt "daniel"} has type {\tt String}. The type of an object, however, is not unique. The type of integer $7$ is not only {\tt Integer} but {\tt NonNegativeInteger}, {\tt PositiveInteger}, and possibly, in general, any other ``subdomain'' of the domain {\tt Integer}. A {\it subdomain} \index{subdomain} is a domain with a ``membership predicate''. {\tt PositiveInteger} is a subdomain of {\tt Integer} with the predicate ``is the integer $> 0$?''. Subdomains with names are defined by abstract datatype programs similar to those for domains. The {\it Export} part of a subdomain, however, must list a subset of the exports of the domain. The {\tt Implementation} part optionally gives special definitions for subdomain objects. \subsection{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 {\it category}. \index{category} Categories are described by programs of the form: \begin{verbatim} Name(...): Category == Exports \end{verbatim} The type of every category is the distinguished symbol {\tt Category.} The category {\tt Name} is used to designate the class of domains of that type. For example, category {\tt Ring} designates the class of all rings. Like domains, categories can take zero or more parameters as indicated by the ``{\tt ...}'' part following {\tt Name.} Two examples are {\tt Module(R)} and {\tt MatrixCategory(R,Row,Col)}. The {\tt Exports} part defines a set of operations. For example, {\tt Ring} exports the operations \spadopFrom{0}{Ring}, \spadopFrom{1}{Ring}, \spadopFrom{+}{Ring}, \spadopFrom{-}{Ring}, and \spadopFrom{*}{Ring}. Many algebraic domains such as {\tt Integer} and {\tt Polynomial (Float)} are rings. {\tt String} and {\tt List (R)} (for any domain $R$) are not. Categories serve to ensure the type-correctness. The definition of matrices states {\tt Matrix(R: Ring)} requiring its single parameter $R$ 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. \subsection{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$: \begin{verbatim} R: Ring power: (R, NonNegativeInteger): R -> R power(x, n) == x ** n \end{verbatim} Line 1 declares the symbol $R$ to be a ring. Line 2 declares the type of $power$ in terms of $R$. From the definition on line 3, $power(3,2)$ produces 9 for $x = 3$ and $R =$ {\tt Integer}. Also, $power(3.0,2)$ produces $9.0$ for $x = 3.0$ and $R =$ {\tt Float}. $power("oxford",2)$ however fails since $"oxford"$ has type {\tt String} which is not a ring. Using symbolic domains, algorithms can be defined in their most natural or general setting. \subsection{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 {\tt SetCategory}, the class of algebraic sets. The notions of parents, ancestors, and descendants is clear. Thus ordered sets (domains of category {\tt 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. \begin{verbatim} SetCategory +---- Ring ---- IntegralDomain ---- Field | +---- Finite ---+ | \ +---- OrderedSet -----+ OrderedFinite \end{verbatim} \begin{center} Figure 1. A simplified category hierarchy. \end{center} \subsection{Domains Belong to Categories by Assertion} A category designates a class of domains. Which domains? You might think that {\tt Ring} designates the class of all domains that export $0$, $1$, \spadopFrom{+}{Integer}, \spadopFrom{-}{Integer}, and \spadopFrom{*}{Integer}. But this is not so. Each domain must {\it assert} which categories it belongs to. The {\tt Export} part of the definition for {\tt Integer} reads, for example: \begin{verbatim} Join(OrderedSet, IntegralDomain, ...) with ... \end{verbatim} This definition asserts that {\tt Integer} is both an ordered set and an integral domain. In fact, {\tt Integer} does not explicitly export constants $0$ and $1$ and operations \spadopFrom{+}{Ring}, \spadopFrom{-}{Ring} and \spadopFrom{*}{Ring} at all: it inherits them all from $Ring$! Since {\tt IntegralDomain} is a descendant of $Ring$, {\tt Integer} is therefore also a ring. Assertions can be conditional. For example, {\tt Complex(R)} defines its exports by: \begin{verbatim} Ring with ... if R has Field then Field ... \end{verbatim} Thus {\tt Complex(Float)} is a field but {\tt Complex(Integer)} is not since {\tt 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, {\bf 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 {\tt <} might be used to denote lexicographic-comparison in an algorithm. However, it is wrong to use the same {\tt <} with this definition of absolute-value: $$abs(x) == if\ x < 0\ then -x\ else\ x$$ Such a definition for {\tt abs} in Axiom is protected by context: argument $x$ is required to be a member of a domain of category {\tt OrderedSet}. \subsection{Packages Are Clusters of Polymorphic Operations} In Axiom, facilities for symbolic integration, solution of equations, and the like are placed in ``packages''. A {\it package} \index{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 $F$, you can do so with a package of the form: \begin{verbatim} MySolve(F: Field): Exports == Implementation \end{verbatim} where {\tt Exports} specifies the {\bf solve} operations you wish to export from the domain and the {\tt Implementation} defines functions for implementing your algorithms. Once Axiom has compiled your package, your algorithms can then be used for any {\tt F}: floating-point numbers, rational numbers, complex rational functions, and power series, to name a few. \subsection{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 $$M = \pmatrix{x^2+1&0\cr0&x / 2\cr}$$ using the command: \spadcommand{M = [ [x**2+1,0],[0,x / 2] ]::Matrix(POLY(FRAC(INT)))} $$ M={\left[ \begin{array}{cc} x^2+1 & 0 \\ 0 & x/2 \end{array} \right]} $$ \returnType{Type: Matrix Polynomial Fraction Integer} the interpreter first loads the modules {\tt Matrix}, {\tt Polynomial}, {\tt Fraction}, and {\tt Integer} from the library, then builds the {\it domain tower} ``matrices of polynomials of rational numbers (i.e. fractions of integers)''. You can watch the loading process by first typing \spadcommand{)set message autoload on} 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 \spadopFrom{*}{Matrix} from {\tt Matrix} is passed the matrix $M$ to compute $M * M$. The function is also passed an environment containing $R$ that, in this case, is {\tt Polynomial (Fraction (Integer))}. This results in the successive calling of the \spadopFrom{*}{Fraction} operations from {\tt Polynomial}, then from {\tt Fraction}, and then finally from {\tt Integer}. Categories play a policing role in the building of domains. Because the argument of {\tt Matrix} is required to be a {\tt Ring}, Axiom will not build nonsensical types such as ``matrices of input files''. \subsection{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: \begin{itemize} \item static type-checking at compile time; \item fast linkage to operations in domain-valued parameters; \item optimization techniques to be used for partially specified types (operations for ``vectors of $R$'', for instance, can be open-coded even though {\tt R} is unknown). \end{itemize} \subsection{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: \begin{itemize} \item 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. \item 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. \end{itemize} 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. \section{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 {\bf sin}, {\bf cos}, etc). \subsection{Basic Arithmetic} An example of this might be to calculate the cosine of 2.45 (in radians). To do this one would type: \spadcommand{cos 2.45} $$ -{0.7702312540 473073417} $$ \returnType{Type: Float} Before proceeding any further it would be best to explain the previous three lines. Firstly the text ``(1) {\tt ->} '' 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 {\sl 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 {\tt 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: \spadcommand{6.93 * 4.1328} $$ 28.640304 $$ \returnType{Type: Float} \spadcommand{6.93 / 4.1328} $$ 1.6768292682 926829268 $$ \returnType{Type: Float} but integer division isn't quite so obvious. For example, if one types: \spadcommand{4/6} $$ 2 \over 3 $$ \returnType{Type: Fraction Integer} a fractional result is obtained. The function used to display fractions attempts to produce the most readable answer. In the example: \spadcommand{4/2} $$ 2 $$ \returnType{Type: Fraction Integer} the result is stored as the fraction 2/1 but is displayed as the integer 2. This fraction could be converted to type {\tt Integer} with no loss of informatin but Axiom will not do so automatically. \subsection{Type Conversion} To obtain the floating point value of a fraction one must convert ( {\bf conversions} are applied by the user and {\bf coercions} are applied automatically by the interpreter) the result to type {\tt Float} using the ``::'' operator as follows: \spadcommand{(4.6)::Float} $$ 4.6 $$ \returnType{Type: Float} 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: \spadcommand{\%::Fraction Integer} $$ {23} \over 5 $$ \returnType{Type: Fraction Integer} where ``\%'' represents the previous {\it 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 {\bf 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 {\bf round} and {\bf 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 {\bf floating point} number. To extract the fractional part of a floating point number use the function {\bf fractionPart} but note that the sign of the result depends on the sign of the argument. Axiom obtains the fractional partof $x$ using $x - truncate(x)$: \spadcommand{round(3.77623)} $$ 4.0 $$ \returnType{Type: Float} \spadcommand{round(-3.77623)} $$ -{4.0} $$ \returnType{Type: Float} \spadcommand{truncate(9.235)} $$ 9.0 $$ \returnType{Type: Float} \spadcommand{truncate(-9.654)} $$ -{9.0} $$ \returnType{Type: Float} \spadcommand{fractionPart(-3.77623)} $$ -{0.77623} $$ \returnType{Type: Float} \subsection{Useful Functions} To obtain the absolute value of a number the {\bf 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 {\bf sign} function which rturns $-1$, $0$, or $1$ depending on the sign of the argument. \spadcommand{abs(4)} $$ 4 $$ \returnType{Type: PositiveInteger} \spadcommand{abs(-3)} $$ 3 $$ \returnType{Type: PositiveInteger} \spadcommand{abs(-34254.12314)} $$ 34254.12314 $$ \returnType{Type: Float} \spadcommand{sign(-49543.2345346)} $$ -1 $$ \returnType{Type: Integer} \spadcommand{sign(0)} $$ 0 $$ \returnType{Type: NonNegativeInteger} \spadcommand{sign(234235.42354)} $$ 1 $$ \returnType{Type: PositiveInteger} 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: \spadcommand{positive?(-234)} $$ {\tt false} $$ \returnType{Type: Boolean} \spadcommand{negative?(-234)} $$ {\tt true} $$ \returnType{Type: Boolean} \spadcommand{zero?(42)} $$ {\tt false} $$ \returnType{Type: Boolean} \spadcommand{one?(1)} $$ {\tt true} $$ \returnType{Type: Boolean} \spadcommand{odd?(23)} $$ {\tt true} $$ \returnType{Type: Boolean} \spadcommand{odd?(9.435)} $$ {\tt false} $$ \returnType{Type: Boolean} \spadcommand{even?(-42)} $$ {\tt true} $$ \returnType{Type: Boolean} \spadcommand{prime?(37)} $$ {\tt true} $$ \returnType{Type: Boolean} \spadcommand{prime?(-37)} $$ {\tt false} $$ \returnType{Type: Boolean} Some other functions that are quite useful for manipulating numerical values are: \begin{verbatim} 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 \end{verbatim} Some simple infix and prefix operators: \begin{verbatim} + 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 \end{verbatim} Some useful Axiom macros: \begin{verbatim} %i The square root of -1 %e The base of the natural logarithm %pi Pi %infinity Infinity %plusInfinity Positive Infinity %minusInfinity Negative Infinity \end{verbatim} \section{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). \subsection{Expressions Involving Symbols} Expressions involving symbols are entered just as they are written down, for example: \spadcommand{xSquared := x**2} $$ x \sp 2 $$ \returnType{Type: Polynomial Integer} 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 {\tt Polynomial Integer} which is used to represent polynomials with integer coefficients. Some other examples along similar lines are: \spadcommand{xDummy := 3.21*x**2} $$ {3.21} \ {x \sp 2} $$ \returnType{Type: Polynomial Float} \spadcommand{xDummy := x**2.5} $$ {x \sp 2} \ {\sqrt {x}} $$ \returnType{Type: Expression Float} \spadcommand{xDummy := x**3.3} $$ {x \sp 3} \ {{\root {{10}} \of {x}} \sp 3} $$ \returnType{Type: Expression Float} \spadcommand{xyDummy := x**2 - y**2} $$ -{y \sp 2}+{x \sp 2} $$ \returnType{Type: Polynomial Integer} 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 {\bf eval} function which takes an expression as its first argument followed by a list of assignments. For example, to evaluate the expressions {\bf XDummy} and {xyDummy} resulting from their respective assignments above we type: \spadcommand{eval(xDummy,x=3)} $$ 37.5405075985 29552193 $$ \returnType{Type: Expression Float} \spadcommand{eval(xyDummy, [x=3, y=2.1])} $$ 4.59 $$ \returnType{Type: Polynomial Float} \subsection{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 {\bf \%i} macro to represent the square root of $-1$. Thus expressions involving complex numbers are entered just like other expressions. \spadcommand{(2/3 + \%i)**3} $$ -{{46} \over {27}}+{{1 \over 3} \ i} $$ \returnType{Type: Complex Fraction Integer} The real and imaginary parts of a complex number can be extracted using the {\bf real} and {\bf imag} functions and the complex conjugate of a number can be obtained using {\bf conjugate}: \spadcommand{real(3 + 2*\%i)} $$ 3 $$ \returnType{Type: PositiveInteger} \spadcommand{imag(3+ 2*\%i)} $$ 2 $$ \returnType{Type: PositiveInteger} \spadcommand{conjugate(3 + 2*\%i)} $$ 3 -{2 \ i} $$ \returnType{Type: Complex Integer} The function {\bf factor} can also be applied to complex numbers but the results aren't quite so obvious as for factoring integer: \spadcommand{144 + 24*\%i} $$ {144}+{{24} \ i} $$ \returnType{Type: Complex Integer} \subsection{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 {\bf digits} can be called. The result returned by this function is the previous setting. For example, to find the value of $\pi$ to 40 digits we type: \spadcommand{digits(40)} $$ 20 $$ \returnType{Type: PositiveInteger} \spadcommand{\%pi::Float} $$ 3.1415926535\ 8979323846\ 2643383279\ 502884197 $$ \returnType{Type: Float} As can be seen in the example above, there is a gap after every ten digits. This can be changed using the {\bf 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 $0$. Two other functions controlling the appearance of real numbers are {\bf outputFloating} and {\bf 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: \spadcommand{outputFloating(); \%} $$ 0.3141592653 5897932384 6264338327 9502884197 E 1 $$ \returnType{Type: Float} \spadcommand{outputFloating(3); 0.00345} $$ 0.345 E -2 $$ \returnType{Type: Float} \spadcommand{outputFixed(); \%} $$ 0.00345 $$ \returnType{Type: Float} \spadcommand{outputFixed(3); \%} $$ 0.003 $$ \returnType{Type: Float} \spadcommand{outputGeneral(); \%} $$ 0.00345 $$ \returnType{Type: Float} 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 {\bf radix} is used. The first argument of this function is the expression to be displayed and the second is the base to be used. \spadcommand{radix(10**10,32)} $$ {\rm 9A0NP00 } $$ \returnType{Type: RadixExpansion 32} \spadcommand{radix(3/21,5)} $$ 0.{\overline {032412}} $$ \returnType{Type: RadixExpansion 5} Rational numbers can be represented as a repeated decimal expansion using the {\bf decimal} function or as a continued fraction using {\bf continuedFraction}. Any attempt to call these functions with irrational values will fail. \spadcommand{decimal(22/7)} $$ 3.{\overline {142857}} $$ \returnType{Type: DecimalExpansion} \spadcommand{continuedFraction(6543/210)} $$ {31}+ \zag{1}{6}+ \zag{1}{2}+ \zag{1}{1}+ \zag{1}{3} $$ \returnType{Type: ContinuedFraction Integer} Finally, partial fractions in compact and expanded form are available via the functions {\bf partialFraction} and {\bf 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 {\bf compactFraction} does the reverse: \spadcommand{partialFraction(234,40)} $$ 6 -{3 \over {2 \sp 2}}+{3 \over 5} $$ \returnType{Type: PartialFraction Integer} \spadcommand{padicFraction(\%)} $$ 6 -{1 \over 2} -{1 \over {2 \sp 2}}+{3 \over 5} $$ \returnType{Type: PartialFraction Integer} \spadcommand{compactFraction(\%)} $$ 6 -{3 \over {2 \sp 2}}+{3 \over 5} $$ \returnType{Type: PartialFraction Integer} \spadcommand{padicFraction(234/40)} $$ {117} \over {20} $$ \returnType{Type: PartialFraction Fraction Integer} To extract parts of a partial fraction the function {\bf nthFractionalTerm} is available and returns a partial fraction of one term. To decompose this further the numerator can be obtained using {\bf firstNumer} and the denominator with {\bf firstDenom}. The whole part of a partial fraction can be retrieved using {\bf wholePart} and the number of fractional parts can be found using the function {\bf numberOf FractionalTerms}: \spadcommand{t := partialFraction(234,40)} $$ 6 -{3 \over {2 \sp 2}}+{3 \over 5} $$ \returnType{Type: PartialFraction Integer} \spadcommand{wholePart(t)} $$ 6 $$ \returnType{Type: PositiveInteger} \spadcommand{numberOfFractionalTerms(t)} $$ 2 $$ \returnType{Type: PositiveInteger} \spadcommand{p := nthFractionalTerm(t,1)} $$ -{3 \over {2 \sp 2}} $$ \returnType{Type: PartialFraction Integer} \spadcommand{firstNumer(p)} $$ -3 $$ \returnType{Type: Integer} \spadcommand{firstDenom(p)} $$ 2 \sp 2 $$ \returnType{Type: Factored Integer} \subsection{Modular Arithmetic} By using the type constructor {\tt PrimeField} it is possible to do arithmetic modulo some prime number. For example, arithmetic module $7$ can be performed as follows: \spadcommand{x : PrimeField 7 := 5} $$ 5 $$ \returnType{Type: PrimeField 7} \spadcommand{x**5 + 6} $$ 2 $$ \returnType{Type: PrimeField 7} \spadcommand{1/x} $$ 3 $$ \returnType{Type: PrimeField 7} The first example should be read as: \begin{center} {\tt Let $x$ be of type PrimeField(7) and assign to it the value $5$} \end{center} 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 {\tt PrimeField} type constructor with a non-prime argument will generate an error. An example of non-prime modulo arithmetic is: \spadcommand{y : IntegerMod 8 := 11} $$ 3 $$ \returnType{Type: IntegerMod 8} \spadcommand{y*4 + 27} $$ 7 $$ \returnType{Type: IntegerMod 8} Note that polynomials can be constructed in a similar way: \spadcommand{(3*a**4 + 27*a - 36)::Polynomial PrimeField 7} $$ {3 \ {a \sp 4}}+{6 \ a}+6 $$ \returnType{Type: Polynomial PrimeField 7} \section{General Points about Axiom} \subsection{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): \spadcommand{2 + 4*5;} \returnType{Type: PositiveInteger} \subsection{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. \subsection{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 {\bf 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 {\bf 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: \begin{verbatim} 2_ +_ 3 \end{verbatim} $$ 5 $$ \returnType{Type: PositiveInteger} The underscore symbol is an excape character and its presence alters the meaning of the characters that follow it. As mentions above whitespace following an underscore is ignored (the {\bf 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: \spadcommand{ThisIsAVeryLong\_\\ VariableName} $$ ThisIsAVeryLongVariableName $$ \returnType{Type: Variable ThisIsAVeryLongVariableName} \subsection{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 {\bf )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 {\bf 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. \subsection{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: \spadcommand{(2/3)\$Float} $$ 0.6666666666\ 6666666667 $$ \returnType{Type: Float} tells Axiom to use the ``/'' operator from the {\tt Float} package to evaluate the expression $2/3$. This doe 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 {\bf sign} operator is taken from the {\tt Float} package but the result is of type {\tt Integer}. \spadcommand{sign(2.3)\$Float} $$ 1 $$ \returnType{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. \spadcommand{(2 + 3)::String} $$ \mbox{\tt "5"} $$ \returnType{Type: String} \spadcommand{(2 + 3)@String} \begin{verbatim} An expression involving @ String actually evaluated to one of type PositiveInteger . Perhaps you should use :: String . \end{verbatim} \spadcommand{(2 + 3)\$String} \begin{verbatim} The function + is not implemented in String . \end{verbatim} If an expression {\sl X} is converted using one of the three operators to type {\sl T} the interpretations are: {\bf ::} means explicitly convert {\sl X} to type {\sl T} if possible. {\bf \$} means use the available operators for type {\sl T} to compute {\sl X}. {\bf @} means choose operators to compute {\sl X} so that the result is of type {\sl T}. \section{Data Structures in Axiom} This chapter is an overview of {\sl some} of the data structures provided by Axiom. \subsection{Lists} The Axiom {\tt 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 {\bf list} is available: \spadcommand{[4]} $$ \left[ 4 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{list(4)} $$ \left[ 4 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{[1,2,3,5,7,11]} $$ \left[ 1, 2, 3, 5, 7, {11} \right] $$ \returnType{Type: List PositiveInteger} The function {\bf 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 {\bf cons}: \spadcommand{append([1,2,3,5],[7,11])} $$ \left[ 1, 2, 3, 5, 7, {11} \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{cons(23,[65,42,19])} $$ \left[ {23}, {65}, {42}, {19} \right] $$ \returnType{Type: List PositiveInteger} 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 {\bf first} and {\bf rest}. Both of these functions take a second optional argument which specifies the length of the first part of the list: \spadcommand{first([1,5,6,2,3])} $$ 1 $$ \returnType{Type: PositiveInteger} \spadcommand{first([1,5,6,2,3],2)} $$ \left[ 1, 5 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{rest([1,5,6,2,3])} $$ \left[ 5, 6, 2, 3 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{rest([1,5,6,2,3],2)} $$ \left[ 6, 2, 3 \right] $$ \returnType{Type: List PositiveInteger} Other functions are {\bf empty?} which tests to see if a list contains no elements, {\bf member?} which tests to see if the first argument is a member of the second, {\bf reverse} which reverses the order of the list, {\bf sort} which sorts a list, and {\bf removeDuplicates} which removes any duplicates. The length of a list can be obtained using the ``\#'' operator. \spadcommand{empty?([7,2,-1,2])} $$ {\tt false} $$ \returnType{Type: Boolean} \spadcommand{member?(-1,[7,2,-1,2])} $$ {\tt true} $$ \returnType{Type: Boolean} \spadcommand{reverse([7,2,-1,2])} $$ \left[ 2, -1, 2, 7 \right] $$ \returnType{Type: List Integer} \spadcommand{sort([7,2,-1,2])} $$ \left[ -1, 2, 2, 7 \right] $$ \returnType{Type: List Integer} \spadcommand{removeDuplicates([1,5,3,5,1,1,2])} $$ \left[ 1, 5, 3, 2 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{\#[7,2,-1,2]} $$ 4 $$ \returnType{Type: PositiveInteger} 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, {\bf concat!} takes two lists as arguments and appends the second argument to the first (except when the first argument is an empty list) and {\bf setrest!} changes the link emanating from the first argument to point to the second argument: \spadcommand{u := [9,2,4,7]} $$ \left[ 9, 2, 4, 7 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{concat!(u,[1,5,42]); u} $$ \left[ 9, 2, 4, 7, 1, 5, {42} \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{endOfu := rest(u,4)} $$ \left[ 1, 5, {42} \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{partOfu := rest(u,2)} $$ \left[ 4, 7, 1, 5, {42} \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{setrest!(endOfu,partOfu); u} $$ \left[ 9, 2, {\overline {4, 7, 1}} \right] $$ \returnType{Type: List PositiveInteger} From this it can be seen that the lists returned by {\bf first} and {\bf rest} are pointers to the original list and {\sl not} a copy. Thus great care must be taken when dealing with lists in Axiom. Although the {\sl n}th element of the list {\sl l} can be obtained by applying the {\bf first} function to $n-1$ applications of {\bf rest} to {\sl l}, Axiom provides a more useful access method in the form of the ``.'' operator: \spadcommand{u.3} $$ 4 $$ \returnType{Type: PositiveInteger} \spadcommand{u.5} $$ 1 $$ \returnType{Type: PositiveInteger} \spadcommand{u.6} $$ 4 $$ \returnType{Type: PositiveInteger} \spadcommand{first rest rest u -- Same as u.3} $$ 4 $$ \returnType{Type: PositiveInteger} \spadcommand{u.first} $$ 9 $$ \returnType{Type: PositiveInteger} \spadcommand{u(3)} $$ 4 $$ \returnType{Type: PositiveInteger} The operation {\sl u.i} is referred to as {\sl indexing into u} or {\sl elting into u}. The latter term comes from the {\bf elt} function which is used to extract elements (the first element of the list is at index $1$). \spadcommand{elt(u,4)} $$ 7 $$ \returnType{Type: PositiveInteger} 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: \spadcommand{u.3 := 42; u} $$ \left[ 9, 2, {\overline {{42}, 7, 1}} \right] $$ \returnType{Type: List PositiveInteger} Other list operations are: \spadcommand{L := [9,3,4,7]; \#L} $$ 4 $$ \returnType{Type: PositiveInteger} \spadcommand{last(L)} $$ 7 $$ \returnType{Type: PositiveInteger} \spadcommand{L.last} $$ 7 $$ \returnType{Type: PositiveInteger} \spadcommand{L.(\#L - 1)} $$ 4 $$ \returnType{Type: PositiveInteger} Note that using the ``\#'' operator on a list with cycles causes Axiom to enter an infinite loop. Note that any operation on a list {\sl L} that returns a list ${\sl L}L^{'}$ will, in general, be such that any changes to ${\sl L}L^{'}$ will have the side-effect of altering {\sl L}. For example: \spadcommand{m := rest(L,2)} $$ \left[ 4, 7 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{m.1 := 20; L} $$ \left[ 9, 3, {20}, 7 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{n := L} $$ \left[ 9, 3, {20}, 7 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{n.2 := 99; L} $$ \left[ 9, {99}, {20}, 7 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{n} $$ \left[ 9, {99}, {20}, 7 \right] $$ \returnType{Type: List PositiveInteger} Thus the only save way of copying lists is to copy each element from one to another and not use the assignment operator: \spadcommand{p := [i for i in n] -- Same as `p := copy(n)'} $$ \left[ 9, {99}, {20}, 7 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{p.2 := 5; p} $$ \left[ 9, 5, {20}, 7 \right] $$ \returnType{Type: List PositiveInteger} \spadcommand{n} $$ \left[ 9, {99}, {20}, 7 \right] $$ \returnType{Type: List PositiveInteger} 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 \spadcommand{[i for i in 1..10]} $$ \left[ 1, 2, 3, 4, 5, 6, 7, 8, 9, {10} \right] $$ \returnType{Type: List PositiveInteger} should be read as \begin{center} ``Using the expression {\sl i}, generate each element of the list by iterating the symbol {\sl i} over the range of integers [1,10]'' \end{center} To generate the list of the squares of the first ten elements we just use: \spadcommand{[i**2 for i in 1..10]} $$ \left[ 1, 4, 9, {16}, {25}, {36}, {49}, {64}, {81}, {100} \right] $$ \returnType{Type: List PositiveInteger} 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: \spadcommand{[i for i in 1..10 | even?(i)]} $$ \left[ 2, 4, 6, 8, {10} \right] $$ \returnType{Type: List PositiveInteger} This example should be read as: \begin{center} ``Using the expression {\sl i}, generate each element of the list by iterating the symbol {\sl i} over the range of integers [1,10] such that {\sl i} is even'' \end{center} The following achieves the same result: \spadcommand{[i for i in 2..10 by 2]} $$ \left[ 2, 4, 6, 8, {10} \right] $$ \returnType{Type: List PositiveInteger} \subsection{Segmented Lists} A segmented list is one in which some of the elements are ranges of values. The {\bf expand} function converts lists of this type into ordinary lists: \spadcommand{[1..10]} $$ \left[ {1..{10}} \right] $$ \returnType{Type: List Segment PositiveInteger} \spadcommand{[1..3,5,6,8..10]} $$ \left[ {1..3}, {5..5}, {6..6}, {8..{10}} \right] $$ \returnType{Type: List Segment PositiveInteger} \spadcommand{expand(\%)} $$ \left[ 1, 2, 3, 5, 6, 8, 9, {10} \right] $$ \returnType{Type: List Integer} 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): \spadcommand{[1..]} $$ \left[ {1..} \right] $$ \returnType{Type: List UniversalSegment PositiveInteger} \spadcommand{expand(\%)} $$ \left[ 1, 2, 3, 4, 5, 6, 7, 8, 9, {10}, \ldots \right] $$ \returnType{Type: Stream Integer} \subsection{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: \spadcommand{[i for i in 1..]} $$ \left[ 1, 2, 3, 4, 5, 6, 7, 8, 9, {10}, \ldots \right] $$ \returnType{Type: Stream PositiveInteger} \spadcommand{[i for i in 1.. | prime?(i)]} $$ \left[ 2, 3, 5, 7, {11}, {13}, {17}, {19}, {23}, {29}, \ldots \right] $$ \returnType{Type: Stream PositiveInteger} 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 {\bf generate(f,a)} function. This applies its first argument repeatedly onto its second to produce the stream $[a,f(a),f(f(a)),f(f(f(a)))\ldots]$. Given that the function {\bf nextPrime} returns the lowest prime number greater than its argument we can generate a stream of primes as follows: \spadcommand{generate(nextPrime,2)\$Stream Integer} $$ \left[ 2, 3, 5, 7, {11}, {13}, {17}, {19}, {23}, {29}, \ldots \right] $$ \returnType{Type: Stream Integer} As a longer example a stream of Fibonacci numbers will be computed. The Fibonacci numbers start at $1$ and each following number is the addition of the two numbers that precede it so the Fibonacci sequence is: $$1,1,2,3,5,8,\ldots$$. 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 $[1,1]$ 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 $[a,b]$~{\tt ->}~$[b,a+b]$: \spadcommand{win : List Integer -> List Integer} \returnType{Type: Void} \spadcommand{win(x) == [x.2, x.1 + x.2]} \returnType{Type: Void} \spadcommand{win([1,1])} $$ \left[ 1, 2 \right] $$ \returnType{Type: List Integer} \spadcommand{win(\%)} $$ \left[ 2, 3 \right] $$ \returnType{Type: List Integer} Thus it can be seen that repeatedly applying {\bf win} to the {\sl results} of the previous invocation each element of the series is obtained. Clearly {\bf win} is an ideal function to construct streams using the {\bf generate} function: \spadcommand{fibs := [generate(win,[1,1])]} $$ \left[ {\left[ 1, 1 \right]}, {\left[ 1, 2 \right]}, {\left[ 2, 3 \right]}, {\left[ 3, 5 \right]}, {\left[ 5, 8 \right]}, {\left[ 8, {13} \right]}, {\left[ {13}, {21} \right]}, {\left[ {21}, {34} \right]}, {\left[ {34}, {55} \right]}, {\left[ {55}, {89} \right]}, \ldots \right] $$ \returnType{Type: Stream List Integer} This isn't quite what is wanted -- we need to extract the first element of each list and place that in our series: \spadcommand{fibs := [i.1 for i in [generate(win,[1,1])] ]} $$ \left[ 1, 1, 2, 3, 5, 8, {13}, {21}, {34}, {55}, \ldots \right] $$ \returnType{Type: Stream Integer} Obtaining the 200th Fibonacci number is trivial: \spadcommand{fibs.200} $$ 280571172992510140037611932413038677189525 $$ \returnType{Type: PositiveInteger} One other function of interest is {\bf 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. \subsection{Arrays, Vectors, Strings, and Bits} The simplest array data structure is the {\sl one-dimensional array} which can be obtained by applying the {\bf oneDimensionalArray} function to a list: \spadcommand{oneDimensionalArray([7,2,5,4,1,9])} $$ \left[ 7, 2, 5, 4, 1, 9 \right] $$ \returnType{Type: OneDimensionalArray PositiveInteger} 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: \spadcommand{x := oneDimensionalArray([7,2,5,4,1,9])} $$ \left[ 7, 2, 5, 4, 1, 9 \right] $$ \returnType{Type: OneDimensionalArray PositiveInteger} \spadcommand{y := x} $$ \left[ 7, 2, 5, 4, 1, 9 \right] $$ \returnType{Type: OneDimensionalArray PositiveInteger} \spadcommand{y.3 := 20 ; x} $$ \left[ 7, 2, {20}, 4, 1, 9 \right] $$ \returnType{Type: OneDimensionalArray PositiveInteger} Note that because these arrays are of fixed size the {\bf concat!} function cannot be applied to them without generating an error. If arrays of this type are required use the {\bf FlexibleArray} constructor. One-dimensional arrays can be created using {\bf 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 {\bf map!} which applies a mapping onto each element, {\bf swap!} which swaps two elements and {\bf copyInto!(a,b,c)} which copies the array {\sl b} onto {\sl a} starting at position {\sl c}. \spadcommand{a : ARRAY1 PositiveInteger := new(10,3)} $$ \left[ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 \right] $$ \returnType{Type: OneDimensionalArray PositiveInteger} (note that {\tt ARRAY1} is an abbreviation for the type {\tt OneDimensionalArray}.) Other types based on one-dimensional arrays are {\tt Vector}, {\tt String}, and {tt Bits}. \spadcommand{map!(i +-> i+1,a); a} $$ \left[ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 \right] $$ \returnType{Type: OneDimensionalArray PositiveInteger} \spadcommand{b := oneDimensionalArray([2,3,4,5,6])} $$ \left[ 2, 3, 4, 5, 6 \right] $$ \returnType{Type: OneDimensionalArray PositiveInteger} \spadcommand{swap!(b,2,3); b} $$ \left[ 2, 4, 3, 5, 6 \right] $$ \returnType{Type: OneDimensionalArray PositiveInteger} \spadcommand{copyInto!(a,b,3)} $$ \left[ 4, 4, 2, 4, 3, 5, 6, 4, 4, 4 \right] $$ \returnType{Type: OneDimensionalArray PositiveInteger} \spadcommand{a} $$ \left[ 4, 4, 2, 4, 3, 5, 6, 4, 4, 4 \right] $$ \returnType{Type: OneDimensionalArray PositiveInteger} \spadcommand{vector([1/2,1/3,1/14])} $$ \left[ {1 \over 2}, {1 \over 3}, {1 \over {14}} \right] $$ \returnType{Type: Vector Fraction Integer} \spadcommand{"Hello, World"} $$ \mbox{\tt "Hello, World"} $$ \returnType{Type: String} \spadcommand{bits(8,true)} $$ \mbox{\tt "11111111"} $$ \returnType{Type: Bits} A vector is similar to a one-dimensional array except that if its components belong to a ring then arithmetic operations are provided. \subsection{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 {\bf physicalLength} returns the actual length of the array as stored in memory while the {\bf physicalLength!} allows this value to be changed by the user. \spadcommand{f : FARRAY INT := new(6,1)} $$ \left[ 1, 1, 1, 1, 1, 1 \right] $$ \returnType{Type: FlexibleArray Integer} \spadcommand{f.1:=4; f.2:=3 ; f.3:=8 ; f.5:=2 ; f} $$ \left[ 4, 3, 8, 1, 2, 1 \right] $$ \returnType{Type: FlexibleArray Integer} \spadcommand{insert!(42,f,3); f} $$ \left[ 4, 3, {42}, 8, 1, 2, 1 \right] $$ \returnType{Type: FlexibleArray Integer} \spadcommand{insert!(28,f,8); f} $$ \left[ 4, 3, {42}, 8, 1, 2, 1, {28} \right] $$ \returnType{Type: FlexibleArray Integer} \spadcommand{removeDuplicates!(f)} $$ \left[ 4, 3, {42}, 8, 1, 2, {28} \right] $$ \returnType{Type: FlexibleArray Integer} \spadcommand{delete!(f,5)} $$ \left[ 4, 3, {42}, 8, 2, {28} \right] $$ \returnType{Type: FlexibleArray Integer} \spadcommand{g:=f(3..5)} $$ \left[ {42}, 8, 2 \right] $$ \returnType{Type: FlexibleArray Integer} \spadcommand{g.2:=7; f} $$ \left[ 4, 3, {42}, 8, 2, {28} \right] $$ \returnType{Type: FlexibleArray Integer} \spadcommand{insert!(g,f,1)} $$ \left[ {42}, 7, 2, 4, 3, {42}, 8, 2, {28} \right] $$ \returnType{Type: FlexibleArray Integer} \spadcommand{physicalLength(f)} $$ 10 $$ \returnType{Type: PositiveInteger} \spadcommand{physicalLength!(f,20)} $$ \left[ {42}, 7, 2, 4, 3, {42}, 8, 2, {28} \right] $$ \returnType{Type: FlexibleArray Integer} \spadcommand{merge!(sort!(f),sort!(g))} $$ \left[ 2, 2, 2, 3, 4, 7, 7, 8, {28}, {42}, {42}, {42} \right] $$ \returnType{Type: FlexibleArray Integer} \spadcommand{shrinkable(false)\$FlexibleArray(Integer)} $$ {\tt true} $$ \returnType{Type: Boolean} 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 {\sl b.2} above did not alter {\sl a}. Second, the {\bf merge!} function can take an extra argument before the two arrays are merged. The argument is a comparison function and defaults to ``{\tt <=}'' if omitted. Lastly, {\bf 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. \section{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. \subsection{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 {\bf foo.input} you can feed the contents of the file to the command prompt (as though you typed them) by writing: {\bf )read foo.input}. It is good practice to start each input file with the {\bf )clear all} command so that all functions and variables in the current environment are erased. \subsection{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: {\sl BoolExpr}~{\tt =>}~{\sl Expr} where {\sl BoolExpr} is any Axiom expression that has type {\tt Boolean}. The value and type of {\sl 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: $$( expression1 ; expression2; \ldots ; expressionN )$$ 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 {\sl pile}. As an example of a simple block a list of three integers can be constructed using parentheses: \spadcommand{( a:=4; b:=1; c:=9; L:=[a,b,c])} $$ \left[ 4, 1, 9 \right] $$ \returnType{Type: List PositiveInteger} Doing the same thing using piles in an input file you could type: \begin{verbatim} L := a:=4 b:=1 c:=9 [a,b,c] \end{verbatim} $$ \left[ 4, 1, 9 \right] $$ \returnType{Type: List PositiveInteger} 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: \begin{verbatim} sqrt(4.0 + a:=3.0 b:=1.0 c:=a + b c ) \end{verbatim} $$ 2.8284271247\ 461900976 $$ \returnType{Type: Float} Note that indentation is {\bf 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 \begin{verbatim} sqrt(4.0 + a:=3.0 b:=1.0 c:=a + b c) \end{verbatim} \begin{verbatim} 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 \end{verbatim} 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: \begin{verbatim} sqrt(4.0 + a:=3.0 b:=1.0 c:=a + b c ) \end{verbatim} \begin{verbatim} 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 \end{verbatim} a similar error will be raised. Finally, the ``)'' must be indented by at least one space relative to the sqrt thus: \begin{verbatim} sqrt(4.0 + a:=3.0 b:=1.0 c:=a + b c ) \end{verbatim} $$ 2.8284271247\ 461900976 $$ \returnType{Type: Float} 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: \begin{verbatim} a:=3.0 b:=1.0 c:=a + b sqrt(4.0 + c) \end{verbatim} \begin{verbatim} a:=3.0 \end{verbatim} $$ 3.0 $$ \returnType{Type: Float} \begin{verbatim} b:=1.0 \end{verbatim} $$ 1.0 $$ \returnType{Type: Float} \begin{verbatim} c:=a + b \end{verbatim} $$ 4.0 $$ \returnType{Type: Float} \begin{verbatim} sqrt(4.0 + c) \end{verbatim} $$ 2.8284271247\ 461900976 $$ \returnType{Type: Float} 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. \subsection{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 {\sl x} to be of type {\tt Fraction Integer} we enter: \spadcommand{x : Fraction Integer} \returnType{Type: Void} For functions the method is the same except that the arguments are placed in parentheses and the return type is placed after the symbol ``{\tt ->}''. Some examples of function definitions taking zero, one, two, or three arguments and returning a list of integers are: \spadcommand{f : () -> List Integer} \returnType{Type: Void} \spadcommand{g : (Integer) -> List Integer} \returnType{Type: Void} \spadcommand{h : (Integer, Integer) -> List Integer} \returnType{Type: Void} \spadcommand{k : (Integer, Integer, Integer) -> List Integer} \returnType{Type: Void} Now the actual function definitions might be: \spadcommand{f() == [\ ]} \returnType{Type: Void} \spadcommand{g(a) == [a]} \returnType{Type: Void} \spadcommand{h(a,b) == [a,b]} \returnType{Type: Void} \spadcommand{k(a,b,c) == [a,b,c]} \returnType{Type: Void} with some invocations of these functions: \spadcommand{f()} \begin{verbatim} Compiling function f with type () -> List Integer \end{verbatim} $$ \left[\ \right] $$ \returnType{Type: List Integer} \spadcommand{g(4)} \begin{verbatim} Compiling function g with type Integer -> List Integer \end{verbatim} $$ \left[ 4 \right] $$ \returnType{Type: List Integer} \spadcommand{h(2,9)} \begin{verbatim} Compiling function h with type (Integer,Integer) -> List Integer \end{verbatim} $$ \left[ 2, 9 \right] $$ \returnType{Type: List Integer} \spadcommand{k(-3,42,100)} \begin{verbatim} Compiling function k with type (Integer,Integer,Integer) -> List Integer \end{verbatim} $$ \left[ -3, {42}, {100} \right] $$ \returnType{Type: List Integer} The value returned by a function is either the value of the last expression evaluated or the result of a {\bf return} statement. For example, the following are effectively the same: \spadcommand{p : Integer -> Integer} \returnType{Type: Void} \spadcommand{p x == (a:=1; b:=2; a+b+x)} \returnType{Type: Void} \spadcommand{p x == (a:=1; b:=2; return(a+b+x))} \returnType{Type: Void} Note that a block (pile) is assigned to the function identifier {\bf 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 {\bf pile} notation and thus have to use input files to read the piles. \subsection{Choices} Apart from the ``{\tt =>}'' operator that allows a block to exit before the end Axiom provides the standard {\bf if-then-else} construct. The general syntax is: {\center{if {\sl BooleanExpr} then {\sl Expr1} else {\sl Expr2}}} where ``else {\sl Expr2}'' can be omitted. If the expression {\sl BooleanExpr} evaluates to {\tt true} then {\sl Expr1} is executed otherwise {\sl Expr2} (if present) will be executed. An example of piles and {\bf if-then-else} is: (read from an input file) \begin{verbatim} h := 2.0 if h > 3.1 then 1.0 else z:= cos(h) max(x,0.5) \end{verbatim} \begin{verbatim} h := 2.0 \end{verbatim} $$ 2.0 $$ \returnType{Type: Float} \begin{verbatim} if h > 3.1 then 1.0 else z:= cos(h) max(x,0.5) \end{verbatim} $$ x $$ \returnType{Type: Polynomial Float} 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 {\tt Boolean} can be used as {\tt 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 {\bf Boolean} but in those situations when it isn't you may need to use the ``@'' operator to ensure that it is. \subsection{Loops} Loops in Axiom are regarded as expressions containing another expression called the {\sl loop body}. The loop body is executed zero or more times depending on the kind of loop. Loops can be nested to any depth. \subsubsection{The {\tt repeat} loop} The simplest kind of loop provided by Axiom is the {\bf repeat} loop. The general syntax of this is: {\center{{\bf repeat} {\sl loopBody}}} This will cause Axiom to execute {\sl loopBody} repeatedly until either a {\bf break} or {\bf return} statement is encountered. If {\sl loopBody} contains neither of these statements then it will loop forever. The following piece of code will display the numbers from $1$ to $4$: \begin{verbatim} i:=1 repeat if i > 4 then break output(i) i:=i+1 \end{verbatim} \begin{verbatim} i:=1 \end{verbatim} $$ 1 $$ \returnType{Type: PositiveInteger} \begin{verbatim} repeat if i > 4 then break output(i) i:=i+1 1 2 3 4 \end{verbatim} \returnType{Type: Void} It was mentioned that loops will only be left when either a {\bf break} or {\bf return} statement is encountered so why can't one use the ``{\tt =>}'' operator? The reason is that the ``{\tt =>}'' operator tells Axiom to leave the current block whereas {\bf break} leaves the current loop. The {\bf return} statement leave the current function. To skip the rest of a loop body and continue the next iteration of the loop use the {\bf iterate} statement (the -- starts a comment in Axiom) \begin{verbatim} 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) \end{verbatim} \begin{verbatim} i := 0 \end{verbatim} $$ 0 $$ \returnType{Type: NonNegativeInteger} \begin{verbatim} 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 \end{verbatim} \returnType{Type: Void} \subsubsection{The {\tt while} loop} The while statement extends the basic {\bf 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 {\bf repeat} loop, {\bf break} and ``{\tt =>}'' work in the same way as in the previous section. The general syntax of a {\bf while} loop is: {\center{while {\sl BoolExpr} repeat {\sl loopBody}}} As before, {\sl BoolExpr} must be an expression of type {\bf Boolean}. Before the body of the loop is executed {\sl BoolExpr} is tested. If it evaluates to {\tt true} then the loop body is entered otherwise the loop is terminated. Multiple conditions can be applied using the logical operators such as {\bf and} or by using several {\bf while} statements before the {\bf repeat}. \begin{verbatim} x:=1 y:=1 while x < 4 and y < 10 repeat output [x,y] x := x + 1 y := y + 2 \end{verbatim} \begin{verbatim} x:=1 \end{verbatim} $$ 1 $$ \returnType{Type: PositiveInteger} \begin{verbatim} y:=1 \end{verbatim} $$ 1 $$ \returnType{Type: PositiveInteger} \begin{verbatim} while x < 4 and y < 10 repeat output [x,y] x := x + 1 y := y + 2 [1,1] [2,3] [3,5] \end{verbatim} \returnType{Type: Void} \begin{verbatim} x:=1 y:=1 while x < 4 while y < 10 repeat output [x,y] x := x + 1 y := y + 2 \end{verbatim} \begin{verbatim} x:=1 \end{verbatim} $$ 1 $$ \returnType{Type: PositiveInteger} \begin{verbatim} y:=1 \end{verbatim} $$ 1 $$ \returnType{Type: PositiveInteger} \begin{verbatim} while x < 4 while y < 10 repeat output [x,y] x := x + 1 y := y + 2 [1,1] [2,3] [3,5] \end{verbatim} \returnType{Type: Void} Note that the last example using two {\bf while} statements is {\sl not} a nested loop but the following one is: \begin{verbatim} x:=1 y:=1 while x < 4 repeat while y < 10 repeat output [x,y] x := x + 1 y := y + 2 \end{verbatim} \begin{verbatim} x:=1 \begin{verbatim} $$ 1 $$ \returnType{Type: PositiveInteger} \begin{verbatim} y:=1 \end{verbatim} $$ 1 $$ \returnType{Type: PositiveInteger} \begin{verbatim} 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] \end{verbatim} \returnType{Type: Void} 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: \begin{verbatim} 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 \end{verbatim} \begin{verbatim} m := matrix [ [ 21, 37, 53, 14 ],_ [ 8, 22,-24, 16 ],_ [ 2, 10, 15, 14 ],_ [ 26, 33, 55,-13 ] ] \end{verbatim} $$ \left[ \begin{array}{cccc} {21} & {37} & {53} & {14} \\ 8 & {22} & -{24} & {16} \\ 2 & {10} & {15} & {14} \\ {26} & {33} & {55} & -{13} \end{array} \right] $$ \returnType{Type: Matrix Integer} \begin{verbatim} lastrow := nrows(m) \end{verbatim} $$ 4 $$ \returnType{Type: PositiveInteger} \begin{verbatim} lastcol := ncols(m) \end{verbatim} $$ 4 $$ \returnType{Type: PositiveInteger} \begin{verbatim} r := 1 \end{verbatim} $$ 1 $$ \returnType{Type: PositiveInteger} \begin{verbatim} 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] \end{verbatim} \returnType{Type: Void} \subsubsection{The {\tt for} loop} The last loop statement of interest is the {\bf for} loop. There are two ways of creating a {\bf for} loop. The first way uses either a list or a segment: \begin{center} for {\sl var} in {\sl seg} repeat {\sl loopBody}\\ for {\sl var} in {\sl list} repeat {\sl loopBody} \end{center} where {\sl var} is an index variable which is iterated over the values in {\sl seg} or {\sl list}. The value {\sl seg} is a segment such as $1\ldots10$ or $1\ldots$ and {\sl list} is a list of some type. For example: \begin{verbatim} for i in 1..10 repeat ~prime?(i) => iterate output(i) \end{verbatim} \begin{verbatim} for i in 1..10 repeat ~prime?(i) => iterate output(i) 2 3 5 7 \end{verbatim} \returnType{Type: Void} \begin{verbatim} for w in ["This", "is", "your", "life!"] repeat output(w) \end{verbatim} \begin{verbatim} for w in ["This", "is", "your", "life!"] repeat output(w) This is your life! \end{verbatim} \returnType{Type: Void} The second form of the {\bf for} loop syntax includes a ``{\bf such that}'' clause which must be of type {\bf Boolean}: \begin{center} for {\sl var} | {\sl BoolExpr} in {\sl seg} repeat {\sl loopBody}\\ for {\sl var} | {\sl BoolExpr} in {\sl list} repeat {\sl loopBody} \end{center} Some examples are: \begin{verbatim} for i in 1..10 | prime?(i) repeat output(i) \end{verbatim} \begin{verbatim} for i in 1..10 | prime?(i) repeat output(i) 2 3 5 7 \end{verbatim} \returnType{Type: Void} \begin{verbatim} for i in [1,2,3,4,5,6,7,8,9,10] | prime?(i) repeat output(i) \end{verbatim} \begin{verbatim} for i in [1,2,3,4,5,6,7,8,9,10] | prime?(i) repeat output(i) 2 3 5 7 \end{verbatim} \returnType{Type: Void} You can also use a {\bf while} clause: \begin{verbatim} for i in 1.. while i < 7 repeat if even?(i) then output(i) \end{verbatim} \begin{verbatim} for i in 1.. while i < 7 repeat if even?(i) then output(i) 2 4 6 \end{verbatim} \returnType{Type: Void} Using the ``{\bf such that}'' clause makes this appear simpler: \begin{verbatim} for i in 1.. | even?(i) while i < 7 repeat output(i) \{verbatim} \begin{verbatim} for i in 1.. | even?(i) while i < 7 repeat output(i) 2 4 6 \end{verbatim} \returnType{Type: Void} You can use multiple {\bf for} clauses to iterate over several sequences in parallel: \begin{verbatim} for a in 1..4 for b in 5..8 repeat output [a,b] \end{verbatim} \begin{verbatim} for a in 1..4 for b in 5..8 repeat output [a,b] [1,5] [2,6] [3,7] [4,8] \end{verbatim} \returnType{Type: Void} As a general point it should be noted that any symbols referred to in the ``{\bf such that}'' and {\bf 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 {\bf for} clause appearing before the ``{\bf such that}'' or {\bf while}. For example: \begin{verbatim} for a in 1..4 repeat for b in 7..9 | prime?(a+b) repeat output [a,b,a+b] \end{verbatim} \begin{verbatim} 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] \end{verbatim} \returnType{Type: Void} Finally, the {\bf for} statement has a {\bf by} clause to specify the step size. This makes it possible to iterate over the segment in reverse order: \begin{verbatim} for a in 1..4 for b in 8..5 by -1 repeat output [a,b] \end{verbatim} \begin{verbatim} for a in 1..4 for b in 8..5 by -1 repeat output [a,b] [1,8] [2,7] [3,6] [4,5] \end{verbatim} \returnType{Type: Void} Note that without the ``by -1'' the segment 8..5 is empty so there is nothing to iterate over and the loop exits immediately. \setcounter{chapter}{0} % Chapter 1 \hyphenation{ multi-set Uni-var-iate-Poly-nomial Mul-ti-var-iate-Poly-nomial Distributed-Mul-ti-var-iate-Poly-nomial Homo-gen-eous-Distributed-Mul-ti-var-iate-Poly-nomial New-Distributed-Mul-ti-var-iate-Poly-nomial General-Distributed-Mul-ti-var-iate-Poly-nomial } \setcounter{chapter}{1} \chapter{Overview of Interactive Language} \label{ugLang} In this chapter we look at some of the basic components of the Axiom language that you can use interactively. We show how to create a {\it block} of expressions, how to form loops and list iterations, how to modify the sequential evaluation of a block and how to use {\tt if-then-else} to evaluate parts of your program conditionally. We suggest you first read the boxed material in each section and then proceed to a more thorough reading of the chapter. \section{Immediate and Delayed Assignments} \label{ugLangAssign} A {\it variable} in Axiom refers to a value. A variable has a name beginning with an uppercase or lowercase alphabetic character, ``{\tt \%}'', or ``{\tt !}''. Successive characters (if any) can be any of the above, digits, or ``{\tt ?}''. Case is distinguished. The following are all examples of valid, distinct variable names: \begin{verbatim} a tooBig? a1B2c3%!? A %j numberOfPoints beta6 %J numberofpoints \end{verbatim} The ``{\tt :=}'' operator is the immediate {\it assignment} operator. \index{assignment!immediate} Use it to associate a value with a variable. \index{immediate assignment} \boxed{4.6in}{ \vskip 0.1cm The syntax for immediate assignment for a single variable is \begin{center} {\it variable} $:=$ {\it expression} \end{center} The value returned by an immediate assignment is the value of {\it expression}.\\ } The right-hand side of the expression is evaluated, yielding $1$. This value is then assigned to $a$. \spadcommand{a := 1} $$ 1 $$ \returnType{Type: PositiveInteger} The right-hand side of the expression is evaluated, yielding $1$. This value is then assigned to $b$. Thus $a$ and $b$ both have the value $1$ after the sequence of assignments. \spadcommand{b := a} $$ 1 $$ \returnType{Type: PositiveInteger} What is the value of $b$ if $a$ is assigned the value $2$? \spadcommand{a := 2} $$ 2 $$ \returnType{Type: PositiveInteger} As you see, the value of $b$ is left unchanged. \spadcommand{b} $$ 1 $$ \returnType{Type: PositiveInteger} This is what we mean when we say this kind of assignment is {\it immediate}; $b$ has no dependency on $a$ after the initial assignment. This is the usual notion of assignment found in programming languages such as C, \index{C language!assignment} PASCAL \index{PASCAL!assignment} and FORTRAN. \index{FORTRAN!assignment} Axiom provides delayed assignment with ``{\tt ==}''. \index{assignment!delayed} This implements a \index{delayed assignment} delayed evaluation of the right-hand side and dependency checking. \boxed{4.6in}{ \vskip 0.1cm The syntax for delayed assignment is \begin{center} {\it variable} $==$ {\it expression} \end{center} The value returned by a delayed assignment is the unique value of {\tt Void}.\\ } Using $a$ and $b$ as above, these are the corresponding delayed assignments. \spadcommand{a == 1} \returnType{Type: Void} \spadcommand{b == a} \returnType{Type: Void} The right-hand side of each delayed assignment is left unevaluated until the variables on the left-hand sides are evaluated. Therefore this evaluation and \ldots \spadcommand{a} \begin{verbatim} Compiling body of rule a to compute value of type PositiveInteger \end{verbatim} $$ 1 $$ \returnType{Type: PositiveInteger} this evaluation seem the same as before. \spadcommand{b} \begin{verbatim} Compiling body of rule b to compute value of type PositiveInteger \end{verbatim} $$ 1 $$ \returnType{Type: PositiveInteger} If we change $a$ to $2$ \spadcommand{a == 2} \begin{verbatim} Compiled code for a has been cleared. Compiled code for b has been cleared. 1 old definition(s) deleted for function or rule a \end{verbatim} \returnType{Type: Void} then $a$ evaluates to $2$, as expected, but \spadcommand{a} \begin{verbatim} Compiling body of rule a to compute value of type PositiveInteger +++ |*0;a;1;G82322| redefined \end{verbatim} $$ 2 $$ \returnType{Type: PositiveInteger} the value of $b$ reflects the change to $a$. \spadcommand{b} \begin{verbatim} Compiling body of rule b to compute value of type PositiveInteger +++ |*0;b;1;G82322| redefined \end{verbatim} $$ 2 $$ \returnType{Type: PositiveInteger} It is possible to set several variables at the same time \index{assignment!multiple immediate} by using \index{multiple immediate assignment} a {\it tuple} of variables and a tuple of expressions. Note that a {\it tuple} is a collection of things separated by commas, often surrounded by parentheses. \boxed{4.6in}{ \vskip 0.1cm The syntax for multiple immediate assignments is \begin{center} {\tt ( $\hbox{\it var}_{1}$, $\hbox{\it var}_{2}$, \ldots, $\hbox{\it var}_{N}$ ) := ( $\hbox{\it expr}_{1}$, $\hbox{\it expr}_{2}$, \ldots, $\hbox{\it expr}_{N}$ ) } \end{center} The value returned by an immediate assignment is the value of $\hbox{\it expr}_{N}$.\\ } This sets $x$ to $1$ and $y$ to $2$. \spadcommand{(x,y) := (1,2)} $$ 2 $$ \returnType{Type: PositiveInteger} Multiple immediate assigments are parallel in the sense that the expressions on the right are all evaluated before any assignments on the left are made. However, the order of evaluation of these expressions is undefined. You can use multiple immediate assignment to swap the values held by variables. \spadcommand{(x,y) := (y,x)} $$ 1 $$ \returnType{Type: PositiveInteger} $x$ has the previous value of $y$. \spadcommand{x} $$ 2 $$ \returnType{Type: PositiveInteger} $y$ has the previous value of $x$. \spadcommand{y} $$ 1 $$ \returnType{Type: PositiveInteger} There is no syntactic form for multiple delayed assignments. See the discussion in section \ref{ugUserDelay} on page~\pageref{ugUserDelay} about how Axiom differentiates between delayed assignments and user functions of no arguments. \section{Blocks} \label{ugLangBlocks} A {\it block} is a sequence of expressions evaluated in the order that they appear, except as modified by control expressions such as {\tt break}, \index{break} {\tt return}, \index{return} {\tt iterate} and \index{iterate} {\tt if-then-else} constructions. The value of a block is the value of the expression last evaluated in the block. To leave a block early, use ``{\tt =>}''. For example, $i < 0 => x$. The expression before the ``{\tt =>}'' must evaluate to {\tt true} or {\tt false}. The expression following the ``{\tt =>}'' is the return value for the block. A block can be constructed in two ways: \begin{enumerate} \item the expressions can be separated by semicolons and the resulting expression surrounded by parentheses, and \item the expressions can be written on succeeding lines with each line indented the same number of spaces (which must be greater than zero). \index{indentation} A block entered in this form is called a {\it pile}. \end{enumerate} Only the first form is available if you are entering expressions directly to Axiom. Both forms are available in {\bf .input} files. \boxed{4.6in}{ \vskip 0.1cm The syntax for a simple block of expressions entered interactively is \begin{center} {\tt ( $\hbox{\it expression}_{1}$; $\hbox{\it expression}_{2}$; \ldots; $\hbox{\it expression}_{N}$ )} \end{center} The value returned by a block is the value of an {\tt =>} expression, or $\hbox{\it expression}_{N}$ if no {\tt =>} is encountered.\\ } In {\bf .input} files, blocks can also be written using piles. The examples throughout this book are assumed to come from {\bf .input} files. In this example, we assign a rational number to $a$ using a block consisting of three expressions. This block is written as a pile. Each expression in the pile has the same indentation, in this case two spaces to the right of the first line. \begin{verbatim} a := i := gcd(234,672) i := 3*i**5 - i + 1 1 / i \end{verbatim} $$ 1 \over {23323} $$ \returnType{Type: Fraction Integer} Here is the same block written on one line. This is how you are required to enter it at the input prompt. \spadcommand{a := (i := gcd(234,672); i := 3*i**5 - i + 1; 1 / i)} $$ 1 \over {23323} $$ \returnType{Type: Fraction Integer} Blocks can be used to put several expressions on one line. The value returned is that of the last expression. \spadcommand{(a := 1; b := 2; c := 3; [a,b,c])} $$ \left[ 1, 2, 3 \right] $$ \returnType{Type: List PositiveInteger} Axiom gives you two ways of writing a block and the preferred way in an {\bf .input} file is to use a pile. \index{file!input} Roughly speaking, a pile is a block whose constituent expressions are indented the same amount. You begin a pile by starting a new line for the first expression, indenting it to the right of the previous line. You then enter the second expression on a new line, vertically aligning it with the first line. And so on. If you need to enter an inner pile, further indent its lines to the right of the outer pile. Axiom knows where a pile ends. It ends when a subsequent line is indented to the left of the pile or the end of the file. Blocks can be used to perform several steps before an assignment (immediate or delayed) is made. \begin{verbatim} d := c := a**2 + b**2 sqrt(c * 1.3) \end{verbatim} $$ 2.5495097567 96392415 $$ \returnType{Type: Float} Blocks can be used in the arguments to functions. (Here $h$ is assigned $2.1 + 3.5$.) \begin{verbatim} h := 2.1 + 1.0 3.5 \end{verbatim} $$ 5.6 $$ \returnType{Type: Float} Here the second argument to {\bf eval} is $x = z$, where the value of $z$ is computed in the first line of the block starting on the second line. \begin{verbatim} eval(x**2 - x*y**2, z := %pi/2.0 - exp(4.1) x = z ) \end{verbatim} $$ {{58.7694912705 67072878} \ {y \sp 2}}+{3453.8531042012 59382} $$ \returnType{Type: Polynomial Float} Blocks can be used in the clauses of {\tt if-then-else} expressions (see \ref{ugLangIf} on page~\pageref{ugLangIf}). \spadcommand{if h > 3.1 then 1.0 else (z := cos(h); max(z,0.5))} $$ 1.0 $$ \returnType{Type: Float} This is the pile version of the last block. \begin{verbatim} if h > 3.1 then 1.0 else z := cos(h) max(z,0.5) \end{verbatim} $$ 1.0 $$ \returnType{Type: Float} Blocks can be nested. \spadcommand{a := (b := factorial(12); c := (d := eulerPhi(22); factorial(d));b+c)} $$ 482630400 $$ \returnType{Type: PositiveInteger} This is the pile version of the last block. \begin{verbatim} a := b := factorial(12) c := d := eulerPhi(22) factorial(d) b+c \end{verbatim} $$ 482630400 $$ \returnType{Type: PositiveInteger} Since $c + d$ does equal $3628855$, $a$ has the value of $c$ and the last line is never evaluated. \begin{verbatim} a := c := factorial 10 d := fibonacci 10 c + d = 3628855 => c d \end{verbatim} $$ 3628800 $$ \returnType{Type: PositiveInteger} \section{if-then-else} \label{ugLangIf} Like many other programming languages, Axiom uses the three keywords \index{if} {\tt if}, {\tt then} \index{then} and {\tt else} \index{else} to form \index{conditional} conditional expressions. The {\tt else} part of the conditional is optional. The expression between the {\tt if} and {\tt then} keywords is a {\it predicate}: an expression that evaluates to or is convertible to either {\tt true} or {\tt false}, that is, a {\tt Boolean}. \index{Boolean} \boxed{4.6in}{ \vskip 0.1cm The syntax for conditional expressions is \begin{center} {\tt if\ }{\it predicate} {\tt then\ }$\hbox{\it expression}_{1}$ {\tt else\ }$\hbox{\it expression}_{2}$ \end{center} where the {\tt else} $\hbox{\it expression}_{2}$ part is optional. The value returned from a conditional expression is $\hbox{\it expression}_{1}$ if the predicate evaluates to {\tt true} and $\hbox{\it expression}_{2}$ otherwise. If no {\tt else} clause is given, the value is always the unique value of {\tt Void}.\\ } An {\tt if-then-else} expression always returns a value. If the {\tt else} clause is missing then the entire expression returns the unique value of {\tt Void}. If both clauses are present, the type of the value returned by {\tt if} is obtained by resolving the types of the values of the two clauses. See \ref{ugTypesResolve} on page~\pageref{ugTypesResolve} for more information. The predicate must evaluate to, or be convertible to, an object of type {\tt Boolean}: {\tt true} or {\tt false}. By default, the equal sign \spadopFrom{=}{Equation} creates \index{equation} an equation. This is an equation. \index{Equation} In particular, it is an object of type {\tt Equation Polynomial Integer}. \spadcommand{x + 1 = y} $$ {x+1}=y $$ \returnType{Type: Equation Polynomial Integer} However, for predicates in {\tt if} expressions, Axiom \index{equality testing} places a default target type of {\tt Boolean} on the predicate and equality testing is performed. \index{Boolean} Thus you need not qualify the ``{\tt =}'' in any way. In other contexts you may need to tell Axiom that you want to test for equality rather than create an equation. In those cases, use ``{\tt @}'' and a target type of {\tt Boolean}. See section \ref{ugTypesPkgCall} on page~\pageref{ugTypesPkgCall} for more information. The compound symbol meaning ``not equal'' in Axiom is \index{inequality testing} ``{$\sim =$}''. \index{\_notequal@$\sim =$} This can be used directly without a package call or a target specification. The expression $a$~$\sim =$~$b$ is directly translated into {\tt not}$(a = b)$. Many other functions have return values of type {\tt Boolean}. These include ``{\tt <}'', ``{\tt <=}'', ``{\tt >}'', ``{\tt >=}'', ``{\tt $\sim$=}'' and ``{\bf member?}''. By convention, operations with names ending in ``{\tt ?}'' return {\tt Boolean} values. The usual rules for piles are suspended for conditional expressions. In {\bf .input} files, the {\tt then} and {\tt else} keywords can begin in the same column as the corresponding {\tt if} but may also appear to the right. Each of the following styles of writing {\tt if-then-else} expressions is acceptable: \begin{verbatim} if i>0 then output("positive") else output("nonpositive") if i > 0 then output("positive") else output("nonpositive") if i > 0 then output("positive") else output("nonpositive") if i > 0 then output("positive") else output("nonpositive") if i > 0 then output("positive") else output("nonpositive") \end{verbatim} A block can follow the {\tt then} or {\tt else} keywords. In the following two assignments to {\tt a}, the {\tt then} and {\tt else} clauses each are followed by two-line piles. The value returned in each is the value of the second line. \begin{verbatim} a := if i > 0 then j := sin(i * pi()) exp(j + 1/j) else j := cos(i * 0.5 * pi()) log(abs(j)**5 + 1) a := if i > 0 then j := sin(i * pi()) exp(j + 1/j) else j := cos(i * 0.5 * pi()) log(abs(j)**5 + 1) \end{verbatim} These are both equivalent to the following: \begin{verbatim} a := if i > 0 then (j := sin(i * pi()); exp(j + 1/j)) else (j := cos(i * 0.5 * pi()); log(abs(j)**5 + 1)) \end{verbatim} \section{Loops} \label{ugLangLoops} A {\it loop} is an expression that contains another expression, \index{loop} called the {\it loop body}, which is to be evaluated zero or more \index{loop!body} times. All loops contain the {\tt repeat} keyword and return the unique value of {\tt Void}. Loops can contain inner loops to any depth. \boxed{4.6in}{ \vskip 0.1cm The most basic loop is of the form \begin{center} {\tt repeat\ }{\it loopBody} \end{center} Unless {\it loopBody} contains a {\tt break} or {\tt return} expression, the loop repeats forever. The value returned by the loop is the unique value of {\tt Void}.\\ } \subsection{Compiling vs. Interpreting Loops} \label{ugLangLoopsCompInt} Axiom tries to determine completely the type of every object in a loop and then to translate the loop body to LISP or even to machine code. This translation is called compilation. If Axiom decides that it cannot compile the loop, it issues a \index{loop!compilation} message stating the problem and then the following message: \begin{center} {\bf We will attempt to step through and interpret the code.} \end{center} It is still possible that Axiom can evaluate the loop but in {\it interpret-code mode}. See section \ref{ugUserCompInt} on page~\pageref{ugUserCompInt} where this is discussed in terms \index{panic!avoiding} of compiling versus interpreting functions. \subsection{return in Loops} \label{ugLangLoopsReturn} A {\tt return} expression is used to exit a function with \index{loop!leaving via return} a particular value. In particular, if a {\tt return} is in a loop within the \index{return} function, the loop is terminated whenever the {\tt return} is evaluated. %> This is a bug! The compiler should never accept allow %> Void to be the return type of a function when it has to use %> resolve to determine it. Suppose we start with this. \begin{verbatim} f() == i := 1 repeat if factorial(i) > 1000 then return i i := i + 1 \end{verbatim} \returnType{Type: Void} When {\tt factorial(i)} is big enough, control passes from inside the loop all the way outside the function, returning the value of $i$ (or so we think). \spadcommand{f()} \returnType{Type: Void} What went wrong? Isn't it obvious that this function should return an integer? Well, Axiom makes no attempt to analyze the structure of a loop to determine if it always returns a value because, in general, this is impossible. So Axiom has this simple rule: the type of the function is determined by the type of its body, in this case a block. The normal value of a block is the value of its last expression, in this case, a loop. And the value of every loop is the unique value of {\tt Void}.! So the return type of {\bf f} is {\tt Void}. There are two ways to fix this. The best way is for you to tell Axiom what the return type of $f$ is. You do this by giving $f$ a declaration {\tt f:()~->~Integer} prior to calling for its value. This tells Axiom: ``trust me---an integer is returned.'' We'll explain more about this in the next chapter. Another clumsy way is to add a dummy expression as follows. Since we want an integer, let's stick in a dummy final expression that is an integer and will never be evaluated. \begin{verbatim} f() == i := 1 repeat if factorial(i) > 1000 then return i i := i + 1 0 \end{verbatim} \returnType{Type: Void} When we try {\bf f} again we get what we wanted. See \ref{ugUserBlocks} on page~\pageref{ugUserBlocks} for more information. \spadcommand{f()} \begin{verbatim} Compiling function f with type () -> NonNegativeInteger \end{verbatim} $$ 7 $$ \returnType{Type: PositiveInteger} \subsection{break in Loops} \label{ugLangLoopsBreak} The {\tt break} keyword is often more useful \index{break} in terminating \index{loop!leaving via break} a loop. A {\tt break} causes control to transfer to the expression immediately following the loop. As loops always return the unique value of {\tt Void}., you cannot return a value with {\tt break}. That is, {\tt break} takes no argument. This example is a modification of the last example in the previous section \ref{ugLangLoopsReturn} on page~\pageref{ugLangLoopsReturn}. Instead of using {\tt return}, we'll use {\tt break}. \begin{verbatim} f() == i := 1 repeat if factorial(i) > 1000 then break i := i + 1 i \end{verbatim} \begin{verbatim} Compiled code for f has been cleared. 1 old definition(s) deleted for function or rule f \end{verbatim} \returnType{Type: Void} The loop terminates when {\tt factorial(i)} gets big enough, the last line of the function evaluates to the corresponding ``good'' value of $i$, and the function terminates, returning that value. \spadcommand{f()} \begin{verbatim} Compiling function f with type () -> PositiveInteger +++ |*0;f;1;G82322| redefined \end{verbatim} $$ 7 $$ \returnType{Type: PositiveInteger} You can only use {\tt break} to terminate the evaluation of one loop. Let's consider a loop within a loop, that is, a loop with a nested loop. First, we initialize two counter variables. \spadcommand{(i,j) := (1, 1)} $$ 1 $$ \returnType{Type: PositiveInteger} Nested loops must have multiple {\tt break} \index{loop!nested} expressions at the appropriate nesting level. How would you rewrite this so {\tt (i + j) > 10} is only evaluated once? \begin{verbatim} repeat repeat if (i + j) > 10 then break j := j + 1 if (i + j) > 10 then break i := i + 1 \end{verbatim} \returnType{Type: Void} \subsection{break vs. {\tt =>} in Loop Bodies} \label{ugLangLoopsBreakVs} Compare the following two loops: \begin{verbatim} i := 1 i := 1 repeat repeat i := i + 1 i := i + 1 i > 3 => i if i > 3 then break output(i) output(i) \end{verbatim} In the example on the left, the values $2$ and $3$ for $i$ are displayed but then the ``{\tt =>}'' does not allow control to reach the call to \spadfunFrom{output}{OutputForm} again. The loop will not terminate until you run out of space or interrupt the execution. The variable $i$ will continue to be incremented because the ``{\tt =>}'' only means to leave the {\it block}, not the loop. In the example on the right, upon reaching $4$, the {\tt break} will be executed, and both the block and the loop will terminate. This is one of the reasons why both ``{\tt =>}'' and {\tt break} are provided. Using a {\tt while} clause (see below) with the ``{\tt =>}'' \index{while} lets you simulate the action of {\tt break}. \subsection{More Examples of break} \label{ugLangLoopsBreakMore} Here we give four examples of {\tt repeat} loops that terminate when a value exceeds a given bound. First, initialize $i$ as the loop counter. \spadcommand{i := 0} $$ 0 $$ \returnType{Type: NonNegativeInteger} Here is the first loop. When the square of $i$ exceeds $100$, the loop terminates. \begin{verbatim} repeat i := i + 1 if i**2 > 100 then break \end{verbatim} \returnType{Type: Void} Upon completion, $i$ should have the value $11$. \spadcommand{i} $$ 11 $$ \returnType{Type: NonNegativeInteger} Do the same thing except use ``{\tt =>}'' instead an {\tt if-then} expression. \spadcommand{i := 0} $$ 0 $$ \returnType{Type: NonNegativeInteger} \begin{verbatim} repeat i := i + 1 i**2 > 100 => break \end{verbatim} \returnType{Type: Void} \spadcommand{i} $$ 11 $$ \returnType{Type: NonNegativeInteger} As a third example, we use a simple loop to compute $n!$. \spadcommand{(n, i, f) := (100, 1, 1)} $$ 1 $$ \returnType{Type: PositiveInteger} Use $i$ as the iteration variable and $f$ to compute the factorial. \begin{verbatim} repeat if i > n then break f := f * i i := i + 1 \end{verbatim} \returnType{Type: Void} Look at the value of $f$. \spadcommand{f} \begin{verbatim} 93326215443944152681699238856266700490715968264381621468_ 59296389521759999322991560894146397615651828625369792082_ 7223758251185210916864000000000000000000000000 \end{verbatim} \returnType{Type: PositiveInteger} Finally, we show an example of nested loops. First define a four by four matrix. \spadcommand{m := matrix [ [21,37,53,14], [8,-24,22,-16], [2,10,15,14], [26,33,55,-13] ]} $$ \left[ \begin{array}{cccc} {21} & {37} & {53} & {14} \\ 8 & -{24} & {22} & -{16} \\ 2 & {10} & {15} & {14} \\ {26} & {33} & {55} & -{13} \end{array} \right] $$ \returnType{Type: Matrix Integer} Next, set row counter $r$ and column counter $c$ to $1$. Note: if we were writing a function, these would all be local variables rather than global workspace variables. \spadcommand{(r, c) := (1, 1)} $$ 1 $$ \returnType{Type: PositiveInteger} Also, let {\tt lastrow} and {\tt lastcol} be the final row and column index. \spadcommand{(lastrow, lastcol) := (nrows(m), ncols(m))} $$ 4 $$ \returnType{Type: PositiveInteger} Scan the rows looking for the first negative element. We remark that you can reformulate this example in a better, more concise form by using a {\tt for} clause with {\tt repeat}. See \ref{ugLangLoopsForIn} on page~\pageref{ugLangLoopsForIn} for more information. \begin{verbatim} repeat if r > lastrow then break c := 1 repeat if c > lastcol then break 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,2,- 24] \end{verbatim} \returnType{Type: Void} \subsection{iterate in Loops} \label{ugLangLoopsIterate} Axiom provides an {\tt iterate} expression that \index{iterate} skips over the remainder of a loop body and starts the next loop iteration. We first initialize a counter. \spadcommand{i := 0} $$ 0 $$ \returnType{Type: NonNegativeInteger} Display the even integers from $2$ to $5$. \begin{verbatim} repeat i := i + 1 if i > 5 then break if odd?(i) then iterate output(i) 2 4 \end{verbatim} \returnType{Type: Void} \subsection{while Loops} \label{ugLangLoopsWhile} The {\tt repeat} in a loop can be modified by adding one or more {\tt while} clauses. \index{while} Each clause contains a {\it predicate} immediately following the {\tt while} keyword. The predicate is tested {\it before} the evaluation of the body of the loop. The loop body is evaluated whenever the predicates in a {\tt while} clause are all {\tt true}. \boxed{4.6in}{ \vskip 0.1cm The syntax for a simple loop using {\tt while} is \begin{center} {\tt while} {\it predicate} {\tt repeat} {\it loopBody} \end{center} The {\it predicate} is evaluated before {\it loopBody} is evaluated. A {\tt while} loop terminates immediately when {\it predicate} evaluates to {\tt false} or when a {\tt break} or {\tt return} expression is evaluated in {\it loopBody}. The value returned by the loop is the unique value of {\tt Void}.\\ } Here is a simple example of using {\tt while} in a loop. We first initialize the counter. \spadcommand{i := 1} $$ 1 $$ \returnType{Type: PositiveInteger} The steps involved in computing this example are\\ (1) set $i$ to $1$,\\ (2) test the condition $i < 1$ and determine that it is not {\tt true}, and\\ (3) do not evaluate the loop body and therefore do not display $"hello"$. \begin{verbatim} while i < 1 repeat output "hello" i := i + 1 \end{verbatim} \returnType{Type: Void} If you have multiple predicates to be tested use the logical {\tt and} operation to separate them. Axiom evaluates these predicates from left to right. \spadcommand{(x, y) := (1, 1)} $$ 1 $$ \returnType{Type: PositiveInteger} \begin{verbatim} while x < 4 and y < 10 repeat output [x,y] x := x + 1 y := y + 2 [1,1] [2,3] [3,5] \end{verbatim} \returnType{Type: Void} A {\tt break} expression can be included in a loop body to terminate a loop even if the predicate in any {\tt while} clauses are not {\tt false}. \spadcommand{(x, y) := (1, 1)} $$ 1 $$ \returnType{Type: PositiveInteger} This loop has multiple {\tt while} clauses and the loop terminates