CAMINOREAL: AN INTERACTIVE MATHEMATICAL NOTEBOOK
CAMINOREAL: AN INTERACTIVE MATHEMATICAL NOTEBOOK
CAMINOREAL: AN INTERACTIVE MATHEMATICAL NOTEBOOK
SUBMITTED TO EP88 FOR PUBLICATION
SUBMITTED TO EP88 FOR PUBLICATION
SUBMITTED TO EP88 FOR PUBLICATION
CaminoReal: An Interactive Mathematical Notebook
Dennis Arnon, Richard Beach, Kevin McIsaac, and Carl Waldspurger
© Copyright 1987 Xerox Corporation. All rights reserved.
Abstract: Four broad categories of mathematical software are numerical computation, mathematical typesetting, computer algebra (symbolic mathematics), and ``technical electronic mail'' (mail that contains formatted mathematical expressions). In each of these categories one finds powerful and sophisticated systems. Nonetheless, what one really would like is simultaneous, integrated access to all four types of functionality.
CaminoReal is a working system that addresses this need. It is part of Cedar, the programming environment of Xerox PARC's Computer Science Laboratory, and is used in conjunction with Tioga, Cedar's multimedia document editor. Printing and management of other document components, such as text, graphics, and voice, is provided by Tioga. For computation, CaminoReal offers a small built-in algebra package based on the notions of objects and domains, plus access to ``algebra servers'' on a network. Mathematical expressions are exchanged among CaminoReal, Tioga, and these algebra servers in pure functional notation. Our current algebra servers are the Reduce, SMP, and SAC-2 computer algebra systems. This document has been produced using Tioga/CaminoReal.
Keywords: computational mathematics, document processing, mathematical typesetting, technical documents, mathematics editing, WYSIWYG, user interfaces, direct manipulation, computer algebra, symbolic mathematical computation, object-oriented programming
XEROX   Xerox Corporation
    Palo Alto Research Center
    3333 Coyote Hill Road
    Palo Alto, California 94304

DRAFT — Submitted to EP88 for publication — DRAFT
There is no `royal road' to geometry.
Euclid, said to Ptolemy I
1. Introduction
1.1 Overview of CaminoReal
CaminoReal is a system for direct manipulation of mathematical expressions, whether as part of a technical document or as input and outputs of a computational engine.
CaminoReal supports interactive, syntax-directed, two-dimensional, WYSIWYG editing of mathematical expressions, placing/fetching such expressions in/from formatted documents, and manipulating algebraic expressions. Computation can be performed through the same user interface either by using a small built-in algebra package or accessing well-known algebra systems such as Reduce [Hearn, 1982], SMP [Wolfram, 1985], and SAC-2 [Collins, 1980] over a network. The internal algebra package is based on an object-oriented paradigm that supports polymorphic procedures. For example, with CaminoReal one can easily create and perform simple arithmetic on matrices of polynomials with complex number coefficients, or matrices of such matrices, etc. CaminoReal also provides a testbed for exploring user interface issues concerned with manipulating mathematics within documents.
CaminoReal has much in common with other recent work, but we believe it has two unique features as of this writing in August 1987:
1. The tight coupling of its computation facilities with a sophisticated document system, thereby opening interesting new opportunities for computed and interactive documents (details in sections 3, 4, and 5 below).
2. The accessibility from CaminoReal of a variety of different computational ``math servers'' on our local network (details in section 4 below).
These novel capabilities have been facilitated by building CaminoReal upon the rich base provided by Cedar, the programming environment of the Computer Science Laboratory at Xerox PARC [Swinehart et al. 1986, Donahue 1986]. CaminoReal also depends greatly on Tioga, Cedar's multimedia document editor. Tioga provides document production facilities for printing and managing other document constituents such as text, graphics, and voice. The screen, mouse actions and keyboard input are managed by the Cedar viewers package. A viewer is a window that can be scrolled and resized, and a viewer can have buttons and pop-up menus that invoke commands. The mouse is used to point and select text or expressions.
CaminoReal is a prototype of a recently proposed standard architecture [Arnon, 1987] for so-called ``mathematical systems,'' in which one can edit the mathematical notation interactively, display mathematics in its traditional two-dimensional appearance, compute symbolically or numerically with the mathematical expressions, and format and organize documents containing such mathematical objects. We summarize this architecture in section 2 of this paper.
CaminoReal is composed of three major components:
Meddle, an interactive mathematics expression editor,
AlgebraStructures, an exploratory domain-based algebra system with remote access to other algebra services via distributed network protocols, and
Tioga, the integrated multimedia document production system.
Section 3 below discusses Meddle and Tioga, and section 4 covers AlgebraStructures and additional means of computation. In section 4.2 we explain some of the reasons why we believe that associating domains with mathematical expressions can be a significant help in document creation, proofreading and computation.
CaminoReal supports the creation of ``interactive'' technical documents. For example, the user can browse a typeset draft of a technical document on the workstation screen, select, edit and compute with mathematical expressions in the document (besides editing other document constituents, of course), and insert the resulting expressions back into the document. One can extend this scenario to the notion of a ``computed document,'' that is, a document with imbedded computations. Two particularly useful flavors of computed documents are mathematical form letters and spreadsheets, which we discuss in section 5.
1.2 Previous work
In the 27 years since J.C.R. Licklider presented the notion of man-computer symbiosis [Licklider 1960], there have been continuous efforts to define and build such ``symbiotic systems'' for mathematical work. Clapp and Kain's Magic Paper system [1963], Minsky's MATHSCOPE proposal [1963], and Martin's Symbolic Mathematical Laboratory [1967] appear to be the earliest. The papers of Sammet [1966], Griesmer/Jenks [1971], Sundblad [1974], Ng [1979], Berman/Kulp [1979], Hearn [1980, 1982], Allen/Nix/Perlis [1981], Foster [1984], Engeler [1985], and Fich [1986] chronicle subsequent progress and offer pointers to the future. MathScribe [Smith/Soiffer 1986], MathCAD [MathSOFT 1986], the Dynamicist's Workbench [Abelson 1987], MUFIE [Spirkovska 1986], and the Engineering/Scientific Workstation [Bloomberg/Hogg 1987] are representative examples of recent work.
Following Licklider and most of the works just cited, when we discuss mathematical systems in this paper, we exclude from consideration those aspects that pertain to intelligence, learning, and automated reasoning. These are issues of compelling interest, but we believe that certain more mundane topics deserve greater near-term priority. Much remains to be done before we have satisfactory ``mundane'' systems, and we need good ``dumb'' systems before we try for good ``smart'' ones. Some examples of the sort of ``intelligence'' that we exclude from consideration are: the "mentor" and problem-solving capabilities projected for MACSYMA in section I of Martin/Fateman [1971], the English-speaking MACSYMA Advisor described in Genesereth [1977], the artificial intelligence aspects of the system design in Calmet/Lugiez [1987], the tutoring abilities of the calculus environment described in Suppes et al. [1987], and the theorem proving and heuristic reasoning functionality described in Bundy [1986].
Our work on CaminoReal, like most other current work in this field, leverages off certain hardware and software developments. In hardware, these are: (1) high-resolution screens and printers, (2) pointing devices, such as mice, light-pens and touch-sensitive screens, (3) high-speed networks, and (4) personal computers. Important software developments are: (1) the emergence of large collections of sophisticated and powerful symbolic and numerical software, (2) the rapid diffusion of high-quality electronic publishing systems that utilize the hardware devices just enumerated, and (3) the broad acceptance of certain user interface paradigms for interactive software, such as WYSIWYG editing, direct manipulation [Shneidermann 1983], menus, windows, holophrasting [Koved/Shneidermann 1986], icons, and browsers. Certain of these developments originated at Xerox PARC [Crecine 1986], and most are well integrated into the Cedar environment. We view electronic mail as a form of electronic publishing.
Previous work on mathematical systems has not dealt conclusively with the integration of documents and computation. As detailed in the references [Wactlar 1964], [Foderaro 1979], and [Fateman 1987], a number of translators for computational systems have been built for converting internal representations of mathematical expressions into typeset quality output. However, this has been a one-way path. Once the conversion is done, one cannot subsequently access the expressions for computation. Although a number of interactive WYSIWYG mathematical systems, such as MathCAD [MathSoft 1986], MILO [Avitzur 1987], and INFOR [Schelter 1987], allow the production of some sort of document, only INFOR could be said to support professional-quality typesetting for text and mathematics, but it has no provision for other media such as voice or complex graphics, and is not currently connected to computational systems. Recent multimedia document systems such as Diamond [Crowley 1987] and Andrew [Morris et al. 1986] support a range of media, but are only beginning to support math in documents, and do not yet address the issue of computations with the math in a document. Allen/Nix/Perlis's experimental PEN system [Allen 1981] had some of the same goals as CaminoReal; its design decisions are a continuing resource as we attempt to build systems of broader scope. Spreadsheet systems can be said to integrate documents and computation, but they are typically limited in the types of documents that can be created, and the media that those documents can contain. For us, documents such as multimedia technical papers, automatically generated logs, and audit trails (see section 5.2 for a discussion of the latter), are a crucial part of a mathematical system. Furthermore, we want all of the documents in our system to be ``interactive''. That Tioga/CaminoReal provides a professional-quality publishing system may be gauged by the fact that this document has been produced with it. Tioga/CaminoReal documents are interactive. Hence we call CaminoReal a system for interactive mathematical notebooks.
2. Standard Mathematical Systems
2.1 Introduction
The material in this section is adapted from the Report of the Workshop on Environments for Computational Mathematics [Arnon 1987].
We postulate that there is an abstract syntax for any mathematical expression (cf. [McCarthy 1962]). A piece of abstract syntax consists of an operator and a list of arguments, where each argument is (recursively) a piece of abstract syntax. Functional notation, Lisp s—expressions, directed acyclic graphs, and n-ary trees are isomorphic representations of abstract syntax. For example, the common mathematical expression X could be represented in abstract syntax by the functional notation Plus[Times[a,b],c] or the binary tree
[Artwork node; type 'Artwork on' to command tool]
A ``Standard Mathematical Component'' (abbreviated SMC) is a collection of software and hardware modules, each with a single function, which if it reads mathematical expressions, reads them as abstract syntax, and which if it writes mathematical expressions, writes them as abstract syntax. A ``Standard Mathematical System'' (abbreviated SMS) is a collection of SMC's, which are used together and which communicate with each other in abstract syntax over a ``wire'' joining them. Clearly, there are many possible (isomorphic) abstract syntax representations for a given mathematical expression; we do not assume that the various SMC's within a single SMS all use the same form of abstract syntax.
We identify five possible types of components in an SMS, which we define in section 2.2. Any particular SMS may have zero, one, or several instances of each component type.
2.2 Standard Mathematical Components
2.2.1 ED - Math Editors
An ED component edits abstract syntax to abstract syntax. A particular system may have editors that operate on some other representation of mathematical expressions, such as a bitmap or a formatting language, however such an editor does not qualify as an ED.
2.2.2 DISP - Math Displayers
DISP components are suites of software packages, device drivers, and hardware devices that take in an expression in abstract syntax and render it. Two examples might be (1) the combination of an abstract syntax to TEX translator, plus TEX itself, plus a printer (see [Knuth 1984] for more information on TEX), or (2) a plotting package plus a plotting device. A DISP component may or may not support ``pointing'' (selection) within an expression it has displayed. For example, a DISP that renders onto a printer probably doesn't, but a DISP driving a display screen may. If pointing is supported, then the DISP must be able to pass back the selected subexpression(s) in abstract syntax.
2.2.3 COMP - Computation Systems
A COMP takes in an expression in abstract syntax, performs some computation on it, and returns the result in abstract syntax. Examples of COMP components are numerical libraries and computer algebra systems. When using a COMP as part of an SMS, questions naturally arise as to its state at the time it receives an input expression. For example, what global flags are set, or what previous expressions have been computed that the current expression may refer to? We have no good general answers to these issues at this time, however we describe CaminoReal's current behavior in section 4.2 and some possible modifications in section 4.3.
2.2.4 DOC - Document Systems
The simplest example of a DOC is a text editor for documents in which mathematical expressions are stored in abstract syntax. However a DOC need have no relation to printing, so for example, database, hypertext, and electronic mail systems could all qualify as DOC components. Actually, for our purposes, a DOC is simply a system that manipulates certain data structures (which we think of as "documents" or "databases") in which we can ``park'' multiple math expressions represented in abstract syntax.
Note that if math is editable in place in a document, this is not part of the DOC per se, but part of some ED and perhaps some DISP. The interactions between the various components when an editing operation takes place are: (1) the DISP and the ED process the user's input and modify the abstract syntax representation of the expression, (2) the DISP (if one is involved here, that is, if we are doing more than just showing the text of the abstract syntax) queries the DOC to be given an area (typically a box) in which to display the new expression, and (3) the DISP paints the expression in the specified box.
2.2.5 MAN - System Managers
It is the function of a MAN to coordinate and connect up the ED, DISP, COMP and DOC components that comprise an SMS. Typically an SMS has one MAN component, although it might be able to switch between several. SMS's may vary greatly in the face they present to the user, and such differences may well arise from differing amounts of ``knowledge'' or sophistication possessed by their MAN components. MAN components do whatever is necessary to make the other components play together, and perhaps more besides to make life easier for the user. For example, abstract syntax provides a syntax for a communication language among SMC's, but leaves unspecified the semantics of sentences in this language. Thus, if the function (i.e. operator) names of the abstract syntax used by an ED component differ from those used by a COMP, the MAN provides the translation. The user of a SMS need not, and is encouraged not to, understand the naming conventions of the particular components it contains. As another example, a MAN may have some ``knowledge'' of the relative merits of several COMP components for different tasks, and provide automatic routing of computational requests to the most appropriate one.
2.3 Further notes on the overall architecture
A typical SMS will have a "WYSIWYG expression editor" that consists of an ED and a DISP that are much more closely coupled than is suggested here. For example, the internal representations of abstract syntax in an ED and a DISP (such as a tree of boxes), might have pointers back and forth, or the two may even share a common data structure. This is acceptable, but it should always be possible to access the two components in the canonical decoupled way. This would mean that the ED should be able to receive a standard abstract syntax representation for an expression plus an editing command in abstract syntax, for example, Edit[expr, cmd], and return an abstract syntax representation for the result. Similarly the DISP should be able to receive abstract syntax over the wire and display it, and if it supports pointing, be able to return selected subexpressions in abstract syntax.
The boundaries between the component types are not hard and fast. An ED might support simple computations (such as simplification, rearrangement of subexpressions, and arithmetic), or a DOC might contain a facility for displaying mathematical expressions. The key for a given software, or software/hardware module to qualify as an SMS component of one of the above types is its ability to read and write abstract syntax.
Since abstract syntax is human-readable, any text editor can be used as an ED. However many users of an SMS will only want to interact with mathematics that has a typeset appearance; they should not need to know that their system talks abstract syntax within itself or to the outside world.
Katz's recent proposal [Katz 1987] and others in the typesetting and documents communities, distinguish the form (appearance) of a mathematical expression from its content (meaning or value). It is a thesis of the above architecture that such a distinction cannot usefully be made. Rather, we claim that abstract syntax can convey form, meaning, or both, and that its interpretation is strictly in the eye of the beholder(s). In other words, ``meaning is just a handshake between sender and recipient'' [Arnon 1987].
3. CaminoReal as a prototype SMS: Expression Editing and Basic Documents
3.1. The Expression Editor (ED and DISP)
CaminoReal provides a stand-alone interactive expression editor called Meddle. Its user interface paradigm follows the Tioga document editor quite closely. Multiple selections are made via a mouse pointing device. Operations upon the selections are initiated both from the keyboard and from mouse activation of menu commands. These input actions are parsed by a user interface management system that uses state transitions rather than a formal grammar specification. Incremental modifications to the expression are updated on the display after each keystroke or mouse action. There may be more than one CaminoReal editor tool active at any one time.
The editing paradigm is based on expression trees, with operators as interior nodes and atoms as leaves. For each operator there is a template that defines a notation for that operator. The components of such a notation are zero or more glyphs representing an "operator name", the notations for subexpressions (these are either atomic notations or, recursively, notations of the same sort), and any desired additional glyphs. For example, the summation template specifies that a Greek sigma, S, be used to denote the operator, and that there be three subexpressions: a lower bound, an upper bound and a summand. Such templates are written as procedures in the Cedar language and dynamically loaded with CaminoReal. When templates are first presented, any unfilled expressions are represented by placeholders ( X ).
Thus, if we put up a summation template
X ,
we may then replace its summand placeholder with an indefinite integral template to give
X ,
and then continue to fill in placeholders, eventually arriving at the expression
X .
One may select subexpressions corresponding to subtrees by pointing at the relevant object. This strategy helps ensure that structurally correct expressions are created at the expense of freedom to manipulate all symbols in a notation. The intention is that additional operator templates be added to accommodate new notation rather than permitting the editor to rearrange subexpressions arbitrarily. To facilitate keyboard entry, a complete set of navigational commands is provided, such as select parent, sibling or child of the current selection.
CaminoReal depends on four types of selections: primary, copy, move, and the keyboard caret. These selections may be in any of several CaminoReal tools. The primary selection, made by pointing and clicking with the mouse, establishes the focus of most operations. The copy selection, made by chording the keyboard SHIFT key and clicking the mouse, supplies the argument for copying a subexpression to replace the primary selection. A move selection, made by chording the keyboard CTRL key and clicking the mouse, supplies the argument for moving a subexpression to replace the primary selection. The keyboard caret identifies the expression most recently entered by a keyboard input action and determines where the next keyboard input will be directed.
All editing operations are available from menu buttons and several common ones are mapped onto keyboard keys. CaminoReal uses a pseudo-parser in the Cedar user interface management system to map keystrokes into editing operations. This provides a feel similar to an operator precedence grammar, but is unfortunately not very natural. For example, the <CTRL-P> keystroke invokes the `select parent' operation, so the keyboard sequence x^2<CTRL-P>+1<CTRL-P>=0 is required to get the proper associations for the expression X .
Modifications to the primary selection may occur either by a replace operation or a wrap operation. In a replace operation, the subexpression in the primary selection is deleted and a new subexpression, determined by either a keyboard input action or a menu choice, is inserted in the expression tree. In a wrap operation, the primary selection is retained and replaces one of the placeholders in the new subexpression. For example, consider the first placeholder in the addition template X as the primary selection. Typing the letter `r' replaces the first placeholder with X resulting in the new expression X , and subsequently typing the key `^' wraps a superscript template around the X to produce X (whereas replacing the X with a superscript template would produce X ).
The math expression editor provides several `creature comforts' suited to interactive editing of complex notation, especially the undo command and various scaling operations to improve the readability on low resolution display screens.
Previous mathematical expression editors include the Xerox Star [Kimball 1978], [McGregor 1978a, 1978b, 1980], [Becker 1987], EDIMATH [Quint 1983, 1984], DREAMS [Foster 1984], MathScribe [Smith 1986], MILO [Avitzur 1987], and INFOR [Schelter 1987]. It should be noted that although we, like many others, have been influenced by the Star equation editor, CaminoReal's Meddle editor has been designed and built from scratch in Cedar, and differs from Star's editor in ways both numerous and fundamental.
3.2. Character sets
CaminoReal finesses the challenge of presenting the rich collection of multilingual and technical symbols in mathematics by utilizing the Xerox character code standard [Xerox, 1986]. This standard assigns a unique code (possibly 1, 2 or 3 bytes long) to each symbol and subsumes several international standards, such as ISO and JIS, as well as de facto standards, such as the AMS TEX math symbols [Knuth 1984]. Fonts that conform to the Xerox character code standard will have mathematical symbols in standard code positions. Should a font lack particular symbols, a backstop ``kitchen sink'' font with a glyph for every code may be automatically substituted. Otherwise, the scalable font algorithms in the Cedar Imager (see [Swinehart 1986]) ensure that symbols will appear on the display or in the document with appropriate size and shape information.
Nonetheless, there remains the challenge of identifying and inputing symbols beyond the standard keyboard keys. CaminoReal employs a tentative solution by using menus for special symbols and Greek letters. Other Xerox systems use virtual keyboards to map the keys into arbitrary character codes and abbreviation name lookup translations to map token identifiers into symbols [Becker, 1987], an approach that offers food for thought.
3.3. The Integrated Document Formatter (DOC and DISP)
The integration of mathematical content into a Tioga multimedia document is accomplished by defining a mathematical object class to Tioga. The class specification includes (Cedar) procedures that return a bounding box for layout formatting, and that paint the object into a given imaging context. Thus the CaminoReal DOC component (Tioga) relies on its DISP component (Meddle) to format mathematical notation. The formatted mathematics may appear either as in-line expressions or displayed notation, both of which occur in this paper. Currently Tioga views a mathematical expression in a document as a single, decorated, character, so expressions can be Tioga selections just like any other character. Putting this another way, mathematical expressions in Tioga documents are currently treated as indivisible units: they can be moved around within the document just like text, but there is no way to get at their insides while they reside in the document.
Thus mathematical expressions in a Tioga document cannot currently be edited "in place", but must be extracted into a CaminoReal tool, edited there, and reinserted into the document. However, the expression evaluation operations described in section 4 below, that are part of the CaminoReal tool interface, can operate equally well on Tioga selections and CaminoReal selections. Thus computation on expressions in documents can be performed by simply pointing at them in the document and invoking the desired actions in the CaminoReal tool.
4. CaminoReal as a prototype SMS: Computation
CaminoReal provides two methods for algebraic computation, both integrated through the same tool interface: (1) an experimental domain-oriented package, AlgebraStructures, executed locally in Cedar, and (2) several traditional algebra packages accessed as algebra servers over the network. One may evaluate expressions at several levels of detail, from selected subexpressions to complete expressions to entire documents (see section 5.1 for an example of the latter). The results of evaluating an expression may be alternatively presented in place or in a new CaminoReal tool. The integration of this computation capability and the interactive editing environment, especially utilizing the undo command, provides a very handy tool for exploring complicated expressions.
4.1. The AlgebraStructures Package
The Cedar AlgebraStructures package supports a limited set of algebraic operations defined within a mathematical domain. Ground domains include expressions, variables, integers, booleans, (arbitrary precision) rationals, reals and complex numbers. Domain structuring operations include sets, sequences, vectors, matrices and polynomials. Evaluation of expressions proceeds bottom-up: given an operator and domains for its arguments, a suitable domain for the entire expression is determined. The design of AlgebraStructures was influenced by work such as Abdali/Cherry/Soiffer [1986] and Jenks [1984].
For example, if we create the following expression in a CaminoReal tool:
X
and ask the AlgebraStructures evaluator to evaluate it, then the domain will be determined to be 5 5 matrices of polynomials in x with integer coefficients. If we select the (1,1) element of the matrix and evaluate it, its domain will be determined to be the integers. If we ask for the available operations on the matrix, we get a menu appropriate to its domain, one of whose entries is Determinant. Upon selecting this operation, we get a value of
X ,
whose domain is polynomials in x with integer coefficients.
Domains could be useful for run-time checking that the edited expressions remain in an asserted domain when evaluated. These semantic checks are distinguished from ``compile-time'' checks which prevent the user from making syntactic errors while entering expressions.
Domain information is also useful for guiding a MAN component to choose appropriate algebra servers for particular operations. For example, the AlgebraStructures package currently uses the SAC-2 package for polynomial GCD calculations but does its own integer GCD computations. The design of the algebra system using domains provides a convenient framework for organizing these choices.
4.2. Computation with algebra servers
Algebraic computation is accomplished by selecting an expression or subexpression in a CaminoReal viewer and sending it to a specific algebra server (COMP). The MAN converts the expression to abstract syntax appropriate for the specified algebra server, and that abstract syntax is then passed over the network to the remote computer on which the algebra system exists. The resulting expression from the COMP returns via the same mechanism.
Currently, a new process on the remote machine is invoked for each computation. This takes a few seconds to start up a typical COMP. Furthermore, there is no support for noncomputational communication, such as receiving error messages, querying the help databases or checking the state of a COMP.
Suppose we have the following integral in a CaminoReal editor tool (Cedar users browsing this document online: select the following displayed equation and extract it into a CaminoReal tool):
X
Since AlgebraStructures has no integration algorithms, using it to evaluate this expression yields the result:
X
If we send the selected integral off to Reduce for evaluation, after about ten seconds we get back the expression
X
in our CaminoReal viewer. If we wish, we can display the form into which CaminoReal converts the original integral for transmission to Reduce:
int(quotient(difference(1, times(2, expt(x, 3))), expt(( plus(1, expt(x, 3)) ), 2)), x)
or for transmission to SMP:
Int[Div[Minus[1, Mult[2, Pow[x, 3]]], Pow[( Plus[1, Pow[x, 3]] ), 2]], x]
Thus, CaminoReal allows the user to compute with different algebra systems without knowing the different command names and styles used in each. However, this capability is rather primitive at the moment. CaminoReal's style of interchange of mathematical expressions may be contrasted with the directed-acyclic graphs advocated in the Iris system [Leong, 1986].
4.3. Issues for future work on computation
The ability to access multiple algebra systems through CaminoReal has raised several issues requiring future work.
One issue is the synchronization of outstanding algebra requests with concurrent interactive editing. Because some algebra operations may take a considerable length of time, it is unreasonable to suspend editing completely during such an operation.
It would also be desirable to permit multiple algebra requests from CaminoReal. This raises two issues: (1) the multiplexing of algebra requests to a single server and (2) the definition of the computational state for each request. One might fork a separate process for each request and provide a ``clean'' state for each new request, although the number of processes might be limited with outstanding requests queued.
An irritating problem with existing algebra systems that is partly masked by CaminoReal is the choice of different names for the same command in different systems. Because the design of existing algebra systems precedes the use of abstract syntax, some translation of commands will be necessary.
Additional error handling and error reporting paradigms are also necessary for the convenient integration of algebra servers. At present, the data and message streams are combined into one, making it difficult to identify errors returned by the server.
Long running computations raise the necessity for inquiries to the algebra system for status and progress reporting, as well as additional controls to suspend or abort computations.
The overhead and low bandwidth of communications between clients and servers may make compression and caching of conversations desirable. The underlying communications software in Cedar provides these capabilities, although they are not used at present.
5. Computed Documents
5.1. Mathematical form letters
CaminoReal's expression language supports an assignment statement. Also, expressions assigned to variables are maintained in a symbol table that is global to CaminoReal across all documents and tool instances. This requires metafunctions to kill values in the environment, and special notation to identify unevaluated expressions. For example, X is our current notation for "quote X" (we chose this notation in order to clearly indicate the scope of the quoting). The function X clears the environment, while X removes only the value of the variable X (of course, variables which have not been assigned values evaluate to themselves).
If desired, the math expressions imbedded in a Tioga document can be evaluated prior to being formatted whenever the document is displayed. This evaluation scheme permits expressions to be defined as functions of other expressions, and makes possible Tioga documents that are spreadsheets or mathematical form letters, or more generally, ``computed documents.'' Having the math in a technical paper computed on the fly minimizes the introduction of typographical errors, and therefore reduces the burden of proofreading.
When the EvalBeforePaint flag is off (the default), CaminoReal expressions in a Tioga document are painted just as they are stored. When the EvalBeforePaint flag is on, they are evaluated before being painted. This enables the computing of a document. A Cedar command toggles the EvalBeforePaint flag.
Let's look at an example. The following is the ``definition level'' of a form letter about Sylvester matrices:
====================================
Let F be defined to be X.
Let G be defined to be X.
Let M be the Sylvester matrix of F and G:
X
Then the resultant is the determinant of M, that is
X
====================================
The first two expressions, which define X and X, may be thought of as the ``input data'' to the form letter, in the sense that the last two expressions are functions which depend on the first two. If we now turn EvalBeforePaint on, and simply repaint the document (on screen or printer), we get:
====================================
Let F be defined to be X.
Let G be defined to be X.
Let M be the Sylvester matrix of F and G:
X
Then the resultant is the determinant of M, that is
X
====================================
Suppose now that we edit one of the items of input data, for example, let us suppose that we replace (at the definition level) the expression X by the expression X. Then when EvalBeforePaint is on and we repaint the document, we will get the correctly updated matrix and resultant:
====================================
Let F be defined to be X.
Let G be defined to be X.
Let M be the Sylvester matrix of F and G:
X
Then the resultant is the determinant of M, that is
X
====================================
5.2. Future work on automated proofreading, spreadsheets, audit trails.
The example in the previous section showed the use of the expression environment and evaluation for generating documents. In the future, we expect to refine the use of these tools to provide more proofreading features. For example, suppose in the form letter above that we stored both the unevaluated and evaluated form of each expression. Then one need only do the (possibly expensive) evaluations occasionally, when one wishes to check and verify that the document is correct. The unevaluated expressions could thus be viewed as ``assertions'' about the actual expressions in the document, which can be checked by evaluating them and checking for equality with the evaluated form.
Because spreadsheets may contain formulae and perform computations, it is natural to consider the extension of CaminoReal to provide spreadsheet capabilities in documents. An interesting issue is the provision of a naming scheme for math equations and expressions that is equivalent to the cell naming scheme in spreadsheets. The current use of a global symbol table presents some difficulties. A discussion of spreadsheets that hits on many of the issues of interest to CaminoReal can be found in Davis [1986].
Similarly, an audit trail of computations within a document is a natural extension to the ability to compute expressions. The audit trail would retain the dependency of subexpressions as well as the mathematical operations used to compute the results, so that when one expression is edited, all of the relevant changes elsewhere in the document could be computed and updated. Audit trails could be examined or edited to modify the derivation of new results.
The integration of mathematical content into formatted documents through CaminoReal has provided a rich mother lode for exploring these issues and experimenting with architectures for mathematical systems.
6. Acknowledgements
Thanks to Michael Plass, Ken Pier, and Christian LeCocq for technical assistance. Thanks to those in the Computer Science Lab at PARC who have used CaminoReal for their documents and computations, and suggested improvements, especially James Rauen in his work on algebraic surface display. Thanks to Alan Perlis and Alan Demers for inspiration.
Dennis Arnon has been the chief architect and maintainer of CaminoReal and wrote AlgebraStructures. Carl Waldspurger wrote the expression editor Meddle. Kevin McIsaac has handled the care and feeding of algebra servers and contributed performance improvements and design ideas. Rick Beach had the earliest vision of the system architecture, helped build the connections between Meddle and Tioga, and has provided guidance and moral support throughout the project.
References
Abdali, K., Cherry, G. and Soiffer, N. An Object-Oriented Approach to Algebra System Design, Proc. 1986 Symp. Symbolic and Algebraic Computation (B. Char, ed.), ACM, pp. 24-30.
Abelson, H., The Dynamicist's Workbench: I, Automatic Preparation of Numerical Experiments, AI Memo 955, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, May 1987.
Allen, T., Nix, R. and Perlis, A. PEN: A hierarchical document editor, Proc. 1981 ACM Symp. Text Manipulation, ACM SIGPLAN Notices, 16, 6 (June 1981), pp. 74-81.
Arnon, D., Report of the Workshop on Environments for Computational Mathematics, held at ACM SIGGRAPH Conference, Anaheim, CA, July 27, 1987. Submitted for publication to the ACM SIGSAM Bulletin. Also Request for Comments RFC1019, ARPANET Information Center, SRI-NIC.ARPA, September 1987.
Avitzur, Ron, MILO System [a Macintosh program], Palo Alto, CA 1987.
Becker, J. Arabic word processing, Comm. ACM 30, 7 (July 1987) pp. 600-610.
Berman, R. and Kulp, J., A new environment for computational physics, Proc. 1979 MACSYMA Users Conf. (Washington D.C., June 20-22, 1979), pp. 622-632.
Bloomberg, D. and Hogg, T., Engineering/Scientific Workstation Project, Xerox PARC Technical Report GSL-87-01, Xerox Palo Alto Research Center, January 1987.
Bundy, A., Discovery and reasoning in mathematics, Proc. IJCAI 1985, pp. 1221-1230.
Calmet, J. and Lugiez, D., A Knowledge-Based System for Computer Algebra, ACM SIGSAM Bulletin, 21, 1, Issue #79 (Feb. 1987), pp. 7-13.
Clapp, L. C. and Kain, R.Y., "A computer aid for symbolic mathematics", Proc. AFIPS 1963 Fall Joint Comp. Conf., V. 24, Nov. 1963, pp. 509-517.
Collins, G. SAC-2 and ALDES now available, ACM SIGSAM Bulletin 14 (1980) p. 19.
Crecine, J., The next generation of personal computers, Science, 231 (28 Feb. 1986), pp. 935-943.
Crowley T., Forsdick, H., Landau, M., and Travers, V., The Diamond Multimedia Editor, Proc. USENIX 1987, pp. 1-17.
Davis, R. Knowledge-Based Systems, Science, 231 (28 Feb. 1986), pp. 957-963.
Donahue, J., Integration Mechanisms in Cedar, Proc. of the ACM SIGPLAN 87 Symposium on Language Issues in Programming Environments (Seattle, Wash., Jun. 1985). SIGPLAN Not. 20, 7 (July 1985).
Engeler, E., Scientific computation: the integration of symbolic, numeric and graphic computation, Proc. EUROCAL '85, (B.F. Caviness, ed.), Linz, Austria, April 3-5, 1985, Springer-Verlag, Lecture Notes in Computer Science, 203 (1985), pp. 185-200
Fateman, R. TEX output from MACSYMA-like systems, unpublished manuscript, Department of Electrical Engineering and Computer Science, University of California at Berkeley, July 1987.
Fich, F, Mathematics notepad, private communication, 1986.
Foderaro, J. Typesetting MACSYMA Equations, Proc. 1979 MACSYMA Users Conf. (Washington D.C., June 20-22, 1979), pp. 345-361.
Foster, G, DREAMS:Display Representation for Algebraic Manipulation Systems, Report CSD 84/193, Dept. of EECS, Univ. California Berkeley, April 1984.
Genesereth, M., An automated consultant for MACSYMA, Proc. 1977 MACSYMA Users Conference (Berkeley, California, July 27-29, 1977), NASA CP-2012, pp. 309-314.
Griesmer, J. and Jenks, R., Scratchpad/I - an interactive facility for symbolic mathematics., Proc. Second Symp. on Symbolic and Algebraic Manipulation (SIGSAM '71), ACM, pp. 42-58.
Hearn, A., The Personal Algebra Machine, Proc. IFIP '80, North-Holland, Amsterdam, 1980, pp. 620-628.
Hearn, A., REDUCE - a case study in algebra system development, Proc. EUROCAM '82, Marseille, France, April 1982, Lecture Notes in Computer Science, 144, Springer-Verlag, New York, 1982, pp. 263-272.
Jenks, R.D. A Primer: 11 Keys to New SCRATCHPAD, Proc. EUROSAM 84, Lecture Notes in Computer Science, 174, Springer-Verlag, pp 123-147.
Katz, A. Issues in Defining an Equations Representation Standard, RFC1003, ARPA Network Information Center, March 1987, reprinted in the ACM SIGSAM Bulletin (May 1987), pp. 19-24.
Kimball, R., Formula User Interface Issues, Internal memo, Xerox PARC, March 8, 1978.
Knuth, D.E., The TEXBook, Addison-Wesley, 1984.
Koved L., Shneidermann B., Embedded menus: selecting items in context, Comm. ACM, 29, 4 (April 1986), pp. 312-318.
Leong, B.L. Iris: Design of a User Interface Program for Symbolic Algebra, Proc. 1986 Symp. Symbolic and Algebraic Computation (B. Char, ed.), ACM, pp. 1-6.
Licklider, JCR, Man-Computer Symbiosis, IRE Trans. on Human Factors in Electronics, HFE-1, 4-11 (1960).
Martin, W., Symbolic Mathematical Laboratory, PhD thesis, MIT, Jan. 1967.
Martin, W. and Fateman, R., The MACSYMA System, Proc. Second Symp. on Symbolic and Algebraic Manipulation (SIGSAM '71), ACM, pp. 59-75.
MathSoft Inc, MathCAD System, 1 Kendall Square, Cambridge, MA 02139
McCarthy, J., Towards a Mathematical Theory of Computation, Proc. IFIP '62, North-Holland, Amsterdam, 1962.
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.
Minsky, M., MATHSCOPE, part I - a proposal for a mathematical manipulation-display system, Memo MAC-M-118, Artificial Intelligence Project, Project MAC, MIT, November 1963, 13pp.
Morris, J. et al., Andrew: A Distributed Personal Computing Environment, Comm. ACM 29, 3 (March 1986), pp. 184-201)
Ng, E., Symbolic-numeric interface: a review, Proc. EUROSAM '79, Marseille, France, June 1979, Lecture Notes in Computer Science, 72, Springer-Verlag, New York, 1979, pp. 330-345.
Quint, V., An interactive system for Mathematical Text Processing, Technology and Science of Informatics, 2, 3, (1983), pp. 169-179.
Quint, V., Interactive Editing of Mathematics, Proc. First International Conference on Text Processing Systems, (Dublin, Ireland, 24-26 October 1984), Boole Press, Dublin, 1984, pp. 55-68.
Sammet, J., Survey of formula manipulation, Comm. ACM, 9, 8 (August 1966), pp. 555-569.
Schelter, W.F., INFOR Display Editor, unpublished manuscript, Department of Mathematics, University of Texas-Austin, July 1987, 11pp.
Shneiderman, B., Direct Manipulation: A Step Beyond Programming Languages, IEEE Computer, August 1983, pp. 57-69.
Smith, C.J. 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.
Spirkovska, L., MUFIE: MACSYMA's user friendly interactive executive, MSc report, Department of Electrical Engineering and Computer Science, University of California at Berkeley, July 15, 1986.
Sundblad, Y., Symbolic mathematical systems now and in the future, Proc. EUROSAM '74, ACM SIGSAM Bulletin, 8, 3 (August 1974), pp. 1-8.
Suppes, P. et al., Applications of computer technology to pre-college calculus, first annual report, TR #310, Psychology and Education Series, Institute for Mathematical Studies in the Social Sciences, Stanford University, April 1987.
Swinehart, D.C., Zellweger, P.T., Beach, R.J., and Hagmann, R.B., A Structural View of the Cedar Programming Environment, ACM Trans. on Programming Lang. and Systems 8, 4 (October 1986), p 419-490. Also available as Xerox PARC Technical Report CSL-86-1, Xerox Palo Alto Research Center, June 1986, 74pp.
Wactlar, H. and Barnett, M., Mechanization of Tedious Algebra — the e Coefficients of Theoretical Chemistry, Comm. ACM 7, 12 (December 1964), pp. 704-710.
Wolfram, S., Symbolic Mathematical Computation, Comm. ACM 28, 4 (April 1985), pp. 390-394.
Xerox, Character code standard, Xerox System Integration Standard XNSS 058605, May 1986.