reduce-historical/r38/doc/util/reduce.tex

% The REDUCE User's Manual --- LaTeX version.
% Codemist Version with additional material in the same volume
% To create this manual, the following steps are recommended:
% latex Codemist
% latex Codemist
% latex Codemist
% makeindex Codemist
% latex Codemist

%% Does not contain
%% bibl.tex        sl.tex

\documentclass[11pt,a4paper]{book}

\usepackage{makeidx}
\usepackage{times}
\hyphenation{unique}
\hyphenation{effect}
\hyphenation{Stand-ard}
\hyphenation{libr-ary}
\hyphenation{direct-ory}
\hyphenation{state-ment}
\hyphenation{argu-ment}
\hyphenation{oper-ators}
\hyphenation{symb-olic}
\hyphenation{needs}
\hyphenation{GVARSLAST}
\hyphenation{ODE-SOLVE}
\hyphenation{hyper-geometric}
\hyphenation{equat-ion}
\hyphenation{equat-ions}
\hyphenation{OFF}
\hyphenation{Opt-ions}
\hyphenation{execu-tion}
\hyphenation{poly-nom-ials}
\hyphenation{func-t-ions}
\hyphenation{Inte-grals}
\hyphenation{Stutt-gart}

\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$}}

% Will print out a heading in bold, and then indent the following text.
\def\indented{\list{}{
 \itemindent\listparindent
 \rightmargin\leftmargin}\item[]}
\let\endindented=\endlist
\newenvironment{describe}[1]{\par{\bf #1}\begin{indented}}{\end{indented}}

% 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}}
\newcommand{\extendedmanual}[1]{#1}

%%\pagenumbering{roman}
\pagestyle{empty}

\makeindex

\begin{document}
\pagestyle{empty}

% \s{...} is a sentential form in descriptions. Enclosed \em text in <...>
\newcommand{\s}[1] {$<${\em #1}$>$}

% \meta{...} is an alternative sentential form in descriptions using \it.
%\newcommand{\meta}[1]{\mbox{$\langle$\it#1\/$\rangle$}}

% \k{...} is a keyword. Just do in bold for the moment.
\renewcommand{\k}[1] {{\bf #1}}

% \f is a function name. Just do this as tt.
\newcommand{\f}[1] {{\tt #1}}

% An example macro for numbering and indenting examples.
\newcounter{examplectr}
\newcommand{\example}{\refstepcounter{examplectr}
\noindent{\bf Example \theexamplectr}}

\setcounter{examplectr}{0}

% \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}}
\newcommand{\extendedmanual}[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.8}

\vspace{0.5in}\large\bf

Anthony C.\ Hearn \\
Santa Monica, CA, USA

\vspace{0.1in}

\bf Email: reduce@rand.org

\vspace{0.5in}

\large\bf July 2003

\end{center}
\end{titlepage}

\newpage
\vspace*{3.0in}
\noindent Copyright \copyright 2003 Anthony C. Hearn.  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, Larry Seward and Walter Tietze.  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.8, 15-Jul-2003 ...
\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}
\extendedmanual{See also the user-contributed packages ASSIST
(chapter~\ref{ASSIST}), CAMAL (chapter~\ref{CAMAL}) and TRIGSIMP
(chapter~\ref{TRIGSIMP}).}

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<y and y=z} \> (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}
<infix operator>::= where|:=|or|and|member|memq|=|neq|eq|
                    >=|>|<=|<|+|-|*|/|^|**|.
\end{verbatim}
These operators may be further divided into the following subclasses:
\begin{verbatim}
   <assignment operator>   ::= :=
   <logical operator>      ::= or|and|member|memq
   <relational operator>   ::= =|neq|eq|>=|>|<=|<
   <substitution operator> ::= where
   <arithmetic operator>   ::= +|-|*|/|^|**
   <construction operator> ::= .
\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 <infix operator>}\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}
        <expression> <relational operator> <expression>
\end{verbatim}
or
\begin{verbatim}
        <boolean operator> (<arguments>)
\end{verbatim}
or
\begin{verbatim}
        <boolean expression> <logical operator>
        <boolean expression>.
\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, i.e., any object
other than 0 and plus or minus 1 which is only exactly divisible
by itself or a unit.
 \\
\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}
        <expression> = <expression>.
\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.  This also applies to any substitutions
made by the {\tt SUB}\ttindex{SUB} operator.  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.  Alternatively, one can use
the operator LIST to construct a list.  An important class of operations
on lists are MAP and SELECT operations.  For details, please refer to the
chapters on MAP, SELECT and the FOR command.  See also the documentation
on the ASSIST package.

To facilitate the use of
lists, a number of operators are also available for manipulating
them. {\tt PART(<list>,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{LIST}

The operator LIST is an alternative to the usage of curly brackets. LIST
accepts an arbitrary number of arguments and returns a list
of its arguments. This operator is useful in cases where operators
have to be passed as arguments. E.g.,
\begin{verbatim}
list(a,list(list(b,c),d),e);       ->  {{a},{{b,c},d},e}
\end{verbatim}

\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.

\subsection{Caveats and Examples}

Some of the natural list operations such as {\it member} or {\it delete}
are available only after loading the package {\it ASSIST}.

Please note that a non-list as second argument to CONS
(a "dotted pair" in LISP terms) is not allowed
and causes an "invalid as list" error.
\begin{verbatim}
 a := 17 . 4;

***** 17 4 invalid as list
\end{verbatim}
Also, the initialization of a scalar variable is not the empty list --
one has to set list type variables explicitly, as in the following
example:
\begin{verbatim}
 load_package assist;

 procedure lotto (n,m);
  begin scalar list_1_n, luckies, hit;
     list_1_n := {};
     luckies := {};
     for k:=1:n do list_1_n := k . list_1_n;
     for k:=1:m do
       << hit := part(list_1_n,random(n-k+1) + 1);
          list_1_n := delete(hit,list_1_n);
          luckies := hit . luckies >>;
     return luckies;
  end;                             % In Germany, try lotto (49,6);
\end{verbatim}

{\it Another example:} Find all coefficients of a multivariate
polynomial with respect to a list of variables:

\begin{verbatim}
procedure allcoeffs(q,lis); % q : polynomial, lis: list of vars
   allcoeffs1 (list q,lis);

procedure allcoeffs1(q,lis);
  if lis={} then q else
    allcoeffs1(foreach qq in q join coeff(qq,first lis),rest lis);

\end{verbatim}

\chapter{Statements}

A statement\index{Statement} is any combination of reserved words and
expressions, and has the syntax \index{Proper statement}
\begin{verbatim}
        <statement> ::= <expression>|<proper statement>
\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}
        <terminator> ::= ;|$
\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}
    <assignment statement> ::= <expression> := <expression>
\end{verbatim}
The {\tt <expression>} 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}
    <expression> := ... := <expression> := <expression>
\end{verbatim}
In this form, each {\tt <expression>} but the last is set to the value of
the last {\tt <expression>}.  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(<expression>,<expression>);
\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}
 <conditional statement> ::=
    IF <boolean expression> THEN <statement> [ELSE <statement>]
\end{verbatim}

The boolean expression is evaluated. If this is {\em true}, the first
{\tt <statement>} 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 <<ff:=q1; a:=b+c>>
           else <<ff:=q2; d:=e+f>>
\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 <a> THEN <b> ELSE IF <c> THEN <d> ELSE <e>
\end{verbatim}
is equivalent to:
\begin{verbatim}
        IF <a> THEN <b> ELSE (IF <c> THEN <d> ELSE <e>)
\end{verbatim}
In addition, the construction
\begin{verbatim}
        IF <a> THEN IF <b> THEN <c> ELSE <d>
\end{verbatim}
parses as
\begin{verbatim}
        IF <a> THEN (IF <b> THEN <c> ELSE <d>).
\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 <exprn>} 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 <exprn>} each time are linked together to make a list,
and {\tt JOIN} means that the values of {\tt <exprn>} 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 <exprn>}.

In all cases, {\tt <exprn>} is evaluated algebraically within the
scope of the current value of {\tt <var>}.  If {\tt <action>} is
{\tt DO}\ttindex{DO}, then nothing else happens.  In other cases, {\tt
<action>} 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 <list>} is empty in the {\tt FOR EACH}\ttindex{FOR EACH}
case, {\tt <exprn>} 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 <<a(i):=i^2; b(i):=i^3>>
\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 <<a(i):=i^2; b(i):=i^3>>
\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 <exprn>} 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 <boolean expression> DO <statement>
\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 := ex+term; term:=(term + term^2)/3>>;
        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 <statement> UNTIL <boolean expression>
\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 <<ex := ex+term; term := (term + term^2)/3>>
           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 statement> ::= GO TO <label> | GOTO <label>
        <label> ::= <identifier>
        <labeled statement> ::= <label>:<statement>
\end{verbatim}
Note that statement names cannot be used as labels.

While {\tt GO TO} is an unconditional transfer, it is frequently used
in conditional statements such as
\begin{verbatim}
        if x>5 then go to abcd;
\end{verbatim}
giving the effect of a conditional transfer.

Transfers using {\tt GO TO}s can only occur within the block in which the
{\tt GO TO} is used.  In other words, you cannot transfer from an inner
block to an outer block using a {\tt GO TO}.  However, if a group statement
occurs within a compound statement, it is possible to jump out of that group
statement to a point within the compound statement using a {\tt GO TO}.

\subsection{RETURN Statements}

The value corresponding to a {\tt BEGIN \ldots END} compound statement,
\ttindex{BEGIN \ldots END} such as a procedure body, is normally 0 ({\tt
NIL} in symbolic mode).  By executing a {\tt RETURN}\ttindex{RETURN}
statement in the compound statement a different value can be returned.
After a {\tt RETURN} statement is executed, no further statements within
the compound statement are executed.

{\tt Examples:}
\begin{verbatim}
        return x+y;
        return m;
        return;
\end{verbatim}
Note that parentheses are not required around the {\tt x+y}, although they
are permitted.  The last example is equivalent to {\tt return 0} or {\tt
return nil}, depending on whether the block is used as part of an
expression or not.

Since {\tt RETURN}\ttindex{RETURN} actually moves up only one
block\index{Block} level, in a sense the casual user is not expected to
understand, we tabulate some cautions concerning its use.
\begin{enumerate}
\item {\tt RETURN} can be used on the top level inside the compound
statement, i.e. as one of the statements bracketed together by the {\tt
BEGIN \ldots END}\ttindex{BEGIN \ldots END}

\item {\tt RETURN} can be used within a top level {\tt $<<$} \ldots {\tt
$>>$} construction within the compound statement.  In this case, the {\tt
RETURN} transfers control out of both the group statement and the compound
statement.

\item {\tt RETURN} can be used within an {\tt IF} \ldots {\tt THEN} \ldots
{\tt ELSE} \ldots on the top level within the compound statement.
\end{enumerate}
NOTE:  At present, there is no construct provided to permit early
termination of a {\tt FOR}\ttindex{FOR}, {\tt WHILE}\ttindex{WHILE},
or {\tt REPEAT}\ttindex{REPEAT} statement.  In particular, the use of
{\tt RETURN} in such cases results in a syntax error.  For example,
\begin{verbatim}
        begin scalar y;
           y := for i:=0:99 do if a(i)=x then return b(i);
           ...
\end{verbatim}
will lead to an error.

\chapter{Commands and Declarations}

A command\index{Command} is an order to the system to do something.  Some
commands cause visible results (such as calling for input or output);
others, usually called declarations\index{Declaration}, set options,
define properties of variables, or define procedures.  Commands are
formally defined as a statement followed by a terminator
\begin{verbatim}
        <command> ::= <statement> <terminator>
        <terminator> ::= ;|$
\end{verbatim}
Some {\REDUCE} commands and declarations are described in the following
sub-sections.

\section{Array Declarations}

Array\ttindex{ARRAY} declarations in {\REDUCE} are similar to FORTRAN
dimension statements.  For example:
\begin{verbatim}
        array a(10),b(2,3,4);
\end{verbatim}
Array indices each range from 0 to the value declared. An element of an
array is referred to in standard FORTRAN notation, e.g. {\tt A(2)}.

We can also use an expression for defining an array bound, provided the
value of the expression is a positive integer. For example, if {\tt X} has the
value 10 and {\tt Y} the value 7 then
{\tt array c(5*x+y)} is the same as {\tt array c(57)}.

If an array is referenced by an index outside its range, an error occurs.
If the array is to be one-dimensional, and the bound a number or a variable
(not a more general expression) the parentheses may be omitted:
\begin{verbatim}
        array a 10, c 57;
\end{verbatim}
The operator {\tt LENGTH}\ttindex{LENGTH} applied to an array name
returns a list of its dimensions.

All array elements are initialized to 0 at declaration time. In other words,
an array element has an {\em instant evaluation\/}\index{Instant evaluation}
property and cannot stand for itself.  If this is required, then an
operator should be used instead.

Array declarations can appear anywhere in a program. Once a symbol is
declared to name an array, it can not also be used as a variable, or to
name an operator or a procedure. It can however be re-declared to be an
array, and its size may be changed at that time. An array name can also
continue to be used as a parameter in a procedure, or a local variable in
a compound statement, although this use is not recommended, since it can
lead to user confusion over the type of the variable.

Arrays once declared are global in scope, and so can then be referenced
anywhere in the program. In other words, unlike arrays in most other
languages, a declaration within a block (or a procedure) does not limit
the scope of the array to that block, nor does the array go away on
exiting the block (use {\tt CLEAR} instead for this purpose).

\section{Mode Handling Declarations}\index{Mode}

The {\tt ON}\ttindex{ON} and {\tt OFF}\ttindex{OFF} declarations are
available to the user for controlling various system options.  Each option
is represented by a {\em switch\/}\index{Switch} name. {\tt ON} and {\tt OFF}
take a list of switch names as argument and turn them on and off
respectively, e.g.,
\begin{verbatim}
       on time;
\end{verbatim}
causes the system to print a message after each command giving the elapsed
CPU time since the last command, or since {\tt TIME}\ttindex{TIME} was
last turned off, or the session began.  Another useful switch with
interactive use is {\tt DEMO},\ttindex{DEMO} which causes the system to
pause after each command in a file (with the exception of comments)
until a \key{Return} is typed on the terminal.  This
enables a user to set up a demonstration file and step through it command
by command.

As with most declarations, arguments to {\tt ON} and {\tt OFF} may be
strung together separated by commas.  For example,
\begin{verbatim}
        off time,demo;
\end{verbatim}
will turn off both the time messages and the demonstration switch.

We note here that while most {\tt ON} and {\tt OFF} commands are obeyed
almost instantaneously, some trigger time-consuming actions such as
reading in necessary modules from secondary storage.

A diagnostic message is printed if {\tt ON}\ttindex{ON} or {\tt OFF}
\ttindex{OFF} are used with a switch that is not known to the system.  For
example, if you misspell {\tt DEMO} and type
\begin{verbatim}
     on demq;
\end{verbatim}
you will get the message\index{Switch}
\begin{verbatim}
        ***** DEMQ not defined as switch.
\end{verbatim}

\section{END}

The identifier {\tt END}\ttindex{END} has two separate uses.

1) Its use in a {\tt BEGIN \ldots END} bracket has been discussed in
connection with compound statements.

2) Files to be read using {\tt IN} should end with an extra {\tt END};
command.  The reason for this is explained in the section on the {\tt IN}
command.  This use of {\tt END} does not allow an immediately
preceding {\tt END} (such as the {\tt END} of a procedure definition), so
we advise using {\tt ;END;} there.

%3) A command {\tt END}; entered at the top level transfers control to the
%Lisp system\index{Lisp} which is the host of the {\REDUCE} system.  All
%files opened by {\tt IN} or {\tt OUT} statements are closed in the
%process.  {\tt END;} does not stop {\REDUCE}.  Those familiar with Lisp can
%experiment with typing identifiers and ({\tt <function name> <argument
%list>}) lists to see the value returned by Lisp. (No terminators, other
%than the RETURN key, should be used.) The data structures created during
%the {\REDUCE} run are accessible.

%You remain in this Lisp mode until you explicitly re-enter {\REDUCE} by
%saying {\tt (BEGIN)} at the Lisp top level.  In most systems, a Lisp error
%also returns you to {\REDUCE} (exceptions are noted in the operating
%instructions for your particular {\REDUCE} implementation).  In either
%case, you will return to {\REDUCE} in the same mode, algebraic or
%symbolic, that you were in before the {\tt END};.  If you are in
%Lisp mode\index{Lisp mode} by mistake -- which is usually the case,
%the result of typing more {\tt END}s\ttindex{END} than {\tt BEGIN}s --
%type {\tt (BEGIN)} in parentheses and hit the RETURN key.

\section{BYE Command}\ttindex{BYE}

The command {\tt BYE}; (or alternatively {\tt QUIT};)\ttindex{QUIT}
stops the execution
of {\REDUCE}, closes all open output files, and returns you to the calling
program (usually the operating system).  Your {\REDUCE} session is
normally destroyed.

\section{SHOWTIME Command}\ttindex{SHOWTIME}

{\tt SHOWTIME}; prints the elapsed time since the last call of this
command or, on its first call, since the current {\REDUCE} session began.
The time is normally given in milliseconds and gives the time as measured
by a system clock.  The operations covered by this measure are system
dependent.

\section{DEFINE Command}

The command {\tt DEFINE}\ttindex{DEFINE} allows a user to supply a new name for
any identifier or replace it by any well-formed expression.  Its argument
is a list of expressions of the form
\begin{verbatim}
        <identifier> = <number>|<identifier>|<operator>|
                        <reserved word>|<expression>
\end{verbatim}

{\it Example:}
\begin{verbatim}
        define be==,x=y+z;
\end{verbatim}
means that {\tt BE} will be interpreted as an equal sign, and {\tt X}
as the expression {\tt y+z} from then on.  This renaming is done at parse
time, and therefore takes precedence over any other replacement declared
for the same identifier.  It stays in effect until the end of the
{\REDUCE} run.

The identifiers {\tt ALGEBRAIC} and {\tt SYMBOLIC} have properties which
prevent {\tt DEFINE}\ttindex{DEFINE} from being used on them.  To define
{\tt ALG} to be a synonym for {\tt ALGEBRAIC}, use the more complicated
construction
\begin{verbatim}
        put('alg,'newnam,'algebraic);
\end{verbatim}
\chapter{Built-in Prefix Operators}
In the following subsections are descriptions of the most useful prefix
\index{Prefix}
operators built into {\REDUCE} that are not defined in other sections (such
as substitution operators). Some are fully defined internally as
procedures; others are more nearly abstract operators, with only some of
their properties known to the system.

In many cases, an operator is described by a prototypical header line as
follows. Each formal parameter is given a name and followed by its allowed
type. The names of classes referred to in the definition are printed in
lower case, and parameter names in upper case. If a parameter type is not
commonly used, it may be a specific set enclosed in brackets {\tt \{} \ldots
{\tt \}}.
Operators that accept formal parameter lists of arbitrary length have the
parameter and type class enclosed in square brackets indicating that zero
or more occurrences of that argument are permitted. Optional parameters
and their type classes are enclosed in angle brackets.

\section{Numerical Operators}\index{Numerical operator}
{\REDUCE} includes a number of functions that are analogs of those found
in most numerical systems.  With numerical arguments, such functions
return the expected result.  However, they may also be called with
non-numerical arguments.  In such cases, except where noted, the system
attempts to simplify the expression as far as it can.  In such cases, a
residual expression involving the original operator usually remains.
These operators are as follows:

\subsection{ABS}
{\tt ABS}\ttindex{ABS} returns the absolute value
of its single argument, if that argument has a numerical value.
A non-numerical argument is returned as an absolute value, with an overall
numerical coefficient taken outside the absolute value operator. For example:
\begin{verbatim}
        abs(-3/4)     ->  3/4
        abs(2a)       ->  2*ABS(A)
        abs(i)        ->  1
        abs(-x)       ->  ABS(X)
\end{verbatim}

\subsection{CEILING}\ttindex{CEILING}
This operator returns the ceiling (i.e., the least integer greater than
the given argument) if its single argument has a numerical value.  A
non-numerical argument is returned as an expression in the original
operator.  For example:

\begin{verbatim}
        ceiling(-5/4) ->  -1
        ceiling(-a)   ->  CEILING(-A)
\end{verbatim}

\subsection{CONJ}\ttindex{CONJ}
This returns the complex conjugate
of an expression, if that argument has an numerical value.  A
non-numerical argument is returned as an expression in the operators
{\tt REPART}\ttindex{REPART} and {\tt IMPART}\ttindex{IMPART}. For example:
\begin{verbatim}
        conj(1+i)     -> 1-I
        conj(a+i*b)   -> REPART(A) - REPART(B)*I - IMPART(A)*I
                         - IMPART(B)
\end{verbatim}

\subsection{FACTORIAL}\ttindex{FACTORIAL}

If the single argument of {\tt FACTORIAL} evaluates to a non-negative
integer, its factorial is returned.  Otherwise an expression involving
{\tt FACTORIAL} is returned. For example:
\begin{verbatim}
        factorial(5)  ->  120
        factorial(a)  ->  FACTORIAL(A)
\end{verbatim}

\subsection{FIX}\ttindex{FIX}
This operator returns the fixed value (i.e., the integer part of
the given argument) if its single argument has a numerical value.  A
non-numerical argument is returned as an expression in the original
operator.  For example:

\begin{verbatim}
        fix(-5/4)   ->  -1
        fix(a)      ->  FIX(A)
\end{verbatim}

\subsection{FLOOR}\ttindex{FLOOR}
This operator returns the floor (i.e., the greatest integer less than
the given argument) if its single argument has a numerical value.  A
non-numerical argument is returned as an expression in the original
operator.  For example:

\begin{verbatim}
        floor(-5/4)   ->  -2
        floor(a)      ->  FLOOR(A)
\end{verbatim}

\subsection{IMPART}\ttindex{IMPART}
This operator returns the imaginary part of an expression, if that argument
has an numerical value.  A non-numerical argument is returned as an expression
in the operators {\tt REPART}\ttindex{REPART} and {\tt IMPART}.  For example:
\begin{verbatim}
        impart(1+i)   -> 1
        impart(a+i*b) -> REPART(B) + IMPART(A)
\end{verbatim}

\subsection{MAX/MIN}

{\tt MAX} and {\tt MIN}\ttindex{MAX}\ttindex{MIN} can take an arbitrary
number of expressions as their arguments.  If all arguments evaluate to
numerical values, the maximum or minimum of the argument list is returned.
If any argument is non-numeric, an appropriately reduced expression is
returned.  For example:
\begin{verbatim}
        max(2,-3,4,5) ->  5
        min(2,-2)     ->  -2.
        max(a,2,3)    ->  MAX(A,3)
        min(x)        ->  X
\end{verbatim}
{\tt MAX} or {\tt MIN} of an empty list returns 0.

\subsection{NEXTPRIME}\ttindex{NEXTPRIME}

{\tt NEXTPRIME} returns the next prime greater than its integer argument,
using a probabilistic algorithm.  A type error occurs if the value of the
argument is not an integer.  For example:
\begin{verbatim}
        nextprime(5)      ->  7
        nextprime(-2)     ->  2
        nextprime(-7)     -> -5
        nextprime 1000000 -> 1000003
\end{verbatim}
whereas {\tt nextprime(a)} gives a type error.

\subsection{RANDOM}\ttindex{RANDOM}

{\tt random(}{\em n\/}{\tt)} returns a random number $r$ in the range $0
\leq r < n$.  A type error occurs if the value of the argument is not a
positive integer in algebraic mode, or positive number in symbolic mode.
For example:
\begin{verbatim}
        random(5)         ->    3
        random(1000)      ->  191
\end{verbatim}
whereas {\tt random(a)} gives a type error.

\subsection{RANDOM\_NEW\_SEED}\ttindex{RANDOM\_NEW\_SEED}

{\tt random\_new\_seed(}{\em n\/}{\tt)} reseeds the random number generator
to a sequence determined by the integer argument $n$.  It can be used to
ensure that a repeatable pseudo-random sequence will be delivered
regardless of any previous use of {\tt RANDOM}, or can be called early in
a run with an argument derived from something variable (such as the time
of day) to arrange that different runs of a REDUCE program will use
different random sequences.  When a fresh copy of REDUCE is first created
it is as if {\tt random\_new\_seed(1)} has been obeyed.

A type error occurs if the value of the argument is not a positive integer.

\subsection{REPART}\ttindex{REPART}
This returns the real part of an expression, if that argument has an
numerical value.  A non-numerical argument is returned as an expression in
the operators {\tt REPART} and {\tt IMPART}\ttindex{IMPART}.  For example:
\begin{verbatim}
        repart(1+i)   -> 1
        repart(a+i*b) -> REPART(A) - IMPART(B)
\end{verbatim}

\subsection{ROUND}\ttindex{ROUND}
This operator returns the rounded value (i.e, the nearest integer) of its
single argument if that argument has a numerical value.  A non-numeric
argument is returned as an expression in the original operator.  For
example:
\begin{verbatim}
        round(-5/4)   ->  -1
        round(a)      ->  ROUND(A)
\end{verbatim}

\subsection{SIGN}\ttindex{SIGN}
{\tt SIGN} tries to evaluate the sign of its argument. If this
is possible {\tt SIGN} returns one of 1, 0 or -1.  Otherwise, the result
is the original form or a simplified variant. For example:
\begin{verbatim}
        sign(-5)      ->  -1
        sign(-a^2*b)  ->  -SIGN(B)
\end{verbatim}
Note that even powers of formal expressions are assumed to be
positive only as long as the switch {\tt COMPLEX} is off.

\section{Mathematical Functions}

{\REDUCE} knows that the following represent mathematical functions
\index{Mathematical function} that can
take arbitrary scalar expressions as their single argument:
\begin{verbatim}
       ACOS ACOSH ACOT ACOTH ACSC ACSCH ASEC ASECH ASIN ASINH
       ATAN ATANH ATAN2 COS COSH COT COTH CSC CSCH DILOG EI EXP
       HYPOT LN LOG LOGB LOG10 SEC SECH SIN SINH SQRT TAN TANH
\end{verbatim}
\ttindex{ACOS}\ttindex{ACOSH}\ttindex{ACOT}
\ttindex{ACOTH}\ttindex{ACSC}\ttindex{ACSCH}\ttindex{ASEC}
\ttindex{ASECH}\ttindex{ASIN}
\ttindex{ASINH}\ttindex{ATAN}\ttindex{ATANH}
\ttindex{ATAN2}\ttindex{COS}
\ttindex{COSH}\ttindex{COT}\ttindex{COTH}\ttindex{CSC}
\ttindex{CSCH}\ttindex{DILOG}\ttindex{Ei}\ttindex{EXP}
\ttindex{HYPOT}\ttindex{LN}\ttindex{LOG}\ttindex{LOGB}\ttindex{LOG10}
\ttindex{SEC}\ttindex{SECH}\ttindex{SIN}
\ttindex{SINH}\ttindex{SQRT}\ttindex{TAN}\ttindex{TANH}
where {\tt LOG} is the natural logarithm (and equivalent to {\tt LN}),
and {\tt LOGB} has two arguments of which the second is the logarithmic base.

The derivatives of all these functions are also known to the system.

{\REDUCE} knows various elementary identities and properties
of these functions. For example:
\begin{verbatim}
      cos(-x) = cos(x)              sin(-x) = - sin (x)
      cos(n*pi) = (-1)^n            sin(n*pi) = 0
      log(e)  = 1                   e^(i*pi/2) = i
      log(1)  = 0                   e^(i*pi) = -1
      log(e^x) = x                  e^(3*i*pi/2) = -i
\end{verbatim}

Beside these identities, there are a lot of simplifications
for elementary functions
defined in the {\REDUCE} system as rulelists. In order to
view these, the SHOWRULES operator can be used, e.g.

\begin{verbatim}
      SHOWRULES tan;

{tan(~n*arbint(~i)*pi + ~(~ x)) => tan(x) when fixp(n),

 tan(~x)

  => trigquot(sin(x),cos(x)) when knowledge_about(sin,x,tan)

 ,

      ~x + ~(~ k)*pi
 tan(----------------)
            ~d

             x                             k    1
  =>  - cot(---) when x freeof pi and abs(---)=---,
             d                             d    2

      ~(~ w) + ~(~ k)*pi           w + remainder(k,d)*pi
 tan(--------------------) => tan(-----------------------)
            ~(~ d)                           d

                               k
 when w freeof pi and ratnump(---) and fixp(k)
                               d

           k
  and abs(---)>=1,
           d

 tan(atan(~x)) => x,

                             2
 df(tan(~x),~x) => 1 + tan(x) }

\end{verbatim}

For further simplification, especially of expressions involving
trigonometric functions, see the TRIGSIMP\ttindex{TRIGSIMP} package
documentation.

Functions not listed above may be defined in the special functions
package SPECFN\ttindex{SPECFN}.

The user can add further rules for the reduction of expressions involving
these operators by using the {\tt LET}\ttindex{LET} command.

% The square root function can be input using the name {\tt SQRT}, or the
% power operation {\tt \verb|^|(1/2)}.  On output, unsimplified square roots
% are normally represented by the operator {\tt SQRT} rather than a
% fractional power.

In many cases it is desirable to expand product arguments of logarithms,
or collect a sum of logarithms into a single logarithm.  Since these are
inverse operations, it is not possible to provide rules for doing both at
the same time and preserve the {\REDUCE} concept of idempotent evaluation.
As an alternative, REDUCE provides two switches {\tt EXPANDLOGS}
\ttindex{EXPANDLOGS} and {\tt COMBINELOGS}\ttindex{COMBINELOGS} to carry
out these operations.  Both are off by default.  Thus to expand {\tt
LOG(X*Y)} into a sum of logs, one can say
\begin{verbatim}
        ON EXPANDLOGS; LOG(X*Y);
\end{verbatim}
and to combine this sum into a single log:
\begin{verbatim}
        ON COMBINELOGS; LOG(X) + LOG(Y);
\end{verbatim}

At the present time, it is possible to have both switches on at once,
which could lead to infinite recursion.  However, an expression is
switched from one form to the other in this case.  Users should not rely
on this behavior, since it may change in the next release.

The current version of {\REDUCE} does a poor job of simplifying surds.  In
particular, expressions involving the product of variables raised to
non-integer powers do not usually have their powers combined internally,
even though they are printed as if those powers were combined.  For
example, the expression
\begin{verbatim}
        x^(1/3)*x^(1/6);
\end{verbatim}
will print as
\begin{verbatim}
        SQRT(X)
\end{verbatim}
but will have an internal form containing the two exponentiated terms.
If you now subtract {\tt sqrt(x)} from this expression, you will {\em not\/}
get zero.  Instead, the confusing form
\begin{verbatim}
        SQRT(X) - SQRT(X)
\end{verbatim}
will result.  To combine such exponentiated terms, the switch
{\tt COMBINEEXPT}\ttindex{COMBINEEXPT} should be turned on.

The square root function can be input using the name {\tt SQRT}, or the
power operation {\tt \verb|^|(1/2)}.  On output, unsimplified square roots
are normally represented by the operator {\tt SQRT} rather than a
fractional power.  With the default system switch settings, the argument
of a square root is first simplified, and any divisors of the expression
that are perfect squares taken outside the square root argument.  The
remaining expression is left under the square root.
% However, if the switch {\tt REDUCED}\ttindex{REDUCED} is on,
% multiplicative factors in the argument of the square root are also
% separated, becoming individual square roots. Thus with {\tt REDUCED} off,
Thus the expression
\begin{verbatim}
         sqrt(-8a^2*b)
 \end{verbatim}
becomes
\begin{verbatim}
        2*a*sqrt(-2*b).
\end{verbatim}
% whereas with {\tt REDUCED} on, it would become
% \begin{verbatim}
%         2*a*i*sqrt(2)*sqrt(b) .
% \end{verbatim}
% The switch {\tt REDUCED}\ttindex{REDUCED} also applies to other rational
% powers in addition to square roots.

Note that such simplifications can cause trouble if {\tt A} is eventually
given a value that is a negative number.  If it is important that the
positive property of the square root and higher even roots always be
preserved, the switch {\tt PRECISE}\ttindex{PRECISE} should be set on
(the default value).
This causes any non-numerical factors taken out of surds to be represented
by their absolute value form.
With % both {\tt REDUCED} and
{\tt PRECISE} on then, the above example would become
\begin{verbatim}
        2*abs(a)*sqrt(-2*b).
\end{verbatim}

The statement that {\REDUCE} knows very little about these functions
applies only in the mathematically exact {\tt off rounded} mode.  If
{\tt ROUNDED}\ttindex{ROUNDED} is on, any of the functions
\begin{verbatim}
        ACOS ACOSH ACOT ACOTH ACSC ACSCH ASEC ASECH ASIN ASINH
        ATAN ATANH ATAN2 COS COSH COT COTH CSC CSCH EXP HYPOT
        LN LOG LOGB LOG10 SEC SECH SIN SINH SQRT TAN TANH
\end{verbatim}
\ttindex{ACOS}\ttindex{ACOSH}\ttindex{ACOT}\ttindex{ACOTH}
\ttindex{ACSC}\ttindex{ACSCH}\ttindex{ASEC}\ttindex{ASECH}
\ttindex{ASIN}\ttindex{ASINH}\ttindex{ATAN}\ttindex{ATANH}
\ttindex{ATAN2}\ttindex{COS}\ttindex{COSH}\ttindex{COT}
\ttindex{COTH}\ttindex{CSC}\ttindex{CSCH}\ttindex{EXP}\ttindex{HYPOT}
\ttindex{LN}\ttindex{LOG}\ttindex{LOGB}\ttindex{LOG10}\ttindex{SEC}
\ttindex{SECH}\ttindex{SIN}\ttindex{SINH}\ttindex{SQRT}\ttindex{TAN}
\ttindex{TANH}
when given a numerical argument has its value calculated to the current
degree of floating point precision.  In addition, real (non-integer
valued) powers of numbers will also be evaluated.

If the {\tt COMPLEX} switch is turned on in addition to {\tt ROUNDED},
these functions will also calculate a real or complex result, again to
the current degree of floating point precision,
if given complex arguments.  For example, with {\tt on rounded,complex;}
\begin{verbatim}
        2.3^(5.6i)   ->   -0.0480793490914 - 0.998843519372*I
        cos(2+3i)    ->   -4.18962569097 - 9.10922789376*I
\end{verbatim}

\section{DF Operator}
The operator {\tt DF}\ttindex{DF} is used to represent partial
differentiation\index{Differentiation} with respect
to one or more variables. It is used with the syntax:
\begin{verbatim}
     DF(EXPRN:algebraic[,VAR:kernel<,NUM:integer>]):algebraic.
\end{verbatim}
The first argument is the expression to be differentiated. The remaining
arguments specify the differentiation variables and the number of times
they are applied.

The number {\tt NUM} may be omitted if it is 1.  For example,
\begin{quote}
\begin{tabbing}
{\tt            df(y,x1,2,x2,x3,2)} \= = $\partial^{5}y/\partial x_{1}^{2} \
 \partial x_{2}\partial x_{3}^{2}.$\kill
{\tt            df(y,x)} \> = $\partial y/\partial x$ \\
{\tt            df(y,x,2)} \> = $\partial^{2}y/\partial x^{2}$ \\
{\tt            df(y,x1,2,x2,x3,2)} \> = $\partial^{5}y/\partial x_{1}^{2} \
 \partial x_{2}\partial x_{3}^{2}.$
\end{tabbing}
\end{quote}
The evaluation of {\tt df(y,x)} proceeds as follows: first, the values of
{\tt Y} and {\tt X} are found.  Let us assume that {\tt X} has no assigned
value, so its value is {\tt X}.  Each term or other part of the value of
{\tt Y} that contains the variable {\tt X} is differentiated by the
standard rules.  If {\tt Z} is another variable, not {\tt X} itself, then
its derivative with respect to {\tt X} is taken to be 0, unless {\tt Z}
has previously been declared to {\tt DEPEND} on {\tt X}, in which
case the derivative is reported as the symbol {\tt df(z,x)}.


\subsection{Adding Differentiation Rules}

The {\tt LET}\ttindex{LET} statement can be used to introduce
rules for differentiation of user-defined operators.  Its general form is
\begin{verbatim}
        FOR ALL <var1>,...,<varn>
             LET DF(<operator><varlist>,<vari>)=<expression>
\end{verbatim}
where {\tt <varlist>} ::= ({\tt <var1>},\dots,{\tt <varn>}), and
{\tt <var1>},...,{\tt <varn>} are the dummy variable arguments of
{\tt <operator>}.

An analogous form applies to infix operators.

{\it Examples:}
\begin{verbatim}
        for all x let df(tan x,x)= 1 + tan(x)^2;
\end{verbatim}
(This is how the tan differentiation rule appears in the {\REDUCE}
source.)
\begin{verbatim}
        for all x,y let df(f(x,y),x)=2*f(x,y),
                        df(f(x,y),y)=x*f(x,y);
\end{verbatim}
Notice that all dummy arguments of the relevant operator must be declared
arbitrary by the {\tt FOR ALL} command, and that rules may be supplied for
operators with any number of arguments.  If no differentiation rule
appears for an argument in an operator, the differentiation routines will
return as result an expression in terms of {\tt DF}\ttindex{DF}.  For
example, if the rule for the differentiation with respect to the second
argument of {\tt F} is not supplied, the evaluation of {\tt df(f(x,z),z)}
would leave this expression unchanged. (No {\tt DEPEND} declaration
is needed here, since {\tt f(x,z)} obviously ``depends on'' {\tt Z}.)

Once such a rule has been defined for a given operator, any future
differentiation\index{Differentiation} rules for that operator must be
defined with the same number of arguments for that operator, otherwise we
get the error message
\begin{verbatim}
        Incompatible DF rule argument length for <operator>
\end{verbatim}

\section{INT Operator}
{\tt INT}\ttindex{INT} is an operator in {\REDUCE} for indefinite
integration\index{Integration}\index{Indefinite integration} using a
combination of the Risch-Norman algorithm and pattern matching.  It is
used with the syntax:
\begin{verbatim}
   INT(EXPRN:algebraic,VAR:kernel):algebraic.
\end{verbatim}
This will return correctly the indefinite integral for expressions comprising
polynomials, log functions, exponential functions and tan and atan. The
arbitrary constant is not represented. If the integral cannot be done in
closed terms, it returns a formal integral for the answer in one of two ways:
\begin{enumerate}
\item It returns the input, {\tt INT(\ldots,\ldots)} unchanged.

\item It returns an expression involving {\tt INT}s of some
      other functions (sometimes more complicated than
      the original one, unfortunately).
\end{enumerate}
Rational functions can be integrated when the denominator is factorizable
by the program. In addition it will attempt to integrate expressions
involving error functions, dilogarithms and other trigonometric
expressions. In these cases it might not always succeed in finding the
solution, even if one exists.

{\it Examples:}
\begin{verbatim}
        int(log(x),x) ->  X*(LOG(X) - 1),
        int(e^x,x)    ->  E**X.
\end{verbatim}
The program checks that the second argument is a variable and gives an
error if it is not.

{\it Note:} If the {\tt int} operator is called with 4 arguments,
{\REDUCE} will implicitly call the definite integration package (DEFINT)
and this package will interpret the third and fourth arguments as the lower
and upper limit of integration, respectively.  For details, consult
the documentation on the DEFINT package.


\subsection{Options}

The switch {\tt TRINT} when on will trace the operation of the algorithm. It
produces a great deal of output in a somewhat illegible form, and is not
of much interest to the general user. It is normally off.

If the switch {\tt FAILHARD} is on the algorithm will terminate with an
error if the integral cannot be done in closed terms, rather than return a
formal integration form. {\tt FAILHARD} is normally off.

The switch {\tt NOLNR} suppresses the use of the linear properties of
integration in cases when the integral cannot be found in closed terms.
It is normally off.

\subsection{Advanced Use}

If a function appears in the integrand that is not one of the functions
{\tt EXP, ERF, TAN, ATAN, LOG, DILOG}\ttindex{EXP}\ttindex{ERF}
\ttindex{TAN}\ttindex{ATAN}\ttindex{LOG}\ttindex{DILOG}
then the algorithm will make an
attempt to integrate the argument if it can, differentiate it and reach a
known function.  However the answer cannot be guaranteed in this case.  If
a function is known to be algebraically independent of this set it can be
flagged transcendental by
\begin{verbatim}
        flag('(trilog),'transcendental);
\end{verbatim}
in which case this function will be added to the permitted field
descriptors for a genuine decision procedure. If this is done the user is
responsible for the mathematical correctness of his actions.

The standard version does not deal with algebraic extensions. Thus
integration of expressions involving square roots and other like things
can lead to trouble.  A contributed package that supports integration of
functions involving square roots is available, however
(ALGINT\extendedmanual{, chapter~\ref{ALGINT}}).
In addition there is a definite integration
package, DEFINT\extendedmanual{( chapter~\ref{DEFINT})}.

\subsection{References}

        A. C. Norman \& P. M. A. Moore, ``Implementing the New Risch
                Algorithm'', Proc. 4th International Symposium on Advanced
                Comp. Methods in Theor. Phys., CNRS, Marseilles, 1977.

        S. J. Harrington, ``A New Symbolic Integration System in Reduce'',
                Comp. Journ. 22 (1979) 2.

        A. C. Norman \& J. H. Davenport, ``Symbolic Integration --- The Dust
                Settles?'', Proc. EUROSAM 79, Lecture Notes in Computer
                Science 72, Springer-Verlag, Berlin Heidelberg New York
                (1979) 398-407.

%\subsection{Definite Integration} \index{Definite integration}
%
%If {\tt INT} is used with the syntax
%
%\begin{verbatim}
%   INT(EXPRN:algebraic,VAR:kernel,LOWER:algebraic,UPPER:algebraic):algebraic.
%\end{verbatim}
%
%The definite integral of {\tt EXPRN} with respect to {\tt VAR} is
%calculated between the limits {\tt LOWER} and {\tt UPPER}.  In the present
%system, this is calculated either by pattern matching, or by first finding
%the indefinite integral, and then substituting the limits into this.

\section{LENGTH Operator}
{\tt LENGTH}\ttindex{LENGTH} is a generic operator for finding the
length of various objects in the system.  The meaning depends on the type
of the object.  In particular, the length of an algebraic expression is
the number of additive top-level terms its expanded representation.

{\it Examples:}
\begin{verbatim}
        length(a+b)    ->  2
        length(2)      ->  1.
\end{verbatim}
Other objects that support a length operator include arrays, lists and
matrices. The explicit meaning in these cases is included in the description
of these objects.

\section{MAP Operator}\ttindex{MAP}

The {\tt MAP} operator applies a uniform evaluation pattern to all members
of a composite structure: a matrix, a list, or the arguments of an
operator expression.  The evaluation pattern can be a unary procedure, an
operator, or an algebraic expression with one free variable.

It is used with the syntax:
\begin{verbatim}
   MAP(U:function,V:object)
\end{verbatim}
Here {\tt object} is a list, a matrix or an operator expression.
{\tt Function} can be one of the following:
\begin{enumerate}
\item the name of an operator for a single argument: the operator
is evaluated once with each element of {\tt object} as its single argument;
\item an algebraic expression with exactly one free variable, that is
a variable preceded by the tilde symbol. The expression
is evaluated for each element of {\tt object}, where the element is
substituted for the free variable;
\item a replacement rule of the form {\tt var => rep}
where {\tt var} is a variable (a kernel without a subscript)
and {\tt rep} is an expression that contains {\tt var}.
{\tt Rep} is evaluated for each element of {\tt object} where
the element is substituted for  {\tt var}. {\tt Var} may be
optionally preceded by a tilde.
\end{enumerate}
The rule form  for {\tt function} is needed when more than
one free variable occurs.

Examples:
\begin{verbatim}
        map(abs,{1,-2,a,-a})  ->  {1,2,ABS(A),ABS(A)}
        map(int(~w,x), mat((x^2,x^5),(x^4,x^5))) ->

                [  3     6 ]
                [ x     x  ]
                [----  ----]
                [ 3     6  ]
                [          ]
                [  5     6 ]
                [ x     x  ]
                [----  ----]
                [ 5     6  ]

        map(~w*6, x^2/3 = y^3/2 -1) -> 2*X^2=3*(Y^3-2)
\end{verbatim}

You can use {\tt MAP} in nested expressions. However, you cannot
apply {\tt MAP} to a non-composed object, e.g. an identifier or a number.


\section{MKID Operator}\ttindex{MKID}
In many applications, it is useful to create a set of identifiers for
naming objects in a consistent manner. In most cases, it is sufficient to
create such names from two components. The operator {\tt MKID} is provided
for this purpose. Its syntax is:
\begin{verbatim}
MKID(U:id,V:id|non-negative integer):id
\end{verbatim}
for example
\begin{verbatim}
        mkid(a,3)      -> A3
        mkid(apple,s)  -> APPLES
\end{verbatim}
while {\tt mkid(a+b,2)} gives an error.

The {\tt SET}\ttindex{SET} operator can be used to give a value to the
identifiers created by {\tt MKID}, for example
\begin{verbatim}
        set(mkid(a,3),3);
\end{verbatim}
will give {\tt A3} the value 2.

\section{PF Operator}\ttindex{PF}

{\tt PF(<exp>,<var>)} transforms the expression {\tt <exp>} into a list of
partial fractions with respect to the main variable, {\tt <var>}.  {\tt PF}
does a complete partial fraction decomposition, and as the algorithms used
are fairly unsophisticated (factorization and the extended Euclidean
algorithm), the code may be unacceptably slow in complicated cases.

{\it Example:}
Given {\tt 2/((x+1)\verb|^|2*(x+2))} in the workspace,
{\tt pf(ws,x);} gives the result
\begin{verbatim}
            2      - 2         2
        {-------,-------,--------------} .
          X + 2   X + 1    2
                          X  + 2*X + 1
\end{verbatim}

If you want the denominators in factored form, use {\tt off exp;}.
Thus, with {\tt 2/((x+1)\verb|^|2*(x+2))} in the workspace, the commands
{\tt off exp; pf(ws,x);} give the result
\begin{verbatim}
            2      - 2       2
        {-------,-------,----------} .
          X + 2   X + 1          2
                          (X + 1)
\end{verbatim}

To recombine the terms, {\tt FOR EACH \ldots SUM} can be used.  So with
the above list in the workspace, {\tt for each j in ws sum j;} returns the
result
\begin{verbatim}
             2
     ------------------
                     2
      (X + 2)*(X + 1)
\end{verbatim}

Alternatively, one can use the operations on lists to extract any desired
term.

\section{SELECT Operator}\ttindex{SELECT}
\ttindex{map}\ttindex{list}

The {\tt SELECT} operator extracts from a list,
or from the arguments of an n--ary operator, elements corresponding
to a boolean predicate. It is used with the syntax:
\begin{verbatim}
  SELECT(U:function,V:list)
\end{verbatim}

{\tt Function} can be one of the following forms:
\begin{enumerate}
\item the name of an operator for a single argument: the operator
is evaluated once with each element of {\tt object} as its single argument;
\item an algebraic expression with exactly one free variable, that is
a variable preceded by the tilde symbol. The expression
is evaluated for each element of \meta{object}, where the element is
substituted for the free variable;
\item a replacement rule of the form \meta{var $=>$ rep}
where {\tt var} is a variable (a kernel without subscript)
and {\tt rep} is an expression that contains {\tt var}.
{\tt Rep} is evaluated for each element of {\tt object} where
the element is substituted for  {\tt var}. {\tt var} may be
optionally preceded by a tilde.
\end{enumerate}
The rule form  for {\tt function} is needed when more than
one free variable occurs.

The result of evaluating {\tt function} is
interpreted as a boolean value corresponding to the conventions of
{\REDUCE}. These values are composed with the leading operator of the
input expression.

{\it Examples:}
\begin{verbatim}
        select( ~w>0 , {1,-1,2,-3,3}) -> {1,2,3}
        select(evenp deg(~w,y),part((x+y)^5,0):=list)
               -> {X^5 ,10*X^3*Y^2 ,5*X*Y^4}
        select(evenp deg(~w,x),2x^2+3x^3+4x^4) -> 4X^4 + 2X^2
\end{verbatim}


\section{SOLVE Operator}\ttindex{SOLVE}
SOLVE is an operator for solving one or more simultaneous algebraic
equations. It is used with the syntax:
\begin{verbatim}
  SOLVE(EXPRN:algebraic[,VAR:kernel|,VARLIST:list of kernels])
         :list.
\end{verbatim}
{\tt EXPRN} is of the form {\tt <expression>} or
\{ {\tt <expression1>},{\tt <expression2>}, \dots \}.  Each expression is an
algebraic equation, or is the difference of the two sides of the equation.
The second argument is either a kernel or a list of kernels representing
the unknowns in the system.  This argument may be omitted if the number of
distinct, non-constant, top-level kernels equals the number of unknowns,
in which case these kernels are presumed to be the unknowns.

For one equation, {\tt SOLVE}\ttindex{SOLVE} recursively uses
factorization and decomposition, together with the known inverses of
{\tt LOG}, {\tt SIN}, {\tt COS}, {\tt \verb|^|}, {\tt ACOS}, {\tt ASIN}, and
linear, quadratic, cubic, quartic, or binomial factors. Solutions
of equations built with exponentials or logarithms are often
expressed in terms of Lambert's {\tt W} function.\index{Lambert's W}
This function is (partially) implemented in the special functions package.

Linear equations are solved by the multi-step elimination method due to
Bareiss, unless the switch {\tt CRAMER}\ttindex{CRAMER} is on, in which
case Cramer's method is used.  The Bareiss method is usually more
efficient unless the system is large and dense.

Non-linear equations are solved using the Groebner basis package.
\index{Groebner} Users should note that this can be quite a
time consuming process.

{\it Examples:}
\begin{verbatim}
            solve(log(sin(x+3))^5 = 8,x);
            solve(a*log(sin(x+3))^5 - b, sin(x+3));
            solve({a*x+y=3,y=-2},{x,y});
\end{verbatim}

{\tt SOLVE} returns a list of solutions.  If there is one unknown, each
solution is an equation for the unknown.  If a complete solution was
found, the unknown will appear by itself on the left-hand side of the
equation.  On the other hand, if the solve package could not find a
solution, the ``solution'' will be an equation for the unknown in terms
of the operator {\tt ROOT\_OF}\ttindex{ROOT\_OF}. If there
are several unknowns, each solution will be a list of equations for the
unknowns.  For example,
\begin{verbatim}
     solve(x^2=1,x);             -> {X=-1,X=1}

     solve(x^7-x^6+x^2=1,x)
                            6
            -> {X=ROOT_OF(X_  + X_ + 1,X_,TAG_1),X=1}

     solve({x+3y=7,y-x=1},{x,y}) -> {{X=1,Y=2}}.
\end{verbatim}
The TAG argument is used to uniquely identify those particular solutions.
Solution multiplicities are stored in the global variable {\tt
ROOT\_MULTIPLICITIES} rather than the solution list.  The value of this
variable is a list of the multiplicities of the solutions for the last
call of {\tt SOLVE}. \ttindex{SOLVE} For example,
\begin{verbatim}
       solve(x^2=2x-1,x); root_multiplicities;
\end{verbatim}
gives the results
\begin{verbatim}
        {X=1}

        {2}
\end{verbatim}

If you want the multiplicities explicitly displayed, the switch
{\tt MULTIPLICITIES}\ttindex{MULTIPLICITIES} can be turned on. For example
\begin{verbatim}
        on multiplicities; solve(x^2=2x-1,x);
\end{verbatim}
yields the result
\begin{verbatim}
        {X=1,X=1}
\end{verbatim}

\subsection{Handling of Undetermined Solutions}
When {\tt SOLVE} cannot find a solution to an equation, it normally
returns an equation for the relevant indeterminates in terms of the
operator {\tt ROOT\_OF}.\ttindex{ROOT\_OF}  For example, the expression
\begin{verbatim}
        solve(cos(x) + log(x),x);
\end{verbatim}
returns the result
\begin{verbatim}
       {X=ROOT_OF(COS(X_) + LOG(X_),X_,TAG_1)} .
\end{verbatim}

An expression with a top-level {\tt ROOT\_OF} operator is implicitly a
list with an unknown number of elements (since we don't always know how
many solutions an equation has).  If a substitution is made into such an
expression, closed form solutions can emerge.  If this occurs, the {\tt
ROOT\_OF} construct is replaced by an operator {\tt ONE\_OF}.\ttindex{ONE\_OF}
At this point it is of course possible to transform the result of the
original {\tt SOLVE} operator expression into a standard {\tt SOLVE}
solution.  To effect this, the operator {\tt EXPAND\_CASES}
\ttindex{EXPAND\_CASES} can be used.

The following example shows the use of these facilities:
\extendedmanual{\newpage}
\begin{verbatim}
solve(-a*x^3+a*x^2+x^4-x^3-4*x^2+4,x);
              2     3
{X=ROOT_OF(A*X_  - X_  + 4*X_ + 4,X_,TAG_2),X=1}

sub(a=-1,ws);

{X=ONE_OF({2,-1,-2},TAG_2),X=1}

expand_cases ws;

{X=2,X=-1,X=-2,X=1}
\end{verbatim}

\subsection{Solutions of Equations Involving Cubics and Quartics}

Since roots of cubics and quartics can often be very messy, a switch
{\tt FULLROOTS}\ttindex{FULLROOTS} is available, that, when off (the
default), will prevent the production of a result in closed form.  The
{\tt ROOT\_OF} construct will be used in this case instead.

In constructing the solutions of cubics and quartics, trigonometrical
forms are used where appropriate.  This option is under the control of a
switch {\tt TRIGFORM},\ttindex{TRIGFORM} which is normally on.

The following example illustrates the use of these facilities:
\begin{verbatim}
let xx = solve(x^3+x+1,x);

xx;
             3
{X=ROOT_OF(X_  + X_ + 1,X_)}

on fullroots;

xx;

                           - SQRT(31)*I
                    ATAN(---------------)
                            3*SQRT(3)
{X=(I*(SQRT(3)*SIN(-----------------------)
                              3
\end{verbatim}
\newpage
\begin{verbatim}
                      - SQRT(31)*I
               ATAN(---------------)
                       3*SQRT(3)
        - COS(-----------------------)))/SQRT(3),
                         3

                              - SQRT(31)*I
                       ATAN(---------------)
                               3*SQRT(3)
 X=( - I*(SQRT(3)*SIN(-----------------------)
                                 3

                         - SQRT(31)*I
                  ATAN(---------------)
                          3*SQRT(3)
           + COS(-----------------------)))/SQRT(
                            3

      3),

                  - SQRT(31)*I
           ATAN(---------------)
                   3*SQRT(3)
    2*COS(-----------------------)*I
                     3
 X=----------------------------------}
                SQRT(3)

off trigform;

xx;
                             2/3
{X=( - (SQRT(31) - 3*SQRT(3))   *SQRT(3)*I

                             2/3    2/3
     - (SQRT(31) - 3*SQRT(3))    - 2   *SQRT(3)*I

        2/3                           1/3  1/3
     + 2   )/(2*(SQRT(31) - 3*SQRT(3))   *6

                1/6
              *3   ),

                          2/3
 X=((SQRT(31) - 3*SQRT(3))   *SQRT(3)*I

                             2/3    2/3
     - (SQRT(31) - 3*SQRT(3))    + 2   *SQRT(3)*I

        2/3                           1/3  1/3
     + 2   )/(2*(SQRT(31) - 3*SQRT(3))   *6

                1/6
              *3   ),

                           2/3    2/3
     (SQRT(31) - 3*SQRT(3))    - 2
 X=-------------------------------------}
                          1/3  1/3  1/6
    (SQRT(31) - 3*SQRT(3))   *6   *3
\end{verbatim}

\subsection{Other Options}

If {\tt SOLVESINGULAR}\ttindex{SOLVESINGULAR} is on (the default setting),
degenerate systems such as {\tt x+y=0}, {\tt 2x+2y=0} will be solved by
introducing appropriate arbitrary constants.
The consistent singular equation 0=0 or equations involving functions with
multiple inverses may introduce unique new indeterminant kernels
{\tt ARBCOMPLEX(j)}, or {\tt ARBINT(j)}, ($j$=1,2,...),  % {\tt ARBREAL(j)},
representing arbitrary complex or integer numbers respectively.  To
automatically select the principal branches, do {\tt off allbranch;} .
\ttindex{ALLBRANCH} To avoid the introduction of new indeterminant kernels
do {\tt OFF ARBVARS}\ttindex{ARBVARS} -- then no equations are generated for the free
variables and their original names are used to express the solution forms.
To suppress solutions of consistent singular equations do
{\tt OFF SOLVESINGULAR}.

To incorporate additional inverse functions do, for example:
\begin{verbatim}
        put('sinh,'inverse,'asinh);
        put('asinh,'inverse,'sinh);
\end{verbatim}
together with any desired simplification rules such as
\begin{verbatim}
        for all x let sinh(asinh(x))=x, asinh(sinh(x))=x;
\end{verbatim}
For completeness, functions with non-unique inverses should be treated as
{\tt \verb|^|}, {\tt SIN}, and {\tt COS} are in the {\tt SOLVE}
\ttindex{SOLVE} module source.

Arguments of {\tt ASIN} and {\tt ACOS} are not checked to ensure that the
absolute value of the real part does not exceed 1; and arguments of
{\tt LOG} are not checked to  ensure that the absolute value of the imaginary
part does not exceed $\pi$; but checks (perhaps involving user response
for non-numerical arguments) could be introduced using
{\tt LET}\ttindex{LET} statements for these operators.

\subsection{Parameters and Variable Dependency}

The proper design of a variable sequence
supplied as a second argument to {\tt SOLVE} is important
for the structure of the solution of an equation system.
Any unknown in the system
not in this list is considered totally free. E.g.\  the call
\begin{verbatim}
    solve({x=2*z,z=2*y},{z});
\end{verbatim}
produces an empty list as a result because there is no function
$z=z(x,y)$ which fulfills both equations for arbitrary $x$ and $y$ values.
In such a case the share variable {\tt requirements}\ttindex{requirements}
displays a set of restrictions for the parameters of the system:
\begin{verbatim}
    requirements;

    {x - 4*y}
\end{verbatim}
The non-existence of a formal solution is caused by a
contradiction which disappears only if the parameters
of the initial system are set such that all members
of the requirements list take the value zero.
For a linear system the set is complete: a solution
of the requirements list makes the initial
system solvable. E.g.\  in the above case a substitution
$x=4y$ makes the equation set consistent. For a non-linear
system only one inconsistency is detected. If such a system
has more than one inconsistency, you must reduce them
one after the other.
\footnote{
The difference between linear and non--linear
inconsistent systems is based on the algorithms which
produce this information as a side effect when attempting
to find a formal solution; example:
$solve(\{x=a,x=b,y=c,y=d\},\{x,y\}$ gives a set $\{a-b,c-d\}$
while $solve(\{x^2=a,x^2=b,y^2=c,y^2=d\},\{x,y\}$ leads to $\{a-b\}$.
}
The  set shows you also the dependency among the parameters: here
one of $x$ and $y$ is free and a formal solution of the system can be
computed by adding it to the variable list of {\tt solve}.
The requirement set is not unique -- there may be other such sets.


A system  with parameters may have a formal solution, e.g.\
\begin{verbatim}
     solve({x=a*z+1,0=b*z-y},{z,x});

        y     a*y + b
   {{z=---,x=---------}}
        b        b
\end{verbatim}
which is not valid for all possible values of the parameters.
The variable {\tt assumptions}\ttindex{assumptions} contains then a list of
restrictions: the solutions are valid only as long
as none of these expressions vanishes. Any zero of one of them
represents a special case that is not covered by the
formal solution. In the above case the value is
\extendedmanual{\newpage}
\begin{verbatim}
    assumptions;

    {b}
\end{verbatim}
which excludes formally the case $b=0$; obviously this special
parameter value makes the system singular. The set of assumptions
is complete for both, linear and non--linear systems.


{\tt SOLVE} rearranges the variable sequence
to reduce the (expected) computing time. This behavior is controlled
by the switch {\tt varopt}\ttindex{varopt}, which is on by default.
If it is turned off, the supplied variable sequence is used
or the system kernel ordering is taken if the variable
list is omitted. The effect is demonstrated by an example:
\begin{verbatim}
   s:= {y^3+3x=0,x^2+y^2=1};

   solve(s,{y,x});

                  6       2
   {{y=root_of(y_  + 9*y_  - 9,y_),

            3
         - y
     x=-------}}
          3

   off varopt; solve(s,{y,x});

                  6       4        2
   {{x=root_of(x_  - 3*x_  + 12*x_  - 1,x_),

               4      2
        x*( - x  + 2*x  - 10)
     y=-----------------------}}
                  3

\end{verbatim}
In the first case, {\tt solve} forms the solution as a set of
pairs $(y_i,x(y_i))$ because the degree of $x$ is higher --
such a rearrangement makes the internal computation of the Gr\"obner basis
generally faster. For the second case the explicitly given variable sequence
is used such that the solution has now the form $(x_i,y(x_i))$.
Controlling the variable sequence is especially important if
the system has one or more free variables.
As an alternative to turning off {\tt varopt}, a partial dependency among
the variables can be declared using the {\tt depend}\index{depend}
statement: {\tt solve} then rearranges the variable sequence but keeps any
variable ahead of those on which it depends.
\extendedmanual{\newpage}
\begin{verbatim}
   on varopt;
   s:={a^3+b,b^2+c}$
   solve(s,{a,b,c});

                           3       6
   {{a=arbcomplex(1),b= - a ,c= - a }}

   depend a,c; depend b,c; solve(s,{a,b,c});

   {{c=arbcomplex(2),

                 6
     a=root_of(a_  + c,a_),

           3
     b= - a }}
\end{verbatim}
Here {\tt solve} is forced to put $c$ after $a$ and after $b$, but
there is no obstacle to interchanging $a$ and $b$.

\section{Even and Odd Operators}\index{Even operator}\index{Odd operator}
An operator can be declared to be {\em even\/} or {\em odd\/} in its first
argument by the declarations {\tt EVEN}\ttindex{EVEN} and
{\tt ODD}\ttindex{ODD} respectively.  Expressions involving an operator
declared in this manner are transformed if the first argument contains a
minus sign.  Any other arguments are not affected.  In addition, if say
{\tt F} is declared odd, then {\tt f(0)} is replaced by zero unless
{\tt F} is also declared {\em non zero\/} by the declaration
{\tt NONZERO}\ttindex{NONZERO}.  For example, the declarations
\begin{verbatim}
        even f1; odd f2;
\end{verbatim}
mean that
\begin{verbatim}
        f1(-a)    ->    F1(A)
        f2(-a)    ->   -F2(A)
        f1(-a,-b) ->    F1(A,-B)
        f2(0)     ->    0.
\end{verbatim}
To inhibit the last transformation, say {\tt nonzero f2;}.

\section{Linear Operators}\index{Linear operator}
An operator can be declared to be linear in its first argument over powers
of its second argument.  If an operator {\tt F} is so declared, {\tt F} of
any sum is broken up into sums of {\tt F}s, and any factors that are not
powers of the variable are taken outside.  This means that {\tt F} must
have (at least) two arguments.  In addition, the second argument must be
an identifier (or more generally a kernel), not an expression.

{\it Example:}

If {\tt F} were declared linear, then
\begin{verbatim}
                                5
        f(a*x^5+b*x+c,x) ->  F(X ,X)*A + F(X,X)*B + F(1,X)*C
\end{verbatim}
More precisely, not only will the variable and its powers remain within the
scope of the {\tt F} operator, but so will any variable and its powers that
had been declared to {\tt DEPEND} on the prescribed variable; and so would
any expression that contains that variable or a dependent variable on any
level, e.g. {\tt cos(sin(x))}.

To declare operators {\tt F} and {\tt G} to be linear operators,
use:\ttindex{LINEAR}
\begin{verbatim}
        linear f,g;
\end{verbatim}
The analysis is done of the first argument with respect to the second; any
other arguments are ignored. It uses the following rules of evaluation:
\begin{quote}
\begin{tabbing}
{\tt    f(0)      ->   0} \\
{\tt    f(-y,x)   ->  -F(Y,X)} \\
{\tt    f(y+z,x)  ->   F(Y,X)+F(Z,X)} \\
{\tt    f(y*z,x)  ->   Z*F(Y,X)} \hspace{0.5in}\= if Z does not depend on X \\
{\tt    f(y/z,x)  ->   F(Y,X)/Z} \> if Z does not depend on X
\end{tabbing}
\end{quote}
To summarize, {\tt Y} ``depends'' on the indeterminate {\tt X} in the above
if either of the following hold:
\begin{enumerate}
\item {\tt Y} is an expression that contains {\tt X} at any level as a
      variable, e.g.: {\tt cos(sin(x))}

\item Any variable in the expression {\tt Y} has been declared dependent on
      {\tt X} by use of the declaration {\tt DEPEND}.
\end{enumerate}
The use of such linear operators\index{Linear operator} can be seen in the
paper Fox, J.A. and A. C. Hearn, ``Analytic Computation of Some Integrals
in Fourth Order Quantum Electrodynamics'' Journ. Comp. Phys. 14 (1974)
301-317, which contains a complete listing of a program for definite
integration\index{Integration} of some expressions that arise in fourth
order quantum electrodynamics.

\section{Non-Commuting Operators}\index{Non-commuting operator}
An operator can be declared to be non-commutative under multiplication by
the declaration {\tt NONCOM}.\ttindex{NONCOM}

{\it Example:}

After the declaration \\
{\tt noncom u,v;}\\
the expressions {\tt
u(x)*u(y)-u(y)*u(x)} and {\tt u(x)*v(y)-v(y)*u(x)} will remain unchanged
on simplification, and in particular will not simplify to zero.

Note that it is the operator ({\tt U} and {\tt V} in the above example)
and not the variable that has the non-commutative property.

The {\tt LET}\ttindex{LET} statement may be used to introduce rules of
evaluation for such operators.  In particular, the boolean operator
{\tt ORDP}\ttindex{ORDP} is useful for introducing an ordering on such
expressions.

{\it Example:}

The rule
\begin{verbatim}
        for all x,y such that x neq y and ordp(x,y)
           let u(x)*u(y)= u(y)*u(x)+comm(x,y);
\end{verbatim}
would introduce the commutator of {\tt u(x)} and {\tt u(y)} for all
{\tt X} and {\tt Y}.  Note that since {\tt ordp(x,x)} is {\em true}, the
equality check is necessary in the degenerate case to avoid a circular
loop in the rule.

\section{Symmetric and Antisymmetric Operators}

An operator can be declared to be symmetric with respect to its arguments
by the declaration {\tt SYMMETRIC}.\ttindex{SYMMETRIC} For example
\begin{verbatim}
        symmetric u,v;
\end{verbatim}
means that any expression involving the top level operators {\tt U} or
{\tt V} will have its arguments reordered to conform to the internal order
used by {\REDUCE}.  The user can change this order for kernels by the
command {\tt KORDER}.

For example, {\tt u(x,v(1,2))} would become {\tt u(v(2,1),x)}, since
numbers are ordered in decreasing order, and expressions are ordered in
decreasing order of complexity.

Similarly the declaration {\tt ANTISYMMETRIC}\ttindex{ANTISYMMETRIC}
declares an operator antisymmetric.   For example,
\begin{verbatim}
        antisymmetric l,m;
\end{verbatim}
means that any expression involving the top level operators {\tt L} or
{\tt M} will have its arguments reordered to conform to the internal order
of the system, and the sign of the expression changed if there are an odd
number of argument interchanges necessary to bring about the new order.

For example, {\tt l(x,m(1,2))} would become {\tt -l(-m(2,1),x)} since one
interchange occurs with each operator.  An expression like {\tt l(x,x)}
would also be replaced by 0.

\section{Declaring New Prefix Operators}

The user may add new prefix\index{Prefix} operators to the system by
using the declaration {\tt OPERATOR}. For example:
\begin{verbatim}
        operator h,g1,arctan;
\end{verbatim}
adds the prefix operators {\tt H}, {\tt G1} and {\tt ARCTAN} to the system.

This allows symbols like {\tt h(w), h(x,y,z), g1(p+q), arctan(u/v)} to be
used in expressions, but no meaning or properties of the operator are
implied.  The same operator symbol can be used equally well as a 0-, 1-, 2-,
3-, etc.-place operator.

To give a meaning to an operator symbol, or express some of its
properties, {\tt LET}\ttindex{LET} statements can be used, or the operator
can be given a definition as a procedure.

If the user forgets to declare an identifier as an operator, the system
will prompt the user to do so in interactive mode, or do it automatically
in non-interactive mode. A diagnostic message will also be printed if an
identifier is declared {\tt OPERATOR} more than once.

Operators once declared are global in scope, and so can then be referenced
anywhere in the program.  In other words, a declaration within a block (or
a procedure) does not limit the scope of the operator to that block, nor
does the operator go away on exiting the block (use {\tt CLEAR} instead
for this purpose).


\section{Declaring New Infix Operators}

Users can add new infix operators by using the declarations
{\tt INFIX}\ttindex{INFIX} and {\tt PRECEDENCE}.\ttindex{PRECEDENCE}
For example,
\begin{verbatim}
        infix mm;
        precedence mm,-;
\end{verbatim}
The declaration {\tt infix mm;} would allow one to use the symbol
{\tt MM} as an infix operator:
\begin{quote}
\hspace{0.2in} {\tt a mm b} \hspace{0.3in} instead of \hspace{0.3in}
{\tt mm(a,b)}.
\end{quote}

The declaration {\tt precedence mm,-;} says that {\tt MM} should be
inserted into the infix operator precedence list just {\em after\/}
the $-$ operator.  This gives it higher precedence than $-$ and lower
precedence than * .  Thus

\begin{quote}
\hspace{0.2in}{\tt a - b mm c - d}\hspace{.3in} means \hspace{.3in}
{\tt a - (b mm c) - d},
\end{quote}
while
\begin{quote}
\hspace{0.2in}{\tt   a * b mm c * d}\hspace{.3in} means \hspace{.3in}
{\tt (a * b) mm (c * d)}.
\end{quote}

Both infix and prefix\index{Prefix} operators have no transformation
properties unless {\tt LET}\ttindex{LET} statements or procedure
declarations are used to assign a meaning.

We should note here that infix operators so defined are always binary:
\begin{quote}
\hspace{0.2in}{\tt a mm b mm c}\hspace{.3in} means \hspace{.3in}
{\tt (a mm b) mm c}.
\end{quote}

\section{Creating/Removing Variable Dependency}

There are several facilities in {\REDUCE}, such as the differentiation
\index{Differentiation}
operator and the linear operator\index{Linear operator} facility, that
can utilize knowledge of the dependency between various variables, or
kernels.  Such dependency may be expressed by the command {\tt
DEPEND}.\ttindex{DEPEND} This takes an arbitrary number of arguments and
sets up a dependency of the first argument on the remaining arguments.
For example,
\begin{verbatim}
        depend x,y,z;
\end{verbatim}
says that {\tt X} is dependent on both {\tt Y} and {\tt Z}.
\begin{verbatim}
        depend z,cos(x),y;
\end{verbatim}
says that {\tt Z} is dependent on {\tt COS(X)} and {\tt Y}.

Dependencies introduced by {\tt DEPEND} can be removed by {\tt NODEPEND}.
\ttindex{NODEPEND} The arguments of this are the same as for {\tt DEPEND}.
For example, given the above dependencies,
\begin{verbatim}
        nodepend z,cos(x);
\end{verbatim}
says that {\tt Z} is no longer dependent on {\tt COS(X)}, although it remains
dependent on {\tt Y}.

\chapter{Display and Structuring of Expressions}\index{Display}
\index{Structuring}
In this section, we consider a variety of commands and operators that
permit the user to obtain various parts of algebraic expressions and also
display their structure in a variety of forms. Also presented are some
additional concepts in the {\REDUCE} design that help the user gain a better
understanding of the structure of the system.

\section{Kernels}\index{Kernel}
{\REDUCE} is designed so that each operator in the system has an
evaluation (or simplification)\index{Simplification} function associated
with it that transforms the expression into an internal canonical form.
\index{Canonical form}  This form, which bears little resemblance to the
original expression, is described in detail in Hearn, A. C., ``{\REDUCE} 2:
A System and Language for Algebraic Manipulation,'' Proc. of the Second
Symposium on Symbolic and Algebraic Manipulation, ACM, New York (1971)
128-133.

The evaluation function may transform its arguments in one of two
alternative ways.  First, it may convert the expression into other
operators in the system, leaving no functions of the original operator for
further manipulation.  This is in a sense true of the evaluation functions
associated with the operators {\tt +}, {\tt *} and {\tt /} , for example,
because the canonical form\index{Canonical form} does not include these
operators explicitly.  It is also true of an operator such as the
determinant operator {\tt DET}\ttindex{DET} because the relevant
evaluation function calculates the appropriate determinant, and the
operator {\tt DET} no longer appears.  On the other hand, the evaluation
process may leave some residual functions of the relevant operator.  For
example, with the operator {\tt COS}, a residual expression like {\tt
COS(X)} may remain after evaluation unless a rule for the reduction of
cosines into exponentials, for example, were introduced.  These residual
functions of an operator are termed {\em kernels\/}\index{Kernel} and are
stored uniquely like variables.  Subsequently, the kernel is carried
through the calculation as a variable unless transformations are
introduced for the operator at a later stage.

In those cases where the evaluation process leaves an operator expression
with non-trivial arguments, the form of the argument can vary depending on
the state of the system at the point of evaluation.  Such arguments are
normally produced in expanded form with no terms factored or grouped in
any way.  For example, the expression {\tt cos(2*x+2*y)} will normally be
returned in the same form.  If the argument {\tt 2*x+2*y} were evaluated
at the top level, however, it would be printed as {\tt 2*(X+Y)}.  If it is
desirable to have the arguments themselves in a similar form, the switch
{\tt INTSTR}\ttindex{INTSTR} (for ``internal structure''), if on, will
cause this to happen.

In cases where the arguments of the kernel operators may be reordered, the
system puts them in a canonical order, based on an internal intrinsic
ordering of the variables. However, some commands allow arguments in the
form of kernels, and the user has no way of telling what internal order the
system will assign to these arguments. To resolve this difficulty, we
introduce the notion of a {\em kernel form\/}\index{kernel form} as an
expression that transforms to a kernel on evaluation.

Examples of kernel forms are:
\begin{verbatim}
        a
        cos(x*y)
        log(sin(x))
\end{verbatim}
whereas
\begin{verbatim}
        a*b
        (a+b)^4
\end{verbatim}
are not.

We see that kernel forms can usually be used as generalized variables, and
most algebraic properties associated with variables may also be associated
with kernels.

\section{The Expression Workspace}\index{Workspace}

Several mechanisms are available for saving and retrieving previously
evaluated expressions.  The simplest of these refers to the last algebraic
expression simplified.  When an assignment of an algebraic expression is
made, or an expression is evaluated at the top level, (i.e., not inside a
compound statement or procedure) the results of the evaluation are
automatically saved in a variable {\tt WS} that we shall refer to as the
workspace. (More precisely, the expression is assigned to the variable
{\tt WS} that is then available for further manipulation.)

{\it Example:}

If we evaluate the expression {\tt (x+y)\verb|^|2} at the top level and next
wish to differentiate it with respect to {\tt Y}, we can simply say
\begin{verbatim}
        df(ws,y);
\end{verbatim}
to get the desired answer.

If the user wishes to assign the workspace to a variable or expression for
later use, the {\tt SAVEAS}\ttindex{SAVEAS} statement can be used.  It
has the syntax
\begin{verbatim}
        SAVEAS <expression>
\end{verbatim}
For example, after the differentiation in the last example, the workspace
holds the expression {\tt 2*x+2*y}.  If we wish to assign this to the
variable {\tt Z} we can now say
\begin{verbatim}
        saveas z;
\end{verbatim}
If the user wishes to save the expression in a form that allows him to use
some of its variables as arbitrary parameters, the {\tt FOR ALL}
command can be used.

{\it Example:}
\begin{verbatim}
        for all x saveas h(x);
\end{verbatim}

with the above expression would mean that {\tt h(z)} evaluates to {\tt
2*Y+2*Z}.

A further method for referencing more than the last expression is described
in the section on interactive use of {\REDUCE}.


\section{Output of Expressions}

A considerable degree of flexibility is available in {\REDUCE} in the
printing of expressions generated during calculations.  No explicit format
statements are supplied, as these are in most cases of little use in
algebraic calculations, where the size of output or its composition is not
generally known in advance.  Instead, {\REDUCE} provides a series of mode
options to the user that should enable him to produce his output in a
comprehensible and possibly pleasing form.

The most extreme option offered is to suppress the output entirely from
any top level evaluation.  This is accomplished by turning off the switch
{\tt OUTPUT}\ttindex{OUTPUT} which is normally on.  It is useful for
limiting output when loading large files or producing ``clean'' output from
the prettyprint programs.

In most circumstances, however, we wish to view the output, so we need to
know how to format it appropriately.  As we mentioned earlier, an
algebraic expression is normally printed in an expanded form, filling the
whole output line with terms.  Certain output declarations,\index{Output
declaration} however, can be used to affect this format.  To begin with,
we look at an operator for changing the length of the output line.

\subsection{LINELENGTH Operator}\ttindex{LINELENGTH}

This operator is used with the syntax
\begin{verbatim}
        LINELENGTH(NUM:integer):integer
\end{verbatim}
and sets the output line length to the integer {\tt NUM}. It returns the
previous output line length (so that it can be stored for later resetting
of the output line if needed).

\subsection{Output Declarations}

We now describe a number of switches and declarations that are available
for controlling output formats. It should be noted, however, that the
transformation of large expressions to produce these varied output formats
can take a lot of computing time and space. If a user wishes to speed up
the printing of the output in such cases, he can turn off the switch {\tt
PRI}.\ttindex{PRI} If this is done, then output is produced in one fixed
format, which basically reflects the internal form of the expression, and
none of the options below apply. {\tt PRI} is normally on.

With {\tt PRI} on, the output declarations\index{Output declaration}
and switches available are as follows:

\subsubsection{ORDER Declaration}

The declaration {\tt ORDER}\ttindex{ORDER} may be used to order variables
on output.  The syntax is:
\begin{verbatim}
        order v1,...vn;
\end{verbatim}
where the {\tt vi} are kernels.  Thus,
\begin{verbatim}
        order x,y,z;
\end{verbatim}
orders {\tt X} ahead of {\tt Y}, {\tt Y} ahead of {\tt Z} and all three
ahead of other variables not given an order. {\tt order nil;} resets the
output order to the system default.  The order of variables may be changed
by further calls of {\tt ORDER}, but then the reordered variables would
have an order lower than those in earlier {\tt ORDER}\ttindex{ORDER} calls.
Thus,
\begin{verbatim}
        order x,y,z;
        order y,x;
\end{verbatim}
would order {\tt Z} ahead of {\tt Y} and {\tt X}.  The default ordering is
usually alphabetic.

\subsubsection{FACTOR Declaration}

This declaration takes a list of identifiers or kernels\index{Kernel}
as argument. {\tt FACTOR}\ttindex{FACTOR} is not a factoring command
(use {\tt FACTORIZE} or the {\tt FACTOR} switch for this purpose); rather it
is a separation command.  All terms involving fixed powers of the declared
expressions are printed as a product of the fixed powers and a sum of the
rest of the terms.

All expressions involving a given prefix operator may also be factored by
putting the operator name in the list of factored identifiers. For example:
\begin{verbatim}
        factor x,cos,sin(x);
\end{verbatim}
causes all powers of {\tt X} and {\tt SIN(X)} and all functions of
{\tt COS} to be factored.

Note that {\tt FACTOR} does not affect the order of its arguments.  You
should also use {\tt ORDER} if this is important.

The declaration {\tt remfac v1,...,vn;}\ttindex{REMFAC} removes the
factoring flag from the expressions {\tt v1} through {\tt vn}.

\subsection{Output Control Switches}
\label{sec-output}
In addition to these declarations, the form of the output can be modified
by switching various output control switches using the declarations
{\tt ON} and {\tt OFF}.  We shall illustrate the use of these switches by an
example, namely the printing of the expression
\begin{verbatim}
        x^2*(y^2+2*y)+x*(y^2+z)/(2*a) .
\end{verbatim}
The relevant switches are as follows:

\subsubsection{ALLFAC Switch}

This switch will cause the system to search the whole expression, or any
sub-expression enclosed in parentheses, for simple multiplicative factors
and print them outside the parentheses. Thus our expression with {\tt ALLFAC}
\ttindex{ALLFAC}
off will print as
\begin{verbatim}
            2  2        2          2
        (2*X *Y *A + 4*X *Y*A + X*Y  + X*Z)/(2*A)
\end{verbatim}
and with {\tt ALLFAC} on as
\begin{verbatim}
                2                2
        X*(2*X*Y *A + 4*X*Y*A + Y  + Z)/(2*A) .
\end{verbatim}
{\tt ALLFAC} is normally on, and is on in the following examples, except
where otherwise stated.

\subsubsection{DIV Switch}\ttindex{DIV}

This switch makes the system search the denominator of an expression for
simple factors that it divides into the numerator, so that rational
fractions and negative powers appear in the output. With {\tt DIV} on, our
expression would print as
\begin{verbatim}
              2                2  (-1)        (-1)
        X*(X*Y  + 2*X*Y + 1/2*Y *A     + 1/2*A    *Z) .
\end{verbatim}
{\tt DIV} is normally off.

\subsubsection{LIST Switch}\ttindex{LIST}

This switch causes the system to print each term in any sum on a separate
line. With {\tt LIST} on, our expression prints as
\begin{verbatim}
                2
        X*(2*X*Y *A

            + 4*X*Y*A

               2
            + Y

            + Z)/(2*A) .
\end{verbatim}
{\tt LIST} is normally off.

\subsubsection{NOSPLIT Switch}\ttindex{NOSPLIT}

Under normal circumstances, the printing routines try to break an expression
across lines at a natural point.  This is a fairly expensive process.  If
you are not overly concerned about where the end-of-line breaks come, you
can speed up the printing of expressions by turning off the switch
{\tt NOSPLIT}.  This switch is normally on.

\subsubsection{RAT Switch}\ttindex{RAT}

This switch is only useful with expressions in which variables are
factored with {\tt FACTOR}. With this mode, the overall denominator of the
expression is printed with each factored sub-expression. We assume a prior
declaration {\tt factor x;} in the following output. We first print the
expression with {\tt RAT off}:
\begin{verbatim}
            2                   2
        (2*X *Y*A*(Y + 2) + X*(Y  + Z))/(2*A) .
\end{verbatim}
With {\tt RAT} on the output becomes:
\extendedmanual{\newpage}
\begin{verbatim}
         2                 2
        X *Y*(Y + 2) + X*(Y  + Z)/(2*A) .
\end{verbatim}
{\tt RAT} is normally off.

Next, if we leave {\tt X} factored, and turn on both {\tt DIV} and
{\tt RAT}, the result becomes
\begin{verbatim}
         2                    (-1)   2
        X *Y*(Y + 2) + 1/2*X*A    *(Y  + Z) .
\end{verbatim}
Finally, with {\tt X} factored, {\tt RAT} on and {\tt ALLFAC}\ttindex{ALLFAC}
off we retrieve the original structure
\begin{verbatim}
         2   2              2
        X *(Y  + 2*Y) + X*(Y  + Z)/(2*A) .
\end{verbatim}

\subsubsection{RATPRI Switch}\ttindex{RATPRI}

If the numerator and denominator of an expression can each be printed in
one line, the output routines will print them in a two dimensional
notation, with numerator and denominator on separate lines and a line of
dashes in between. For example, {\tt (a+b)/2} will print as
\begin{verbatim}
        A + B
        -----
          2
\end{verbatim}
Turning this switch off causes such expressions to be output in a linear
form.

\subsubsection{REVPRI Switch}\ttindex{REVPRI}

The normal ordering of terms in output is from highest to lowest power.
In some situations (e.g., when a power series is output), the opposite
ordering is more convenient.  The switch {\tt REVPRI} if on causes such a
reverse ordering of terms.  For example, the expression
{\tt y*(x+1)\verb|^|2+(y+3)\verb|^|2} will normally print as
\begin{verbatim}
         2              2
        X *Y + 2*X*Y + Y  + 7*Y + 9
\end{verbatim}
whereas with {\tt REVPRI} on, it will print as
\begin{verbatim}
                   2            2
        9 + 7*Y + Y  + 2*X*Y + X *Y.
\end{verbatim}

\subsection{WRITE Command}\ttindex{WRITE}

In simple cases no explicit output\index{Output} command is necessary in
{\REDUCE}, since the value of any expression is automatically printed if a
semicolon is used as a delimiter.  There are, however, several situations
in which such a command is useful.

In a {\tt FOR}, {\tt WHILE}, or {\tt REPEAT} statement it may be desired
to output something each time the statement within the loop construct is
repeated.

It may be desired for a procedure to output intermediate results or other
information while it is running. It may be desired to have results labeled
in special ways, especially if the output is directed to a file or device
other than the terminal.

The {\tt WRITE} command consists of the word {\tt WRITE} followed by one
or more items separated by commas, and followed by a terminator.  There
are three kinds of items that can be used:
\begin{enumerate}
\item Expressions (including variables and constants).  The expression is
evaluated, and the result is printed out.

\item Assignments.  The expression on the right side of the {\tt :=}
operator is evaluated, and is assigned to the variable on the left; then
the symbol on the left is printed, followed by a ``{\tt :=}'', followed by
the value of the expression on the right -- almost exactly the way an
assignment followed by a semicolon prints out normally. (The difference is
that if the {\tt WRITE} is in a {\tt FOR} statement and the left-hand side
of the assignment is an array position or something similar containing the
variable of the {\tt FOR} iteration, then the value of that variable is
inserted in the printout.)

\item Arbitrary strings of characters, preceded and followed by double-quote
marks (e.g., {\tt "string"}).
\end{enumerate}
The items specified by a single {\tt WRITE} statement print side by side
on one line. (The line is broken automatically if it is too long.) Strings
print exactly as quoted.  The {\tt WRITE} command itself however does not
return a value.

The print line is closed at the end of a {\tt WRITE} command evaluation.
Therefore the command {\tt WRITE "";} (specifying nothing to be printed
except the empty string) causes a line to be skipped.

{\it Examples:}
\begin{enumerate}
\item If {\tt A} is {\tt X+5}, {\tt B} is itself, {\tt C} is 123, {\tt M} is
an array, and {\tt Q}=3, then
\begin{verbatim}
        write m(q):=a," ",b/c," THANK YOU";
\end{verbatim}
will set {\tt M(3)} to {\tt x+5} and print
\begin{verbatim}
        M(Q) := X + 5 B/123 THANK YOU
\end{verbatim}
The blanks between the {\tt 5} and {\tt B}, and the
{\tt 3} and {\tt T}, come from the blanks in the quoted strings.

\item To print a table of the squares of the integers from 1 to 20:
\begin{verbatim}
        for i:=1:20 do write i," ",i^2;
\end{verbatim}

\item To print a table of the squares of the integers from 1 to 20, and at
the same time store them in positions 1 to 20 of an array {\tt A:}
\begin{verbatim}
        for i:=1:20 do <<a(i):=i^2; write i," ",a(i)>>;
\end{verbatim}
This will give us two columns of numbers. If we had used
\begin{verbatim}
        for i:=1:20 do write i," ",a(i):=i^2;
\end{verbatim}
we would also get {\tt A(}i{\tt ) := } repeated on each line.

\item The following more complete example calculates the famous f and g
series, first reported in Sconzo, P., LeSchack, A. R., and Tobey, R.,
``Symbolic Computation of f and g Series by Computer'', Astronomical Journal
70 (May 1965).
\begin{verbatim}
 x1:= -sig*(mu+2*eps)$
 x2:= eps - 2*sig^2$
 x3:= -3*mu*sig$
 f:= 1$
 g:= 0$
 for i:= 1 step 1 until 10 do begin
    f1:= -mu*g+x1*df(f,eps)+x2*df(f,sig)+x3*df(f,mu);
    write "f(",i,") := ",f1;
    g1:= f+x1*df(g,eps)+x2*df(g,sig)+x3*df(g,mu);
    write "g(",i,") := ",g1;
    f:=f1$
    g:=g1$
   end;
\end{verbatim}
 A portion of the output, to illustrate the printout from the {\tt WRITE}
command, is as follows:
\begin{verbatim}
                ... <prior output> ...

                           2
 F(4) := MU*(3*EPS - 15*SIG  + MU)

 G(4) := 6*SIG*MU

                                    2
 F(5) := 15*SIG*MU*( - 3*EPS + 7*SIG  - MU)

                           2
 G(5) := MU*(9*EPS - 45*SIG  + MU)

                ... <more output> ...

\end{verbatim}
\end{enumerate}
\subsection{Suppression of Zeros}

It is sometimes annoying to have zero assignments (i.e. assignments of the
form {\tt <expression> := 0}) printed, especially in printing large arrays
with many zero elements.  The output from such assignments can be
suppressed by turning on the switch {\tt NERO}.\ttindex{NERO}

\subsection{{FORTRAN} Style Output Of Expressions}

It is naturally possible to evaluate expressions numerically in {\REDUCE} by
giving all variables and sub-expressions numerical values. However, as we
pointed out elsewhere the user must declare real arithmetical operation by
turning on the switch {\tt ROUNDED}\ttindex{ROUNDED}.  However, it should be
remembered that arithmetic in {\REDUCE} is not particularly fast, since
results are interpreted rather than evaluated in a compiled form. The user
with a large amount of numerical computation after all necessary algebraic
manipulations have been performed is therefore well advised to perform
these calculations in a FORTRAN\index{FORTRAN} or similar system.  For
this purpose, {\REDUCE} offers facilities for users to produce FORTRAN
compatible files for numerical processing.

First, when the switch {\tt FORT}\ttindex{FORT} is on, the system will
print expressions in a FORTRAN notation.  Expressions begin in column
seven.  If an expression extends over one line, a continuation mark (.)
followed by a blank appears on subsequent cards.  After a certain number
of lines have been produced (according to the value of the variable {\tt
CARD\_NO}),\ttindex{CARD\_NO} a new expression is started.  If the
expression printed arises from an assignment to a variable, the variable
is printed as the name of the expression.  Otherwise the expression is
given the default name {\tt ANS}.  An error occurs if identifiers or
numbers are outside the bounds permitted by FORTRAN.

A second option is to use the {\tt WRITE} command to produce other programs.

{\it Example:}

The following {\REDUCE} statements
\begin{verbatim}
 on fort;
 out "forfil";
 write "C     this is a fortran program";
 write " 1    format(e13.5)";
 write "      u=1.23";
 write "      v=2.17";
 write "      w=5.2";
 x:=(u+v+w)^11;
 write "C     it was foolish to expand this expression";
 write "      print 1,x";
 write "      end";
 shut "forfil";
 off fort;
\end{verbatim}
will generate a file {\tt forfil} that contains:

{\small
\begin{verbatim}
c this is a fortran program
 1    format(e13.5)
      u=1.23
      v=2.17
      w=5.2
      ans1=1320.*u**3*v*w**7+165.*u**3*w**8+55.*u**2*v**9+495.*u
     . **2*v**8*w+1980.*u**2*v**7*w**2+4620.*u**2*v**6*w**3+
     . 6930.*u**2*v**5*w**4+6930.*u**2*v**4*w**5+4620.*u**2*v**3*
     . w**6+1980.*u**2*v**2*w**7+495.*u**2*v*w**8+55.*u**2*w**9+
     . 11.*u*v**10+110.*u*v**9*w+495.*u*v**8*w**2+1320.*u*v**7*w
     . **3+2310.*u*v**6*w**4+2772.*u*v**5*w**5+2310.*u*v**4*w**6
     . +1320.*u*v**3*w**7+495.*u*v**2*w**8+110.*u*v*w**9+11.*u*w
     . **10+v**11+11.*v**10*w+55.*v**9*w**2+165.*v**8*w**3+330.*
     . v**7*w**4+462.*v**6*w**5+462.*v**5*w**6+330.*v**4*w**7+
     . 165.*v**3*w**8+55.*v**2*w**9+11.*v*w**10+w**11
      x=u**11+11.*u**10*v+11.*u**10*w+55.*u**9*v**2+110.*u**9*v*
     . w+55.*u**9*w**2+165.*u**8*v**3+495.*u**8*v**2*w+495.*u**8
     . *v*w**2+165.*u**8*w**3+330.*u**7*v**4+1320.*u**7*v**3*w+
     . 1980.*u**7*v**2*w**2+1320.*u**7*v*w**3+330.*u**7*w**4+462.
     . *u**6*v**5+2310.*u**6*v**4*w+4620.*u**6*v**3*w**2+4620.*u
     . **6*v**2*w**3+2310.*u**6*v*w**4+462.*u**6*w**5+462.*u**5*
     . v**6+2772.*u**5*v**5*w+6930.*u**5*v**4*w**2+9240.*u**5*v
     . **3*w**3+6930.*u**5*v**2*w**4+2772.*u**5*v*w**5+462.*u**5
     . *w**6+330.*u**4*v**7+2310.*u**4*v**6*w+6930.*u**4*v**5*w
     . **2+11550.*u**4*v**4*w**3+11550.*u**4*v**3*w**4+6930.*u**
     . 4*v**2*w**5+2310.*u**4*v*w**6+330.*u**4*w**7+165.*u**3*v
     . **8+1320.*u**3*v**7*w+4620.*u**3*v**6*w**2+9240.*u**3*v**
     . 5*w**3+11550.*u**3*v**4*w**4+9240.*u**3*v**3*w**5+4620.*u
     . **3*v**2*w**6+ans1
c     it was foolish to expand this expression
      print 1,x
      end
\end{verbatim}
}
If the arguments of a {\tt WRITE} statement include an expression that
requires continuation records, the output will need editing, since the
output routine prints the arguments of {\tt WRITE} sequentially, and the
continuation mechanism therefore generates its auxiliary variables after
the preceding expression has been printed.

Finally, since there is no direct analog of {\em list\/} in FORTRAN,
a comment line of the form
\begin{verbatim}
        c ***** invalid fortran construct (list) not printed
\end{verbatim}
will be printed if you try to print a list with {\tt FORT} on.

\subsubsection{{FORTRAN} Output Options}\index{Output}\index{FORTRAN}

There are a number of methods available to change the default format of the
FORTRAN output.

The breakup of the expression into subparts is such that the number of
continuation lines produced is less than a given number. This number can
be modified by the assignment
\begin{verbatim}
        card_no := <number>;
\end{verbatim}
where {\tt <number>} is the {\em total\/} number of cards allowed in a
statement. The default value of {\tt CARD\_NO} is 20.

The width of the output expression is also adjustable by the assignment
\begin{verbatim}
        fort_width := <integer>;
\end{verbatim}
\ttindex{FORT\_WIDTH} which sets the total width of a given line to
{\tt <integer>}.  The initial FORTRAN output width is 70.

{\REDUCE} automatically inserts a decimal point after each isolated integer
coefficient in a FORTRAN expression (so that, for example, 4 becomes
{\tt 4.} ). To prevent this, set the {\tt PERIOD}\ttindex{PERIOD}
mode switch to {\tt OFF}.

FORTRAN output is normally produced in lower case.  If upper case is desired,
the switch {\tt FORTUPPER}\ttindex{FORTUPPER} should be turned on.

Finally, the default name {\tt ANS} assigned to an unnamed expression and
its subparts can be changed by the operator {\tt VARNAME}.
\ttindex{VARNAME}  This takes a single identifier as argument, which then
replaces {\tt ANS} as the expression name.  The value of {\tt VARNAME} is
its argument.

Further facilities for the production of FORTRAN and other language output
are provided by the SCOPE and GENTRAN
packages\extendedmanual{described in chapters~\ref{GENTRAN} and \ref{SCOPE}}.

\subsection{Saving Expressions for Later Use as Input}
\index{Saving an expression}

It is often useful to save an expression on an external file for use later
as input in further calculations. The commands for opening and closing
output files are explained elsewhere. However, we see in the examples on
output of expressions that the standard ``natural'' method of printing
expressions is not compatible with the input syntax. So to print the
expression in an input compatible form we must inhibit this natural style
by turning off the switch {\tt NAT}.\ttindex{NAT} If this is done, a
dollar sign will also be printed at the end of the expression.

{\it Example:}

The following sequence of commands
\begin{verbatim}
        off nat; out "out"; x := (y+z)^2; write "end";
        shut "out"; on nat;
\end{verbatim}
will generate a file {\tt out} that contains
\begin{verbatim}
        X := Y**2 + 2*Y*Z + Z**2$
        END$
\end{verbatim}

\subsection{Displaying Expression Structure}\index{Displaying structure}

In those cases where the final result has a complicated form, it is often
convenient to display the skeletal structure of the answer.  The operator
{\tt STRUCTR},\ttindex{STRUCTR} that takes a single expression as argument,
will do this for you.  Its syntax is:
\begin{verbatim}
   STRUCTR(EXPRN:algebraic[,ID1:identifier[,ID2:identifier]]);
\end{verbatim}
The structure is printed effectively as a tree, in which the subparts are
laid out with auxiliary names.  If the optional {\tt ID1} is absent, the
auxiliary names are prefixed by the root {\tt ANS}.  This root may be
changed by the operator {\tt VARNAME}\ttindex{VARNAME}.  If the
optional {\tt ID1} is present, and is an array name, the subparts are
named as elements of that array, otherwise {\tt ID1} is used as the root
prefix. (The second optional argument {\tt ID2} is explained later.)

The {\tt EXPRN} can be either a scalar or a matrix expression.  Use of any
other will result in an error.

{\it Example:}

Let us suppose that the workspace contains
{\tt ((A+B)\verb|^|2+C)\verb|^|3+D}.
Then the input {\tt STRUCTR WS;} will (with {\tt EXP} off) result in the
output:\newpage
\begin{verbatim}
        ANS3

           where

                          3
              ANS3 := ANS2  + D

                          2
              ANS2 := ANS1  + C

              ANS1 := A + B
\end{verbatim}
The workspace remains unchanged after this operation, since {\tt STRUCTR}
\ttindex{STRUCTR} in the default situation returns
no value (if {\tt STRUCTR} is used as a sub-expression, its value is taken
to be 0).  In addition, the sub-expressions are normally only displayed
and not retained. If you wish to access the sub-expressions with their
displayed names, the switch {\tt SAVESTRUCTR}\ttindex{SAVESTRUCTR} should be
turned on.  In this case, {\tt STRUCTR} returns a list whose first element
is a representation for the expression, and subsequent elements are the
sub-expression relations.  Thus, with {\tt SAVESTRUCTR} on, {\tt STRUCTR WS}
in the above example would return
\vspace{-11pt}
\begin{verbatim}
                       3              2
        {ANS3,ANS3=ANS2  + D,ANS2=ANS1  + C,ANS1=A + B}
\end{verbatim}
The {\tt PART}\ttindex{PART} operator can
be used to retrieve the required parts of the expression.  For example, to
get the value of {\tt ANS2} in the above, one could say:
\begin{verbatim}
        part(ws,3,2);
\end{verbatim}
If {\tt FORT} is on, then the results are printed in the reverse order; the
algorithm in fact guaranteeing that no sub-expression will be referenced
before it is defined.  The second optional argument {\tt ID2} may also be
used in this case to name the actual expression (or expressions in the
case of a matrix argument).

{\it Example:}

Let us suppose that {\tt M}, a 2 by 1 matrix, contains the elements {\tt
((a+b)\verb|^|2 + c)\verb|^|3 + d} and {\tt (a + b)*(c + d)} respectively,
and that {\tt V} has been declared to be an array.  With {\tt EXP} off and
{\tt FORT} on, the statement {\tt structr(2*m,v,k);} will result in the output

\begin{verbatim}
      V(1)=A+B
      V(2)=V(1)**2+C
      V(3)=V(2)**3+D
      V(4)=C+D
      K(1,1)=2.*V(3)
      K(2,1)=2.*V(1)*V(4)
\end{verbatim}

\section{Changing the Internal Order of Variables}

The internal ordering of variables (more specifically kernels) can have
a significant effect on the space and time associated with a calculation.
In its default state, {\REDUCE} uses a specific order for this which may
vary between sessions.  However, it is possible for the user to change
this internal order by means of the declaration
{\tt KORDER}\ttindex{KORDER}.  The syntax for this is:
\begin{verbatim}
        korder v1,...,vn;
\end{verbatim}
where the {\tt Vi} are kernels\index{Kernel}.  With this declaration, the
{\tt Vi} are ordered internally ahead of any other kernels in the system.
{\tt V1} has the highest order, {\tt V2} the next highest, and so on.  A
further call of {\tt KORDER} replaces a previous one. {\tt KORDER NIL;}
resets the internal order to the system default.

Unlike the {\tt ORDER}\ttindex{ORDER} declaration, that has a purely
cosmetic effect on the way results are printed, the use of {\tt KORDER}
can have a significant effect on computation time.  In critical cases
then, the user can experiment with the ordering of the variables used to
determine the optimum set for a given problem.

\section{Obtaining Parts of Algebraic Expressions}

There are many occasions where it is desirable to obtain a specific part
of an expression, or even change such a part to another expression. A
number of operators are available in {\REDUCE} for this purpose, and will be
described in this section. In addition, operators for obtaining specific
parts of polynomials and rational functions (such as a denominator) are
described in another section.

\subsection{COEFF Operator}\ttindex{COEFF}
Syntax:
\begin{verbatim}
        COEFF(EXPRN:polynomial,VAR:kernel)
\end{verbatim}
{\tt COEFF} is an operator that partitions {\tt EXPRN} into its various
coefficients with respect to {\tt VAR} and returns them as a list, with
the coefficient independent of {\tt VAR} first.

Under normal circumstances, an error results if {\tt EXPRN} is not a
polynomial in {\tt VAR}, although the coefficients themselves can be
rational as long as they do not depend on {\tt VAR}.  However, if the
switch {\tt RATARG}\ttindex{RATARG} is on, denominators are not checked for
dependence on {\tt VAR}, and are taken to be part of the coefficients.

{\it Example:}
\begin{verbatim}
        coeff((y^2+z)^3/z,y);
\end{verbatim}
returns the result
\begin{verbatim}
          2
        {Z ,0,3*Z,0,3,0,1/Z}.
\end{verbatim}
whereas
\begin{verbatim}
        coeff((y^2+z)^3/y,y);
\end{verbatim}
gives an error if {\tt RATARG} is off, and the result
\begin{verbatim}
          3        2
        {Z /Y,0,3*Z /Y,0,3*Z/Y,0,1/Y}
\end{verbatim}
if {\tt RATARG} is on.

The length of the result of {\tt COEFF} is the highest power of {\tt VAR}
encountered plus 1.  In the above examples it is 7.  In addition, the
variable {\tt HIGH\_POW}\ttindex{HIGH\_POW} is set to the highest non-zero
power found in {\tt EXPRN} during the evaluation, and {\tt LOW\_POW}
\ttindex{LOW\_POW} to the lowest non-zero power, or zero if there is a
constant term.  If {\tt EXPRN} is a constant, then {\tt HIGH\_POW} and
{\tt LOW\_POW} are both set to zero.

\subsection{COEFFN Operator}\ttindex{COEFFN}

The {\tt COEFFN} operator is designed to give the user a particular
coefficient of a variable in a polynomial, as opposed to {\tt COEFF} that
returns all coefficients. {\tt COEFFN} is used with the syntax
\begin{verbatim}
        COEFFN(EXPRN:polynomial,VAR:kernel,N:integer)
\end{verbatim}
It returns the $n^{th}$ coefficient of {\tt VAR} in the polynomial
{\tt EXPRN}.

\subsection{PART Operator}\ttindex{PART}
Syntax:
\begin{verbatim}
        PART(EXPRN:algebraic[,INTEXP:integer])
\end{verbatim}

This operator works on the form of the expression as printed {\em or as it
would have been printed at that point in the calculation\/} bearing in mind
all the relevant switch settings at that point.  The reader therefore
needs some familiarity with the way that expressions are represented in
prefix form in {\REDUCE} to use these operators effectively.  Furthermore,
it is assumed that {\tt PRI} is {\tt ON} at that point in the calculation.
The reason for this is that with {\tt PRI} off, an expression is printed
by walking the tree representing the expression internally.  To save
space, it is never actually transformed into the equivalent prefix
expression as occurs when {\tt PRI} is on.  However, the operations on
polynomials described elsewhere can be equally well used in this case to
obtain the relevant parts.

The evaluation proceeds recursively down the integer expression list. In
other words,
\begin{verbatim}
     PART(<expression>,<integer1>,<integer2>)
         ->  PART(PART(<expression>,<integer1>),<integer2>)
\end{verbatim}
 and so on, and
\begin{verbatim}
        PART(<expression>) ->  <expression>.
\end{verbatim}
{\tt INTEXP} can be any expression that evaluates to an integer.  If the
integer is positive, then that term of the expression is found.  If the
integer is 0, the operator is returned.  Finally, if the integer is
negative, the counting is from the tail of the expression rather than the
head.

For example, if the expression {\tt a+b} is printed as {\tt A+B} (i.e.,
the ordering of the variables is alphabetical), then
\begin{verbatim}
        part(a+b,2)  ->   B
        part(a+b,-1) ->   B
and
        part(a+b,0)  ->  PLUS
\end{verbatim}
An operator {\tt ARGLENGTH}\ttindex{ARGLENGTH} is available to determine
the number of arguments of the top level operator in an expression.  If
the expression does not contain a top level operator, then $-1$ is returned.
For example,
\begin{verbatim}
        arglength(a+b+c) ->  3
        arglength(f())   ->  0
        arglength(a)     ->  -1
\end{verbatim}

\subsection{Substituting for Parts of Expressions}

{\tt PART} may also be used to substitute for a given part of an
expression.  In this case, the {\tt PART} construct appears on the
left-hand side of an assignment statement, and the expression to replace
the given part on the right-hand side.

For example, with the normal settings of the {\REDUCE} switches:
\begin{verbatim}
        xx := a+b;
        part(xx,2) := c;   ->  A+C
        part(c+d,0) := -;   -> C-D
\end{verbatim}

Note that {\tt xx} in the above is not changed by this substitution.  In
addition, unlike expressions such as array and matrix elements that have
an {\em instant evaluation\/}\index{Instant evaluation} property, the values
of {\tt part(xx,2)} and {\tt part(c+d,0)} are also not changed.
\chapter{Polynomials and Rationals}

Many operations in computer algebra are concerned with polynomials
\index{Polynomial} and rational functions\index{Rational function}.  In
this section, we review some of the switches and operators available for
this purpose.  These are in addition to those that work on general
expressions (such as {\tt DF} and {\tt INT}) described elsewhere.  In the
case of operators, the arguments are first simplified before the
operations are applied.  In addition, they operate only on arguments of
prescribed types, and produce a type mismatch error if given arguments
which cannot be interpreted in the required mode with the current switch
settings.  For example, if an argument is required to be a kernel and
{\tt a/2} is used (with no other rules for {\tt A}), an error
\begin{verbatim}
        A/2 invalid as kernel
\end{verbatim}
will result.

With the exception of those that select various parts of a polynomial or
rational function, these operations have potentially significant effects on
the space and time associated with a given calculation. The user should
therefore experiment with their use in a given calculation in order to
determine the optimum set for a given problem.

One such operation provided by the system is an operator {\tt LENGTH}
\ttindex{LENGTH} which returns the number of top level terms in the
numerator of its argument.  For example,
\begin{verbatim}
        length ((a+b+c)^3/(c+d));
\end{verbatim}
has the value 10.  To get the number of terms in the denominator, one
would first select the denominator by the operator {\tt DEN}\ttindex{DEN}
and then call {\tt LENGTH}, as in
\begin{verbatim}
        length den ((a+b+c)^3/(c+d));
\end{verbatim}
Other operations currently supported, the relevant switches and operators,
and the required argument and value modes of the latter, follow.

\section{Controlling the Expansion of Expressions}

The switch {\tt EXP}\ttindex{EXP} controls the expansion of expressions.  If
it is off, no expansion of powers or products of expressions occurs.
Users should note however that in this case results come out in a normal
but not necessarily canonical form.  This means that zero expressions
simplify to zero, but that two equivalent expressions need not necessarily
simplify to the same form.

{\it Example:} With {\tt EXP} on, the two expressions
\begin{verbatim}
        (a+b)*(a+2*b)
\end{verbatim}
and
\begin{verbatim}
        a^2+3*a*b+2*b^2
\end{verbatim}
will both simplify to the latter form.  With {\tt EXP}
off, they would remain unchanged, unless the complete factoring {\tt
(ALLFAC)} option were in force. {\tt EXP} is normally on.

Several operators that expect a polynomial as an argument behave
differently when {\tt EXP} is off, since there is often only one term at
the top level.  For example, with {\tt EXP} off
\begin{verbatim}
        length((a+b+c)^3/(c+d));
\end{verbatim}
returns the value 1.

\section{Factorization of Polynomials}\index{Factorization}
{\REDUCE} is capable of factorizing univariate and multivariate polynomials
that have integer coefficients, finding all factors that also have integer
coefficients. The package for doing this was written by Dr. Arthur C.
Norman and Ms. P. Mary Ann Moore at The University of Cambridge. It is
described in P. M. A. Moore and A. C. Norman, ``Implementing a Polynomial
Factorization and GCD Package'', Proc. SYMSAC '81, ACM (New York) (1981),
109-116.

The easiest way to use this facility is to turn on the switch
{\tt FACTOR},\ttindex{FACTOR} which causes all expressions to be output in
a factored form.  For example, with {\tt FACTOR} on, the expression
{\tt A\verb|^|2-B\verb|^|2} is returned as {\tt (A+B)*(A-B)}.

It is also possible to factorize a given expression explicitly.  The
operator {\tt FACTORIZE}\ttindex{FACTORIZE} that invokes this facility is
used with the syntax
\begin{verbatim}
     FACTORIZE(EXPRN:polynomial[,INTEXP:prime integer]):list,
\end{verbatim}
the optional argument of which will be described later. Thus to find and
display all factors of the cyclotomic polynomial $x^{105}-1$, one could
write:
\begin{verbatim}
        factorize(x^105-1);
\end{verbatim}
The result is a list of factor,exponent pairs.
In the above example, there is no overall numerical factor in the result,
so the results will consist only of polynomials in x.  The number of such
polynomials can be found by using the operator {\tt LENGTH}.\ttindex{LENGTH}
If there is a numerical factor, as in factorizing $12x^{2}-12$,
that factor will appear as the first member of the result.
It will however not be factored further.  Prime factors of such numbers
can be found, using a probabilistic algorithm, by turning on the switch
{\tt IFACTOR}.\ttindex{IFACTOR}  For example,
\begin{verbatim}
        on ifactor; factorize(12x^2-12);
\end{verbatim}
would result in the output
\begin{verbatim}
        {{2,2},{3,1},{X + 1,1},{X - 1,1}}.
\end{verbatim}

If the first argument of {\tt FACTORIZE} is an integer, it will be
decomposed into its prime components, whether or not {\tt IFACTOR} is on.

Note that the {\tt IFACTOR} switch only affects the result of {\tt FACTORIZE}.
It has no effect if the {\tt FACTOR}\ttindex{FACTOR} switch is also on.

The order in which the factors occur in the result (with the exception of
a possible overall numerical coefficient which comes first) can be system
dependent and should not be relied on. Similarly it should be noted that
any pair of individual factors can be negated without altering their
product, and that {\REDUCE} may sometimes do that.

The factorizer works by first reducing multivariate problems to univariate
ones and then solving the univariate ones modulo small primes. It normally
selects both evaluation points and primes using a random number generator
that should lead to different detailed behavior each time any particular
problem is tackled. If, for some reason, it is known that a certain
(probably univariate) factorization can be performed effectively with a
known prime, {\tt P} say, this value of {\tt P} can be handed to
{\tt FACTORIZE}\ttindex{FACTORIZE} as a second
argument. An error will occur if a non-prime is provided to {\tt FACTORIZE} in
this manner. It is also an error to specify a prime that divides the
discriminant of the polynomial being factored, but users should note that
this condition is not checked by the program, so this capability should be
used with care.

Factorization can be performed over a number of polynomial coefficient
domains in addition to integers. The particular description of the relevant
domain should be consulted to see if factorization is supported. For
example, the following statements will factorize $x^{4}+1$ modulo 7:
\begin{verbatim}
        setmod 7;
        on modular;
        factorize(x^4+1);
\end{verbatim}
The factorization module is provided with a trace facility that may be useful
as a way of monitoring progress on large problems, and of satisfying
curiosity about the internal workings of the package. The most simple use
of this is enabled by issuing the {\REDUCE} command\ttindex{TRFAC}
{\tt on trfac;} .
Following this, all calls to the factorizer will generate informative
messages reporting on such things as the reduction of multivariate to
univariate cases, the choice of a prime and the reconstruction of full
factors from their images.  Further levels of detail in the trace are
intended mainly for system tuners and for the investigation of suspected
bugs.  For example, {\tt TRALLFAC} gives tracing information at all levels
of detail.  The switch that can be set by {\tt on timings;} makes it
possible for one who is familiar with the algorithms used to determine
what part of the factorization code is consuming the most resources.
{\tt on overview}; reduces the amount of detail presented in other forms of
trace.  Other forms of trace output are enabled by directives of the form
\begin{verbatim}
        symbolic set!-trace!-factor(<number>,<filename>);
\end{verbatim}
where useful numbers are 1, 2, 3 and 100, 101, ... .  This facility is
intended to make it possible to discover in fairly great detail what just
some small part of the code has been doing --- the numbers refer mainly to
depths of recursion when the factorizer calls itself, and to the split
between its work forming and factorizing images and reconstructing full
factors from these.  If {\tt NIL} is used in place of a filename the trace
output requested is directed to the standard output stream.  After use of
this trace facility the generated trace files should be closed by calling
\begin{verbatim}
        symbolic close!-trace!-files();
\end{verbatim}
{\it NOTE:} Using the factorizer with {\tt MCD}\ttindex{MCD} off will
result in an error.

\section{Cancellation of Common Factors}
Facilities are available in {\REDUCE} for cancelling common factors in the
numerators and denominators of expressions, at the option of the user. The
system will perform this greatest common divisor computation if the switch
{\tt GCD}\ttindex{GCD} is on. ({\tt GCD} is normally off.)

A check is automatically made, however, for common variable and numerical
products in the numerators and denominators of expressions, and the
appropriate cancellations made.

When {\tt GCD} is on, and {\tt EXP} is off, a check is made for square
free factors in an expression.  This includes separating out and
independently checking the content of a given polynomial where
appropriate. (For an explanation of these terms, see Anthony C. Hearn,
``Non-Modular Computation of Polynomial GCDs Using Trial Division'', Proc.
EUROSAM 79, published as Lecture Notes on Comp.  Science, Springer-Verlag,
Berlin, No 72 (1979) 227-239.)

{\it Example:} With {\tt EXP}\ttindex{EXP} off and {\tt GCD}\ttindex{GCD}
on,
the polynomial {\tt a*c+a*d+b*c+b*d} would be returned as {\tt (A+B)*(C+D)}.

Under normal circumstances, GCDs are computed using an algorithm described
in the above paper. It is also possible in {\REDUCE} to compute GCDs using
an alternative algorithm, called the EZGCD Algorithm, which uses modular
arithmetic.  The switch {\tt EZGCD}\ttindex{EZGCD}, if on in addition to
{\tt GCD}, makes this happen.

In non-trivial cases, the EZGCD algorithm is almost always better
than the basic algorithm, often by orders of magnitude.  We therefore
{\em strongly\/} advise users to use the {\tt EZGCD} switch where they have the
resources available for supporting the package.

For a description of the EZGCD algorithm, see J. Moses and D.Y.Y. Yun,
``The EZ GCD Algorithm'', Proc. ACM 1973, ACM, New York (1973) 159-166.

{\it NOTE:}
This package shares code with the factorizer, so a certain amount of trace
information can be produced using the factorizer trace switches.

\subsection{Determining the GCD of Two Polynomials}
This operator, used with the syntax
\begin{verbatim}
        GCD(EXPRN1:polynomial,EXPRN2:polynomial):polynomial,
\end{verbatim}
returns the greatest common divisor of the two polynomials {\tt EXPRN1} and
{\tt EXPRN2}.

{\it Examples:}
\begin{verbatim}
        gcd(x^2+2*x+1,x^2+3*x+2) ->  X+1
        gcd(2*x^2-2*y^2,4*x+4*y) ->  2*X+2*Y
        gcd(x^2+y^2,x-y)         ->  1.
\end{verbatim}

\section{Working with Least Common Multiples}

Greatest common divisor calculations can often become expensive if
extensive work with large rational expressions is required. However, in
many cases, the only significant cancellations arise from the fact that
there are often common factors in the various denominators which are
combined when two rationals are added. Since these denominators tend to be
smaller and more regular in structure than the numerators, considerable
savings in both time and space can occur if a full GCD check is made when
the denominators are combined and only a partial check when numerators are
constructed. In other words, the true least common multiple of the
denominators is computed at each step. The switch {\tt LCM}\ttindex{LCM}
is available for this purpose, and is normally on.

In addition, the operator {\tt LCM},\ttindex{LCM} used with the syntax
\begin{verbatim}
        LCM(EXPRN1:polynomial,EXPRN2:polynomial):polynomial,
\end{verbatim}
returns the least common multiple of the two polynomials {\tt EXPRN1} and
{\tt EXPRN2}.

{\it Examples:}
\begin{verbatim}
        lcm(x^2+2*x+1,x^2+3*x+2) ->  X**3 + 4*X**2 + 5*X + 2
        lcm(2*x^2-2*y^2,4*x+4*y) ->  4*(X**2 - Y**2)
\end{verbatim}

\section{Controlling Use of Common Denominators}

When two rational functions are added, {\REDUCE} normally produces an
expression over a common denominator. However, if the user does not want
denominators combined, he or she can turn off the switch {\tt MCD}
\ttindex{MCD} which controls this process.  The latter switch is
particularly useful if no greatest common divisor calculations are
desired, or excessive differentiation of rational functions is required.

{\it CAUTION:}  With {\tt MCD} off, results are not guaranteed to come out in
either normal or canonical form.  In other words, an expression equivalent
to zero may in fact not be simplified to zero.  This option is therefore
most useful for avoiding expression swell during intermediate parts of a
calculation.

{\tt MCD}\ttindex{MCD} is normally on.

\section{REMAINDER Operator}\ttindex{REMAINDER}

This operator is used with the syntax
\begin{verbatim}
     REMAINDER(EXPRN1:polynomial,EXPRN2:polynomial):polynomial.
\end{verbatim}
It returns the remainder when {\tt EXPRN1} is divided by {\tt EXPRN2}.  This
is the true remainder based on the internal ordering of the variables, and
not the pseudo-remainder. The pseudo-remainder \ttindex{PSEUDO\_REMAINDER}
and in general pseudo-division \ttindex{PSEUDO\_DIVIDE} of polynomials
can be calculated after loading  the {\tt polydiv} package.
Please refer to the documentation of this package for details.

{\it Examples:}
\begin{verbatim}
        remainder((x+y)*(x+2*y),x+3*y) ->  2*Y**2
        remainder(2*x+y,2)             ->  Y.
\end{verbatim}

{\it CAUTION:} In the default case, remainders are calculated over the
integers.  If you need the remainder with respect to another domain, it
must be declared explicitly.

{\it Example:}
\begin{verbatim}
        remainder(x^2-2,x+sqrt(2)); -> X^2 - 2
        load_package arnum;
        defpoly sqrt2**2-2;
        remainder(x^2-2,x+sqrt2); -> 0
\end{verbatim}

\section{RESULTANT Operator}\ttindex{RESULTANT}

This is used with the syntax
\begin{verbatim}
     RESULTANT(EXPRN1:polynomial,EXPRN2:polynomial,VAR:kernel):
        polynomial.
\end{verbatim}
It computes the resultant of the two given polynomials with respect to the
given variable, the coefficients of the polynomials can be taken from any
domain. The result can be identified as the determinant of a
Sylvester matrix, but can often also be thought of informally as the
result obtained when the given variable is eliminated between the two input
polynomials. If the two input polynomials have a non-trivial GCD their
resultant vanishes.

The switch {\tt Bezout}\ttindex{Bezout} controls the computation of the
resultants. It is off by default. In this case a subresultant algorithm
is used. If the switch Bezout is turned on, the resultant is computed via
the Bezout Matrix. However, in the latter case, only polynomial coefficients
are permitted.

\begin{samepage}
The sign conventions used by the resultant function follow those in R.
Loos, ``Computing in Algebraic Extensions'' in ``Computer Algebra --- Symbolic
and Algebraic Computation'', Second Ed., Edited by B. Buchberger, G.E.
Collins and R. Loos, Springer-Verlag, 1983. Namely, with {\tt A} and {\tt B}
not dependent on {\tt X}:

\begin{verbatim}
                               deg(p)*deg(q)
   resultant(p(x),q(x),x)= (-1)             *resultant(q,p,x)

                            deg(p)
   resultant(a,p(x),x)   = a

   resultant(a,b,x)      = 1
\end{verbatim}
\end{samepage}

{\it Examples:}

\begin{samepage}
\begin{verbatim}
                                     2
   resultant(x/r*u+y,u*y,u)   ->  - y
\end{verbatim}
\end{samepage}

{\it calculation in an algebraic extension:}

\begin{samepage}
\begin{verbatim}
   load arnum;
   defpoly sqrt2**2 - 2;

   resultant(x + sqrt2,sqrt2 * x +1,x) -> -1
\end{verbatim}
\end{samepage}

{\it or in a modular domain:}

\begin{samepage}
\begin{verbatim}
   setmod 17;
   on modular;

   resultant(2x+1,3x+4,x)    -> 5
\end{verbatim}
\end{samepage}
\section{DECOMPOSE Operator}\ttindex{DECOMPOSE}

The {\tt DECOMPOSE} operator takes a multivariate polynomial as argument,
and returns an expression and a list of equations from which the
original polynomial can be found by composition.  Its syntax is:
\begin{verbatim}
     DECOMPOSE(EXPRN:polynomial):list.
\end{verbatim}
For example:
\begin{verbatim}
     decompose(x^8-88*x^7+2924*x^6-43912*x^5+263431*x^4-
                    218900*x^3+65690*x^2-7700*x+234)
                   2                  2            2
              -> {U  + 35*U + 234, U=V  + 10*V, V=X  - 22*X}
                                     2
     decompose(u^2+v^2+2u*v+1)  -> {W  + 1, W=U + V}
\end{verbatim}
Users should note however that, unlike factorization, this decomposition
is not unique.

\section{INTERPOL operator}\ttindex{INTERPOL}

Syntax:
\begin{verbatim}
        INTERPOL(<values>,<variable>,<points>);
\end{verbatim}

where {\tt <values>} and {\tt <points>} are lists of equal length and
{\tt <variable>} is an algebraic expression (preferably a kernel).

{\tt INTERPOL} generates an interpolation polynomial {\em f\/} in the given
variable of degree length({\tt <values>})-1.  The unique polynomial {\em f\/}
is defined by the property that for corresponding elements {\em v\/} of
{\tt <values>} and {\em p\/} of {\tt <points>} the relation $f(p)=v$ holds.

The Aitken-Neville interpolation algorithm is used which guarantees a
stable result even with rounded numbers and an ill-conditioned problem.

\section{Obtaining Parts of Polynomials and Rationals}

These operators select various parts of a polynomial or rational function
structure. Except for the cost of rearrangement of the structure, these
operations take very little time to perform.

For those operators in this section that take a kernel {\tt VAR} as their
second argument, an error results if the first expression is not a
polynomial in {\tt VAR}, although the coefficients themselves can be
rational as long as they do not depend on {\tt VAR}.  However, if the
switch {\tt RATARG}\ttindex{RATARG} is on, denominators are not checked
for dependence on {\tt VAR}, and are taken to be part of the coefficients.

\subsection{DEG Operator}\ttindex{DEG}

This operator is used with the syntax
\begin{verbatim}
        DEG(EXPRN:polynomial,VAR:kernel):integer.
\end{verbatim}
It returns the leading degree\index{Degree} of the polynomial {\tt EXPRN}
in the variable {\tt VAR}.  If {\tt VAR} does not occur as a variable in
{\tt EXPRN}, 0 is returned.

{\it Examples:}
\begin{verbatim}
        deg((a+b)*(c+2*d)^2,a) ->  1
        deg((a+b)*(c+2*d)^2,d) ->  2
        deg((a+b)*(c+2*d)^2,e) ->  0.
\end{verbatim}
Note also that if {\tt RATARG} is on,
\begin{verbatim}
        deg((a+b)^3/a,a)       ->  3
\end{verbatim}
since in this case, the denominator {\tt A} is considered part of the
coefficients of the numerator in {\tt A}.  With {\tt RATARG} off, however,
an error would result in this case.

\subsection{DEN Operator}\ttindex{DEN}

This is used with the syntax:
\begin{verbatim}
        DEN(EXPRN:rational):polynomial.
\end{verbatim}
It returns the denominator of the rational expression {\tt EXPRN}.  If
{\tt EXPRN} is a polynomial, 1 is returned.

{\it Examples:}
\begin{verbatim}
        den(x/y^2)   ->  Y**2
        den(100/6)   ->  3
                [since 100/6 is first simplified to 50/3]
        den(a/4+b/6) ->  12
        den(a+b)     ->  1
\end{verbatim}

\subsection{LCOF Operator}\ttindex{LCOF}

LCOF is used with the syntax
\begin{verbatim}
        LCOF(EXPRN:polynomial,VAR:kernel):polynomial.
\end{verbatim}
It returns the leading coefficient\index{Leading coefficient} of the
polynomial {\tt EXPRN} in the variable {\tt VAR}.  If {\tt VAR} does not
occur as a variable in {\tt EXPRN}, {\tt EXPRN} is returned.
\extendedmanual{\newpage}
{\it Examples:}
\begin{verbatim}
        lcof((a+b)*(c+2*d)^2,a) ->  C**2+4*C*D+4*D**2
        lcof((a+b)*(c+2*d)^2,d) ->  4*(A+B)
        lcof((a+b)*(c+2*d),e)   ->  A*C+2*A*D+B*C+2*B*D
\end{verbatim}

\subsection{LPOWER Operator}\ttindex{LPOWER}

\begin{samepage}
Syntax:
\begin{verbatim}
        LPOWER(EXPRN:polynomial,VAR:kernel):polynomial.
\end{verbatim}
LPOWER returns the leading power of {\tt EXPRN} with respect to {\tt VAR}.
If {\tt EXPRN} does not depend on {\tt VAR}, 1 is returned.
\end{samepage}

{\it Examples:}
\begin{verbatim}
        lpower((a+b)*(c+2*d)^2,a) ->  A
        lpower((a+b)*(c+2*d)^2,d) ->  D**2
        lpower((a+b)*(c+2*d),e)   ->  1
\end{verbatim}

\subsection{LTERM Operator}\ttindex{LTERM}

\begin{samepage}
Syntax:
\begin{verbatim}
        LTERM(EXPRN:polynomial,VAR:kernel):polynomial.
\end{verbatim}
LTERM returns the leading term of {\tt EXPRN} with respect to {\tt VAR}.
If {\tt EXPRN} does not depend on {\tt VAR}, {\tt EXPRN} is returned.
\end{samepage}

{\it Examples:}
\begin{verbatim}
        lterm((a+b)*(c+2*d)^2,a) ->  A*(C**2+4*C*D+4*D**2)
        lterm((a+b)*(c+2*d)^2,d) ->  4*D**2*(A+B)
        lterm((a+b)*(c+2*d),e)   ->  A*C+2*A*D+B*C+2*B*D
\end{verbatim}

{\COMPATNOTE} In some earlier versions of REDUCE, {\tt LTERM} returned
{\tt 0} if the {\tt EXPRN} did not depend on {\tt VAR}.  In the present
version, {\tt EXPRN} is always equal to {\tt LTERM(EXPRN,VAR)} $+$ {\tt
REDUCT(EXPRN,VAR)}.

\subsection{MAINVAR Operator}\ttindex{MAINVAR}

Syntax:
\begin{verbatim}
        MAINVAR(EXPRN:polynomial):expression.
\end{verbatim}
Returns the main variable (based on the internal polynomial representation)
of {\tt EXPRN}. If {\tt EXPRN} is a domain element, 0 is returned.

{\it Examples:}

Assuming {\tt A} has higher kernel order than {\tt B}, {\tt C}, or {\tt D}:
\begin{verbatim}
        mainvar((a+b)*(c+2*d)^2) ->  A
        mainvar(2)               ->  0
\end{verbatim}

\subsection{NUM Operator}\ttindex{NUM}

Syntax:
\begin{verbatim}
        NUM(EXPRN:rational):polynomial.
\end{verbatim}
Returns the numerator of the rational expression {\tt EXPRN}.  If {\tt EXPRN}
is a polynomial, that polynomial is returned.

{\it Examples:}
\begin{verbatim}
        num(x/y^2)  ->  X
        num(100/6)   ->  50
        num(a/4+b/6) ->  3*A+2*B
        num(a+b)     ->  A+B
\end{verbatim}

\subsection{REDUCT Operator}\ttindex{REDUCT}

Syntax:
\begin{verbatim}
        REDUCT(EXPRN:polynomial,VAR:kernel):polynomial.
\end{verbatim}
Returns the reductum of {\tt EXPRN} with respect to {\tt VAR} (i.e., the
part of {\tt EXPRN} left after the leading term is removed).  If {\tt
EXPRN} does not depend on the variable {\tt VAR}, 0 is returned.

{\it Examples:}
\begin{verbatim}
     reduct((a+b)*(c+2*d),a) ->  B*(C + 2*D)
     reduct((a+b)*(c+2*d),d) ->  C*(A + B)
     reduct((a+b)*(c+2*d),e) ->  0
\end{verbatim}

{\COMPATNOTE} In some earlier versions of REDUCE, {\tt REDUCT} returned
{\tt EXPRN} if it did not depend on {\tt VAR}.  In the present version, {\tt
EXPRN} is always equal to {\tt LTERM(EXPRN,VAR)} $+$ {\tt
REDUCT(EXPRN,VAR)}.

\section{Polynomial Coefficient Arithmetic}\index{Coefficient}
{\REDUCE} allows for a variety of numerical domains for the numerical
coefficients of polynomials used in calculations.  The default mode is
integer arithmetic, although the possibility of using real coefficients
\index{Real coefficient} has been discussed elsewhere.  Rational
coefficients have also been available by using integer coefficients in
both the numerator and denominator of an expression, using the {\tt ON
DIV}\ttindex{DIV} option to print the coefficients as rationals.
However, {\REDUCE} includes several other coefficient options in its basic
version which we shall describe in this section.  All such coefficient
modes are supported in a table-driven manner so that it is
straightforward to extend the range of possibilities.  A description of
how to do this is given in R.J. Bradford, A.C. Hearn, J.A. Padget and
E. Schr\"ufer, ``Enlarging the {\REDUCE} Domain of Computation,'' Proc. of
SYMSAC '86, ACM, New York (1986), 100--106.

\subsection{Rational Coefficients in Polynomials}\index{Coefficient}
\index{Rational coefficient}
Instead of treating rational numbers as the numerator and denominator of a
rational expression, it is also possible to use them as polynomial
coefficients directly. This is accomplished by turning on the switch
{\tt RATIONAL}.\ttindex{RATIONAL}

{\it Example:} With {\tt RATIONAL} off, the input expression {\tt a/2}
would be converted into a rational expression, whose numerator was {\tt A}
and denominator 2.  With {\tt RATIONAL} on, the same input would become a
rational expression with numerator {\tt 1/2*A} and denominator {\tt 1}.
Thus the latter can be used in operations that require polynomial input
whereas the former could not.

\subsection{Real Coefficients in Polynomials}\index{Coefficient}
\index{Real coefficient}
The switch {\tt ROUNDED}\ttindex{ROUNDED} permits the use of arbitrary
sized real coefficients in polynomial expressions.  The actual precision
of these coefficients can be set by the operator {\tt PRECISION}.
\ttindex{PRECISION} For example, {\tt precision 50;} sets the precision to
fifty decimal digits.  The default precision is system dependent and can
be found by {\tt precision 0;}.  In this mode, denominators are
automatically made monic, and an appropriate adjustment is made to the
numerator.

{\it Example:} With {\tt ROUNDED} on, the input expression {\tt a/2} would
be converted into a rational expression whose numerator is {\tt 0.5*A} and
denominator {\tt 1}.

Internally, {\REDUCE} uses floating point numbers up to the precision
supported by the underlying machine hardware, and so-called {\em
bigfloats} for higher precision or whenever necessary to represent numbers
whose value cannot be represented in floating point.  The internal
precision is two decimal digits greater than the external precision to
guard against roundoff inaccuracies.  Bigfloats represent the fraction and
exponent parts of a floating-point number by means of (arbitrary
precision) integers, which is a more precise representation in many cases
than the machine floating point arithmetic, but not as efficient.  If a
case arises where use of the machine arithmetic leads to problems, a user
can force {\REDUCE} to use the bigfloat representation at all precisions by
turning on the switch {\tt ROUNDBF}.\ttindex{ROUNDBF}  In rare cases,
this switch is turned on by the system, and the user informed by the
message
\begin{verbatim}
        ROUNDBF turned on to increase accuracy
\end{verbatim}

Rounded numbers are normally printed to the specified precision.  However,
if the user wishes to print such numbers with less precision, the printing
precision can be set by the command {\tt PRINT\_PRECISION}.
\ttindex{PRINT\_PRECISION} For example, {\tt print\_precision 5;} will
cause such numbers to be printed with five digits maximum.

Under normal circumstances when {\tt ROUNDED} is on, {\REDUCE} converts the
number 1.0 to the integer 1.  If this is not desired, the switch
{\tt NOCONVERT}\ttindex{NOCONVERT} can be turned on.

Numbers that are stored internally as bigfloats are normally printed with
a space between every five digits to improve readability.  If this
feature is not required, it can be suppressed by turning off the switch
{\tt BFSPACE}.\ttindex{BFSPACE}

Further information on the bigfloat arithmetic may be found in T. Sasaki,
``Manual for Arbitrary Precision Real Arithmetic System in {\REDUCE}'',
Department of Computer Science, University of Utah, Technical Note No.
TR-8 (1979).

When a real number is input, it is normally truncated to the precision in
effect at the time the number is read.  If it is desired to keep the full
precision of all numbers input, the switch {\tt ADJPREC}\ttindex{ADJPREC}
(for {\em adjust precision\/}) can be turned on.  While on, {\tt ADJPREC}
will automatically increase the precision, when necessary, to match that
of any integer or real input, and a message printed to inform the user of
the precision increase.

When {\tt ROUNDED} is on, rational numbers are normally converted to
rounded representation.  However, if a user wishes to keep such numbers in
a rational form until used in an operation that returns a real number,
the switch {\tt ROUNDALL}\ttindex{ROUNDALL} can be turned off.  This
switch is normally on.

Results from rounded calculations are returned in rounded form with two
exceptions: if the result is recognized as {\tt 0} or {\tt 1} to the
current precision, the integer result is returned.

\subsection{Modular Number Coefficients in Polynomials}\index{Coefficient}
\index{Modular coefficient}
{\REDUCE} includes facilities for manipulating polynomials whose
coefficients are computed modulo a given base.  To use this option, two
commands must be used; {\tt SETMOD} {\tt <integer>},\ttindex{SETMOD} to set
the prime modulus, and {\tt ON MODULAR}\ttindex{MODULAR} to cause the
actual modular calculations to occur.
For example, with {\tt setmod 3;} and {\tt on modular;}, the polynomial
{\tt (a+2*b)\verb|^|3} would become {\tt A\verb|^|3+2*B\verb|^|3}.

The argument of {\tt SETMOD} is evaluated algebraically, except that
non-modular (integer) arithmetic is used.  Thus the sequence
\begin{verbatim}
        setmod 3; on modular; setmod 7;
\end{verbatim}
will correctly set the modulus to 7.

Modular numbers are by default represented by integers in the interval
[0,p-1] where p is the current modulus.  Sometimes it is more convenient
to use an equivalent symmetric representation in the interval
[-p/2+1,p/2], or more precisely
[-floor((p-1)/2), ceiling((p-1)/2)],
especially if the modular numbers map objects that include
negative quantities.  The switch {\tt BALANCED\_MOD}\ttindex{BALANCED\_MOD}
allows you to select the symmetric representation for output.

Users should note that the modular calculations are on the polynomial
coefficients only.  It is not currently possible to reduce the exponents
since no check for a prime modulus is made (which would allow
$x^{p-1}$ to be reduced to 1 mod p).  Note also that any division by a
number not co-prime with the modulus will result in the error ``Invalid
modular division''.

\subsection{Complex Number Coefficients in Polynomials}\index{Coefficient}
\index{Complex coefficient}
Although {\REDUCE} routinely treats the square of the variable {\em i\/} as
equivalent to $-1$, this is not sufficient to reduce expressions involving
{\em i\/} to lowest terms, or to factor such expressions over the complex
numbers.  For example, in the default case,
\begin{verbatim}
        factorize(a^2+1);
\end{verbatim}
gives the result
\begin{verbatim}
        {{A**2+1,1}}
\end{verbatim}
and
\begin{verbatim}
        (a^2+b^2)/(a+i*b)
\end{verbatim}
is not reduced further.  However, if the switch
{\tt COMPLEX}\ttindex{COMPLEX} is turned on, full complex arithmetic is then
carried out.  In other words, the above factorization will give the result
\begin{verbatim}
        {{A + I,1},{A - I,1}}
\end{verbatim}
and the quotient will be reduced to {\tt A-I*B}.

The switch {\tt COMPLEX} may be combined with {\tt ROUNDED} to give complex
real numbers; the appropriate arithmetic is performed in this case.

Complex conjugation is used to remove complex numbers from denominators of
expressions.  To do this if {\tt COMPLEX} is off, you must turn the switch
{\tt RATIONALIZE}\ttindex{RATIONALIZE} on.

\chapter{Substitution Commands}\index{Substitution}
An important class of commands in {\REDUCE} define
substitutions for variables and expressions to be made during the
evaluation of expressions.  Such substitutions use the prefix operator
{\tt SUB}, various forms of the command {\tt LET}, and rule sets.

\section{SUB Operator}\ttindex{SUB}

Syntax:
\begin{verbatim}
        SUB(<substitution_list>,EXPRN1:algebraic):algebraic
\end{verbatim}
where {\tt <substitution\_list>} is a list of one or more equations of the
form
\begin{verbatim}
        VAR:kernel=EXPRN:algebraic
\end{verbatim}
or a kernel that evaluates to such a list.

The {\tt SUB} operator gives the algebraic result of replacing every
occurrence of the variable {\tt VAR} in the expression {\tt EXPRN1} by the
expression {\tt EXPRN}.  Specifically, {\tt EXPRN1} is first evaluated
using all available rules.  Next the substitutions are made, and finally
the substituted expression is reevaluated.  When more than one variable
occurs in the substitution list, the substitution is performed by
recursively walking down the tree representing {\tt EXPRN1}, and replacing
every {\tt VAR} found by the appropriate {\tt EXPRN}.  The {\tt EXPRN} are
not themselves searched for any occurrences of the various {\tt VAR}s.
The trivial case {\tt SUB(EXPRN1)} returns the algebraic value of
{\tt EXPRN1}.

{\it Examples:}
\begin{verbatim}
                                    2              2
     sub({x=a+y,y=y+1},x^2+y^2) -> A  + 2*A*Y + 2*Y  + 2*Y + 1
\end{verbatim}
and with {\tt s := \{x=a+y,y=y+1\}},
\begin{verbatim}
                                    2              2
     sub(s,x^2+y^2)             -> A  + 2*A*Y + 2*Y  + 2*Y + 1
\end{verbatim}

Note that the global assignments {\tt x:=a+y}, etc., do not take place.

{\tt EXPRN1} can be any valid algebraic expression whose type is such that
a substitution process is defined for it (e.g., scalar expressions, lists
and matrices).  An error will occur if an expression of an invalid type
for substitution occurs either in {\tt EXPRN} or {\tt EXPRN1}.

The braces around the substitution list may also be omitted, as in:

\begin{verbatim}
                                    2              2
     sub(x=a+y,y=y+1,x^2+y^2)   -> A  + 2*A*Y + 2*Y  + 2*Y + 1
\end{verbatim}

\section{LET Rules}\ttindex{LET}
Unlike substitutions introduced via {\tt SUB}, {\tt LET}
rules are global in scope and stay in effect until replaced or {\tt CLEAR}ed.

The simplest use of the {\tt LET} statement is in the form
\begin{verbatim}
        LET <substitution list>
\end{verbatim}
where {\tt <substitution list>} is a list of rules separated by commas, each
of the form:
\begin{verbatim}
        <variable> = <expression>
\end{verbatim}
or
\begin{verbatim}
    <prefix operator>(<argument>,...,<argument>) = <expression>
\end{verbatim}
or
\begin{verbatim}
    <argument> <infix operator>,..., <argument> = <expression>
\end{verbatim}
For example,
\begin{verbatim}
        let {x => y^2,
             h(u,v) => u - v,
             cos(pi/3) => 1/2,
             a*b => c,
             l+m => n,
             w^3 => 2*z - 3,
             z^10 => 0}
\end{verbatim}
The list brackets can be left out if preferred.  The above rules could
also have been entered as seven separate {\tt LET} statements.

After such {\tt LET} rules have been input, {\tt X} will always be
evaluated as the square of {\tt Y}, and so on.  This is so even if at the
time the {\tt LET} rule was input, the variable {\tt Y} had a value other
than {\tt Y}. (In contrast, the assignment {\tt x:=y\verb|^|2} will set {\tt X}
equal to the square of the current value of {\tt Y}, which could be quite
different.)

The rule {\tt let a*b=c} means that whenever {\tt A} and {\tt B} are both
factors in an expression their product will be replaced by {\tt C}.  For
example, {\tt a\verb|^|5*b\verb|^|7*w} would be replaced by
{\tt c\verb|^|5*b\verb|^|2*w}.

The rule for {\tt l+m} will not only replace all occurrences of {\tt l+m}
by {\tt N}, but will also normally replace {\tt L} by {\tt n-m}, but not
{\tt M} by {\tt n-l}.  A more complete description of this case is given
in Section~\ref{sec-gensubs}.

The rule pertaining to {\tt w\verb|^|3} will apply to any power of {\tt W}
greater than or equal to the third.

Note especially the last example, {\tt let z\verb|^|10=0}.  This declaration
means, in effect: ignore the tenth or any higher power of {\tt Z}.  Such
declarations, when appropriate, often speed up a computation to a
considerable degree. (See\index{Asymptotic command}
Section~\ref{sec-asymp} for more details.)

Any new operators occurring in such {\tt LET} rules will be automatically
declared {\tt OPERATOR} by the system, if the rules are being read from a
file.  If they are being entered interactively, the system will ask
{\tt DECLARE} ... {\tt OPERATOR?} .  Answer {\tt Y} or {\tt N} and hit
\key{Return}.

In each of these examples, substitutions are only made for the explicit
expressions given; i.e., none of the variables may be considered arbitrary
in any sense. For example, the command
\begin{verbatim}
        let h(u,v) = u - v;
\end{verbatim}
will cause {\tt h(u,v)} to evaluate to {\tt U - V}, but will not affect
{\tt h(u,z)} or {\tt H} with any arguments other than precisely the
symbols {\tt U,V}.

These simple {\tt LET} rules are on the same logical level as assignments
made with the := operator.  An assignment {\tt x := p+q} cancels a rule
{\tt let x = y\verb|^|2} made earlier, and vice versa.

{\it CAUTION:} A recursive rule such as
\begin{verbatim}
        let x = x + 1;
\end{verbatim}
is erroneous, since any subsequent evaluation of {\tt X} would lead to a
non-terminating chain of substitutions:
\begin{verbatim}
      x -> x + 1 -> (x + 1) + 1 -> ((x + 1) + 1) + 1 -> ...
\end{verbatim}
Similarly, coupled substitutions such as
\begin{verbatim}
        let l = m + n, n = l + r;
\end{verbatim}
would lead to the same error. As a result, if you try to evaluate an {\tt X},
{\tt L} or {\tt N} defined as above, you will get an error such as
\begin{verbatim}
        X improperly defined in terms of itself
\end{verbatim}

Array and matrix elements can appear on the left-hand side of a {\tt LET}
statement. However, because of their {\em instant evaluation\/}
\index{Instant evaluation} property, it is the value of the element that
is substituted for, rather than the element itself.  E.g.,
\begin{verbatim}
        array a(5);
        a(2) := b;
        let a(2) = c;
\end{verbatim}
results in {\tt B} being substituted by {\tt C}; the assignment for
{\tt a(2)} does not change.

Finally, if an error occurs in any equation in a {\tt LET} statement
(including generalized statements involving {\tt FOR ALL} and {\tt SUCH
THAT)}, the remaining rules are not evaluated.

\subsection{FOR ALL \ldots LET}\ttindex{FOR ALL}
If a substitution for all possible values of a given argument of an
operator is required, the declaration {\tt FOR ALL} may be used. The
syntax of such a command is
\begin{verbatim}
        FOR ALL <variable>,...,<variable>
                <LET statement> <terminator>
\end{verbatim}
e.g.,
\begin{verbatim}
        for all x,y let h(x,y) = x-y;
        for all x let k(x,y) = x^y;
\end{verbatim}
The first of these declarations would cause {\tt h(a,b)} to be evaluated
as {\tt A-B}, {\tt h(u+v,u+w)} to be {\tt V-W}, etc.  If the operator
symbol {\tt H} is used with more or fewer argument places, not two, the
{\tt LET} would have no effect, and no error would result.

The second declaration would cause {\tt k(a,y)} to be evaluated as
{\tt a\verb|^|y}, but would have no effect on {\tt k(a,z)} since the rule
didn't say {\tt FOR ALL Y} ... .

Where we used {\tt X} and {\tt Y} in the examples, any variables could
have been used.  This use of a variable doesn't affect the value it may
have outside the {\tt LET} statement.  However, you should remember what
variables you actually used.  If you want to delete the rule subsequently,
you must use the same variables in the {\tt CLEAR} command.

It is possible to use more complicated expressions as a template for a
{\tt LET} statement, as explained in the section on substitutions for
general expressions.  In nearly all cases, the rule will be accepted, and
a consistent application made by the system.  However, if there is a sole
constant or a sole free variable on the left-hand side of a rule (e.g.,
{\tt let 2=3} or {\tt for all x let x=2)}, then the system is unable to
handle the rule, and the error message
\begin{verbatim}
        Substitution for ... not allowed
\end{verbatim}
will be issued.  Any variable listed in the {\tt FOR ALL} part will have
its symbol preceded by an equal sign: {\tt X} in the above example will
appear as {\tt =X}.  An error will also occur if a variable in the
{\tt FOR ALL} part is not properly matched on both sides of the {\tt LET}
equation.

\subsection{FOR ALL \ldots SUCH THAT \ldots LET}
\ttindex{FOR ALL}\ttindex{SUCH THAT}

If a substitution is desired for more than a single value of a variable in
an operator or other expression, but not all values, a conditional form of
the {\tt FOR ALL \ldots LET} declaration can be used.

{\it Example:}
\begin{verbatim}
        for all x such that numberp x and x<0 let h(x)=0;
\end{verbatim}
will cause {\tt h(-5)} to be evaluated as 0, but {\tt H} of a positive
integer, or of an argument that is not an integer at all, would not be
affected.  Any boolean expression can follow the {\tt SUCH THAT} keywords.

\subsection{Removing Assignments and Substitution Rules}\ttindex{CLEAR}

The user may remove all assignments and substitution rules from any
expression by the command {\tt CLEAR}, in the form
\begin{verbatim}
        CLEAR <expression>,...,<expression><terminator>
\end{verbatim}
e.g.
\begin{verbatim}
        clear x, h(x,y);
\end{verbatim}
Because of their {\em instant evaluation\/} property, array and matrix elements
cannot be cleared with {\tt CLEAR}.  For example, if {\tt A} is an array,
you must say
\begin{verbatim}
        a(3) := 0;
\end{verbatim}
rather than
\begin{verbatim}
        clear a(3);
\end{verbatim}
to ``clear'' element {\tt a(3)}.

On the other hand, a whole array (or matrix) {\tt A} can be cleared by the
command {\tt clear a};  This means much more than resetting to 0 all the
elements of {\tt A}.  The fact that {\tt A} is an array, and what its
dimensions are, are forgotten, so {\tt A} can be redefined as another type
of object, for example an operator.

The more general types of {\tt LET} declarations can also be deleted by
using {\tt CLEAR}.  Simply repeat the {\tt LET} rule to be deleted, using
{\tt CLEAR} in place of {\tt LET}, and omitting the equal sign and
right-hand part.  The same dummy variables must be used in the {\tt FOR
ALL} part, and the boolean expression in the {\tt SUCH THAT} part must be
written the same way. (The placing of blanks doesn't have to be
identical.)

{\it Example:} The {\tt LET} rule
\begin{verbatim}
        for all x such that numberp x and x<0 let h(x)=0;
\end{verbatim}
can be erased by the command
\begin{verbatim}
        for all x such that numberp x and x<0 clear h(x);
\end{verbatim}

\subsection{Overlapping LET Rules}
{\tt CLEAR} is not the only way to delete a {\tt LET} rule.  A new {\tt
LET} rule identical to the first, but with a different expression after
the equal sign, replaces the first.  Replacements are also made in other
cases where the existing rule would be in conflict with the new rule.  For
example, a rule for {\tt x\verb|^|4} would replace a rule for {\tt x\verb|^|5}.
The user should however be cautioned against having several {\tt LET}
rules in effect that relate to the same expression.  No guarantee can be
given as to which rules will be applied by {\REDUCE} or in what order.  It
is best to {\tt CLEAR} an old rule before entering a new related {\tt LET}
rule.

\subsection{Substitutions for General Expressions}
\label{sec-gensubs}
The examples of substitutions discussed in other sections have involved
very simple rules. However, the substitution mechanism used in {\REDUCE} is
very general, and can handle arbitrarily complicated rules without
difficulty.

The general substitution mechanism used in {\REDUCE} is discussed in Hearn, A.
C., ``{\REDUCE}, A User-Oriented Interactive System for Algebraic
Simplification,'' Interactive Systems for Experimental Applied Mathematics,
(edited by M. Klerer and J. Reinfelds), Academic Press, New York (1968),
79-90, and Hearn. A. C., ``The Problem of Substitution,'' Proc. 1968 Summer
Institute on Symbolic Mathematical Computation, IBM Programming Laboratory
Report FSC 69-0312 (1969). For the reasons given in these
references, {\REDUCE} does not attempt to implement a general pattern
matching algorithm.  However, the present system uses far more sophisticated
techniques than those discussed in the above papers.  It is now possible for
the rules appearing in arguments of {\tt LET} to have the form
\begin{verbatim}
        <substitution expression> = <expression>
\end{verbatim}
where any rule to which a sensible meaning can be assigned is permitted.
However, this meaning can vary according to the form of {\tt <substitution
expression>}. The semantic rules associated with the application of the
substitution are completely consistent, but somewhat complicated by the
pragmatic need to perform such substitutions as efficiently as possible.
The following rules explain how the majority of the cases are handled.

To begin with, the {\tt <substitution expression>} is first partly
simplified by collecting like terms and putting identifiers (and kernels)
in the system order.  However, no substitutions are performed on any part
of the expression with the exception of expressions with the {\em instant
evaluation\/} property, such as array and matrix elements, whose actual
values are used.  It should also be noted that the system order used is
not changeable by the user, even with the {\tt KORDER} command.  Specific
cases are then handled as follows:
\begin{enumerate}
\item If the resulting simplified rule has a left-hand side that is an
identifier, an expression with a top-level algebraic operator or a power,
then the rule is added without further change to the appropriate table.

\item If the operator * appears at the top level of the simplified left-hand
side, then any constant arguments in that expression are moved to the
right-hand side of the rule.  The remaining left-hand side is then added
to the appropriate table.  For example,
\begin{verbatim}
        let 2*x*y=3
\end{verbatim}
becomes
\begin{verbatim}
        let x*y=3/2
\end{verbatim}
so that {\tt x*y} is added to the product substitution table, and when
this rule is applied, the expression {\tt x*y} becomes 3/2, but {\tt X} or
{\tt Y} by themselves are not replaced.

\item If the operators {\tt +}, {\tt -} or {\tt /} appear at the top level
of the simplified left-hand side, all but the first term is moved to the
right-hand side of the rule.  Thus the rules
\begin{verbatim}
        let l+m=n, x/2=y, a-b=c
\end{verbatim}
become
\begin{verbatim}
        let l=n-m, x=2*y, a=c+b.
\end{verbatim}
\end{enumerate}
One problem that can occur in this case is that if a quantified expression
is moved to the right-hand side, a given free variable might no longer
appear on the left-hand side, resulting in an error because of the
unmatched free variable. E.g.,
\begin{verbatim}
        for all x,y let f(x)+f(y)=x*y
\end{verbatim}
would become
\begin{verbatim}
        for all x,y let f(x)=x*y-f(y)
\end{verbatim}
which no longer has {\tt Y} on both sides.

The fact that array and matrix elements are evaluated in the left-hand side
of rules can lead to confusion at times. Consider for example the
statements
\begin{verbatim}
        array a(5); let x+a(2)=3; let a(3)=4;
\end{verbatim}
The left-hand side of the first rule will become {\tt X}, and the second
0.  Thus the first rule will be instantiated as a substitution for
{\tt X}, and the second will result in an error.

The order in which a list of rules is applied is not easily understandable
without a detailed knowledge of the system simplification protocol. It is
also possible for this order to change from release to release, as improved
substitution techniques are implemented. Users should therefore assume
that the order of application of rules is arbitrary, and program
accordingly.

After a substitution has been made, the expression being evaluated is
reexamined in case a new allowed substitution has been generated. This
process is continued until no more substitutions can be made.

As mentioned elsewhere, when a substitution expression appears in a
product, the substitution is made if that expression divides the product.
For example, the rule
\begin{verbatim}
        let a^2*c = 3*z;
\end{verbatim}
would cause {\tt a\verb|^|2*c*x} to be replaced by {\tt 3*Z*X} and
{\tt a\verb|^|2*c\verb|^|2} by {\tt 3*Z*C}.  If the substitution is desired only
when the substitution expression appears in a product with the explicit
powers supplied in the rule, the command {\tt MATCH} should be used
instead.\ttindex{MATCH}

For example,
\begin{verbatim}
        match a^2*c = 3*z;
\end{verbatim}
would cause {\tt a\verb|^|2*c*x} to be replaced by {\tt 3*Z*X}, but
{\tt a\verb|^|2*c\verb|^|2} would not be replaced. {\tt MATCH} can also be used
with the {\tt FOR ALL} constructions described above.

To remove substitution rules of the type discussed in this section, the
{\tt CLEAR}\ttindex{CLEAR} command can be used, combined, if necessary,
with the same {\tt FOR ALL} clause with which the rule was defined, for
example:
\begin{verbatim}
        for all x clear log(e^x),e^log(x),cos(w*t+theta(x));
\end{verbatim}
Note, however, that the arbitrary variable names in this case {\em must\/}
be the same as those used in defining the substitution.

\section{Rule Lists} \index{Rule lists}

Rule lists offer an alternative approach to defining substitutions that is
different from either {\tt SUB} or {\tt LET}.  In fact, they provide the
best features of both, since they have all the capabilities of {\tt LET},
but the rules can also be applied locally as is possible with {\tt SUB}.
In time, they will be used more and more in {\REDUCE}.  However, since they
are relatively new, much of the {\REDUCE} code you see uses the older
constructs.

A rule list is a list of {\em rules\/} that have the syntax
\begin{verbatim}
     <expression> => <expression> (WHEN <boolean expression>)
\end{verbatim}
For example,
\begin{verbatim}
        {cos(~x)*cos(~y) => (cos(x+y)+cos(x-y))/2,
         cos(~n*pi)      => (-1)^n when remainder(n,2)=0}
\end{verbatim}

The tilde preceding a variable marks that variable as {\em free\/} for that
rule, much as a variable in a {\tt FOR ALL} clause in a {\tt LET}
statement.  The first occurrence of that variable in each relevant rule
must be so marked on input, otherwise inconsistent results can occur.
For example, the rule list
\begin{verbatim}
        {cos(~x)*cos(~y) => (cos(x+y)+cos(x-y))/2,
         cos(x)^2        => (1+cos(2x))/2}
\end{verbatim}
designed to replace products of cosines, would not be correct, since the
second rule would only apply to the explicit argument {\tt X}.  Later
occurrences in the same rule may also be marked, but this is optional
(internally, all such rules are stored with each relevant variable
explicitly marked).  The optional {\tt WHEN}\ttindex{WHEN} clause allows
constraints to be placed on the application of the rule, much as the {\tt
SUCH THAT} clause in a {\tt LET} statement.

A rule list may be named, for example
\begin{verbatim}
        trig1 := {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,
                  cos(~x)^2       => (1+cos(2*x))/2,
                  sin(~x)^2       => (1-cos(2*x))/2};
\end{verbatim}

Such named rule lists may be inspected as needed. E.g., the command
{\tt trig1;} would cause the above list to be printed.

Rule lists may be used in two ways.  They can be globally instantiated by
means of the command {\tt LET}.\ttindex{LET} For example,
\begin{verbatim}
        let trig1;
\end{verbatim}
would cause the above list of rules to be globally active from then on until
cancelled by the command {\tt CLEARRULES},\ttindex{CLEARRULES} as in
\begin{verbatim}
        clearrules trig1;
\end{verbatim}
{\tt CLEARRULES} has the syntax
\begin{verbatim}
        CLEARRULES <rule list>|<name of rule list>(,...) .
\end{verbatim}

The second way to use rule lists is to invoke them locally by means of a
{\tt WHERE}\ttindex{WHERE} clause.  For example
\begin{verbatim}
        cos(a)*cos(b+c)
           where {cos(~x)*cos(~y) => (cos(x+y)+cos(x-y))/2};
\end{verbatim}
or
\begin{verbatim}
        cos(a)*sin(b) where trigrules;
\end{verbatim}

The syntax of an expression with a {\tt WHERE} clause is:
\begin{verbatim}
        <expression>
            WHERE <rule>|<rule list>(,<rule>|<rule list> ...)
\end{verbatim}
so the first example above could also be written
\begin{verbatim}
        cos(a)*cos(b+c)
           where cos(~x)*cos(~y) => (cos(x+y)+cos(x-y))/2;
\end{verbatim}

The effect of this construct is that the rule list(s) in the {\tt WHERE}
clause only apply to the expression on the left of {\tt WHERE}.  They have
no effect outside the expression.  In particular, they do not affect
previously defined {\tt WHERE} clauses or {\tt LET} statements.  For
example, the sequence
\begin{verbatim}
     let a=2;
     a where a=>4;
     a;
\end{verbatim}
would result in the output
\begin{verbatim}
     4

     2
\end{verbatim}

Although {\tt WHERE} has a precedence less than any other infix operator,
it still binds higher than keywords such as {\tt ELSE}, {\tt THEN},
{\tt DO}, {\tt REPEAT} and so on.  Thus the expression
\begin{verbatim}
        if a=2 then 3 else a+2 where a=3
\end{verbatim}
will parse as
\begin{verbatim}
        if a=2 then 3 else (a+2 where a=3)
\end{verbatim}

{\tt WHERE} may be used to introduce auxiliary variables in symbolic mode
expressions, as described in Section~\ref{sec-lambda}.  However, the
symbolic mode use has different semantics, so expressions do not carry
from one mode to the other.

\COMPATNOTE In order to provide compatibility with older versions of rule
lists released through the Network Library, it is currently possible to use
an equal sign interchangeably with the replacement sign {\tt =>} in rules
and {\tt LET} statements.  However, since this will change in future
versions, the replacement sign is preferable in rules and the equal sign
in non-rule-based {\tt LET} statements.

\subsection*{Advanced Use of Rule Lists}

Some advanced features of the rule list mechanism make it possible to
write more complicated rules than those discussed so far, and in many
cases to write more compact rule lists.  These features are:

\begin{itemize}
\item Free operators
\item Double slash operator
\item Double tilde variables.
\end{itemize}
A {\bf free operator} in the left hand side of a pattern will match any
operator with the same number of arguments.  The free operator is written
in the same style as a variable.  For example, the implementation of the
product rule of differentiation can be written as:
\begin{verbatim}
operator diff, !~f, !~g;

prule := {diff(~f(~x) * ~g(~x),x) =>
             diff(f(x),x) * g(x) + diff(g(x),x) * f(x)};

let prule;

diff(sin(z)*cos(z),z);

         cos(z)*diff(sin(z),z) + diff(cos(z),z)*sin(z)
\end{verbatim}

The {\bf double slash operator} may be used as an alternative to a single
slash (quotient) in order to match quotients properly.  E.g., in the
example of the Gamma function above, one can use:
\begin{verbatim}
gammarule :=
   {gamma(~z)//(~c*gamma(~zz))  => gamma(z)/(c*gamma(zz-1)*zz)
                  when fixp(zz -z) and (zz -z) >0,
    gamma(~z)//gamma(~zz) => gamma(z)/(gamma(zz-1)*zz)
                  when fixp(zz -z) and (zz -z) >0};

let gammarule;

gamma(z)/gamma(z+3);

          1
----------------------
  3      2
 z  + 6*z  + 11*z + 6
\end{verbatim}
The above example suffers from the fact that two rules had to be
written in order to perform the required operation. This can be simplified
by the use of {\bf double tilde variables}. E.g. the rule list
\begin{verbatim}
 GGrule :=  {
    gamma(~z)//(~~c*gamma(~zz))  => gamma(z)/(c*gamma(zz-1)*zz)
     when fixp(zz -z) and (zz -z) >0};
\end{verbatim}
will implement the same operation in a much more compact way.
In general, double tilde variables are bound to the neutral element
with respect to the operation in which they are used.

\begin{tabular}{lll}

Pattern given & Argument used & Binding  \\
\\
\symbol{126}z + \symbol{126}\symbol{126}y  &   x   &  z=x; y=0  \\
\symbol{126}z + \symbol{126}\symbol{126}y  &   x+3 &  z=x; y=3  or  z=3; y=x \\
\\
\symbol{126}z * \symbol{126}\symbol{126}y  &   x   &  z=x; y=1\\
\symbol{126}z * \symbol{126}\symbol{126}y  &   x*3 &  z=x; y=3  or  z=3; y=x\\
\\
\symbol{126}z / \symbol{126}\symbol{126}y  &    x   &  z=x; y=1\\
\symbol{126}z / \symbol{126}\symbol{126}y  &    x/3 &  z=x; y=3  \\
\\
\end{tabular}

Remarks: A double tilde variable as the numerator of a pattern is not allowed.
Also, using double tilde variables may lead to recursion errors when the
zero case is not handled properly.
\begin{verbatim}
let f(~~a * ~x,x)  => a * f(x,x) when freeof (a,x);

f(z,z);

***** f(z,z) improperly defined in terms of itself

% BUT:

let ff(~~a * ~x,x)
       => a * ff(x,x) when freeof (a,x) and a neq 1;

ff(z,z);
                 ff(z,z)

ff(3*z,z);
                 3*ff(z,z)
\end{verbatim}

\subsection*{Displaying Rules Associated with an Operator}

The operator {\tt SHOWRULES}\ttindex{SHOWRULES} takes a single identifier
as argument, and returns in rule-list form the operator rules associated
with that argument.  For example:
\begin{verbatim}
showrules log;

{LOG(E) => 1,

 LOG(1) => 0,

      ~X
 LOG(E  ) => ~X,

                    1
 DF(LOG(~X),~X) => ----}
                    ~X
\end{verbatim}

Such rules can then be manipulated further as with any list.  For example
{\tt rhs first ws;} has the value {\tt 1}.  Note that an operator may
have other properties that cannot be displayed in such a form, such as the
fact it is an odd function, or has a definition defined as a procedure.

\subsection*{Order of Application of Rules}

If rules have overlapping domains, their order of application is
important.  In general, it is very difficult to specify this order
precisely, so that it is best to assume that the order is arbitrary.
However, if only one operator is involved, the order of application of the
rules for this operator can be determined from the following:

\begin{enumerate}
\item Rules containing at least one free variable apply before all rules
without free variables.
\item Rules activated in the most recent {\tt LET}
command are applied first.
\item {\tt LET} with several entries generate
the same order of application as a corresponding sequence of commands with
one rule or rule set each.
\item Within a rule set, the rules containing at least
one free variable are applied in their given order.
In other words, the first member of the list is applied first.
\item Consistent with the first item, any rule in a rule list that
contains no free variables is applied after all rules containing free
variables.
\end{enumerate}
{\it Example:} The following rule set enables the computation of exact
values of the Gamma function:
\begin{verbatim}
        operator gamma,gamma_error;
        gamma_rules :=
        {gamma(~x)=>sqrt(pi)/2 when x=1/2,
         gamma(~n)=>factorial(n-1) when fixp n and n>0,
         gamma(~n)=>gamma_error(n) when fixp n,
         gamma(~x)=>(x-1)*gamma(x-1) when fixp(2*x) and x>1,
         gamma(~x)=>gamma(x+1)/x when fixp(2*x)};
\end{verbatim}
Here, rule by rule, cases of known or definitely uncomputable values
are sorted out; e.g. the rule leading to the error expression
will be applied for negative integers only, since the positive
integers are caught by the preceding rule, and the
last rule will apply for negative odd multiples of $1/2$ only.
Alternatively the first rule could have been written as
\begin{verbatim}
        gamma(1/2) => sqrt(pi)/2,
\end{verbatim}
but then the case $x=1/2$ should be excluded in the {\tt WHEN} part of the
last rule explicitly because a rule without free variables cannot take
precedence over the other rules.

\section{Asymptotic Commands} \index{Asymptotic command}
\label{sec-asymp}
In expansions of polynomials involving variables that are known to be
small, it is often desirable to throw away all powers of these variables
beyond a certain point to avoid unnecessary computation.  The command {\tt
LET} may be used to do this.  For example, if only powers of {\tt X} up to
{\tt x\verb|^|7} are needed, the command
\begin{verbatim}
        let x^8 = 0;
\end{verbatim}
will cause the system to delete all powers of {\tt X} higher than 7.

{\it CAUTION:}  This particular simplification works differently from most
substitution mechanisms in {\REDUCE} in that it is applied during
polynomial manipulation rather than to the whole evaluated expression.
Thus, with the above rule in effect, {\tt x\verb|^|10/x\verb|^|5} would give the
result zero, since the numerator would simplify to zero.  Similarly
{\tt x\verb|^|20/x\verb|^|10} would give a {\tt Zero divisor} error message,
since both numerator and denominator would first simplify to zero.

The method just described is not adequate when expressions involve several
variables having different degrees of smallness. In this case, it is
necessary to supply an asymptotic weight to each variable and count up the
total weight of each product in an expanded expression before deciding
whether to keep the term or not. There are two associated commands in the
system to permit this type of asymptotic constraint. The command {\tt WEIGHT}
\ttindex{WEIGHT}
takes a list of equations of the form
\begin{verbatim}
        <kernel form> = <number>
\end{verbatim}
where {\tt <number>} must be a positive integer (not just evaluate to a
positive integer).  This command assigns the weight {\tt <number>} to the
relevant kernel form.  A check is then made in all algebraic evaluations
to see if the total weight of the term is greater than the weight level
assigned to the calculation.  If it is, the term is deleted.  To compute
the total weight of a product, the individual weights of each kernel form
are multiplied by their corresponding powers and then added.

The weight level of the system is initially set to 1. The user may change
this setting by the command\ttindex{WTLEVEL}
\begin{verbatim}
        wtlevel <number>;
\end{verbatim}
which sets {\tt <number>} as the new weight level of the system.
{\tt <number>} must evaluate to a positive integer.  WTLEVEL will also
allow NIL as an argument, in which case the current weight level is returned.
\chapter{File Handling Commands}\index{File handling}

In many applications, it is desirable to load previously prepared {\REDUCE}
files into the system, or to write output on other files. {\REDUCE} offers
four commands for this purpose, namely, {\tt IN}, {\tt OUT}, {\tt SHUT},
{\tt LOAD}, and {\tt LOAD\_PACKAGE}.  The first\ttindex{IN}\ttindex{OUT}
\ttindex{SHUT} three operators are described here; {\tt LOAD} and {\tt
LOAD\_PACKAGE} are discussed in Section~\ref{sec-load}.

\section{IN Command}\ttindex{IN}
This command takes a list of file names as argument and directs the system
to input\index{Input} each file (that should contain {\REDUCE} statements
and commands) into the system.  File names can either be an identifier or
a string.  The explicit format of these will be system dependent and, in
many cases, site dependent.  The explicit instructions for the
implementation being used should therefore be consulted for further
details. For example:
\begin{verbatim}
        in f1,"ggg.rr.s";
\end{verbatim}
will first load file {\tt F1}, then {\tt ggg.rr.s}.  When a semicolon is
used as the terminator of the IN statement, the statements in the file are
echoed on the terminal or written on the current output file.  If \$
\index{Command terminator} is used as the terminator, the input is not
shown.  Echoing of all or part of the input file can be prevented, even if
a semicolon was used, by placing an {\tt off echo;}\ttindex{ECHO} command
in the input file.

Files to be read using {\tt IN} should end with {\tt ;END;}.  Note the two
semicolons!  First of all, this is protection against obscure difficulties
the user will have if there are, by mistake, more {\tt BEGIN}s than
{\tt END}s on the file.  Secondly, it triggers some file control book-keeping
which may improve system efficiency.  If {\tt END} is omitted, an error
message {\tt "End-of-file read"} will occur.

\section{OUT Command}\ttindex{OUT}
This command takes a single file name as argument, and directs output to
that file from then on, until another {\tt OUT} changes the output file,
or {\tt SHUT} closes it.  Output can go to only one file at a time,
although many can be open.  If the file has previously been used for
output during the current job, and not {\tt SHUT},\ttindex{SHUT} the new
output is appended to the end of the file.  Any existing file is erased
before its first use for output in a job, or if it had been {\tt SHUT}
before the new {\tt OUT}.

To output on the terminal without closing the output file, the reserved
file name T (for terminal) may be used.  For example,
{\tt out ofile;} will direct output to the file {\tt OFILE} and
{\tt out t;} will direct output to the user's terminal.

The output sent to the file will be in the same form that it would have on
the terminal.  In particular {\tt x\verb|^|2} would appear on two lines, an
{\tt X} on the lower line and a 2 on the line above.  If the purpose of the
output file is to save results to be read in later, this is not an
appropriate form.  We first must turn off the {\tt NAT} switch that
specifies that output should be in standard mathematical notation.

{\it Example:} To create a file {\tt ABCD} from which it will be possible
to read -- using {\tt IN} -- the value of the expression {\tt XYZ}:
\begin{verbatim}
 off echo$      % needed if your input is from a file.
 off nat$       % output in IN-readable form. Each expression
                % printed will end with a $ .
 out abcd$      % output to new file
 linelength 72$ % for systems with fixed input line length.
 xyz:=xyz;      % will output "XYZ := " followed by the value
                % of XYZ
 write ";end"$  % standard for ending files for IN
 shut abcd$     % save ABCD, return to terminal output
 on nat$                % restore usual output form
\end{verbatim}

\section{SHUT Command}\ttindex{SHUT}
This command takes a list of names of files that have been previously
opened via an {\tt OUT} statement and closes them. Most systems require this
action by the user before he ends the {\REDUCE} job (if not sooner),
otherwise the output may be lost. If a file is shut and a further {\tt OUT}
command issued for the same file, the file is erased before the new output
is written.

If it is the current output file that is shut, output will switch to the
terminal.  Attempts to shut files that have not been opened by {\tt OUT},
or an input file, will lead to errors.

\chapter{Commands for Interactive Use}\index{Interactive use}

{\REDUCE} is designed as an interactive system, but naturally it can also
operate in a batch processing or background mode by taking its input
command by command from the relevant input stream. There is a basic
difference, however, between interactive and batch use of the system. In
the former case, whenever the system discovers an ambiguity at some point
in a calculation, such as a forgotten type assignment for instance, it asks
the user for the correct interpretation. In batch operation, it is not
practical to terminate the calculation at such points and require
resubmission of the job, so the system makes the most obvious guess of the
user's intentions and continues the calculation.

There is also a difference in the handling of errors.  In the former case,
the computation can continue since the user has the opportunity to correct
the mistake.  In batch mode, the error may lead to consequent erroneous
(and possibly time consuming) computations.  So in the default case, no
further evaluation occurs, although the remainder of the input is checked
for syntax errors.  A message {\tt "Continuing with parsing only"}
informs the user that this is happening.  On the other hand, the switch
{\tt ERRCONT},\ttindex{ERRCONT} if on, will cause the system to continue
evaluating expressions after such errors occur.

When a syntactical error occurs, the place where the system detected the
error is marked with three dollar signs (\$\$\$). In interactive mode, the
user can then use {\tt ED}\ttindex{ED} to correct the error, or retype the
command.  When a non-syntactical error occurs in interactive mode, the
command being evaluated at the time the last error occurred is saved, and
may later be reevaluated by the command {\tt RETRY}.\ttindex{RETRY}

\section{Referencing Previous Results}

It is often useful to be able to reference results of previous
computations during a {\REDUCE} session.  For this purpose, {\REDUCE}
maintains a history\index{History} of all interactive inputs and the
results of all interactive computations during a given session.  These
results are referenced by the command number that {\REDUCE} prints
automatically in interactive mode.  To use an input expression in a new
computation, one writes {\tt input(}$n${\tt )},\ttindex{INPUT} where
$n$ is the command number.  To use an output expression, one writes {\tt
WS(}$n${\tt )}.\ttindex{WS} {\tt WS} references the previous command.
E.g., if command number 1 was {\tt INT(X-1,X)}; and the result of command
number 7 was {\tt X-1}, then
\begin{verbatim}
        2*input(1)-ws(7)^2;
\end{verbatim}
would give the result {\tt -1}, whereas
\begin{verbatim}
        2*ws(1)-ws(7)^2;
\end{verbatim}
would yield the same result, but {\em without\/} a recomputation of the
integral.

The operator {\tt DISPLAY}\ttindex{DISPLAY} is available to display previous
inputs.  If its argument is a positive integer, {\it n} say, then the
previous n inputs are displayed.  If its argument is {\tt ALL} (or in fact
any non-numerical expression), then all previous inputs are displayed.

\section{Interactive Editing}
It is possible when working interactively to edit any {\REDUCE} input that
comes from the user's terminal, and also some user-defined procedure
definitions.  At the top level, one can access any previous command string
by the command {\tt ed(}$n${\tt )},\ttindex{ED} where n is the desired
command number as prompted by the system in interactive mode. {\tt ED};
(i.e. no argument) accesses the previous command.

After {\tt ED} has been called, you can now edit the displayed string using a
string editor with the following commands:

\begin{tabular}{lp{\rboxwidth}}
{\tt~~~~~  B} & move pointer to beginning \\
{\tt~~~~~  C<character>} & replace next character by
{\em character} \\
{\tt~~~~~  D} & delete next character \\
{\tt~~~~~  E} & end editing and reread text \\
{\tt~~~~~  F<character>} & move pointer to next
occurrence of {\em character} \\[1.7pt]
{\tt~~~~~  I<string><escape>} &
 insert {\em string\/} in front of pointer \\
{\tt~~~~~  K<character>} & delete all characters
 until {\em character} \\
{\tt~~~~~  P} & print string from current pointer \\
{\tt~~~~~  Q} & give up with error exit \\
{\tt~~~~~  S<string><escape>} &
 search for first occurrence of {\em string},
                             positioning pointer just before it \\
{\tt~~~~~  space} or {\tt X} & move pointer right
one character.
\end{tabular}

The above table can be displayed online by typing a question mark followed
by a carriage return to the editor. The editor prompts with an angle
bracket. Commands can be combined on a single line, and all command
sequences must be followed by a carriage return to become effective.

Thus, to change the command {\tt x := a+1;} to {\tt x := a+2}; and cause
it to be executed, the following edit command sequence could be used:
\begin{verbatim}
        f1c2e<return>.
\end{verbatim}
The interactive editor may also be used to edit a user-defined procedure that
has not been compiled.  To do this, one says:
\ttindex{EDITDEF}
\begin{verbatim}
        editdef <id>;
\end{verbatim}
where {\tt <id>} is the name of the procedure.  The procedure definition
will then be displayed in editing mode, and may then be edited and
redefined on exiting from the editor.

Some versions of {\REDUCE} now include input editing that uses the
capabilities of modern window systems.  Please consult your system
dependent documentation to see if this is possible.  Such editing
techniques are usually much easier to use then {\tt ED} or {\tt EDITDEF}.

\section{Interactive File Control}
If input is coming from an external file, the system treats it as a batch
processed calculation.  If the user desires interactive
\index{Interactive use} response in this case, he can include the command
{\tt on int};\ttindex{INT} in the file.  Likewise, he can issue the
command {\tt off int}; in the main program if he does not desire continual
questioning from the system.  Regardless of the setting of {\tt INT},
input commands from a file are not kept in the system, and so cannot be
edited using {\tt ED}.  However, many implementations of {\REDUCE} provide
a link to an external system editor that can be used for such editing.
The specific instructions for the particular implementation should be
consulted for information on this.

Two commands are available in {\REDUCE} for interactive use of files. {\tt
PAUSE};\ttindex{PAUSE} may be inserted at any point in an input file.  When
this command is encountered on input, the system prints the message {\tt
CONT?} on the user's terminal and halts.  If the user responds {\tt Y}
(for yes), the calculation continues from that point in the file.  If the
user responds {\tt N} (for no), control is returned to the terminal, and
the user can input further statements and commands.  Later on he can use
the command {\tt cont;}\ttindex{CONT} to transfer control back to the
point in the file following the last {\tt PAUSE} encountered.  A top-level
{\tt pause;}\ttindex{PAUSE} from the user's terminal has no effect.

\chapter{Matrix Calculations} \index{Matrix calculations}
A very powerful feature of {\REDUCE} is the ease with which matrix
calculations can be performed. To extend our syntax to this class of
calculations we need to add another prefix operator, {\tt MAT},
\ttindex{MAT} and a further
variable and expression type as follows:

\section{MAT Operator}\ttindex{MAT}
This prefix operator is used to represent $n\times m$ matrices. {\tt
MAT} has {\em n} arguments interpreted as rows of the matrix, each of
which is a list of {\em m} expressions representing elements in that row.
For example, the matrix
\[ \left( \begin{array}{lcr} a & b & c \\ d & e & f \end{array} \right) \]
would be written as {\tt mat((a,b,c),(d,e,f))}.

Note that the single column matrix
\[ \left( \begin{array}{c} x \\ y \end{array} \right) \]
becomes {\tt mat((x),(y))}.  The inside parentheses are required to
distinguish it from the single row matrix
\[ \left( \begin{array}{lr} x & y \end{array} \right) \]
that would be written as {\tt mat((x,y))}.

\section{Matrix Variables}

An identifier may be declared a matrix variable by the declaration {\tt
MATRIX}.\ttindex{MATRIX}
The size of the matrix may be declared explicitly in the matrix
declaration, or by default in assigning such a variable to a matrix
expression. For example,
\begin{verbatim}
        matrix x(2,1),y(3,4),z;
\end{verbatim}
declares {\tt X} to be a 2 x 1 (column) matrix, {\tt Y} to be a 3 x 4
matrix and {\tt Z} a matrix whose size is to be declared later.

Matrix declarations can appear anywhere in a program. Once a symbol is
declared to name a matrix, it can not also be used to name an array,
operator or a procedure, or used as an ordinary variable. It can however
be redeclared to be a matrix, and its size may be changed at that time.
Note however that matrices once declared are {\em global\/} in scope, and so
can then be referenced anywhere in the program.  In other words, a
declaration within a block (or a procedure) does not limit the scope of
the matrix to that block, nor does the matrix go away on exiting the block
(use {\tt CLEAR} instead for this purpose).  An element of a matrix is
referred to in the expected manner; thus {\tt x(1,1)} gives the first
element of the matrix {\tt X} defined above.  References to elements of a
matrix whose size has not yet been declared leads to an error.  All
elements of a matrix whose size is declared are initialized to 0.  As a
result, a matrix element has an {\em instant evaluation\/}\index{Instant
evaluation} property and cannot stand for itself.  If this is required,
then an operator should be used to name the matrix elements as in:
\begin{verbatim}
        matrix m; operator x;  m := mat((x(1,1),x(1,2));
\end{verbatim}

\section{Matrix Expressions}

These follow the normal rules of matrix algebra as defined by the
following syntax:\ttindex{MAT}
\begin{verbatim}
        <matrix expression> ::=
                  MAT<matrix description>|<matrix variable>|
                  <scalar expression>*<matrix expression>|
                  <matrix expression>*<matrix expression>
                  <matrix expression>+<matrix expression>|
                  <matrix expression>^<integer>|
                  <matrix expression>/<matrix expression>
\end{verbatim}
Sums and products of matrix expressions must be of compatible size;
otherwise an error will result during their evaluation.  Similarly, only
square matrices may be raised to a power.  A negative power is computed as
the inverse of the matrix raised to the corresponding positive power.
{\tt a/b} is interpreted as {\tt a*b\verb|^|(-1)}.

{\it Examples:}

Assuming {\tt X} and {\tt Y} have been declared as matrices, the following
are matrix expressions
\begin{verbatim}
        y
        y^2*x-3*y^(-2)*x
        y + mat((1,a),(b,c))/2
\end{verbatim}
The computation of the quotient of two matrices normally uses a two-step
elimination method due to Bareiss.  An alternative method using Cramer's
method is also available.  This is usually less efficient than the Bareiss
method unless the matrices are large and dense, although we have no solid
statistics on this as yet.  To use Cramer's method instead, the switch
{\tt CRAMER}\ttindex{CRAMER} should be turned on.


\section{Operators with Matrix Arguments}

The operator {\tt LENGTH}\ttindex{LENGTH} applied to a matrix returns a
list of the number of rows and columns in the matrix.  Other operators
useful in matrix calculations are defined in the following subsections.
Attention is also drawn to the LINALG
\extendedmanual{(chapter~\ref{LINALG})} and NORMFORM
\extendedmanual{(chapter~\ref{NORMFORM})} packages.

\subsection{DET Operator}\ttindex{DET}
Syntax:
\begin{verbatim}
        DET(EXPRN:matrix_expression):algebraic.
\end{verbatim}

The operator {\tt DET} is used to represent the determinant of a square
matrix expression.  E.g.,
\begin{verbatim}
        det(y^2)
\end{verbatim}
is a scalar expression whose value is the determinant of the square of the
matrix {\tt Y}, and
\begin{verbatim}
        det mat((a,b,c),(d,e,f),(g,h,j));
\end{verbatim}
is a scalar expression whose value is the determinant of the matrix
\[ \left( \begin{array}{lcr} a & b & c \\ d & e & f \\ g & h & j
\end{array} \right) \]

Determinant expressions have the {\em instant evaluation\/} property.
\index{Instant evaluation}  In other words, the statement
\begin{verbatim}
        let det mat((a,b),(c,d)) = 2;
\end{verbatim}
sets the {\em value\/} of the determinant to 2, and does not set up a rule
for the determinant itself.

\subsection{MATEIGEN Operator}\ttindex{MATEIGEN}
Syntax:
\begin{verbatim}
        MATEIGEN(EXPRN:matrix_expression,ID):list.
\end{verbatim}

{\tt MATEIGEN} calculates the eigenvalue equation and the corresponding
eigenvectors of a matrix, using the variable {\tt ID} to denote the
eigenvalue.  A square free decomposition of the characteristic polynomial
is carried out.  The result is a list of lists of 3 elements, where the
first element is a square free factor of the characteristic polynomial,
the second its multiplicity and the third the corresponding eigenvector
(as an {\em n} by 1 matrix).  If the square free decomposition was
successful, the product of the first elements in the lists is the minimal
polynomial.  In the case of degeneracy, several eigenvectors can exist for
the same eigenvalue, which manifests itself in the appearance of more than
one arbitrary variable in the eigenvector.  To extract the various parts
of the result use the operations defined on lists.

{\it Example:}
 The command
\begin{verbatim}
        mateigen(mat((2,-1,1),(0,1,1),(-1,1,1)),eta);
\end{verbatim}
gives the output
\begin{verbatim}
        {{ETA - 1,2,

          [ARBCOMPLEX(1)]
          [             ]
          [ARBCOMPLEX(1)]
          [             ]
          [      0      ]

          },

         {ETA - 2,1,

          [      0      ]
          [             ]
          [ARBCOMPLEX(2)]
          [             ]
          [ARBCOMPLEX(2)]

          }}
\end{verbatim}

\subsection{TP Operator}\ttindex{TP}
Syntax:
\begin{verbatim}
        TP(EXPRN:matrix_expression):matrix.
\end{verbatim}

This operator takes a single matrix argument and returns its transpose.

\subsection{Trace Operator}\ttindex{TRACE}
Syntax:
\begin{verbatim}
        TRACE(EXPRN:matrix_expression):algebraic.
\end{verbatim}
The operator {\tt TRACE} is used to represent the trace of a square matrix.

\subsection{Matrix Cofactors}\ttindex{COFACTOR}
Syntax:
\begin{verbatim}
  COFACTOR(EXPRN:matrix_expression,ROW:integer,COLUMN:integer):
           algebraic
\end{verbatim}

The operator {\tt COFACTOR} returns the cofactor of the element in row
{\tt ROW} and column {\tt COLUMN} of the matrix {\tt MATRIX}.  Errors occur
if {\tt ROW} or {\tt COLUMN} do not simplify to integer expressions or if
{\tt MATRIX} is not square.

\subsection{NULLSPACE Operator}\ttindex{NULLSPACE}
Syntax:
\begin{verbatim}
        NULLSPACE(EXPRN:matrix_expression):list
\end{verbatim}
{\tt NULLSPACE} calculates for a matrix {\tt A} a list of linear
independent vectors (a basis) whose linear combinations satisfy the
equation $A x = 0$.  The basis is provided in a form such that as many
upper components as possible are isolated.

Note that with {\tt b := nullspace a} the expression {\tt length b} is the
{\em nullity\/} of A, and that {\tt second length a - length b} calculates the
{\em rank\/} of A.  The rank of a matrix expression can also be found more
directly by the {\tt RANK} operator described below.

{\it Example:} The command
\begin{verbatim}
        nullspace mat((1,2,3,4),(5,6,7,8));
\end{verbatim}
   gives the output

\begin{verbatim}
        {
         [ 1  ]
         [    ]
         [ 0  ]
         [    ]
         [ - 3]
         [    ]
         [ 2  ]
         ,
         [ 0  ]
         [    ]
         [ 1  ]
         [    ]
         [ - 2]
         [    ]
         [ 1  ]
         }
\end{verbatim}

In addition to the {\REDUCE} matrix form, {\tt NULLSPACE} accepts as input a
matrix given as a list of lists, that is interpreted as a row matrix.  If
that form of input is chosen, the vectors in the result will be
represented by lists as well.  This additional input syntax facilitates
the use of {\tt NULLSPACE} in applications different from classical linear
algebra.

\subsection{RANK Operator}\ttindex{RANK}

Syntax:
\begin{verbatim}
        RANK(EXPRN:matrix_expression):integer
\end{verbatim}
{\tt RANK} calculates the rank of its argument, that, like {\tt NULLSPACE}
can either be a standard matrix expression, or a list of lists, that can
be interpreted either as a row matrix or a set of equations.

{\tt Example:}

\begin{verbatim}
        rank mat((a,b,c),(d,e,f));
\end{verbatim}
returns the value 2.

\section{Matrix Assignments} \index{Matrix assignment}

Matrix expressions may appear in the right-hand side of assignment
statements. If the left-hand side of the assignment, which must be a
variable, has not already been declared a matrix, it is declared by default
to the size of the right-hand side. The variable is then set to the value
of the right-hand side.

Such an assignment may be used very conveniently to find the solution of a
set of linear equations. For example, to find the solution of the
following set of equations
\begin{verbatim}
        a11*x(1) + a12*x(2) = y1
        a21*x(1) + a22*x(2) = y2
\end{verbatim}
we simply write
\begin{verbatim}
        x := 1/mat((a11,a12),(a21,a22))*mat((y1),(y2));
\end{verbatim}

\section{Evaluating Matrix Elements}

Once an element of a matrix has been assigned, it may be referred to in
standard array element notation.  Thus {\tt y(2,1)} refers to the element
in the second row and first column of the matrix {\tt Y}.

\chapter{Procedures}\ttindex{PROCEDURE}

It is often useful to name a statement for repeated use in calculations
with varying parameters, or to define a complete evaluation procedure for
an operator. {\REDUCE} offers a procedural declaration for this purpose. Its
general syntax is:
\begin{verbatim}
  [<procedural type>] PROCEDURE <name>[<varlist>];<statement>;
\end{verbatim}
where
\begin{verbatim}
        <varlist> ::= (<variable>,...,<variable>)
\end{verbatim}
This will be explained more fully in the following sections.

In the algebraic mode of {\REDUCE} the {\tt <procedure type>} can be
omitted, since the default is {\tt ALGEBRAIC}.  Procedures of type {\tt
INTEGER} or {\tt REAL} may also be used.  In the former case, the system
checks that the value of the procedure is an integer.  At present, such
checking is not done for a real procedure, although this will change in
the future when a more complete type checking mechanism is installed.
Users should therefore only use these types when appropriate.  An empty
variable list may also be omitted.

All user-defined procedures are automatically declared to be operators.

In order to allow users relatively easy access to the whole {\REDUCE} source
program, system procedures are not protected against user redefinition. If
a procedure is redefined, a message
\begin{verbatim}
        *** <procedure name> REDEFINED
\end{verbatim}
is printed. If this occurs, and the user is not redefining his own
procedure, he is well advised to rename it, and possibly start over
(because he has {\em already\/} redefined some internal procedure whose correct
functioning may be required for his job!)

All required procedures should be defined at the top level, since they
have global scope throughout a program. In particular, an attempt to
define a procedure within a procedure will cause an error to occur.

\section{Procedure Heading}\index{Procedure heading}

Each procedure has a heading consisting of the word {\tt PROCEDURE}
(optionally preceded by the word {\tt ALGEBRAIC}), followed by the name of
the procedure to be defined, and followed by its formal parameters -- the
symbols that will be used in the body of the definition to illustrate
what is to be done.  There are three cases:
\begin{enumerate}
\item No parameters. Simply follow the procedure name with a terminator
(semicolon or dollar sign).
\begin{verbatim}
        procedure abc;
\end{verbatim}

When such a procedure is used in an expression or command, {\tt abc()}, with
empty parentheses, must be written.

\item One parameter.  Enclose it in parentheses {\em or\/} just leave at
least one space, then follow with a terminator.
\begin{verbatim}
        procedure abc(x);
\end{verbatim}
or
\begin{verbatim}
        procedure abc x;
\end{verbatim}

\item More than one parameter. Enclose them in parentheses, separated by
commas, then follow with a terminator.
\begin{verbatim}
        procedure abc(x,y,z);
\end{verbatim}
\end{enumerate}
Referring to the last example, if later in some expression being evaluated
the symbols {\tt abc(u,p*q,123)} appear, the operations of the procedure
body will be carried out as if {\tt X} had the same value as {\tt U} does,
{\tt Y} the same value as {\tt p*q} does, and {\tt Z} the value 123.  The
values of {\tt X}, {\tt Y}, {\tt Z}, after the procedure body operations
are completed are unchanged.  So, normally, are the values of {\tt U},
{\tt P}, {\tt Q}, and (of course) 123. (This is technically referred to as
call by value.)\index{Call by value}

The reader will have noted the word {\em normally\/} a few lines earlier. The
call by value protections can be bypassed if necessary, as described
elsewhere.

\section{Procedure Body}\index{Procedure body}

Following the delimiter that ends the procedure heading must be a {\em
single} statement defining the action to be performed or the value to be
delivered.  A terminator must follow the statement.  If it is a semicolon,
the name of the procedure just defined is printed.  It is not printed if a
dollar sign is used.

If the result wanted is given by a formula of some kind, the body is just
that formula, using the variables in the procedure heading.

{\it Simple Example:}

If {\tt f(x)} is to mean {\tt (x+5)*(x+6)/(x+7)}, the entire procedure
definition could read
\begin{verbatim}
        procedure f x; (x+5)*(x+6)/(x+7);
\end{verbatim}
Then {\tt f(10)} would evaluate to 240/17, {\tt f(a-6)} to
{\tt A*(A-1)/(A+1)}, and so on.

{\it More Complicated Example:}

Suppose we need a function {\tt p(n,x)} that, for any positive integer
{\tt N}, is the Legendre polynomial\index{Legendre polynomials} of order
{\em n}. We can define this operator using the
textbook formula defining these functions:
\begin{displaymath}
p_n(x) = \displaystyle{1\over{n!}}\
\displaystyle{d^n\over dy^n}\ \displaystyle{{1\over{(y^2 - 2xy + 1)
^{{1\over2}}}}}\Bigg\vert_{y=0}
\end{displaymath}
Put into words, the Legendre polynomial $p_n(x)$ is the result of
substituting $y=0$ in the $n^{th}$ partial derivative with respect to $y$
of a certain fraction involving $x$ and $y$, then dividing that by $n!$.

This verbal formula can easily be written in {\REDUCE}:
\begin{verbatim}
        procedure p(n,x);
           sub(y=0,df(1/(y^2-2*x*y+1)^(1/2),y,n))
               /(for i:=1:n product i);
\end{verbatim}
Having input this definition, the expression evaluation
\begin{verbatim}
        2p(2,w);
\end{verbatim}
would result in the output
\begin{verbatim}
           2
        3*W  - 1 .
\end{verbatim}
If the desired process is best described as a series of steps, then a group
or compound statement can be used.
\extendedmanual{\newpage}
{\it Example:}

The above Legendre polynomial example can be rewritten as a series of steps
instead of a single formula as follows:
\begin{verbatim}
        procedure p(n,x);
          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}
Procedures may also be defined recursively.  In other words, the procedure
body\index{Procedure body} can include references to the procedure name
itself, or to other procedures that themselves reference the given
procedure.  As an example, we can define the Legendre polynomial through
its standard recurrence relation:
\begin{verbatim}
        procedure p(n,x);
           if n<0 then rederr "Invalid argument to P(N,X)"
            else if n=0 then 1
            else if n=1 then x
            else ((2*n-1)*x*p(n-1,x)-(n-1)*p(n-2,x))/n;
\end{verbatim}

The operator {\tt REDERR}\ttindex{REDERR} in the above example provides
for a simple error exit from an algebraic procedure (and also a block).
It can take a string as argument.

It should be noted however that all the above definitions of {\tt p(n,x)} are
quite inefficient if extensive use is to be made of such polynomials, since
each call effectively recomputes all lower order polynomials. It would be
better to store these expressions in an array, and then use say the
recurrence relation to compute only those polynomials that have not already
been derived. We leave it as an exercise for the reader to write such a
definition.


\section{Using LET Inside Procedures}

By using {\tt LET}\ttindex{LET} instead of an assignment in the procedure
body\index{Procedure body} it is possible to bypass the call-by-value
\index{Call by value} protection.  If {\tt X} is a formal parameter or local
variable of the procedure (i.e. is in the heading or in a local
declaration), and {\tt LET} is used instead of {\tt :=} to make an
assignment to {\tt X}, e.g.

\begin{verbatim}
        let x = 123;
\end{verbatim}
then it is the variable that is the value of {\tt X} that is changed.
This effect also occurs with local variables defined in a block.  If the
value of {\tt X} is not a variable, but a more general expression, then it
is that expression that is used on the left-hand side of the {\tt LET}
statement.  For example, if {\tt X} had the value {\tt p*q}, it is as if
{\tt let p*q = 123} had been executed.

\section{LET Rules as Procedures}

The {\tt LET}\ttindex{LET} statement offers an alternative syntax and
semantics for procedure definition.

In place of
\begin{verbatim}
        procedure abc(x,y,z); <procedure body>;
\end{verbatim}
one can write
\begin{verbatim}
        for all x,y,z let abc(x,y,z) = <procedure body>;
\end{verbatim}
There are several differences to note.

If the procedure body contains an assignment to one of the formal
parameters, e.g.
\begin{verbatim}
        x := 123;
\end{verbatim}
in the {\tt PROCEDURE} case it is a variable holding a copy of the first
actual argument that is changed.  The actual argument is not changed.

In the {\tt LET} case, the actual argument is changed.  Thus, if {\tt ABC}
is defined using {\tt LET}, and {\tt abc(u,v,w)} is evaluated, the value
of {\tt U} changes to 123.  That is, the {\tt LET} form of definition
allows the user to bypass the protections that are enforced by the call
by value conventions of standard {\tt PROCEDURE} definitions.

{\it Example:}  We take our earlier {\tt FACTORIAL}\ttindex{FACTORIAL}
procedure and write it as a {\tt LET} statement.
\begin{verbatim}
        for all n let factorial n =
                    begin scalar m,s;
                    m:=1; s:=n;
                l1: if s=0 then return m;
                    m:=m*s;
                    s:=s-1;
                    go to l1
                end;
\end{verbatim}
The reader will notice that we introduced a new local variable, {\tt S},
and set it equal to {\tt N}.  The original form of the procedure contained
the statement {\tt n:=n-1;}.  If the user asked for the value of {\tt
factorial(5)} then {\tt N} would correspond to, not just have the value
of, 5, and {\REDUCE} would object to trying to execute the statement
5 := $5-1$.

If {\tt PQR} is a procedure with no parameters,
\begin{verbatim}
        procedure pqr;
           <procedure body>;
\end{verbatim}
it can be written as a {\tt LET} statement quite simply:
\begin{verbatim}
        let pqr = <procedure body>;
\end{verbatim}
To call {\em procedure\/} {\tt PQR}, if defined in the latter form, the empty
parentheses would not be used: use {\tt PQR} not {\tt PQR()} where a call
on the procedure is needed.

The two notations for a procedure with no arguments can be combined. {\tt PQR}
can be defined in the standard {\tt PROCEDURE} form. Then a {\tt LET}
statement
\begin{verbatim}
        let pqr = pqr();
\end{verbatim}
would allow a user to use {\tt PQR} instead of {\tt PQR()} in calling the
procedure.

A feature available with {\tt LET}-defined procedures and not with procedures
defined in the standard way is the possibility of defining partial
functions.\index{Function}
\begin{verbatim}
    for all x such that numberp x let uvw(x)=<procedure body>;
\end{verbatim}
Now {\tt UVW} of an integer would be calculated as prescribed by the procedure
body, while {\tt UVW} of a general argument, such as {\tt Z} or {\tt p+q}
(assuming these evaluate to themselves) would simply stay {\tt uvw(z)}
or {\tt uvw(p+q)} as the case may be.

\section{REMEMBER Statement}\ttindex{REMEMBER}

Setting the remember option for an algebraic procedure by
\begin{verbatim}
     REMEMBER (PROCNAME:procedure);
\end{verbatim}
saves all intermediate results of such procedure evaluations, including
recursive calls.  Subsequent calls to the procedure can then be determined
from the saved results, and thus the number of evaluations (or the
complexity) can be reduced.  This mode of evalation costs extra memory, of
course.  In addition, the procedure must be free of side--effects.

The following examples show the effect of the remember statement
on two well--known examples.

\begin{samepage}
\begin{verbatim}
procedure H(n);      % Hofstadter's function
 if numberp n then
 << cnn := cnn +1;   % counts the calls
 if n < 3 then 1 else H(n-H(n-1))+H(n-H(n-2))>>;

remember h;

> << cnn := 0; H(100); cnn>>;

100

% H has been called 100 times only.

procedure A(m,n);    % Ackermann function

 if m=0 then n+1 else
  if n=0 then A(m-1,1) else
  A(m-1,A(m,n-1));

remember a;

A(3,3);

\end{verbatim}
\end{samepage}

\chapter{Symbolic Mode}\index{Symbolic mode}

At the system level, {\REDUCE} is based on a version of the programming
language Lisp\index{Lisp} known as {\em Standard Lisp\/} which is described
in J. Marti, Hearn, A. C., Griss, M. L. and Griss, C., ``Standard LISP
Report" SIGPLAN Notices, ACM, New York, 14, No 10 (1979) 48-68.  We shall
assume in this section that the reader is familiar with the material in
that paper.  This also assumes implicitly that the reader has a reasonable
knowledge about Lisp in general, say at the level of the LISP 1.5
Programmer's Manual (McCarthy, J., Abrahams, P. W., Edwards, D. J., Hart,
T. P. and Levin, M. I., ``LISP 1.5 Programmer's Manual'', M.I.T.  Press,
1965) or any of the books mentioned at the end of this section.  Persons
unfamiliar with this material will have some difficulty understanding this
section.

Although {\REDUCE} is designed primarily for algebraic calculations, its
source language is general enough to allow for a full range of Lisp-like
symbolic calculations.  To achieve this generality, however, it is
necessary to provide the user with two modes of evaluation, namely an
algebraic mode\index{Algebraic mode} and a symbolic mode.\index{Symbolic
mode} To enter symbolic mode, the user types {\tt symbolic;}
\ttindex{SYMBOLIC} (or {\tt lisp;})\ttindex{LISP} and to return to
algebraic mode one types {\tt algebraic;}.\ttindex{ALGEBRAIC}
Evaluations proceed differently in each mode so the user is advised to
check what mode he is in if a puzzling error arises.  He can find his mode
by typing\ttindex{EVAL\_MODE}

\begin{verbatim}
        eval_mode;
\end{verbatim}
The current mode will then be printed as {\tt ALGEBRAIC} or {\tt SYMBOLIC}.

Expression evaluation may proceed in either mode at any level of a
calculation, provided the results are passed from mode to mode in a
compatible manner. One simply prefixes the relevant expression by the
appropriate mode. If the mode name prefixes an expression at the top
level, it will then be handled as if the global system mode had been
changed for the scope of that particular calculation.

For example, if the current mode is {\tt ALGEBRAIC}, then the commands
\extendedmanual{\newpage}
\begin{verbatim}
        symbolic car '(a);
        x+y;
\end{verbatim}
will cause the first expression to be evaluated and printed in symbolic
mode and the second in algebraic mode. Only the second evaluation will
thus affect the expression workspace. On the other hand, the statement
\begin{verbatim}
        x + symbolic car '(12);
\end{verbatim}
will result in the algebraic value {\tt X+12}.

The use of {\tt SYMBOLIC} (and equivalently {\tt ALGEBRAIC}) in this
manner is the same as any operator.  That means that parentheses could be
omitted in the above examples since the meaning is obvious.  In other
cases, parentheses must be used, as in

\begin{verbatim}
        symbolic(x := 'a);
\end{verbatim}
Omitting the parentheses, as in
\begin{verbatim}
        symbolic x := a;
\end{verbatim}
would be wrong, since it would parse as
\begin{verbatim}
        symbolic(x) := a;
\end{verbatim}
For convenience, it is assumed that any operator whose {\em first\/} argument is
quoted is being evaluated in symbolic mode, regardless of the mode in
effect at that time. Thus, the first example above could be equally well
written:
\begin{verbatim}
        car '(a);
\end{verbatim}
Except where explicit limitations have been made, most {\REDUCE} algebraic
constructions carry over into symbolic mode.\index{Symbolic mode}
However, there are some differences.  First, expression evaluation now
becomes Lisp evaluation.  Secondly, assignment statements are handled
differently, as we shall discuss shortly.  Thirdly, local variables and array
elements are initialized to {\tt NIL} rather than {\tt 0}. (In fact, any
variables not explicitly declared {\tt INTEGER} are also initialized to
{\tt NIL} in algebraic mode, but the algebraic evaluator recognizes {\tt
NIL} as {\tt 0}.) Finally, function definitions follow the conventions of
Standard Lisp.

To begin with, we mention a few extensions to our basic syntax which are
designed primarily if not exclusively for symbolic mode.

\section{Symbolic Infix Operators}

There are three binary infix operators in {\REDUCE} intended for use in
symbolic mode, namely . {\tt (CONS), EQ and MEMQ}. The precedence of
these operators was given in another section.

\section{Symbolic Expressions}

These consist of scalar variables and operators and follow the normal
rules of the Lisp meta language.

{\it Examples:}
\begin{verbatim}
        x
        car u . reverse v
        simp (u+v^2)
\end{verbatim}

\section{Quoted Expressions}\ttindex{QUOTE}

Because symbolic evaluation requires that each variable or expression has a
value, it is necessary to add to {\REDUCE} the concept of a quoted expression
by analogy with the Lisp {\tt QUOTE} function. This is provided by the single
quote mark {\tt '}.  For example,
\begin{quote}
\begin{tabbing}
{\tt '(a b c)} \= represents the Lisp S-expression \= {\tt (quote (a b
c))}\kill
{\tt 'a} \> represents the Lisp S-expression \>
{\tt (quote a)} \\
{\tt '(a b c)} \> represents the Lisp S-expression \> {\tt (quote (a b c))}
\end{tabbing}
\end{quote}
Note, however, that strings are constants and therefore evaluate to
themselves in symbolic mode. Thus, to print the string {\tt "A String"}, one
would write
\begin{verbatim}
        prin2 "A String";
\end{verbatim}
Within a quoted expression, identifier syntax rules are those of {\REDUCE}.
Thus {\tt  (A~!.~~B)} is the list consisting of the three elements {\tt A},
{\tt .}, and {\tt B}, whereas {\tt (A .  B)} is the dotted pair of {\tt A}
and {\tt B}.

\section{Lambda Expressions}\ttindex{LAMBDA}
\label{sec-lambda}

{\tt LAMBDA} expressions provide the means for constructing Lisp {\tt LAMBDA}
expressions in symbolic mode. They may not be used in algebraic mode.

Syntax:
\begin{verbatim}
        <LAMBDA expression> ::=
                LAMBDA <varlist><terminator><statement>
\end{verbatim}
 where
\begin{verbatim}
        <varlist> ::= (<variable>,...,<variable>)
\end{verbatim}
e.g.,
\begin{verbatim}
        lambda (x,y); car x . cdr y;
\end{verbatim}
is equivalent to the Lisp {\tt LAMBDA} expression
\begin{verbatim}
        (lambda (x y) (cons (car x) (cdr y)))
\end{verbatim}
The parentheses may be omitted in specifying the variable list if desired.

{\tt LAMBDA} expressions may be used in symbolic mode in place of prefix
operators, or as an argument of the reserved word {\tt FUNCTION}.

In those cases where a {\tt LAMBDA} expression is used to introduce local
variables to avoid recomputation, a {\tt WHERE} statement can also be
used.  For example, the expression
\begin{verbatim}
        (lambda (x,y); list(car x,cdr x,car y,cdr y))
            (reverse u,reverse v)
\end{verbatim}
can also be written
\begin{verbatim}
      {car x,cdr x,car y,cdr y} where x=reverse u,y=reverse v
\end{verbatim}
Where possible, {\tt WHERE} syntax is preferred to {\tt LAMBDA} syntax,
since it is more natural.

\section{Symbolic Assignment Statements}\index{Assignment}

In symbolic mode, if the left side of an assignment statement is a
variable, a {\tt SETQ} of the right-hand side to that variable occurs.  If
the left-hand side is an expression, it must be of the form of an array
element, otherwise an error will result.  For example, {\tt x:=y}
translates into {\tt (SETQ X Y)} whereas {\tt a(3) := 3} will be valid if
{\tt A} has been previously declared a single dimensioned array of at
least four elements.

\section{FOR EACH Statement}\ttindex{FOR EACH}

The {\tt FOR EACH} form of the {\tt FOR} statement, designed for iteration
down a list, is more general in symbolic mode.  Its syntax is:

\begin{verbatim}
        FOR EACH ID:identifier {IN|ON} LST:list
            {DO|COLLECT|JOIN|PRODUCT|SUM} EXPRN:S-expr
\end{verbatim}

As in algebraic mode, if the keyword {\tt IN} is used, iteration is on
each element of the list.  With {\tt ON}, iteration is on the whole list
remaining at each point in the iteration.  As a result, we have the
following equivalence between each form of {\tt FOR EACH} and the various
mapping functions in Lisp:
\begin{center}
{\tt
\begin{tabular}{|l|lr r|} \hline
& DO & COLLECT & JOIN \\ \hline
        IN &   MAPC & MAPCAR & MAPCAN \\
        ON &   MAP &  MAPLIST & MAPCON \\ \hline
\end{tabular}}
\end{center}
{\it Example:} To list each element of the list {\tt (a b c)}:
\begin{verbatim}
        for each x in '(a b c) collect list x;
\end{verbatim}

\section{Symbolic Procedures}\index{Symbolic procedure}

All the functions described in the Standard Lisp Report are available to
users in symbolic mode. Additional functions may also be defined as
symbolic procedures. For example, to define the Lisp function {\tt ASSOC},
the following could be used:
\begin{verbatim}
        symbolic procedure assoc(u,v);
           if null v then nil
            else if u = caar v then car v
            else assoc(u, cdr v);
\end{verbatim}
If the default mode were symbolic, then {\tt SYMBOLIC} could be omitted in
the above definition. {\tt MACRO}s\ttindex{MACRO} may be defined by
prefixing the keyword {\tt PROCEDURE} by the word {\tt MACRO}.
(In fact, ordinary functions may be defined with the keyword {\tt EXPR}
\ttindex{EXPR} prefixing {\tt PROCEDURE} as was used in the Standard Lisp
Report.) For example, we could define a {\tt MACRO CONSCONS} by
\begin{verbatim}
        symbolic macro procedure conscons l;
           expand(cdr l,'cons);
\end{verbatim}

Another form of macro, the {\tt SMACRO}\ttindex{SMACRO} is also available.
These are described in the Standard Lisp Report.  The Report also defines
a function type {\tt FEXPR}.\ttindex{FEXPR}
However, its use is discouraged since it is hard to implement efficiently,
and most uses can be replaced by macros.  At the present time, there are
no {\tt FEXPR}s in the core REDUCE system.

\section{Standard Lisp Equivalent of Reduce Input}

A user can obtain the Standard Lisp equivalent of his {\REDUCE} input by
turning on the switch {\tt DEFN}\ttindex{DEFN} (for definition).  The
system then prints the Lisp translation of his input but does not evaluate
it.  Normal operation is resumed when {\tt DEFN} is turned off.

\section{Communicating with Algebraic Mode}\index{Mode communication}

One of the principal motivations for a user of the algebraic facilities of
{\REDUCE} to learn about symbolic mode\index{Symbolic mode} is that it
gives one access to a wider range of techniques than is possible in
algebraic mode\index{Algebraic mode} alone.  For example, if a user
wishes to use parts of the system defined in the basic system source code,
or refine their algebraic code definitions to make them more efficient,
then it is necessary to understand the source language in fairly complete
detail.  Moreover, it is also necessary to know a little more about the
way {\REDUCE} operates internally.  Basically, {\REDUCE} considers
expressions in two forms: prefix form, which follow the normal Lisp rules
of function composition, and so-called canonical form, which uses a
completely different syntax.

Once these details are understood, the most critical problem faced by a
user is how to make expressions and procedures communicate between symbolic
and algebraic mode. The purpose of this section is to teach a user the
basic principles for this.

If one wants to evaluate an expression in algebraic mode, and then use
that expression in symbolic mode calculations, or vice versa, the easiest
way to do this is to assign a variable to that expression whose value is
easily obtainable in both modes.  To facilitate this, a declaration {\tt
SHARE}\ttindex{SHARE} is available. {\tt SHARE} takes a list of
identifiers as argument, and marks these variables as having recognizable
values in both modes.  The declaration may be used in either mode.

E.g.,
\begin{verbatim}
        share x,y;
\end{verbatim}
says that {\tt X} and {\tt Y} will receive values to be used in both modes.

If a {\tt SHARE} declaration is made for a variable with a previously
assigned algebraic value, that value is also made available in symbolic
mode.

\subsection{Passing Algebraic Mode Values to Symbolic Mode}

If one wishes to work with parts of an algebraic mode
\index{Algebraic mode} expression in symbolic mode,\index{Symbolic mode}
one simply makes an assignment\index{Assignment} of a shared variable to
the relevant expression in algebraic mode.  For example, if one wishes to
work with {\tt (a+b)\verb|^|2}, one would say, in algebraic mode:
\begin{verbatim}
        x := (a+b)^2;
\end{verbatim}
assuming that {\tt X} was declared shared as above.  If we now change to
symbolic mode and say
\begin{verbatim}
        x;
\end{verbatim}
its value will be printed as a prefix form with the syntax:
\begin{verbatim}
        (*SQ <standard quotient> T)
\end{verbatim}
This particular format reflects the fact that the algebraic mode processor
currently likes to transfer prefix forms from command to command, but
doesn't like to reconvert standard forms\index{Standard form} (which
represent polynomials) and standard quotients back to a true Lisp prefix
form for the expression (which would result in excessive computation).  So
{\tt *SQ} is used to tell the algebraic processor that it is dealing with
a prefix form which is really a standard quotient\index{Standard
quotient} and the second argument ({\tt T} or {\tt NIL}) tells it whether
it needs further processing (essentially, an {\em already simplified\/}
flag).

So to get the true standard quotient form in symbolic mode, one needs
{\tt CADR} of the variable. E.g.,
\begin{verbatim}
        z := cadr x;
\end{verbatim}
would store in {\tt Z} the standard quotient form for {\tt (a+b)\verb|^|2}.

Once you have this expression, you can now manipulate it as you wish.  To
facilitate this, a standard set of selectors\index{Selector} and
constructors\index{Constructor} are available for getting at parts of the
form.  Those presently defined are as follows:
\extendedmanual{\newpage}
\begin{center}
\vspace{10pt}
{\large  REDUCE Selectors\par}
%\end{center}
%\begin{center}
\renewcommand{\arraystretch}{1.5}
\begin{tabular}{lp{\rboxwidth}}
{\tt DENR} & denominator of standard quotient \\
%
{\tt LC} & leading coefficient of polynomial \\
%
{\tt LDEG} & leading degree of polynomial \\
%
{\tt LPOW} & leading power of polynomial \\
%
{\tt LT} & leading term of polynomial \\
%
{\tt MVAR} & main variable of polynomial \\
%
{\tt NUMR} & numerator (of standard quotient) \\
%
{\tt PDEG} & degree of a power \\
%
{\tt RED} & reductum of polynomial \\
%
{\tt TC} & coefficient of a term \\
%
{\tt TDEG} & degree of a term \\
%
{\tt TPOW} & power of a term
\end{tabular}
\end{center}

\begin{center}
\vspace{10pt}
{\large REDUCE Constructors \par}
%\end{center}
%\begin{center}
\renewcommand{\arraystretch}{1.5}
\begin{tabular}{lp{\redboxwidth}}
\verb|.+| & add a term to a polynomial \\
%
\verb|./| & divide (two polynomials to get quotient) \\
\verb|.*| & multiply power by coefficient to produce term \\
%
\verb|.^| & raise a variable to a power
\end{tabular}
\end{center}

For example, to find the numerator of the standard quotient above, one
could say:
\begin{verbatim}
        numr z;
\end{verbatim}
or to find the leading term of the numerator:
\begin{verbatim}
        lt numr z;
\end{verbatim}
Conversion between various data structures is facilitated by the use of a
set of functions defined for this purpose. Those currently implemented
include:

{\renewcommand{\arraystretch}{1.5}
\begin{tabular}{lp{\reduceboxwidth}}
{\tt !*A2F} & convert an algebraic expression to
a standard form.  If result is rational, an error results; \\
%
{\tt !*A2K} & converts an algebraic expression to
a kernel.  If this is not possible, an error results; \\
%
{\tt !*F2A} & converts a standard form to an
algebraic expression; \\
%
{\tt !*F2Q} & convert a standard form to a
standard quotient; \\
%
{\tt !*K2F} & convert a kernel to a standard form; \\
{\tt !*K2Q} & convert a kernel to a standard quotient; \\
%
{\tt !*P2F} & convert a standard power to a
standard form; \\
%
{\tt !*P2Q} & convert a standard power to a standard quotient; \\
%
{\tt !*Q2F} & convert a standard quotient to a
standard form.  If the quotient denominator is not 1, an error results; \\
%
{\tt !*Q2K} & convert a standard quotient to a
kernel.  If this is not possible, an error results; \\
%
{\tt !*T2F} & convert a standard term to a standard form \\
%
{\tt !*T2Q} & convert a standard term to a standard quotient.
\end{tabular}}

\subsection{Passing Symbolic Mode Values to Algebraic Mode}

In order to pass the value of a shared variable from symbolic mode to
algebraic mode, the only thing to do is make sure that the value in
symbolic mode is a prefix expression. E.g., one uses
{\tt (expt (plus a b) 2)} for {\tt (a+b)\verb|^|2}, or the format ({\tt *sq
<standard quotient> t}) as described above.  However, if you have
been working with parts of a standard form they will probably not be in
this form.  In that case, you can do the following:
\begin{enumerate}
\item If it is a standard quotient, call {\tt PREPSQ} on it.  This takes a
standard quotient as argument, and returns a prefix expression.
Alternatively, you can call {\tt MK!*SQ} on it, which returns a prefix
form like ({\tt *SQ <standard quotient> T)} and avoids translation of
the expression into a true prefix form.

\item If it is a standard form, call {\tt PREPF} on it.  This takes a
standard form as argument, and returns the equivalent prefix expression.
Alternatively, you can convert it to a standard quotient and then call
{\tt MK!*SQ}.

\item If it is a part of a standard form, you must usually first build up a
standard form out of it, and then go to step 2. The conversion functions
described earlier may be used for this purpose. For example,
\begin{enumerate}
\item If {\tt Z} is an expression which is a term, {\tt !*T2F Z} is a
standard form.
\item If {\tt Z} is a standard power, {\tt !*P2F Z} is a standard form.
\item If {\tt Z} is a variable, you can pass it direct to algebraic mode.
\end{enumerate}
\end{enumerate}
For example, to pass the leading term of {\tt (a+b)\verb|^|2} back to
algebraic mode, one could say:
\begin{verbatim}
        y:= mk!*sq !*t2q lt numr z;
\end{verbatim}
where {\tt Y} has been declared shared as above.  If you now go back to
algebraic mode, you can work with {\tt Y} in the usual way.


\subsection{Complete Example}

The following is the complete code for doing the above steps. The end
result will be that the square of the leading term of $(a+b)^{2}$ is
calculated.

%%\begin{tabular}{lp{\rboxwidth}}
%%{\tt share x,y;} & {\tt \% declare {\tt X} and
%%{\tt Y} as shared} \\
%%{\tt x := (a+b)\verb|^|2;} & {\tt \% store (a+b)\verb|^|2 in X} \\
%%{\tt symbolic;} & {\tt \% transfer to symbolic mode} \\
%%{\tt z := cadr x;} & {\tt \% store a true standard quotient \newline
%%                          \% in Z} \\[1.7pt]
%%{\tt lt numr z;} & {\tt \% print the leading term of the \newline
%%                        \% numerator of Z} \\
%%{\tt y := mk!*sq !*t2q lt numr z;} & {\tt \% store the
%%                       prefix form of this \newline
%%                     \% leading term in Y} \\
%%{\tt algebraic;} & {\tt \% return to algebraic mode} \\
%%{\tt y\verb|^|2;} & {\tt \% evaluate square of the leading \newline
%%\% term of (a+b)\verb|^|2}
%%\end{tabular}
\begin{verbatim}
share x,y;                   % declare X and Y as shared
x := (a+b)^2;                % store (a+b)^2 in X
symbolic;                    % transfer to symbolic mode
z := cadr x;                 % store a true standard quotient in Z
lt numr z;                   % print the leading term of the
                             % numerator of Z
y := mk!*sq !*t2q lt numr z; % store the prefix form of this
                             % leading term in Y
algebraic;                   % return to algebraic mode
y^2;                         % evaluate square of the leading term
                             % of (a+b)^2
\end{verbatim}

\subsection{Defining Procedures for Intermode Communication}

If one wishes to define a procedure in symbolic mode for use as an
operator in algebraic mode, it is necessary to declare this fact to the
system by using the declaration {\tt OPERATOR}\ttindex{OPERATOR} in
symbolic mode. Thus
\begin{verbatim}
        symbolic operator leadterm;
\end{verbatim}
would declare the procedure {\tt LEADTERM} as an algebraic operator. This
declaration {\em must\/} be made in symbolic mode as the effect in algebraic
mode is different.  The value of such a procedure must be a prefix form.

The algebraic processor will pass arguments to such procedures in prefix
form. Therefore if you want to work with the arguments as standard
quotients you must first convert them to that form by using the function
{\tt SIMP!*}. This function takes a prefix form as argument and returns the
evaluated standard quotient.

For example, if you want to define a procedure {\tt LEADTERM} which gives the
leading term of an algebraic expression, one could do this as follows:
\begin{samepage}
\begin{verbatim}
symbolic operator leadterm; % Declare LEADTERM as a symbolic
                            % mode procedure to be used in
                            % algebraic mode.

symbolic procedure leadterm u; % Define LEADTERM.
   mk!*sq !*t2q lt numr simp!* u;
\end{verbatim}
\end{samepage}
Note that this operator has a different effect than the operator {\tt LTERM}
\ttindex{LTERM}.  In the latter case, the calculation is done
with respect to the second argument of the operator.  In the example here,
we simply extract the leading term with respect to the system's choice of
main variable.

Finally, if you wish to use the algebraic evaluator on an argument in a
symbolic mode definition, the function {\tt REVAL} can be used.  The one
argument of {\tt REVAL} must be the prefix form of an expression. {\tt
REVAL} returns the evaluated expression as a true Lisp prefix form.

\section{Rlisp '88}

Rlisp '88 is a superset of the Rlisp that has been traditionally used for
the support of REDUCE.  It is fully documented in the book
Marti, J.B., ``{RLISP} '88:  An Evolutionary Approach to Program Design
and Reuse'', World Scientific, Singapore (1993).
Rlisp '88 adds to the traditional Rlisp the following facilities:
\begin{enumerate}
\item more general versions of the looping constructs {\tt for},
{\tt repeat} and {\tt while};

\item support for a backquote construct;

\item support for active comments;

\item support for vectors of the form name[index];

\item support for simple structures;

\item support for records.
\end{enumerate}

In addition, ``--'' is a letter in Rlisp '88.  In other words, {\tt A-B} is an
identifier, not the difference of the identifiers {\tt A} and {\tt B}.  If
the latter construct is required, it is necessary to put spaces around the
- character.  For compatibility between the two versions of Rlisp, we
recommend this convention be used in all symbolic mode programs.

To use Rlisp '88, type {\tt on rlisp88;}\ttindex{RLISP88}.  This switches to
symbolic mode with the Rlisp '88 syntax and extensions.  While in this
environment, it is impossible to switch to algebraic mode, or prefix
expressions by ``algebraic''.  However, symbolic mode programs written in
Rlisp '88 may be run in algebraic mode provided the rlisp88 package has been
loaded.  We also expect that many of the extensions defined in Rlisp '88
will migrate to the basic Rlisp over time.  To return to traditional Rlisp
or to switch to algebraic mode, say ``off rlisp88''.

\section{References}

There are a number of useful books which can give you further information
about LISP. Here is a selection:

 Allen, J.R., ``The Anatomy of LISP'', McGraw Hill, New York, 1978.

 McCarthy J., P.W. Abrahams, J. Edwards, T.P. Hart and
     M.I. Levin, ``LISP 1.5 Programmer's Manual'', M.I.T. Press, 1965.

 Touretzky, D.S, ``{LISP}: A Gentle Introduction to Symbolic Computation'',
 Harper \& Row, New York, 1984.

 Winston, P.H. and Horn, B.K.P., ``LISP'', Addison-Wesley, 1981.

\chapter{Calculations in High Energy Physics}

A set of {\REDUCE} commands is provided for users interested in symbolic
calculations in high energy physics. Several extensions to our basic
syntax are necessary, however, to allow for the different data structures
encountered.

\section{High Energy Physics Operators}
\label{HEPHYS}

We begin by introducing three new operators required in these calculations.

\subsection{. (Cons) Operator}\index{Dot product}
Syntax:
\begin{verbatim}
        (EXPRN1:vector_expression)
                 . (EXPRN2:vector_expression):algebraic.
\end{verbatim}
The binary {\tt .} operator, which is normally used to denote the addition
of an element to the front of a list, can also be used in algebraic mode
to denote the scalar product of two Lorentz four-vectors.  For this to
happen, the second argument must be recognizable as a vector expression
\index{High energy vector expression} at the time of
evaluation.  With this meaning, this operator is often referred to as the
{\em dot\/} operator.  In the present system, the index handling routines all
assume that Lorentz four-vectors are used, but these routines could be
rewritten to handle other cases.

Components of vectors can be represented by including representations of
unit vectors in the system.  Thus if {\tt EO} represents the unit vector
{\tt (1,0,0,0)}, {\tt (p.eo)} represents the zeroth component of the
four-vector P.  Our metric and notation follows Bjorken and Drell
``Relativistic Quantum Mechanics'' (McGraw-Hill, New York, 1965).
Similarly, an arbitrary component {\tt P} may be represented by
{\tt (p.u)}.  If contraction over components of vectors is required, then
the declaration {\tt INDEX}\ttindex{INDEX} must be used.  Thus
\begin{verbatim}
        index u;
\end{verbatim}
declares {\tt U} as an index, and the simplification of
\begin{verbatim}
        p.u * q.u
\end{verbatim}
would result in
\begin{verbatim}
        P.Q
\end{verbatim}
The metric tensor $g^{\mu \nu}$ may be represented by {\tt (u.v)}.  If
contraction over {\tt U} and {\tt V} is required, then they should be
declared as indices.

Errors occur if indices are not properly matched in expressions.

If a user later wishes to remove the index property from specific vectors,
he can do it with the declaration {\tt REMIND}.\ttindex{REMIND} Thus
{\tt remind v1...vn;} removes the index flags from the variables {\tt V1}
through {\tt Vn}.  However, these variables remain vectors in the system.

\subsection{G Operator for Gamma Matrices}\index{Dirac $\gamma$ matrix}
\ttindex{G}

Syntax:
\begin{verbatim}
        G(ID:identifier[,EXPRN:vector_expression])
                :gamma_matrix_expression.
\end{verbatim}
{\tt G} is an n-ary operator used to denote a product of $\gamma$ matrices
contracted with Lorentz four-vectors. Gamma matrices are associated with
fermion lines in a Feynman diagram. If more than one such line occurs,
then a different set of $\gamma$ matrices (operating in independent spin
spaces) is required to represent each line. To facilitate this, the first
argument of {\tt G} is a line identification identifier (not a number)
used to distinguish different lines.

Thus
\begin{verbatim}
        g(l1,p) * g(l2,q)
\end{verbatim}
denotes the product of {\tt $\gamma$.p} associated with a fermion line
identified as {\tt L1}, and {\tt $\gamma$.q} associated with another line
identified as {\tt L2} and where {\tt p} and {\tt q} are Lorentz
four-vectors.  A product of $\gamma$ matrices associated with the same
line may be written in a contracted form.

Thus
\begin{verbatim}
        g(l1,p1,p2,...,p3) = g(l1,p1)*g(l1,p2)*...*g(l1,p3) .
\end{verbatim}
The vector {\tt A} is reserved in arguments of G to denote the special
$\gamma$ matrix $\gamma^{5}$. Thus
\begin{quote}
\begin{tabbing}
\ \ \ \ \ {\tt g(l,a)}\hspace{0.2in} \= =\ \ \  $\gamma^{5}$ \hspace{0.5in}
\= associated with the line {\tt L} \\[0.1in]
\ \ \ \ \ {\tt g(l,p,a)} \> =\ \ \  $\gamma$.p $\times \gamma^{5}$ \>
associated with the line {\tt L}.
\end{tabbing}
\end{quote}
$\gamma^{\mu}$ (associated with the line {\tt L}) may be written as
{\tt g(l,u)}, with {\tt U} flagged as an index if contraction over {\tt U}
is required.

The notation of Bjorken and Drell is assumed in all operations involving
$\gamma$ matrices.

\subsection{EPS Operator}\ttindex{EPS}
Syntax:
\begin{verbatim}
         EPS(EXPRN1:vector_expression,...,EXPRN4:vector_exp)
            :vector_exp.
\end{verbatim}
The operator {\tt EPS} has four arguments, and is used only to denote the
completely antisymmetric tensor of order 4 and its contraction with Lorentz
four-vectors. Thus
\[ \epsilon_{i j k l} = \left\{ \begin{array}{cl}
                                +1 & \mbox{if $i,j,k,l$ is an even permutation
                                              of 0,1,2,3} \\
                                -1 & \mbox{if an odd permutation} \\
                                0 & \mbox{otherwise}
                              \end{array}
                      \right. \]

A contraction of the form $\epsilon_{i j \mu \nu}p_{\mu}q_{\nu}$ may be
written as {\tt eps(i,j,p,q)}, with {\tt I} and {\tt J} flagged as indices,
and so on.

\section{Vector Variables}

Apart from the line identification identifier in the {\tt G} operator, all
other arguments of the operators in this section are vectors.  Variables
used as such must be declared so by the type declaration {\tt VECTOR},
\ttindex{VECTOR} for example:
\begin{verbatim}
        vector  p1,p2;
\end{verbatim}
declares {\tt P1} and {\tt P2} to be vectors.  Variables declared as
indices or given a mass\ttindex{MASS} are automatically declared
vector by these declarations.

\section{Additional Expression Types}

Two additional expression types are necessary for high energy
calculations, namely

\subsection{Vector Expressions}\index{High energy vector expression}

These follow the normal rules of vector combination. Thus the product of a
scalar or numerical expression and a vector expression is a vector, as are
the sum and difference of vector expressions. If these rules are not
followed, error messages are printed. Furthermore, if the system finds an
undeclared variable where it expects a vector variable, it will ask the
user in interactive mode whether to make that variable a vector or not. In
batch mode, the declaration will be made automatically and the user
informed of this by a message.

{\tt Examples:}

Assuming {\tt P} and {\tt Q} have been declared vectors, the following are
vector expressions
\begin{verbatim}
        p
        2*q/3
        2*x*y*p - p.q*q/(3*q.q)
\end{verbatim}
whereas {\tt p*q} and {\tt p/q} are not.

\subsection{Dirac Expressions}

These denote those expressions which involve $\gamma$ matrices. A $\gamma$
matrix is implicitly a 4 $\times$ 4 matrix, and so the product, sum and
difference of such expressions, or the product of a scalar and Dirac
expression is again a Dirac expression.  There are no Dirac variables in
the system, so whenever a scalar variable appears in a Dirac expression
without an associated $\gamma$ matrix expression, an implicit unit 4
by 4 matrix is assumed.  For example, {\tt g(l,p) + m} denotes {\tt
g(l,p) + m*<unit 4 by 4 matrix>}.  Multiplication of Dirac
expressions, as for matrix expressions, is of course non-commutative.

\section{Trace Calculations}\index{High energy trace}

When a Dirac expression is evaluated, the system computes one quarter of
the trace of each $\gamma$ matrix product in the expansion of the expression.
One quarter of each trace is taken in order to avoid confusion between the
trace of the scalar {\tt M}, say, and {\tt M} representing {\tt M * <unit
4 by 4 matrix>}.  Contraction over indices occurring in such expressions is
also performed.  If an unmatched index is found in such an expression, an
error occurs.

The algorithms used for trace calculations are the best available at the
time this system was produced. For example, in addition to the algorithm
developed by Chisholm for contracting indices in products of traces,
{\REDUCE} uses the elegant algorithm of Kahane for contracting indices in
$\gamma$ matrix products.  These algorithms are described in Chisholm, J. S.
R., Il Nuovo Cimento X, 30, 426 (1963) and Kahane, J., Journal Math.
Phys. 9, 1732 (1968).

It is possible to prevent the trace calculation over any line identifier
by the declaration {\tt NOSPUR}.\ttindex{NOSPUR}  For example,
\begin{verbatim}
        nospur l1,l2;
\end{verbatim}
will mean that no traces are taken of $\gamma$ matrix terms involving the line
numbers {\tt L1} and {\tt L2}.  However, in some calculations involving
more than one line, a catastrophic error
\begin{verbatim}
        This NOSPUR option not implemented
\end{verbatim}
can occur (for the reason stated!) If you encounter this error, please let
us know!

A trace of a $\gamma$ matrix expression involving a line identifier which has
been declared {\tt NOSPUR} may be later taken by making the declaration
{\tt SPUR}.\ttindex{SPUR}

See also the CVIT package for an alternative
mechanism\extendedmanual{ (chapter~\ref{CVIT})}.

\section{Mass Declarations}\ttindex{MASS}

It is often necessary to put a particle ``on the mass shell'' in a
calculation.  This can, of course, be accomplished with a {\tt LET}
command such as
\begin{verbatim}
        let p.p= m^2;
\end{verbatim}
but an alternative method is provided by two commands {\tt MASS} and
{\tt MSHELL}.\ttindex{MSHELL}
{\tt MASS} takes a list of equations of the form:
\begin{verbatim}
        <vector variable> = <scalar variable>
\end{verbatim}
for example,
\begin{verbatim}
        mass p1=m, q1=mu;
\end{verbatim}
The only effect of this command is to associate the relevant scalar
variable as a mass with the corresponding vector. If we now say
\begin{verbatim}
        mshell <vector variable>,...,<vector variable>;
\end{verbatim}
and a mass has been associated with these arguments, a substitution of the
form
\begin{verbatim}
        <vector variable>.<vector variable> = <mass>^2
\end{verbatim}
is set up. An error results if the variable has no preassigned mass.

\section{Example}

We give here as an example of a simple calculation in high energy physics
the computation of the Compton scattering cross-section as given in
Bjorken and Drell Eqs. (7.72) through (7.74). We wish to compute the trace of

$$\left. \alpha^2\over2 \right. \left({k^\prime\over k}\right)^2
 \left({\gamma.p_f+m\over2m}\right)\left({\gamma.e^\prime \gamma.e
 \gamma.k_i\over2k.p_i} + {\gamma.e\gamma.e^\prime
 \gamma.k_f\over2k^\prime.p_i}\right)
 \left({\gamma.p_i+m\over2m}\right)$$
$$
 \left({\gamma.k_i\gamma.e\gamma.e^\prime\over2k.p_i} +
 {\gamma.k_f\gamma.e^\prime\gamma.e\over2k^\prime.p_i}
 \right)
$$

where $k_i$ and $k_f$ are the four-momenta of incoming and outgoing photons
(with polarization vectors $e$ and $e^\prime$ and laboratory energies
$k$ and $k^\prime$
respectively) and $p_i$, $p_f$ are incident and final electron four-momenta.

Omitting therefore an overall factor
${\alpha^2\over2m^2}\left({k^\prime\over k}\right)^2$ we need to find
one quarter of the trace of
$${
 \left( \gamma.p_f + m\right)
 \left({\gamma.e^\prime \gamma.e\gamma.k_i\over2k.p_i} +
  {\gamma.e\gamma.e^\prime \gamma.k_f\over 2k^\prime.p_i}\right) \left(
  \gamma.p_i + m\right)}$$
$${
 \left({\gamma.k_i\gamma.e\gamma.e^\prime\over 2k.p_i} +
  {\gamma.k_f\gamma.e^\prime \gamma.e\over2k^\prime.p_i}\right) }$$

A straightforward REDUCE program for this, with appropriate substitutions
(using {\tt P1} for $p_i$, {\tt PF} for $p_f$, {\tt KI}
for $k_i$ and {\tt KF} for $k_f$) is
\begin{verbatim}
 on div; % this gives output in same form as Bjorken and Drell.
 mass ki= 0, kf= 0, p1= m, pf= m; vector e,ep;
 % if e is used as a vector, it loses its scalar identity as
 %      the base of natural logarithms.
 mshell ki,kf,p1,pf;
 let p1.e= 0, p1.ep= 0, p1.pf= m^2+ki.kf, p1.ki= m*k,p1.kf=
     m*kp, pf.e= -kf.e, pf.ep= ki.ep, pf.ki= m*kp, pf.kf=
     m*k, ki.e= 0, ki.kf= m*(k-kp), kf.ep= 0, e.e= -1,
     ep.ep=-1;
 for all p let gp(p)= g(l,p)+m;
 comment this is just to save us a lot of writing;
 gp(pf)*(g(l,ep,e,ki)/(2*ki.p1) + g(l,e,ep,kf)/(2*kf.p1))
   * gp(p1)*(g(l,ki,e,ep)/(2*ki.p1) + g(l,kf,ep,e)/
     (2*kf.p1))$
 write "The Compton cxn is",ws;
\end{verbatim}

(We use {\tt P1} instead of {\tt PI} in the above to avoid confusion with
the reserved variable {\tt PI}).

This program will print the following result
\begin{verbatim}
                            (-1)        (-1)            2
 The Compton cxn is 1/2*K*KP     + 1/2*K    *KP + 2*E.EP  - 1
\end{verbatim}

\section{Extensions to More Than Four Dimensions}

In our discussion so far, we have assumed that we are working in the
normal four dimensions of QED calculations. However, in most cases, the
programs will also work in an arbitrary number of dimensions. The command
\ttindex{VECDIM}
\begin{verbatim}
        vecdim <expression>;
\end{verbatim}
sets the appropriate dimension. The dimension can be symbolic as well as
numerical. Users should note however, that the {\tt EPS} operator and the
$\gamma_{5}$ symbol ({\tt A}) are not properly defined in other than four
dimensions and will lead to an error if used.

\chapter{{\REDUCE} and Rlisp Utilities}

{\REDUCE} and its associated support language system Rlisp\index{Rlisp}
include a number of utilities which have proved useful for program
development over the years.  The following are supported in most of the
implementations of {\REDUCE} currently available.

\section{The Standard Lisp Compiler}\index{Compiler}

Many versions of {\REDUCE} include a Standard Lisp compiler that is
automatically loaded on demand.  You should check your system specific
user guide to make sure you have such a compiler.  To make the compiler
active, the switch {\tt COMP}\ttindex{COMP} should be turned on.  Any
further definitions input after this will be compiled automatically.  If
the compiler used is a derivative version of the original Griss-Hearn
compiler,
(M. L. Griss and A.
C. Hearn, ``A Portable LISP Compiler", SOFTWARE --- Practice and Experience
11 (1981) 541-605),
there are other switches that might also be
used in this regard.  However, these additional switches are not supported
in all compilers.  They are as follows:
%\ttindex{PLAP}\ttindex{PGWD}\ttindex{PWRDS}

{\renewcommand{\arraystretch}{2}
\begin{tabular}{lp{\reduceboxwidth}}
{\tt PLAP} & If ON, causes the printing of the
portable macros produced by the compiler; \\
%
{\tt PGWD} & If ON, causes the printing of the
actual assembly language instructions generated from the macros; \\
%
{\tt PWRDS} & If ON, causes a statistic
message of the form \newline
{\tt    <function> COMPILED, <words> WORDS, <words> LEFT} \newline
to be printed.  The first number is the number of words of binary
program space the compiled function took, and the second number
the number of words left unused in binary program space. \\
\end{tabular}}

\section{Fast Loading Code Generation Program}\index{Fast loading of code}
\label{sec-load}
In most versions of {\REDUCE}, it is possible to take any set of Lisp, Rlisp
or {\REDUCE} commands and build a fast loading version of them. In Rlisp or
{\REDUCE}, one does the following:
\begin{verbatim}
         faslout <filename>;
         <commands or IN statements>
         faslend;
\end{verbatim}
To load such a file, one uses the command {\tt LOAD},\ttindex{LOAD}
e.g. {\tt load foo;}
or {\tt load foo,bah;}

This process produces a fast-loading version of the original file.  In some
implementations, this means another file is created with the same name but
a different extension. For example, in PSL-based systems, the extension is
{\tt b} (for binary). In CSL-based systems, however, this process adds the
fast-loading code to a single file in which all such code is stored.
Particular functions are provided by CSL for managing this file, and
described in the CSL user documentation.

In doing this build, as with the production of a Standard Lisp form of
such statements, it is important to remember that some of the commands
must be instantiated during the building process.  For example, macros
must be expanded, and some property list operations must happen.
The {\REDUCE} sources should be consulted for further details on this.
% To facilitate this, the {\tt EVAL} and {\tt IGNORE} flags may be
% used.  Note also that there can be no {\tt LOAD} command within the input
% statements.

To avoid excessive printout, input statements should be followed by a \$
instead of the semicolon.  With {\tt LOAD} however, the input doesn't
print out regardless of which terminator is used with the command.

If you subsequently change the source files used in producing a fast
loading file, don't forget to repeat the above process in order to update
the fast loading file correspondingly.  Remember also that the text which
is read in during the creation of the fast load file, in the compiling
process described above, is {\em not\/} stored in your {\REDUCE}
environment, but only translated and output.  If you want to use the file
just created, you must then use {\tt LOAD} to load the output of the
fast-loading file generation program.

When the file to be loaded contains a complete package for a given
application, {\tt LOAD\_PACKAGE}\ttindex{LOAD\_PACKAGE} rather than
{\tt LOAD} should be used.  The syntax is the same.  However,
{\tt LOAD\_PACKAGE} does some additional bookkeeping such as recording that
this package has now been loaded, that is required for the correct
operation of the system.

\section{The Standard Lisp Cross Reference Program}\index{Cross reference}

{\tt CREF}\ttindex{CREF} is a Standard Lisp program for processing a
set of Standard LISP function definitions to produce:
\begin{enumerate}
\item A ``summary'' showing:
\begin{enumerate}
\item A list of files processed;
\item A list of ``entry points'' (functions which are not called or
are only called by themselves);
\item A list of undefined functions (functions called but not
defined in this set of functions);
\item A list of variables that were used non-locally but not
declared {\tt GLOBAL} or {\tt FLUID} before their use;
\item A list of variables that were declared {\tt GLOBAL} but not used
as {\tt FLUID}s, i.e., bound in a function;
\item A list of {\tt FLUID} variables that were not bound in a function
so that one might consider declaring them {\tt GLOBAL}s;
\item A list of all {\tt GLOBAL} variables present;
\item A list of all {\tt FLUID} variables present;
\item A list of all functions present.
\end{enumerate}
\item A ``global variable usage'' table, showing for each non-local
   variable:
\begin{enumerate}
\item Functions in which it is used as a declared {\tt FLUID} or {\tt GLOBAL};
\item Functions in which it is used but not declared;
\item Functions in which it is bound;
\item Functions in which it is changed by {\tt SETQ}.
\end{enumerate}
\item A ``function usage'' table showing for each function:
\begin{enumerate}
\item Where it is defined;
\item Functions which call this function;
\item Functions called by it;
\item Non-local variables used.
\end{enumerate}
\end{enumerate}

The program will also check that functions are called with the correct
number of arguments, and print a diagnostic message otherwise.

The output is alphabetized on the first seven characters of each function
name.

\subsection{Restrictions}

Algebraic procedures in {\REDUCE} are treated as if they were symbolic, so
that algebraic constructs will actually appear as calls to symbolic
functions, such as {\tt AEVAL}.

\subsection{Usage}

To invoke the cross reference program, the switch {\tt CREF}
\ttindex{CREF} is used. {\tt on cref} causes the cref program to load
and the cross-referencing process to begin.  After all the required
definitions are loaded, {\tt off cref} will cause the cross-reference
listing to be produced.  For example, if you wish to cross-reference all
functions in the file {\tt tst.red}, and produce the cross-reference
listing in the file {\tt tst.crf}, the following sequence can be used:
\begin{verbatim}
        out "tst.crf";
        on cref;
        in "tst.red"$
        off cref;
        shut "tst.crf";
\end{verbatim}
To process more than one file, more {\tt IN} statements may be added
before the call of {\tt off cref}, or the {\tt IN} statement changed to
include a list of files.

\subsection{Options}

Functions with the flag {\tt NOLIST} will not be examined or output.
Initially, all Standard Lisp functions are so flagged. (In fact, they are
kept on a list {\tt NOLIST!*}, so if you wish to see references to {\em
all} functions, then {\tt CREF} should be first loaded with the command {\tt
load cref}, and this variable then set to {\tt NIL}).

It should also be remembered that any macros with the property list flag
{\tt EXPAND}, or, if the switch {\tt FORCE} is on, without the property
list flag {\tt NOEXPAND}, will be expanded before the definition is seen
by the cross-reference program, so this flag can also be used to select
those macros you require expanded and those you do not.

\section{Prettyprinting Reduce Expressions}\index{Prettyprinting}

{\REDUCE} includes a module for printing {\REDUCE} syntax in a standard
format.  This module is activated by the switch {\tt PRET},
\ttindex{PRET} which is normally off.

Since the system converts algebraic input into an equivalent symbolic form,
the printing program tries to interpret this as an algebraic expression
before printing it. In most cases, this can be done successfully. However,
there will be occasional instances where results are printed in symbolic
mode form that bears little resemblance to the original input, even though
it is formally equivalent.

If you want to prettyprint a whole file, say {\tt off output,msg;}
\ttindex{MSG} and (hopefully) only clean output will result.  Unlike {\tt
DEFN},\ttindex{DEFN} input is also evaluated with {\tt PRET}
\ttindex{PRET} on.

\section{Prettyprinting Standard Lisp S-Expressions}\index{Prettyprinting}

REDUCE includes a module for printing
S-expressions in a standard format.  The Standard Lisp function for this
purpose is {\tt PRETTYPRINT}\ttindex{PRETTYPRINT} which takes a Lisp
expression and prints the formatted equivalent.

Users can also have their {\REDUCE} input printed in this form by use of
the switch {\tt DEFN}.\ttindex{DEFN} This is in fact a convenient way to
convert {\REDUCE} (or Rlisp) syntax into Lisp. {\tt off msg;} will prevent
warning messages from being printed.

NOTE: When {\tt DEFN} is on, input is not evaluated.

\chapter {Maintaining {\REDUCE}}

{\REDUCE} continues to evolve both in terms of the number of facilities
available, and the power of the individual facilities.  Corrections are
made as bugs are discovered, and awkward features simplified.  In order to
provide users with easy access to such enhancements, a {\em {\REDUCE}
network library\/} has been established from which material can be extracted
by anyone with electronic mail access to the Internet computer network.

In addition to miscellaneous documents, source and utility files, the
library includes a bibliography of papers referencing {\REDUCE} which
contains over 800 entries.  Instructions on using this library are sent to
all registered {\REDUCE} users who provide a network address.  If you
would like a more complete list of the contents of the library, send to
{\em reduce-netlib@rand.org\/} the single line message {\em send index\/} or
{\em help}. The current {\REDUCE} information
package can be obtained from the network library by including on a
separate line {\em send info-package\/} and a demonstration file by
including the line {\em send demonstration}.  If you prefer, hard copies
of the information package and the bibliography are available from the
{\REDUCE} secretary at RAND, 1700 Main Street, P.O. Box 2138, Santa
Monica, CA 90407-2138 ({\em reduce@rand.org}).  Copies of the network
library are also maintained at other addresses.  At the time of writing,
{\em reduce-netlib@can.nl\/} and {\em reduce-netlib@pi.cc.u-tokyo.ac.jp\/}
may also be used instead of {\em reduce-netlib@rand.org}.

A World Wide Web {\REDUCE} server with URL
\begin{verbatim}
        http://www.rrz.uni-koeln.de/REDUCE/
\end{verbatim}
is also supported.  In addition to general information about {\REDUCE}, this
server has pointers to the network library, the demonstration versions,
examples of {\REDUCE} programming, a set of manuals, and the {\REDUCE} online
help system.

Finally, there is a {\REDUCE} electronic forum accessible from the same
networks.  This enables {\REDUCE} users to raise questions and discuss
ideas concerning the use and development of {\REDUCE} with other users.
Additions and changes to the network library and new releases of {\REDUCE}
are also announced in this forum.  Any user with appropriate electronic
mail access is encouraged to register for membership in this forum.  To do
so, send a message requesting inclusion to \\
{\em reduce-forum-request@rand.org}.

\appendix
\chapter{Reserved Identifiers}

We list here all identifiers that are normally reserved in \REDUCE{}
including names of commands, operators and switches initially in the system.
Excluded are words that are reserved in specific implementations of the
system.

\vspace{13pt}
\begin{list}{}{\renewcommand{\makelabel}[1]{#1\hspace{\fill}}%
               \settowidth{\labelwidth}{Numerical Operators}%
               \setlength{\labelsep}{1em}%
               \settowidth{\leftmargin}{Numerical Operators\hspace*{\labelsep}}%
               \sloppy}

\item[Commands] {\tt ALGEBRAIC} {\tt ANTISYMMETRIC}
{\tt ARRAY} {\tt BYE} {\tt CLEAR} \linebreak
{\tt CLEARRULES} {\tt COMMENT} {\tt
CONT} {\tt DECOMPOSE} {\tt DEFINE} {\tt DEPEND} {\tt DISPLAY} {\tt ED}
{\tt EDITDEF} {\tt END} {\tt EVEN} {\tt FACTOR} {\tt FOR} {\tt FORALL}
{\tt FOREACH} {\tt GO} {\tt GOTO} {\tt IF} {\tt IN} {\tt INDEX} {\tt INFIX}
{\tt INPUT} {\tt INTEGER} {\tt KORDER} {\tt LET} {\tt LINEAR} {\tt LISP}
{\tt LISTARGP} {\tt LOAD} {\tt LOAD\_PACKAGE} {\tt MASS} {\tt MATCH} {\tt
MATRIX} {\tt MSHELL} {\tt NODEPEND} {\tt NONCOM} {\tt NONZERO} {\tt NOSPUR}
{\tt ODD} {\tt OFF}
{\tt ON} {\tt OPERATOR} {\tt ORDER} {\tt OUT} {\tt PAUSE} {\tt PRECEDENCE}
{\tt PRINT\_PRECISION} {\tt PROCEDURE} {\tt QUIT} {\tt REAL} {\tt REMFAC}
{\tt REMIND} {\tt RETRY} {\tt RETURN} {\tt SAVEAS} {\tt SCALAR} {\tt
SETMOD} {\tt SHARE} {\tt SHOWTIME} {\tt SHUT} {\tt SPUR} {\tt SYMBOLIC}
{\tt SYMMETRIC} {\tt VECDIM} {\tt VECTOR} {\tt WEIGHT} {\tt WRITE} {\tt
WTLEVEL}

\item[Boolean Operators] {\tt EVENP} {\tt FIXP}
{\tt FREEOF} {\tt NUMBERP} {\tt ORDP} {\tt PRIMEP}

\item[Infix Operators]
 \verb|:=| \verb|=| \verb|>=| \verb|>| \verb|<=| \verb|<| \verb|=>|
 \verb|+| \verb|*| \verb|/| \verb|^| \verb|**| \verb|.| {\tt WHERE}
{\tt SETQ} {\tt OR} {\tt AND} {\tt MEMBER} {\tt MEMQ} {\tt
EQUAL} {\tt NEQ} {\tt EQ} {\tt GEQ} {\tt GREATERP} {\tt LEQ} {\tt LESSP}
{\tt PLUS} {\tt DIFFERENCE} {\tt MINUS} {\tt TIMES} {\tt QUOTIENT} {\tt
EXPT} {\tt CONS}

\item[Numerical Operators] {\tt ABS} {\tt ACOS}
{\tt ACOSH} {\tt ACOT} {\tt ACOTH} {\tt ACSC} {\tt ACSCH} {\tt ASEC} {\tt
ASECH} {\tt ASIN} {\tt ASINH} {\tt ATAN} {\tt ATANH} {\tt ATAN2} {\tt COS}
{\tt COSH} {\tt COT} {\tt COTH} {\tt CSC} {\tt CSCH} {\tt EXP} {\tt
FACTORIAL} {\tt FIX} {\tt FLOOR} {\tt HYPOT} {\tt LN} {\tt LOG} {\tt LOGB}
{\tt LOG10} {\tt NEXTPRIME} {\tt ROUND} {\tt SEC} {\tt SECH} {\tt SIN}
{\tt SINH} {\tt SQRT} {\tt TAN} {\tt TANH}

\item[Prefix Operators] {\tt APPEND} {\tt
ARGLENGTH} {\tt CEILING} {\tt COEFF} {\tt COEFFN} {\tt COFACTOR} {\tt
CONJ} {\tt DEG} {\tt DEN} {\tt DET} {\tt DF} {\tt DILOG} {\tt EI}
{\tt EPS} {\tt ERF} {\tt FACTORIZE} {\tt FIRST} {\tt GCD} {\tt G} {\tt
IMPART} {\tt INT} {\tt INTERPOL} {\tt LCM} {\tt LCOF} {\tt LENGTH} {\tt
LHS} {\tt LINELENGTH} {\tt LTERM} {\tt MAINVAR} {\tt MAT} {\tt MATEIGEN}
{\tt MAX} {\tt MIN} {\tt MKID} {\tt NULLSPACE} {\tt NUM} {\tt PART} {\tt
PF} {\tt PRECISION} {\tt RANDOM} {\tt RANDOM\_NEW\_SEED} {\tt RANK} {\tt
REDERR} {\tt REDUCT} {\tt REMAINDER} {\tt REPART} {\tt REST} {\tt
RESULTANT} {\tt REVERSE} {\tt RHS} {\tt SECOND} {\tt SET} {\tt SHOWRULES}
{\tt SIGN} {\tt SOLVE} {\tt STRUCTR} {\tt SUB} {\tt SUM} {\tt THIRD} {\tt
TP} {\tt TRACE} {\tt VARNAME}

\item[Reserved Variables] {\tt CARD\_NO} {\tt E} {\tt EVAL\_MODE}
{\tt FORT\_WIDTH} {\tt HIGH\_POW} {\tt I} {\tt INFINITY} {\tt K!*} {\tt
LOW\_POW} {\tt NIL} {\tt PI} {\tt ROOT\_MULTIPLICITY} {\tt T}

\item[Switches] {\tt ADJPREC} {\tt ALGINT} {\tt ALLBRANCH} {\tt ALLFAC}
{\tt BFSPACE} {\tt COMBINEEXPT} {\tt COMBINELOGS}
{\tt COMP} {\tt COMPLEX} {\tt CRAMER} {\tt CREF} {\tt DEFN} {\tt DEMO}
{\tt DIV} {\tt ECHO} {\tt ERRCONT} {\tt EVALLHSEQP} {\tt EXP} {\tt
EXPANDLOGS} {\tt EZGCD} {\tt FACTOR} {\tt FORT} {\tt FULLROOTS} {\tt GCD}
{\tt IFACTOR} {\tt INT} {\tt INTSTR} {\tt LCM} {\tt LIST} {\tt LISTARGS}
{\tt MCD} {\tt MODULAR} {\tt MSG} {\tt MULTIPLICITIES} {\tt NAT} {\tt
NERO} {\tt NOSPLIT} {\tt OUTPUT} {\tt PERIOD} {\tt PRECISE} {\tt PRET}
{\tt PRI} {\tt RAT} {\tt RATARG} {\tt RATIONAL} {\tt RATIONALIZE} {\tt
RATPRI} {\tt REVPRI} {\tt RLISP88} {\tt ROUNDALL} {\tt ROUNDBF} {\tt
ROUNDED} {\tt SAVESTRUCTR} {\tt SOLVESINGULAR} {\tt TIME} {\tt TRA} {\tt
TRFAC} {\tt TRIGFORM} {\tt TRINT}

\item[Other Reserved Ids] {\tt BEGIN} {\tt DO} {\tt
EXPR} {\tt FEXPR} {\tt INPUT} {\tt LAMBDA} {\tt
LISP} {\tt MACRO} {\tt PRODUCT} {\tt REPEAT} {\tt SMACRO} {\tt
SUM} {\tt UNTIL} {\tt WHEN} {\tt WHILE} {\tt WS}

\end{list}

\printindex\end{document}