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.