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:

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:

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.

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.

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

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.

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].

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

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.

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.

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.

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:

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.

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):

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].

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.

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:

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:

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:

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.