Macsyma Users' Conference 1979
MACSYMA's General Simplifier: Philosophy and
Operation
Richard J. Fateman
Computer Science Division
Electrical Engineering and Computer Sciences Dept.
University of California
Berkeley California
1. Introduction
Ideally the transformations performed by MACSYMA's simplification
program on algebraic expressions correspond to those simplifications
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, 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. 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 some 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 routine,
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. {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, 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 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 8.
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
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 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" &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) 1 2)
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 1: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)
`INTECRATE(AIB,C,D) ((%INTEGRATE) $A $B $C $D)
BLOCK([L1,L2], S1,S2e) ((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(ab) ==> f(a)f(b)
outative f(3a) ==> 3*f(a)
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 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 problems. 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
"$F". The TELLSIMP and TELLSIMPAFTER 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" 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 subtly 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.
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 X0 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 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 "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, 88] R. Fenichel, "An On-line System for Algebraic
Manipulation," doctoral 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
Computational 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 and 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).
Footnotes.
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 Foundation under Grant No. UCS
7807291 and by the Laboratory for Computer Science at M.I.T.,
currently supported by the United States Department of Energy under
contract E(11-1)-a3070. and the National Aeronautics and Space
Administration under grant NSG 1323.
Thanks to John Gerard Malecki for correcting
the OCR generated from the original manuscript. There has been no
attempt to change the contents from 1979 to reflect changes in
the simplifier code. (RJF 10/2001)**