% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\texht{\setcounter{chapter}{5}}{} % Chapter 6

\newcommand{\pred}[1]{\subscriptIt{pred}{#1}}
\newcommand{\expr}[1]{\subscriptIt{expression}{#1}}

%
\newcommand{\ugUserTitle}{User-Defined Functions, Macros and Rules}
\newcommand{\ugUserNumber}{6.}
%
% =====================================================================
\begin{page}{ugUserPage}{6. User-Defined Functions, Macros and Rules}
% =====================================================================
\beginscroll

In this chapter we show you how to write functions and macros,
and we explain how \Language{} looks for and applies them.
We show some simple one-line examples of functions, together
with larger ones that are defined piece-by-piece or through the use of
piles.

\beginmenu
    \menudownlink{{6.1. Functions vs. Macros}}{ugUserFunMacPage}
    \menudownlink{{6.2. Macros}}{ugUserMacrosPage}
    \menudownlink{{6.3. Introduction to Functions}}{ugUserIntroPage}
    \menudownlink{{6.4. Declaring the Type of Functions}}{ugUserDeclarePage}
    \menudownlink{{6.5. One-Line Functions}}{ugUserOnePage}
    \menudownlink{{6.6. Declared vs. Undeclared Functions}}{ugUserDecUndecPage}
    \menudownlink{{6.7. Functions vs. Operations}}{ugUserDecOpersPage}
    \menudownlink{{6.8. Delayed Assignments vs. Functions with No Arguments}}{ugUserDelayPage}
    \menudownlink{{6.9. How \Language{} Determines What Function to Use}}{ugUserUsePage}
    \menudownlink{{6.10. Compiling vs. Interpreting}}{ugUserCompIntPage}
    \menudownlink{{6.11. Piece-Wise Function Definitions}}{ugUserPiecePage}
    \menudownlink{{6.12. Caching Previously Computed Results}}{ugUserCachePage}
    \menudownlink{{6.13. Recurrence Relations}}{ugUserRecurPage}
    \menudownlink{{6.14. Making Functions from Objects}}{ugUserMakePage}
    \menudownlink{{6.15. Functions Defined with Blocks}}{ugUserBlocksPage}
    \menudownlink{{6.16. Free and Local Variables}}{ugUserFreeLocalPage}
    \menudownlink{{6.17. Anonymous Functions}}{ugUserAnonPage}
    \menudownlink{{6.18. Example: A Database}}{ugUserDatabasePage}
    \menudownlink{{6.19. Example: A Famous Triangle}}{ugUserTrianglePage}
    \menudownlink{{6.20. Example: Testing for Palindromes}}{ugUserPalPage}
    \menudownlink{{6.21. Rules and Pattern Matching}}{ugUserRulesPage}
\endmenu
\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserFunMacTitle}{Functions vs. Macros}
\newcommand{\ugUserFunMacNumber}{6.1.}
%
% =====================================================================
\begin{page}{ugUserFunMacPage}{6.1. Functions vs. Macros}
% =====================================================================
\beginscroll

A function is a program to perform some
%-% \HDindex{function!vs. macro}{ugUserFunMacPage}{6.1.}{Functions vs. Macros}
computation.
%-% \HDindex{macro!vs. function}{ugUserFunMacPage}{6.1.}{Functions vs. Macros}
Most functions have names so that it is easy to refer to them.
A simple example of a function is one named
\axiomFunFrom{abs}{Integer} which
computes the absolute value of an integer.
%
\xtc{
This is a use of the ``absolute value'' library function for integers.
}{
\spadpaste{abs(-8)}
}
\xtc{
This is an unnamed function that does the same thing, using the
``maps-to'' syntax \axiomSyntax{+->} that we discuss in
\downlink{``\ugUserAnonTitle''}{ugUserAnonPage} in Section \ugUserAnonNumber\ignore{ugUserAnon}.
}{
\spadpaste{(x +-> if x < 0 then -x else x)(-8)}
}
%
Functions can be used alone or serve as the building blocks for larger
programs.
Usually they return a value that you might want to use in the next stage
of a computation, but not always (for example, see
\downlink{`Exit'}{ExitXmpPage}\ignore{Exit} and \downlink{`Void'}{VoidXmpPage}\ignore{Void}).
They may also read data from your keyboard, move information from one
place to another, or format and display results on your screen.

In \Language{}, as in mathematics, functions
%-% \HDindex{function!parameters}{ugUserFunMacPage}{6.1.}{Functions vs. Macros}
are usually \spadglossSee{parameterized}{parameterized form}.
Each time you {\it call} (some people say \spadgloss{apply} or
\spadglossSee{invoke}{invocation}) a function, you give
%-% \HDindex{parameters to a function}{ugUserFunMacPage}{6.1.}{Functions vs. Macros}
values to the parameters (variables).
Such a value is called an \spadgloss{argument} of
%-% \HDindex{function!arguments}{ugUserFunMacPage}{6.1.}{Functions vs. Macros}
the function.
\Language{} uses the arguments for the computation.
In this way you get different results depending on what you ``feed'' the
function.

Functions can have local variables or refer to global variables in the
workspace.
\Language{} can often \spadglossSee{compile}{compiler} functions so that
they execute very efficiently.
Functions can be passed as arguments to other functions.

Macros are textual substitutions.
They are used to clarify the meaning of constants or expressions and to be
templates for frequently used expressions.
Macros can be parameterized but they are not objects that can be passed as
arguments to functions.
In effect, macros are extensions to the \Language{} expression parser.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserMacrosTitle}{Macros}
\newcommand{\ugUserMacrosNumber}{6.2.}
%
% =====================================================================
\begin{page}{ugUserMacrosPage}{6.2. Macros}
% =====================================================================
\beginscroll

A \spadgloss{macro} provides general textual substitution of
%-% \HDindex{macro}{ugUserMacrosPage}{6.2.}{Macros}
an \Language{} expression for a name.
You can think of a macro as being a generalized abbreviation.
You can only have one macro in your workspace with
a given name, no matter how many arguments it has.

\beginImportant
The two general forms for macros are
\centerline{{{\tt macro} {\it name} {\tt ==} {\it body} }}
\centerline{{{\tt macro} {\it name(arg1,...)} {\tt ==} {\it body}}}
where the body of the macro can be any \Language{} expression.
\endImportant

%
\xtc{
For example, suppose you decided that you
like to use \axiom{df} for \axiomFun{D}.
You define the macro \axiom{df} like this.
}{
\spadpaste{macro df == D \bound{df}}
}
\xtc{
Whenever you type \axiom{df}, the system expands it to
\axiomFun{D}.
}{
\spadpaste{df(x**2 + x + 1,x) \free{df}}
}
\xtc{
Macros can be parameterized and so can be used for many different
kinds of objects.
}{
\spadpaste{macro ff(x) == x**2 + 1 \bound{ff}}
}
\xtc{
Apply it to a number, a symbol, or an expression.
}{
\spadpaste{ff z \free{ff}}
}
\xtc{
Macros can also be nested, but you get an error message if you
run out of space because of an infinite nesting loop.
}{
\spadpaste{macro gg(x) == ff(2*x - 2/3) \bound{gg}\free{ff}}
}
\xtc{
This new macro is fine as it does not produce a loop.
}{
\spadpaste{gg(1/w) \free{gg}}
}
%
\xtc{
This, however, loops since \axiom{gg} is
defined in terms of \axiom{ff}.
}{
\spadpaste{macro ff(x) == gg(-x) \free{gg}}
}
\xtc{
The body of a macro can be a block.
}{
\spadpaste{macro next == (past := present; present := future; future := past + present) \bound{next}}
}
\xtc{
Before entering \axiom{next}, we need
values for \axiom{present} and \axiom{future}.
}{
\spadpaste{present : Integer := 0 \bound{present}}
}
\xtc{
}{
\spadpaste{future : Integer := 1 \bound{future}}
}
\xtc{
Repeatedly evaluating \axiom{next} produces the next Fibonacci number.
}{
\spadpaste{next \free{future}\free{present}}
}
\xtc{
And the next one.
}{
\spadpaste{next \free{future}\free{present}}
}
\xtc{
Here is the infinite stream of the rest of the Fibonacci numbers.
}{
\spadpaste{[next for i in 1..] \free{future}\free{present}}
}
\xtc{
Bundle all the above lines into a single macro.
}{
\begin{spadsrc}[\bound{fibstr}]
macro fibStream ==
  present : Integer := 1
  future : Integer := 1
  [next for i in 1..] where
    macro next ==
      past := present
      present := future
      future := past + present
\end{spadsrc}
}
\xtc{
Use \axiomFunFrom{concat}{Stream} to start with the first two
%-% \HDindex{Fibonacci numbers}{ugUserMacrosPage}{6.2.}{Macros}
Fibonacci numbers.
}{
\spadpaste{concat([0,1],fibStream) \free{fibstr}}
}
\xtc{
An easier way to compute these numbers is to
use the library operation \axiomFun{fibonacci}.
}{
\spadpaste{[fibonacci i for i in 1..]}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserIntroTitle}{Introduction to Functions}
\newcommand{\ugUserIntroNumber}{6.3.}
%
% =====================================================================
\begin{page}{ugUserIntroPage}{6.3. Introduction to Functions}
% =====================================================================
\beginscroll

Each name in your workspace can refer to a single object.
This may be any kind of object including a function.
You can use interactively any function from the library or any that you
define in the workspace.
In the library the same name can have very many functions, but you
can have only one function with a given name, although it can have any
number of arguments that you choose.

If you define a function in the workspace that has the same name and number
of arguments as one in the library, then your definition takes precedence.
In fact, to get the library function you must
\spadglossSee{package-call}{package call} it (see \downlink{``\ugTypesPkgCallTitle''}{ugTypesPkgCallPage} in Section \ugTypesPkgCallNumber\ignore{ugTypesPkgCall}).

To use a function in \Language{}, you apply it to its arguments.
Most functions are applied by entering the name of the function followed by
its argument or arguments.
\xtc{
}{
\spadpaste{factor(12)}
}
%
\xtc{
Some functions like \axiomOp{+} have {\it infix} \spadgloss{operators} as names.
}{
\spadpaste{3 + 4}
}
\xtc{
The function \axiomOp{+} has two arguments.
When you give it more than two arguments,
\Language{} groups the arguments to the left.
This expression is equivalent to \axiom{(1 + 2) + 7}.
}{
\spadpaste{1 + 2 + 7}
}

All operations, including infix operators, can be written in prefix form,
that is, with the operation name followed by the arguments
in parentheses.
For example, \axiom{2 + 3} can alternatively be written as \axiom{+(2,3)}.
But \axiom{+(2,3,4)} is an error since \axiomOp{+}
takes only two arguments.

Prefix operations are generally applied before the infix operation.
Thus \axiom{factorial 3 + 1} means \axiom{factorial(3) + 1} producing
\axiom{7}, and
\axiom{- 2 + 5} means \axiom{(-2) + 5} producing \axiom{3}.
An example of a prefix operator is prefix \axiomOp{-}.
For example, \axiom{- 2 + 5} converts to \axiom{(- 2) + 5} producing
the value \axiom{3}.
Any prefix function taking two arguments can be written in
an infix manner by putting an
ampersand (\axiomSyntax{\&}) before the name.
Thus \axiom{D(2*x,x)} can be written as
\axiom{2*x \&D x} returning \axiom{2}.

Every function in \Language{} is identified by
a \spadgloss{name} and \spadgloss{type}.\footnote{An exception is
an ``anonymous function''
discussed in
\downlink{``\ugUserAnonTitle''}{ugUserAnonPage} in Section \ugUserAnonNumber\ignore{ugUserAnon}.}
The type of a function is always a mapping of the form
\spadsig{Source}{Target}
where \axiom{Source} and \axiom{Target} are types.
To enter a type from the keyboard, enter the arrow by using
a hyphen \axiomSyntax{-} followed by a greater-than sign
\axiomSyntax{>}, e.g. {\tt Integer -> Integer}.

Let's go back to \axiomOp{+}.
There are many \axiomOp{+} functions in the
\Language{} library: one for integers, one for floats, another for
rational numbers, and so on.
These \axiomOp{+} functions have different types and thus are
different functions.
You've seen examples of this \spadgloss{overloading}
before---using the same name for different functions.
Overloading is the rule rather than the exception.
You can add two integers, two polynomials, two matrices or
two power series.
These are all done with the same function name
but with different functions.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserDeclareTitle}{Declaring the Type of Functions}
\newcommand{\ugUserDeclareNumber}{6.4.}
%
% =====================================================================
\begin{page}{ugUserDeclarePage}{6.4. Declaring the Type of Functions}
% =====================================================================
\beginscroll

In \downlink{``\ugTypesDeclareTitle''}{ugTypesDeclarePage} in Section \ugTypesDeclareNumber\ignore{ugTypesDeclare} we discussed how to declare a variable
to restrict the kind of values that can be assigned to it.
In this section we show how to declare a variable that refers to
function objects.

\beginImportant
A function is an object of type
\centerline{{\spadsig{Source}{Type}}}
where \axiom{Source} and \axiom{Target} can be any type.
A common type for \axiom{Source} is
\axiomType{Tuple}(\subscriptIt{T}{1}, \ldots, \subscriptIt{T}{n}),
usually written
(\subscriptIt{T}{1}, \ldots, \subscriptIt{T}{n}),
to indicate a function of \axiom{n} arguments.
\endImportant

\xtc{
If \axiom{g} takes an \axiomType{Integer}, a \axiomType{Float} and
another \axiomType{Integer}, and returns a
\axiomType{String}, the declaration is written this way.
}{
\spadpaste{g: (Integer,Float,Integer) -> String}
}
\xtc{
The types need not be written fully; using abbreviations, the above
declaration is:
}{
\spadpaste{g: (INT,FLOAT,INT) -> STRING}
}
\xtc{
It is possible for a function to take no arguments.
If \axiom{ h} takes no arguments
but returns a \axiomType{Polynomial} \axiomType{Integer}, any
of the following declarations is acceptable.
}{
\spadpaste{h: () -> POLY INT}
}
\xtc{
}{
\spadpaste{h: () -> Polynomial INT}
}
\xtc{
}{
\spadpaste{h: () -> POLY Integer}
}


\beginImportant
Functions can also be declared when they are being defined.
The syntax for combined declaration/definition is:
\centerline{{\frenchspacing{\tt {\it functionName}(\subscriptIt{parm}{1}: \subscriptIt{parmType}{1}, \ldots, \subscriptIt{parm}{N}: \subscriptIt{parmType}{N}): {\it functionReturnType}}}}
\endImportant

The following definition fragments show how this can be done for
the functions \axiom{g} and \axiom{h} above.
\begin{verbatim}
g(arg1: INT, arg2: FLOAT, arg3: INT): STRING == ...

h(): POLY INT == ...
\end{verbatim}

A current restriction on function declarations is that they must
involve fully specified types (that is, cannot include modes involving
explicit or implicit \axiomSyntax{?}).
For more information on declaring things in general, see
\downlink{``\ugTypesDeclareTitle''}{ugTypesDeclarePage} in Section \ugTypesDeclareNumber\ignore{ugTypesDeclare}.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserOneTitle}{One-Line Functions}
\newcommand{\ugUserOneNumber}{6.5.}
%
% =====================================================================
\begin{page}{ugUserOnePage}{6.5. One-Line Functions}
% =====================================================================
\beginscroll

As you use \Language{}, you will find that you will write many short functions
%-% \HDindex{function!one-line definition}{ugUserOnePage}{6.5.}{One-Line Functions}
to codify sequences of operations that you often perform.
In this section we write some simple one-line functions.

\xtc{
This is a simple recursive factorial function for positive integers.
}{
\spadpaste{fac n == if n < 3 then n else n * fac(n-1) \bound{fac}}
}
\xtc{
}{
\spadpaste{fac 10 \free{fac}}
}
%>> Thankfully, the $ is no longer needed in the next example.
\xtc{
This function computes \axiom{1 + 1/2 + 1/3 + ... + 1/n}.
}{
\spadpaste{s n == reduce(+,[1/i for i in 1..n]) \bound{s}}
}
\xtc{
}{
\spadpaste{s 50 \free{s}}
}
\xtc{
This function computes a Mersenne number, several of which are prime.
%-% \HDindex{Mersenne number}{ugUserOnePage}{6.5.}{One-Line Functions}
}{
\spadpaste{mersenne i == 2**i - 1 \bound{mersenne}}
}
\xtc{
If you type \axiom{mersenne}, \Language{} shows you
the function definition.
}{
\spadpaste{mersenne \free{mersenne}}
}
\xtc{
Generate a stream of Mersenne numbers.
}{
\spadpaste{[mersenne i for i in 1..] \free{mersenne}}
}
\xtc{
Create a stream of those values of \axiom{i} such that
\axiom{mersenne(i)} is prime.
}{
\spadpaste{mersenneIndex := [n for n in 1.. | prime?(mersenne(n))] \bound{mersenneIndex}\free{mersenne}}
}
\xtc{
Finally, write a function that returns the \eth{\axiom{n}} Mersenne
prime.
}{
\spadpaste{mersennePrime n == mersenne mersenneIndex(n) \free{mersenne mersenneIndex}\bound{mersennePrime}}
}
\xtc{
}{
\spadpaste{mersennePrime 5 \free{mersennePrime}}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserDecUndecTitle}{Declared vs. Undeclared Functions}
\newcommand{\ugUserDecUndecNumber}{6.6.}
%
% =====================================================================
\begin{page}{ugUserDecUndecPage}{6.6. Declared vs. Undeclared Functions}
% =====================================================================
\beginscroll

If you declare the type of a function, you can apply
it to any data that can be converted to the source type
of the function.

\labelSpace{2pc}
\xtc{
Define \userfun{f} with type \spadsig{Integer}{Integer}.
}{
\spadpaste{f(x: Integer): Integer == x + 1 \bound{f}}
}
\xtc{
The function
\userfun{f} can be applied to integers, \ldots
}{
\spadpaste{f 9 \free{f}}
}
\xtc{
and to values that convert to integers, \ldots
}{
\spadpaste{f(-2.0) \free{f}}
}
\xtc{
but not to values that cannot be converted to integers.
}{
\spadpaste{f(2/3) \free{f}}
}

To make the function over a wide range of types, do not
declare its type.
\xtc{
Give the same definition with no declaration.
}{
\spadpaste{g x == x + 1 \bound{g}}
}
\xtc{
If \axiom{x + 1} makes sense, you can apply \userfun{g} to \axiom{x}.
}{
\spadpaste{g 9 \free{g}}
}
\xtc{
A version of \userfun{g} with different argument types
get compiled for each new kind of argument used.
}{
\spadpaste{g(2/3)  \free{g}}
}
\xtc{
Here \axiom{x+1} for \axiom{x = "axiom"} makes no sense.
}{
\spadpaste{g("axiom")\free{g}}
}

As you will see in \downlink{``\ugCategoriesTitle''}{ugCategoriesPage} in Chapter \ugCategoriesNumber\ignore{ugCategories},
\Language{} has a formal idea of categories for what ``makes sense.''

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserDecOpersTitle}{Functions vs. Operations}
\newcommand{\ugUserDecOpersNumber}{6.7.}
%
% =====================================================================
\begin{page}{ugUserDecOpersPage}{6.7. Functions vs. Operations}
% =====================================================================
\beginscroll

A function is an object that you can create, manipulate, pass to,
and return from functions (for some interesting examples of
library functions that manipulate functions, see
\downlink{`MappingPackage1'}{MappingPackageOneXmpPage}\ignore{MappingPackage1}).
Yet, we often seem to use the term \spadgloss{operation} and
function interchangeably in \Language{}.
What is the distinction?

First consider values and types associated with some variable \axiom{n} in
your workspace.
You can make the declaration \axiom{n : Integer}, then assign \axiom{n} an
integer value.
You then speak of the integer \axiom{n}.
However, note that the integer is not the name \axiom{n} itself, but
the value that you assign to \axiom{n}.

Similarly, you can declare a variable \axiom{f} in your workspace to have
type \spadsig{Integer}{Integer}, then assign \axiom{f}, through a definition
or an assignment of an anonymous function.
You then speak of the function \axiom{f}.
However, the function is not \axiom{f}, but the value that you
assign to \axiom{f}.

A function is a value, in fact, some machine code for doing something.
Doing what?
Well, performing some \spadgloss{operation}.
Formally, an operation consists of the constituent parts of \axiom{f} in your
workspace, excluding the value; thus an operation has a name and a type.
An operation is what domains and packages export.
Thus \axiomType{Ring} exports one operation \axiomOp{+}.
Every ring also exports this operation.
Also, the author of every ring in the system is obliged under contract
(see \downlink{``\ugPackagesAbstractTitle''}{ugPackagesAbstractPage} in Section \ugPackagesAbstractNumber\ignore{ugPackagesAbstract})
to provide an implementation for this operation.

This chapter is all about functions---how you create them interactively and
how you apply them to meet your needs.
In \downlink{``\ugPackagesTitle''}{ugPackagesPage} in Chapter \ugPackagesNumber\ignore{ugPackages} you will learn how to create them for the
\Language{} library.
Then in \downlink{``\ugCategoriesTitle''}{ugCategoriesPage} in Chapter \ugCategoriesNumber\ignore{ugCategories}, you will learn about categories and
exported operations.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserDelayTitle}{Delayed Assignments vs. Functions with No Arguments}
\newcommand{\ugUserDelayNumber}{6.8.}
%
% =====================================================================
\begin{page}{ugUserDelayPage}{6.8. Delayed Assignments vs. Functions with No Arguments}
% =====================================================================
\beginscroll

In \downlink{``\ugLangAssignTitle''}{ugLangAssignPage} in Section \ugLangAssignNumber\ignore{ugLangAssign} we discussed the difference between immediate and
%-% \HDindex{function!with no arguments}{ugUserDelayPage}{6.8.}{Delayed Assignments vs. Functions with No Arguments}
delayed assignments.
In this section we show the difference between delayed
assignments and functions of no arguments.

\labelSpace{2pc}
\xtc{
A function of no arguments is sometimes called a {\it nullary function.}
}{
\spadpaste{sin24() == sin(24.0) \bound{sin24}}
}
\xtc{
You must use the parentheses (\axiomSyntax{()}) to evaluate it.
Like a delayed assignment, the right-hand-side of a function evaluation
is not evaluated until the left-hand-side is used.
}{
\spadpaste{sin24() \free{sin24}}
}
\xtc{
If you omit the parentheses, you just get the function definition.
%(Note how the explicit floating point number in the definition
%has been translated into a function call involving a mantissa,
%exponent and radix.)
}{
\spadpaste{sin24 \free{sin24}}
}
\xtc{
You do not use the parentheses \axiomSyntax{()} in a delayed assignment\ldots
}{
\spadpaste{cos24 == cos(24.0) \bound{cos24}}
}
\xtc{
nor in the evaluation.
}{
\spadpaste{cos24 \free{cos24}}
}
The only syntactic difference between delayed assignments
and nullary functions is that you use \axiomSyntax{()} in the latter case.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserUseTitle}{How \Language{} Determines What Function to Use}
\newcommand{\ugUserUseNumber}{6.9.}
%
% =====================================================================
\begin{page}{ugUserUsePage}{6.9. How \Language{} Determines What Function to Use}
% =====================================================================
\beginscroll

What happens if you define a function that has the same name as a library
function?
Well, if your function has the same name and number of arguments (we
sometimes say \spadgloss{arity}) as another function
in the library, then your function covers up the library function.
If you want then to call the library function, you will have to package-call
it.
\Language{} can use both the functions you write and those that come
from the library.
Let's do a simple example to illustrate this.
\xtc{
Suppose you (wrongly!) define \userfun{sin} in this way.
}{
\spadpaste{sin x == 1.0 \bound{sin}}
}
\xtc{
The value \axiom{1.0} is returned for any argument.
}{
\spadpaste{sin 4.3 \free{sin}}
}
\xtc{
If you want the library operation, we have to package-call it
(see \downlink{``\ugTypesPkgCallTitle''}{ugTypesPkgCallPage} in Section \ugTypesPkgCallNumber\ignore{ugTypesPkgCall}
for more information).
}{
\spadpaste{sin(4.3)\$Float}
}
\xtc{
}{
\spadpaste{sin(34.6)\$Float}
}
\xtc{
Even worse, say we accidentally used the same name as a library
function in the function.
}{
\spadpaste{sin x == sin x \bound{sin1}}
}
\xtc{
Then \Language{} definitely does not understand us.
}{
\spadpaste{sin 4.3 \free{sin1}}
}
\xtc{
Again, we could package-call the inside function.
}{
\spadpaste{sin x == sin(x)\$Float \bound{sin2}}
}
\xtc{
}{
\spadpaste{sin 4.3 \free{sin2}}
}
Of course, you are unlikely to make such obvious errors.
It is more probable that you would write a function and in the body use a
function that you think is a library function.
If you had also written a function by that same name, the library function
would be invisible.

How does \Language{} determine what library function to call?
It very much depends on the particular example, but the simple case of
creating the polynomial
\axiom{x + 2/3} will give you an idea.
\indent{4}
\beginitems
\item[1. ] The \axiom{x} is analyzed and its default type is
\axiomType{Variable(x)}.
\item[2. ] The \axiom{2} is analyzed and its default type is
\axiomType{PositiveInteger}.
\item[3. ] The \axiom{3} is analyzed and its default type is
\axiomType{PositiveInteger}.
\item[4. ] Because the arguments to \axiomOp{/} are integers, \Language{}
gives the expression \axiom{2/3} a default target type of
\axiomType{Fraction(Integer)}.
\item[5. ] \Language{} looks in \axiomType{PositiveInteger} for \axiomOp{/}.
It is not found.
\item[6. ] \Language{} looks in \axiomType{Fraction(Integer)} for \axiomOp{/}.
It is found for arguments of type \axiomType{Integer}.
\item[7. ] The \axiom{2} and \axiom{3} are converted to objects of type
\axiomType{Integer} (this is trivial) and \axiomOp{/} is applied,
creating an object of type \axiomType{Fraction(Integer)}.
\item[8. ] No \axiomOp{+} for arguments of types \axiomType{Variable(x)} and
\axiomType{Fraction(Integer)} are found in either domain.
\item[9. ] \Language{} resolves
%-% \HDindex{resolve}{ugUserUsePage}{6.9.}{How \Language{} Determines What Function to Use}
(see \downlink{``\ugTypesResolveTitle''}{ugTypesResolvePage} in Section \ugTypesResolveNumber\ignore{ugTypesResolve})
the types and gets \axiomType{Polynomial (Fraction (Integer))}.
\item[10. ] The \axiom{x} and the \axiom{2/3} are converted to objects of this
type and \axiomOp{+} is applied, yielding the answer, an object of type
\axiomType{Polynomial (Fraction (Integer))}.
\enditems
\indent{0}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserCompIntTitle}{Compiling vs. Interpreting}
\newcommand{\ugUserCompIntNumber}{6.10.}
%
% =====================================================================
\begin{page}{ugUserCompIntPage}{6.10. Compiling vs. Interpreting}
% =====================================================================
\beginscroll

When possible, \Language{} completely determines the type of every object in
a function, then translates the function definition to \Lisp{} or
to machine code (see next section).
This translation,
%-% \HDindex{function!compiler}{ugUserCompIntPage}{6.10.}{Compiling vs. Interpreting}
called \spadglossSee{compilation}{compiler}, happens the first time you call
the function and results in a computational delay.
Subsequent function calls with the same argument types use the compiled
version of the code without delay.

If \Language{} cannot determine the type of everything, the
function may still be executed
%-% \HDindex{function!interpretation}{ugUserCompIntPage}{6.10.}{Compiling vs. Interpreting}
but
%-% \HDindex{interpret-code mode}{ugUserCompIntPage}{6.10.}{Compiling vs. Interpreting}
in \spadglossSee{interpret-code mode}{interpreter} :
each statement in the function is analyzed and executed as the control
flow indicates.
This process is slower than executing a compiled function, but it
allows the execution of code that may involve objects whose types
change.

\beginImportant
If \Language{} decides that it cannot compile the code, it
issues a message stating the problem and then the following
message:
%
\centerline{{{\bf We will attempt to step through and interpret the code.}}}
%
This is not a time to panic.
%-% \HDindex{panic!avoiding}{ugUserCompIntPage}{6.10.}{Compiling vs. Interpreting}
Rather, it just means that what you gave to \Language{}
is somehow ambiguous: either it is not specific enough to be analyzed
completely, or it is beyond \Language{}'s present interactive
compilation abilities.
\endImportant

\xtc{
This function runs in interpret-code mode, but it does not compile.
}{
\begin{spadsrc}[\bound{varPolys}]
varPolys(vars) ==
  for var in vars repeat
    output(1 :: UnivariatePolynomial(var,Integer))
\end{spadsrc}
}
\xtc{
For \axiom{vars} equal to \axiom{['x, 'y, 'z]}, this function displays
\axiom{1} three times.
}{
\spadpaste{varPolys ['x,'y,'z] \free{varPolys}}
}
\xtc{
The type of the argument to \axiomFun{output} changes in each iteration,
so \Language{} cannot compile the function.
In this case, even the inner loop by itself would have a problem:
}{
\begin{spadsrc}
for var in ['x,'y,'z] repeat
  output(1 :: UnivariatePolynomial(var,Integer))
\end{spadsrc}
}

Sometimes you can help a function to compile by using an extra conversion
or by using \axiom{pretend}.
\spadkey{pretend}
See \downlink{``\ugTypesSubdomainsTitle''}{ugTypesSubdomainsPage} in Section \ugTypesSubdomainsNumber\ignore{ugTypesSubdomains} for details.

When a function is compilable, you have the choice of whether it is
compiled to \Lisp{} and then interpreted by the \Lisp{}
interpreter or then further compiled from \Lisp{} to machine code.
%-% \HDindex{machine code}{ugUserCompIntPage}{6.10.}{Compiling vs. Interpreting}
The option is controlled via \spadcmd{)set functions compile}.
%-% \HDsyscmdindex{set function compile}{ugUserCompIntPage}{6.10.}{Compiling vs. Interpreting}
Issue \spadcmd{)set functions compile on} to compile all the way to
machine code.
With
the default setting \spadcmd{)set functions compile off},
\Language{} has its \Lisp{} code interpreted
because the overhead of further compilation is larger than the run-time
of most of the functions our users have defined.
You may find that selectively turning this option on and off will
%-% \HDindex{performance}{ugUserCompIntPage}{6.10.}{Compiling vs. Interpreting}
give you the best performance in your particular application.
For example, if you are writing functions for graphics applications
where hundreds of points are being computed, it is almost certainly true
that you will get the best performance by issuing
\spadcmd{)set functions compile on}.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserPieceTitle}{Piece-Wise Function Definitions}
\newcommand{\ugUserPieceNumber}{6.11.}
%
% =====================================================================
\begin{page}{ugUserPiecePage}{6.11. Piece-Wise Function Definitions}
% =====================================================================
\beginscroll

To move beyond functions defined in one line, we introduce in this section
functions that are defined piece-by-piece.
That is, we say ``use this definition when the argument is such-and-such and
use this other definition when the argument is that-and-that.''

\beginmenu
    \menudownlink{{6.11.1. A Basic Example}}{ugUserPieceBasicPage}
    \menudownlink{{6.11.2. Picking Up the Pieces}}{ugUserPiecePickingPage}
    \menudownlink{{6.11.3. Predicates}}{ugUserPiecePredPage}
\endmenu
\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserPieceBasicTitle}{A Basic Example}
\newcommand{\ugUserPieceBasicNumber}{6.11.1.}
%
% =====================================================================
\begin{page}{ugUserPieceBasicPage}{6.11.1. A Basic Example}
% =====================================================================
\beginscroll

There are many other ways to define a factorial function for nonnegative
integers.
You might
%-% \HDindex{function!piece-wise definition}{ugUserPieceBasicPage}{6.11.1.}{A Basic Example}
say
%-% \HDindex{piece-wise function definition}{ugUserPieceBasicPage}{6.11.1.}{A Basic Example}
factorial of \axiom{0} is \axiom{1,} otherwise factorial of \axiom{n} is
\axiom{n} times factorial of \axiom{n-1}.
Here is one way to do this in \Language{}.
%
\xtc{
Here is the value for \axiom{n = 0}.
}{
\spadpaste{fact(0) == 1 \bound{fact0}}
}
\xtc{
Here is the value for \axiom{n > 0}.
The vertical bar \axiomSyntax{|} means
``such that''.
}{
\spadpaste{fact(n | n > 0) == n * fact(n - 1) \free{fact0}\bound{factn}}
}
%-% \HDindex{such that}{ugUserPieceBasicPage}{6.11.1.}{A Basic Example}
%>> am moving this back
%The vertical bar \axiomSyntax{|} is read as ``such that'' and so
%\index{such that}
%the second line means that that part of the definition for \userfun{fact}
%is for any \axiom{n} such that \axiom{n} is greater than 0.
%In fact, the first line is really just a shorthand expression for
%\axiom{fact(n | n = 0) == 1}.
%>> prefer scratching next 4 lines
%We are implicitly using a \spadgloss{predicate} with a \axiomSyntax{|} in
%this line (see \downlink{``\ugUserPiecePredTitle''}{ugUserPiecePredPage} in Section \ugUserPiecePredNumber\ignore{ugUserPiecePred} for more on predicates).
%So this piece of the function is applicable to all (the not so many!)
%values of \axiom{n} that are equal to zero.
\xtc{
What is the value for \axiom{n = 3}?
}{
\spadpaste{fact(3) \free{factn}}
}
\xtc{
What is the value for \axiom{n = -3}?
}{
\spadpaste{fact(-3) \free{factn}}
}
\xtc{
Now for a second definition.
Here is the value for \axiom{n = 0}.
}{
\spadpaste{facto(0) == 1 \bound{facto0}}
}
\xtc{
Give an error message if \axiom{n < 0}.
}{
\spadpaste{facto(n | n < 0) == error "arguments to facto must be non-negative" \free{facto0}\bound{factop}}
}
\xtc{
Here is the value otherwise.
}{
\spadpaste{facto(n) == n * facto(n - 1) \free{factop}\bound{facton}}
}
\xtc{
What is the value for \axiom{n = 7}?
}{
\spadpaste{facto(3) \free{facton}}
}
\xtc{
What is the value for \axiom{n = -7}?
}{
\spadpaste{facto(-7) \free{facton}}
}
\xtc{
To see the current piece-wise definition of a function,
use \spadsys{)display value}.
}{
\spadpaste{)display value facto \free{facton}}
}

In general a {\it piece-wise definition} of a function consists of two or
more parts.
Each part gives a ``piece'' of the entire definition.
\Language{} collects the pieces of a function as you enter them.
When you ask for a value of the function, it then ``glues''
the pieces together to form a function.

The two piece-wise definitions for the factorial function
are examples of recursive functions, that is, functions that
are defined in terms of themselves.
Here is an interesting doubly-recursive function.
This function returns the value \axiom{11} for all positive integer arguments.
\xtc{
Here is the first of two pieces.
}{
\spadpaste{eleven(n | n < 1) == n + 11\bound{ff0}}
}
\xtc{
And the general case.
}{
\spadpaste{eleven(m) == eleven(eleven(m - 12))\bound{ff1}\free{ff0}}
}
\xtc{
Compute \axiom{elevens}, the infinite stream
of values of \axiom{eleven}.
}{
\spadpaste{elevens := [eleven(i) for i in 0..]\bound{ff2}\free{ff1}}
}
\xtc{
What is the value at \axiom{n = 200}?
}{
\spadpaste{elevens 200\free{ff2}}
}
\xtc{
What is the \Language{}'s definition of \axiom{eleven}?
}{
\spadpaste{)display value eleven\free{ff2}}
}
\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserPiecePickingTitle}{Picking Up the Pieces}
\newcommand{\ugUserPiecePickingNumber}{6.11.2.}
%
% =====================================================================
\begin{page}{ugUserPiecePickingPage}{6.11.2. Picking Up the Pieces}
% =====================================================================
\beginscroll

Here are the details about how \Language{} creates a function from its
pieces.
\Language{} converts the \eth{\axiom{i}} piece of a function definition into a
conditional expression of the form: \axiom{if} \pred{i} \axiom{then}
\expr{i}.
If any new piece has a \pred{i} that is identical\footnote{after all
variables are uniformly named} to an earlier \pred{j}, the earlier piece is
removed.
Otherwise, the new piece is always added at the end.

\beginImportant
If there are \axiom{n} pieces to a function definition for \axiom{f},
the function defined \axiom{f} is: \newline
%
\texht{\hspace*{3pc}}{\tab{6}}
{\tt if} \pred{1} {\tt then} \expr{1} {\tt else}\newline
\texht{\hspace*{6pc}}{\tab{12}}. . . \newline
\texht{\hspace*{3pc}}{\tab{6}}
{\tt if} \pred{n} {\tt then} \expr{n} {\tt else}\newline
\texht{\hspace*{3pc}}{\tab{6}}
{\tt  error "You did not define f for argument <arg>."}
%
\endImportant

You can give definitions of any number of mutually recursive function
definitions, piece-wise or otherwise.
No computation is done until you ask for a value.
When you do ask for a value, all the relevant definitions are gathered,
analyzed, and translated into separate functions and compiled.

\xtc{
Let's recall the definition of \userfun{eleven} from
\texht{the previous section}{\downlink{``\ugUserPieceBasicTitle''}{ugUserPieceBasicPage} in Section \ugUserPieceBasicNumber\ignore{ugUserPieceBasic}}.
}{
\spadpaste{eleven(n | n < 1) == n + 11\bound{ff0}}
}
\xtc{
}{
\spadpaste{eleven(m) == eleven(eleven(m - 12))\bound{ff1}\free{ff0}}
}

A similar doubly-recursive function below produces \axiom{-11} for all
negative positive integers.
If you haven't worked out why or how \userfun{eleven} works,
the structure of this definition gives a clue.
\xtc{
This definition we write as a block.
}{
\begin{spadsrc}[\bound{rf1}]
minusEleven(n) ==
  n >= 0 => n - 11
  minusEleven (5 + minusEleven(n + 7))
\end{spadsrc}
}
\xtc{
Define \axiom{s(n)} to be the
sum of plus and minus ``eleven'' functions divided by \axiom{n}.
Since \axiom{11 - 11 = 0}, we define \axiom{s(0)} to be \axiom{1}.
}{
\spadpaste{s(0) == 1\bound{rf2}}
}
\xtc{
And the general term.
}{
\spadpaste{s(n) == (eleven(n) + minusEleven(n))/n\bound{rf3}\free{rf2 rf1 ff1}}
}
\xtc{
What are the first ten values of \axiom{s}?
}{
\spadpaste{[s(n) for n in 0..]\free{rf3}}
}
%% interpreter puts the rule at the end - should fix
\Language{} can create infinite streams in the positive direction (for
example, for index values \axiom{0,1, \ldots}) or negative direction (for
example, for index values \axiom{0,-1,-2, \ldots}).
Here we would like a stream of values of \axiom{s(n)} that is infinite in
both directions.
The function \axiom{t(n)} below returns the \eth{\axiom{n}} term of the infinite
stream \axiom{[s(0), s(1), s(-1), s(2), s(-2), \ldots].}
Its definition has three pieces.
\xtc{
Define the initial term.
}{
\spadpaste{t(1) == s(0)\bound{t1}\free{rf4}}
}
\xtc{
The even numbered terms are the \axiom{s(i)} for positive \axiom{i}.
We use \axiomOp{quo} rather than \axiomOp{/}
since we want the result to be an integer.
}{
\spadpaste{t(n | even?(n)) == s(n quo 2)\free{t1}\bound{t2}}
}
\xtc{
Finally, the odd numbered terms are the
\axiom{s(i)} for negative \axiom{i}.
In piece-wise definitions, you can use different variables
to define different pieces. \Language{} will not get confused.
}{
\spadpaste{t(p) == s(- p quo 2)\free{t2}\bound{t3}}
}
\xtc{
Look at the definition of \axiom{t}.
In the first piece, the variable \axiom{n}
was used; in the second piece, \axiom{p}.
\Language{} always uses
your last variable to display your definitions
back to you.
}{
\spadpaste{)display value t\free{t2}}
}
\xtc{
Create a series of values of \axiom{s} applied to
alternating positive and negative arguments.
}{
\spadpaste{[t(i) for i in 1..]\free{t3}\bound{t4}}
}
\xtc{
Evidently \axiom{t(n) = 1} for all \axiom{i.}
Check it at \axiom{n= 100}.
}{
\spadpaste{t(100)\free{t4}}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserPiecePredTitle}{Predicates}
\newcommand{\ugUserPiecePredNumber}{6.11.3.}
%
% =====================================================================
\begin{page}{ugUserPiecePredPage}{6.11.3. Predicates}
% =====================================================================
\beginscroll

We have already seen some examples of
%-% \HDindex{function!predicate}{ugUserPiecePredPage}{6.11.3.}{Predicates}
predicates
%-% \HDindex{predicate!in function definition}{ugUserPiecePredPage}{6.11.3.}{Predicates}
(\downlink{``\ugUserPieceBasicTitle''}{ugUserPieceBasicPage} in Section \ugUserPieceBasicNumber\ignore{ugUserPieceBasic}).
Predicates are \axiomType{Boolean}-valued expressions and \Language{} uses them
for filtering collections
(see \downlink{``\ugLangItsTitle''}{ugLangItsPage} in Section \ugLangItsNumber\ignore{ugLangIts})
and for placing
constraints on function arguments.
In this section we discuss their latter usage.

\xtc{
The simplest use of a predicate is one you don't see at all.
}{
\spadpaste{opposite 'right == 'left}
}
\xtc{
Here is a longer way to give the ``opposite definition.''
}{
\spadpaste{opposite (x | x = 'left) == 'right}
}
\xtc{
Try it out.
}{
\spadpaste{for x in ['right,'left,'inbetween] repeat output opposite x}
}

Explicit predicates tell \Language{} that the given function definition
piece is to be applied if the predicate evaluates to {\tt true} for the
arguments to the function.
You can use such ``constant'' arguments for integers,
%-% \HDindex{function!constant argument}{ugUserPiecePredPage}{6.11.3.}{Predicates}
strings, and quoted symbols.
%-% \HDindex{constant function argument}{ugUserPiecePredPage}{6.11.3.}{Predicates}
The \axiomType{Boolean} values \axiom{true} and \axiom{false} can also be used
if qualified with ``\spad{@}'' or ``\spad{\$}'' and \axiomType{Boolean}.
The following are all valid function definition fragments using
constant arguments.
\begin{verbatim}
a(1) == ...
b("unramified") == ...
c('untested) == ...
d(true@Boolean) == ...
\end{verbatim}

If a function has more than one argument,
each argument can have its own predicate.
However, if a predicate involves two or more arguments, it must be given
{\it after} all the arguments mentioned in the predicate have been given.
You are always safe to give
a single predicate at the end of the argument list.
\xtc{
A function involving predicates on two arguments.
}{
\spadpaste{inFirstHalfQuadrant(x | x > 0,y | y < x) == true}
}
\xtc{
This is incorrect as it gives a predicate on \axiom{y}
before the argument \axiom{y} is given.
}{
\spadpaste{inFirstHalfQuadrant(x | x > 0 and y < x,y) == true}
}
\xtc{
It is always correct to write the predicate at the end.
}{
\spadpaste{inFirstHalfQuadrant(x,y | x > 0 and y < x) == true \bound{ifq1a}}
}
\xtc{
Here is the rest of the definition.
}{
\spadpaste{inFirstHalfQuadrant(x,y) == false \bound{ifq1b}}
}
\xtc{
Try it out.
}{
\spadpaste{[inFirstHalfQuadrant(i,3) for i in 1..5]\bound{ifq1b}}
}

{\bf Remark:} Very old versions of \Language{} allowed predicates
to be given after a {\tt when} keyword as in
{\tt inFirstHalfQuadrant(x ,y) == true when x >0 and y < x}.
This is no longer supported, is WRONG, and will cause a syntax
error or strange behavior.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserCacheTitle}{Caching Previously Computed Results}
\newcommand{\ugUserCacheNumber}{6.12.}
%
% =====================================================================
\begin{page}{ugUserCachePage}{6.12. Caching Previously Computed Results}
% =====================================================================
\beginscroll

By default, \Language{} does not save the values of any function.
%-% \HDindex{function!caching values}{ugUserCachePage}{6.12.}{Caching Previously Computed Results}
You can cause it to save values and not to recompute unnecessarily
%-% \HDindex{remembering function values}{ugUserCachePage}{6.12.}{Caching Previously Computed Results}
by using \spadcmd{)set functions cache}.
%-% \HDsyscmdindex{set functions cache}{ugUserCachePage}{6.12.}{Caching Previously Computed Results}
This should be used before the functions are defined or, at least, before
they are executed.
The word following ``cache'' should be \axiom{0} to turn off
caching, a positive integer \axiom{n} to save the last \axiom{n}
computed values or ``all'' to save all computed values.
If you then give a list of names of functions, the caching
only affects those functions.
Use no list of names or ``all'' when you want to define the default
behavior for functions not specifically mentioned in other
\spadcmd{)set functions cache} statements.
If you give no list of names, all functions will have the caching behavior.
If you explicitly turn on caching for one or more names, you must
explicitly turn off caching for those names when you want to stop
saving their values.

\xtc{
This causes the functions \userfun{f} and \userfun{g} to have
the last three computed values saved.
}{
\spadpaste{)set functions cache 3 f g \bound{cache}}
}
\xtc{
This is a sample definition for \userfun{f}.
}{
\spadpaste{f x == factorial(2**x) \bound{fdef}\free{cache}}
}
\xtc{
A message is displayed stating what \userfun{f} will cache.
}{
\spadpaste{f(4) \free{}\free{cache}}
}
\xtc{
This causes all other functions to have all computed values saved by
default.
}{
\spadpaste{)set functions cache all}
}
\xtc{
This causes all functions that have not been specifically cached in some way
to have no computed values saved.
}{
\spadpaste{)set functions cache 0}
}
\xtc{
We also make \userfun{f} and \userfun{g} uncached.
}{
\spadpaste{)set functions cache 0 f g}
}

\beginImportant
Be careful about caching functions that have
\spadglossSee{side effects}{side effect}.
Such a function might destructively modify the elements of an array or
issue a \axiomFun{draw} command, for example.
A function that you expect to execute every time it is called should
not be cached.
Also, it is highly unlikely that a function with no arguments should
be cached.
\endImportant

You should also be careful about caching functions that depend on
free variables.
See \downlink{``\ugUserFreeLocalTitle''}{ugUserFreeLocalPage} in Section \ugUserFreeLocalNumber\ignore{ugUserFreeLocal}
for an example.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserRecurTitle}{Recurrence Relations}
\newcommand{\ugUserRecurNumber}{6.13.}
%
% =====================================================================
\begin{page}{ugUserRecurPage}{6.13. Recurrence Relations}
% =====================================================================
\beginscroll

One of the most useful classes of function are those defined via a
``recurrence relation.''
A {\it recurrence relation} makes each successive
%-% \HDindex{recurrence relation}{ugUserRecurPage}{6.13.}{Recurrence Relations}
value depend on some or all of the previous values.
A simple example is the ordinary ``factorial'' function:
\begin{verbatim}
fact(0) == 1
fact(n | n > 0) == n * fact(n-1)
\end{verbatim}

The value of
\axiom{fact(10)} depends on the value of \axiom{fact(9)}, \axiom{fact(9)}
on \axiom{fact(8)}, and so on.
Because it depends on only one previous value, it is usually called a
{\it first order recurrence relation.}
You can easily imagine a function based on two, three or more previous
values.
The Fibonacci numbers are probably the most famous function defined by a
%-% \HDindex{Fibonacci numbers}{ugUserRecurPage}{6.13.}{Recurrence Relations}
second order recurrence relation.
\xtc{
The library function \axiomFun{fibonacci} computes Fibonacci numbers.
It is obviously optimized for speed.
}{
\spadpaste{[fibonacci(i) for i in 0..]}
}
\xtc{
Define the
Fibonacci numbers ourselves using a piece-wise definition.
}{
\spadpaste{fib(1) == 1 \bound{fib0}}
}
\xtc{
}{
\spadpaste{fib(2) == 1 \bound{fib1}\free{fib0}}
}
\xtc{
}{
\spadpaste{fib(n) == fib(n-1) + fib(n-2) \bound{fibn}\free{fib1}}
}

As defined, this recurrence relation is obviously doubly-recursive.
To compute \axiom{fib(10)}, we need to compute \axiom{fib(9)} and
\axiom{fib(8)}.
And to  \axiom{fib(9)}, we need to compute \axiom{fib(8)} and
\axiom{fib(7)}.
And so on.
It seems that to compute \axiom{fib(10)} we need to compute
\axiom{fib(9)} once, \axiom{fib(8)} twice, \axiom{fib(7)} three times.
Look familiar?
The number of function calls needed to compute {\it any} second order
recurrence relation in the obvious way is exactly \axiom{fib(n)}.
These numbers grow!
For example, if \Language{} actually did this, then \axiom{fib(500)}
requires more than \texht{$10^{104}$}{\axiom{10**104}} function calls.
And, given all this, our definition of \userfun{fib} obviously could not be
used to calculate the five-hundredth Fibonacci number.
\xtc{
Let's try it anyway.
}{
\spadpaste{fib(500) \free{fibn}}
}

Since this takes a short time to compute, it obviously didn't do
as many as \texht{$10^{104}$}{\axiom{10**104}} operations!
By default, \Language{} transforms any recurrence relation it recognizes
into an iteration.
Iterations are efficient.
To compute the value of the \eth{\axiom{n}}
term of a recurrence relation using an iteration requires only
\axiom{n} function calls.\footnote{If
you compare the speed of our \userfun{fib} function
to the library function, our version is still slower.
This is because the library
\axiomFunFrom{fibonacci}{IntegerNumberTheoryFunctions}
uses a ``powering algorithm'' with a computing time
proportional to \texht{$\log^3(n)$}{\axiom{log(n)**3}} to compute
\axiom{fibonacci(n).}}

To turn off this special recurrence relation compilation, issue
%-% \HDsyscmdindex{set function recurrence}{ugUserRecurPage}{6.13.}{Recurrence Relations}
\begin{verbatim}
)set functions recurrence off
\end{verbatim}
To turn it back on, substitute ``{\tt on}'' for ``{\tt off}''.

The transformations that \Language{} uses for \userfun{fib} caches the
last two values.\footnote{For a more general \eth{\axiom{k}} order recurrence
relation, \Language{} caches the last \axiom{k} values.}
If, after computing a value for \userfun{fib}, you ask
for some larger value, \Language{} picks up the cached values
and continues computing from there.
See \downlink{``\ugUserFreeLocalTitle''}{ugUserFreeLocalPage} in Section \ugUserFreeLocalNumber\ignore{ugUserFreeLocal}
for an example of a function definition that has this same behavior.
Also see \downlink{``\ugUserCacheTitle''}{ugUserCachePage} in Section \ugUserCacheNumber\ignore{ugUserCache}
for a more general discussion of how you can cache function values.

Recurrence relations can be used for defining recurrence relations
involving polynomials, rational functions, or anything you like.
Here we compute the infinite stream of Legendre polynomials.
\xtc{
The Legendre polynomial of degree \axiom{0.}
}{
\spadpaste{p(0) == 1\bound{p0}}
}
\xtc{
The Legendre polynomial of degree \axiom{1.}
}{
\spadpaste{p(1) == x\bound{p1}}
}

\xtc{
The Legendre polynomial of degree \axiom{n}.
}{
\spadpaste{p(n) == ((2*n-1)*x*p(n-1) - (n-1)*p(n-2))/n\bound{pn}\free{p1}}
}
\xtc{
Compute the Legendre polynomial of degree \axiom{6.}
}{
\spadpaste{p(6)\free{pn}}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserMakeTitle}{Making Functions from Objects}
\newcommand{\ugUserMakeNumber}{6.14.}
%
% =====================================================================
\begin{page}{ugUserMakePage}{6.14. Making Functions from Objects}
% =====================================================================
\beginscroll

There are many times when you compute a complicated expression
and then wish to use that expression as the body of a function.
\Language{} provides an operation called \axiomFun{function} to do
%-% \HDindex{function!from an object}{ugUserMakePage}{6.14.}{Making Functions from Objects}
this.
%-% \HDindex{function!made by function @{made by {\bf function}}}{ugUserMakePage}{6.14.}{Making Functions from Objects}
It creates a function object and places it into the workspace.
There are several versions, depending on how many arguments the function
has.
The first argument to \axiomFun{function} is always the expression to be
converted into the function body, and the second is always the name to be
used for the function.
For more information, see \downlink{`MakeFunction'}{MakeFunctionXmpPage}\ignore{MakeFunction}.

\xtc{
Start with a simple example of a polynomial in three variables.
}{
\spadpaste{p := -x + y**2 - z**3 \bound{p}}
}
\xtc{
To make this into a function of no arguments that
simply returns the polynomial, use the two argument form of
\axiomFun{function}.
}{
\spadpaste{function(p,'f0) \free{p}\bound{f0}}
}
\xtc{
To avoid possible conflicts (see below), it is a good idea to
quote always this second argument.
}{
\spadpaste{f0 \free{f0}}
}
\xtc{
This is what you get when you evaluate the function.
}{
\spadpaste{f0() \free{f0}}
}
\xtc{
To make a function in \axiom{x}, use a version of
\axiomFun{function} that takes three arguments.
The last argument is the name of the variable to use as the parameter.
Typically, this variable occurs in the expression and, like the function
name, you should quote it to avoid possible confusion.
}{
\spadpaste{function(p,'f1,'x) \free{p}\bound{f1}}
}
\xtc{
This is what the new function looks like.
}{
\spadpaste{f1 \free{f1}}
}
\xtc{
This is the value of \userfun{f1} at \axiom{x = 3}.
Notice that the return type of the function is
\axiomType{Polynomial (Integer)}, the same as \axiom{p}.
}{
\spadpaste{f1(3) \free{f1}}
}
\xtc{
To use \axiom{x} and \axiom{y} as parameters, use the
four argument form of \axiomFun{function}.
}{
\spadpaste{function(p,'f2,'x,'y) \free{p}\bound{f2}}
}
\xtc{
}{
\spadpaste{f2 \free{f2}}
}
\xtc{
Evaluate \axiom{f2} at \axiom{x = 3} and \axiom{y = 0}.
The return type of \userfun{f2} is still
\axiomType{Polynomial(Integer)} because the variable \axiom{z}
is still present and not one of the parameters.
}{
\spadpaste{f2(3,0) \free{f2}}
}
\xtc{
Finally, use all three variables as parameters.
There is no five argument form of \axiomFun{function}, so use the one with
three arguments, the third argument being a list of the parameters.
}{
\spadpaste{function(p,'f3,['x,'y,'z]) \free{p}\bound{f3}}
}
\xtc{
Evaluate this using the same values for \axiom{x} and \axiom{y}
as above, but let \axiom{z} be \axiom{-6}.
The result type of \userfun{f3} is \axiomType{Integer}.
}{
\spadpaste{f3 \free{f3}}
}
\xtc{
}{
\spadpaste{f3(3,0,-6) \free{f3}}
}

The four functions we have defined via \axiom{p} have been undeclared.
To declare a function whose body is to be generated by
%-% \HDindex{function!declaring}{ugUserMakePage}{6.14.}{Making Functions from Objects}
\axiomFun{function}, issue the declaration {\it before} the function is created.
\xtc{
}{
\spadpaste{g: (Integer, Integer) -> Float \bound{g}}
}
\xtc{
}{
\spadpaste{D(sin(x-y)/cos(x+y),x) \bound{prev}}
}
\xtc{
}{
\spadpaste{function(\%,'g,'x,'y) \free{g}\free{prev}}
}
\xtc{
}{
\spadpaste{g \free{g}}
}
It is an error to use \axiom{g} without the quote in the
penultimate expression since \axiom{g} had been declared but did not have
a value.
Similarly, since it is common to overuse variable names like \axiom{x},
\axiom{y}, and so on,
you avoid problems if you always quote the variable names
for \axiomFun{function}.
In general,
if \axiom{x} has a value and you use \axiom{x} without a quote in a call to
\axiomFun{function}, then
\Language{} does not know what you are trying to do.

What kind of object is allowable as the first argument to \axiomFun{function}?
Let's use the \Browse{} facility of \HyperName{} to find out.
%-% \HDindex{Browse@\Browse{}}{ugUserMakePage}{6.14.}{Making Functions from Objects}
At the main \Browse{} menu, enter the string {\tt function} and then
click on {\bf Operations.}
The exposed operations called \axiomFun{function} all take an object
whose type belongs to category \axiomType{ConvertibleTo InputForm}.
What domains are those?
Go back to the main \Browse{} menu, erase {\tt function},
enter {\tt ConvertibleTo} in the
input area, and click on {\bf categories} on the {\bf Constructors} line.
At the bottom of the page, enter {\tt InputForm} in the input area
following {\bf S =}.
Click on {\bf Cross Reference} and then on {\bf Domains}.
The list you see contains over forty domains that belong to the
category \axiomType{ConvertibleTo InputForm}.
Thus you can use \axiomFun{function} for \axiomType{Integer},
\axiomType{Float},
\axiomType{String},
\axiomType{Complex},
\axiomType{Expression}, and so on.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserBlocksTitle}{Functions Defined with Blocks}
\newcommand{\ugUserBlocksNumber}{6.15.}
%
% =====================================================================
\begin{page}{ugUserBlocksPage}{6.15. Functions Defined with Blocks}
% =====================================================================
\beginscroll

You need not restrict yourself to functions that only fit on one line
or are written in a piece-wise manner.
The body of the function can be a block, as discussed in
\downlink{``\ugLangBlocksTitle''}{ugLangBlocksPage} in Section \ugLangBlocksNumber\ignore{ugLangBlocks}.

\labelSpace{1pc}
\xtc{
Here is a short function that swaps two elements of a list,
array or vector.
}{
\begin{spadsrc}[\bound{swap}]
swap(m,i,j) ==
  temp := m.i
  m.i := m.j
  m.j := temp
\end{spadsrc}
}
\xtc{
The significance of \userfun{swap} is that it has a destructive
effect on its first argument.
}{
\spadpaste{k := [1,2,3,4,5] \bound{k}}
}
\xtc{
}{
\spadpaste{swap(k,2,4) \free{l swap}\bound{swapk}}
}
\xtc{
You see that the second and fourth elements are interchanged.
}{
\spadpaste{k \free{swapk}}
}

\xtc{
Using this, we write a couple of different sort functions.
First, a simple bubble sort.
%-% \HDindex{sort!bubble}{ugUserBlocksPage}{6.15.}{Functions Defined with Blocks}
The operation \axiomOpFrom{\#}{List} returns the number of elements in
an aggregate.
}{
\begin{spadsrc}[\bound{bubbleSort}]
bubbleSort(m) ==
  n := #m
  for i in 1..(n-1) repeat
    for j in n..(i+1) by -1 repeat
      if m.j < m.(j-1) then swap(m,j,j-1)
  m
\end{spadsrc}
}
\xtc{
Let this be the list we want to sort.
}{
\spadpaste{m := [8,4,-3,9] \bound{m}}
}
\xtc{
This is the result of sorting.
}{
\spadpaste{bubbleSort(m) \free{m swap bubbleSort}\bound{sortm}}
}
\xtc{
Moreover, \axiom{m} is destructively changed to be the sorted version.
}{
\spadpaste{m \free{sortm}}
}

\xtc{
This function implements an insertion sort.
%-% \HDindex{sort!insertion}{ugUserBlocksPage}{6.15.}{Functions Defined with Blocks}
The basic idea is to traverse the list and insert the \eth{\axiom{i}}
element in its correct position among the \axiom{i-1} previous
elements.
Since we start at the beginning of the list, the list elements before the
\eth{\axiom{i}} element have already been placed in ascending order.
}{
\begin{spadsrc}[\bound{insertionSort}]
insertionSort(m) ==
  for i in 2..#m repeat
    j := i
    while j > 1 and m.j < m.(j-1) repeat
      swap(m,j,j-1)
      j := j - 1
  m
\end{spadsrc}
}
\xtc{
As with our bubble sort, this is a destructive function.
}{
\spadpaste{m := [8,4,-3,9] \bound{m1}}
}
\xtc{
}{
\spadpaste{insertionSort(m) \free{m1 swap insertionSort}\bound{sortm1}}
}
\xtc{
}{
\spadpaste{m \free{sortm1}}
}

Neither of the above functions is efficient for sorting large lists since
they reference elements by asking for the \eth{\axiom{j}} element of the
structure \axiom{m}.
%For lists, compute \axiom{m.(j+1) = rest(m,j).first}, and thus, starting at
%the first node of \axiom{m}, walk down to the \eth{\axiom{j}} node, then call
%\axiomFun{first}.

\xtc{
Here is a more efficient bubble sort for lists.
}{
\begin{spadsrc}[\bound{bubbleSort2}]
bubbleSort2(m: List Integer): List Integer ==
  null m => m
  l := m
  while not null (r := l.rest) repeat
     r := bubbleSort2 r
     x := l.first
     if x < r.first then
       l.first := r.first
       r.first := x
     l.rest := r
     l := l.rest
  m
\end{spadsrc}
}
\xtc{
Try it out.
}{
\spadpaste{bubbleSort2 [3,7,2]\free{bubbleSort2}}
}

This definition is both recursive and iterative, and is tricky!
Unless you are {\it really} curious about this definition,
we suggest you skip immediately to the next section.

Here are the key points in the definition.
First notice that if you are sorting a list with less than two elements,
there is nothing to do: just return the list.
This definition returns immediately if there are zero elements, and skips
the entire \axiom{while} loop if there is just one element.

The second point to realize is that on each outer iteration, the bubble sort
ensures that the minimum element is propagated leftmost.
Each iteration of the \axiom{while} loop calls \userfun{bubbleSort2}
recursively to sort all but the first element.
When finished, the minimum element is either in the first or second position.
The conditional expression ensures that it comes first.
If it is in the second, then a swap occurs.
In any case, the \axiomFun{rest} of the original list must be updated to hold
the result of the recursive call.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserFreeLocalTitle}{Free and Local Variables}
\newcommand{\ugUserFreeLocalNumber}{6.16.}
%
% =====================================================================
\begin{page}{ugUserFreeLocalPage}{6.16. Free and Local Variables}
% =====================================================================
\beginscroll

When you want to refer to a variable that is not local to your
function, use a ``\axiom{free}'' declaration.
\spadkey{free}
Variables declared to be \axiom{free}
%-% \HDindex{free variable}{ugUserFreeLocalPage}{6.16.}{Free and Local Variables}
are assumed to be defined globally
%-% \HDindex{variable!free}{ugUserFreeLocalPage}{6.16.}{Free and Local Variables}
in the
%-% \HDindex{variable!global}{ugUserFreeLocalPage}{6.16.}{Free and Local Variables}
workspace.
%-% \HDindex{global variable}{ugUserFreeLocalPage}{6.16.}{Free and Local Variables}

\labelSpace{1pc}
\xtc{
This is a global workspace variable.
}{
\spadpaste{counter := 0 \bound{counter}}
}
\xtc{
This function refers to the global \axiom{counter}.
}{
\begin{spadsrc}[\free{counter}\bound{f}]
f() ==
  free counter
  counter := counter + 1
\end{spadsrc}
}
\xtc{
The global \axiom{counter} is incremented by \axiom{1}.
}{
\spadpaste{f() \free{f}\bound{f1}}
}
\xtc{
}{
\spadpaste{counter \free{f1}}
}

Usually \Language{} can tell that you mean to refer to a global
variable and so \axiom{free} isn't always necessary.
However, for clarity and the sake of self-documentation, we encourage
you to use it.

Declare a variable to be ``\axiom{local}'' when you do not want to refer to
%-% \HDindex{variable!local}{ugUserFreeLocalPage}{6.16.}{Free and Local Variables}
a global variable by the same name.
%-% \HDindex{local variable}{ugUserFreeLocalPage}{6.16.}{Free and Local Variables}

\xtc{
This function uses \axiom{counter} as a local variable.
}{
\begin{spadsrc}[\bound{g}]
g() ==
  local counter
  counter := 7
\end{spadsrc}
}
\xtc{
Apply the function.
}{
\spadpaste{g() \free{g}}
}
\xtc{
Check that the global value of \axiom{counter} is unchanged.
}{
\spadpaste{counter\free{g f1}}
}

Parameters to a function are local variables in the function.
Even if you issue a \axiom{free} declaration for a parameter, it is
still local.

What happens if you do not declare that a variable \axiom{x} in
the body of your function is \axiom{local} or \axiom{free}?
Well, \Language{} decides on this basis:

\indent{4}
\beginitems
\item[1. ] \Language{} scans your function line-by-line, from top-to-bottom.
The right-hand side of an assignment is looked at before the left-hand
side.
\item[2. ] If \axiom{x} is referenced before it is assigned a value, it is a
\axiom{free} (global) variable.
\item[3. ] If \axiom{x} is assigned a value before it is referenced, it is a
\axiom{local} variable.
\enditems
\indent{0}

\xtc{
Set two global variables to 1.
}{
\spadpaste{a := b := 1\bound{ab1}}
}
\xtc{
Refer to \axiom{a} before it is assigned a value, but
assign a value to \axiom{b} before it is referenced.
}{
\begin{spadsrc}[\bound{hh}]
h() ==
  b := a + 1
  a := b + a
\end{spadsrc}
}
\xtc{
Can you predict this result?
}{
\spadpaste{h() \free{ab1 hh}\bound{hhh}}
}
\xtc{
How about this one?
}{
\spadpaste{[a, b] \free{hhh}}
}

What happened?
In the first line of the function body for \axiom{h}, \axiom{a} is
referenced on the right-hand side of the assignment.
Thus \axiom{a} is a free variable.
The variable \axiom{b} is not referenced in that line, but it is
assigned a value.
Thus \axiom{b} is a local variable and is given the value
\axiom{a + 1 = 2}.
In the second line, the free variable \axiom{a} is assigned the value
\axiom{b + a}which equals \axiom{2 + 1 = 3.}
This is the value returned by the function.
Since \axiom{a} was free in \userfun{h}, the global variable \axiom{a}
has value \axiom{3.}
Since \axiom{b} was local in \userfun{h}, the global variable \axiom{b}
is unchanged---it still has the value \axiom{1.}

It is good programming practice always to declare global variables.
However, by far the most common situation is to have local variables in
your functions.
No declaration is needed for this situation, but be sure to
initialize their values.

Be careful if you use free variables and you cache the value of
your function (see \downlink{``\ugUserCacheTitle''}{ugUserCachePage} in Section \ugUserCacheNumber\ignore{ugUserCache}).
Caching {\it only} checks if the values of the function arguments
are the same as in a function call previously seen.
It does not check if any of the free variables on which the
function depends have changed between function calls.
\xtc{
Turn on caching for \userfun{p}.
}{
\spadpaste{)set fun cache all p \bound{pcache}}
}
\xtc{
Define \userfun{p} to depend on the free variable \axiom{N}.
}{
\spadpaste{p(i,x) == ( free N; reduce( + , [ (x-i)**n for n in 1..N ] ) ) \free{pcache}\bound{pdef}}
}
\xtc{
Set the value of \axiom{N}.
}{
\spadpaste{N := 1 \bound{Nass}}
}
\xtc{
Evaluate \userfun{p} the first time.
}{
\spadpaste{p(0, x) \free{pdef Nass}\bound{pfirst}}
}
\xtc{
Change the value of \axiom{N}.
}{
\spadpaste{N := 2 \bound{Nass2}}
}
\xtc{
Evaluate \userfun{p} the second time.
}{
\spadpaste{p(0, x) \free{pfirst Nass2}}
}
If caching had been turned off, the second evaluation would have
reflected the changed value of \axiom{N}.
\xtc{
Turn off caching for \userfun{p}.
}{
\spadpaste{)set fun cache 0 p}
}

\Language{} does not allow {\it fluid variables}, that is, variables
%-% \HDindex{variable!fluid}{ugUserFreeLocalPage}{6.16.}{Free and Local Variables}
\spadglossSee{bound}{binding} by a function \spad{f} that can be referenced by
functions called by \spad{f}.
%-% \HDindex{fluid variable}{ugUserFreeLocalPage}{6.16.}{Free and Local Variables}

Values are passed to functions by \spadgloss{reference}: a pointer
to the value is passed rather than a copy of the value or a pointer to
a copy.

\xtc{
This is a global variable that is bound to a record object.
}{
\spadpaste{r : Record(i : Integer) := [1] \free{r}}
}
\xtc{
This function first modifies the one component of its
record argument and then rebinds the parameter to another
record.
}{
\begin{spadsrc}[\bound{resetRecord}]
resetRecord rr ==
  rr.i := 2
  rr := [10]
\end{spadsrc}
}
\xtc{
Pass \axiom{r} as an argument to \userfun{resetRecord}.
}{
\spadpaste{resetRecord r \free{r resetRecord}\bound{rr}}
}
\xtc{
The value of \axiom{r} was changed by the expression
\axiom{rr.i := 2} but not by \axiom{rr := [10]}.
}{
\spadpaste{r \free{rr}}
}

To conclude this section, we give an iterative definition of
%-% \HDindex{Fibonacci numbers}{ugUserFreeLocalPage}{6.16.}{Free and Local Variables}
a function that computes Fibonacci numbers.
This definition approximates the definition into which \Language{}
transforms the recurrence relation definition of \userfun{fib} in
\downlink{``\ugUserRecurTitle''}{ugUserRecurPage} in Section \ugUserRecurNumber\ignore{ugUserRecur}.

\xtc{
Global variables
\axiom{past} and \axiom{present} are used
to hold the last computed Fibonacci numbers.
}{
\spadpaste{past := present := 1\bound{f0}}
}
\xtc{
Global variable \axiom{index} gives the
current index of \axiom{present}.
}{
\spadpaste{index := 2\bound{f1}\free{f0}}
}
\xtc{
Here is a recurrence relation defined in terms
of these three global variables.
}{
\begin{spadsrc}[\bound{f3}\free{f2}]
fib(n) ==
  free past, present, index
  n < 3 => 1
  n = index - 1 => past
  if n < index-1 then
    (past,present) := (1,1)
    index := 2
  while (index < n) repeat
    (past,present) := (present, past+present)
    index := index + 1
  present
\end{spadsrc}
}
\xtc{
Compute the infinite stream of Fibonacci numbers.
}{
\spadpaste{fibs := [fib(n) for n in 1..] \bound{fibs}\free{f3}}
}
\xtc{
What is the 1000th Fibonacci number?
}{
\spadpaste{fibs 1000 \free{fibs}}
}

As an exercise, we suggest you write a function in an iterative
style that computes the value of the recurrence relation
\texht{$p(n) = p(n-1) - 2 \, p(n-2) + 4 \, p(n-3)$}{\axiom{p(n) = p(n-1) - 2*p(n-2) + 4*p(n-3)}}
having the initial values
\texht{$p(1) = 1,\, p(2) = 3 \hbox{ and } p(3) = 9.$}{\axiom{p(1) = 1, p(2) = 3 {\rm and} p(3) = 9.}}
How would you write the function using an element
\axiomType{OneDimensionalArray} or \axiomType{Vector}
to hold the previously computed values?

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserAnonTitle}{Anonymous Functions}
\newcommand{\ugUserAnonNumber}{6.17.}
%
% =====================================================================
\begin{page}{ugUserAnonPage}{6.17. Anonymous Functions}
% =====================================================================
\beginscroll

\beginImportant
An {\it anonymous function} is a function that is
%-% \HDindex{function!anonymous}{ugUserAnonPage}{6.17.}{Anonymous Functions}
defined
%-% \HDindex{anonymous function}{ugUserAnonPage}{6.17.}{Anonymous Functions}
by giving a list of parameters, the ``maps-to'' compound
%-% \HDindex{+-> @{\tt +->}}{ugUserAnonPage}{6.17.}{Anonymous Functions}
symbol \axiomSyntax{+->} \texht{(from the mathematical symbol
$\mapsto$)}{},
and by an expression involving the parameters, the evaluation of
which determines the return value of the function.

\centerline{{{\tt ( \subscriptIt{parm}{1}, \subscriptIt{parm}{2}, \ldots, \subscriptIt{parm}{N} ) +-> {\it expression}}}}
\endImportant

You can apply an anonymous function in several ways.
\indent{4}
\beginitems
\item[1. ] Place the anonymous function definition in parentheses
directly followed by a list of arguments.
\item[2. ] Assign the anonymous function to a variable and then
use the variable name when you would normally use a function name.
\item[3. ] Use \axiomSyntax{==} to use the anonymous function definition as
the arguments and body of a regular function definition.
\item[4. ] Have a named function contain a declared anonymous function and
use the result returned by the named function.
\enditems
\indent{0}

\beginmenu
    \menudownlink{{6.17.1. Some Examples}}{ugUserAnonExampPage}
    \menudownlink{{6.17.2. Declaring Anonymous Functions}}{ugUserAnonDeclarePage}
\endmenu
\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserAnonExampTitle}{Some Examples}
\newcommand{\ugUserAnonExampNumber}{6.17.1.}
%
% =====================================================================
\begin{page}{ugUserAnonExampPage}{6.17.1. Some Examples}
% =====================================================================
\beginscroll

Anonymous functions are particularly useful for defining functions
``on the fly.'' That is, they are handy for simple functions that
are used only in one place.
In the following examples, we show how to write some simple
anonymous functions.

\xtc{
This is a simple absolute value function.
}{
\spadpaste{x +-> if x < 0 then -x else x \bound{anon0}}
}
\xtc{
}{
\spadpaste{abs1 := \% \free{anon0}\bound{abs1}}
}
\xtc{
This function returns {\tt true} if the absolute value of
the first argument is greater than the absolute value of the
second, {\tt false} otherwise.
}{
\spadpaste{(x,y) +-> abs1(x) > abs1(y) \bound{anon1}\free{abs1}}
}
\xtc{
We use the above function to ``sort'' a list of integers.
}{
\spadpaste{sort(\%,[3,9,-4,10,-3,-1,-9,5]) \free{anon1}}
}

\xtc{
This function returns \axiom{1} if \axiom{i + j} is even, \axiom{-1} otherwise.
}{
\spadpaste{ev := ( (i,j) +-> if even?(i+j) then 1 else -1) \bound{ev}}
}
\xtc{
We create a four-by-four matrix containing \axiom{1} or \axiom{-1}
depending on whether the row plus the column index is even or not.
}{
\spadpaste{matrix([[ev(row,col) for row in 1..4] for col in 1..4]) \free{ev}}
}

\xtc{
This function returns {\tt true} if a polynomial in \axiom{x} has multiple
roots, {\tt false} otherwise.
It is defined and applied in the same expression.
}{
\spadpaste{( p +-> not one?(gcd(p,D(p,x))) )(x**2+4*x+4)}
}

\xtc{
This and the next expression are equivalent.
}{
\spadpaste{g(x,y,z) == cos(x + sin(y + tan(z)))}
}
\xtc{
The one you use is a matter of taste.
}{
\spadpaste{g == (x,y,z) +-> cos(x + sin(y + tan(z)))}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserAnonDeclareTitle}{Declaring Anonymous Functions}
\newcommand{\ugUserAnonDeclareNumber}{6.17.2.}
%
% =====================================================================
\begin{page}{ugUserAnonDeclarePage}{6.17.2. Declaring Anonymous Functions}
% =====================================================================
\beginscroll

If you declare any of the arguments you must declare all of them.
Thus,
\begin{verbatim}
(x: INT,y): FRAC INT +-> (x + 2*y)/(y - 1)
\end{verbatim}
is not legal.

\xtc{
This is an example of a fully declared anonymous
%-% \HDindex{function!declaring}{ugUserAnonDeclarePage}{6.17.2.}{Declaring Anonymous Functions}
function.
%-% \HDindex{function!anonymous!declaring}{ugUserAnonDeclarePage}{6.17.2.}{Declaring Anonymous Functions}
The output shown just indicates that the object you created is a
particular kind of map, that is, function.
}{
\spadpaste{(x: INT,y: INT): FRAC INT +-> (x + 2*y)/(y - 1)}
}
\xtc{
\Language{} allows you to declare the arguments and not declare
the return type.
}{
\spadpaste{(x: INT,y: INT) +-> (x + 2*y)/(y - 1)}
}
The return type is computed from the types of the arguments and the
body of the function.
You cannot declare the return type if you do not declare the arguments.
Therefore,
\begin{verbatim}
(x,y): FRAC INT +-> (x + 2*y)/(y - 1)
\end{verbatim}
is not legal.

\xtc{
This and the next expression are equivalent.
}{
\spadpaste{h(x: INT,y: INT): FRAC INT == (x + 2*y)/(y - 1)}
}
\xtc{
The one you use is a matter of taste.
}{
\spadpaste{h == (x: INT,y: INT): FRAC INT +-> (x + 2*y)/(y - 1)}
}

When should you declare an anonymous function?
\indent{4}
\beginitems
\item[1. ] If you use an anonymous function and \Language{} can't figure
out what you are trying to do, declare the function.
\item[2. ] If the function has nontrivial argument types or a
nontrivial return type that
\Language{} may be able to determine eventually, but you are not
willing to wait that long, declare the function.
\item[3. ] If the function will only be used for arguments of specific
types and it is not too much trouble to declare the function, do so.
\item[4. ] If you are using the anonymous function as an argument to
another function (such as \axiomFun{map} or \axiomFun{sort}),
consider declaring the function.
\item[5. ] If you define an anonymous function inside a named function,
you {\it must} declare the anonymous function.
\enditems
\indent{0}

\xtc{
This is an example of a named function for integers that returns a
function.
}{
\spadpaste{addx x == ((y: Integer): Integer +-> x + y) \bound{addx}}
}
\xtc{
We define \userfun{g} to be a function that adds \axiom{10} to its
argument.
}{
\spadpaste{g := addx 10 \free{addx}\bound{g}}
}
\xtc{
Try it out.
}{
\spadpaste{g 3 \free{g}}
}
\xtc{
}{
\spadpaste{g(-4) \free{g}}
}

%-% \HDindex{function!anonymous!restrictions}{ugUserAnonDeclarePage}{6.17.2.}{Declaring Anonymous Functions}
An anonymous function cannot be recursive: since it does not have a
name, you cannot even call it within itself!
If you place an anonymous function inside a named function, the
anonymous function must be declared.

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserDatabaseTitle}{Example: A Database}
\newcommand{\ugUserDatabaseNumber}{6.18.}
%
% =====================================================================
\begin{page}{ugUserDatabasePage}{6.18. Example: A Database}
% =====================================================================
\beginscroll

This example shows how you can use \Language{} to organize a database of
lineage data and then query the database for relationships.

\labelSpace{1.5pc}
\xtc{
The database is entered as ``assertions'' that are really
pieces of a function definition.
}{
\spadpaste{children("albert") == ["albertJr","richard","diane"]\bound{d1}}
}
\xtc{
Each piece
\axiom{children(x) == y} means
``the children of \axiom{x} are \axiom{y}''.
}{
\spadpaste{children("richard") == ["douglas","daniel","susan"]\free{d1}\bound{d2}}
}
\xtc{
This family tree thus spans four generations.
}{
\spadpaste{children("douglas") == ["dougie","valerie"]\free{d2}\bound{d3}}
}
\xtc{
Say ``no one else has children.''
}{
\spadpaste{children(x) == []\free{d3}\bound{d4}}
}

\xtc{
We need some functions for computing lineage.
Start with \axiom{childOf}.
}{
\spadpaste{childOf(x,y) == member?(x,children(y))\bound{d9}\free{d10}}
}
\xtc{
To find the \axiom{parentOf} someone,
you have to scan the database of
people applying \axiom{children}.
}{
\begin{spadsrc}[\bound{d8a}\free{d9}]
parentOf(x) ==
  for y in people repeat
    (if childOf(x,y) then return y)
  "unknown"
\end{spadsrc}
}
\xtc{
And a grandparent of \axiom{x} is just a parent of a parent of \axiom{x}.
}{
\spadpaste{grandParentOf(x) == parentOf parentOf x\bound{d8}\free{d8a}}
}
\xtc{
The grandchildren of \axiom{x}
are the people \axiom{y} such that
\axiom{x} is a grandparent of \axiom{y}.
}{
\spadpaste{grandchildren(x) == [y for y in people | grandParentOf(y) = x]\free{d7}\bound{d8}}
}
\xtc{
Suppose you want to make a list of all great-grandparents.
Well, a great-grandparent is a grandparent of a person who has children.
}{
\begin{spadsrc}[\free{d6}\bound{d7}]
greatGrandParents == [x for x in people |
  reduce(_or,[not empty? children(y) for y in grandchildren(x)],false)]
\end{spadsrc}
}
\xtc{
Define \axiom{descendants} to include the parent as well.
}{
\begin{spadsrc}[\free{d5}\bound{d6}]
descendants(x) ==
  kids := children(x)
  null kids => [x]
  concat(x,reduce(concat,[descendants(y)
    for y in kids],[]))
\end{spadsrc}
}
\xtc{
Finally, we need a list of people.
Since all people are descendants of ``albert'', let's say so.
}{
\spadpaste{people == descendants "albert"\free{d4}\bound{d5}}
}

We have used \axiomSyntax{==} to define the database and some functions to
query the database.
But no computation is done until we ask for some information.
Then, once and for all, the functions are analyzed and compiled to machine
code for run-time efficiency.
Notice that no types are given anywhere in this example.
They are not needed.

\xtc{
Who are the grandchildren of ``richard''?
}{
\spadpaste{grandchildren "richard"\bound{d10}\free{d11}}
}
\xtc{
Who are the great-grandparents?
}{
\spadpaste{greatGrandParents\bound{d11}\free{d12}}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserTriangleTitle}{Example: A Famous Triangle}
\newcommand{\ugUserTriangleNumber}{6.19.}
%
% =====================================================================
\begin{page}{ugUserTrianglePage}{6.19. Example: A Famous Triangle}
% =====================================================================
\beginscroll

In this example we write some functions that display
Pascal's triangle.
%-% \HDindex{Pascal's triangle}{ugUserTrianglePage}{6.19.}{Example: A Famous Triangle}
It demonstrates the use of piece-wise definitions and some output
operations you probably haven't seen before.

\labelSpace{1pc}
\xtc{
To make these output operations
available, we have to \spadgloss{expose} the domain
\axiomType{OutputForm}.
%-% \HDexptypeindex{OutputForm}{ugUserTrianglePage}{6.19.}{Example: A Famous Triangle}
See \downlink{``\ugTypesExposeTitle''}{ugTypesExposePage} in Section \ugTypesExposeNumber\ignore{ugTypesExpose} for more information about exposing domains
and packages.
}{
\spadpaste{)set expose add constructor OutputForm \bound{expose}}
}
\xtc{
Define the values along the first
row and any column \axiom{i}.
}{
\spadpaste{pascal(1,i) == 1 \bound{pas1}}
}
\xtc{
Define the values for when the row
and column index \axiom{i} are equal.
Repeating the argument name indicates that
the two index values are equal.
}{
\spadpaste{pascal(n,n) == 1 \bound{pas2}\free{pas1}}
}
\xtc{
}{
\begin{spadsrc}[\bound{pas3}\free{pas1 pas2}]
pascal(i,j | 1 < i and i < j) ==
   pascal(i-1,j-1)+pascal(i,j-1)
\end{spadsrc}
}
Now that we have defined the coefficients in Pascal's triangle,
let's write a couple of one-liners to display it.
\xtc{
First, define a function that gives the \eth{\axiom{n}} row.
}{
\spadpaste{pascalRow(n) == [pascal(i,n) for i in 1..n] \bound{pascalRow}\free{pas3}}
}
\xtc{
Next, we write the function \userfun{displayRow}
to display the row, separating entries by blanks and centering.
}{
\spadpaste{displayRow(n) == output center blankSeparate pascalRow(n) \free{pascalRow}\bound{displayRow}\free{expose}}
}
%
Here we have used three output operations.
Operation \axiomFunFrom{output}{OutputForm}
displays the printable form of objects on the screen,
\axiomFunFrom{center}{OutputForm} centers a printable form in the
width of the screen, and \axiomFunFrom{blankSeparate}{OutputForm} takes a list of
printable forms and inserts a blank between successive elements.
\xtc{
Look at the result.
}{
\spadpaste{for i in 1..7 repeat displayRow i \free{displayRow}}
}
Being purists, we find this less than satisfactory.
Traditionally, elements of Pascal's triangle are centered between
the left and right elements on the line above.
%
\xtc{
To fix this misalignment, we go back and
redefine \userfun{pascalRow} to right adjust the entries within the
triangle within a width of four characters.
}{
\spadpaste{pascalRow(n) == [right(pascal(i,n),4) for i in 1..n] \bound{pascalRow2}}
}
%
\xtc{
Finally let's look at our purely reformatted triangle.
}{
\spadpaste{for i in 1..7 repeat displayRow i \free{pascalRow2}\free{displayRow}}
}
\xtc{
Unexpose \axiomType{OutputForm} so we don't get unexpected
results later.
}{
\spadpaste{)set expose drop constructor OutputForm}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserPalTitle}{Example: Testing for Palindromes}
\newcommand{\ugUserPalNumber}{6.20.}
%
% =====================================================================
\begin{page}{ugUserPalPage}{6.20. Example: Testing for Palindromes}
% =====================================================================
\beginscroll


In this section we define a function \userfun{pal?} that tests whether its
%-% \HDindex{palindrome}{ugUserPalPage}{6.20.}{Example: Testing for Palindromes}
argument is a {\it palindrome}, that is, something that reads the same
backwards and forwards.
For example, the string ``Madam I'm Adam'' is a palindrome (excluding blanks
and punctuation) and so is the number \axiom{123454321.}
The definition works for any datatype that has \axiom{n} components that
are accessed by the indices \axiom{1\ldots n}.

\xtc{
Here is the definition for \userfun{pal?}.
It is simply a call to an auxiliary function called
\userfun{palAux?}.
We are following the convention of ending a function's name with
\axiomSyntax{?} if the function returns a \axiomType{Boolean} value.
}{
\spadpaste{pal? s ==  palAux?(s,1,\#s) \bound{pal}}
}
\xtc{
Here is \userfun{palAux?}.
It works by comparing elements that are equidistant from the start and end
of the object.
}{
\begin{spadsrc}[\bound{palAux}]
palAux?(s,i,j) ==
  j > i =>
    (s.i = s.j) and palAux?(s,i+1,i-1)
  true
\end{spadsrc}
}
\xtc{
Try \userfun{pal?} on some examples.
First, a string.
}{
\spadpaste{pal? "Oxford"  \free{pal palAux}}
}
\xtc{
A list of polynomials.
}{
\spadpaste{pal? [4,a,x-1,0,x-1,a,4]  \free{pal palAux}}
}
\xtc{
A list of integers from the example in
\texht{the last section.}{\downlink{``\ugUserTriangleTitle''}{ugUserTrianglePage} in Section \ugUserTriangleNumber\ignore{ugUserTriangle}.}
}{
\spadpaste{pal? [1,6,15,20,15,6,1] \free{pal palAux}}
}
\xtc{
To use \userfun{pal?} on an integer, first convert it to a string.
}{
\spadpaste{pal?(1441::String)\free{pal palAux}}
}
\xtc{
Compute an infinite stream of decimal numbers,
each of which is an obvious palindrome.
}{
\spadpaste{ones := [reduce(+,[10**j for j in 0..i]) for i in 1..]\free{pal palAux}\bound{pal5}}
}
\xtc{
How about their squares?
}{
\spadpaste{squares := [x**2 for x in ones]\free{pal5}\bound{pal6}}
}
\xtc{
Well, let's test them all!
}{
\spadpaste{[pal?(x::String) for x in squares]\free{pal6}}
}

\endscroll
\autobuttons
\end{page}
%
%
\newcommand{\ugUserRulesTitle}{Rules and Pattern Matching}
\newcommand{\ugUserRulesNumber}{6.21.}
%
% =====================================================================
\begin{page}{ugUserRulesPage}{6.21. Rules and Pattern Matching}
% =====================================================================
\beginscroll

A common mathematical formula is
\texht{\narrowDisplay{%
\log(x) + \log(y) = \log(x y) \quad\forall \, x \hbox{\ and\ } y.}}{
\axiom{log(x) + log(y) == log(x * y)} for any \axiom{x} and \axiom{y}.}
The presence of
\texht{``$\forall$''}{the word ``any''}
indicates that \axiom{x} and \axiom{y} can stand for arbitrary mathematical
expressions in the above formula.
You can use such mathematical formulas in \Language{} to specify ``rewrite
rules''.
Rewrite rules are objects in \Language{} that can be assigned to variables for
later use, often for the purpose of simplification.
Rewrite rules look like ordinary function definitions except that they are
preceded by the reserved word \axiom{rule}.
\spadkey{rule}
For example, a rewrite rule for the above formula is:
\begin{verbatim}
rule log(x) + log(y) == log(x * y)
\end{verbatim}
Like function definitions, no action is taken when a rewrite rule is issued.
Think of rewrite rules as functions that take one argument.
When a rewrite rule \axiom{A = B} is applied to an argument \axiom{f}, its
meaning is: ``rewrite every subexpression of \axiom{f} that {\it matches}
\axiom{A} by \axiom{B.}''
The left-hand side of a rewrite rule is called a \spadgloss{pattern}; its
right-side side is called its \spadgloss{substitution}.

\xtc{
Create a rewrite rule named \userfun{logrule}.
The generated symbol beginning with a \axiomSyntax{\%} is a place-holder
for any other terms that might occur in the sum.
}{
\spadpaste{logrule := rule log(x) + log(y) == log(x * y) \bound{logrule}}
}
\xtc{
Create an expression with logarithms.
}{
\spadpaste{f := log sin x + log x \bound{f}}
}
\xtc{
Apply \userfun{logrule} to \axiom{f}.
}{
\spadpaste{logrule f \free{f}\free{logrule}}
}

The meaning of our example rewrite rule is:
``for all expressions \axiom{x} and \axiom{y}, rewrite
\axiom{log(x) + log(y)} by \axiom{log(x * y)}.''
Patterns generally have both operation names
(here, \axiomFun{log} and \axiomOp{+})
and variables (here, \axiom{x} and \axiom{y}).
By default, every operation name stands for itself.
Thus \axiomFun{log}  matches only ``\axiom{log}'' and not any
other operation such as \axiomFun{sin}.
On the other hand, variables do not stand for themselves.
Rather, a variable denotes a
{\it pattern variable} that is free to match any expression whatsoever.
%-% \HDindex{pattern!variables}{ugUserRulesPage}{6.21.}{Rules and Pattern Matching}

When a rewrite rule is applied, a process called
\spadgloss{pattern matching} goes to work by systematically
scanning
%-% \HDindex{pattern!matching}{ugUserRulesPage}{6.21.}{Rules and Pattern Matching}
the subexpressions of the argument.
When a subexpression is found that ``matches'' the pattern, the subexpression
is replaced by the right-hand side of the rule.
The details of what happens will be covered later.

The customary \Language{} notation for patterns is actually a shorthand for a
longer, more general notation.
Pattern variables can be made explicit by using a percent
(\axiomSyntax{\%}) as the first character of the variable name.
To say that a name stands for itself, you can prefix that name with a quote
operator (\axiomSyntax{'}).
Although the current \Language{} parser does not let you quote an operation
name, this more general notation gives you an alternate way of giving the same
rewrite rule:
\begin{verbatim}
rule log(%x) + log(%y) == log(x * y)
\end{verbatim}
This longer notation gives you patterns that the
standard notation won't handle.
For example, the rule
\texht{\typeout{check this example}}{}
\begin{verbatim}
rule %f(c * 'x) ==  c*%f(x)
\end{verbatim}
means ``for all \axiom{f} and \axiom{c}, replace \axiom{f(y)} by
\axiom{c * f(x)} when \axiom{y} is the product of \axiom{c}
and the explicit variable \axiom{x}.''

Thus the pattern can have several adornments on the names that appear there.
Normally, all these adornments are dropped in the substitution on the
right-hand side.

To summarize:

\beginImportant
To enter a single rule in \Language{}, use the following syntax:
\spadkey{rule}
\centerline{{{\tt rule {\it leftHandSide} == {\it rightHandSide}}}}
The {\it leftHandSide} is a pattern to be matched and
the {\it rightHandSide} is its substitution.
The rule is an object of type \axiomType{RewriteRule} that can be
assigned to a variable and applied to expressions to transform them.
\endImportant

Rewrite rules can be collected
into rulesets so that a set of rules can be applied at once.
Here is another simplification rule for logarithms.
\texht{\narrowDisplay{y \log(x) = \log(x^y) \quad\forall \, x \hbox{\ and\ } y.}}{
\axiom{y * log(x) == log(x ** y)} for any \axiom{x} and \axiom{y}.}
If instead of giving a single rule following the reserved word \axiom{rule}
you give a ``pile'' of rules, you create
what is called a {\it ruleset.}
%-% \HDindex{ruleset}{ugUserRulesPage}{6.21.}{Rules and Pattern Matching}
Like rules, rulesets are objects in \Language{} and
can be assigned to variables.
You will find it useful to group commonly used rules into input files, and read
them in as needed.
\xtc{
Create a ruleset named \axiom{logrules}.
}{
\begin{spadsrc}[\bound{logrules}]
logrules := rule
  log(x) + log(y) == log(x * y)
  y * log x       == log(x ** y)
\end{spadsrc}
}
\xtc{
Again, create an expression \axiom{f} containing logarithms.
}{
\spadpaste{f := a * log(sin x) - 2 * log x \bound{f1}}
}
\xtc{
Apply the ruleset \userfun{logrules} to \axiom{f}.
}{
\spadpaste{logrules f \free{f1}\free{logrules}}
}

We have allowed pattern variables to match arbitrary expressions in the
above examples.
Often you want a variable only to match expressions
satisfying some predicate.
For example, we may want to apply the transformation
\texht{\narrowDisplay{y \log(x) = \log(x^y)}}{\axiom{y * log(x) == log(x ** y)}}
only when \axiom{y} is an integer.
%
The way to restrict a pattern variable \axiom{y} by a predicate \axiom{f(y)}
%-% \HDindex{pattern!variable!predicate}{ugUserRulesPage}{6.21.}{Rules and Pattern Matching}
is by using a vertical bar \axiomSyntax{|}, which means ``such that,'' in
%-% \HDindex{such that}{ugUserRulesPage}{6.21.}{Rules and Pattern Matching}
much the same way it is used in function definitions.
%-% \HDindex{predicate!on a pattern variable}{ugUserRulesPage}{6.21.}{Rules and Pattern Matching}
You do this only once, but at the earliest
(meaning deepest and leftmost) part of the pattern.
\xtc{
This restricts the logarithmic rule to create integer exponents only.
}{
\begin{spadsrc}[\bound{logrules2}]
logrules2 := rule
  log(x) + log(y)          == log(x * y)
  (y | integer? y) * log x == log(x ** y)
\end{spadsrc}
}
\xtc{
Compare this with the result of applying the previous set of rules.
}{
\spadpaste{f \free{f1}}
}
\xtc{
}{
\spadpaste{logrules2 f \free{f1}\free{logrules2}}
}
You should be aware that you might need to apply a function like
\spadfun{integer} within your predicate expression to actually apply
the test function.
\xtc{
Here we use \spadfun{integer} because \spad{n} has
type \spadtype{Expression Integer} but \spadfun{even?} is an operation
defined on integers.
}{
\spadpaste{evenRule := rule cos(x)**(n | integer? n and even? integer n)==(1-sin(x)**2)**(n/2) \bound{evenRule}}
}
\xtc{
Here is the application of the rule.
}{
\spadpaste{evenRule( cos(x)**2 ) \free{evenRule}}
}
\xtc{
This is an example of some of the usual identities involving products of
sines and cosines.
}{
\begin{spadsrc}[\bound{sinCosProducts}]
sinCosProducts == rule
  sin(x) * sin(y) == (cos(x-y) - cos(x + y))/2
  cos(x) * cos(y) == (cos(x-y) + cos(x+y))/2
  sin(x) * cos(y) == (sin(x-y) + sin(x + y))/2
\end{spadsrc}
}
\xtc{
}{
\spadpaste{g := sin(a)*sin(b) + cos(b)*cos(a) + sin(2*a)*cos(2*a) \bound{g}}
}
\xtc{
}{
\spadpaste{sinCosProducts g \free{sinCosProducts g}}
}

Another qualification you will often want to use is to allow a pattern to
match an identity element.
Using the pattern \axiom{x + y}, for example, neither \axiom{x} nor \axiom{y}
matches the expression \axiom{0}.
Similarly, if a pattern contains a product \axiom{x*y} or an exponentiation
\axiom{x**y}, then neither \axiom{x} or \axiom{y} matches \axiom{1}.
%
\xtc{
If identical elements were matched, pattern matching would generally loop.
Here is an expansion rule for exponentials.
}{
\spadpaste{exprule := rule exp(a + b) == exp(a) * exp(b)\bound{exprule}}
}
\xtc{
This rule would cause infinite rewriting on this if either \axiom{a} or
\axiom{b} were allowed to match \axiom{0}.
}{
\spadpaste{exprule exp x \free{exprule}}
}
%
There are occasions when you do want a pattern variable in a sum or
product to match \axiom{0} or \axiom{1}.
If so, prefix its name
with a \axiomSyntax{?} whenever it appears in a left-hand side of a rule.
For example, consider the following rule for the exponential integral:
\texht{\narrowDisplay{\int \left(\frac{y+e^x}{x}\right)\: dx = \int \frac{y}{x}\: dx + \hbox{\rm Ei}(x)
\quad\forall \, x \hbox{\ and\ } y.}}{
\axiom{integral((y + exp x)/x, x) == integral(y/x, x) + Ei x}
for any \axiom{x} and \axiom{y}.}
This rule is valid for \axiom{y = 0}.
One solution is to create a \axiomType{Ruleset} with two
rules, one with and one without \axiom{y}.
A better solution is to use an ``optional'' pattern variable.
%
\xtc{
Define rule \axiom{eirule} with
a pattern variable \axiom{?y} to indicate
that an expression may or may not occur.
}{
\spadpaste{eirule := rule integral((?y + exp x)/x,x) == integral(y/x,x) + Ei x \bound{eirule}}
}
\xtc{
Apply rule \axiom{eirule} to an integral without this term.
}{
\spadpaste{eirule integral(exp u/u, u) \free{eirule}}
}
\xtc{
Apply rule \axiom{eirule} to an integral with this term.
}{
\spadpaste{eirule integral(sin u + exp u/u, u) \free{eirule}}
}

Here is one final adornment you will find useful.
When matching a pattern of the form \axiom{x + y} to an expression containing a
long sum of the form \axiom{a +\ldots+ b}, there is no way to predict in
advance which subset of the sum  matches \axiom{x} and which matches
\axiom{y}.
Aside from efficiency, this is generally unimportant since the rule holds for
any possible combination of matches for \axiom{x} and \axiom{y}.
In some situations, however, you may want to say which pattern variable is a sum
(or product) of several terms, and which should match only a single term.
To do this, put a prefix colon \axiomSyntax{:} before the pattern variable
that you want to match multiple terms.
%-% \HDindex{pattern!variable!matching several terms}{ugUserRulesPage}{6.21.}{Rules and Pattern Matching}
%
\xtc{
The remaining rules involve operators \axiom{u} and \axiom{v}.
%-% \HDindex{operator}{ugUserRulesPage}{6.21.}{Rules and Pattern Matching}
}{
\spadpaste{u := operator 'u \bound{u}}
}
\xtc{
These definitions tell \Language{} that
\axiom{u} and \axiom{v} are formal operators to be used in expressions.
}{
\spadpaste{v := operator 'v \bound{v}}
}
\xtc{
First define \axiom{myRule}
with no restrictions on the pattern variables
\axiom{x} and \axiom{y}.
}{
\spadpaste{myRule := rule u(x + y) == u x + v y \free{u v}\bound{m}}
}
\xtc{
Apply \axiom{myRule} to an expression.
}{
\spadpaste{myRule u(a + b + c + d) \free{m}}
}
\xtc{
Define \axiom{myOtherRule} to match several terms
so that the rule gets applied recursively.
}{
\spadpaste{myOtherRule := rule u(:x + y) == u x + v y \free{u v}\bound{m2}}
}
\xtc{
Apply \axiom{myOtherRule} to the same expression.
}{
\spadpaste{myOtherRule u(a + b + c + d) \free{m2}}
}


Here are some final remarks on pattern matching.
Pattern matching provides a very useful paradigm for solving
certain classes of problems, namely, those that involve
transformations of one form to another and back.
However, it is important to recognize its limitations.
%-% \HDindex{pattern!matching!caveats}{ugUserRulesPage}{6.21.}{Rules and Pattern Matching}

First, pattern matching slows down as the number of rules you have to apply
increases.
Thus it is good practice to organize the sets of rules you use optimally so
that irrelevant rules are never included.

Second, careless use of pattern matching can lead to wrong answers.
You should avoid using pattern matching to handle hidden algebraic
relationships that can go undetected by other programs.
As a simple example, a symbol such as ``J'' can easily be used to represent
the square root of \axiom{-1} or some other important algebraic quantity.
Many algorithms branch on whether an expression is zero or not, then divide by
that expression if it is not.
If you fail to simplify an expression involving powers of
\axiom{J} to \axiom{-1,}
algorithms may incorrectly assume an expression is non-zero, take a wrong
branch, and produce a meaningless result.

Pattern matching should also not be used as a substitute for a domain.
In \Language{}, objects of one domain are transformed to objects of other
domains using well-defined \axiomFun{coerce} operations.
Pattern matching should be used on objects that are all the same type.
Thus if your application can be handled by type \axiomType{Expression} in
\Language{} and you think you need pattern matching, consider this choice
carefully.
%-% \HDexptypeindex{Expression}{ugUserRulesPage}{6.21.}{Rules and Pattern Matching}
You may well be better served by extending an existing domain
or by building a new domain of objects for your application.
\endscroll
\autobuttons
\end{page}
%