.EQ
delim @@
.EN
.tl
Symbolic and Algebraic Computing
.pp
This paper describes the field of Symbolic and Algebraic computing
with a view toward what current
algebraic manipulation systems can do, and what,
in principle, they can be expected to do in the future. We
provide a framework for discussing concepts and facilities, rather
than a completely detailed comparative study of various systems.
.pp
.NH
Understanding the Past: Guidelines for Comparing Systems
.pp
Periodically, existing systems have been surveyed, generally
comparing computing times for solving specific problems.
Some comparisons have been
made on the presence or absence of specific
features or bugs. While these are useful, they do not exhaust the options.
.PP
What are the options for comparing systems?
[Demonstrating applications]
Applications must make sense to the reader.
Since the applications are drawn from rather distinct disciplines,
most, (sometimes all), illustrations are unappealing to any given person.
[Chauvinism]
Authors who have worked on systems find it natural to use their own
system as a touch-stone to study issues.
Which systems to include or exclude in such comparisons are subject
to debate.
If comparative timings are provided, they may be on
different computers, and therefore hard to evaluate.
[Generality vs. Specificity]
Some systems are claimed to be "general purpose" by which
is meant they have embraced every bit of program that has come
their way, and resemble encyclopedias. (Macsyma, SMP)
Other systems are
moderately general in nature in that they are intended for use by people other
than their designers, and can be used, fairly directly, to state and
solve not only the problems initially of interest to the designers,
but a variety of other problems.
Sometimes the designers have no particular computation in mind, but
implement a set of techniques believed to
be useful (e.g. rational function arithmetic). Alternatively, the
system design may be justified by mathematical or data
abstraction, programming language experimentation, hardware
exploitation, or some other application.
Some "special purpose" systems
are useful for solving only a single
problem, although perhaps a very important one.
Nevertheless, most systems are sufficiently general so that, subject
only to the cleverness of the programmer and the amount of money
available to devote to time and equipment, they can all solve the
same class of problems. In theory, the same class can be solved
by masterful programming in Fortran or some other mundane language.
Thus the issue of what a system can do, and how well, is rather muddled
when special purpose systems are compared to more generally directed
ones.
[Theory of computation]
There are important theoretical results which have been
applied to problems in algebraic manipulation. Generally, however,
the most
prominently published items of apparent relevance to this
field, are relevant to asymptotically large problems, or recently,
large numbers of communicating computing systems .
Many of these results are
irrelevant to computation on finite machines or collections of them,
restricted to running in practical times.
There is painstaking work needed to separate the
wheat from the chaff. In any case,
surveys of such results are thus disappointing
from a practical standpoint (Collins AMM, AHU).
.NH
The Future
.pp
This survey is intended to identify various types of activities
that can be computer-automated, and indicate the fields of endeavor
which are related to these activities.
.pp
Our principle goal is to clarify the relationship of
mathematical and computing notions.
Sometimes it is useful to combine such concepts, since they are
often close enough that the "abuse of notation" is less confusing
that the formality which would otherwise be needed.
Rarely, however, are the abuses so flagrant and inconsistent
as in a system (e.g.
.Ma )
.(f
\** We use "Macsyma 81" to fix a point in time, since the
system has undergone almost continual evolution since 1968. It might
be appropriate to call it Macsyma 77, since the last major revision
of the reference manual dates to that year. While some contend that as
far as the basic system goes, the years from 77 to 81 are characterized
by Brownian motion, there are a few clever algorithm improvements
that were introduced. They would not ordinarily be visible to a user,
however.
.)f
which has had some 15 years of hackery.
.pp
.sh 1 "Basic Data Types"
.pp
integers, bignums, rationals, floats, polynomials, Expressions
(log, exp, cos, sin), forms and operators (integ. diff)
aggregations (matrices, arrays, tables), programs, functions,
program-objects, evaluation environments (contexts), files, (directories?),
graphs.
.sh 1 "Supported Activities"
We are going to describe five types of activity provided by
algebraic manipulation systems such as
.Ma .
They are \fB Identity Transformations, Mathematical-Analytic,
Substitutions,
Approximations, \fP and \fBOther Manipulations.\fP
In a sufficiently simple system, we could make clear distinctions
for each of these classes. A system in which expressions are the
sole object would be much more straightforward, but inconvenient.
The situation in
.Ma
has been obscured in various ways because of engineering decisions*
.(f
\** or occasionally indecisions
.)f
which are intended
to make the human interface simpler (often at the expense of
uniformity). These are, for good or ill, abuses of notation.
.sh 2 "Identity Transformations"
.pp
This are commands which do not change the value of an expression, but
only its form. Simplification is supposed to be
an identity transformation, and most algebra systems use some level of
simplication as a standard adjunct to every other operation.
.pp
Commands in
.Ma
which fit in this category include
.(b
factor expand
radcan ratsimp ratexpand rat
multthru
horner
powerseries
trigexpand trigreduce
partfrac
.)b
Some of these commands represent prompting to the
simplification algorithm: a suggestion as to how to make a
desirable identity transformation.
.pp
Because simplification in
.Ma
involves some controversial transformations, it
does fail upon occasion to be an identity transformation.
Furthermore, by overloading the alleged identity transformations with extra
flags, strange things happen.
.eB
(c1) y: sqrt(x^2+2*x+1);
2
(d1) sqrt(x + 2 x + 1)
(c2) eq: y = radcan(y);
2
(d2) sqrt(x + 2 x + 1) = x + 1
(c3) is (radcan(eq));
(d3) true
(c4) subst(-4,x,eq);
(d4) 3 = - 3
.eE
Here \fIradcan\fP made the wrong assumption about the sign of @ x+1@.
A stranger example is in arithmetic in GF(7):
.eB
(c5) modulus:7$
(c6) sqt5 : sqrt(5);
(d6) sqrt(2) %i
(c7) sqt5^2;
(d7) - 2
(c8) ratsimp(sqt5);
(d8) %i
.eE
Now what is this "%i" business? (The symbol %i is used to represent
@sqrt -1 @. We can explain how it got there:
@ 5 mod 7 @ using
.Ma 's
balanced notation is reduced to -2. @sqrt -2 @ is @ sqrt 2 i @ according
to some other simplification notion. Some program though we were
in the complex number domain.
.pp
To continue the example:
.eB
(c9) sqt5^2;
(d9) - 2
.eE
This makes sense, in GF(7), of course, but look at the next
line!
.eB
(c10) ratsimp(sqt5);
(d10) %i
.eE
What happened here was that \fIratsimp\fP saw d11 as
@2 sup 1/2 i@ and first computed @1/2 mod 7 = -3@. Then @2 sup -3 = 1/8 == 1/1 mod 7@
.PP
If we are to retain the notion that we are doing mathematics, we must
either limit the domain of discourse, or what would be a
.i much
preferable solution,
.i understand
the domains of discourse, so that identity transformations can
be asserted. Thus the \fIradcan\fP example has a side condition that
@x+1~>=~0@.
The use of square-roots in a finite field is a bit of nonsense:
some elements have two roots, some none, and 0 has one.
.pp
There is no simple solution to this problem: it is rampant throughout
.Ma .
.sh 2 Mathematical-Analytic
.pp
Among these activities we include differentiation, integration,
calculation of limits, and in some cases, the transformations of
.Ma 's
built-in facilities such as \fIlog\fP, etc.
in this category, diff(x^2,x), but not diff(f(x),x);
diff(f(x),x,3) but not diff(f(x),x,n) {fractional derivatives}.
log(x^2) -> 2*log(x) (what if x is -3?)
Impose analytic interpretation?
.sh 2 "Substitution"
.pp
The simplest substitution is the association of values with
indeterminates by the subst command: subst(a,b,c) means
substitute a for b in c.
.Ex
(give simple example)
.pp
There are a few subtleties, for example
when c is an expression which contains free and bound instances of b:
substitute @a@ for @x@ in @integrate { f ( x ) d x } from 0 to x @ has
three possibilities:
.EQ (1)
integrate {f ( x ) d x } from 0 to a
.EN
.EQ (2)
integrate { f ( a ) d a} from 0 to a
.EN
.lp
This may seem a perverse alternative, but must be considered:
.EQ (3)
integrate {f ( a ) d a } from 0 to x
.EN
.pp
We would like to say that (1) is the reasonable version since the
@x@ in the integral is merely a placeholder, and changing it to @a@
cannot change anything. Imposing this interpretation,
we are imposing an analytic semantics that is sometimes at odds
with a manipulative desire. The second interpretation
and possibly even the third may be desirable:
.Ea
try to simplify
.EQ (4)
integrate {f ( a ) d a } from 0 to a ~~+~~ integrate { f ( x ) d x} from 0 to a ~~~->~~ 2 integrate {f ( a ) d a} from 0 to a
.EN
.Eb
.pp
Evaluation is another type of
substitution mechanism which is very popular. Unfortunately the
semantics for evaluation in terms of
substitution are clear only in simple cases.
Discuss pattern/replacement rules.
.sh 2 Approximation
.pp
Taylor series, ratweight, modular arithmetic, numeric computation.
.sh 1
Other manipulation
.pp
.sh 2
Programming
.pp
In many ways, the programming environment in an AM system is comparable
to that of the usual programming languages: iteration, procedures,
variables, etc. The primary difficulty comes in specifying the meaning
of constructions which can be overloaded to accomodate what appears,
on first blush, to be extensions of usual interpretations.
.sh 1 "Conditional Statements"
.pp
Consider the usual
\fBif \fIB \fBthen \fIC1 \fBelse \fIC2 \fR construction.
The usual programming language insists that the value of \fIB \fPbe
of type Boolean, and thus can assume only the values
.i true
or
.i false.
.pp
A language like Lisp, where the Boolean value
.i true
is represented by any non-\fInil \fP object, presents only a minor
extension to a type-free interpretation of the conditional.
.pp
.Ma ,
on the other hand, has changed the notion of \fBif \fP to depend upon
the nature of the test expression \fIB. \fP
There are (at least) three additional interpretations for
the \fBif \fIB \fBthen \fIC1 \fBelse \fIC2 \fR construction.
.ip
If @B@ cannot be evaluated to a Boolean type:
1. The conditional can cause a exception. ("
.Ma
cannot evaluate the predicate @B@").
2. The conditional can proceed to the \fBelse\fP alternative.
(The choice between 1 and 2 is controlled by a global "flag" in
.Ma .)
3. The conditional can be returned "unevaluated" for later
re-evaluation. This is essentially providing a "lazy evaluation"
mechanism or what is sometimes called "call by need". [ref: Henderson, Morris,
also Wand].
This might
be considered useful in dealing with definitions such as
abs(x):=\fBif \fIx<0 \fBthen \fI-x \fBelse \fIx \fR, which could
then be used in evaluating
.EQ
integrate {abs(x) dx} from 0 to a
.EN
where the pre-condition @ a > 0 @ could be combined with the
definition of abs "returned" from abs(x) to determine that
for this environment, @ abs(x) = x @.
.pp
It is also possible for the conditional to be simplified. For example,
consider
\fBif @ a sup 2 > a @ \fBthen \fIC1 \fBelse \fIC2 \fR,
which could be reduced to
\fBif @ (a < 0) ~bold or ~(a > 1)@ \fBthen \fIC1 \fBelse \fIC2 \fR.
If @C1@ or @C2@ themselves make assumptions about the values of @a@,
further reductions in the conditional may be possible. Examples exist
in which array-referencing arithmetic can be simplified in programs for
matrix calculations by logical simplifications.
.pp
Another area for puzzling over is that questions such as is (@i > 0@)?
can be stated easily, although not resolved. Is (@ sin ( x ) > 1)@?
This depends on your mind set, and the possible values of @x@. For
real values of @x@, @sin (x) <= 1@. For some pure imaginary values
of @x@, @sin ( x ) > 1@. For some complex values, the question is
meaningless.
.pp
Yet another is the question of equality. As a mathematical question,
there is no difficulty in asking if two expressions are equal,
yet from an algorithmic point of view, we can say only that two
expressions are equal if they are identical in form, or can be
reduced to being identical in form, or perhaps their difference
(assuming that "difference" has meaning in the structure under
consideration), can be reduced to zero.
Typically the answer is that two expressions are equal (=) if
they are character-for-character identical. Thus
@ integrate a da =! integrate b db @.
.sh 2 Environments
.pp
We have already broached the subject of environments indirectly,
several times. For example, in
.Ma
it is possible to set a global flag which determines the "modulus"
of arithmetic.
(passing, storing, invoking , environments)
.sh 2
storage/retrieval
.pp
In most programming languages, files are treated as a qualitatively
different object from other named entities. Alterations are
made via "write" commands, and the sequence of values which
are stored accessed via "read" commands. Except for
making use of operating system
files for paging of data and programs implicitly,
.Ma ,
and other AM systems are generally similar.
.Ma
makes use of files for text input and output (This allows
the preparation of
programs by conventional text editors,
and the use of output for printing, examination, inclusion in
on-line text, etc.).
.Ma
makes use of named files for storage and retrieval of "internal form"
data and programs (in load-modules or interpreter-ready form). These
are used in libraries, check-points for saving and restoring the
total environment during long computer runs, and for saving, for
later recombination, partial environments from several runs.
A significant problem is encountered in storing Lisp data on files,
if the original data had shared substructures. The data as read
back in is devoid of that sharing, and hence may be far
larger than originally.
(defun fool(n)(cond ((equal n 0)(cons 0 0))
(t (cons (setq n (fool (sub1 n)n)) n))))
Because of shared substructure,
(fool n) when printed
will appear to have O(@2 sup n @) cells instead of O(@n@). This example
is unfortunately not entirely artificial.
.pp
Some system designers, anticipating the large size of expressions,
.(f
\** especially for problems in celestial mechanics. [Rom, Deprit, Schoonschip])
.)f
arranged data and algorithms for fast and efficient
use of objects stored on random-access disk systems.
This has enabled such systems to solve certain problems in times
which are orders of
magnitude shorter than systems which rely on the good will and omniscience
of paging and scheduling algorithms in operating systems to
provide access to the right data. In fact, the speed obtained by
such encodings of data and algorithms, make certain calculations feasible.