123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555 
 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
 floatingpoint 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 usersupplied
 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)/(X1));
 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
 closedform product formulas, then test it on the valid formula that
 COS(N*X) equals the product of COS(J*X)/COS(J*XX) 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 toplevel 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
 expressionvalued sequence called a BEGINblock, 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 BEGINblock consists of the word BEGIN, followed by optional
 declarations, followed by a sequence of statements, followed by the
 word END. Within BEGINblocks, 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
 RETURNstatement of the form
 RETURN expression
 or
 RETURN,
 0 being returned in the latter case. A BEGINblock 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 zerodivide
 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 usersupplied
 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**X1)/X;
 % Evaluation at 1, causes Zero denominator error at top level, continue
 % anyway.
 SUB(X=0, G1);
 LIMIT(G1, X, 0);
 G1:= ((1X)/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 BEGINblocks 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 WHILEloop 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 WHILEloop 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 BEGINblocks are less
 confusing if written entirely without GOTOs, and I mention
 them primarily to explain WHILEloops 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 multiline statements
 and loopbodies 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 ELSEclause 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 righthand 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 FORloop, 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 WHILEloop and the FORloop 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 WRITEstatement, 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 WRITEstatement is the value of its last
 expression, and any of the expressions can be a characterstring
 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, LHSRHS);
 COMMENT LHS and RHS are expressions such that P=NUM(LHSRHS) 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 firstdegree
 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 LHSRHS contains X. If
 LHSRHS 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*XC) 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**X1);
 %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 builtin
 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
 BEGINblock 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 3by3 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 nonzero 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 ith 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, ..., l1,
 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;
