diff options
author | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
---|---|---|
committer | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
commit | ab8cc85adde879fb963c94d15675783f2cf4b183 (patch) | |
tree | c202482327f474583b750b2c45dedfc4e4312b1d /src/hyper/pages/ug06.ht | |
download | open-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz |
Initial population.
Diffstat (limited to 'src/hyper/pages/ug06.ht')
-rw-r--r-- | src/hyper/pages/ug06.ht | 2970 |
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} +% |