[Indigo]<CaminoReal>CaminoRealPaper.tioga!5

CaminoRealPaper.tioga

Dennis Arnon, May 11, 1987 11:12:14 am PDT

CaminoReal: A Direct Manipulation Style User Interface for Mathematical Software

Dennis Arnon*, Richard Beach*, and Carl Waldspurger'

* Xerox Palo Alto Research Center

3333 Coyote Hill Road

Palo Alto, California 94304

' Massachusetts Institute of Technology

Cambridge, Massachusetts 02139

Abstract: In the realm of Mathematical Software one finds Computer Algebra systems (e.g. Macsyma, Reduce, Scratchpad, Views), Numerical libraries and systems (e.g. IMSL, NAG), nice user interfaces for Computer Algebra systems (e.g. MathScribe), and high-quality Mathematical Typesetting systems (e.g. TeX, Eqn-Troff). Each type of software offers powerful and sophisticated facilities. Nonetheless, what one really wants is integrated access to all of them, and this is not currently available.

One type of activity that an integrated user interface should support is the creation of "interactive" technical documents. For example, the user browses a (nicely typeset) draft of a technical document on the WorkStation screen, selects, edits and computes with mathematical expressions in it (besides editing text and graphics, of course), and inserts the resulting expressions into the document. A second type of activity to be supported is a session of computations with interactive Computer Algebra or Numerical systems: the interface should offer convenient access to computational methods, offer facilities for data management and display, and maintain an audit trail of the session (in the form of an interactive document that can later be browsed, replayed, or edited). We see that In the integrated user interface, "editing" and "computation" are just different flavors of activity that we switch between at will. Furthermore, Direct Manipulation is clearly the most suitable user paradigm.

CaminoReal is a Direct Manipulation style user interface for integrated access to documentational and computational mathematical functionality. Currently it lives in Cedar, the programming environment of Xerox PARC's Computer Science Laboratory, and is used in conjunction with Tioga, Cedar's multimedia document editor. It is built on top of a device-independent graphics model, however, and is designed to be easily ported to any other environment that supports a comparable graphics model. It utilizes the notions of Object-Oriented Programming and Domains for organizing its editor's knowledge base of mathematical notations, for organizing its evaluator's knowledge base of computational methods, and for integrating the two. Actual document production (e.g. printing, management of other document constituents such as text and graphics) is expected to be provided by an existing document editor in whatever environment CaminoReal runs. Actual computational functionality is provided by "math servers" on a network, typical instances of which are Computer Algebra systems and Numerical libraries. Math servers can be written in Lisp, Fortran, or any other language supported somewhere on the network.

For the longer term, our goal is to make CaminoReal an attractive and efficient mechanism for marshalling the full imaging (e.g. plotting, rendering, graphical, illustrative, document-producing) and computational resources of PARC computing environments, in mathematical contexts.

Keywords: Computational Mathematics, Document Processing, Mathematical Typesetting, Technical Documents, Mathematics Editing, WYSIWYG, User Interfaces, Direct Manipulation, Computer Algebra, Symbolic Mathematical Computation, Numerical Computation, Object-Oriented Programming

XEROX Xerox Corporation
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, California 94304

For Internal Xerox Use Only

There is no 'royal road' to geometry.

Euclid, said to Ptolemy I

1. Introduction and Goals

a. A Brief History of visible mathematics: writing mathematics, mathematical computation

This section consists of preliminary considerations on how mathematical language is currently used and how this relates to computer manipulation of mathematical language.

1. History and background- Leibniz's dream, Ada Lovelace's elaboration of it.

1. Form and content in mathematics: In the integrated environment we have to deal with both. Some math notations correspond to programs, others don't.

2. Inherent ambiguities in mathematical notation: e.g. is F' a variable or a derivative? The poverty of simple rules such as "every variable evaluates to itself unless it has some other value assigned": probably we don't want dF/dx to evaluate to zero.

3. Mathematics is intrinsically open-ended. You have to make the system extensible, allow for the incorporation of new no

4. Kaltofen's example of definition by pattern: giving the ijth element of a matrix.

5. The scope and impact of TeX.

6. Historical sketch of typesetting practice (cite Knuth, "Math Typography").

7. Historical sketch of the evolution of numercial computing.

6. Historical sketch of computer algebra.

8. Where we are now: PC tools, multimedia documents, etc.

b. CaminoReal Goals

1. Make mathematical expressions a citizen of documents manipulable with the Tioga multimedia editor, in a fashion consistent with existing Tioga editing paradigms (WYSIWYG, mouse, selections).

2. Offer access to the functionality of existing algebra systems, (a) in a manner consistent with the the documentation function of 1., (b) leveraging as much as possible off the paradigms and facilities of the PARC and Cedar environments, (c) presenting a user interface that incorporates the modern structuring of mathematical software (Scratchpad, Views).

3. Integrate 1. and 2. to offer "active" document capabilities: mathematical form letters, proofreading.

4. Offer the mathematical software environment of choice to support our imaging environment: 2D illustration, 3D rendering and modelling, plotting.

5. Present a well-structured, integrated, repertoire of mathematical software to the user.

c. The setting for our work: a synopsis of Programming Environments at Xerox PARC

1. General

a. Bit-mapped displays, mice, servers, networks

b. The WYSIWYG philosophy of editing - there is disagreement about whether it suits math, but our point of view is that if we can convert Tioga documents to TeX and let the final polishing be done there, that's fine.

2. Cedar

a. The legacy of Mesa - strongly typed language, modules.

c. Cedar Imaging software.

b. In our environment, everyone is a Cedar programmer, so its not unreasonable to make writing (hopefully simple) Cedar programs the mechanism for extending the system. Also, its functionality is available through public interfaces for incoporation into larger program units.

3. Lisp

4. Smalltalk

a. No connections anticipated in near term.

d. Organization of this paper

Since the design of CaminoReal has been strongly influenced by the goal of being consistent with the Cedar programming environment, and since it is implemented in Cedar, we begin in Section 2 with a brief description of the Cedar programming environment.

We discuss prior work last, since it won't be clear what prior work is relevant until we have presented CaminoReal.

2. The Basic Architecture of CaminoReal

a. Basics

Function as a Middleman to do the necessary handshaking when a user wants to do algebra on WYSIWYG math expressions. Don't attempt to rewrite the algebra engines themselves. Piggback off what already exists in Tioga, e.g. WYSIWYG multi-media editor, Artwork machinery (see Appendix for details on Tioga Artwork).

Produce TeX output for the fine tuning that may be wanted for the final stages of document preparation. CaminoReal aims to support the evolving document, not the tweaking of the final version.

Math Servers on a network. Crucial for extensibility, e.g. to allow access to supercomputers, other specialized servers.

b. The need for a Universal interchange language for mathematics

1. Things that a universal interchange language for mathematics must include: (1) a minimal set of programming language constructs (control and data structures), (1) formatting information, (1) representation of Domains, (1) the state of a mathematical server on the network.

2. Historical sketch of typesetting languages for mathematics: Eqn, TeX, SGML

3. Historical sketch of algebraic description languages for mathematics: postfix/prefix, lambda calculus, Lisp, Martin's ideas, APL, Scratchpad, Foderaro.

3. The Mathematical Expression Editor

a. Tioga

CaminoReal is used in conjunction with the general Cedar document editor, i.e. Tioga.

b. CaminoReal's Mathematical Expression Editor

6. Mathematical Expressions and Documents

a. Survey of Tioga.

b. Applications - mixing text, equations, and graphics (i.e. examples of CaminoReal equations in Gargoyle illustrations)

c. Towards multimedia documents.

Seems like in general, the most you want for editing math "in place" is to easily be able to pop up an editor tool containing the object, because math can grow or shrink when edited. You would then edit in the mathediting tool, and then perhaps indicate in the document some box into which the object is to be squeezed when put back into the document. So for CaminoReal, there should be some way to indicate to Tioga that you want to edit an expression (e.g. Control-something), which then pops up a CaminoReal tool containing the expression; you edit it, hit ReturnToDocument, and it goes back in (Tioga remembers where it goes). This seems like an alternative to the Chameleon "layers" approach.

4. Mathematical Expressions and Documents

a. The fonts and sizes used in displaying an expression should by default be taken from some environment (e.g. a document Style), and be overridable. Thus the CR editor has defaults for fonts and sizes to use in displaying an expr; when you put the expression into a document, you get the current settings from the environment.

5. The AlgebraStructures package: Organizing Computational Mathematical Software

a. Domains

Principle for integration - we should apply the Domains idea in the realm of numerical software as well as algebraic.

b. Object-Oriented programming. A "Category" (a la Scratchpad or Views) is just something we put on the proplist.

The issue of specifications checking, axioms, correctness of the system: We don't try to offer a Scratchpad-like programming language, but instead offer a collection of domain and object constructors to both the programmer and user, that enable object-oriented programming of algebraic objects. In other words, I bite off only a certain chunk of algebraic functionality (what Maple provides, for example), and I try to provide clean, well-structured access to that functionality through the client and user interfaces of CaminoReal. I claim that if I build my system correctly, then it will be able to catch client and user run-time errors without needing a special algebraic specifications checking mechanism. The system is extensible, and guidelines for doing so are provided, but I don't attempt to check whether those guidelines are actually followed, i.e. those who extend the system have to check their own work.

c. How we get polymorphism and generic procs

b. Recasting

b. Question for ongoing research: extending the structuring to ever wider bodies of types and algorithms. The immediate areas in an incomplete state are classical applied mathematics (special function, complex analysis), and physics (tensors). An interesting question is how far can one go with this approach, i.e. are there important bodies of math software that can't be organized into this sort of framework?

Note that the ELSE clause is General Expression: if you can't identify an Expression as an element of some more narrow domain, put it there. Note that in Macsyma there are just two nontrivial representations: CRE (Canonical Rational Expression) form and General. Guy speculates that maybe that is appropriate.

6. The Evaluator: the Form -> Content -> Form loop

a. General principle: we must be able to evaluate any expression and convert it to an object in some Domain. In so doing, the form (i.e. display) of the expression may change, e.g. since complex numbers contagious, eval of a matrix containing exact rats and float complexes will convert it to a matrix all of whose elements are float complexes.

b. The problem of finding the least upper bound of a set of Domains

c. The type inference problem

d. Comparisons with Evaluators in other algebra systems, e.g. Macsyma.

9. The Integrated Environment

a. Arguments for why AlgebraStructures notions (Domains) enter into the user interface

1. Domain-driven editing, i.e. facilitate, by narrowing the menu, i.e. the focus, the creation of notations. Prevent the skilled user from unintentionally, or the unskilled user period, from creating nonsensical expressions. Computed documents can prevent "derived errors", i.e. when an expression is computed from some other expression, but there will always be "initial expressions", which the user creates by editing.

2. A good type inference algorithm is a key part of the evaluator which is the integration mechanism between typeless expressions in documents and a type-based algebra system, i.e. the evaluator makes a Form -> Content -> Form loop possible. Presumably Domains are essential to the functioning of the type inference algorithm and evaluator. Users may want to override or control the way their notations get evaluated, to do so, they will need to learn how the builtin mechanisms work, i.e. learn about Domains.

3. The CaminoReal user who is a making sophisticated use of a Domain-oriented algebra system (e.g. Views, Scratchpad) over the net as a math server, may well need to talk about domains in his interactions with that system. Thus CaminoReal must provide some mechanism for describing Domains.

b. Algebra server interface issues

a. Algebra system state: general policy - algebra system state is maintained locally; every time we use the system we prepend a full description of state to the command, i.e. we make no assumptions about what state the system is in when we use it. Thus we don't use its history, or environment, facilities for example. This may seem extreme but it seems likely to be the only way to support multiple algebra systems. Thus we have to come up with a system-independent specification of "algebra system state"; when we call any particular system, CaminoReal knows how to map its system-independent state into a state specification for that particular system.

b. Exception handling?

c. Applications

1. Automated Proofreading of technical documents, mathematical form letters

2. Active notebooks and drafts, e.g. generalized plotting, constructing Galois group of a given regular polygon.

10. Prior work

a. Early work at Xerox PARC: Ralph Kimball's Alto Expression Editor, the Star/Viewpoint Expression Editor.

b. Interesting historical point - there seem to be no significant interactive numerical systems, i.e. there isn't a tradition of interactive systems there. Probably due to Fortran vs. Lisp.

11. Future plans

a. Should work on ability to scan in math from printed pages

b. CaminoReal should be the gateway to accessing "Applied Geometry" and "Geometric Reasoning" software from Cedar.

A general feature we want to support: when appropriate (e.g. as it is for Computational Geometry, and isn't for Geometry Theorem Proving), to allow the user to use the same high-level algorithms (e.g. convex hull) while switching between different underlying arithmetic models (e.g. floating point, exact rational, Yao-Greene finite precision).

Classes of software:

a. Rendering, plotting - topologically reliable curve and surface display

b. Geometry Theorem Proving

This has evolved to the point of canned modules to plug into your computer algebra system. This software is now at the level of being able to prove many standard theorems of elementary Euclidean Geometry

c. Computational Geometry software

E.g. convex hull, convex decomposition, etc.

d. Geometric modeling

e. Robot motion planning

Scenario: quickly implement and animate a motion planning algorithm.

Acknowledgements

Thanks to Michael Plass for enlightenment on Tioga and other matters. Thanks to Ken Pier for the "point and stuff" part of the CaminoReal-Tioga interface. Thanks to the members of the PARC Computer Science Laboratory for using CaminoReal.

References

Selected References on Mathematical Typesetting

Bell Telephone Laboratories, "The Preparation and Typing of Mathematical Manuscripts", Third Revised Edition, 1979.

Knuth, Donald, "Mathematical Typography", Bull. AMS (New Series), March 1979, V. 1, No. 2, 337-372.

Palais, Richard, Column on Technical Wordprocessing, Notices of the AMS, ongoing.

Swanson, E., "Mathematics into Type: Copying, Editing, and Proofreading of Mathematics for Editorial Assistants and Authors", American Mathematical Society, Revised Edition, 1979.

Markup Languages for Representation of Mathematics (Form-focused)

Association of American Publishers, Electronic Manuscript Series, "Markup of Mathematical Formulas", 1985.

Kernighan, B.L., Cherry, L, "A system for typesetting mathematics", CACM, 18 (March 1975), 151-157.

Knuth, D.E., "The TeXBook", Addison-Wesley, 1984.

Algebraic Languages for Representation of Mathematics (Content-focused)

Foderaro, J.K., "The Design of a Language for Algebraic Computation Systems", Report No. UCB/CSD 83/160, Computer Science Division (EECS), UC Berkeley, August 1983, 81pp. (Ph.D. Thesis)

Jenks, R., "A language for computational algebra", Proc. ACM 1981 Symposium on Symbolic and Algebraic Computation, Snowbird, Utah, Aug 5-7, 1981, pp. 6-13. Report RC8930, Math. Science Dept., IBM TJ Watson Research Center, July 14, 1981.

Martin, William, "Symbolic Mathematical Laboratory", Ph.D. thesis, MIT, Jan. 1967.

Old work on Computer Input and Output of Mathematics

Anderson, Richard, "Computer Recognition of Hand-Drawn Math" (not quite right), Harvard Ph.D. thesis, 1965?

Martin, William, "Symbolic Mathematical Laboratory", Ph.D. thesis, MIT, Jan. 1967.

Martin, William, "Computer input/output of mathematical expressions.", Proc. Second Symp. on Symbolic and Algebraic Manipulation (SIGSAM '71), ACM, pp. 78-89.

Selected References on Technical Document Production Systems

Knuth, D., "The TeXBook", Addison-Wesley, 1984.

M. Spivak, "The Joy of TeX", Addison-Wesley, 1986.

Selected References on Computer Algebra

Fenichel, An online system for mathematics (?), Harvard Ph.D., 60's.

Hearn, A., The Personal Algebra Machine, Proc. IFIP '80, North-Holland, Amsterdam, 1980, pp. 620-628.

R. Pavelle, M. Rothstein, and J. Fitch, "Computer Algebra", Scientific American, 245, 6 (December 1981), pp. 136-152.

S. Watt, Parallel algorithms for computer algebra, Ph.D., University of Waterloo, 1984

Selected References on Numerical Computation

Dongarra, J., and Grosse, E., "Distribution of Mathematical Software via Electronic Mail", Comm. ACM, 30,5 (May 1987), pp. 403-407.

Selected References on Mathematical Hardware

Hewlett-Packard 28C Calculator

Report on the Interset 2000 System, Seybold Report on Publishing Systems, February 2, 1987, pp. 1-18.

Interleaf system? , referenced by Allan Katz

Selected References on Programming Environments and Distributed Computation

Swinehart, D.C., Zellweger, P.T., Beach, R.J., Hagmann, R.B., "A Structural View of the Cedar Programming Environment", Report CSL-86-1, Xerox Palo Alto Research Center, June 1986, 74pp.

Selected References on Object-Oriented programming

Bobrow D. et al, "CommonLoops: Merging Lisp and Object-Oriented Programming", OOPSLA Proceedings, 1986.

M. Stefik and D. Bobrow, "Object-oriented programming: themes and variations", AI Magazine, VI, 4, Winter 1986, pp. 40-62.

Selected References on User Interfaces

S. Card and T. Moran, "User technology: from pointing to pondering", ACM Conf. on Personal Workstations, 1986, pp. 183-197

Shneiderman, B., "The Future of Interactive Systems and the Emergence of Dirct Manipulation", Behav. Inf. Technol. 1, 2 (1982), 237-256.

Furnas, G., "Generalized Fisheye Views", "Human Factors in Computing Systems", CHI-86 Conference Proceedings, ACM, 1986, 16-23.

Selected References on Integrated Systems for Mathematical Work

Calmet, J. and Lugiez, D., "A Knowledge-Based System for Computer Algebra", ACM SIGSAM Bulletin, V. 21, No. 1, Issue #79, pp. 7-13.

Bloomberg, D. and Hogg, T., "Engineering/Scientific Workstation Project", Internal Report GSL-87-01, P87-00001, Xerox Palo Alto Research Center, January 1987.

Klerer, M. and Reinfelds, J., "Interactive Systems for Experimental Applied Mathematics", Academic Press, New York, 1968, 472 pp

Martin, William, "Symbolic Mathematical Laboratory", Ph.D. thesis, MIT, Jan. 1967.

PC Magazine, The Scientific PC: Software for Problem Solving", April 14, 1987, pp. 155ff.

Wells, M. B. and Morris, J. B. (eds.), Proceedings of a Symposium on Two-Dimensional Man-Machine Communication, ACM SIGPLAN notices, Vol 7, No 10, October 1972.

Evaluation of Mathematical Expressions

MathLab Group, "Macsyma Reference Manual", Version 9, Laboratory for Computer Science, MIT, December 1977, Chapter 3.

Domain and/or Object-oriented Computer Algebra Systems

Abdali, S.K., Cherry, G.W., Soiffer, N., "An Object-Oriented Approach to Algebra System Design", Proc. 1986 Symp. Symbolic and Algebraic Computation (B. Char, ed.), ACM, pp. 24-30.

A. Fortenbacher et al, "An Overview of the Scratchpad Language and System", Document Number Pre-Release V0M11, Mathematical Sciences Department, Knowledge Systems, Computer Algebar group, IBM TJ Watson Research Center, April 1987, 116pp.

Soiffer, N., "A Perplexed User's Guide to Andante", MS, UC Berkeley, 12+1 pp, November, 1981.

User Interfaces for Computer Algebra Systems

Abdali, S.K., Cherry, G.W., Soiffer, N., "On the Road to Better Computer Algebra System Interfaces", TR #CR-87-26, Computer Research Laboratory, Tektronix Laboratories, Beaverton OR, March 1987, 10pp.

Foderaro, J.K., "Typesetting MACSYMA Equations", in Proc. of the 1979 MACSYMA Users Conf, V.E. Lewis (ed), Washington DC 345-361, also, UCB MS Project Rpt. EECS Dept. 1978.

Fateman, R., "TeX Output from Macsyma-like systems", MS, 5pp, University of California, Berkeley, May 1987.

Foster, G., "User interface considerations for algebraic manipulation systems", Report No. UCB/CSD 84/192, Computer Science Division (EECS), University of California, Berkeley, June 1984.

Foster, G., "DREAMS: Display REpresentation for Algebraic Manipulation Systems", Report No. UCB/CSD 84/193, Computer Science Division (EECS), University of California, Berkeley, April 1984.

Leong, B. "Iris: Design of a User Interface Program for Symbolic Algebra", Proc. 1986 Symp. Symbolic and Algebraic Computation (B. Char, ed.), ACM, pp. 1-6.

C.J. Smith and N. Soiffer, "MathScribe: A User Interface for Computer Algebra Systems", Proc. 1986 Symp. Symbolic and Algebraic Computation (B. Char, ed.), ACM, pp. 7-12.

User Interfaces for Technical Document Production; Mathematical Expression Editing

Kimball, R., "Formula User Interface Issues", Internal memo, Xerox PARC, March 8, 1978.

McGregor, S., "Desktop Formula Frames Implementation", Xerox Office Products Division Internal Memo, November 1978, 13pp.

McGregor, S., "Star Formula Implementation", Xerox Office Products Division Internal Memo, November 1978, 3pp.

McGregor, S., "Tasks for Implementing Formulae in Star", Xerox Office Products Division Internal Memo, August 1980, 4pp.

Quint, V., "An interactive system for Mathematical Text Processing", Technology and Science of Informatics, V. 2, #3, (1983), pp. 169-179.

Quint, V., "Interactive Editing of Mathematics", Proc. First International Conference on Text Processing Systems, 24-26 October 1984, Dublin, Ireland, Boole Press, Dublin, 1984, pp. 55-68.

Schelter, W.F., "Sample INFOR Display", MS, Department of Mathematics, University of Texas-Austin, August 1986, 11pp.

User Interfaces for Numerical Systems

G. Culler, "Mathematical laboratories: a new tool for the physical and social sciences", ACM Conf. on Personal Workstations, 1986, pp. 59-72, reprinted from Klerer and Reinfelds 1968 (op. cit.)

Rice, J. and Rosen, S., "NAPSS, Numerical Analysis and Problem Solving System", Proc. ACM 21st National Conference, Los Angeles, 1966, ACM Publication P-66, (1966), p. 51ff.

Appendix - An overview of the Tioga artwork machinery