%LaTex2e
%%% \KLUWER STYLE enabled.
\documentclass{edbk}
\usepackage{edbkps}
\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{2}
%\documentclass{article}
%
%%%%\kluwerbib THIS DOESNT WORK FOR ME
\let\footnote\savefootnote
\let\footnotetext\savefootnotetext
\let\footnoterule\savefootnoterule
\normallatexbib
\begin{document}
\articletitle{Problem Solving Environments and Symbolic Computing}
\author{Richard J. Fateman}
\affil{University of California, Berkeley}
\email{fateman@cs.berkeley.edu}
\chaptitlerunninghead{Symbolic Computing}
%\date{}
%\maketitle
%\tableofcontents
%\newpage
\begin{abstract}
What role should be played by symbolic mathematical computation
facilities in scientific and engineering ``problem solving
environments''? Drawing upon standard facilities
such as numerical and graphical libraries,
symbolic computation should
be useful for: %\begin{itemize}
%\item
The creation and manipulation of mathematical models;
%\item
The production of custom optimized numerical software;
%\item
The solution of delicate classes of mathematical problems
that require handling beyond that available in traditional
machine-supported floating-point computation.
%\end{itemize}
Symbolic representation and manipulation can potentially play a
central organizing role in PSEs since their more general object
representation allows a program to deal with a wider range
of computational issues.
In particular
Numerical, graphical, and other processing can be viewed as special
cases of symbolic manipulation with interactive symbolic
computing providing both an organizing backbone and the communication
``glue'' among otherwise dissimilar components.
{\bf This is an extended abstract. A full-length version can be found
at {\verb| www.cs.berkeley.edu/~fateman/papers/pse-kluwer.pdf|. }}
\end{abstract}
\begin{keywords}
PSE, ``computer algebra'', CAS, optimization, ``symbolic computation'' Mathematica, Maple, Macsyma, Axiom,
glue
\end{keywords}
\section{Introduction}
%snip
{ The search for tools to make computers easier to use is as old as
computers themselves. In the few years following the release of Algol
60 and Fortran, it was thought that the ready availability
of compilers for such high-level languages would eliminate the
need for professional programmers --- instead, all educated persons,
and certainly all scientists, would be able to
write programs whenever needed.
While some aspects of programming have been automated, deriving
programs from specifications or models remains a difficult step in
computational sciences. Furthermore, as computers have gotten
substantially more complicated it is more difficult to get the fastest
performance from these systems. Advanced computer programs now depend
for their efficiency not only on clever algorithms, but also on
constraining patterns of memory access. The needs for advanced error
analysis has also grown as more ambitious computations on faster
computers combine ever-longer sequences of computations, potentially
accumulating and propagating more computational error. The
mathematical models used in scientific computing have also become far
more sophisticated.
\bigskip
Symbolic computation tools (including especially computer algebra systems)
are now generally recognized as providing useful components in many
scientific computing environments.
}
\subsection{Symbolic vs. Numeric}
{What makes a symbolic computing system distinct from a non-symbolic
(or numeric) one?
We can give one general characterization:
the questions one asks and the resulting answers one expects,
are irregular in some way. That is, their ``complexity'' may be
larger\footnote{
Although some numeric programs deal with compound data objects,
the complexity of the results
are rarely more structured than 2-dimensional arrays of floating-point
numbers, or perhaps character strings. The sizes of the results
are typically fixed, or limited by some arbitrary maximum
array-size in Fortran COMMON allocated at ``compile-time''.)}
and their sizes
may be unpredictable. For example, if one somehow
asks a numeric program to
``solve for $x$ in the equation $\sin(x)=0$'' it is plausible that the answer
will be some 32-bit quantity that we could print
as $0.0$. There is generally no way for such a program to give
an answer ``$\{n \pi ~|~ {\rm integer}(n)\}$''. A program that
{\em could} provide this more elaborate symbolic, non-numeric, parametric
answer dominates the merely numerical from a mathematical perspective.
The single numerical answer might be a suitable result for some purposes:
it is simple, but it is a compromise.
If the problem-solving
environment requires computing that includes
asking and answering questions about sets,
functions, expressions (polynomials, algebraic expressions), geometric
domains, derivations, theorems, or proofs, then it is
plausible that the tools in a symbolic computing
system will be of some use.
%snip of section 1.2, a history of CAS
\section{Symbolic Mathematics Components}
Computer Algebra Systems (CAS) have had a small but faithful following
through the last several decades, but it was not until the late 1980's
that this software technology made a major entrance into the consumer
and education market. It was pushed by cheap memory, fast personal
computers and better user interfaces, as well as the appearance of
newly engineered programs.
Now programs like Mathematica, Maple, Macsyma, Derive, Reduce, Axiom, MuPad,
and Theorist are fairly well known.
Each addresses at some level symbolic, numerical, and
graphical computing.
Yet none of the commercial systems is designed to provide components
that can be {\em easily broken off and re-used} ---called by, for example,
``Fortran'' programs. (but then
since Fortran deals with numbers or arrays
of numbers, there is no {\em natural} way for
a Fortran program to accept an answer that is an expression!)
Even if one cannot easily break off modules, most CAS make an efforts to
enable a procedure to communicate in two directions
with other programs or processes. These existing tools generally
require a delicate hand, in spite of considerable effort expended
to try to support communication protocols and interconnections.
There have been examples, mostly in
research systems when investigators needed certain
separable components in the context of (for example) expert systems
dealing with physical reasoning, or qualitative analysis.
Our own experiences suggest that CAS whose host language is
Lisp can be re-cycled in fairly large modules to be used with
other Lisp programs. Lisp provides
a common base representation serving as
a lingua franca between programs running in the same system.
Another approach is to provide a relatively primitive interconnection
strategy amounting to the exchange of character streams: one
program prints out a question and the other answers it. This
this is clumsy and fragile\footnote{For example,
handling errors: streams, traps, messages, return-flags, etc.~is difficult.}.
It also makes it
difficult to solve significant problems whose size and complexity
make character-printing impractical.
The communication situation could be likened to two
mathematicians expert in different disciplines trying to solve a
problem requiring both of their expertises, but restricting them to
oral communication by telephone. They could try to
maintain a common image of a blackboard, but it would not be easy.
We will get back to the issue of interconnection when we discuss
symbolic math systems as ``glue''.
Let us assume we have overcome this issue of re-use, either
by teasing out components or
via input/output interfaces for separate command modules.
What components would we hope to get?
What capabilities might they have, in practical terms?
How do existing components fall short?
\subsection{Programs that manipulate programs}
The notion of symbolically manipulating programs
has a long history. In fact, the earliest uses of
the term ``symbolic programming'' referred to writing
code in assembly language (instead of binary!). We are used
to manipulation of programs by compilers, symbolic debuggers, and similar
programs. Language-oriented editors and
environments have become prominent in software engineering:
tools for human manipulation of what appears to
be a text form of the program, with some assistance in
keeping track of the details, by the computer. Usually another
coordinated model of the program is being maintained by the system
to assist in debugging, incremental compiling, formatting,
etc. In addition to
compiling programs,there are macro-expansion systems, and other tools like
cross-referencing, pretty-printing, tracing etc. These common tools
represent a basis that most programmers expect from any decent
programming environment.
By contrast with these mostly record-keeping tasks, we computers
can play a much more significant role in program manipulation.
Historically the Lisp
programming language has figured prominently here
because the data representations and the program
representations have been so close\footnote{Recently, Common Lisp has actually
modified this stand on duality by generally making a
distinction between a function and the lists of symbols (data) that
describe it.}.
For example, in an interesting and influential thesis project,
Warren Teitelman \cite{teitel} in 1966 described the use of
an interactive environment to assist in developing a high-level view of
the programming task itself. His PILOT system showed how the user
could ``advise'' arbitrary programs---generally without knowing their internal
structure at all --- to modify their behavior. The facility of catching
and modifying the input or output (or both) of functions can be
surprisingly powerful. While ADVISE is available in most Lisp systems,
it is unknown to most programmers in other languages.
%snip
In fact Teitelman
shows how he could have the program translate such English advice as
given above into
Lisp, by {\em advising the advise program}. He also
demonstrates that he could advise his program
to take advice in German as well!
We mention this to emphasize the generality that such
flexibility is possible and often
lost in the shuffle, when programmers attempt to constrain solutions
to ``pipe'' or ``bus'' architectures, or even traditionally
compiled languages.
The favorite paradigm for linking general
computer-algebra systems with specific
numerical solution methods is to try to define a
``class of problem'' that corresponds to a solution template. In this
template there are
``insertions'' with symbolic
expressions to be evaluated, perhaps derivatives or simplifications
or reformulations of expressions,
etc. We can point to work as early as the mid-1970s: ambitious efforts
using symbolic mathematics systems (e.g. M. Wirth \cite{wirth} who
used Macsyma to automate work in computational physics). This
paradigm is
periodically re-discovered, re-worked, applied to different
problem classes with different computer algebra systems \cite{lanam,gates,wang,dewar,
sofroniou,cook,akers}.
%snip
\subsubsection{Example: Preconditioning polynomials}
A well-known and useful example of program manipulation that most
programmers learn early in their education is the rearrangement of
the evaluation of a polynomial into Horner's rule. It seems
that handling this rearrangement with a program is like swatting a fly with
a cannon. Nevertheless, even polynomial evaluation has its
subtleties, and we will start with a somewhat real-life exercise
related to this.
Consider the
Fortran program segment from \cite{press} (p.~178)
computing an approximation to a Bessel function:
{\small \begin{verbatim}
...
DATA Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,Q9/0.39894228D0,-0.3988024D-1,
* -0.362018D-2,0.163801D-2,-0.1031555D-1,0.2282967D-1,
* -0.2895312D-1,0.1787654D-1,-0.420059D-2/
...
BESSI1=(EXP(AX)/SQRT(AX))*(Q1+Y*(Q2+Y*(Q3+Y*(Q4+
* Y*(Q5+Y*(Q6+Y*(Q7+Y*(Q8+Y*Q9))))))))
...
\end{verbatim}}
(In this case we know $|x|>3.75$, {\small\tt AX=ABS(X)} and {\small\tt Y=3.75/X})
Partly to show that Lisp, notorious for many parentheses,
need not be ugly, and partly to aid in further manipulation, we
can rewrite this as Lisp, abstracting the polynomial evaluation
operation, as:
{\small \begin{verbatim}
(setf
bessi1
(* (/ (exp ax) (sqrt ax))
(poly-eval y
(0.39894228d0 -0.3988024d-1 -0.362018d-2 0.163801d-2
-0.1031555d-1 0.2282967d-1 -0.2895312d-1 0.1787654d-1
-0.420059d-2))))
\end{verbatim}}
An objection might be that we have replaced an arithmetic expression
(fast), with a subroutine call, and how fast could that be?
Indeed, we can define {\small\tt poly-eval} as a program that expands
in-line, via symbolic computation, before compilation into
a {\em pre-conditioned} version of the above. That is we
replace {\small\tt (poly-eval ...)} with
{\small \begin{verbatim}
(let* ((z (+ (* (+ x -0.447420246891662d0) x)
0.5555574445841143d0))
(w (+ (* (+ x -2.180440363165497d0) z)
1.759291809106734d0)))
(* (+ (* x (+ (* x (+ (* w (+ -1.745986568814345d0 w z))
1.213871280862968d0))
9.4939615625424d0))
-94.9729157094598d0)
-0.00420059d0))
\end{verbatim}
}
The advantage of this particular reformulated version is that it uses fewer
multiplies (6 instead of 8). While it uses 9 additions, {\em at least
two of them can be done at the same time}. This kind of form generalizes
and saves more work for higher degree.
Computing coefficients in this form required the accurate solution of a cubic
equation, followed by some ``macro-expansion'' all of which is
accomplished at compile-time and stuffed away in the mathematical
subroutine library. Defining {\small\tt poly-eval} to do ``the right thing''
at compile time for any polynomial of any degree $n>1$ is feasible
in a symbolic mathematics environment using exact rational and
high-precision floating-point arithmetic, and also assuming the
programmer is willing to ``license'' suc a transformation
(in a term coined by my colleague W. Kahan).
Consider that the rare carefully-crafted
programs the coefficients and the arithmetic sequence is specified
so as to balance off
round-off error {\em but only if the sequence of operations is
not modified by ``optimization''}.
This is not the case here:
the coefficients were taken from a 1954 paper by E.E. Allen as
quoted by Abramowitz and Stegun \cite{abram}.
As long as we are working on polynomials, we should point out that
another possibility emerges: a simple source code template can be
inserted to carefully compute other items of interest. For example,
the derivative of the polynomial, or a rigorous bound on the error in
the evaluation or the derivative. Running such code typically doubles
the time to compute a polynomial.
In some cases if we know in advance the range of input,
the ``program manipulation program'' could provide a useful error
bound for evaluation of
a polynomial {\em BEFORE it is RUN}.
If, in this Bessel function evaluation context we know that $0\le x \le
3.75$, we can determine the maximum error in the
polynomial for {\em any} $x$ that region. We could in principle
extend this kind of reasoning to produce, in this symbolic programming
environment, a library routine with an {\em a prior}
error bound. (As it happens, the truncation error in this approximation far exceeds
the roundoff in this routine).
While the total automation of error analysis requires far more than
routine algebra, local application of rules-of-thumb and some
practical expertise in an arcane subject (error analysis) can be
provided in a PSE. We foresee one difficulty in optimizing: the
design objectives and limits are rarely specified formally. Is the
goal to write the fastest or most accurate or most robust possible
numerical program? Is the goal constrained to writing the program that
will run on the widest range of possible computer architectures while
giving exactly the same answers? These are open research areas.
Finally, we should comment that the original Fortran segment displayed
above shows constants given in double-precision syntax
The number of figures given is only about half that precision.
It would be delightful to have intelligent libraries that
could on command, reformulate their entries to take advantage
of full accuracy or other considerations by reference to the
original mathematical analysis.
Instead we see programmers copying, by proxy, not very
accurate code developed in 1954.
In a scheme for computing improved approximations on command
we might also see the elimination of other errors, such as
those caused by copying coefficients.
\subsubsection{Example: Generating perturbation expansions}
A common task for some computational scientists is the generation
(at considerable mental expense) of a formula to be inserted
into a Fortran or other program.
%add
A lengthly explanation and sample code-generation for
the solution to the Euler equation,
$E = u + e \sin(E)$
is discussed in the full version of this paper.
One consequence of the development is a need to rapidly
compute many sines and cosines at evenly-spaced intervals.
Here's how computer algebra can help:
{
Here we use a two-term recurrence which
for each additional sin and cos pair requires only two adds and two multiplies.
Using the facts that
\begin{eqnarray*}
{0.5\sin(a+d)/\sin(d)}& =& {0.5\sin(a-d)/\sin(d)} +\cos(a)\cr
\cos(a+2d)&=& \cos(a)-4\sin^2(d) {0.5\sin(a+d)/\sin(d)}\cr
\end{eqnarray*}
we can construct a very simple program
whose inner loop computes $s_n = 0.5 \sin(n u)/\sin(u)$.
First set $k_1=2\sin(u)$ and $k_2=k_1^2$, $s_0=0$, $s_1=1/2$, $c_0=1$, $c_1=\cos u$. Then for $i>1$:
\begin{eqnarray*}
s_i &:= &s_{i-2}+c_{i-1}\\
c_i &:= &c_{i-2} -k_2*s_{i-1}\\
\end{eqnarray*}
Then $\sin(n u)$ is $k_1*s_n$ and $\cos (n u)$ is simply $c_n$. (There is some accumulation of round-off; this can
be counteracted if necessary with minor additional effort.)
}
We have chosen these illustrations because they show that
\begin{enumerate}
\item Symbolic computing can be used to produce small
expressions, not just relatively large ones. Furthermore, the important
contribution is to
form {\em sequences of program statements involving clever optimization of
inner loops.}
\item Some relatively small expressions (just sin and cos)
may nevertheless be costly to compute when they
occur in inner loops; there are tools, far beyond what
compilers can do, to make this faster.
\item Having computed expressions symbolically, prematurely
converting them to Fortran (etc.) is generally a mistake unless
you are so carefully crafting the program that the Fortran code
is {\em exactly} what you mean: no more and no less.
\item As long as we are generating the code,
it is in some cases possible to produce
auxiliary program text related to the main computation.
For example, keeping track of accumulated roundoff is often
possible.
\item Other auxiliary information such as
typeset forms can be routinely produced for inclusion in papers such as this.
These expressions may be quite different from computationally
optimal ones.
\end{enumerate}
By contrast, CAS vendors illustrate their
systems' capability of producing
hugely-long expressions. It is usually a bad idea
to dump large expressions into a Fortran source file. Not only are
such expressions likely to suffer from instability, but their
size may strain
common-subexpression elimination ``optimizers'' or
exceed the input-buffer sizes or stack
sizes. Breaking expressions
into smaller ``prograsm statement'' pieces as we advocate
above is not difficult; even better may be the systematic
replacement of expressions by calculation schemes
such as {\small\tt poly-eval} discussed previously.
}
\bigskip
In the interests of brievity we omit entirely sections on
Derivatives and integrals,
Semi-symbolic solutions of differential equations,
Exact, high-precision, interval or other novel arithmetic,
Finite element analysis, geometry, and adaptive precision,
Licenses and code generation for special architectures.
Support for proofs, derivations, and Documentation and communication.
The interested reader
should consult the related WWW page for the full text.
\section{Symbolic Manipulation Systems as Glue}
In this section we spend some time discussing our favorite solutions
to interconnection problems.
Gallopoulos {\em et al} \cite{nsfpse} suggest that symbolic
manipulation systems already have some of the critical characteristics
of the glue for assembling a PSE but are not explicit in how this
might actually work. Let's be more specific about aspects of glue, as
well as help in providing organizing principles (a backbone). This
section is somewhat more nitty-gritty with respect to computing
technology.
The notion of glue as we have suggested it
has become associated with ``scripting languages,'' a popular description
for a collection of languages including
Perl, Tcl, Python, Basic, Rexx, Scheme (a dialect of lisp).
Rarely is a CAS mentioned
though if the glue is intended to connect programs speaking
mathematics, this suddenly becomes plausible.
CAS do not figure prominently partly because they
are ``large'' and partly because most people doing scripting are
generating e-commerce web pages, or controlling data-bases.
(Of course the CAS could also do these tasks, but mostly
without use of any
of their mathematical capabilities.)
In any case, the common currency of
scripting languages tends to be character strings as a
lowest-common-denominator of computer communication. The other
distinction for scripting languages is that they are interactive in
environment and execution. They provide a mechanism
to piece together a string which can then be evaluated as a program.
The simultaneous beauty and horror of this prospect may be what
makes scripting languages a hackers' playground.
When large-scale program development is part of the objective, the inability
of some scripting languages to be able to handle complicated objects
(in particular, large programs)
can be a critical deficiency. The long history
of effectively treating Lisp programs as data and Lisp data
as programs is a particular strength of this language that causes
it to rise to the top of the heap for scripting. The next two
sections give some details.
\subsection{Exchange of values}
We prefer that the glue be an interpretive language
with the capability of compiling routines, linking to routines written
in other languages, and (potentially, at least)
{\em sharing memory space with these routines}. We emphasize this
last characteristic because the notion of communicating via pipes
or remote-procedure call, while technically feasible and widely
used, is nevertheless relatively fragile.
Consider, by contrast, a typical Common Lisp implementation
with a ``foreign function'' interface. (Virtually all systems have this but
with minor syntactic differences).
On the workstation at which I am typing this paper, and using
Allegro Common Lisp,
if I have developed a Fortran-language package, or if my
program has generated one, in which there is a
{\small\tt double-precision function} subroutine FX taking one double-precision
argument, I can use it from Lisp by loading the object file (using
the command {\small\tt (load "filename.o")}).
and then declaring
{\small \begin{verbatim}
(ff:defforeign 'FX :language :fortran
:return-type :double-float :arguments '(double-float))
\end{verbatim}}
Although additional options are available to {\small\tt defforeign}, the
point we wish to make is that virtually everything that makes sense to
Fortran (or C) can be passed across the boundary to Lisp, and thus there is
no ``pinching off'' of data interchange as there
would be if everything had to be converted to character strings,
as in the UNIX operating system pipes convention. While this would open up
``non-numeric'' data, it would be quite inefficient for numeric data,
and quite unsuitable for structures with pointers.
Lisp provides tools to mimic structures in C:
({\small\tt def-c-type}) creates structures and accessors
for sub-fields of a C structure, whether
created in Lisp or C.
%It is possible for the ``foreign'' functions to
%violate integrity for Lisp data in ways that Lisp itself would be
%unlikely to attempt, like addressing past the end of an array, but
%such transgressions are possible in those languages already
%(especially C).
What else can be glued together? Certainly calls to produce web pages,
displays in window systems, and graphics routines. In fact, the
gluing and pasting has already been done and provided in
libraries.
%in most commercial and even
%academic Lisp systems, providing access to (depending on your host
%machine and operating system) X-window, Macintosh, Microsoft-Windows,
%and other interfaces.
We have hooked up Lisp to two arbitrary-precision floating-point
packages, LINPACK and MINPACK,
and others have interfaced Lisp to the Numerical Algorithms
Group (NAG) library, LAPACK and the library from {\em Numerical Recipes}.
Interfaces to SQL and database management systems have also
been constructed at Berkeley and apparently elsewhere.
\subsection{More arguments for Lisp}
The linkage of {\em Lisp-based} symbolic mathematics tools
such as Macsyma and Reduce into Lisp naturally is in a major sense ``free''
and doesn't require any glue at all. It is clear that
Fortran can't provide the glue. C or Java can only provide glue
indirectly: you must first write a glue system in them. (You could,
like most other people, write a Lisp system in C, but you would
not exactly be breaking new ground.)
We return in part to an argument in our first section.
Linkage from a large PSE to symbolic tools in CAS is
typically supported
via a somewhat narrow character-string channel. Yet one
would might have considerable difficulty tweezing out just a
particular routine like our Euler Fortran example
function above. The systems may require the assembling of one or
more commands into strings, and parsing the return values.
It is as though each time you wished to take some food
out of the refrigerator, you had to re-enter the house via the front
door and navigate to the kitchen. It would be preferable, if we were
to follow this route, to work with the system-providers for a better
linkage -- at least move the refrigerator to the front hall.
Yet there are a number of major advantages of Common Lisp over most
other languages that these links do not provide. The primary
advantage is that {\em Common Lisp provides very useful organizing
principles for dealing with complex objects, especially those built up
incrementally during the course of an interaction.} This is precisely
why Lisp has been so useful in tackling artificial intelligence (AI)
problems in the past, and in part how Common Lisp features were
designed for the future. The CLOS (Common Lisp Object System)
facility is one such important component. This is not the only
advantage; we find that among the others is the posibility of
compiling programs for additional space and time efficiency. The
prototyping and debugging environments are dramatically superior to
those in C or Java even considering the interpretive C environments
that have been developed. There is still a vast gap in tools, as well
as in support of many layers of abstraction, that in my opinion, gives
Lisp the edge: Symbolic compound objects which include documentation,
geometric information, algebraic expressions, arrays of numbers,
functions, inheritance information, debugging information, etc. are
well supported.
Another traditional advantage to Lisp is that a list structure can be
written out for human viewing, and generally read back in to the same
or another Lisp, with the result being a structure that is equivalent
to the original\footnote{
Modern Lisps tend to back away from
this principle of built-in universal read/write
capabilities for non-list structures:
Although every structure has some default form for
printing, information-preserving print and read methods may have to be programmed.}.
By comparison, if one were to design a structure with C's pointers, one
cannot do much debugging without first investing in
programs to read and display each type of structure.
\bigskip
In spite of our expressed preference, what about other
possible glues? Script languages
seem to have little special regard
for symbolic mathematics, although several mentioned
in our earlier list are quite interesting.
Ambitious CAS vendors certainly would like to come
forward; using proprietary code is one barrier. Nevertheless,
we hope to benefit from the current surge in
exploration and design of languages for interaction, scripting, and
communication as a reaction to the dominant ``thinking in C'' of
previous decades.
\section{Two short-term directions for symbolic computing}
Martin's \cite{martin} goal of building a general assistant, an
artificially intelligent robot mathematician composed of a collection
of ``facts'' seems, in retrospect, too vague and ambitious. Two
alternative views that have emerged from the mathematics and computer
science (not AI) community resemble the ``top-down'' vs ``bottom-up''
design controversy that reappears in many contexts. A top-down
approach is epitomized by AXIOM \cite{jenks-sutor}. The goal is to
lay out a hierarchy of concepts and relationships starting with
``Set'' and build upon it all of mathematics (as well as abstract and
concrete data structures). While this has been shown to be reasonably
successful for a kind of constructive algebra, an efficient
implementation of higher constructs seems to
be difficult. Perhaps this reflects an underlying problem
relating to approximations to continuum engineering mathematics.
By contrast, the bottom-up approach attempts
to build successful applications and then generalizing. At the
moment, this latter approach seems more immediately illuminating.
We discuss these approaches in slightly more detail below.
{\subsection {The top-down approach}
As we have indicated,
the approach implicit or occasionally explicit in some CAS development
has started from the abstract: Make as much mathematics constructive as possible,
and hope that applications (which, after all, use mathematics) will
follow.
In addition to the challenge of overcoming such humble beginnings,
is that general constructive solutions
may be too slow or inefficient to put to work on specific problems.
Yet it seems to us that
taking the ``high road'' of building a constructive model
of mathematics is an inevitable, if difficult, approach. Patching
it on later is not likely to be easy.
Of the
commercial CAS today, AXIOM sees to have the right algebraic
approach, at least in principle. Software engineering,
object-oriented programming and other buzzwords of current
technology may obscure the essential nature of having programs
and representations mirror mathematics, and certainly the details
may change; the principles should remain for the core of constructive
algebra.
We hope this is not incompatible with the view of the next section;
with perseverance and luck, these two approaches may converge and
help solve problems in a practical fashion.}
\subsection{Bottom Up: Learning from specifics}
{As an example of assessing the compromises
needed to solve problems effectively,
consider
the work of Fritzson and Fritzson \cite{fritzson} who discuss
several real-life mechanical design
scenarios. One is modeling the behavior of a 20-link saw chain
when cutting wood, another is the modeling of a roller-bearing.
To quote from their introduction.
\begin{quote}
``The current state of
the art in modeling for advanced mechanical analysis of a machine element is
still
very low-level. An engineer often spends more than
half the time and effort of a typical project in implementing and
debugging Fortran programs. These programs are written in order to perform
numerical experiments to evaluate and optimize a mathematical model
of the machine element. Numerical problems and convergence problems
often arise, since the optimization problems usually are non-linear.
A substantial amount of time is spent on fixing the program to achieve
convergence.
Feedback from results of numerical experiments usually lead to
revisions in the mathematical model which subsequently require
re-implementing the Fortran program. The whole process is rather
laborious.
There is a clear need for a higher-level programming environment that
would eliminate most of these low-level problems and allow the
designer to concentrate on the modeling aspects.
\end{quote}
They continue by explaining why CAD (computer aided
design) programs don't help much: These are mostly systems for
specifying geometrical properties and other documentation of
mechanical designs. The most general systems of this kind may
incorporate known design rules within interactive programs or
databases. However such systems {\em provide no support for the
development of new theoretical models or the computations associated
with such development... [the] normal practice is to write one's own
programs}.
The Fritzsons' view is quite demanding of computer systems, but
emphasizes, for those who need such prompting, the central notion that
the PSE must support a single, high-level abstract description of a
model. This model can then serve as the basis for documentation as
well as computation. All design components must deal with this model,
which they have refined in various ways to an object-oriented line of
abstraction and representation. If one is to make use of this model,
the working environment must support iterative development to refine
the theoretical model on the basis of numerical experiments.}
Thus, starting from an application, one is inevitably driven to
look at the higher-level abstractions. These are not likely to
be initially a close match to modern algebra but there may
be some common ground nevertheless.
\section{The Future}
What tools are available but need further development? What new
directions should be explored? Are we being inhibited by technology?
There are some impressive symbolic tools available
in at least one non-trivial form, in at least one CAS. Often
these can and should be extended for use in PSEs.
\begin{itemize}
\item Manipulation of formulas, natural notation,
algebraic structures, graphs, matrices
\item Categories of types that appear in mathematical discourse.
\item Constructive algorithmic mathematical types, canonical forms, etc.
\item Manipulation of programs or expressions:
symbolic integrals and quadrature, finite element calculations:
dealing with the imperfect model of the real numbers that occurs
in computers.
\item Exact computation (typically with arbitrary precision integer
and rational numbers).
\item Symbolic approximate computation (Taylor, Laurent or asymptotic series,
Chebyshev approximations)
\item Access to numerical libraries
\item Typeset quality equation display / interactive manipulation
\item 2-D and 3-D (surface) plots
\item On-line documentation, notebooks.
\end{itemize}
There are tools, capabilities, or abstractions
fundamentally missing from today's CAS, although many of
them are available in some partial implementation or
are being studied in a research
context. They seem to us to be worthy of consideration for
inclusion in a PSE, and probably fit most closely with the
symbolic components of such a system.
\begin{itemize}
\item Assertions, assumptions
\item Geometric reasoning
\item Constraint-based problem solving
\item Qualitative analysis (Reasoning about physical systems)
\item Derivations, theorems, proofs
\item Mechanical, electronic, or other computer-aided design data
\end{itemize}
As an example of another area in which CAS can support PSEs in the future,
consider plotting and visualization.
To date, most of the tools in scientific
visualization are primarily
numerical: ultimately
computing the points on a curve, surface or volume, and displaying
them.
In fact, when current
CAS provide plotting, it is usually in two steps. Only the first
step has a symbolic component: producing the expression to be
evaluated. The rest of the task
is then essentially the traditional
numerical one.
{Yet by maintaining a hold on the
symbolic form, more insight may be available.
Instead of viewing an expression as a ``black box''
to be evaluated at some set of points, the expression can be
analyzed in various ways: local maxima and minima can be found
to assure they are represented on the plot. Points of inflection
can be found. Asymptotes and other limiting behaviors can be
detected (e.g. ``for large $x$ approaches $\log x$ from below).
By using interval
arithmetic \cite{fatemanplot}, areas of the function in which additional
sampling might be justified, can be detected. In some cases exact
arithmetic, rather than floating-point, may be justified.
These techniques
are relevant to functions defined mathematically and
for the most part do not pertain to plots of measured data.
}
Finally, we feel that a the recent interest in communication in the
MathML/XML OpenMath communities may provide a foundation for
a better appreciation of the merits of symbolic computation
in a broad context of PSEs.
\section{Acknowledgments}
Discussions and electronic mail with Ken Rimey, Carl Andersen, Richard
Anderson, Neil Soiffer, Allan Bonadio, William Kahan, Bruce Char and
others have influenced this paper and its predecessor notes. Some of
this material appeared in an unpublished talk at {the Third IMACS
Conference on Expert Systems for Numerical Computing, 1993}.
This work was supported in part by NSF Infrastructure Grant number CDA-8722788
and by NSF Grant number CCR-9214963 and CCR-9901933.
\begin{chapthebibliography}{99}
\bibitem{abram}
M. Abramowitz and I.A.~Stegun (eds.), {\em Handbook of Mathematical Functions},
Dover publ. 1964.
\bibitem{akers}
R. Akers, E. Kant, C. Randall, S. Steinberg, and R. Young, "SciNapse: A Problem-Solving Environment for Partial Differential Equations," IEEE Computational Science and Engineering, vol. 4, no. 3, July-Sept. 1997, 32--42.
(see {\small\tt http:/www.scicomp.com/publications})
\bibitem{cook}
G.O.~Cook, Jr.
``Code Generation in ALPAL using Symbolic Techniques,''
{\em Proc. of ISSAC'92}
ACM Press (1992), 27--35.
\bibitem{dewar} M.C.~Dewar., Interfacing Algebraic and Numeric
Computation, Ph. D. Thesis, University of Bath, U.K. available as Bath
Mathematics and Computer Science Technical Report 92-54, 1992.
See also Dewar, M.C.
``IRENA -- An Integrated Symbolic and Numerical Computational Environment,''
{\em Proc. ISSAC'89}, ACM Press (1989) 171 -- 179.
\bibitem{fatemanplot}
R.~Fateman.
``Honest Plotting, Global Extrema, and Interval Arithmetic,''
{\em Proc. ISSAC'92}
ACM Press, (1992) 216--223.
\bibitem{fritzson} P. Fritzson and D. Fritzson.
The need for high-level programming support in scientific computing
applied to mechanical analysis.
{\em Computer and Structures 45} no. 2, (1992) pp. 387--395.
\bibitem{nsfpse}
E.~Gallopoulos, E.~Houstis and J.~R.~Rice.
``Future Research Directions in Problem Solving Environments
for Computational Science,''
Ctr. for Supercomputing Res. Univ. of Ill. Urbana (rpt 1259), 51 pp.
\bibitem{gates} B.L.~Gates, {\em The GENTRAN User's Manual : Reduce
Version,} The RAND Corporation, 1987.
\bibitem{jenks-sutor}
Richard D.~Jenks and Robert S. Sutor.
{\em AXIOM, the Scientific Computation System}.
NAG and Springer Verlag, NY, 1992.
\bibitem{lanam}
D.H. Lanam,
``An Algebraic Front-end for the Production and Use of
Numeric Programs'',
Proc. ACM-SYMSAC-81 Conference, Snowbird, UT,August, 1981 (223---227).
\bibitem{martin}
W.~A.~Martin and R.~J.~Fateman. ``The MACSYMA System''
{\em Proc. 2nd Symp. on Symbolic and Algeb. Manip}
ACM Press, 1971, 59--75.
\bibitem{press}
W. H. Press, B. P. Flannery, S. A. Teukolsky and W. T. Vetterling.
{\em Numerical Recipes (Fortran)},
Cambridge University Press, Cambridge UK,
1989.
\bibitem{sofroniou} Sofroniou M. {\em Symbolic And Numerical Methods for
Hamiltonian Systems}, Ph.D. thesis, Loughborough University of
Technology, UK, 1993.
\bibitem{teitel}
W.~Teitelman.
{\em Pilot: A Step toward Man-computer Symbiosis,}
MAC-TR-32 Project Mac, MIT
Sept. 1966,
193 pages.
\bibitem{wang} P.~S.~Wang.
``FINGER: A Symbolic System for Automatic Generation of Numerical
Programs in Finite Element Analysis,''
{\em J. Symbolic Computing} vol. 2 no. 3 (Sept. 1986). 305--316.
\bibitem{wirth}
Michael C. Wirth. {\em On the Automation of Computational Physics}
PhD. diss. Univ. Calif., Davis School of Aplied Science, Lawrence Livermore
Lab., Sept. 1980.
\end{chapthebibliography}
\end{document}