MACSYMA'S General Simplifier Philosophy and
Operation
Richard J. Fateman
Computer Science Division
Electrical Engineering and Computer Science. Dept.
University of California
Berkeley California
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 neces-
sary 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, 1979. not clear this would be different in 2001. 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}
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 deal-
ing 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
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.
Macsyma Users' Conference 1979
564
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 expres-
sions 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 manipula-
tion of algebraic expressions in the "general" tree-like form used for most of
MACSYMA. Several special purpose simplifiers, such as those for rational func-
tions, 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 pos-
sible, 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 run-
ning 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 undecid-
able".
Many programs are written in such a fashion as to be resistant to mis-
behavior 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 origi-
nally 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
565
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 gen-
erated at a low level are not usually able to reflect the global causes Thus "divi-
sion 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 Alge-
braic Simplify Program" written by Knut Korsvold [Korsvold, 85] 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 simpli-
fying 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.
{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-effLcient data structure and/or provide the fastest type of compu-
tation.
566
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, SIMPLIFY, 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
partiy 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 indi-
cates 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 users' name space from the
Lisp-programmers' name space. The `?` prefix is an attempt to thwart this
separation. The separation is not effective in any case since using a MACSYMA-
coded package written by someone else (or yourself!) again provides a potential
567
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 provides a useful alternative
is not entirely clear. Current Macsyma implementations certainly try to
make use of the package system in CL, but also seem to have retained the
single-character prefix tradition. RJF}
MACSYMA Syntax and Internal Representation
Input String Parser Output
A
?A A
"A"
`A ((MQUOTE) SA)
X+Y ((MPLUS) SX SY)
X-Y ((MPLUS) $X ((MMINUS) SY)
X*Y ((MTIMES) Sx SY)
A(X) ((SA) $X)
A[1,2] (($AARRAY) 12)
A[1,2](X) ((MQAPPLY) (($AARR.AY) 12) $X)
SIN(X) ((%SIN) $X)
X/Y ((MQUOTIENT) SX SY)
X.Y ((MNCTIMES) SX SY)
X"2 or X2 ((MEXPT) $X 2)
X-"'2 ((MNCEXPT) $X 2)
[A,B,C] ((MLIST) SA SB SC)
(A,B,C) ((DOLIST) $A SB SC)
IF A THEN B ((MCOND) SA SB T $FALSE)
IF A THEN B ELSE C ((MCOND) SA SB T SC)
FOR I:A THRU B STEP C
UNLESS Q DO F(I) ((MDO) SI SA SC NIL SB SQ ((SF) $1))
FOR 1:A NEXT N
UNLESS Q DO F(I) ((MDO) $1 SA NiL SN NIL SQ ((SF) SI))
FORIINL
DO F(I) ((MDOIN) $1 SL NIL NIL NIL NIL ((SF) SI))
DIFF(Y,X) ((SDIFF) SY $X 1)
DIFF(Y,X,2,Z,1) (($DIFF) SY $X 2 $Z 1)
`DIFF(Y.X) ((%DERIVATIVE) SY SX 1)
INTEGRATE(A,B,C,D) ((SINTEGRATE) SA SB SC SD)
`INTECRATE(AIB,C,D) ((%INTEGRATE) SA SB SC SD)
BLOCK([L1,L2], Si,se) ((MPROG) ((MUST) $L1 $L2) 5Si $S2)
BLOCK(S1,S2) ((MPROG) ((MLIST)) $S1 $S2)
NOT A ((MNOT) SA)
A OR B ((MOR) SA SB)
AAND B ((MAND) SA SB)
A=B ((MEQUAL) SA SB)
568
MACSYMA Syntax and Internal Representation (continued)
Input String Parser Output
A>B ((MGREATERP) SA SB)
A>=B ((MGEQP) SA SB)
A** f(a)+f(b)
antisymmetric f(a,b)+f(b, a) ==> 0
commutative f(a,b)-f(b,a) > 0
multiplicative f(ab) ==> f(a)f(b)
outative f(3a) > 3*f(pj~)
linear f(a+3b) ==> 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 argu-
ments. 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 func-
tions, 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 capabil-
ity 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 eos(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
578
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 combina-
tion 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 (linear-
ity 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 utter-
ing 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 SF 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" cxd
infinilum 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 com-
mands, the simplifier can be restored to earlier pristine states.
The TELLSIMPAFTER command is subtiely 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" disablecL This last restriction turns out to be
fairly natural. In efTe ct 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 pro-
grams 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 com-
piled, is under construction.
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):tIF X0 THEN 1 ELSE 0$
(this may not have desired effect: F('R) evaluates to 0 since R is not syntacti-
cally identical to 0) or
580
F(X):zlF 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 replac-
ing any expression F() by 0. This can be programmed by
MATCHDECLARE(NZ.NONZERO)$
NONZERO(X): tlS(X#0)$
TELLSIMP(F(NZ) ,o)$
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 modelling 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.
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. TRJGEXPAND
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 "work-
ing" 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 con-
text 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 impor-
tant argument for keeping things simple.
For the present, the MACSYM.A simplifier works for all of the people some of
the time, and some of the people, all of the time. While this crude characteriza-
tion 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 suc-
cessful, this structure must reflect the underlying mathematics and the algo-
rithmic 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
582
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, 88] 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, 85] Knut Korsvold, "On-Line Algebraic Simplify Program," Stanford
A.I. Project Memo 37, Nov. 1985, 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).
**