Problem Solving Environments: Expectations and Reality
Richard Fateman Dec, 1998
Part I:
The Name Game:
Accelerated Strategic Grand Challenge High Performance
Environments.
Question:
Is it just Old Wine in New Bottles?
Answer: Not really. There are some things we have learned, and
we should continue to pursue stated objectives.
Reality check:
* It is hard to re-use programs.
* For computer scientists it is especially easier to try to innovate
than re-use: the appearance of new code is a form of progress.
* PSEs tend to be driven by current technology at least as much as
problems (+ and -).
* A PSE without an important user community is on a relatively short
leash (financially).
* Some application communities are very grateful for even modest
assistance in using nearly intolerably difficult software and
hardware.
* Some application communities are sufficient unto themselves and are
reasonably set on their research path. They principally need to make
sure that they are not cheated out of the next increment of Moore's
law by some hare-brained computer science interference.
* Even for these communities, it may be that there are unexploited
technologies in computer science, mathematics, and even AI that can
contribute to solving really hard problems. But that case will not be
made in the absence of visible success on similar hard problems.
In other words, getting scientists to divert valuable time and
energy to learning new speculative technology requires a convincing
story.
Times change.
* We are faced with ever-changing technical and economic influences
relating to standards wars, technology "lock-in" and
"winner-takes-all" competitions. In the past, these did not have such
a strong effect on high-end computing. (No longer can DOE labs
buy/build the fastest computer and then start writing software and
building networking for it from the ground up: there's not enough
time between computer generations.)
* Pricing of commodity computers now affects supercomputing
hardware and software: economies of scale (fortunately!) affect high-end
government computer purchases.
* Increasingly the computer industry is focused on end-user issues and
marketing, rather than core technology.
What are we spending our time doing? What's a PSE?
1. PSEs can be broadly defined to include much of what has been done
and might be done in the name of making computers useful to people.
Gallopoulos, Houstis and Rice coined the term and explain
"they create a framework that is all things to all people: they solve
simple or complex problems, support rapid prototyping or detailed
analysis, and can be used in introductory education or at the
frontiers of science."
a. What is excluded?
Maybe something you write as a one-time run-once custom-written
program. You could have written it using a PSE, though.
b. Some use of the computer that solves no problem whatsoever.
A screensaver comes to mind.
2. We have seen two direction to go in the PSE-building field: specific
and general.
SPECIFIC: We can come up with a PSE to solve a tightly constrained
problem, yet still somewhat interesting problem. It could be a
particular design problem, or some knowledge-based system using
multiple collaborating components, a graphical user interface and
communication services. Here's one we made up for this slide:
TBSFPSE, the "Traveling From Berkeley to Santa Fe Problem Solving
Environment" An integrated, graphical, user-friendly program that
would be clever enough to advise on flights, times, and prices; it
would suggest that one NOT fly to Santa Fe airport but
that one can fly from Oakland non-stop to Albuquerque and
rent a car. It would be able to book a flight, reserve a car, make a
secure credit card transaction, and send a confirming FAX.
Here's another one, available on many home computers: a PSE to
solve the problem of "design an overhead slide show."
A successful specific PSE is valuable for two reasons. It is a "stick
in the ground". That is, if you can somehow do this, you can build
another specific system for a similar problem (or for the CS types, a
more general system to produce applications just like this)
It is naturally valuable for the applications specialists since a
custom-built environment means that they do not have to deal with
excess generality/stupidity of computer systems as ordinarily
deliveried. The the software/environment specialists have created or
perhaps duplicated in the computer a comfortable problem-solving
paradigm.
The contrast to these application-based PSEs
runs to those PSEs are designed around scientific or engineering
computational principles.
GENERAL:
a. Instead of writing a specific PSE, we write PSEs that embody some
principle. Think of this as Support of Goodness. That is, from "X is
good" we conclude PSEs should be designed to support X. (X =
visualization, collaboration, object-orientation, re-use, laboratory
data analysis, signal processing, artificial intelligence, security,
legacy data, parallelism, geometry, etc.)
b. we write components or tools to be used by PSEs. The simplest example
might be a subroutine or a subroutine library to be used at runtime.
A program to compute a cosine. or a Java Bean style component.
c. we write tools to be used by those who BUILD PSEs. This might be a
graphics-based editor that allows a "programmer" or an application
expert to visualize how to connect components of the previous
category. (Khoros, AVS) Or it might be a problem decision tree like
that supported by NIST's Guide to Available Mathematical Software
(GAMS) http://gams.nist.gov:80/ or netlib http://www.netlib.org/.
These provide the wisdom of the ages (or at some of it from the last
few decades). It might be communications protocol support like
interfaces to CORBA, Active/X etc. assuming that the PSE world
view will require multiple distributed computing engines.
d. we might write meta-tools to assist in writing components of
PSEs. For example we might talk about languages in which to
build graphics editors, or a semi-automatic HTML generator.
For example, one meta tool is PPK (Purdue PSE Kernel),
a software framework designed to assist in the development of PSEs.
e. we might even look at meta-meta-tools. For example, should
one be writing meta-tools in Java, C, C++, Lisp, Fortran, TCL,
or writing in one of several not-yet-ready-for-prime-time
nascent standards for communicating among these languages?
[Aside: I've been using Java but I'm not happy with it.
Java is Good Because....
Java is good because
although it's usually interpreted and is slow it
Runs really fast on someone else's machine,
so we hear.
Java is good because although
it is object-oriented, it
Runs really fast on someone else's machine,
so we hear.
Java is good because it is secure,
and a program written in pure Java is
easy to debug, has a
well-defined semantics, and
Runs really fast on someone else's machine,
so we hear.
Java does automatic storage allocation, but
that's ok because times are different now...
although garbage collection was funny in lisp,
GC in Java
Runs really fast on someone else's machine,
so we hear.
Java is really truly machine independent,
provided all incorrect implementations
are erased and the correct JVM downloaded.
Then everyone's Java will compute the same thing; plus
a correct version
Runs really fast on someone else's machine,
so we hear.
If we must rewrite I would personnally
prefer either a computer algebra
system or lisp, which has compilers, objects, machine
independence.
:
(?) if you sell lisp programs, you have
to either give out source code or code compiled to a specific
machine... This can't be a good reason to do Java though. Anyone
can steal anything written in Java to run anywhere, from one copy.
(?) You can run Java code given to you with some modest hope that
it is not going to run amok on your computer, unless you
provide some running-amok plugins.
(?) Some manufacturers as well as government agences
are big on supporting Java (IBM and Sun)
(?)
There is a huge and growing body of programmers and
mostly-working Java code that is specifically net oriented,
so if you are doing net-gui stuff, you can use Java.
If you are doing (say) science stuff, you can use Java if
you not in hurry.
]
or
even meta^3 tools like various development kits, source-code
control systems, products like Metrowerks Code Warrior, etc.
3. There is another dimension of PSEs.
These systems all deal with computersbut some are
a. inward-looking, trying to solve the problem caused by our attempt
to use the computer itself. Typical of this would be a PSE for
wrassling with parallel computation. Another would be a PSE for
developing Java Applets. (Language-centric tools are often grouped in
a kit with debuggers, editors, project managers etc. called a
development kit).
b Others are outward-looking: the central consideration for such a
system would not be the computer's use, but some application. It might
be (for example) aimed at the development of mathematical proofs based
not on computation per se, but throught the enabling of human
collaboration. The problem solution method is not inherent in the
computer at all, which is providing convenience in communication.
Other categories of this nature might be document processing or digital
library applications: making legacy documents available, or in
some way "enlivening" them.
The features are virtually limitless, though some designs forbid this
direction: too many features will make it hard to use and therefore
useless for the target audience.
This is an old issue addressed in the programming language community
by the buzz-word "orthogonally." A language design can resemble
cross-product of features, requiring less human brain volume to
understand than a linear list. An orthogonal design would aim at
assuring that a person ignorant of a feature is not injured by its
presence.
The DOE national labs have been working on PSEs under the name of
Electronic Notebooks. Among the perhaps novel features needed for
some users in this domain are: secure time-stamps and non-eraseable
entries of data appropriate for patent applications. Direct
incorporation of machine sensor data. Logs of machine usage by
different people. Shared (vs. personal) notebooks.
The Digital Library projects (NSF, NASA, DARPA funded) have been
working on PSEs as well. Here the basic approach is to make available
the knowledge of the collection, with tools for adding to the
collection, searching (visual, statistical, geographical, ...),
annotation, collaboration, distribution. Scientific computation per
se has not played a major role in these ventures, but clearly has
something to offer the scientist who would otherwise include "the
library" in his problem solving environment.
4. Regardless of the name, what do we really want??
a. Ways for computers to be set up to help humans (or other computers)
to solve problems by providing guidance on what is known:
[is this a previously solved problem or a previously written
algorithm? By whom? when? where? Can I re-use this?],
b. Help for humans to explore new directions
[If I must solve this myself, what partial solutions are there, and
how do I use them?}, and
c. Diverse other resources that can be aided by computer intervention,
including communication with other humans, validation and presentation
of graphical results, educational presentations and interactive
programs, even protection from patent theft.
Part II:
What can we say about computer algebra systems and PSEs?
Let us assume we are talking about computing in the context of
math/science/engineering, and not, for example, about systems for
travel agencies.
1. A common language, expressive enough to unify our discussion.
If we are to re-use tools and communicate with other systems, we
benefit from a common language for description of problems and
solutions.
Fortran 77 (for example) is deficient by modern language standards. It
supports only the simplest mathematical constructs. Small integers,
floats (a subset of real numbers) complex numbers, and arrays of them.
Fortran 90 helps address some problems in Fortran 77, but fails to be
particularly expressive as a mathematical language.
How can this be?
On the top of the Most Wanted List: the notion of function. Close
behind: the notion of an exact rational number. Persons raised in the
Fortran culture do not notice a failure that is particularly glaring
from the computer science perspective (We teach about 25% of all
undergraduates at UC Berkeley, and about 100% of the science students,
about this).. the notion that a procedure can produce, as a
computational result, a procedure. This is possible in a variety of
computer languages, the most widely used "in the raw" is likely to be
Lisp.
Not only do computer algebra systems tend to share this more advanced
attitude toward programs as objects, but they tend to have "more
mathematical flesh" than generic "object oriented systems."
There is no conflict between O-O and computer algebra; indeed
some computer algebra systems make a big fuss about being
written in O-O systems.
2. Talking about math over networks
New roles for computers have appeared in the past decade for use in
storage and communication of mathematics. Some of this has been
motivated by the publishing/typesetting community looking for ways to
more effectively disseminate ideas. Some by the document analysis
community (optical character recognition or OCR), seeking to recognize
and preserve legacy documents, as well as new information first
produced on paper. The last five years has seen an enormous boost in
interest in on-line math, for display, communication, and
interaction. Proprietary notions have yielded somewhat to standards
efforts: OpenMath, MathML or an offshoot of XML. Combine math
typesetting information with semantic encoding sufficient to convey
underlying mathematical meaning. (http://http.cs.berkeley.edu/~fateman/MVSD.html) Some computer algebra
systems have had to solve this problem, though only in the reduced
context of what they need to communicate between their front and
back end programs (Mathematica, Maple, Macsyma, and perhaps others.
See also CAS/PI).
Enlivening books and journals: the MVD perspective..
3. The community of cooperating agents: the lesson from Unix.
Components that often work together, are fragile and not
user-friendly, but utilitarian;
4. The other side of the coin: the residential computer system. The
inheritors of the Xerox Alto, the Lisp Machines, the man-machine
symbiosis crowd, can now put most of their programs on a home
computer. When Wolfram touts his Mathematica as a revolution in
mathematics, is to what extent is he blowing smoke? The clear failure
of special-purpose hardware, when that is devoted to making
programmer's lives easier. ..The prospect of stock hardware for
programmers, stock hardware for supercomputers?
(PDP-10 vs CDC7600?) Sun vs Cray, SGI vs??? Cray, Sun vs CM5?
What is the objective here? Depends who is paying. The company
cutting out leather upholstery from cowhides? The quantum
mechanics? The nuclear stockpile stewards?
Back to computer algebra.
We are all so clever that we know $x^3+6x^2+11x+6$ can be evaluated
as $6+x(11+x(6+x))$, which looks computationally superior
because it uses fewer explicit operations.
We may even notice that $(x+1)(x+2)(x+3)$ computes the
same mathematical function. But which makes the best program?
Or is there yet another program that is even better?
The answer is: under some circumstances, and defining
better as faster and/or more accurate for some values of $x$,
yes.
How should we tell? One way is to learn as much error analysis as
is needed to allow us to tell. Another way is to
ask a program written by an expert to help
us write the program. Advantage: we save time, and we
RE-USE someone else's cleverness to use computers to better advantage.
Another way is to ignore this issue and assume that whatever
we compute will be good enough.
We are used to ``optimizing compilers'' improving our programs
in trivial and sometimes incorrect ways. Why not use computer algebra
to improve our programs in non-trivial and provably correct ways?
Derivatives of programs (Greiwank and Corliss)
Closed form integrals, or semi-closed form.. In fact,
computer algebra systems really don't work well enough today
because they were written to address symbolic questions and
need more thought.
Whose closed form do we use, Maple, Macsyma or Maple?
Integrate[1/x,{x,a,b}] or
integrate(1/x,x,a,b); or
int(1/x,x=a..b);
all give log(b)-log(a).
Not log(b/a)
or if 1/2** Numeric
2. Symbolic Mathematics Components
Can we extract them?
Program that manipulate programs
Derivatives, integrals
Closed form solutions
Semi-symbolic solutions
Exact, high-precision, interval ... arith.
Code generation for special arch.
Support for proofs, etc
Documentation/Output
Databases
Specific toolboxes: FEA, etc.
3. Symbolic Manipulation Systems as Glue
An argument for Lisp as scripting
and symbolic language
4. Objectives for Symbolic Computing
5. Future tools and problem areas
....................
INTRODUCTION
What is Symbolic Computation and how is it different?
Symbolic includes Numeric, Graphical, ...
Computer Algebra systems are becoming
interactive environments
(Mathematica, Maple, Macsyma)
Computer Algebra systems are being joined with
other environments (e.g. MathCAD+Maple)
Why is it that computer algebra is not so widely used?
* Because it is not as clever as the cleverest humans?
* Humans are more concerned with the absolutely fastest
computation, even if it is possibly wrong.
* It tends to be more rigorous that desired, and harder
to use, partly for that reason.
* Some systems suffer design flaws for historical
reasons (egos of designers!)
* No killer app?
....................
PART I: SYMBOLIC COMPONENTS
Toolkit approach is difficult:
It is hard to tease out individual pieces
[storage model, abstraction, run-time semantics]
(and futile to do so, in some cases)
{Commercial via Research objectives}
-------------------
Program that manipulate programs
* Assemblers, interpreters,
(pre-)Compilers, macro-expansion, etc.
The symbolic view is that:
expressions <==> programs <==> data
Consider this section
of a Bessel Function evaluation pgm. (from Numerical Recipes)
...
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))))))))
...
....................
Bessel Function/ Polynomial Eval in Lisp
(program --> better program )
(setf
bessi0
(* (/ (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))))
extract the polynomial part, and reformulate
(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))
uses 6 multiplies, 7 adds, not 8 of each (Better than just
Horner's rule!)
....................
Euler equation
(expression --> program(s))
The Euler equation is a favorite benchmark of Celestial Mechanics
symbolic calculation programs.
Systems without Poisson series do poorly on it.
E = u + e sin (E)
as commonly solved iteratively (for small e) gives a
4th order expansion for E= u+A as:
4 3 2 4
e sin(4 U) 3 e sin(3 U) (12 e - 4 e ) sin(2 U)
A = ----------- + ------------- + -----------------------
4 3 8 24
3
(24 e - 3 e ) sin(U)
+ --------------------
24
....................
Euler equation (continued 1)
In Fortran as rendered by Mathematica (version of 1993):
FortranForm=
- (24*e - 3*e**3)*Sin(U)/24 + (12*e**2 - 4*e**4)*Sin(2*U)/24 +
- 3*e**3*Sin(3*U)/8 + e**4*Sin(4*U)/3
(Here, Mathematica is outright wrong in conversion
into Fortran since it produces forms like 1/3 )
Call... Expand[N[%]]
FortranForm=
- 1.*e*Sin(U) - 0.125*e**3*Sin(U) + 0.5*e**2*Sin(2.*U) -
- 0.1666666666666666*e**4*Sin(2.*U) + 0.375*e**3*Sin(3.*U) +
- 0.3333333333333333*e**4*Sin(4.*U)
Apparently Mathematica's Fortran has some other errors: it
produces text with multiplications by 1., and has decided exactly
how many 3's are relevant for your Fortran compiler.
....................
Euler equation (continued 2)
Maple produces
t0 = E**4*sin(4*U)/3+3.0/8.0*E**3*sin(3*U)+(12*E**2-4*E**4)*sin(2*
#U)/24+(24*E-3*E**3)*sin(U)/24
or after floating-point conversion using evalf
t0 = 0.3333333E0*e**4*sin(4.0*U)+0.375E0*e**3*sin(3.0*U)+0.4166667
#E-1*(12.0*e**2-4.0*e**4)*sin(2.0*U)+0.4166667E-1*(24.0*e-3.0*e**3)
#*sin(U)
Maple has also decided how many 3's in 1/3, though this can be changed.
After rearranging using Horner's rule (convert(expression,horner,[e])}))
t0 = (sin(U)+(sin(2*U)/2+(3.0/8.0*sin(3*U)-sin(U)/8+(-sin(2*U)/6+s
#in(4*U)/3)*e)*e)*e)*e
Note sin(u) occurs twice..
....................
Euler equation (continued 3)
Macsyma can do about the same but also can pick out common
subexpressions. But notice that
s1 := sin(u)
c1 := cos(u)
s2 := 2*s*c
c2 := 2*c*c-1
s3 := s*(2*c2+1)
s4 := 2*s2*c2
gives s2 = sin(2 u), s3 = sin(3 u), s4 = sin(4 u) ?
None of the computer systems notice this.
....................
Derivatives, Integrals
Careful approaches (Griewank and Corliss) to derivatives can help a
great deal more than Computer Algebra systems. Naively sticking in
symbolic derivatives is often a bad idea.
Simple example: Evaluating a polynomial AND its derivative can be done
a lot faster by a modest change to Horner's reccurence than by using a
new expression.
Integrals
Closed form or quadrature? which is faster?
integrate(1/(1+z^5),z), or even worse, integrate(1/(1+z^64),z)
can be integrated, but the form is horrendous.
Whose closed form do we use
Integrate[1/x,{x,a,b}] or
integrate(1/x,x,a,b); or
int(1/x,x=a..b);
all give log(b)-log(a).
Not log(b/a) or if 1/2**** a sure-fire tool.
....................
Closed form solutions
The closed form symbolic expression, wearing singularities
on its face: The exactly zero expression. Proving identities.
Semi-symbolic solutions
Taylor, Laurent, Fourier, Asymptotic- series, perturbation
expansion; expansions in terms of sets of orthogonal polynomials
Exact, high-precision, interval ... arith.
Arithmetic on objects of variable size is offered:
Most systems support exact integer and rational computing.
This breaks down for exponential, log, trignometric function
computing --> arbitrary-precision floats.
exp(pi*sqrt(163))=262537412640768743.9999999999992500726.
New algorithms can be developed, e.g. for root-finding.
(Initial Root isolation in fixed precision, root refinement
in whatever precision is necessary.
(Variety of approaches in in 1994-1998, including parallel
processing)
....................
Code generation for special architectures
"factoring" of matrix code to maintain mathematical correctness
over various iterative patterns;
either analysis or timing of runs..
Support for derivations, proofs, reasoning,
Justifications, etc.
Documentation:
Output as TeX
Notebooks (Mathematica, Maple, Axiom, MathCAD)
Spreadsheets (Theorist, MathCAD)
Graphics into AVS, Khoros, other graphics packages
Specific Toolboxes e.g.
Finite Element Analysis
....................
PART III
Symbolic Manipulation Systems as Glue
Fortran or C cannot "naturally" talk about objects
the way (for example) Lisp or Axiom can.
Matrix languages (Matlab etc) are also deficient.
Character strings in pipes or RPC don't work
well enough.
Is there a role for Lisp?
Lisp as scripting and symbolic language
Other scripting languages.
....................
PART IV
Future objectives for Symbolic Tools and Environments
* Integration of data bases of properties, formulas, algorithms.
* Visualization
* Refined application packages.
* Geometric, constraint-based reasoning.
* Linear and non-linear inequalities.
* Very fast constructive mathematics algorithms using all the tools
at our disposal:
floating point, parallel/distributed techniques (e.g.
Strand-88 and Linda- Maple)
* Management of queries into large data bases (e.g. algebraic
or logical simplification of queries)
* Access to networked data and algorithms (e.g. the world's
best integration program; ODE program generator; closed-form
summation etc.)
* Collaboration support
* Legacy digital library
* Programming plus non-programmed "application kits"
*****IMPORTANT TEST CASES*******
....................
Future Objectives for Glue
* Ease of use -- e.g. AVS or Khoros style box programming.
* Ease of use -- clean functional /scripting language.
* Enhances portability
* Access to "everything" in other languages.
(now looks more like Java, Perl, TCL, Visual Basic. Active X,
in addition to a variety of more academic languages, including
Lisp, scheme, ML ,Prolog are in the running Somewhere.. )
....................
References: The PSE pages of various project groups are linked
to each other; Drexel, Rice, UV, DoE electronic notebooks at
ORNL. Char/Drexel paper in ISSAC98 on computer algebra components.
**