reduce-historical/r30/less4

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));

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

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.

A BEGIN-block consists of the word BEGIN, followed by optional
declarations, followed by a sequence of statements, followed by the
word END. As a convenience, any text from the word END to the next
statement separator, >>, END, ELSE, or UNTIL is a comment. Within
BEGIN-blocks, it is often convenient to return control and a value
from someplace other than the end of the block rather than have the
value be that of the last statement. Consequently, control and a
value must be returned via a RETURN-statement or the form

         RETURN expression
or
          RETURN,

0 being returned in the latter case.


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 0, causes zero divide prompt at top level, continue
% anyway.
SUB(X=0, G1);

LIMIT(G1, X, 0);

G1:= ((1-X)/LOG(X))**2;

% Evaluation at 1, causes zero divide prompt 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.
   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 .

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;

ARRAY CF(2);

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.
   This function also uses the global array CF as temporary storage.  If
   LHS-RHS is not polynomial in X, it is wise to execute this function
   under the influence of ON GCD;

FOR ALL X, LHSMRHS LET SOLVEFOR(X, LHSMRHS) =
   BEGIN INTEGER HIPOW;  SCALAR TEMP;
   IF LHSMRHS = 0 THEN <<
      SOLN(1) := ARBITRARY;
      RETURN 1 >>;
   HIPOW := COEFF(LHSMRHS, X, CF);
   IF HIPOW = 0 THEN <<
      SOLN(1) := NONE;
      RETURN 1 >>;
   IF HIPOW > 2 THEN <<
      SOLN(1) := UNKNOWN;
      RETURN 1 >>;
   IF HIPOW = 1 THEN <<
      SOLN(1) := -CF(0)/CF(1);
      IF DF(SUB(X=!*FOO, SOLN(1)), !*FOO) NEQ 0 THEN
         SOLN(1) := UNKNOWN;
      RETURN 1 >>;
   CF(0) := CF(0)/CF(2);
   CF(1) := -CF(1)/CF(2)/2;
   IF DF(SUB(X=!*FOO, CF(0)), !*FOO) NEQ 0
         OR DF(SUB(X=!*FOO, CF(1)), !*FOO) NEQ 0  THEN <<
      SOLN(1) := UNKNOWN;
      RETURN 1 >>;
   TEMP := (CF(1)**2 - CF(0))**(1/2);
   SOLN(1) := CF(1) + TEMP;
   SOLN(2) := CF(1) - TEMP;
   RETURN 2
   END;

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);

FOR K:=1:SOLVEFOR(X, G1) DO WRITE SOLN(K) := SOLN(K);

SUB(X=SOLN(1), G1);

LIMIT(G1, X, SOLN(1));

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.  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 value-type parameters, 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.
   8.  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.

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, and
the third argument is a singly-subscripted array-name or an array
cross-section for receiving the polynomial coefficients of the
integer powers which correspond to their subscripts.  An array
cross-section is a multiply-subscripted array-reference with an
asterisk as one subscript and specific integer values as the others.
Examples are Q(5,*) which indicates the fifth row of Q, and Q(*,5)
which indicates the fifth column of Q.

Alternatively, the third argument of COEFF can be an indeterminate,
in which case nonzero coefficients are assigned to indeterminates
with names constructed by concatenating the integer power, as a
suffix, to the given indeterminate. For example;

CLEAR C,X;

COEFF(X**5+2, X, C);

PAUSE;

COMMENT This technique is usually more convenient when COEFF is used
interactively at the top level, whereas the array technique is
usually more convenient when COEFF is used indirectly within a group
or block.

COEFF returns the highest subscript or suffix for which it made an
assignment.

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
flag 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;