CaminoRealPaper.tioga
Dennis Arnon, October 13, 1986 12:52:18 pm PDT
CaminoReal: A Way to Real Algebra and Geometry
Dennis Arnon
© Copyright 1986 Xerox Corporation. All rights reserved.
Abstract:
Keywords:
There is no royal road to geometry.
There is no 'royal road' to geometry.
Euclid, said to Ptolemy I. Proclus, Comment on Euclid, Prol. G. 20 (The Oxford Dictionary of Quotations, p. 209)
Introduction
Our concerns fall into three areas: (1) user interface for math expression editing, technical documents, and doing algebra, (2) display and manipulation of 2d and 3d semi-algebraic sets, and (3) facilities for cad and QE computations.
Serve spectrum from technical typist to physicist and mathematician. Very few people want to know about groups, rings, fields, maybe a few more want to know that domain is matrices of polys with complex coeffs. Should provide for secretaries enforcement/templates of subscript types to avoid typos.
Cedar/Mesa is a strongly typed language.
The data I want to work with is highly structured, uniform.
Our metaphors are mathematical document, mathematical database. Thus we expect to have expressions interspersed with text, as in a technical paper. So "history mechanism" has to be integrated with document editor.
We want the user to be unaware of dealing with a special interface to the algebra system. It should feel like I'm browsing my technical document and can do algebra whenever I want. From the other side, when I have some serious computing to do, the document system should be a handy secretary, allowing me to record and refer back to what I do.
The question is: what is Iris's history mechanism, and what is it's ability to delve into existing databases of expressions?
Portability doesn't matter to us. We have a hierarchy of display system, local algebra system, and remote algebra systems. The display system and local algebra system run in the same address space, so their data representations should be as uniform as possible.
Object-oriented algebra system
Motivation was to get generic procs for the domains of interest.
No inheritance.
Living with domains
A domain means: (1) a certain set of objects is denoted; this set may or may not be an algebraic structure such as group, ring field, (2) a certain syntax for input objects is enforced, (3) certain display rules for output objects are used.
Our point of view is that all actions take place within some domain, and if that domain is anything other than general expressions, the user must know what it is and specify it.
The default is to do natural conversions, e.g. imbed integer as rat, rat as algebraic.
Macsyma, Reduce are allowable domains. Selecting one of these domains means that the input is assumed to be legal Macsymese or Reducese.
We try to follow the rule that there is one class record for more than one domain. However the sequence constructor violates this; every time you make a new sequence structure you make a new class record.
Cad domain ops
Request for any AlgebraicSurfaces display op starts up the tool if not already started. Or have it running all the time, and each display request creates a new surfaceDisplay viewer.
AlgebraClasses has proc to add an op to a structures property list. Or MakeSequenceStructure proc takes procs to add to prop list as args.
Cad ops
induced cad
Alternate display
showTriangulationAll (valid only for cad's of 1-, 2- and 3-space)
showTriangulationSections
showTriangulation0Cells
showTriangulation1Cells
showTriangulation2Cells
rayTraceInputPolynomials (valid only for cad's of 3-space)
show cells
show statistics
Cad's should have names, statistics
Store only basis signatures with cells. Both clustering during cad construction, and clustering for disambiguation of signatures, are done with basis signatures (if basis signatures with ordinary projections don't suffice to get unambiguous clusters, then we have to go back and refine cad with respect to augmented projections).
Cluster ops
select containing cad
rayTrace (valid only for 2-cluster in 3-space)
showTriangulation (valid only for clusters in cad's of 1-, 2- and 3-space)
Cell ops
select containing cad
rayTrace (valid only for 2-section in 3-space)
showTriangulation (valid only for cells in cad's of 1-, 2- and 3-space)
Polynomial sequence ops, for base coeffs that are ints or bigrats
rayTraceZeros (valid only 3-variate polys)
decomposeZeros (forks Vax computation; pop up menu for options (including covering set parameters); inserts cad in Active MessageSet)
showZerosTriangulation (valid only for 1-, 2- and 3-variate polys)
New Polynomial ops, for base coeffs that are ints or bigrats
rayTrace (valid only for 3-variate poly)
decomposeZeros (forks Vax computation; pop up menu for options (including covering set parameters); inserts cad in Active MessageSet)
showZeroTriangulation (valid only for 1-, 2- and 3-variate poly)
Sequences
Basic display is one line: "sequence of n shortPNames"
Alternate display: Slider bar onto popup menu
popup menu entries are shortPNames of sequence elements
Insert creates a blank entry in popup menu; then select item to be inserted as an operand, it is type checked, inserted.
Delete modifies pop up menu
Selection of Insert or Delete forces Alternate display
Graph ops, read adjacencies, compute clusters
Cad statistics records
SmartInfo about the cad (0-cell bounding box, singularities, turning points).
Display methods for 1D space
Display a scaled line with cells.
Display methods for 2D space
Use SmartInfo
Draw2D.
General info for plotting points in an imager context.
Display 2-cell in a given color.
Handling collections of cells in 2D, a la object management in 3D world.
Displaying clusters, and management of adjacency info, in 2D.
Display a specified cell, or collection of cells (e.g. cluster, cells in solution set) in a specified color.
New Ops: Zoom, Orbit.
Algebraic surface display pipeline
How do you come up with a good triangulation? How to have a good algorithm which both may, and may not, take account of adjacency information?
Steps by which Rauen takes a triangulation and renders it.
Default: automatically scale Camion viewer to be just tall enough to hold expression in it.
New cell Ops: read covering set, display covering set
Background: Prior work and software base at Xerox
Star/VP editor.
Background: The legacy of TeX
Our claim is that it's great for the final beautiful output, but not for the document evolution, daytoday working process.
High precision typesetting vs. getting your day-to-day work done.
Rick's ideas are in MathComposition.DF, /cyan/tioga/top/tabletool.df
Hard questions: Fateman thinks a possible problem with the scheme we propose is - how do you get control over the fine details of how the expression will be displayed in a document, i.e. the Interpress fragment, if you edit it with an EXED -like editor? For example, how would you specify the insertion of a half em space between two characters? Apparently the problem he sees is that if you have such information in an expression, and then you edit it, what are default rules for what happens to it, or perhaps, how can you avoid it being either lost or rendered meaningless?
One facility is the ability to specify expressions as programs, and have expressions dependent on others, This might require invoking an algebra system to evaluate the expressions when a document is to be run off. This raises the general problem of how to know when evaluating an expression may invoke a huge algebra computation - meanwhile the user is wondering why his document isn't coming out. In general, seems that we want to be able to only reeavaluate expressions when necessary, i.e. after changes.
Another thing one can consider is a "document-like" approach to using an algebra system, i.e. automatic history mechanism of a more sophisticated, attractive, and useful kind. A simple version of this would be to have your session with the algebra system automatically logged as a formatted document. Note that the boundary between this paradigm, and the model in which you are writing a document but can invoke an algebra system when you want to, is fuzzy.
Math nodes in Tioga documents
The idea is to have a new kind of node ("Math") in Tioga documents. A list representation and an Interpress fragment are stored with the node. When you just want to paint the object on your screen, you get Tioga to paint the Interpress fragment (an extnsion to Tioga is needed to make this happen). When you want to print the document, you get the TSetter to be able to use the Interpress fragment in the node. When you want to edit the equation, you go get a separate window for it, and pass the list representation to the expression editor. When you're done, you regenerate an Interpress fragment and put it, plus the new list representation, back into the document.
Equations among text are done in two levels. Such nodes have a "MathInText" property. To edit, you first break the whole Text node out into a window in which indivudual expressions are Math nodes, then edit each of Math node as just described.
New sequence op: Apply elementStructure UnaryOp to each element of sequence, generating a new sequence.
New cell Ops: rootfinder, generate covering set
Compute and add adjacencies to an existing cad.
Remote algebra systems
RPC interface to Reduce in Interlisp. Running Cedar and Lisp in separate partitions on the same Dorado, communication by files (Bobrow). Common microcode project (Bobrow). Remote procedure call. Examples of useful Interlisp facilities are - Notecards, Argnoter, Cognoter. People who have built connections between Cedar and Interlisp: Swinehart (see Yearend report), Russ, Bobrow.
Foster - RPC (Henry Thompson's) takes 100 ms in InterLisp, 10ms in Cedar. (- that's the RPC from one Cedar machine to another? How long does it take for the dictionary server?) In his COLAB work they have the ability to move mouse across different machines.
Foster - There is a FORMAX? layout program in Interlisp, which can be used as part of Tedit.
Numerical computation and plotting
User interfaces: What do typical users want? Can algebraic, numerical, and graphical facilities all be available in one environment?
Geometric reasoning
Four key things:
Hopcroft article June 86 CACM
German guy's article in Bulletin AMS
Oxford Workshop
Special session on Geometry Theorem Proving at SYMSAC
This is both a trip report and a personal review of the areas of activity in this area that are relevant to the Imaging Group.
The particular focus is how computer algebra is, and can be, useful to such areas as computer graphics, computer aided design, and computer vision.
I try to focus on a few illustrative examples in some detail.
Part I deals with sample problems. Part II deals with the three problem-solving methodologies which have been used to attack these types of problems, and results so far. Part III briefly sketches the current availability of these methodologies in our environment, and possible pathways, with estimates of labor involved, for future development of the methodologies, and integration with existing Cedar tools.
\section{Sample problems.}
These are of two kinds: shape construction and solution of problems.
\subsection{Root configuration coefficient constraints.}
The evaluate-substitute paradigm for solution of intersection problems.
Sequence of problems: univariate polynomials, ellipse problem, surface intersections.
\subsection{Fat curves, tubular ("sweep") solids.}
\subsection{Topologically reliable display of parametric curves and surfaces.}
\subsection{Full Kahan ellipse problem.}
\subsection{Blending surfaces.}
Defined by qe, or just cad.
\subsection{Buchberger example.}
\subsection{Mundy example.}
\subsection{Kapur example: 3D configurations giving rise to 2D projection.}
\subsection{Chou inequalities examples.}
\subsection{Davenport motion planning example.}
\section{Three problem-solving methodologies.}
\subsection{Introduction.}
The basic principle is analytic geometry, i.e. conversion of a geometry problem to an algebra problem.
\subsection{Cellular decomposition.}
\subsection{Groebner bases.}
\subsection{Wu's method.}
References
[AND83]
R. A{\small NDERSON}, {\sl EXED: A prototype user interface for algebraic manipulation systems}, Stanford University, MS., October 1983.
[COW78]
R. C{\small OWAN AND} M. G{\small RISS}, {\sl Towards an algebra system based on pattern matching}, Report UCP-67, University of Utah, Oct. 1978.
[FIT82]
J. F{\small ITCH AND} J. P{\small ADGETT}, {\sl A pure and really simple initial functional algebraic language}, Mathematics Unit, University of Bath, December 1982.
[FOS84a]
G. F{\small OSTER}, {\sl User interface considerations for algebraic manipulation systems}, Report No. UCB/CSD 84/192, EECS Dept., U.C. Berkeley, April 1984.
[FOS84b]
G. F{\small OSTER}, {\sl DREAMS: Display REpresentation for Algebraic Manipulation Systems}, Report No. UCB/CSD 84/193, EECS Dept., U.C. Berkeley, June 1984.
[HEA80]
A. H{\small EARN}, {\sl The personal algebra machine}, Proc. IFIP '80, North-Holland, Amsterdam, 1980, pp. 620-628.
[JEN78]
R. J{\small ENKS}, {\sl Towards a language for use and implementation of algebra systems}, Report UCP-64, Symbolic Computation Group, Comp. Sci. Dept., Univ. of Utah, April 1978, 20pp.
[JEN80]
R. J{\small ENKS}, {\sl MODLISP: A preliminary design}, Report RC8073, Math. Science Dept., IBM TJ Watson Research Center, Jan 18, 1980.
[JEN81]
R. J{\small ENKS}, {\sl A language for computational algebra}, Report RC8930, Math. Science Dept., IBM TJ Watson Research Center, July 14, 1981.
[MAR80]
J. M{\small ARTI}, {\sl Compilation techniques for a control-flow LISP system}, Proceedings of the LISP '80 Conference, 203-207.
[MAF82]
J. M{\small ARTI AND} J. F{\small ITCH}, {\sl The Bath Concurrent Lisp Machine}, Mathematics Unit, University of Bath, December 1982; Also Proc. EUROCAL '83?
[MAR82]
J. M{\small ARTI}, {\sl Interprocess comuunication in the Bath Multiple 68000}, Mathematics Unit, University of Bath, December 1982.
[PAD82]
J. P{\small ADGETT AND} J. F{\small ITCH}, {\sl A new model for dynamic access environments}, Mathematics Unit, University of Bath, December 1982.
[SOI??]
N. S{\small OIFFER}, {\sl A perplexed user's guide to Andante}, MS. U.C. Berkeley.
[WAT85]
S. W{\small ATT}, {\sl Parallel algorithms for computer algebra}, Ph.D., University of Waterloo, 1984.