Problem Solving Environments (PSE)

Nuprl has provided semantic foundations for computer algebra systems and more generally for PSEs. In the early 90s we began to study the connections to computer algebra. Paul Jackson, Richard Zippel and Robert Constable studied the relationship between the computer algebra systems Axiom and Weyl and Nuprl. Jackson's thesis and CADE paper report on some of this work. Our Web paper on Collaborative Mathematics Environments puts this work in a broader context, and Constable's lectures on the topic report other aspects. There are draft papers waiting to be finished, but with Nuprl-Light we will have much better concepts for elaborating the ideas, so the drafts are waiting. The MathBus project also grew out of this work. It is now used in Nuprl 5.

The Context: Scientific Computing, Computer Algebra and Computational Geometry

The field of scientific computing and numerical analysis has led the way in software systems for integrating tools and for sharing algorithms. For example, the Computer Algebra Systems (CAS) like Axiom, Maple, Macsyma, and Mathematica provide an integration of numerical algorithms, graphics and algorithms for manipulating the data types of algebra such as polynomials, power series, integrals and so forth.

Numerical analysts have for many years shared algorithms through libraries such as Linpack and Eispack. Now systems like Matlab make available such libraries of algorithms integrated with graphics packages. The OpenMath project in Europe is trying to build a problem solving environment which is in the public domain and to which users will add symbolic, numerical and graphical algorithms.


The computational geometry community (CG) uses the Leda system that Kurt Mehlhorn and his group at the Max Planc Institute have created to provide good algorithms for robustly processing geometric objects. The Seagull project is an open effort of the CG community to standardize on the definitions of geometric objects and algorithms.

Broader Context: Computational Science

The problems posed in problem solving environments typically arise in building a computational model of some physical system - air flow over a wing, propagation of cracks in the surface skin of an airplane, stress on bolts holding an engine to a wing, transmissions of electrical signals along a nerve cell, the binding of a protein to a the surface of a cell, and so forth.

There are many software systems that attempt to embody our knowledge of physical systems in simulators, e.g., Gauss for chemistry. It is important that these systems interact with PSEs; this can be done by sending models to a PSE for further processing of a simulation. PSEs are also used to build these simulators.

Technical Contributions

Nuprl has played a role in providing a semantic foundation for the types and domains of computer algebra systems used in integrated PSEs. Doing this work led us to see that formal systems of mathematics could provide a semantics that would help support the linking of components of a PSE such a programming language, algebra system and geometry system.

We think that this work is very promising. Some of our plans appear in the on-line article Collaborative Mathematics Enviroments. The articles of Paul Jackson discuss the foundations of computer algebra systems. Robert Constable has lectured on this topic at several algebra meetings and some of the work is described in his invited address at LICS 95, an expended version appears on this Web page as Experience using Type Theory as a Foundation for Computer Science, circa 1995

The Nuprl work on CAS was supported by DARPA and has led to the notion of the MathBus discussed in Collaborative Mathematics Environments and developed in the paper of Richard Zippel and used by Richard Eaton and Lori Lorigo in coding the Nuprl 5 system.