less5 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467
  1. COMMENT
  2. REDUCE INTERACTIVE LESSON NUMBER 5
  3. David R. Stoutemyer
  4. University of Hawaii
  5. COMMENT This is lesson 5 of 7 REDUCE lessons.
  6. There are at least two good reasons for wanting to save REDUCE
  7. expression assignments on secondary storage:
  8. 1. So that one can logout, then resume computation at a later
  9. time.
  10. 2. So that needed storage space can be cleared without
  11. irrecoverably losing the values of variables which are not
  12. needed in the next expression but will be needed later.
  13. Using trivial small expressions, the following sequence illustrates
  14. how this could be done:
  15. OFF NAT,
  16. OUT TEMP,
  17. F1 := (F + G)**2,
  18. G1 := G*F1,
  19. OUT T,
  20. CLEAR F1,
  21. H1 := H*G1,
  22. OUT TEMP,
  23. CLEAR G1,
  24. H2 := F*H1,
  25. CLEAR H1,
  26. SHUT TEMP,
  27. IN TEMP,
  28. F1,
  29. ON NAT,
  30. F1 .
  31. ON NAT yields the natural output style with raised exponents, which
  32. is unsuitable for subsequent input.
  33. The OUT-statement causes subsequent output to be directed to the file
  34. named in the statement, until overridden by a different OUT-statement
  35. or until the file is closed by a SHUT-statement. File T is the
  36. terminal, and any other name designates a file on secondary storage.
  37. Such names must comply with the local file-naming conventions as well
  38. as with the REDUCE syntax. If the output is not of lasting
  39. importance, I find that including something like "TEMPORARY" or
  40. "SCRATCH" in the name helps remind me to delete it later.
  41. Successive OUT-statements to the same file will append rather than
  42. overwrite output if and only if there is no intervening SHUT-
  43. statement for that file. The SHUT-statement also has the effect of
  44. an implied OUT T.
  45. Note:
  46. 1. The generated output is the simplified expression rather than
  47. the raw form entered at the terminal.
  48. 2. Each output assignment automatically has a dollar-sign
  49. appended so that it is legal input and so that (perhaps
  50. lengthy) output will not unavoidably be generated at the
  51. terminal when the file is read in later.
  52. 3. Output cannot be sent simultaneously to 2 or more files.
  53. 4. Statements entered at the terminal which do not generate
  54. output -- such as declarations, LET rules, and procedure
  55. definitions -- do not appear in the secondary storage file.
  56. 5. One could get declarations, procedure definitions, rules, etc.
  57. written on secondary storage from the terminal by typing
  58. statements such as
  59. WRITE "
  60. ALGEBRAIC PROCEDURE ...
  61. ... " .
  62. This could serve as a means of generating permanent copies
  63. of LET rules, procedures, etc., but it is quite awkward
  64. compared with the usual way, which is to generate a file
  65. containing the REDUCE program by using a text editor, then
  66. load the program by using the IN-statement. If you have
  67. refrained from learning a local text editor and the operating-
  68. system file-management commands, hesitate no longer. A half
  69. dozen of the most basic commands will enable you to produce
  70. (and modify!) programs more conveniently than any other method.
  71. To keep from confusing the editor from REDUCE, I suggest that
  72. your first text-editing exercise be a letter to me:
  73. David R. Stoutemyer
  74. Electrical Engineering Department
  75. University of Hawaii
  76. Honolulu, Hawaii 96822 .
  77. Tell me your suggestions for improving this set of lessons.
  78. 5. The reason I didn't actually execute the above sequence of
  79. statements is that when the input to REDUCE comes from a batch
  80. file, both the input and output are sent to the output file,
  81. (which is convenient for producing a file containing both the
  82. input and output of a demonstration.) Consequently, you would
  83. have seen none of the statements between the "OUT TEMP" and
  84. "OUT T" as well as between the second "OUT TEMP" and the
  85. "SHUT TEMP", until the IN statement was executed. The example
  86. is confusing enough without having things scrambled from the
  87. order you would type them. To clarify all of this, I encourage
  88. you to actually execute the above sequence, with an
  89. appropriately chosen file name and using semicolons rather
  90. than commas. Afterwards, to return to the lesson, type CONT;
  91. PAUSE;
  92. COMMENT Suppose you and your colleagues developed or obtained a set
  93. of REDUCE files containing supplementary packages such as trigono-
  94. metric simplification, Laplace transforms, etc. It would be a waste
  95. of time (and perhaps paper) to have these files printed at the
  96. terminal every time they were loaded, so this printing can be
  97. suppressed by inserting the statement "OFF ECHO" at the beginning of
  98. the file, together with the statement "ON ECHO" at the end of the
  99. file.
  100. The lessons have amply demonstrated the PAUSE-statement, which is
  101. useful for insertion in batch files at the top-level or within
  102. functions when input from the user is necessary or desired.
  103. It often happens that after generating an expression, one decides
  104. that it would be convenient to use it as the body of a function
  105. definition, with one or more of the indeterminates therein as
  106. parameters. This can be done as follows;
  107. (1-(V/C)**2)**(1/2);
  108. FOR ALL V SAVEAS F(V);
  109. F(5);
  110. COMMENT Alternatively, we can use SAVEAS to save the previous
  111. expression as an indeterminate;
  112. SAVEAS FOF5;
  113. FOF5;
  114. COMMENT I find this technique more convenient than referring to the
  115. special variable WS;
  116. PAUSE;
  117. COMMENT The FOR-loop provides a convenient way to form finite sums or
  118. products with specific integer index limits. However, this need is
  119. so ubiquitous that REDUCE provides even more convenient syntax of
  120. the forms
  121. FOR index := initial STEP increment UNTIL final SUM expression,
  122. FOR index := initial STEP increment UNTIL final PRODUCT expression.
  123. As before, ":" is an acceptable abbreviation for "STEP 1 UNTIL". As
  124. an example of their use, here is a very concise definition of a
  125. function which computes Taylor-series expansions of symbolic
  126. expressions:;
  127. ALGEBRAIC PROCEDURE TAYLOR(EX, X, PT, N);
  128. COMMENT This function returns the degree N Taylor-series
  129. expansion of expression EX with respect to indeterminate X,
  130. expanded about expression PT. For a series-like appearance,
  131. display the answer under the influence of FACTOR X, ON RAT,
  132. and perhaps also ON DIV;
  133. SUB(X=PT, EX) + FOR K:=1:N SUM(SUB(X=PT, DF(EX,X,K))*(X-PT)**K
  134. / FOR J:=1:K PRODUCT J);
  135. CLEAR A, X; FACTOR X; ON RAT, DIV;
  136. G1 := TAYLOR(E**X, X, 0, 4);
  137. G2 := TAYLOR(E**COS(X)*COS(SIN(X)), X, 0, 3);
  138. TAYLOR(LOG(X), X, 0, 4);
  139. COMMENT It would, of course, be more efficient to compute each
  140. derivative and factorial from the preceding one. (Similarly for
  141. (X-PT)**K if and only if PT NEQ 0).
  142. The Fourier series expansion of our example E**COS(X)*COS(SIN(X))
  143. is 1 + cos(x) + cos(2*x)/2 + cos(3*x)/(3*2) + ... .
  144. Use the above SUM and PRODUCT features to generate the partial sum of
  145. this series through terms of order COS(6*X);
  146. PAUSE;
  147. COMMENT Closed-form solutions are often unobtainable for nontrivial
  148. problems, even using computer algebra. When this is the case,
  149. truncated symbolic series solutions are often worth trying before
  150. resorting to approximate numerical solutions.
  151. When we combine truncated series it is pointless (and worse yet,
  152. misleading) to retain terms of higher order than is justified by the
  153. constituents. For example, if we wish to multiply together the
  154. truncated series G1 and G2 generated above, there is no point in
  155. retaining terms higher than third degree in X. We can avoid even
  156. generating such terms as follows;
  157. LET X**4 = 0;
  158. G3 := G1*G2;
  159. COMMENT Replacing X**4 with 0 has the effect of also replacing all
  160. higher powers of X with 0. We could, of course, use our TAYLOR
  161. function to compute G3 directly, but differentiation is time
  162. consuming compared to truncated polynomial algebra. Moreover, our
  163. TAYLOR function requires a closed-form expression to begin with,
  164. whereas iterative techniques often permit us to construct symbolic
  165. series solutions even when we have no such closed form.
  166. Now consider the truncated series;
  167. CLEAR Y; FACTOR Y;
  168. H1 := TAYLOR(COS Y, Y, 0, 6);
  169. COMMENT Suppose we regard terms of order X**N in G1 as being
  170. comparable to terms of order Y**(2*N) in H1, and we want to form
  171. (G1*H1)**2. This can be done as follows;
  172. LET Y**7 = 0;
  173. F1 := (G1*H1)**2;
  174. COMMENT Note however that any terms of the form C*X**M*Y**N with
  175. 2*M+N > 6 are inconsistent with the accuracy of the constituent
  176. series, and we have generated several such misleading terms by
  177. independently truncating powers of X and Y. To avoid generating
  178. such junk, we can specify that a term be replaced by 0 whenever a
  179. weighted sum of exponents of specified indeterminates and functional
  180. forms exceeds a specified weight level. In our example this is done
  181. as follows;
  182. WEIGHT X=2, Y=1;
  183. WTLEVEL 6;
  184. F1 := F1;
  185. COMMENT variables not mentioned in a WEIGHT declaration have a
  186. weight of 0, and the default weight-level is 2;
  187. PAUSE;
  188. COMMENT In lesson 2 I promised to show you ways to overcome the lack
  189. in most REDUCE implementations of automatic numerical techniques
  190. for approximating fractional powers and transcendental functions of
  191. numerical values. One way is to provide a supplementary LET rule
  192. for numerical arguments. For example, since our TAYLOR function
  193. would reveal that the Taylor series for cos x is
  194. 1 - x**2/2! + x**4/4! - ...;
  195. FOR ALL X SUCH THAT NUMBERP X LET ABS(X)=X,ABS(-X)=X;
  196. EPSRECIP := 1024 $
  197. ON FLOAT;
  198. WHILE 1.0 + 1.0/EPSRECIP NEQ 1.0 DO
  199. EPSRECIP := EPSRECIP + EPSRECIP;
  200. FOR ALL X SUCH THAT NUMBERP NUM X AND NUMBERP DEN X LET COS X =
  201. BEGIN COMMENT X is integer, real, or a rational number. This rule
  202. returns the Taylor-series approximation to COS X, truncated when
  203. the last included term is less than (1/EPSRECIP) of the returned
  204. answer. EPSRECIP is a global variable initialized to a value
  205. that is appropriate to the local floating-point precision.
  206. Arbitrarily larger values are justifiable when X is exact and
  207. FLOAT is off. No angle reduction is performed, so this function
  208. is not recommended for ABS(X) >= about PI/2;
  209. INTEGER K; SCALAR MXSQ, TERM, ANS;
  210. K := 1;
  211. MXSQ := -X*X;
  212. TERM := MXSQ/2;
  213. ANS := TERM + 1;
  214. WHILE ABS(NUM TERM)*EPSRECIP*DEN(ANS)-ABS(NUM ANS)*DEN(TERM)>0 DO
  215. << TERM:= TERM*MXSQ/K/(K+1);
  216. ANS:= TERM + ANS;
  217. K := K+2 >>;
  218. RETURN ANS
  219. END;
  220. COS(F) + COS(1/2);
  221. OFF FLOAT;
  222. COS(1/2);
  223. COMMENT As an exercise, write a similar rule for the SIN or LOG, or
  224. replace the COS rule with an improved one which uses angle reduction
  225. so that angles outside a modest range are represented as equivalent
  226. angles within the range, before computing the Taylor series;
  227. PAUSE;
  228. COMMENT There is a REDUCE compiler, and you may wish to learn the
  229. local incantations for using it. However, even if rules such as
  230. the above ones are compiled, they will be slow compared to the
  231. implementation-dependent hand-coded ones used by most FORTRAN-like
  232. systems, so REDUCE provides a way to generate FORTRAN programs which
  233. can then be compiled and executed in a subsequent job step. This is
  234. useful when there is a lot of floating-point computation or when we
  235. wish to exploit an existing FORTRAN program. Suppose, for example,
  236. that we wish to utilize an existing FORTRAN subroutine which uses the
  237. Newton-Rapheson iteration
  238. Xnew := Xold - SUB(X=Xold, F(X)/DF(F(X),X))
  239. to attempt an approximate solution to the equation F(X)=0. Most such
  240. subroutines require the user to provide a FORTRAN function or
  241. subroutine which, given Xold, returns F(X)/DF(F(X),X) evaluated at
  242. X=Xold. If F(X) is complicated, manual symbolic derivation of
  243. DF(F(X),X) is a tedious and error-prone process. We can get
  244. REDUCE to relieve us of this responsibility as is illustrated below
  245. for the trivial example F(X) = X*E**X - 1:
  246. ON FORT, FLOAT,
  247. OUT FONDFFILE,
  248. WRITE " REAL FUNCTION FONDF(XOLD)",
  249. WRITE " REAL XOLD, F",
  250. F := XOLD*E**XOLD - 1.0,
  251. FONDF := F/DF(F,XOLD),
  252. WRITE " RETURN",
  253. WRITE " END",
  254. SHUT FONDFFILE .
  255. COMMENT Under the influence of ON FORT, the output generated by
  256. assignments is printed as valid FORTRAN assignment statements, using
  257. as many continuation lines as necessary up to the amount specified
  258. by the global variable !*CARDNO, which is initially set to 20. The
  259. output generated by an expression which is not an assignment is a
  260. corresponding assignment to a variable named ANS. In either case,
  261. expressions which would otherwise exceed !*CARDNO continuation
  262. lines are evaluated piecewise, using ANS as an intermediate variable.
  263. Try executing the above sequence, using an appropriate filename and
  264. using semicolons rather than commas at the end of the lines, then
  265. print the file after the lesson to see how it worked;
  266. PAUSE;
  267. OFF FORT, FLOAT;
  268. COMMENT To make this technique usable by non-REDUCE programmers, we
  269. could write a more general REDUCE program which given merely the
  270. expression F by the user, outputs not only the function FONDF, but
  271. also any necessary Job-control commands and an appropriate main
  272. program for calling the Newton-Rapheson subroutine and printing the
  273. results.
  274. Sometimes it is desirable to modify or supplement the syntax
  275. of REDUCE. For example:
  276. 1. Electrical engineers may prefer to input J as the representation
  277. of (-1)**(1/2).
  278. 2. Many users may prefer to input LN to denote natural logarithms.
  279. 3. A user with previous exposure to the PL/I-FORMAC computer-
  280. algebra system might prefer to use DERIV instead of DF to
  281. request differentiation.
  282. 4. A macrophiliac might prefer to have N! followed by a blank
  283. always be replaced by the expression (FOR K:=1:N PRODUCT N).
  284. Such lexical macros can be established by the DEFINE declaration:;
  285. CLEAR X,J,N;
  286. %Define for 1:N causes a prompt for an unbound ID. Continue anyway.
  287. DEFINE J=I, LN=LOG, DERIV=DF, N! =(FOR K:=1:N PRODUCT K);
  288. COMMENT Now watch!;
  289. N := 3;
  290. G1 := SUB(X=LN(J**3*X), DERIV(X**2,X)/N! );
  291. COMMENT Each "equation" in a DEFINE declaration must be of the form
  292. "name = item", where each item is an expression, an operator, or a
  293. REDUCE-reserved word such as "FOR". Such replacements take place
  294. during the lexical scanning, before any evaluation, LET rules, or
  295. built-in simplification. Think of a good application for this
  296. facility, then try it;
  297. PAUSE;
  298. COMMENT When REDUCE is being run in batch mode, it is preferable to
  299. have REDUCE make reasonable decisions and proceed when it encounters
  300. apparently undeclared operators, divisions by zero, etc. In
  301. interactive mode, it is preferable to pause and query the user. ON
  302. INT specifies the latter style, and OFF INT specifies the
  303. former. Under the influence of OFF INT, we can also have most
  304. error messages suppressed by specifying OFF MSG. This is sometimes
  305. useful when we expect abnormal conditions and do not want our listing
  306. marred by the associated messages. INT is automatically turned off
  307. during input from a batch file in response to an IN-command from a
  308. terminal.
  309. Some implementations permit the user to dynamically request more
  310. storage by executing a command of the form
  311. CORE number,
  312. where the number is an integer specifying the total desired core in
  313. some units such as bytes, words, kilobytes, or kilowords;
  314. PAUSE;
  315. COMMENT Some implementations have a trace command for debugging,
  316. which employs the syntax
  317. TR functionname1, functionname2, ..., functionnameN .
  318. An analogous command named UNTR removes function names from trace
  319. status;
  320. PAUSE;
  321. COMMENT Some implementations have an assignment-tracing command for
  322. debugging, which employs the syntax
  323. TRST functionname1, functionname2, ..., functionnameN.
  324. An analogous command named UNTRST removes functionnames from
  325. this status. All assignments in the designated functions are
  326. reported, except for assignments to array elements. Such functions
  327. must be uncompiled and must have a top-level BEGIN-block. To apply
  328. both TRST and TR to a function simultaneously, it is crucial to
  329. request them in that order, and it is necessary to relinquish the two
  330. kinds of tracing in the opposite order;
  331. PAUSE;
  332. COMMENT The REDUCE algebraic algorithms are written in a subset of
  333. REDUCE called RLISP. In turn, the more sophisticated features of
  334. RLISP are written in a small subset of RLISP which is written in a
  335. subset of LISP that is relatively common to most LISP systems.
  336. RLISP is ideal for implementing algebraic algorithms, but the RLISP
  337. environment is not most suitable for the routine use of these
  338. algorithms in the natural mathematical style of the preceding
  339. lessons. Accordingly, REDUCE jobs are initially in a mode called
  340. ALGEBRAIC, which provides the user with the environment illustrated
  341. in the preceding lessons, while insulating him from accidental
  342. interaction with the numerous functions, global variables, etc.
  343. necessary for implementing the built-in algebra. In contrast, the
  344. underlying RLISP system together with all of the algebraic
  345. simplification algorithms written therein is called SYMBOLIC mode.
  346. As we have seen, algebraic-mode rules and procedures can be used to
  347. extend the built-in algebraic capabilities. However, some extensions
  348. can be accomplished most easily or efficiently by descending to
  349. SYMBOLIC mode.
  350. To make REDUCE operate in symbolic mode, we merely execute the top
  351. level mode-declaration statement consisting of the word SYMBOLIC. We
  352. can subsequently switch back by executing the statement consisting of
  353. the word ALGEBRAIC.
  354. RLISP has the semantics of LISP with the syntax of our by-now-familiar
  355. algebraic-mode REDUCE, so RLISP provides a natural tool for many
  356. applications besides computer algebra, such as games, theorem-proving,
  357. natural-language translation, computer-aided instruction, and
  358. artificial intelligence in general. For this reason, it is possible
  359. to run RLISP without any of the symbolic-mode algebraic algorithms
  360. that are written in RLISP, and it is advisable to thus save space
  361. when the application does not involve computer algebra.
  362. We have now discussed virtually every feature that is available in
  363. algebraic mode, so lesson 6 will deal solely with RLISP, and
  364. lesson 7 will deal with communication between ALGEBRAIC and
  365. SYMBOLIC mode for mathematical purposes. However, I suggest that
  366. you proceed to those lessons only if and when:
  367. 1. You have consolidated and fully absorbed the information in
  368. lessons 1 through 5 by considerable practice beyond the
  369. exercises therein. (The exercises were intended to also
  370. suggest good related project ideas.)
  371. 2. You feel the need for a facility which you believe is impossible
  372. or quite awkward to implement solely in ALGEBRAIC mode.
  373. 3. You have read the pamphlet "Introduction to LISP", by D. Lurie,
  374. or an equivalent.
  375. 4. You are familiar with definition of Standard LISP, as described
  376. in the "Standard LISP Report" which was published in the October
  377. 1979 SIGPLAN Notices.
  378. Remember, when you decide to take lesson 6, it is better to do so from
  379. a RLISP job than from a REDUCE job. Also, don't forget to print your
  380. newly generated FORTRAN file and to delete any temporary files created
  381. by this lesson.
  382. ;END;