Initial population.

1 files changed, 2970 insertions, 0 deletions

diff --git a/src/hyper/pages/ug06.ht b/src/hyper/pages/ug06.ht
new file mode 100644
index 00000000..92842e31
--- /dev/null
+++ b/src/hyper/pages/ug06.ht
@@ -0,0 +1,2970 @@
+% 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}
+%