version 5b RS (principal recent contributors include Roland Salz, Richard Fateman.8/2016) 9.1 Introduction to Simplification Maxima performs a cycle of actions in response to each new user-typed command. This consists of four steps: reading or "parsing" the input, evaluation, simplification and output. Parsing converts a syntactically-valid sequence of typed characters into a data structure to be used for the rest of the operations. Evaluation includes replacing names with their assigned values. Simplification means rewriting an expression to be easier for the user or other programs to understand. Output includes displaying computational results in a variety of different formats and notations. Evaluation and simplification sometimes appear to have similar functionality as they both have the goal of removing "complexity" and system designers have sometimes divided a task so that it is performed partly in each. For example, integrate(x,x) evaluates the answer as x*x/2, which is then simplified to x^2/2. Evaluation is always present: it is the consequence of having a programming system with functions, subroutines, variables, values, loops, assignments and so on. In the evaluation step, built-in or user-defined function names are replaced by their definitions, variables are replaced by their values. This is largely the same as activities of a conventional programming language, but extended to work with symbolic mathematical data. Because of the generality of the mathematics at hand, there are different possible models of evaluation and so the systems has optional "flags" that can steer the process of evaluation. Chapter 8 describes this process in detail. By contrast, the intent of simplification is to maintain the value of an expression while re-formulating its representation to be smaller, simpler to understand, or to conform to particular specifications (like factored, expanded). For example, sin(0) to 0 or x+x to 2*x. There are several powerful tools to alter the results of simplification, since it is largely in this part of the system that a user can incorporate knowledge of the interrelationships of newly introduced functions or symbolic notation into Maxima. Simplification is generally done at four different levels: 1. The internal, built-in automated simplifier, 2. Built-in simplification routines that can be explicitly called by the user at selected places in a program or command sequence, 3. User-written simplification routines, linked to the simplifier by using "tellsimp" or "tellsimpafter" and called automatically, 4. User-written routines that can be explicitly called by the user at selected places in a program or command sequence. The internal simplifier belongs to the heart of Maxima. It is a large and complicated collection of programs, and it has been refined over many years and by thousands of users. Nevertheless, especially if you are trying out novel ideas or unconventional notation, you may find it helpful to make small (or large) changes to the program yourself. You can get help for a more sophisticated understanding of this program by reading the (1979) paper, "MACSYMA’s General Simplifier: Philosophy and Operation" by Richard J. Fateman. A copy of this paper is attached, below. Maxima internally represents expressions as "trees" with operators or "roots" like +, * , = and operands ("leaves") which are variables like x, y, z, functions or sub-trees, like x*y. Each operator has a simplification program associated with it. + (which also covers binary - since a-b = a+(-1)*b) and * (which also covers / since a/b = a*b^(-1)) have rather elaborate simplification programs. These simplification programs (simplus, simptimes, simpexpt, etc.) are called whenever the simplifier encounters the respective arithmetic operators in an expression tree to be analyzed. The structure of the simplifier dates back to 1965, and many hands have worked on it through the years. The structure turns out to be, in modern jargon, data- directed, or object-oriented. The program dispatches to the appropriate routine depending on the root of some sub-tree of the expression, recursively. This general notion means you can make modifications to the simplification process by very local changes to the program. In many cases it is conceptually straightforward to add an operator and add its simplification routine without disturbing existing code. We note that in addition to this general simplifier operating on algebraic expression trees, there are several other representations of expressions in Maxima which have separate methods and simplifiers. For example, the rat() function converts polynomials to vectors of coefficients to assist in rapid manipulation of such forms. Other representations include Taylor series and the (rarely used) Poisson series. A new operator introduced by a user initially has no simplification programs associated with it. Maxima does not know anything about function "f" and so typing f(a,b) will result in simplifying a,b, but not f. Even some built-in operators have no simplifications. For example, = does not "simplify" -- it is a place-holder with no simplification semantics other than to simplify its two arguments, in this case referred to as the left and right sides. Other parts of Maxima such as the solve program take special note of equations, that is, trees with = as the root. (Note -- in Maxima, the assignment operation is ":" . That is, q: 4 sets the value of the symbol q to 4. Function definition is done with ":=". ) The general simplifier returns results with an internal flag indicating the expression and each sub-expression has been simplified. This does not guarantee that it is unique over all possible equivalent expressions. That's too hard (theoretically, not possible given the generality of what can be expressed in Maxima). However, some aspects of the expression, such as the ordering of terms in a sum or product, are made uniform. This is important for the other programs to work properly. You can set a number of option variables which direct Maxima's processing to favor particular kinds of patterns as being goals. You can even use the most extreme option which is to turn the simplifier off by simp:false. We do not recommend this since many internal routines expect their arguments to be simplified. (About the only time it seems plausible to turn off the simplifier is in the rare case that you want to over-ride a built-in simplification. In that case you might temporarily disable the simplifier, put in the new transformation via "tellsimp", and then re-enable the simplifier by simp:true.) It is more plausible for you to associate user-defined symbolic function names (see chapter 36) or operators (see chapter 7) with properties (additive, lassociative, oddfun, antisymmetric, linear, outative, commutative, multiplicative, rassociative, evenfun, nary, symmetric). These options steer the simplifier processing in systematic directions. For example, declare(f,oddfun) specifies that f is an odd function. Maxima will simplify f(-x) to –f(x). In the case of an even function, that is declare(g,evenfun), Maxima will simplify g(-x) to g(x). You can also associate a programming function with a name such as h(x):=x^2+1. In that case the evaluator will immediately replace h(3) by 10, and h(a+1) by (a+1)^2+1, so any other properties of h will be ignored. In addition to these directly related properties set up by the user, facts and properties from the actual context may have an impact on the simplifier’s behavior, too. See chapter 11, Maxima’s Database. Example: sin(n*%pi) is simplified to zero, if n is an integer. (%i1) sin(n*%pi); (%o1) sin(%pi n) (%i2) declare(n, integer); (%o2) done (%i3) sin(n*%pi); (%o3) 0 If automated simplification is not sufficient, you can consider a variety of built-in, but explicitly called simplification functions (ratsimp, expand, factor, radcan, and others). There are also flags that will push simplification into one or another direction. Given demoivre:true, the simplifier rewrites complex exponentials as trigonometric forms. Given exponentialize:true, the simplifier tries to do the reverse: rewrite trigonometric forms as complex exponentials. As everywhere in Maxima, by writing your own functions (be it in the Maxima user language or in the implementation language Lisp) and explicitly calling them at selected places in the program, you can seek to transform expressions toward your simplification goal. While Lisp gives you a handle on all the internal mechanisms, you rarely need this full generality. "Tellsimp" is designed to generate much of the Lisp internal interface into the simplifier automatically. See chapter 34, Rules and Patterns. Over the years (Maxima/Macsyma's origins date back to about 1966!) users have contributed numerous application packages and tools to extend or alter its functional behavior. Various non-standard and "share" packages provide tools to extend simplification as well. You are invited to look into this more experimental material where work is still in progress. See chapter 80 and check the "share" directory of your Maxima distribution. The following appended material is optional on a first reading, and reading it is not necessary for productive use of Maxima. It is for the curious user who wants to understand what is going on, or the ambitious programmer who might wish to change the (open-source) code. Experimentation with redefining Maxima Lisp code is easily possible: to change the definition of a Lisp program (say the one that simplifies cos(), named simp%cos), you simply load into Maxima a text file that redefines and will overwrite the built-in simp%cos. /////////////////////////////////////////// (note, the current spelling Maxima is a corruption of the original name, Macsyma, used by Massachussetts Institute of Technology, Project MAC, which sold commercial rights to a version of this program. In order to avoid legal disputes, the public open-source version of the program was renamed. In the text below, most statements are true without change in Maxima. However, MACSYMA (along with its original version of Lisp) does not distinguish upper and lower case, and so the programs may look like they are shouted out. To use them in Maxima, use lower case. -- RJF 2016) MACSYMA'S General Simplifier Philosophy and Operation Richard J. Fateman Computer Science Division Electrical Engineering and Computer Science. Dept. University of California Berkeley California From "Macsyma Users Conference 1979". This was run through an OCR program which introduced typos. We fixed the ones we noticed. RJF 2016.) 1. Introduction Ideally the transformations performed by MACSYMA's simplification pro- gram on algebraic expressions correspond to those simplification. desired by each user and each program. Since it is impossible for a program to intuit all users' requirements simultaneously, explicit control of the simplifier is necessary to override default transformations. A model of the simplification process is helpful in controlling this large and complex program. Having examined several algebraic simplification programs, it appears that to date no program has been written which combines a conceptually simple and useful view of simplification with a program nearly as powerful as MACSYMA's. {note date, 1979. RJF) Rule-directed transformation schemes struggle to approach the power of the varied control structures in more usual program schemes [Fenichel, 68]. {note, Mathematica pushes rules further. RJF} It is our belief that a thorough grasp of the decision and data structures of the MACSYMA simplifier program itself is the most direct way of understanding its potential for algebraic expression transformation. This is an unfortunate admission to have to make, but it appears to reflect the state of the art in dealing with formalizations of complex programs. Simplification is a perplexing task. Because of this, we feel it behooves the "guardians of the simplifier" to try to meet the concerned MACSYMA users part-way by documenting the program as it has evolved. We hope this paper continues to grow to reflect a reasonably accurate, complete, and current description. Of course Lisp program details are available to the curious, but even for those without a working knowledge of the Lisp language (in which the simplifier is written) we expect this paper to be of some help in answering questions which arise perennially as to why MACSYMA deals with same particular class of expressions in some unanticipated fashion, or is inefficient in performing some set of transformations. Most often difficulties such as these are accounted for by implicit design decisions which are not evident from mere descriptions of what is done in the anticipated and usual cases. We also hope that improvements or revisions of the simplifier will benefit from the more centralized treatment of issues given here. We also provide additional commentary which reflects our current outlook on how simplification programs should be written, and what capabilities they should have. 2. The ground rules The general simplification package of MACSYMA is a set of programs written in MacLisp, a dialect of Lisp 1.5. This package allows simplification and manipulation of algebraic expressions in the "general" tree-like form used for most of MACSYMA. Several special purpose simplifiers, such as those for rational functions, Taylor series, trigonometric forms, factorial forms, etc., are not included in this discussion except peripherally. The general simplifier is the heart of MACSYMA. and has the unenviable task of dealing with the multiplicity of data types in MACSYMA. It must also respond to a large number of "flag" settings in the environment in directing the simplification process. It must be sufficiently flexible so that additions, alterations, and deletions from its repertoire are possible, since the concept of simplicity is highly context dependent, and the user may seek to modify the program to conform to his specifications. An excellent discussion of the various meanings of simplification is given in [Moses, 71]. When we use the word "simplified" in this paper, we mean the result of running the simplification program on an expression. The fact that the "simplified" form may not appear to be simpler to the reader is usually irrelevant. The form is a consequence of the myriad transformations incorporated into the program over the years. Among the (less desirable) properties of the form is that two mathematically equivalent expressions may not simplify into identical results. -- Given the generality of the class of expressions handled, this is to be expected, in fact, necessary since the zero-equivalence problem is "recursively undecidable". Many programs are written in such a fashion as to be resistant to misbehavior on invalid inputs. So-called "robust" programs thrive on the ability to detect and ward off illegal inputs. It is clearly of value to have a robust simplifier in MACSYMA. However, as far as possible MACSYMA attempts to avoid specific checks for bad input until absolutely necessary. In this way an input not originally envisioned by the author of the main program can percolate down to a rou- tine, added later, which makes sense of it. The intermediate programs will not notice the problem at all. This is a very effective way of working in a growing system but obviously has its pitfalls if truly unexpected errors percolate down to a routine unable to handle them. Furthermore, the messages that can be generated at a low level are not usually able to reflect the global causes Thus "division by zero" can sometimes be very uninformative, when the user has typed a command with no division in it at all. We will return to these issues in particular contexts. Historically, the MACSYMA simplifier is a modification of an "On-line Algebraic Simplify Program" written by Knut Korsvold [Korsvold, 65] Some of the programs remain only as shells of their original form, but many names are the same. (Some variable names have a definite Norwegian flavor.) Major additions were made along lines not possible in Korsvold's original program because of space limitations in his Q-32 Lisp system. Major deletions from his simplifier structure include his provisions for substitution and "rule-directed" simplification, and for polynomial canonical forms, including greatest-common-divisor calculation. These functions are provided in considerably different form in MACSYMA. 3. Internal forms of data in MACSYMA There are two external forms of data in MACSYMA visible to the user, and three (sometimes more) internal forms. The external form for input is a string of ASCII characters as typed in by the user or read from a file. (For example, the string "Y+3/X+Y;"). The output display of characters on a two-dimensional "grid" is the other external form, for example, 3 2Y + ---. X Between the external forms there are several internal forms. In actuality each is a Lisp "S-expression," a tree-like nested structure of list cells, pointers, and atomic names. The printed forms of these, expressed in the Lisp language, will usually look like parenthesized prefix strings. The different internal forms are: (1) The output from the parser, which is handed to the command interpreter. (2) The simplified form which most commands obtain by evaluating and simplifying their arguments. (3) The formatted form, which the display program uses to translate from the simplified form to a more "user oriented" expression. In the Berkeley VAX/UNIX version of the simplifier/display, a fourth form, namely typesetter code, is also used. (note: Other forms, some related to the MathML representation for World-Wide Web display are used in various front-ends for the Maxima version of Macsyma. RJF 2016) {There can be other forms, e.g. TeX form, rational form..} Some commands, as have been previously noted, impose different notions of simplification on expressions. We will not deal with these in any detail, although it is part of the overall philosophy of MACSYMA that alternative forms are allowed to co-exist, or can be converted to one another, in order to provide the most storage-efficient data structure and/or provide the fastest type of computation. By and large the data represents algebraic expressions, but sometimes represents programs, program fragments, messages, names of variables, files, or other information. The simplification program, SIMPLIFYA, is usually invoked by manipulatory functions such as the integration package. The input is an algebraic expression written in a type of parenthesized prefix notation. The input may have been partly simplified in the past, or may be "raw" from the parser. An expression is either an integer or floating-point number, an atomic "indeterminate," or a Lisp S-expression of the form (OPERATOR . ARGLIST). The ARGLIST is a list in the Lisp meaning, which contains the appropriate number of arguments for the associated OPERATOR. Each argument is itself (with a few exceptions having to do with the OPERATORs MRAT and \$POIS) an algebraic expression. Many operators have a fixed number of arguments. The exceptions include "n-ary" operators like PLUS, TIMES and DERIVATIVE. There is an initial collection of OPERATORs known to the simplifier; these may be augmented by using the "TELLSIMP" commands in MACSYMA discussed in section B. The symbols in the OPERATORs are a mixture of historical conventions, and several have two or more variants which are intended to signify the difference between a "verb" (e.g. Integrate this expression) and a "noun" (e.g. Consider the integral ...). The first part of each OPERATOR (the Lisp CAR) is indicative of the algebraic meaning. The rest of the OPERATOR consists of "flags" describing the arguments, or modifying the meaning of the OPERATOR. We make these notions more definite by examples in the next sections. 3.1. The internal form generated by the parser The following table indicates the "raw" output of the parser which corresponds to various input strings. The "input" column consists of character strings which (if followed by ";" or "\$") are accepted by the top-level MACSYMA parser. Since the parser is extensible, it is possible for the user to extend this table. An attentive reader may wonder if this table indicates all the possible forms of input to the simplifier. In fact, it does not, because some programs can and do generate forms which cannot be typed in directly by the user. Some of these forms may be generated by components of the simplifier itself. Some of the parser input is included primarily for completeness, and indicates various subtleties in the current MACSYMA "top-level" language which we will not explain here. The mysterious prefixing system involving the translation of single-quote (') to % and & originated in an attempt to separate the user's name space from the Lisp-programmer's name space. The `?` prefix is an attempt to thwart this separation. The separation is not effective in any case since using a MACSYMA- oded package written by someone else (or yourself!) again provides a potential for name-conflict. There are other techniques for "automatic prefixing" to achieve proper results. The prefixes are also used to separate related "noun" and "verb" forms, where they can both exist. {whether the ANSI CL programming language with its package mechanism provides a useful alternative is not entirely clear. The Maxima implementation makes only slight use of the package system in CL and retains the single-character prefix tradition. RJF 2016} MACSYMA Syntax and Internal Representation Input String Parser Output a \$a ?a a "a" "a" 'a ((mquote) \$a) x+y ((mplus) \$x \$y) x-y ((mplus) \$x ((mminus) \$y) x*y ((mtimes) \$x \$y) a(x) ((\$a) \$x) a[1,2] ((\$a array) 12) a[1,2](x) ((mqapply) ((\$a array) 1 2) \$x) sin(x) ((%sin) \$x) x/y ((mquotient) \$x \$y) x.y ((mnctimes) \$x \$y) x^2 or x**2 ((mexpt) \$x 2) x^^2 ((mncexpt) \$x 2) [a,b,c] ((mlist) \$a \$b \$c) (a,b,c) ((dolist) \$a \$b \$c) if a then b ((mcond) \$a \$b t \$false) if a then b else c ((mcond) \$a \$b t \$c) for i:a thru b step c unless q do f(i) ((mdo) \$i \$a \$c nil \$b \$q ((\$f) \$i)) for i:a next n unless q do f(i) ((mdo) \$i \$a nil \$n nil \$q ((\$f) \$i)) for i in L do f(i) ((mdoin) \$i \$L nil nil nil nil ((\$f) \$i)) diff(y,x) ((\$diff) \$y \$x 1) diff(y,x,2,z,1) ((\$diff) \$y \$x 2 \$z 1) 'diff(y,x) ((%derivative) \$y \$x 1) integrate(a,b,c,d) ((\$integrate) \$a \$b \$c \$d) 'integrate(a,b,c,d) ((%integrate) \$a \$b \$c \$d) block([l1,l2], s1,s2) ((mprog) ((mlist) \$l1 \$l2) \$s1 \$s2) block(s1,s2) ((mprog) ((mlist)) \$s1 \$s2) not a ((mnot) \$a) a or b ((mor) \$a \$b) a and b ((mand) \$a \$b) a=b ((mequal) \$a \$b) a>b ((mgreaterp) \$a \$b) a>=b ((mgeqp) \$a \$b) a f(a)+f(b) antisymmetric f(a,b)+f(b, a) ==> 0 commutative f(a,b)-f(b,a) > 0 multiplicative f(a*b) ==> f(a)f(b) outative f(3*a) > 3*f(pj~) linear f(a+3*b) ==> f(a)+3*f(b) ~or instead of "3", any constant.~ associative f(f(a,b),f(c,d))-f(a,f(b,f(c,d))) ==> 0 rassociative f(a,f(b,c)) ==> f(f(a,b),c) lassociative f(f(a,b),c) ==> f(b,f(a,c)) evenfun f(-g) ==> f(g) oddfun f(-g) ==> -f(g) nary f(f(a,b),f(c,d)) => f(a,b, c,d) In the case of linear, the first argument is used if f has two or more arguments. Thus the noun forms of limit, sum, and integrate are linear in their first arguments, with respect to their second arguments. That is, the definition of "constant" means "free of the second argument." Some of these declarations are not used directly in the simplifier as we have delimited it here, but because of the arbitrarily extended boundaries of the simplifier, can be considered within its realm. For example, the program which "simplifies" limits, can use information about increasing or decreasing functions, and the integration program can reduce certain problems considerably by determining that the integrand is an odd function integrated over a symmetric domain or that a parameter is not an integer. A rudimentary inference capability allows for some deductions, and is sometimes used by commands in an attempt to determine the sign of an expression. Additional declarations are available for objects which are not functions. Some of the uses are indicated below, where the indeterminate x has been declared to have the property indicated in the left-hand column. even cos(x*%pi) ==> 1 odd cos(x*%pi) ==> 0 integer cos((x+1/2)*%pi) ==> 0 noninteger used by integration rational irrational real imaginary constant linearfunction(x*y) = => x*linearfunction(y) complex scalar used by matrix manipulation The question arises: given all the possible functional simplifications described in these tables, how much of the simplifier needs to be hard-wired? It is clear that some of the reliance on switches would be difficult to consider within the framework of such declarations. One possibility would be to allow declarations to be conditional, depending on switch settings. A major question of efficiency emerges in any system which is interpretive or rule directed. Attempts to compile rule-sets into functions have appeared at various times. (See [Jenks, 76] for what is probably the best description.) We remain skeptical about efficiency compared to conventional programs, both in data structure and program structure. Recently SCRATCHPAD seems to have conceded this point [Jenks, 79], and REDUCE has for some time permitted both types of program construction: rule transformations via general pattern matches and a program mode. (see for example, [Hearn, 73] and [Hearn, 76]). We would like to see progress toward a more ambitious goal of "automatic programming" of algebraic manipulation programs. This would entail a combination of mathematical properties of the objects to be handled, and programming and data-structure expertise. Current algebra systems are most notable for their syntactic features and particular expertise in certain mathematical prob- lems. These do not typically include algorithm selection or data-structure design. An exploration of just how much of a simplifier can be constructed out of a skeleton and declarations is worth embarking on. Clearly REDUCE (see, for example, [Hearn, 73], and more recently [Hearn, 76]) has attempted to provide such a facility, but without the elaboration of as many built-in properties (linearity being one which REDUCE does include). The consequent reliance on a fairly general pattern matcher in REDUCE for so much of the simplification process doubtless exacts a penalty in speed. 6.2. The TELLSIMP constructions The objective of this section is not to provide a tutorial in how to use the two commands TELLSIMP and TELLSIMPAFTER, but in how their use affects the behavior of the simplifier. As has been indicated earlier, most operators in MACSYMA have a built-in simplification program, indicated by the OPERATOR property of the operator-name. A newly introduced operator has no OPERATOR property. Thus by uttering F(X); the user introduces the operator "SF". The TELLSIMP and TELLSIM- PAFTER commands allow the user to insert a simplifier program on the property list of the atom \$F where SIMPLIFY will use it. This fits in to the usual simplifier procedures. If an operator already has a simplifier, say "oldsimp-\$F", and then TELLSIMP(F(), ) is executed, a new program replaces the old, having the following general outline: newsimp-\$F(args): = if new matches then return (simplify( )) else return(oldsimp-\$F(args)); Note that this can be recursively redone for an "evennewersimp\$F" ad infinitum and also that the invocation of "simplify" can cause "newsimp-\$F" to be invoked again. (Sometimes leading to an infinitely recursive scheme, if the replacement still consists of an instance of the same pattern.) By maintaining auxiliary information about the order of TELLSIMP commands, the simplifier can be restored to earlier pristine states. The TELLSIMPAFTER command is subtlely different: the new program replacing the old follows the outline: newsimp-\$F(args): = temp: oldsimp-\$F(args); if temp still has leading operator "F" and temp's args match then return(simplify*( ) ); Where "simplify*" is similar to the ordinary simplification program, but has this TELLSIMPAFTER program on "F" disabled This last restriction turns out to be fairly natural. In effect TELLSIMPAFTER(F(), replacementi) means, "If all previous efforts to simplify F(args) have not removed the F as principal operator, see if matches args. If no match, leave it alone, otherwise return ." The sophisticated user of MACSYMA who wishes to see exact programs for these advice-taking systems should study the easily-accessed Lisp programs produced by these commands. A design criterion for the pattern matching programs originally written by Fateman was that the patterns should actually be compilable and executable Lisp. An interpretive version, which has a speed and space advantage if in fact the pattern program is interpreted rather than compiled, is under construction. (note: the rules are currently interpreted. RJF 2016) 6.3. Other semantic alterations to the system The user is faced with a complex set of tools for specifying knowledge in MACSYMA. In addition to simplification, there is a process of evaluation, drawing upon function definitions and substitution of values for variables. In this section we illustrate some of these alternatives briefly, so as to distinguish them from the objectives of the simplifier modification techniques described above. For example, F may be defined as a function, e.g. F(X):=IF X=0 THEN 1 ELSE 0\$ (this may not have desired effect: F('R) evaluates to 0 since R is not syntactically identical to 0) or F(X):=IF EQUAL(X,0) THEN 1 ELSE 0\$ (this may not be desired: F('R) evaluates to an error condition: "MACSYMA was unable to evaluate the predicate EQUAL(R,0)") F may be left undefined, but with certain properties, for example, derivatives, or simplification rules. TELLSIMP(F(0), i)\$ causes F(0) to be replaced by 1, anywhere it occurs, but leaves F('R) untouched. This last situation is very similar to interspersing SUBST(1,F(0),lastexpression) frequently during the course of a calculation. A more subtle situation is replacing any expression F() by 0. This can be programmed by MATCHDECLARE(NZ,NONZERO)\$ NONZERO(X):=IS(X#0)\$ TELLSIMP(F(NZ),0)\$ which cannot be easily simulated by calls to SUBST. Without dwelling on the details here, we merely wish to indicate that in MACSYMA the evaluator is another layer of interface which attempts to intuit the users' needs, and which coexists, sometimes uncomfortably, with the simplifier. The modeling of the evaluation process, which in some algebraic manipulation systems is equated with simplification (see [Hearn, 78]), represents another challenging area for study. In MACSYMA, evaluation is more directly related to programming language semantics than algebraic transformations. We would like to see it move even more in that direction, and away from simplification. 7. Other Simplifiers One of the principal suggestions we wish to see adopted is a move to strengthen simplification programs by taking advantage of canonical simplifiers, and other special purpose programs, which in their contexts, can be relatively sure of achieving the desired affect. We here do no more than list the sections which we hope can be expanded upon in a future version of this paper, but whose contents can in fact be derived from previously published manuals or papers. The power of these programs represents the strongest argument for continuing to build upon the structure of MACSYMA, rather than starting ab initio in writing a new system attempting to do everything one more time around, right. {This consists of the titles of subsections that might appropriately be added to this paper. Expanded version not written as of 2016. RJF} 7.1. Canonical Rational Expressions 7.2. RATSIMP and RADCAN 7.3. Simplification of Sums 7.4. Taylor Series 7.5. Trigonometric expressions 7.5.1. Poisson Series 7.5.2. TRIGEXPAND 7.5.3. TRIGREDUCE 7.5.4. TRIGSIMP 8. Summary and Conclusions In this presentation we have suggested that a good algebraic simplification program be structured to allow for disciplined growth. Restructuring of "working" code may very well be desirable. More powerful simplification routines may be most easily constructed as canonical simplifiers for particular classes of expressions, whose applications are controlled, perhaps, by rule-directed context switching. The tools are at hand for storing "contexts of simplification," if we can resolve an adequate model for manipulation of these contexts. We hope to see more progress in "automatic programming" as an aid to the construction of simplification programs and related data structures. Regardless of the techniques used for achieving this goal, it is necessary that the user of an algebraic manipulation system be able to comprehend and to some extent alter, the default transformations of that system. This is an important argument for keeping things simple. For the present, the MACSYMA simplifier works for all of the people some of the time, and some of the people, all of the time. While this crude characterization is not likely to change, we can provide much better service to those not immediately satisfied by providing better-documented and more consistent facilities in a framework which reflects a more systematic structure. To be successful, this structure must reflect the underlying mathematics and the algorithmic nature of the simplification process. The current program makes good use of a operator-operand tree model of algebraic expressions, which however, fails to make use of operator models [Doohovskoy, 1977]. It makes possible the use of canonical form simplifiers, but does not take full advantage of them in an entirely systematic way. While it provides schemes for altering the default behavior of the program via TELLSIMP, DECLAREs, and user-settable flags, it is quite difficult to model the effects of these changes in the large. Overall, we consider the MACSYMA simplifier an impressive program, in spite of our criticisms. Working on and with it has given many of us insights into the challenges of simplification. It has helped us to redefine our objectives in view of many user requirements. We hope that we have also started to refine our techniques for constructing such programs in the future. 9. References [Doohovskoy, 77] Doohovskoy, A. "Varieties of operator manipulation," Proc. of the 1977 MACSYMA Users' Conf. NASA CP-2012, July, 1977, (473-490). [Fenichel, 68] R. Fenichel, "An On-line System for Algebraic Manipulation," doc- toral dissertation, Harvard University, July, 1968, also Report MAC-TR-35, Project MAC, M.I.T., available from the Clearinghouse, document AD-857-282. [Hearn, 73] A. C. Hearn, Reduce 2 User's Manual University of Utah Computa- tional Physics Group Report No. UCP-19, March 1973. [Hearn, 78] A. C. Hearn, "A new REDUCE model for algebraic simplification," Proc. 1976 ACM Symposium on Symbolic cznd Algebraic Computation, August, 1976, (46-50). [Jenks. 76] R. D. Jenks, "A pattern compiler," Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, August, 1978, (60-65). [Jenks, 79] R. D. Jenks, "SCRATCHPAD/380: Reflections on a language design," SICSAM Bulletin 13, no. 1, Feb., 1979, (18-26). [Korsvold, 65] Knut Korsvold, "On-Line Algebraic Simplify Program," Stanford A.I. Project Memo 37, Nov. 1965, 30 p. [Moses, 71] Joel Moses, "Algebraic simplification, a guide for the perplexed," Comm. A.C.M. 14, no. 8, Aug., 1971, (527-538). [Tobey, 65] R. G. Tobey, R. J. Bobrow, and S. N. Ziles, "Automatic Simplification in Formac," Proc. AFIPS 1965 Fall Joint Comput. Conf., (1965) (37-52). {1. Work reported herein was supported in part by the U. S. Department of Energy. Contract DE-ATO3-76SF00034, Project Agreement DE-ASO3-79ER10358, and the National Science Fowi- dation under Grant No. UCS 7807291 and by the Laboratory for Computer Science at ML?.. currently supported by the United States Department of Energy under contract E(11-1)- 3070. and the National Aeronautics and Space Administration under grant NSG 1323.}