@@ -1,8118 +1,8118 @@ -% The REDUCE User's Manual --- LaTeX version. -% To create this manual, the following steps are recommended: -% latex reduce -% latex reduce -% latex reduce -% makeindex reduce -% latex reduce - -\documentstyle[11pt,makeidx]{book} - -\setlength{\parindent}{0pt} - -\setlength{\parskip}{6pt} - -\setlength{\hfuzz}{5pt} % don't complain about tiny overfull boxes -\setlength{\vfuzz}{1pt} - -\renewcommand{\sloppy}{\tolerance=9999\relax%} - \setlength{\emergencystretch}{0.2\hsize}} - -\tolerance=1000 - -\raggedbottom - -\newlength{\reduceboxwidth} -\setlength{\reduceboxwidth}{4in} - -\newlength{\redboxwidth} -\setlength{\redboxwidth}{3.5in} - -\newlength{\rboxwidth} -\setlength{\rboxwidth}{2.6in} - -\newcommand{\REDUCE}{REDUCE} -\newcommand{\RLISP}{RLISP} -\newcommand{\underscore}{\_} -\newcommand{\ttindex}[1]{{\renewcommand{\_}{\protect\underscore}% - \index{#1@{\tt #1}}}} -\newcommand{\COMPATNOTE}{{\em Compatibility Note:\ }} -% \meta{...} is an alternative sentential form in descriptions using \it. -\newcommand{\meta}[1]{\mbox{$\langle$\it#1\/$\rangle$}} - -% Close up default vertical spacings: -\setlength{\topsep}{0.5\baselineskip} % above and below environments -\setlength{\itemsep}{\topsep} -\setlength{\abovedisplayskip}{\topsep} % for "long" equations -\setlength{\belowdisplayskip}{\topsep} - -\newcommand{\key}[1]{\fbox{\sf #1}} - -\pagestyle{headings} - -\makeindex - -\begin{document} -\pagestyle{empty} -\begin{titlepage} -\vspace*{\fill} -\begin{center} - -{\Huge\bf {\REDUCE}} \\ [0.2cm] -{\LARGE\bf User's Manual\vspace{0.4cm} \\ - Version 3.6} - -\vspace{0.5in}\large\bf - -Anthony C.\ Hearn \\ -RAND \\ -Santa Monica, CA 90407-2138 - -\vspace{0.1in} - -\bf Email: reduce@rand.org - -\vspace{0.5in} - -\large\bf July 1995 - -\vspace*{2.5in} - -\bf RAND Publication CP78 (Rev. 7/95) -\end{center} -\end{titlepage} - -\newpage -\vspace*{3.0in} -\noindent Copyright \copyright 1995 RAND. All rights reserved. \\ -\mbox{}\\ -% -\noindent Registered system holders may reproduce all or any part of this -publication for internal purposes, provided that the source of the -material is clearly acknowledged, and the copyright notice is retained. - -\pagestyle{headings} -\setcounter{page}{0} -\tableofcontents - -\chapter*{Abstract} - -\addcontentsline{toc}{chapter}{Abstract} - -This document provides the user with a description of the algebraic -programming system {\REDUCE}. The capabilities of this system include: -\begin{enumerate} -\item expansion and ordering of polynomials and rational functions, -\item substitutions and pattern matching in a wide variety of forms, -\item automatic and user controlled simplification of expressions, -\item calculations with symbolic matrices, -\item arbitrary precision integer and real arithmetic, -\item facilities for defining new functions and extending program syntax, -\item analytic differentiation and integration, -\item factorization of polynomials, -\item facilities for the solution of a variety of algebraic equations, -\item facilities for the output of expressions in a variety of formats, -\item facilities for generating numerical programs from symbolic input, -\item Dirac matrix calculations of interest to high energy physicists. -\end{enumerate} - -\chapter*{Acknowledgment} - -The production of this version of the manual has been the result of the -contributions of a large number of individuals who have taken the time and -effort to suggest improvements to previous versions, and to draft new -sections. Particular thanks are due to Gerry Rayna, who provided a draft -rewrite of most of the first half of the manual. Other people who have -made significant contributions have included John Fitch, Martin Griss, -Stan Kameny, Jed Marti, Herbert Melenk, Don Morrison, Arthur Norman, -Eberhard Schr\"ufer and Larry Seward. Finally, Richard Hitt produced a {\TeX} -version of the {\REDUCE} 3.3 manual, which has been a useful guide for the -production of the {\LaTeX} version of this manual. - -\chapter{Introductory Information} - -\index{Introduction}{\REDUCE} is a system for carrying out algebraic -operations accurately, no matter how complicated the expressions become. -It can manipulate polynomials in a variety of forms, both expanding and -factoring them, and extract various parts of them as required. {\REDUCE} can -also do differentiation and integration, but we shall only show trivial -examples of this in this introduction. Other topics not -considered include the use of arrays, the definition of procedures and -operators, the specific routines for high energy physics calculations, the -use of files to eliminate repetitious typing and for saving results, and -the editing of the input text. - -Also not considered in any detail in this introduction are the many options -that are available for varying computational procedures, output forms, -number systems used, and so on. - -{\REDUCE} is designed to be an interactive system, so that the user can input -an algebraic expression and see its value before moving on to the next -calculation. For those systems that do not support interactive use, or -for those calculations, especially long ones, for which a standard script -can be defined, {\REDUCE} can also be used in batch mode. In this case, -a sequence of commands can be given to {\REDUCE} and results obtained -without any user interaction during the computation. - -In this introduction, we shall limit ourselves to the interactive use of -{\REDUCE}, since this illustrates most completely the capabilities of the -system. When {\REDUCE} is called, it begins by printing a banner message -like: -\begin{verbatim} - REDUCE 3.6, 15-Jul-95 ... -\end{verbatim} -where the version number and the system release date will change from time -to time. It then prompts the user for input by: -\begin{verbatim} - 1: -\end{verbatim} -You can now type a {\REDUCE} statement, terminated by a semicolon to indicate -the end of the expression, for example: -\begin{verbatim} - (x+y+z)^2; -\end{verbatim} -This expression would normally be followed by another character (a -\key{Return} on an ASCII keyboard) to ``wake up'' the system, which would -then input the expression, evaluate it, and return the result: -\begin{verbatim} - 2 2 2 - X + 2*X*Y + 2*X*Z + Y + 2*Y*Z + Z -\end{verbatim} -Let us review this simple example to learn a little more about the way that -{\REDUCE} works. First, we note that {\REDUCE} deals with variables, and -constants like other computer languages, but that in evaluating the former, -a variable can stand for itself. Expression evaluation normally follows -the rules of high school algebra, so the only surprise in the above example -might be that the expression was expanded. {\REDUCE} normally expands -expressions where possible, collecting like terms and ordering the -variables in a specific manner. However, expansion, ordering of variables, -format of output and so on is under control of the user, and various -declarations are available to manipulate these. - -Another characteristic of the above example is the use of lower case on -input and upper case on output. In fact, input may be in either mode, but -output is usually in lower case. To make the difference between input and -output more distinct in this manual, all expressions intended for input -will be shown in lower case and output in upper case. However, for -stylistic reasons, we represent all single identifiers in the text in -upper case. - -Finally, the numerical prompt can be used to reference the result in a -later computation. - -As a further illustration of the system features, the user should try: -\begin{verbatim} - for i:= 1:40 product i; -\end{verbatim} -The result in this case is the value of 40!, -\begin{verbatim} - 815915283247897734345611269596115894272000000000 -\end{verbatim} -You can also get the same result by saying -\begin{verbatim} - factorial 40; -\end{verbatim} -Since we want exact results in algebraic calculations, it is essential that -integer arithmetic be performed to arbitrary precision, as in the above -example. Furthermore, the {\tt FOR} statement in the above is illustrative of a -whole range of combining forms that {\REDUCE} supports for the convenience of -the user. - -Among the many options in {\REDUCE} is the use of other number systems, such -as multiple precision floating point with any specified number of digits --- -of use if roundoff in, say, the $100^{th}$ digit is all that can be tolerated. - -In many cases, it is necessary to use the results of one calculation in -succeeding calculations. One way to do this is via an assignment for a -variable, such as -\begin{verbatim} - u := (x+y+z)^2; -\end{verbatim} -If we now use {\tt U} in later calculations, the value of the right-hand -side of the above will be used. - -The results of a given calculation are also saved in the variable -{\tt WS}\ttindex{WS} (for WorkSpace), so this can be used in the next -calculation for further processing. - -For example, the expression -\begin{verbatim} - df(ws,x); -\end{verbatim} -following the previous evaluation will calculate the derivative of -{\tt (x+y+z)\verb|^|2} with respect to {\tt X}. Alternatively, -\begin{verbatim} - int(ws,y); -\end{verbatim} -would calculate the integral of the same expression with respect to y. - -{\REDUCE} is also capable of handling symbolic matrices. For example, -\begin{verbatim} - matrix m(2,2); -\end{verbatim} -declares m to be a two by two matrix, and -\begin{verbatim} - m := mat((a,b),(c,d)); -\end{verbatim} -gives its elements values. Expressions that include {\tt M} and make -algebraic sense may now be evaluated, such as {\tt 1/m} to give the -inverse, {\tt 2*m - u*m\verb|^|2} to give us another matrix and {\tt det(m)} -to give us the determinant of {\tt M}. - -{\REDUCE} has a wide range of substitution capabilities. The system knows -about elementary functions, but does not automatically invoke many of their -well-known properties. For example, products of trigonometrical functions -are not converted automatically into multiple angle expressions, but if the -user wants this, he can say, for example: -\begin{verbatim} - (sin(a+b)+cos(a+b))*(sin(a-b)-cos(a-b)) - where cos(~x)*cos(~y) = (cos(x+y)+cos(x-y))/2, - cos(~x)*sin(~y) = (sin(x+y)-sin(x-y))/2, - sin(~x)*sin(~y) = (cos(x-y)-cos(x+y))/2; -\end{verbatim} -where the tilde in front of the variables {\tt X} and {\tt Y} indicates -that the rules apply for all values of those variables. -The result of this calculation is -\begin{verbatim} - -(COS(2*A) + SIN(2*B)) -\end{verbatim} -Another very commonly used capability of the system, and an illustration -of one of the many output modes of {\REDUCE}, is the ability to output -results in a FORTRAN compatible form. Such results can then be used in a -FORTRAN based numerical calculation. This is particularly useful as a way -of generating algebraic formulas to be used as the basis of extensive -numerical calculations. - -For example, the statements -\begin{verbatim} - on fort; - df(log(x)*(sin(x)+cos(x))/sqrt(x),x,2); -\end{verbatim} -will result in the output -\begin{verbatim} - ANS=(-4.*LOG(X)*COS(X)*X**2-4.*LOG(X)*COS(X)*X+3.* - . LOG(X)*COS(X)-4.*LOG(X)*SIN(X)*X**2+4.*LOG(X)* - . SIN(X)*X+3.*LOG(X)*SIN(X)+8.*COS(X)*X-8.*COS(X)-8. - . *SIN(X)*X-8.*SIN(X))/(4.*SQRT(X)*X**2) -\end{verbatim} -These algebraic manipulations illustrate the algebraic mode of {\REDUCE}. -{\REDUCE} is based on Standard Lisp. A symbolic mode is also available for -executing Lisp statements. These statements follow the syntax of Lisp, -e.g. -\begin{verbatim} - symbolic car '(a); -\end{verbatim} -Communication between the two modes is possible. - -With this simple introduction, you are now in a position to study the -material in the full {\REDUCE} manual in order to learn just how extensive -the range of facilities really is. If further tutorial material is -desired, the seven {\REDUCE} Interactive Lessons by David R. Stoutemyer are -recommended. These are normally distributed with the system. - -\chapter{Structure of Programs} - -A {\REDUCE} program\index{Program structure} consists of a set of -functional commands which are evaluated sequentially by the computer. -These commands are built up from declarations, statements and expressions. -Such entities are composed of sequences of numbers, variables, operators, -strings, reserved words and delimiters (such as commas and parentheses), -which in turn are sequences of basic characters. - -\section{The {\REDUCE} Standard Character Set} - -\index{Character set}The basic characters which are used to build -{\REDUCE} symbols are the following: -\begin{enumerate} -\item The 26 letters {\tt a} through {\tt z} -\item The 10 decimal digits {\tt 0} through {\tt 9} -\item The special characters \_\_ ! " \$ \% ' ( ) * + , - . / : ; $<$ $>$ - = \{ \} $<$blank$>$ -\end{enumerate} -With the exception of strings and characters preceded by an -exclamation mark\index{Exclamation mark}, the case -of characters is ignored: depending of the underlying LISP -they will all be converted internally into lower case or -upper case: {\tt ALPHA}, {\tt Alpha} and {\tt alpha} -represent the same symbol. Most implementations allow you to switch -this conversion off. The operating instructions for a particular -implementation should be consulted on this point. For portability, we -shall limit ourselves to the standard character set in this exposition. - -\section{Numbers} - -\index{Number}There are several different types of numbers available in -\REDUCE. Integers consist of a signed or unsigned sequence of decimal -digits written without a decimal point, for example: -\begin{verbatim} - -2, 5396, +32 -\end{verbatim} -In principle, there is no practical limit on the number of digits -permitted as exact arithmetic is used in most implementations. (You should -however check the specific instructions for your particular system -implementation to make sure that this is true.) For example, if you ask -for the value of $2^{2000}$ you get it -displayed as a number of 603 decimal digits, taking up nine lines of -output on an interactive display. It should be borne in mind of course -that computations with such long numbers can be quite slow. - -Numbers that aren't integers are usually represented as the quotient of -two integers, in lowest terms: that is, as rational numbers. - -In essentially all versions of {\REDUCE} it is also possible (but not always -desirable!) to ask {\REDUCE} to work with floating point approximations to -numbers again, to any precision. Such numbers are called {\em real}. -\index{Real} They can be input in two ways: -\begin{enumerate} -\item as a signed or unsigned sequence of any number of decimal digits - with an embedded or trailing decimal point. -\item as in 1. followed by a decimal exponent which is written as the - letter {\tt E} followed by a signed or unsigned integer. -\end{enumerate} -e.g. {\tt 32. +32.0 0.32E2} and {\tt 320.E-1} are all representations of -32. - -The declaration {\tt SCIENTIFIC\_NOTATION}\ttindex{SCIENTIFIC\_NOTATION} -controls the output format of floating point numbers. At -the default settings, any number with five or less digits before the -decimal point is printed in a fixed-point notation, e.g., {\tt 12345.6}. -Numbers with more than five digits are printed in scientific notation, -e.g., {\tt 1.234567E+5}. Similarly, by default, any number with eleven or -more zeros after the decimal point is printed in scientific notation. To -change these defaults, {\tt SCIENTIFIC\_NOTATION} can be used in one of two -ways. {\tt SCIENTIFIC\_NOTATION} {\em m};, where {\em m\/} is a positive -integer, sets the printing format so that a number with more than {\em m\/} -digits before the decimal point, or {\em m\/} or more zeros after the -decimal point, is printed in scientific notation. {\tt SCIENTIFIC\_NOTATION} -\{{\em m,n}\}, with {\em m\/} and {\em n\/} both positive integers, sets the -format so that a number with more than {\em m\/} digits before the decimal -point, or {\em n\/} or more zeros after the decimal point is printed in -scientific notation. - -{\it CAUTION:} The unsigned part of any number\index{Number} may {\em not\/} -begin with a decimal point, as this causes confusion with the {\tt CONS} (.) -operator, i.e., NOT ALLOWED: {\tt .5 -.23 +.12}; -use {\tt 0.5 -0.23 +0.12} instead. - -\section{Identifiers} - -Identifiers\index{Identifier} in {\REDUCE} consist of one or more -alphanumeric characters (i.e. alphabetic letters or decimal -digits) the first of which must be alphabetic. The maximum number of -characters allowed is implementation dependent, although twenty-four is -permitted in most implementations. In addition, the underscore character -(\_) is considered a letter if it is {\it within} an identifier. For example, -\begin{verbatim} - a az p1 q23p a_very_long_variable -\end{verbatim} -are all identifiers, whereas -\begin{verbatim} - _a -\end{verbatim} -is not. - -A sequence of alphanumeric characters in which the first is a digit is -interpreted as a product. For example, {\tt 2ab3c} is interpreted as -{\tt 2*ab3c}. There is one exception to this: If the first letter after a -digit is {\tt E}, the system will try to interpret that part of the -sequence as a real number\index{Real}, which may fail in some cases. For -example, {\tt 2E12} is the real number $2.0*10^{12}$, {\tt 2e3c} is -2000.0*C, and {\tt 2ebc} gives an error. - -Special characters, such as $-$, *, and blank, may be used in identifiers -too, even as the first character, but each must be preceded by an -exclamation mark in input. For example: -\begin{verbatim} - light!-years d!*!*n good! morning - !$sign !5goldrings -\end{verbatim} -{\it CAUTION:} Many system identifiers have such special characters in their -names (especially * and =). If the user accidentally picks the name of one -of them for his own purposes it may have catastrophic consequences for his -{\REDUCE} run. Users are therefore advised to avoid such names. - -Identifiers are used as variables, labels and to name arrays, operators -and procedures. - -\subsection*{Restrictions} - -The reserved words listed in another section may not be used as -identifiers. No spaces may appear within an identifier, and an identifier -may not extend over a line of text. (Hyphenation of an identifier, by -using a reserved character as a hyphen before an end-of-line character is -possible in some versions of {\REDUCE}). - -\section{Variables} - -Every variable\index{Variable} is named by an identifier, and is given a -specific type. The type is of no concern to the ordinary user. Most -variables are allowed to have the default type, called {\em scalar}. -These can receive, as values, the representation of any ordinary algebraic -expression. In the absence of such a value, they stand for themselves. - -\subsection*{Reserved Variables} - -Several variables\index{Reserved variable} in {\REDUCE} have particular -properties which should not be changed by the user. These variables -include: - -\begin{list}{}{\renewcommand{\makelabel}[1]{{\tt#1}\hspace{\fill}}% - \settowidth{\labelwidth}{\tt INFINITY}% - \setlength{\labelsep}{1em}% - \settowidth{\leftmargin}{\tt INFINITY\hspace*{\labelsep}}} -\item[E] Intended to represent the base of -\ttindex{E} -the natural logarithms. {\tt log(e)}, if it occurs in an expression, is -automatically replaced by 1. If {\tt ROUNDED}\ttindex{ROUNDED} is -on, {\tt E} is replaced by the value of E to the current degree of -floating point precision\index{Numerical precision}. - -\item[I] Intended to represent the square -\ttindex{I} -root of $-1$. {\tt i\verb|^|2} is replaced by $-1$, and appropriately for higher -powers of {\tt I}. This applies only to the symbol {\tt I} used on the top -level, not as a formal parameter in a procedure, a local variable, nor in -the context {\tt for i:= ...} - -\item[INFINITY] Intended to represent $\infty$ -\ttindex{INFINITY} -in limit and power series calculations for example. Note however that the -current system does {\em not\/} do proper arithmetic on $\infty$. For example, -{\tt infinity + infinity} is {\tt 2*infinity}. - -\item[NIL] In {\REDUCE} (algebraic mode only) -taken as a synonym for zero. Therefore {\tt NIL} cannot be used as a -variable. - -\item[PI] Intended to represent the circular -\ttindex{PI} -constant. With {\tt ROUNDED} on, it is replaced by the value of $\pi$ to -the current degree of floating point precision. - -\item[T] Should not be used as a formal -\ttindex{T} -parameter or local variable in procedures, since conflict arises with the -symbolic mode meaning of T as {\em true}. -\end{list} - -Other reserved variables, such as {\tt LOW\_POW}, described in other sections, -are listed in Appendix A. - -Using these reserved variables\index{Reserved variable} inappropriately -will lead to errors. - -There are also internal variables used by {\REDUCE} that have similar -restrictions. These usually have an asterisk in their names, so it is -unlikely a casual user would use one. An example of such a variable is -{\tt K!*} used in the asymptotic command package. - -Certain words are reserved in {\REDUCE}. They may only be used in the manner -intended. A list of these is given in the section ``Reserved Identifiers''. -There are, of course, an impossibly large number of such names to keep in -mind. The reader may therefore want to make himself a copy of the list, -deleting the names he doesn't think he is likely to use by mistake. - -\section{Strings} - -Strings\index{String} are used in {\tt WRITE} statements, in other -output statements (such as error messages), and to name files. A string -consists of any number of characters enclosed in double quotes. For example: -\begin{verbatim} - "A String". -\end{verbatim} -Lower case characters within a string are not converted to upper case. - -The string {\tt ""} represents the empty string. A double quote may be -included in a string by preceding it by another double quote. Thus -{\tt "a""b"} is the string {\tt a"b}, and {\tt """"} is the string {\tt "}. - -\section{Comments} - -Text can be included in program\index{Program} listings for the -convenience of human readers, in such a way that {\REDUCE} pays no -attention to it. There are two ways to do this: - -\begin{enumerate} -\item Everything from the word {\tt COMMENT}\ttindex{COMMENT} to the next -statement terminator, normally ; or \$, is ignored. Such comments -can be placed anywhere a blank could properly appear. (Note that {\tt END} -and $>>$ are {\em not\/} treated as {\tt COMMENT} delimiters!) - -\item Everything from the symbol {\tt \%}\index{Percent sign} to the end -of the line on which it appears is ignored. Such comments can be placed -as the last part of any line. Statement terminators have no special -meaning in such comments. Remember to put a semicolon before the {\tt \%} -if the earlier part of the line is intended to be so terminated. Remember -also to begin each line of a multi-line {\tt \%} comment with a {\tt \%} -sign. -\end{enumerate} - -\section{Operators} -\label{sec-operators} - -Operators\index{Operator} in {\REDUCE} are specified by name and type. -There are two types, infix\index{Infix operator} and prefix. -\index{Prefix operator} Operators can be purely abstract, just symbols -with no properties; they can have values assigned (using {\tt :=} or -simple {\tt LET} declarations) for specific arguments; they can have -properties declared for some collection of arguments (using more general -{\tt LET} declarations); or they can be fully defined (usually by a -procedure declaration). - -Infix operators\index{Infix operator} have a definite precedence with -respect to one another, and normally occur between their arguments. -For example: -\begin{quote} -\begin{tabbing} -{\tt a + b - c} \hspace{1.5in} \= (spaces optional) \\ -{\tt x (spaces required where shown) -\end{tabbing} -\end{quote} -Spaces can be freely inserted between operators and variables or operators -and operators. They are required only where operator names are spelled out -with letters (such as the {\tt AND} in the example) and must be unambiguously -separated from another such or from a variable (like {\tt Y}). Wherever one -space can be used, so can any larger number. - -Prefix operators occur to the left of their arguments, which are written as -a list enclosed in parentheses and separated by commas, as with normal -mathematical functions, e.g., -\begin{verbatim} - cos(u) - df(x^2,x) - q(v+w) -\end{verbatim} -Unmatched parentheses, incorrect groupings of infix operators -\index{Infix operator} and the like, naturally lead to syntax errors. The -parentheses can be omitted (replaced by a space following the -operator\index{Operator} name) if the operator is unary and the argument -is a single symbol or begins with a prefix operator name: - -\begin{quote} -\begin{tabbing} -{\tt cos y} \hspace{1.75in} \= means cos(y) \\ -{\tt cos (-y)} \> -- parentheses necessary \\ -{\tt log cos y} \> means log(cos(y)) \\ -{\tt log cos (a+b)} \> means log(cos(a+b)) -\end{tabbing} -\end{quote} -but -\begin{quote} -\begin{tabbing} -{\tt cos a*b} \hspace{1.6in} \= means (cos a)*b \\ -{\tt cos -y} \> is erroneous (treated as a variable \\ -\> ``cos'' minus the variable y) -\end{tabbing} -\end{quote} -A unary prefix operator\index{Prefix operator} has a precedence -\index{Operator precedence} higher than any infix operator, including -unary infix operators. \index{Infix operator} -In other words, {\REDUCE} will always interpret {\tt cos~y + 3} as -{\tt (cos~y) + 3} rather than as {\tt cos(y + 3)}. - -Infix operators may also be used in a prefix format on input, e.g., -{\tt +(a,b,c)}. On output, however, such expressions will always be -printed in infix form (i.e., {\tt a + b + c} for this example). - -A number of prefix operators are built into the system with predefined -properties. Users may also add new operators and define their rules for -simplification. The built in operators are described in another section. - -\subsection*{Built-In Infix Operators} - -The following infix operators\index{Infix operator} are built into the -system. They are all defined internally as procedures. -\begin{verbatim} -::= where|:=|or|and|member|memq|=|neq|eq| - >=|>|<=|<|+|-|*|/|^|**|. -\end{verbatim} -These operators may be further divided into the following subclasses: -\begin{verbatim} - ::= := - ::= or|and|member|memq - ::= =|neq|eq|>=|>|<=|< - ::= where - ::= +|-|*|/|^|** - ::= . -\end{verbatim} -{\tt MEMQ} and {\tt EQ} are not used in the algebraic mode of -{\REDUCE}. They are explained in the section on symbolic mode. -{\tt WHERE} is described in the section on substitutions. - -In previous versions of {\REDUCE}, {\em not} was also defined as an infix -operator. In the present version it is a regular prefix operator, and -interchangeable with {\em null}. - -For compatibility with the intermediate language used by {\REDUCE}, each -special character infix operator\index{Infix operator} has an alternative -alphanumeric identifier associated with it. These identifiers may be used -interchangeably with the corresponding special character names on input. -This correspondence is as follows: -\begin{quote} -\begin{tabbing} -{\tt := setq} \hspace{0.5in} \= (the assignment operator) \\ -{\tt = equal} \\ -{\tt >= geq} \\ -{\tt > greaterp} \\ -{\tt <= leq} \\ -{\tt < lessp} \\ -{\tt + plus} \\ -{\tt - difference} \> (if unary, {\tt minus}) \\ -{\tt * times} \\ -{\tt / quotient} \> (if unary, {\tt recip}) \\ -{\tt \verb|^| or ** expt} \> (raising to a power) \\ -{\tt . cons} -\end{tabbing} -\end{quote} -Note: {\tt NEQ} is used to mean {\em not equal}. There is no special -symbol provided for it. - -The above operators\index{Operator} are binary, except {\tt NOT} which is -unary and {\tt +} and {\tt *} which are nary (i.e., taking an arbitrary -number of arguments). In addition, {\tt -} and {\tt /} may be used as -unary operators, e.g., /2 means the same as 1/2. Any other operator is -parsed as a binary operator using a left association rule. Thus {\tt -a/b/c} is interpreted as {\tt (a/b)/c}. There are two exceptions to this -rule: {\tt :=} and {\tt .} are right associative. Example: {\tt a:=b:=c} -is interpreted as {\tt a:=(b:=c)}. Unlike ALGOL and PASCAL, {\tt \verb|^|} is -left associative. In other words, {\tt a\verb|^|b\verb|^|c} is interpreted as -{\tt (a\verb|^|b)\verb|^|c}. - -The operators\index{Operator} {\tt $<$}, {\tt $<$=}, {\tt $>$}, {\tt $>$=} -can only be used for making comparisons between numbers. No meaning is -currently assigned to this kind of comparison between general expressions. - -Parentheses may be used to specify the order of combination. If -parentheses are omitted then this order is by the ordering of the -precedence list\index{Operator precedence} defined by the right-hand side -of the {\tt }\index{Infix operator} table -at the beginning of this section, -from lowest to highest. In other words, {\tt WHERE} has the lowest -precedence, and {\tt .} (the dot operator) the highest. - -\chapter{Expressions} - -{\REDUCE} expressions\index{Expression} may be of several types and consist -of sequences of numbers, variables, operators, left and right parentheses -and commas. The most common types are as follows: - -\section{Scalar Expressions} - -\index{Scalar}Using the arithmetic operations {\tt + - * / \verb|^|} -(power) and parentheses, scalar expressions are composed from numbers, -ordinary ``scalar'' variables (identifiers), array names with subscripts, -operator or procedure names with arguments and statement expressions. - -{\it Examples:} -\begin{verbatim} - x - x^3 - 2*y/(2*z^2 - df(x,z)) - (p^2 + m^2)^(1/2)*log (y/m) - a(5) + b(i,q) -\end{verbatim} -The symbol ** may be used as an alternative to the caret symbol (\verb+^+) -for forming powers, particularly in those systems that do not support a -caret symbol. - -Statement expressions, usually in parentheses, can also form part of -a scalar\index{Scalar} expression, as in the example -\begin{verbatim} - w + (c:=x+y) + z . -\end{verbatim} -When the algebraic value of an expression is needed, {\REDUCE} determines it, -starting with the algebraic values of the parts, roughly as follows: - -Variables and operator symbols with an argument list have the algebraic -values they were last assigned, or if never assigned stand for themselves. -However, array elements have the algebraic values they were last assigned, -or, if never assigned, are taken to be 0. - -Procedures are evaluated with the values of their actual parameters. - -In evaluating expressions, the standard rules of algebra are applied. -Unfortunately, this algebraic evaluation of an expression is not as -unambiguous as is numerical evaluation. This process is generally referred -to as ``simplification''\index{Simplification} in the sense that the -evaluation usually but not always produces a simplified form for the -expression. - -There are many options available to the user for carrying out such -simplification\index{Simplification}. If the user doesn't specify any -method, the default method is used. The default evaluation of an -expression involves expansion of the expression and collection of like -terms, ordering of the terms, evaluation of derivatives and other -functions and substitution for any expressions which have values assigned -or declared (see assignments and {\tt LET} statements). In many cases, -this is all that the user needs. - -The declarations by which the user can exercise some control over the way -in which the evaluation is performed are explained in other sections. For -example, if a real (floating point) number is encountered during -evaluation, the system will normally convert it into a ratio of two -integers. If the user wants to use real arithmetic, he can effect this by -the command {\tt on rounded;}.\ttindex{ROUNDED} Other modes for -coefficient arithmetic are described elsewhere. - -If an illegal action occurs during evaluation (such as division by zero) -or functions are called with the wrong number of arguments, and so on, an -appropriate error message is generated. -% A list of such error messages is given in an appendix. - -\section{Integer Expressions} - -\index{Integer}These are expressions which, because of the values of the -constants and variables in them, evaluate to whole numbers. - -{\it Examples:} -\begin{verbatim} - 2, 37 * 999, (x + 3)^2 - x^2 - 6*x -\end{verbatim} -are obviously integer expressions. -\begin{verbatim} - j + k - 2 * j^2 -\end{verbatim} -is an integer expression when {\tt J} and {\tt K} have values that are -integers, or if not integers are such that ``the variables and fractions -cancel out'', as in -\begin{verbatim} - k - 7/3 - j + 2/3 + 2*j^2. -\end{verbatim} - -\section{Boolean Expressions} -\label{sec-boolean} -A boolean expression\index{Boolean} returns a truth value. In the -algebraic mode of {\REDUCE}, boolean expressions have the syntactical form: -\begin{verbatim} - -\end{verbatim} -or -\begin{verbatim} - () -\end{verbatim} -or -\begin{verbatim} - - . -\end{verbatim} -Parentheses can also be used to control the precedence of expressions. - -In addition to the logical and relational operators defined earlier as -infix operators, the following boolean operators are also defined:\\ -\mbox{}\\ -\ttindex{EVENP}\ttindex{FIXP}\ttindex{FREEOF}\ttindex{NUMBERP} -\ttindex{ORDP}\ttindex{PRIMEP} -{\renewcommand{\arraystretch}{2} -\begin{tabular}{lp{\redboxwidth}} -{\tt EVENP(U)} & determines if the number {\tt U} is even or not; \\ - -{\tt FIXP(U)} & determines if the expression {\tt U} is integer or not; \\ - -{\tt FREEOF(U,V)} & determines if the expression -{\tt U} does not contain the kernel {\tt V} anywhere in its -structure; \\ - -{\tt NUMBERP(U)} & determines if {\tt U} is a number or not; \\ - -{\tt ORDP(U,V)} & determines if {\tt U} is ordered -ahead of {\tt V} by some canonical ordering (based on the expression structure -and an internal ordering of identifiers); \\ - -{\tt PRIMEP(U)} & true if {\tt U} is a prime object. \\ -\end{tabular}} - -{\it Examples:} -\begin{verbatim} - j<1 - x>0 or x=-2 - numberp x - fixp x and evenp x - numberp x and x neq 0 -\end{verbatim} -Boolean expressions can only appear directly within {\tt IF}, {\tt FOR}, -{\tt WHILE}, and {\tt UNTIL} statements, as described in other sections. -Such expressions cannot be used in place of ordinary algebraic expressions, -or assigned to a variable. - -NB: For those familiar with symbolic mode, the meaning of some of -these operators is different in that mode. For example, {\tt NUMBERP} is -true only for integers and reals in symbolic mode. - -When two or more boolean expressions are combined with {\tt AND}, they are -evaluated one by one until a {\em false\/} expression is found. The rest are -not evaluated. Thus -\begin{verbatim} - numberp x and numberp y and x>y -\end{verbatim} -does not attempt to make the {\tt x>y} comparison unless {\tt X} and {\tt Y} -are both verified to be numbers. - -Similarly, evaluation of a sequence of boolean expressions connected by -{\tt OR} stops as soon as a {\em true\/} expression is found. - -NB: In a boolean expression, and in a place where a boolean expression is -expected, the algebraic value 0 is interpreted as {\em false}, while all -other algebraic values are converted to {\em true}. So in algebraic mode -a procedure can be written for direct usage in boolean expressions, -returning say 1 or 0 as its value as in - -\begin{verbatim} - procedure polynomialp(u,x); - if den(u)=1 and deg(u,x)>=1 then 1 else 0; -\end{verbatim} - -One can then use this in a boolean construct, such as -\begin{verbatim} - if polynomialp(q,z) and not polynomialp(q,y) then ... -\end{verbatim} - -In addition, any procedure that does not have a defined return value -(for example, a block without a {\tt RETURN} statement in it) -has the boolean value {\em false}. - -\section{Equations} - -Equations\index{Equation} are a particular type of expression with the syntax - -\begin{verbatim} - = . -\end{verbatim} - -In addition to their role as boolean expressions, they can also be used as -arguments to several operators (e.g., {\tt SOLVE}), and can be -returned as values. - -Under normal circumstances, the right-hand-side of the equation is evaluated -but not the left-hand-side. If both sides are to be evaluated, the switch -{\tt EVALLHSEQP}\ttindex{EVALLHSEQP} should be turned on. - -To facilitate the handling of equations, two selectors, {\tt LHS} -\ttindex{LHS} and {\tt RHS},\ttindex{RHS} which return the left- and -right-hand sides of a equation\index{Equation} respectively, are provided. -For example, -\begin{verbatim} - lhs(a+b=c) -> a+b -and - rhs(a+b=c) -> c. -\end{verbatim} - -\section{Proper Statements as Expressions} - -Several kinds of proper statements\index{Proper statement} deliver -an algebraic or numerical result of some kind, which can in turn be used as -an expression or part of an expression. For example, an assignment -statement itself has a value, namely the value assigned. So -\begin{verbatim} - 2 * (x := a+b) -\end{verbatim} -is equal to {\tt 2*(a+b)}, as well as having the ``side-effect''\index{Side -effect} of assigning the value {\tt a+b} to {\tt X}. In context, -\begin{verbatim} - y := 2 * (x := a+b); -\end{verbatim} -sets {\tt X} to {\tt a+b} and {\tt Y} to {\tt 2*(a+b)}. - -The sections on the various proper statement\index{Proper statement} types -indicate which of these statements are also useful as expressions. - -\chapter{Lists} - -A list\index{List} is an object consisting of a sequence of other objects -(including lists themselves), separated by commas and surrounded by -braces. Examples of lists are: -\begin{verbatim} - {a,b,c} - - {1,a-b,c=d} - - {{a},{{b,c},d},e}. -\end{verbatim} -The empty list is represented as -\begin{verbatim} - {}. -\end{verbatim} - -\section{Operations on Lists}\index{List operation} - -Several operators in the system return their results as lists, and a user -can create new lists using braces and commas. To facilitate the use of -such lists, a number of operators are also available for manipulating -them. {\tt PART(,n)}\ttindex{PART} for example will return the -$n^{th}$ element of a list. {\tt LENGTH}\ttindex{LENGTH} will return the -length of a list. Several operators are also defined uniquely for lists. -For those familiar with them, these operators in fact mirror the -operations defined for Lisp lists. These operators are as follows: - -\subsection{FIRST} - -This operator\ttindex{FIRST} returns the first member of a list. An error -occurs if the argument is not a list, or the list is empty. - -\subsection{SECOND} - -{\tt SECOND}\ttindex{SECOND} returns the second member of a list. An error -occurs if the argument is not a list or has no second element. - -\subsection{THIRD} - -This operator\ttindex{THIRD} returns the third member of a list. An error -occurs if the argument is not a list or has no third element. - -\subsection{REST} - -{\tt REST}\ttindex{REST} returns its argument with the first element -removed. An error occurs if the argument is not a list, or is empty. - -\subsection{$.$ (Cons) Operator} - -This operator\ttindex{. (CONS)} adds (``conses'') an expression to the -front of a list. For example: -\begin{verbatim} - a . {b,c} -> {a,b,c}. -\end{verbatim} - -\subsection{APPEND} - -This operator\ttindex{APPEND} appends its first argument to its second to -form a new list. -{\it Examples:} -\begin{verbatim} - append({a,b},{c,d}) -> {a,b,c,d} - append({{a,b}},{c,d}) -> {{a,b},c,d}. -\end{verbatim} - -\subsection{REVERSE} - -The operator {\tt REVERSE}\ttindex{REVERSE} returns its argument with the -elements in the reverse order. It only applies to the top level list, not -any lower level lists that may occur. Examples are:\index{List operation} -\begin{verbatim} - reverse({a,b,c}) -> {c,b,a} - reverse({{a,b,c},d}) -> {d,{a,b,c}}. -\end{verbatim} - -\subsection{List Arguments of Other Operators} - -If an operator other than those specifically defined for lists is given a -single argument that is a list, then the result of this operation will be -a list in which that operator is applied to each element of the list. For -example, the result of evaluating {\tt log\{a,b,c\}} is the expression -{\tt \{LOG(A),LOG(B),LOG(C)\}}. - -There are two ways to inhibit this operator distribution. Firstly, the -switch {\tt LISTARGS},\ttindex{LISTARGS} if on, will globally inhibit -such distribution. Secondly, one can inhibit this distribution for a -specific operator by the declaration {\tt LISTARGP}.\ttindex{LISTARGP} For -example, with the declaration {\tt listargp log}, {\tt log\{a,b,c\}} would -evaluate to {\tt LOG(\{A,B,C\})}. - -If an operator has more than one argument, no such distribution occurs. - -\chapter{Statements} - -A statement\index{Statement} is any combination of reserved words and -expressions, and has the syntax \index{Proper statement} -\begin{verbatim} - ::= | -\end{verbatim} -A {\REDUCE} program consists of a series of commands which are statements -followed by a terminator:\index{Terminator}\index{Semicolon} -\index{Dollar sign} -\begin{verbatim} - ::= ;|$ -\end{verbatim} -The division of the program into lines is arbitrary. Several statements -can be on one line, or one statement can be freely broken onto several -lines. If the program is run interactively, statements ending with ; or \$ -are not processed until an end-of-line character is encountered. This -character can vary from system to system, but is normally the \key{Return} -key on an ASCII terminal. Specific systems may also use additional keys -as statement terminators. - -If a statement is a proper statement\index{Proper statement}, the -appropriate action takes place. - -Depending on the nature of the proper statement some result or response may -or may not be printed out, and the response may or may not depend on the -terminator used. - -If a statement is an expression, it is evaluated. If the terminator is a -semicolon, the result is printed. If the terminator is a dollar sign, the -result is not printed. Because it is not usually possible to know in -advance how large an expression will be, no explicit format statements are -offered to the user. However, a variety of output declarations are -available so that the output can be produced in different forms. These -output declarations are explained in Section~\ref{sec-output}. - -The following sub-sections describe the types of proper statements -\index{Proper statement} in {\REDUCE}. - -\section{Assignment Statements} - -These statements\index{Assignment} have the syntax -\begin{verbatim} - ::= := -\end{verbatim} -The {\tt } on the left side is normally the name of a variable, an -operator symbol with its list of arguments filled in, or an array name with -the proper number of integer subscript values within the array bounds. For -example: -\begin{quote} -\begin{tabbing} -{\tt a1 := b + c} \\ -{\tt h(l,m) := x-2*y} \hspace{1in} \= (where {\tt h} is an operator) \\ -{\tt k(3,5) := x-2*y} \> (where {\tt k} is a 2-dim. array) -\end{tabbing} -\end{quote} -More general assignments\index{Assignment} such as {\tt a+b := c} are also -allowed. The effect of these is explained in Section~\ref{sec-gensubs}. - -An assignment statement causes the expression on the right-hand-side to be -evaluated. If the left-hand-side is a variable, the value of the -right-hand-side is assigned to that unevaluated variable. If the -left-hand-side is an operator or array expression, the arguments of that -operator or array are evaluated, but no other simplification done. The -evaluated right-hand-side is then assigned to the resulting expression. -For example, if {\tt A} is a single-dimensional array, {\tt a(1+1) := b} -assigns the value {\tt B} to the array element {\tt a(2)}. - -If a semicolon is used as the terminator when an assignment -\index{Assignment} is issued as a command (i.e. not as a part of a group -statement or procedure or other similar construct), the left-hand side -symbol of the assignment statement is printed out, followed by a -``{\tt :=}'', followed by the value of the expression on the right. - -It is also possible to write a multiple assignment statement: -\index{Multiple assignment statement} -\begin{verbatim} - := ... := := -\end{verbatim} -In this form, each {\tt } but the last is set to the value of -the last {\tt }. If a semicolon is used as a terminator, each -expression except the last is printed followed by a ``{\tt :=}'' ending -with the value of the last expression. - - -\subsection{Set Statement} - -In some cases, it is desirable to perform an assignment in which {\em both\/} -the left- and right-hand sides of an assignment\index{Assignment} are -evaluated. In this case, the {\tt SET}\ttindex{SET} statement can be used -with the syntax: - -\begin{verbatim} - SET(,); -\end{verbatim} -For example, the statements -\begin{verbatim} - j := 23; - set(mkid(a,j),x); -\end{verbatim} -assigns the value {\tt X} to {\tt A23}. - -\section{Group Statements} - -The group statement\index{Group statement} is a construct used where -{\REDUCE} expects a single statement, but a series of actions needs to be -performed. It is formed by enclosing one or more statements (of any kind) -between the symbols {\tt $<<$} and {\tt $>>$}, separated by semicolons or -dollar signs -- it doesn't matter which. The statements are executed one -after another. - -Examples will be given in the sections on {\tt IF}\ttindex{IF} and other -types of statements in which the {\tt $<<$} \ldots {\tt $>>$} construct is -useful. - -If the last statement in the enclosed group has a value, then that is also -the value of the group statement. Care must be taken not to have a -semicolon or dollar sign after the last grouped statement, if the value of -the group is relevant: such an extra terminator causes the group to have -the value NIL or zero. - -\section{Conditional Statements} - -The conditional statement\index{Conditional statement} has the following -syntax: - -\begin{verbatim} - ::= - IF THEN [ELSE ] -\end{verbatim} - -The boolean expression is evaluated. If this is {\em true}, the first -{\tt } is executed. If it is {\em false}, the second is. - -{\it Examples:} -\begin{verbatim} - if x=5 then a:=b+c else d:=e+f - - if x=5 and numberp y - then <> - else <> -\end{verbatim} -Note the use of the group statement\index{Group statement}. -\\ -Conditional statements associate to the right; i.e.,\ttindex{IF} -\begin{verbatim} - IF THEN ELSE IF THEN ELSE -\end{verbatim} -is equivalent to: -\begin{verbatim} - IF THEN ELSE (IF THEN ELSE ) -\end{verbatim} -In addition, the construction -\begin{verbatim} - IF THEN IF THEN ELSE -\end{verbatim} -parses as -\begin{verbatim} - IF THEN (IF THEN ELSE ). -\end{verbatim} -If the value of the conditional statement\index{Conditional -statement} is of primary interest, it is often called a conditional -expression instead. Its value is the value of whichever statement was -executed. (If the executed statement has no value, the conditional -expression has no value or the value 0, depending on how it is used.) - -{\it Examples:} -\begin{verbatim} - a:=if x<5 then 123 else 456; - b:=u + v^(if numberp z then 10*z else 1) + w; -\end{verbatim} -If the value is of no concern, the {\tt ELSE} clause may be omitted if no -action is required in the {\em false\/} case. -\begin{verbatim} - if x=5 then a:=b+c; -\end{verbatim} -Note: As explained in Section~\ref{sec-boolean},a -if a scalar or numerical expression is used in place of -the boolean expression -- for example, a variable is written there -- the -{\em true\/} alternative is followed unless the expression has the value 0. - -\section{FOR Statements} - -The {\tt FOR} statement is used to define a variety of program -loops\index{Loop}. Its general syntax is as follows:\ttindex{UNTIL} -\ttindex{DO}\ttindex{PRODUCT}\ttindex{SUM}\ttindex{COLLECT}\ttindex{JOIN} -\begin{small} -\[ \mbox{\tt FOR} \left\{ \begin{array}{@{}ccc@{}} - \mbox{\tt \meta{var} := \meta{number} } \left\{ \begin{array}{@{}c@{}} - \mbox{\tt STEP \meta{number} UNTIL} \\ - \mbox{\tt :} - \end{array} - \right\} \mbox{\tt \meta{number}} \\[3mm] - \multicolumn{1}{c}{\mbox{\tt EACH \meta{var} - \(\left\{ - \begin{tabular}{@{}c@{}} - IN \\ ON - \end{tabular} - \right\}\) - \meta{list}}} - \end{array} - \right\} \mbox{\tt \meta{action} \meta{exprn}} \] -\end{small}% -% -where -\begin{center} -\tt \meta{action} ::= do|product|sum|collect|join. -\end{center} -The assignment\index{Assignment} form of the {\tt FOR} statement defines an -iteration over the indicated numerical range. If expressions that do not -evaluate to numbers are used in the designated places, an error will -result. - -The {\tt FOR EACH}\ttindex{FOR EACH} form of the {\tt FOR} statement is -designed to iterate down a list. Again, an error will occur if a list is -not used. - -The action {\tt DO}\ttindex{DO} means that {\tt } is simply -evaluated and no value kept; the statement returning 0 in this case (or no -value at the top level). {\tt COLLECT} means that the results of -evaluating {\tt } each time are linked together to make a list, -and {\tt JOIN} means that the values of {\tt } are themselves -lists that are joined to make one list (similar to {\tt CONC} in Lisp). -Finally, {\tt PRODUCT}\ttindex{PRODUCT} and {\tt SUM}\ttindex{SUM} -form the respective combined value out of the values of {\tt }. - -In all cases, {\tt } is evaluated algebraically within the -scope of the current value of {\tt }. If {\tt } is -{\tt DO}\ttindex{DO}, then nothing else happens. In other cases, {\tt -} is a binary operator that causes a result to be built up and -returned by {\tt FOR}. In those cases, the loop\index{Loop} is -initialized to a default value ({\tt 0} for {\tt SUM},\ttindex{SUM} {\tt -1} for {\tt PRODUCT},\ttindex{PRODUCT} and an empty list for the other -actions). The test for the end condition is made before any action is -taken. As in Pascal, if the variable is out of range in the assignment -case, or the {\tt } is empty in the {\tt FOR EACH}\ttindex{FOR EACH} -case, {\tt } is not evaluated at all. - -{\it Examples:} -\begin{enumerate} -\item If {\tt A}, {\tt B} have been declared to be arrays, the following -stores $5^{2}$ through $10^{2}$ in {\tt A(5)} through {\tt A(10)}, and at -the same time stores the cubes in the {\tt B} array: -\begin{verbatim} - for i := 5 step 1 until 10 do <> -\end{verbatim} -\item As a convenience, the common construction -\begin{verbatim} - STEP 1 UNTIL -\end{verbatim} -may be abbreviated to a colon. Thus, instead of the above we could write: -\begin{verbatim} - for i := 5:10 do <> -\end{verbatim} -\item The following sets {\tt C} to the sum of the squares of 1,3,5,7,9; -and {\tt D} to the expression {\tt x*(x+1)*(x+2)*(x+3)*(x+4):} -\begin{verbatim} - c := for j:=1 step 2 until 9 sum j^2; - d := for k:=0 step 1 until 4 product (x+k); -\end{verbatim} -\item The following forms a list of the squares of the elements of the list -{\tt \{a,b,c\}:}\ttindex{FOR EACH} -\begin{verbatim} - for each x in {a,b,c} collect x^2; -\end{verbatim} -\item The following forms a list of the listed squares of the elements of the -list {\tt \{a,b,c\}} -(i.e., {\tt \{\{A\verb|^|2\},\{B\verb|^|2\},\{C\verb|^|2\}\}):} -\begin{verbatim} - for each x in {a,b,c} collect {x^2}; -\end{verbatim} -\item The following also forms a list of the squares of the elements of -the list {\tt \{a,b,c\},} since the {\tt JOIN} operation joins the -individual lists into one list:\ttindex{FOR EACH} -\begin{verbatim} - for each x in {a,b,c} join {x^2}; -\end{verbatim} -\end{enumerate} -The control variable used in the {\tt FOR} statement is actually a new -variable, not related to the variable of the same name outside the {\tt -FOR} statement. In other words, executing a statement {\tt for i:=} \ldots -doesn't change the system's assumption that $i^{2} = -1$. -Furthermore, in algebraic mode, the value of the control variable is -substituted in {\tt } only if it occurs explicitly in that -expression. It will not replace a variable of the same name in the value -of that expression. For example: -\begin{verbatim} - b := a; for a := 1:2 do write b; -\end{verbatim} -prints {\tt A} twice, not 1 followed by 2. - -\section{WHILE \ldots DO} - -The\ttindex{WHILE} {\tt FOR \ldots DO}\ttindex{DO} feature allows easy -coding of a repeated operation in which the number of repetitions is known -in advance. If the criterion for repetition is more complicated, {\tt -WHILE \ldots DO} can often be used. Its syntax is: -\begin{verbatim} - WHILE DO -\end{verbatim} -The {\tt WHILE \ldots DO} controls the single statement following {\tt DO}. -If several statements are to be repeated, as is almost always the case, -they must be grouped using the $<<$ \ldots $>>$ or {\tt BEGIN \ldots END} -as in the example below. - -The {\tt WHILE} condition is tested each time {\em before\/} the action -following the {\tt DO} is attempted. If the condition is false to begin -with, the action is not performed at all. Make sure that what is to be -tested has an appropriate value initially. - -{\it Example:} - -Suppose we want to add up a series of terms, generated one by one, until -we reach a term which is less than 1/1000 in value. For our simple -example, let us suppose the first term equals 1 and each term is obtained -from the one before by taking one third of it and adding one third its -square. We would write: -\begin{verbatim} - ex:=0; term:=1; - while num(term - 1/1000) >= 0 do - <>; - ex; -\end{verbatim} -As long as {\tt TERM} is greater than or equal to ({\tt >=}) 1/1000 it will -be added to {\tt EX} and the next {\tt TERM} calculated. As soon as {\tt -TERM} becomes less than 1/1000 the {\tt WHILE} test fails and the {\tt -TERM} will not be added. - - -\section{REPEAT \ldots UNTIL} - -\ttindex{REPEAT} {\tt REPEAT \ldots UNTIL} is very similar in purpose to -{\tt WHILE \ldots DO}. Its syntax is: -\begin{verbatim} - REPEAT UNTIL -\end{verbatim} -(PASCAL users note: Only a single statement -- usually a group statement --- is allowed between the {\tt REPEAT} and the {\tt UNTIL.)} - -There are two essential differences: -\begin{enumerate} -\item The test is performed {\em after\/} the controlled statement (or group of -statements) is executed, so the controlled statement is always executed at -least once. - -\item The test is a test for when to stop rather than when to continue, so its -``polarity'' is the opposite of that in {\tt WHILE \ldots DO.} -\end{enumerate} - -As an example, we rewrite the example from the {\tt WHILE \ldots DO} section: -\begin{samepage} -\begin{verbatim} - ex:=0; term:=1; - repeat <> - until num(term - 1/1000) < 0; - ex; -\end{verbatim} -\end{samepage} -In this case, the answer will be the same as before, because in neither -case is a term added to {\tt EX} which is less than 1/1000. - -\section{Compound Statements} - -\index{Compound statement}Often the desired process can best (or only) be -described as a series of steps to be carried out one after the other. In -many cases, this can be achieved by use of the group statement\index{Group -statement}. However, each step often provides some intermediate -result, until at the end we have the final result wanted. Alternatively, -iterations on the steps are needed that are not possible with constructs -such as {\tt WHILE}\ttindex{WHILE} or {\tt REPEAT}\ttindex{REPEAT} -statements. In such cases the steps of the process must be -enclosed between the words {\tt BEGIN} and {\tt END}\ttindex{BEGIN \ldots -END} forming what is technically called a {\em block\/}\index{Block} or -{\em compound\/} statement. Such a compound statement can in fact be used -wherever a group statement appears. The converse is not true: {\tt BEGIN -\ldots END} can be used in ways that {\tt $<<$} \ldots {\tt $>>$} cannot. - -If intermediate results must be formed, local variables must be provided -in which to store them. {\em Local\/} means that their values are deleted as -soon as the block's operations are complete, and there is no conflict with -variables outside the block that happen to have the same name. Local -variables are created by a {\tt SCALAR}\ttindex{SCALAR} declaration -immediately after the {\tt BEGIN}: -\begin{verbatim} - scalar a,b,c,z; -\end{verbatim} -If more convenient, several {\tt SCALAR} declarations can be given one after -another: -\begin{verbatim} - scalar a,b,c; - scalar z; -\end{verbatim} -In place of {\tt SCALAR} one can also use the declarations -{\tt INTEGER}\ttindex{INTEGER} or {\tt REAL}\ttindex{REAL}. In the present -version of {\REDUCE} variables declared {\tt INTEGER} are expected to have -only integer values, and are initialized to 0. {\tt REAL} -variables on the other hand are currently treated as algebraic mode {\tt -SCALAR}s. - -{\it CAUTION:} {\tt INTEGER}, {\tt REAL} and {\tt SCALAR} declarations can -only be given immediately after a {\tt BEGIN}. An error will result if -they are used after other statements in a block (including {\tt ARRAY} and -{\tt OPERATOR} declarations, which are global in scope), or outside the -top-most block (e.g., at the top level). All variables declared {\tt -SCALAR} are automatically initialized to zero in algebraic mode ({\tt NIL} -in symbolic mode). - -Any symbols not declared as local variables in a block refer to the -variables of the same name in the current calling environment. In -particular, if they are not so declared at a higher level (e.g., in a -surrounding block or as parameters in a calling procedure), their values can -be permanently changed. - -Following the {\tt SCALAR}\ttindex{SCALAR} declaration(s), if any, write the -statements to be executed, one after the other, separated by delimiters -(e.g., {\tt ;} or {\tt \$}) (it doesn't matter which). However, from a -stylistic point of view, {\tt ;} is preferred. - -The last statement in the body, just before {\tt END}, need not have a -terminator (since the {\tt BEGIN \ldots END} are in a sense brackets -confining the block statements). The last statement must also be the -command {\tt RETURN}\ttindex{RETURN} followed by the variable or -expression whose value is to be the value returned by the procedure. If -the {\tt RETURN} is omitted (or nothing is written after the word -{\tt RETURN}) the procedure will have no value or the value zero, depending -on how it is used (and {\tt NIL} in symbolic mode). Remember to put a -terminator after the {\tt END}. - -{\it Example:} - -Given a previously assigned integer value for {\tt N}, the following block -will compute the Legendre polynomial of degree {\tt N} in the variable -{\tt X}: -\begin{verbatim} - begin scalar seed,deriv,top,fact; - seed:=1/(y^2 - 2*x*y +1)^(1/2); - deriv:=df(seed,y,n); - top:=sub(y=0,deriv); - fact:=for i:=1:n product i; - return top/fact - end; -\end{verbatim} - -\subsection{Compound Statements with GO TO} - -It is possible to have more complicated structures inside the {\tt BEGIN -\ldots END}\ttindex{BEGIN \ldots END} brackets than indicated in the -previous example. That the individual lines of the program need not be -assignment\index{Assignment} statements, but could be almost any other -kind of statement or command, needs no explanation. For example, -conditional statements, and {\tt WHILE}\ttindex{WHILE} and {\tt REPEAT} -\ttindex{REPEAT} constructions, have an obvious role in defining more -intricate blocks. - -If these structured constructs don't suffice, it is possible to use labels -\index{Label} and {\tt GO} {\tt TO}s\ttindex{GO TO} within a compound -statement,\index{Compound statement} and also to use {\tt RETURN} -\ttindex{RETURN} in places within the block other than just before the -{\tt END}. The following subsections discuss these matters in detail. -For many readers the following example, presenting one possible definition -of a process to calculate the factorial of {\tt N} for preassigned {\tt N} -will suffice: - -{\it Example:} -\begin{verbatim} - begin scalar m; - m:=1; - l: if n=0 then return m; - m:=m*n; - n:=n-1; - go to l - end; -\end{verbatim} - -\subsection{Labels and GO TO Statements} - -\index{Label}\ttindex{GO TO}Within a {\tt BEGIN \ldots END} compound -statement it is possible to label statements, and transfer to them out of -sequence using {\tt GO} {\tt TO} statements. Only statements on the top -level inside compound statements can be labeled, not ones inside -subsidiary constructions like {\tt $<<$} \ldots {\tt $>>$}, {\tt IF} \ldots -{\tt THEN} \ldots , {\tt WHILE} \ldots {\tt DO} \ldots , etc. - -Labels and {\tt GO TO} statements have the syntax: -\begin{verbatim} - ::= GO TO THEN ELSE IF THEN ELSE +\end{verbatim} +is equivalent to: +\begin{verbatim} + IF THEN ELSE (IF THEN ELSE ) +\end{verbatim} +In addition, the construction +\begin{verbatim} + IF THEN IF THEN ELSE +\end{verbatim} +parses as +\begin{verbatim} + IF THEN (IF THEN ELSE ). +\end{verbatim} +If the value of the conditional statement\index{Conditional +statement} is of primary interest, it is often called a conditional +expression instead. Its value is the value of whichever statement was +executed. (If the executed statement has no value, the conditional +expression has no value or the value 0, depending on how it is used.) + +{\it Examples:} +\begin{verbatim} + a:=if x<5 then 123 else 456; + b:=u + v^(if numberp z then 10*z else 1) + w; +\end{verbatim} +If the value is of no concern, the {\tt ELSE} clause may be omitted if no +action is required in the {\em false\/} case. +\begin{verbatim} + if x=5 then a:=b+c; +\end{verbatim} +Note: As explained in Section~\ref{sec-boolean},a +if a scalar or numerical expression is used in place of +the boolean expression -- for example, a variable is written there -- the +{\em true\/} alternative is followed unless the expression has the value 0. + +\section{FOR Statements} + +The {\tt FOR} statement is used to define a variety of program +loops\index{Loop}. Its general syntax is as follows:\ttindex{UNTIL} +\ttindex{DO}\ttindex{PRODUCT}\ttindex{SUM}\ttindex{COLLECT}\ttindex{JOIN} +\begin{small} +\[ \mbox{\tt FOR} \left\{ \begin{array}{@{}ccc@{}} + \mbox{\tt \meta{var} := \meta{number} } \left\{ \begin{array}{@{}c@{}} + \mbox{\tt STEP \meta{number} UNTIL} \\ + \mbox{\tt :} + \end{array} + \right\} \mbox{\tt \meta{number}} \\[3mm] + \multicolumn{1}{c}{\mbox{\tt EACH \meta{var} + \(\left\{ + \begin{tabular}{@{}c@{}} + IN \\ ON + \end{tabular} + \right\}\) + \meta{list}}} + \end{array} + \right\} \mbox{\tt \meta{action} \meta{exprn}} \] +\end{small}% +% +where +\begin{center} +\tt \meta{action} ::= do|product|sum|collect|join. +\end{center} +The assignment\index{Assignment} form of the {\tt FOR} statement defines an +iteration over the indicated numerical range. If expressions that do not +evaluate to numbers are used in the designated places, an error will +result. + +The {\tt FOR EACH}\ttindex{FOR EACH} form of the {\tt FOR} statement is +designed to iterate down a list. Again, an error will occur if a list is +not used. + +The action {\tt DO}\ttindex{DO} means that {\tt } is simply +evaluated and no value kept; the statement returning 0 in this case (or no +value at the top level). {\tt COLLECT} means that the results of +evaluating {\tt } each time are linked together to make a list, +and {\tt JOIN} means that the values of {\tt } are themselves +lists that are joined to make one list (similar to {\tt CONC} in Lisp). +Finally, {\tt PRODUCT}\ttindex{PRODUCT} and {\tt SUM}\ttindex{SUM} +form the respective combined value out of the values of {\tt }. + +In all cases, {\tt } is evaluated algebraically within the +scope of the current value of {\tt }. If {\tt } is +{\tt DO}\ttindex{DO}, then nothing else happens. In other cases, {\tt +} is a binary operator that causes a result to be built up and +returned by {\tt FOR}. In those cases, the loop\index{Loop} is +initialized to a default value ({\tt 0} for {\tt SUM},\ttindex{SUM} {\tt +1} for {\tt PRODUCT},\ttindex{PRODUCT} and an empty list for the other +actions). The test for the end condition is made before any action is +taken. As in Pascal, if the variable is out of range in the assignment +case, or the {\tt } is empty in the {\tt FOR EACH}\ttindex{FOR EACH} +case, {\tt } is not evaluated at all. + +{\it Examples:} +\begin{enumerate} +\item If {\tt A}, {\tt B} have been declared to be arrays, the following +stores $5^{2}$ through $10^{2}$ in {\tt A(5)} through {\tt A(10)}, and at +the same time stores the cubes in the {\tt B} array: +\begin{verbatim} + for i := 5 step 1 until 10 do <> +\end{verbatim} +\item As a convenience, the common construction +\begin{verbatim} + STEP 1 UNTIL +\end{verbatim} +may be abbreviated to a colon. Thus, instead of the above we could write: +\begin{verbatim} + for i := 5:10 do <> +\end{verbatim} +\item The following sets {\tt C} to the sum of the squares of 1,3,5,7,9; +and {\tt D} to the expression {\tt x*(x+1)*(x+2)*(x+3)*(x+4):} +\begin{verbatim} + c := for j:=1 step 2 until 9 sum j^2; + d := for k:=0 step 1 until 4 product (x+k); +\end{verbatim} +\item The following forms a list of the squares of the elements of the list +{\tt \{a,b,c\}:}\ttindex{FOR EACH} +\begin{verbatim} + for each x in {a,b,c} collect x^2; +\end{verbatim} +\item The following forms a list of the listed squares of the elements of the +list {\tt \{a,b,c\}} +(i.e., {\tt \{\{A\verb|^|2\},\{B\verb|^|2\},\{C\verb|^|2\}\}):} +\begin{verbatim} + for each x in {a,b,c} collect {x^2}; +\end{verbatim} +\item The following also forms a list of the squares of the elements of +the list {\tt \{a,b,c\},} since the {\tt JOIN} operation joins the +individual lists into one list:\ttindex{FOR EACH} +\begin{verbatim} + for each x in {a,b,c} join {x^2}; +\end{verbatim} +\end{enumerate} +The control variable used in the {\tt FOR} statement is actually a new +variable, not related to the variable of the same name outside the {\tt +FOR} statement. In other words, executing a statement {\tt for i:=} \ldots +doesn't change the system's assumption that $i^{2} = -1$. +Furthermore, in algebraic mode, the value of the control variable is +substituted in {\tt } only if it occurs explicitly in that +expression. It will not replace a variable of the same name in the value +of that expression. For example: +\begin{verbatim} + b := a; for a := 1:2 do write b; +\end{verbatim} +prints {\tt A} twice, not 1 followed by 2. + +\section{WHILE \ldots DO} + +The\ttindex{WHILE} {\tt FOR \ldots DO}\ttindex{DO} feature allows easy +coding of a repeated operation in which the number of repetitions is known +in advance. If the criterion for repetition is more complicated, {\tt +WHILE \ldots DO} can often be used. Its syntax is: +\begin{verbatim} + WHILE DO +\end{verbatim} +The {\tt WHILE \ldots DO} controls the single statement following {\tt DO}. +If several statements are to be repeated, as is almost always the case, +they must be grouped using the $<<$ \ldots $>>$ or {\tt BEGIN \ldots END} +as in the example below. + +The {\tt WHILE} condition is tested each time {\em before\/} the action +following the {\tt DO} is attempted. If the condition is false to begin +with, the action is not performed at all. Make sure that what is to be +tested has an appropriate value initially. + +{\it Example:} + +Suppose we want to add up a series of terms, generated one by one, until +we reach a term which is less than 1/1000 in value. For our simple +example, let us suppose the first term equals 1 and each term is obtained +from the one before by taking one third of it and adding one third its +square. We would write: +\begin{verbatim} + ex:=0; term:=1; + while num(term - 1/1000) >= 0 do + <>; + ex; +\end{verbatim} +As long as {\tt TERM} is greater than or equal to ({\tt >=}) 1/1000 it will +be added to {\tt EX} and the next {\tt TERM} calculated. As soon as {\tt +TERM} becomes less than 1/1000 the {\tt WHILE} test fails and the {\tt +TERM} will not be added. + + +\section{REPEAT \ldots UNTIL} + +\ttindex{REPEAT} {\tt REPEAT \ldots UNTIL} is very similar in purpose to +{\tt WHILE \ldots DO}. Its syntax is: +\begin{verbatim} + REPEAT UNTIL +\end{verbatim} +(PASCAL users note: Only a single statement -- usually a group statement +-- is allowed between the {\tt REPEAT} and the {\tt UNTIL.)} + +There are two essential differences: +\begin{enumerate} +\item The test is performed {\em after\/} the controlled statement (or group of +statements) is executed, so the controlled statement is always executed at +least once. + +\item The test is a test for when to stop rather than when to continue, so its +``polarity'' is the opposite of that in {\tt WHILE \ldots DO.} +\end{enumerate} + +As an example, we rewrite the example from the {\tt WHILE \ldots DO} section: +\begin{samepage} +\begin{verbatim} + ex:=0; term:=1; + repeat <> + until num(term - 1/1000) < 0; + ex; +\end{verbatim} +\end{samepage} +In this case, the answer will be the same as before, because in neither +case is a term added to {\tt EX} which is less than 1/1000. + +\section{Compound Statements} + +\index{Compound statement}Often the desired process can best (or only) be +described as a series of steps to be carried out one after the other. In +many cases, this can be achieved by use of the group statement\index{Group +statement}. However, each step often provides some intermediate +result, until at the end we have the final result wanted. Alternatively, +iterations on the steps are needed that are not possible with constructs +such as {\tt WHILE}\ttindex{WHILE} or {\tt REPEAT}\ttindex{REPEAT} +statements. In such cases the steps of the process must be +enclosed between the words {\tt BEGIN} and {\tt END}\ttindex{BEGIN \ldots +END} forming what is technically called a {\em block\/}\index{Block} or +{\em compound\/} statement. Such a compound statement can in fact be used +wherever a group statement appears. The converse is not true: {\tt BEGIN +\ldots END} can be used in ways that {\tt $<<$} \ldots {\tt $>>$} cannot. + +If intermediate results must be formed, local variables must be provided +in which to store them. {\em Local\/} means that their values are deleted as +soon as the block's operations are complete, and there is no conflict with +variables outside the block that happen to have the same name. Local +variables are created by a {\tt SCALAR}\ttindex{SCALAR} declaration +immediately after the {\tt BEGIN}: +\begin{verbatim} + scalar a,b,c,z; +\end{verbatim} +If more convenient, several {\tt SCALAR} declarations can be given one after +another: +\begin{verbatim} + scalar a,b,c; + scalar z; +\end{verbatim} +In place of {\tt SCALAR} one can also use the declarations +{\tt INTEGER}\ttindex{INTEGER} or {\tt REAL}\ttindex{REAL}. In the present +version of {\REDUCE} variables declared {\tt INTEGER} are expected to have +only integer values, and are initialized to 0. {\tt REAL} +variables on the other hand are currently treated as algebraic mode {\tt +SCALAR}s. + +{\it CAUTION:} {\tt INTEGER}, {\tt REAL} and {\tt SCALAR} declarations can +only be given immediately after a {\tt BEGIN}. An error will result if +they are used after other statements in a block (including {\tt ARRAY} and +{\tt OPERATOR} declarations, which are global in scope), or outside the +top-most block (e.g., at the top level). All variables declared {\tt +SCALAR} are automatically initialized to zero in algebraic mode ({\tt NIL} +in symbolic mode). + +Any symbols not declared as local variables in a block refer to the +variables of the same name in the current calling environment. In +particular, if they are not so declared at a higher level (e.g., in a +surrounding block or as parameters in a calling procedure), their values can +be permanently changed. + +Following the {\tt SCALAR}\ttindex{SCALAR} declaration(s), if any, write the +statements to be executed, one after the other, separated by delimiters +(e.g., {\tt ;} or {\tt \$}) (it doesn't matter which). However, from a +stylistic point of view, {\tt ;} is preferred. + +The last statement in the body, just before {\tt END}, need not have a +terminator (since the {\tt BEGIN \ldots END} are in a sense brackets +confining the block statements). The last statement must also be the +command {\tt RETURN}\ttindex{RETURN} followed by the variable or +expression whose value is to be the value returned by the procedure. If +the {\tt RETURN} is omitted (or nothing is written after the word +{\tt RETURN}) the procedure will have no value or the value zero, depending +on how it is used (and {\tt NIL} in symbolic mode). Remember to put a +terminator after the {\tt END}. + +{\it Example:} + +Given a previously assigned integer value for {\tt N}, the following block +will compute the Legendre polynomial of degree {\tt N} in the variable +{\tt X}: +\begin{verbatim} + begin scalar seed,deriv,top,fact; + seed:=1/(y^2 - 2*x*y +1)^(1/2); + deriv:=df(seed,y,n); + top:=sub(y=0,deriv); + fact:=for i:=1:n product i; + return top/fact + end; +\end{verbatim} + +\subsection{Compound Statements with GO TO} + +It is possible to have more complicated structures inside the {\tt BEGIN +\ldots END}\ttindex{BEGIN \ldots END} brackets than indicated in the +previous example. That the individual lines of the program need not be +assignment\index{Assignment} statements, but could be almost any other +kind of statement or command, needs no explanation. For example, +conditional statements, and {\tt WHILE}\ttindex{WHILE} and {\tt REPEAT} +\ttindex{REPEAT} constructions, have an obvious role in defining more +intricate blocks. + +If these structured constructs don't suffice, it is possible to use labels +\index{Label} and {\tt GO} {\tt TO}s\ttindex{GO TO} within a compound +statement,\index{Compound statement} and also to use {\tt RETURN} +\ttindex{RETURN} in places within the block other than just before the +{\tt END}. The following subsections discuss these matters in detail. +For many readers the following example, presenting one possible definition +of a process to calculate the factorial of {\tt N} for preassigned {\tt N} +will suffice: + +{\it Example:} +\begin{verbatim} + begin scalar m; + m:=1; + l: if n=0 then return m; + m:=m*n; + n:=n-1; + go to l + end; +\end{verbatim} + +\subsection{Labels and GO TO Statements} + +\index{Label}\ttindex{GO TO}Within a {\tt BEGIN \ldots END} compound +statement it is possible to label statements, and transfer to them out of +sequence using {\tt GO} {\tt TO} statements. Only statements on the top +level inside compound statements can be labeled, not ones inside +subsidiary constructions like {\tt $<<$} \ldots {\tt $>>$}, {\tt IF} \ldots +{\tt THEN} \ldots , {\tt WHILE} \ldots {\tt DO} \ldots , etc. + +Labels and {\tt GO TO} statements have the syntax: +\begin{verbatim} + ::= GO TO