COMMENT
REDUCE INTERACTIVE LESSON NUMBER 4
David R. Stoutemyer
University of Hawaii
COMMENT This is lesson 4 of 7 REDUCE lessons. As before, please
refrain from using variables beginning with the letters F through H
during the lesson.
In theory, assignments and LET statements are sufficient to
accomplish anything that any other practical computing mechanism is
capable of doing. However, it is more convenient for some purposes
to use function procedures which can employ branched selection and
iteration as do most traditional programming languages. As a trivial
example, if we invariably wanted to replace cotangents with the
corresponding tangents, we could type;
ALGEBRAIC PROCEDURE COT(X); 1/TAN(X);
COMMENT As an example of the use of this function, we have;
COT(LOG(F));
PAUSE;
COMMENT Note:
1. The procedure definition automatically declares the procedure
name as an operator.
2. A procedure can be executed any time after its definition,
until it is cleared.
3. Any parameters are dummy variables that are distinct from
any other variables with the same name outside the procedure
definition, and the corresponding arguments can be
arbitrary expressions.
4. The value returned by a procedure is the value of the
expression following the procedure statement.
We can replace this definition with a different one;
ALGEBRAIC PROCEDURE COT(Y); COS(Y)/SIN(Y);
G1:= COT(LOG(F));
COMMENT In place of the word ALGEBRAIC, we can optionally use the
word INTEGER when a function always returns an integer value, or we
can optionally use the word REAL when a function always returns a
floating-point value.
Try writing a procedure definition for the sine in terms of the
cosine, then type G1;
PAUSE;
COMMENT Here is a more complicated function which introduces the
notion of a conditional expression;
ALGEBRAIC PROCEDURE SUMCHECK(AJ, J, M, N, S);
COMMENT J is an indeterminate and the other parameters are
expressions. This function returns the global variable named
PROVED if the function can inductively verify that S equals the
sum of AJ for J going from M through N, returning the global
variable named UNPROVED otherwise. For the best chance of
proving a correct sum, the function should be executed under
the influence of ON EXP, ON MCD, and any other user-supplied
simplification rules relevant to the expression classes of AJ
and S;
IF SUB(J=M,AJ)-SUB(N=M,S) NEQ 0
OR S+SUB(J=N+1,AJ)-SUB(N=N+1,S) NEQ 0 THEN UNPROVED
ELSE PROVED;
ON EXP, MCD;
CLEAR X, J, N;
SUMCHECK(J, J, 1, N, N*(N+1)/2);
SUMCHECK(X**J, J, 0, N, (X**(N+1)-1)/(X-1));
COMMENT Within procedures of this sort a global variable is any
variable which is not one of the parameters, and a global variable
has the value, if any, which is current for that name at the point
from where the procedure is used.
;PAUSE; COMMENT
Conditional expressions have the form
IF condition THEN expression1 ELSE expression2.
There are generally several equivalent ways of writing a conditional
expression. For example, the body of the above procedure could have
been written
IF SUB(J=M,A)-SUB(N=M,S)=0 AND S+SUB(J=N+1,A)-SUB(N=N+1,S)=0
THEN PROVED
ELSE UNPROVED.
Note how we compare a difference with 0, rather than comparing
two nonzero expressions, for reasons explained in lesson 3.
As an exercise, write a procedure analogous to SUMCHECK for proving
closed-form product formulas, then test it on the valid formula that
COS(N*X) equals the product of COS(J*X)/COS(J*X-X) for J ranging from
1 through N. You do not need to include prefatory comments
describing parameters and the returned value until you learn how to
use a text editor;
PAUSE;
COMMENT Most REDUCE statements are also expressions because they have
a value. The value is usually 0 if nothing else makes sense, but I
will mention the value only if it is useful.
The value of an assignment statement is the assigned value. Thus a
multiple assignment, performed right to left, can be achieved by a
sequence of the form
"variable1 := variable2 := ... := variableN := expression",
moreover, assignments can be inserted within ordinary expressions
such as X*(Y:=5). Such assignments must usually be parenthesized
because of the low precedence of the assignment operator, and
excessive use of this construct tends to make programs confusing.
;PAUSE;COMMENT
REDUCE treats as a single expression any sequence of statements
preceded by the pair of adjacent characters << and followed by the
pair >>. The value of such a group expression is the value of the
last statement in the group.
Group expressions facilitate the implementation of tasks that are
most easily stated as a sequence of operations. However, such
sequences often utilize temporary variables to count, hold
intermediate results, etc., and it is hazardous to use global
variables for that purpose. If a top-level REDUCE statement or
another function directly or indirectly uses that variable name, then
its value or its virgin indeterminate status there might be damaged
by our use as a temporary variable. In large programs or programs
which rely on the work of others, such interference has a
nonnegligible probability, even if all programmers agree to the
convention that all such temporary variables should begin with the
function name as a prefix and all programmers attempt to comply with
the convention. For this reason, REDUCE provides another
expression-valued sequence called a BEGIN-block, which permits the
declaration of local variables that are distinct from any other
variables outside the block having the same name. Another advantage
of using local variables for temporary variables is that the perhaps
large amount of storage occupied by their values can be reclaimed
after leaving their block.
;PAUSE;COMMENT
A BEGIN-block consists of the word BEGIN, followed by optional
declarations, followed by a sequence of statements, followed by the
word END. Within BEGIN-blocks, it is often convenient to return
control and a value from someplace other than the end of the block.
Control and a value may be returned via a
RETURN-statement of the form
RETURN expression
or
RETURN,
0 being returned in the latter case. A BEGIN-block does not return
the value of the last statement. If a value is to be returned RETURN
must be used. These features and others are illustrated by the
following function;
PAUSE;
ALGEBRAIC PROCEDURE LIMIT(EX, INDET, PNT);
BEGIN COMMENT This function uses up through 4 iterations of
L'Hospital's rule to attempt determination of the limit of
expression EX as indeterminate INDET approaches expression
PNT. This function is intended for the case where
SUB(INDET=PNT, EX) yields 0/0, provoking a zero-divide
message. This function returns the global variable named
UNDEFINED when the limit is 0 dividing an expression which did
not simplify to 0, and this function returns the global
variable named UNKNOWN when it cannot determine the limit.
Otherwise this function returns an expression which is the
limit. For best results, this function should be executed
under the influence of ON EXP, ON MCD, and any user-supplied
simplification rules appropriate to the expression classes of
EX and PNT;
INTEGER ITERATION;
SCALAR N, D, NLIM, DLIM;
ITERATION := 0;
N := NUM(EX);
D := DEN(EX);
NLIM := SUB(INDET=PNT, N);
DLIM := SUB(INDET=PNT, D);
WHILE NLIM=0 AND DLIM=0 AND ITERATION<5 DO <<
N := DF(N, INDET);
D := DF(D, INDET);
NLIM := SUB(INDET=PNT, N);
DLIM := SUB(INDET=PNT, D);
ITERATION := ITERATION + 1 >>;
RETURN (IF NLIM=0 THEN
IF DLIM=0 THEN UNKNOWN
ELSE 0
ELSE IF DLIM=0 THEN UNDEFINED
ELSE NLIM/DLIM)
END;
% Examples follow..
PAUSE;
G1 := (E**X-1)/X;
% Evaluation at 1, causes Zero denominator error at top level, continue
% anyway.
SUB(X=0, G1);
LIMIT(G1, X, 0);
G1:= ((1-X)/LOG(X))**2;
% Evaluation at 1, causes Zero denominator error at top level, continue
% anyway.
SUB(X=1, G1);
LIMIT(G1, X, 1);
COMMENT Note:
1. The idea behind L'Hospital's rule is that as long as the
numerator and denominator are both zero at the limit point, we
can replace them by their derivatives without altering the
limit of the quotient.
2. Assignments within groups and BEGIN-blocks do not
automatically cause output.
3. Local variables are declared INTEGER, REAL, or SCALAR, the
latter corresponding to the same most general class denoted by
ALGEBRAIC in a procedure statement. All local variables are
initialized to zero, so they cannot serve as indeterminates.
Moreover, if we attempted to overcome this by clearing them,
we would clear all variables with their names.
4. We do not declare the attributes of parameters.
5. The NUM and DEN functions respectively extract the numerator
and denominator of their arguments. (With OFF MCD, the
denominator of 1+1/X would be 1.)
6. The WHILE-loop has the general form
WHILE condition DO statement.
REDUCE also has a "GO TO" statement, and using commas rather
than semicolons to prevent termination of this comment, the
above general form of a WHILE-loop is equivalent to
BEGIN GO TO TEST,
LOOP: statement,
TEST: IF condition THEN GO TO LOOP,
RETURN 0
END .
A GOTO statement is permitted only within a block, and the
GOTO statement cannot refer to a label outside the same block
or to a label inside a block that the GOTO statement is not
also within. Actually, 99.99% of REDUCE BEGIN-blocks are less
confusing if written entirely without GOTOs, and I mention
them primarily to explain WHILE-loops in terms of a more
primitive notion.
;PAUSE;COMMENT
7. The LIMIT function provides a good illustration of nested
conditional expressions. Proceeding sequentially through such
nests, each ELSE clause is matched with the nearest preceding
unmatched THEN clause in the group or block. In order to help
reveal their structure, I have consistently indented nested
conditional statements, continuations of multi-line statements
and loop-bodies according to one of the many staunchly
defended indentation styles. However, older versions of REDUCE
may ruin my elegant style. If you have such a version, I
encourage you to indent nonetheless, in anticipation of a
replacement for your obsolete version. (If you have an
instructor, I also urge you to humor him by adopting his style
for the duration of the course.)
8. PL/I programmers take note: "IF ... THEN ... ELSE ..." is
regarded as one expression, and semicolons are used to
separate rather than terminate statements. Moreover, BEGIN
and END are brackets rather than statements, so a semicolon is
never needed immediately after BEGIN, and a semicolon is
necessary immediately preceding END only if the END is
intended as a labeled destination for a GOTO. Within
conditional expressions, an inappropriate semicolon after an
END, a >>, or an ELSE-clause is likely to be one of your most
prevalent mistakes.;
PAUSE;
COMMENT The next exercise is based on the above LIMIT function:
For the sum of positive expressions AJ for J ranging from some finite
initial value to infinity, the infinite series converges if the limit
of the ratio SUB(J=J+1,AJ)/AJ is less than 1 as J approaches
infinity. The series diverges if this limit exceeds 1, and the test
is inconclusive if the limit is 1. To convert the problem to the
form required by the above LIMIT program, we can replace J by the
indeterminate 1/!*FOO in the ratio, then take the limit as !*FOO
approaches zero. (Since an indeterminate is necessary here, I picked
the weird name !*FOO to make the chance of conflict negligible)
After writing such a function to perform the ratio test, test it on
the examples AJ=J/2**J, AJ=1/J**2, AJ=2**J/J**10, and AJ=1/J. (The
first two converge and the second two diverge);
PAUSE;
COMMENT Groups or blocks can be used wherever any arbitrary
expression is allowed, including the right-hand side of a LET rule.
The need for loops with an integer index variable running from a
given initial value through a given final value by a given increment
is so prevalent that REDUCE offers a convenient special way of
accomplishing it via a FOR-loop, which has the general form
FOR index := initial STEP increment UNTIL final DO statement .
Except for the use of commas as statement separators, this construct
is equivalent to
BEGIN INTEGER index,
index := initial,
IF increment>0 THEN WHILE index <= final DO <<
statement,
index := index + increment >>
ELSE WHILE index >= final DO <<
statement,
index := index + increment >>,
RETURN 0
END .
;PAUSE;COMMENT
Note:
1. The index variable is automatically declared local to the FOR-
loop.
2. "initial", "increment", and "final" must have integer values.
3. FORTRAN programmers take note: the body of the loop is not
automatically executed at least once.
4. An acceptable abbreviation for "STEP 1 UNTIL" is ":".
5. Since the WHILE-loop and the FOR-loop have implied BEGIN-
blocks, a RETURN statement within their bodies cannot transfer
control further than the point following the loops.
Another frequent need is to produce output from within a group or
block, because such output is not automatically produced. This can
be done using the WRITE-statement, which has the form
WRITE expression1, expression2, ..., expressionN.
Beginning a new line with expression1, the expressions are printed
immediately adjacent to each other, split over line boundaries if
necessary. The value of the WRITE-statement is the value of its last
expression, and any of the expressions can be a character-string
of the form "character1 character2 ... characterM" .
Inserting the word "WRITE" on a separate line before an assignment
is convenient for debugging, because the word is then easily deleted
afterward. These features and others are illustrated by the following
equation solver;
PAUSE;
OPERATOR SOLVEFOR, SOLN;
FOR ALL X, LHS, RHS LET SOLVEFOR(X, LHS, RHS) = SOLVEFOR(X, LHS-RHS);
COMMENT LHS and RHS are expressions such that P=NUM(LHS-RHS) is a
polynomial of degree at most 2 in the indeterminate or functional
form X. Otherwise an error message is printed. As a convenience,
RHS can be omitted if it is 0. If P is quadratic in X, the two
values of X which satisfy P=0 are stored as the values of the
functional forms SOLN(1) and SOLN(2). If P is a first-degree
polynomial in X, SOLN(1) is set to the one solution. If P simplifies
to 0, SOLN(1) is set to the identifier ARBITRARY. If P is an
expression which does not simplify to zero but does not contain X,
SOLN(1) is set to the identifier NONE. In all other cases, SOLN(1)
is set to the identifier UNKNOWN. The function then returns the
number of SOLN forms which were set. This function prints a well
deserved warning message if the denominator of LHS-RHS contains X. If
LHS-RHS is not polynomial in X, it is wise to execute this function
under the influence of ON GCD;
PAUSE;
FOR ALL X, LHSMRHS LET SOLVEFOR(X, LHSMRHS) =
BEGIN INTEGER HIPOW; SCALAR TEMP, CFLIST, CF0, CF1, CF2;
IF LHSMRHS = 0 THEN <<
SOLN(1) := ARBITRARY;
RETURN 1 >>;
CFLIST := COEFF(LHSMRHS, X);
HIPOW := HIPOW!*;
IF HIPOW = 0 THEN <<
SOLN(1) := NONE;
RETURN 1 >>;
IF HIPOW > 2 THEN <<
SOLN(1) := UNKNOWN;
RETURN 1 >>;
IF HIPOW = 1 THEN <<
SOLN(1) := FIRST(CFLIST)/SECOND(CFLIST);
IF DF(SUB(X=!*FOO, SOLN(1)), !*FOO) NEQ 0 THEN
SOLN(1) := UNKNOWN;
RETURN 1 >>;
CF0 := FIRST(CFLIST)/THIRD(CFLIST);
CF1 := -SECOND(CFLIST)/THIRD(CFLIST)/2;
IF DF(SUB(X=!*FOO, CF0), !*FOO) NEQ 0
OR DF(SUB(X=!*FOO, CF1), !*FOO) NEQ 0 THEN <<
SOLN(1) := UNKNOWN;
RETURN 1 >>;
TEMP := (CF1**2 - CF0)**(1/2);
SOLN(1) := CF1 + TEMP;
SOLN(2) := CF1 - TEMP;
RETURN 2
END;
COMMENT And some examples;
PAUSE;
FOR K:=1:SOLVEFOR(X, A*X**2, -B*X-C) DO WRITE SOLN(K) := SOLN(K);
FOR K:=1:SOLVEFOR(LOG(X), 5*LOG(X)-7) DO WRITE SOLN(K) := SOLN(K);
FOR K:=1:SOLVEFOR(X, X, X) DO WRITE SOLN(K) := SOLN(K);
FOR K:= 1:SOLVEFOR(X, 5) DO WRITE SOLN(K) := SOLN(K);
FOR K:=1:SOLVEFOR(X, X**3+X+1) DO WRITE SOLN(K) := SOLN(K);
FOR K:=1:SOLVEFOR(X, X*E**X, 1) DO WRITE SOLN(K) := SOLN(K);
G1 := X/(E**X-1);
%Results in 'invalid as POLYNOMIAL' error, continue anyway;
FOR K:=1:SOLVEFOR(X, G1) DO WRITE SOLN(K) := SOLN(K);
SUB(X=SOLN(1), G1);
LIMIT(G1, X, SOLN(1));
PAUSE;
COMMENT Here we have used LET rules to permit the user the
convenience of omitting default arguments. (Function definitions have
to have a fixed number of parameters.)
Array elements are designated by the same syntax as matrix elements
and as functional forms having integer arguments. Here are some
desiderata that may help you decide which of these alternatives is
most appropriate for a particular application:
1. The lower bound of each array subscript is 0, vs. 1 for
matrices vs unrestricted for functional forms.
2. The upper bound of each array subscript must have a specific
integer value at the time the array is declared, as must the
upper bounds of matrix subscripts when a matrix is first
referred to, on the left side of a matrix assignment. In
contrast, functional forms never require a commitment to a
specific upper bound.
3. An array can have any fixed number of subscripts, a matrix
must have exactly 2, and a functional form can have a varying
arbitrary number.
4. Matrix operations, such as transpose and inverse, are built-in
only for matrices.
5. For most implementations, access to array elements requires
time approximately proportional to the number of subscripts,
whereas access to matrix elements takes time approximately
proportional to the sum of the two subscript values, whereas
access to functional forms takes average time approximately
proportional to the number of bound functional forms having
that name.
6. Only functional forms permit the effect of a subscripted
indeterminate such as having an answer be "A(M,N) + B(3,4)".
7. Only functional forms can be used alone in the LHS of LET
substitutions.
;PAUSE; COMMENT
8. All arrays, matrices, and operators are global regardless
of where they are declared, so declaring them within a BEGIN
block does not afford the protection and automatic storage
recovery of local variables. Moreover, clearing them within a
BEGIN-block will clear them globally, and functions
cannot return an array or a matrix value. Furthermore, REDUCE
parameters are referenced by value, which means that an
assignment to a parameter has no effect on the corresponding
argument. Thus, matrix or array results cannot be transmitted
back to an argument either.
9. It is often advantageous to use two or more of these
alternatives to represent a set of quantities at different
times in the same program. For example, to get the general
form of the inverse of a 3-by-3 matrix, we could write
MATRIX AA,
OPERATOR A,
AA := MAT((0,0,0),(0,0,0),(0,0,0)),
FOR J:=1:3 DO
FOR K:=1:3 DO AA(J,K) := A(J,K),
AA**-1 .
As another example, we might use an array to receive some
polynomial coefficients, then transfer the values to a matrix
for inversion.
;PAUSE;COMMENT
The COEFF function is the remaining new feature in our SOLVEFOR
example. The first argument is a polynomial expression in the
indeterminate or functional form which is the second argument. The
polynomial coefficients of the integer powers of the indeterminate are
returned as a LIST, with the independent coefficient first. The
highest and lowest non-zero powers are placed in the variables HIPOW!*
and LOWPOW!* respectively.
A LIST is a kind of data structure, just as matrices and arrays are.
It is represented as comma separated list of elements enclosed in
braces. The elements can be accessed with the functions FIRST,
SECOND, THIRD, PART(i) which returns the i-th element, and REST, which
returns a list of all but the first element. For example;
CLEAR X;
COEFF(X**5+2, X);
LOWPOW!*;
HIPOW!*;
PAUSE;
COMMENT COEFF does not check to make sure that the coefficients do not
contain its second argument within a functional form, so that is the
reason we differentiated. The reason we first substituted the
indeterminate !*FOO for the second argument is that differentiation
does not work with respect to a functional form.
The last exercise is to rewrite the last rule so that we can solve
equations which simplify to the form
a*x**(m+2*l) + b*x**(m+l) + c*x**m = 0, where m>=0 and l>=1.
The solutions are
0, with multiplicity m,
x1*E**(2*j*I*pi/l),
x2*E**(2*j*I*pi/l), with j = 0, 1, ..., l-1,
where x1 and x2 are the solutions to the quadratic equation
a*x**2 + b*x + c = 0 .
As a convenience to the user, you might also wish to have a global
switch named SOLVEPRINT, such that when it is nonzero, the solutions
are automatically printed.
This is the end of lesson 4. When you are ready to run lesson 5,
start a new REDUCE job.
;END;