123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467 |
- COMMENT
-
- REDUCE INTERACTIVE LESSON NUMBER 5
-
- David R. Stoutemyer
- University of Hawaii
-
-
- COMMENT This is lesson 5 of 7 REDUCE lessons.
-
- There are at least two good reasons for wanting to save REDUCE
- expression assignments on secondary storage:
- 1. So that one can logout, then resume computation at a later
- time.
- 2. So that needed storage space can be cleared without
- irrecoverably losing the values of variables which are not
- needed in the next expression but will be needed later.
-
- Using trivial small expressions, the following sequence illustrates
- how this could be done:
-
- OFF NAT,
- OUT TEMP,
- F1 := (F + G)**2,
- G1 := G*F1,
- OUT T,
- CLEAR F1,
- H1 := H*G1,
- OUT TEMP,
- CLEAR G1,
- H2 := F*H1,
- CLEAR H1,
- SHUT TEMP,
- IN TEMP,
- F1,
- ON NAT,
- F1 .
-
- ON NAT yields the natural output style with raised exponents, which
- is unsuitable for subsequent input.
-
- The OUT-statement causes subsequent output to be directed to the file
- named in the statement, until overridden by a different OUT-statement
- or until the file is closed by a SHUT-statement. File T is the
- terminal, and any other name designates a file on secondary storage.
- Such names must comply with the local file-naming conventions as well
- as with the REDUCE syntax. If the output is not of lasting
- importance, I find that including something like "TEMPORARY" or
- "SCRATCH" in the name helps remind me to delete it later.
-
- Successive OUT-statements to the same file will append rather than
- overwrite output if and only if there is no intervening SHUT-
- statement for that file. The SHUT-statement also has the effect of
- an implied OUT T.
-
- Note:
- 1. The generated output is the simplified expression rather than
- the raw form entered at the terminal.
- 2. Each output assignment automatically has a dollar-sign
- appended so that it is legal input and so that (perhaps
- lengthy) output will not unavoidably be generated at the
- terminal when the file is read in later.
- 3. Output cannot be sent simultaneously to 2 or more files.
- 4. Statements entered at the terminal which do not generate
- output -- such as declarations, LET rules, and procedure
- definitions -- do not appear in the secondary storage file.
- 5. One could get declarations, procedure definitions, rules, etc.
- written on secondary storage from the terminal by typing
- statements such as
-
- WRITE "
- ALGEBRAIC PROCEDURE ...
- ... " .
-
- This could serve as a means of generating permanent copies
- of LET rules, procedures, etc., but it is quite awkward
- compared with the usual way, which is to generate a file
- containing the REDUCE program by using a text editor, then
- load the program by using the IN-statement. If you have
- refrained from learning a local text editor and the operating-
- system file-management commands, hesitate no longer. A half
- dozen of the most basic commands will enable you to produce
- (and modify!) programs more conveniently than any other method.
- To keep from confusing the editor from REDUCE, I suggest that
- your first text-editing exercise be a letter to me:
-
- David R. Stoutemyer
- Electrical Engineering Department
- University of Hawaii
- Honolulu, Hawaii 96822 .
-
- Tell me your suggestions for improving this set of lessons.
- 5. The reason I didn't actually execute the above sequence of
- statements is that when the input to REDUCE comes from a batch
- file, both the input and output are sent to the output file,
- (which is convenient for producing a file containing both the
- input and output of a demonstration.) Consequently, you would
- have seen none of the statements between the "OUT TEMP" and
- "OUT T" as well as between the second "OUT TEMP" and the
- "SHUT TEMP", until the IN statement was executed. The example
- is confusing enough without having things scrambled from the
- order you would type them. To clarify all of this, I encourage
- you to actually execute the above sequence, with an
- appropriately chosen file name and using semicolons rather
- than commas. Afterwards, to return to the lesson, type CONT;
-
- PAUSE;
-
- COMMENT Suppose you and your colleagues developed or obtained a set
- of REDUCE files containing supplementary packages such as trigono-
- metric simplification, Laplace transforms, etc. It would be a waste
- of time (and perhaps paper) to have these files printed at the
- terminal every time they were loaded, so this printing can be
- suppressed by inserting the statement "OFF ECHO" at the beginning of
- the file, together with the statement "ON ECHO" at the end of the
- file.
-
- The lessons have amply demonstrated the PAUSE-statement, which is
- useful for insertion in batch files at the top-level or within
- functions when input from the user is necessary or desired.
-
- It often happens that after generating an expression, one decides
- that it would be convenient to use it as the body of a function
- definition, with one or more of the indeterminates therein as
- parameters. This can be done as follows;
-
- (1-(V/C)**2)**(1/2);
- FOR ALL V SAVEAS F(V);
- F(5);
-
- COMMENT Alternatively, we can use SAVEAS to save the previous
- expression as an indeterminate;
-
- SAVEAS FOF5;
- FOF5;
-
- COMMENT I find this technique more convenient than referring to the
- special variable WS;
-
- PAUSE;
-
- COMMENT The FOR-loop provides a convenient way to form finite sums or
- products with specific integer index limits. However, this need is
- so ubiquitous that REDUCE provides even more convenient syntax of
- the forms
-
- FOR index := initial STEP increment UNTIL final SUM expression,
-
- FOR index := initial STEP increment UNTIL final PRODUCT expression.
-
- As before, ":" is an acceptable abbreviation for "STEP 1 UNTIL". As
- an example of their use, here is a very concise definition of a
- function which computes Taylor-series expansions of symbolic
- expressions:;
-
- ALGEBRAIC PROCEDURE TAYLOR(EX, X, PT, N);
- COMMENT This function returns the degree N Taylor-series
- expansion of expression EX with respect to indeterminate X,
- expanded about expression PT. For a series-like appearance,
- display the answer under the influence of FACTOR X, ON RAT,
- and perhaps also ON DIV;
- SUB(X=PT, EX) + FOR K:=1:N SUM(SUB(X=PT, DF(EX,X,K))*(X-PT)**K
- / FOR J:=1:K PRODUCT J);
- CLEAR A, X; FACTOR X; ON RAT, DIV;
- G1 := TAYLOR(E**X, X, 0, 4);
- G2 := TAYLOR(E**COS(X)*COS(SIN(X)), X, 0, 3);
- TAYLOR(LOG(X), X, 0, 4);
-
- COMMENT It would, of course, be more efficient to compute each
- derivative and factorial from the preceding one. (Similarly for
- (X-PT)**K if and only if PT NEQ 0).
-
- The Fourier series expansion of our example E**COS(X)*COS(SIN(X))
- is 1 + cos(x) + cos(2*x)/2 + cos(3*x)/(3*2) + ... .
- Use the above SUM and PRODUCT features to generate the partial sum of
- this series through terms of order COS(6*X);
-
- PAUSE;
-
- COMMENT Closed-form solutions are often unobtainable for nontrivial
- problems, even using computer algebra. When this is the case,
- truncated symbolic series solutions are often worth trying before
- resorting to approximate numerical solutions.
-
- When we combine truncated series it is pointless (and worse yet,
- misleading) to retain terms of higher order than is justified by the
- constituents. For example, if we wish to multiply together the
- truncated series G1 and G2 generated above, there is no point in
- retaining terms higher than third degree in X. We can avoid even
- generating such terms as follows;
-
- LET X**4 = 0;
- G3 := G1*G2;
-
- COMMENT Replacing X**4 with 0 has the effect of also replacing all
- higher powers of X with 0. We could, of course, use our TAYLOR
- function to compute G3 directly, but differentiation is time
- consuming compared to truncated polynomial algebra. Moreover, our
- TAYLOR function requires a closed-form expression to begin with,
- whereas iterative techniques often permit us to construct symbolic
- series solutions even when we have no such closed form.
-
- Now consider the truncated series;
-
- CLEAR Y; FACTOR Y;
- H1 := TAYLOR(COS Y, Y, 0, 6);
-
- COMMENT Suppose we regard terms of order X**N in G1 as being
- comparable to terms of order Y**(2*N) in H1, and we want to form
- (G1*H1)**2. This can be done as follows;
-
- LET Y**7 = 0;
- F1 := (G1*H1)**2;
-
- COMMENT Note however that any terms of the form C*X**M*Y**N with
- 2*M+N > 6 are inconsistent with the accuracy of the constituent
- series, and we have generated several such misleading terms by
- independently truncating powers of X and Y. To avoid generating
- such junk, we can specify that a term be replaced by 0 whenever a
- weighted sum of exponents of specified indeterminates and functional
- forms exceeds a specified weight level. In our example this is done
- as follows;
-
- WEIGHT X=2, Y=1;
- WTLEVEL 6;
- F1 := F1;
-
- COMMENT variables not mentioned in a WEIGHT declaration have a
- weight of 0, and the default weight-level is 2;
-
- PAUSE;
-
- COMMENT In lesson 2 I promised to show you ways to overcome the lack
- in most REDUCE implementations of automatic numerical techniques
- for approximating fractional powers and transcendental functions of
- numerical values. One way is to provide a supplementary LET rule
- for numerical arguments. For example, since our TAYLOR function
- would reveal that the Taylor series for cos x is
- 1 - x**2/2! + x**4/4! - ...;
-
- FOR ALL X SUCH THAT NUMBERP X LET ABS(X)=X,ABS(-X)=X;
- EPSRECIP := 1024 $
- ON FLOAT;
- WHILE 1.0 + 1.0/EPSRECIP NEQ 1.0 DO
- EPSRECIP := EPSRECIP + EPSRECIP;
- FOR ALL X SUCH THAT NUMBERP NUM X AND NUMBERP DEN X LET COS X =
- BEGIN COMMENT X is integer, real, or a rational number. This rule
- returns the Taylor-series approximation to COS X, truncated when
- the last included term is less than (1/EPSRECIP) of the returned
- answer. EPSRECIP is a global variable initialized to a value
- that is appropriate to the local floating-point precision.
- Arbitrarily larger values are justifiable when X is exact and
- FLOAT is off. No angle reduction is performed, so this function
- is not recommended for ABS(X) >= about PI/2;
- INTEGER K; SCALAR MXSQ, TERM, ANS;
- K := 1;
- MXSQ := -X*X;
- TERM := MXSQ/2;
- ANS := TERM + 1;
- WHILE ABS(NUM TERM)*EPSRECIP*DEN(ANS)-ABS(NUM ANS)*DEN(TERM)>0 DO
- << TERM:= TERM*MXSQ/K/(K+1);
- ANS:= TERM + ANS;
- K := K+2 >>;
- RETURN ANS
- END;
- COS(F) + COS(1/2);
- OFF FLOAT;
- COS(1/2);
-
- COMMENT As an exercise, write a similar rule for the SIN or LOG, or
- replace the COS rule with an improved one which uses angle reduction
- so that angles outside a modest range are represented as equivalent
- angles within the range, before computing the Taylor series;
-
- PAUSE;
-
- COMMENT There is a REDUCE compiler, and you may wish to learn the
- local incantations for using it. However, even if rules such as
- the above ones are compiled, they will be slow compared to the
- implementation-dependent hand-coded ones used by most FORTRAN-like
- systems, so REDUCE provides a way to generate FORTRAN programs which
- can then be compiled and executed in a subsequent job step. This is
- useful when there is a lot of floating-point computation or when we
- wish to exploit an existing FORTRAN program. Suppose, for example,
- that we wish to utilize an existing FORTRAN subroutine which uses the
- Newton-Rapheson iteration
-
- Xnew := Xold - SUB(X=Xold, F(X)/DF(F(X),X))
-
- to attempt an approximate solution to the equation F(X)=0. Most such
- subroutines require the user to provide a FORTRAN function or
- subroutine which, given Xold, returns F(X)/DF(F(X),X) evaluated at
- X=Xold. If F(X) is complicated, manual symbolic derivation of
- DF(F(X),X) is a tedious and error-prone process. We can get
- REDUCE to relieve us of this responsibility as is illustrated below
- for the trivial example F(X) = X*E**X - 1:
-
- ON FORT, FLOAT,
- OUT FONDFFILE,
- WRITE " REAL FUNCTION FONDF(XOLD)",
- WRITE " REAL XOLD, F",
- F := XOLD*E**XOLD - 1.0,
- FONDF := F/DF(F,XOLD),
- WRITE " RETURN",
- WRITE " END",
- SHUT FONDFFILE .
-
- COMMENT Under the influence of ON FORT, the output generated by
- assignments is printed as valid FORTRAN assignment statements, using
- as many continuation lines as necessary up to the amount specified
- by the global variable !*CARDNO, which is initially set to 20. The
- output generated by an expression which is not an assignment is a
- corresponding assignment to a variable named ANS. In either case,
- expressions which would otherwise exceed !*CARDNO continuation
- lines are evaluated piecewise, using ANS as an intermediate variable.
-
- Try executing the above sequence, using an appropriate filename and
- using semicolons rather than commas at the end of the lines, then
- print the file after the lesson to see how it worked;
-
- PAUSE;
- OFF FORT, FLOAT;
-
- COMMENT To make this technique usable by non-REDUCE programmers, we
- could write a more general REDUCE program which given merely the
- expression F by the user, outputs not only the function FONDF, but
- also any necessary Job-control commands and an appropriate main
- program for calling the Newton-Rapheson subroutine and printing the
- results.
-
- Sometimes it is desirable to modify or supplement the syntax
- of REDUCE. For example:
- 1. Electrical engineers may prefer to input J as the representation
- of (-1)**(1/2).
- 2. Many users may prefer to input LN to denote natural logarithms.
- 3. A user with previous exposure to the PL/I-FORMAC computer-
- algebra system might prefer to use DERIV instead of DF to
- request differentiation.
- 4. A macrophiliac might prefer to have N! followed by a blank
- always be replaced by the expression (FOR K:=1:N PRODUCT N).
-
- Such lexical macros can be established by the DEFINE declaration:;
-
- CLEAR X,J,N;
- %Define for 1:N causes a prompt for an unbound ID. Continue anyway.
- DEFINE J=I, LN=LOG, DERIV=DF, N! =(FOR K:=1:N PRODUCT K);
-
- COMMENT Now watch!;
-
- N := 3;
- G1 := SUB(X=LN(J**3*X), DERIV(X**2,X)/N! );
-
- COMMENT Each "equation" in a DEFINE declaration must be of the form
- "name = item", where each item is an expression, an operator, or a
- REDUCE-reserved word such as "FOR". Such replacements take place
- during the lexical scanning, before any evaluation, LET rules, or
- built-in simplification. Think of a good application for this
- facility, then try it;
-
- PAUSE;
-
- COMMENT When REDUCE is being run in batch mode, it is preferable to
- have REDUCE make reasonable decisions and proceed when it encounters
- apparently undeclared operators, divisions by zero, etc. In
- interactive mode, it is preferable to pause and query the user. ON
- INT specifies the latter style, and OFF INT specifies the
- former. Under the influence of OFF INT, we can also have most
- error messages suppressed by specifying OFF MSG. This is sometimes
- useful when we expect abnormal conditions and do not want our listing
- marred by the associated messages. INT is automatically turned off
- during input from a batch file in response to an IN-command from a
- terminal.
-
- Some implementations permit the user to dynamically request more
- storage by executing a command of the form
-
- CORE number,
-
- where the number is an integer specifying the total desired core in
- some units such as bytes, words, kilobytes, or kilowords;
-
- PAUSE;
-
- COMMENT Some implementations have a trace command for debugging,
- which employs the syntax
-
- TR functionname1, functionname2, ..., functionnameN .
-
- An analogous command named UNTR removes function names from trace
- status;
-
- PAUSE;
-
- COMMENT Some implementations have an assignment-tracing command for
- debugging, which employs the syntax
-
- TRST functionname1, functionname2, ..., functionnameN.
-
- An analogous command named UNTRST removes functionnames from
- this status. All assignments in the designated functions are
- reported, except for assignments to array elements. Such functions
- must be uncompiled and must have a top-level BEGIN-block. To apply
- both TRST and TR to a function simultaneously, it is crucial to
- request them in that order, and it is necessary to relinquish the two
- kinds of tracing in the opposite order;
-
- PAUSE;
-
- COMMENT The REDUCE algebraic algorithms are written in a subset of
- REDUCE called RLISP. In turn, the more sophisticated features of
- RLISP are written in a small subset of RLISP which is written in a
- subset of LISP that is relatively common to most LISP systems.
-
- RLISP is ideal for implementing algebraic algorithms, but the RLISP
- environment is not most suitable for the routine use of these
- algorithms in the natural mathematical style of the preceding
- lessons. Accordingly, REDUCE jobs are initially in a mode called
- ALGEBRAIC, which provides the user with the environment illustrated
- in the preceding lessons, while insulating him from accidental
- interaction with the numerous functions, global variables, etc.
- necessary for implementing the built-in algebra. In contrast, the
- underlying RLISP system together with all of the algebraic
- simplification algorithms written therein is called SYMBOLIC mode.
-
- As we have seen, algebraic-mode rules and procedures can be used to
- extend the built-in algebraic capabilities. However, some extensions
- can be accomplished most easily or efficiently by descending to
- SYMBOLIC mode.
-
- To make REDUCE operate in symbolic mode, we merely execute the top
- level mode-declaration statement consisting of the word SYMBOLIC. We
- can subsequently switch back by executing the statement consisting of
- the word ALGEBRAIC.
-
- RLISP has the semantics of LISP with the syntax of our by-now-familiar
- algebraic-mode REDUCE, so RLISP provides a natural tool for many
- applications besides computer algebra, such as games, theorem-proving,
- natural-language translation, computer-aided instruction, and
- artificial intelligence in general. For this reason, it is possible
- to run RLISP without any of the symbolic-mode algebraic algorithms
- that are written in RLISP, and it is advisable to thus save space
- when the application does not involve computer algebra.
-
- We have now discussed virtually every feature that is available in
- algebraic mode, so lesson 6 will deal solely with RLISP, and
- lesson 7 will deal with communication between ALGEBRAIC and
- SYMBOLIC mode for mathematical purposes. However, I suggest that
- you proceed to those lessons only if and when:
- 1. You have consolidated and fully absorbed the information in
- lessons 1 through 5 by considerable practice beyond the
- exercises therein. (The exercises were intended to also
- suggest good related project ideas.)
- 2. You feel the need for a facility which you believe is impossible
- or quite awkward to implement solely in ALGEBRAIC mode.
- 3. You have read the pamphlet "Introduction to LISP", by D. Lurie,
- or an equivalent.
- 4. You are familiar with definition of Standard LISP, as described
- in the "Standard LISP Report" which was published in the October
- 1979 SIGPLAN Notices.
- Remember, when you decide to take lesson 6, it is better to do so from
- a RLISP job than from a REDUCE job. Also, don't forget to print your
- newly generated FORTRAN file and to delete any temporary files created
- by this lesson.
- ;END;
|