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 branch 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 input:; algebraic procedure cotan(x); 1/tan(x); COMMENT As an example of the use of this function, we have; cotan(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. 5. The function COT is already defined in REDUCE and should not be redefined. We can replace this definition with a different one:; algebraic procedure cotan(y); cos(y)/sin(y); g1 := cotan(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. (ALGEBRAIC can also be omitted, since it is the default procedure type.) 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,AJ) - SUB(N=M,S) = 0 AND S + SUB(J=N+1,AJ) - 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 non-negligible 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 possibly 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 then 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 0 causes a zero denominator error at top level but % continue anyway. sub(x=0, g1); limit(g1, x, 0); g1:= ((1-x)/log(x))^2; % Evaluation at 1 causes a zero denominator error at top level but % 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. (If you have an instructor, I also urge you to humor him by adopting his style for the duration of the course.) 8. C and Java 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 1/!*FOO in the ratio, then take the limit as the indeterminate !*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 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, namely 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 normal 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(3,3), OPERATOR A, 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 a comma-separated sequence 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 session. ;end;