CaminoReal has much in common with other recent work, but we believe it has two unique features as of this writing: the tight coupling of its computation facilities with a sophisticated document system, thereby opening interesting opportunities for computed and interactive documents (details in Sections 3, 4, and 5), and its access to computational ``algebra servers'' on our local network (details in Section 4). These capabilities have been facilitated by building it upon the rich base provided by Cedar, the programming environment of the Computer Science Laboratory at Xerox PARC [Swinehart86, Donahue86]. CaminoReal is closely linked to Tioga, Cedar's multimedia document editor, which provides facilities for printing and management of other document content types such as text, graphics [Pier88], and voice [Zellweger88a]. The screen, mouse actions, and keyboard input for CaminoReal and Tioga are managed by the Cedar viewers package (as for most Cedar tools). A viewer is a window that can be scrolled and resized, and which can have buttons and pop-up menus that invoke commands. The mouse is used to point and select text or expressions.

CaminoReal implements a recently proposed [Arnon87] standard architecture for ``mathematical systems'' that provides for interactive editing of mathematical notation, display of math in its traditional two-dimensional appearance, symbolic and numerical computation, and technical document production. We have found this architecture useful, and we summarize it in Section 2. Section 3 discusses Meddle, CaminoReal's interactive mathematics expression editor, and Tioga. Section 4 covers Algebra-Structures (CaminoReal's built-in algebra package) and algebra servers. In Section 4.2, we explain why 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 work-station screen, select, edit, and compute with mathematical expressions in the document, and insert the resulting expressions back into the document. One can extend this paradigm to the notion of a ``computed document,'' that is, a document with embedded computations. Two examples of computed documents are mathe-matical form letters and spreadsheets, which we discuss in Section 5. CaminoReal is one of several current experiments with active documents in Cedar [Zellweger88b].

Following Licklider and most of the authors just cited, we do not in this paper consider the questions of ``intelligent behavior,'' learning, or automated reasoning in mathematical systems. These are issues of compelling interest, but we believe that certain more mundane topics deserve priority at present. Some examples of topics we exclude are: ``mentor'' and problem-solving capabilities projected for MACSYMA [Martin71], English-speaking MACSYMA Advisor [Genesereth77], artificial intelligence aspects of mathematical systems design [Calmet87], tutoring abilities of a calculus environment [Suppes87], and theorem proving and heuristic reasoning functionality [Bundy86].

CaminoReal, like most similar current work, builds on certain hardware and software developments of recent years. In hardware, these are: (1) high-resolution screens and printers, (2) pointing devices, e.g., mice, (3) high-speed networks, and (4) personal workstations. Important software developments are: (1) the emergence of large collections of sophisticated and powerful symbolic and numerical algorithms, (2) the rapid diffusion of high-quality electronic publishing systems that utilize the hardware base just enumerated, and (3) the broad acceptance of certain user interface paradigms for interactive software, such as WYSIWYG editing, direct manipulation [Shneidermann83], menus, windows, holophrasting [Koved86], icons, and browsers. Certain of these developments originated at Xerox PARC [Crecine86], and most are well integrated into the Cedar environment. We view electronic mail as a form of electronic publishing and, in fact, multimedia, WYSIWYG Tioga documents are routinely exchanged by electronic mail in Cedar.

Previous work on mathematical systems has not dealt conclusively with the integration of documents and computation. There have been a number of translators for converting the internal expression representations of algebra systems into typeset quality output [Wactlar64, Foderaro79, Fateman87]. 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 mathe-matical systems, such as MathCAD [MathSoft87], MILO [Avitzur87], and INFOR [Schelter87], allow the production of some sort of document, only INFOR could be said to support professional-quality typesetting for text and mathematics. However, 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 [Crowley87] and Andrew [Morris86] 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. The experimental PEN system [Allen81] 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 crucial parts of a mathematical system. Furthermore, we want all of the documents in our system to be ``interactive.'' That Tioga and CaminoReal provide a professional-quality publishing system may be gauged by the fact that this document has been produced with them. Tioga/CaminoReal documents are interactive. Hence we call CaminoReal a system for interactive mathematical notebooks.

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 in abstract syntax and which, if it writes mathematical expressions, writes them in abstract syntax. A ``Standard Mathematical System'' (abbreviated SMS) is a collection of SMCs, which are used together and which communicate with each other in abstract syntax over ``wires'' that connect them. In Section 2.2 we identify five possible types of SMCs. Any particular SMS may have zero or more instances of each.

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' recent proposal [Katz87] and others in the typesetting and document communities, distinguish the form (appearance) of a mathematical expression from its content (meaning or value). It is a thesis of the SMS architecture that such a distinction cannot usefully be made. Rather, we claim that abstract syntax can convey form, content, 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'' [Arnon87].

Meddle's internal data structure for mathematical expressions is n-ary trees, with operators as interior nodes and atoms as leaves (i.e., abstract syntax). For each operator, there is a template that defines its displayed notation. The components of such a notation are zero or more glyphs representing the ``operator name,'' a notation for each subexpression (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 subexpressions are represented by placeholders ( X ). CaminoReal tools are initialized to contain an expression consisting of the single placeholder X.

If, for example, we replace a selected placeholder with a summation template (chosen from a menu), we see

One may select a subexpression corresponding to a subtree by pointing at it and clicking the mouse; the actual selection is the ``smallest'' subexpression whose bounding box contains the hit. This strategy insures that Meddle constructs only structurally correct expressions, at the expense of freedom to manipulate all the glyphs in a notation. The intention is that additional operator templates be added to accommodate new notation rather than permitting the user 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.

Meddle depends on four types of selections: primary, copy, move, and keyboard. The primary selection, made by pointing and clicking with the mouse, establishes the focus of most operations. The copy selection, made by chording (holding down) 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 selection is a ``primary selection in progress'' for keyboard input of multi-character identifiers and numbers. If, for example, a primary selection exists and we strike `M' on the keyboard, then a new keyboard selection of X is set and replaces the previous primary selection. If we next strike `a', we get a new keyboard selection of (the identifier) X, whereas if we next strike `^', the keyboard selection X is converted into the primary selection, wrapped (see next paragraph) with a superscript template, and we get X with the primary selection set to the superscript placeholder. When two or more selections are active at one time, e.g., primary and copy, the selected expressions can be in different CaminoReal viewers.

Modifications to the primary selection may occur by either a replace or a wrap operation. In replace, the subexpression in the primary selection is deleted and a new subexpression, determined by either keyboard input or a menu choice, is inserted in the expression tree. In a wrap, 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 X , and subsequently typing the key `^' wraps a superscript template around the X to produce X (whereas replacing the X with a superscript template, chosen from a menu, would produce X ).

Previous mathematical expression editors include the Xerox Star [Xerox86b, Becker87], EDIMATH [Quint83, 84], DREAMS [Foster84], MathScribe [Smith86], MILO [Avitzur87], and INFOR [Schelter87]. The Star editor has existed since the mid-1970's, and although we, like many others, have been influenced by it, Meddle has been designed and built from scratch in Cedar.

Nonetheless, there remains the challenge of entering symbols that do not occur on typical keyboards. CaminoReal employs a tentative solution by using menus for special symbols and Greek letters. Other Xerox systems employ the attractive techniques of virtual keyboards to map keys into arbitrary character codes, and abbreviation name lookup translations, to map token identifiers into symbols [Becker87].

Tioga actually views a math object as a single, decorated character, so expressions can be Tioga selections just as any other character. Putting this another way, mathematical expressions in Tioga documents are indivisible units: they can be moved around within the document just like text, but there is no way to get at subexpressions while they reside in the document. Thus math 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 provided by the CaminoReal tool interface (cf. Section 4) can operate equally well on Tioga 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 a CaminoReal tool.

For example, if we create the following Meddle expression in a CaminoReal tool:

Domains could be useful for run-time checks that mathematical expressions belong to some asserted domain when evaluated. Such ``semantic'' checking is not the same as the ``syntax'' checking that is performed on Meddle keyboard input. 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 such choices.

The design of AlgebraStructures was influenced by VIEWS [Abdali86] and SCRATCHPAD [Jenks84], among others.

Suppose we have the following integral in a CaminoReal tool:

The abstract syntax into which CaminoReal converts the integral for transmission to Reduce is:

It would be desirable to permit multiple concurrent 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. The simplest scheme would probably be to fork a separate process for each request, giving it a clean initial state, with a limit on the number of such processes active at any one time, and a queue for requests that arrive after the limit is reached.

Additional error-handling and error-reporting protocols are necessary for the full incorporation of algebra servers into the CaminoReal user interface. At present, the data and message streams are combined into one, making it difficult to identify errors returned by the server. The overhead and low bandwidth of communications between clients and servers may mandate compression and caching of conversations, facilities which are provided by Cedar's underlying communications software, but are not currently used in CaminoReal.

When CaminoReal's internal EvalBeforePaint switch is off (the default), math expressions in a Tioga document are painted just as they are stored. When EvalBeforePaint is on, they are evaluated before being painted. As might be expected, the order in which expressions are evaluated and painted in the latter case is left-to-right and top-to-bottom order in the Tioga document. A Cedar command is provided for toggling the EvalBeforePaint switch. References to previous expressions in the definitions of later expressions (via the symbol table), coupled with EvalBeforePaint on, make possible Tioga documents that are spreadsheets, ``mathematical form letters,'' or, more generally, ``computed documents.'' For example, here is the ``definition level'' (EvalBeforePaint off) of a sample form letter:

Suppose now that we change the input data, for example, let us replace (at the definition level) the expression X by X. Then by turning EvalBeforePaint on and repainting the document, we get the correctly updated matrix and determinant:

Having the math in a technical paper computed ``on the fly'' minimizes the introduction of typographical errors and thereby lightens the proofreading task.

Because current spreadsheets may contain formulae and perform computations, it is natural to consider the extension of CaminoReal to provide such capabilities in Tioga documents. An interesting issue is how to provide a naming scheme for math equations and expressions that is equivalent to the cell-naming scheme of typical spreadsheets. CaminoReal's current use of a global symbol table presents some difficulties. A recent discussion of spreadsheets [Davis86] raises many of the issues of interest to CaminoReal.

Similarly, an audit trail of computations within a document is a natural extension of 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 was edited, all of the relevant changes elsewhere in the document would be computed and updated. Audit trails could be examined or edited to modify the derivation of new results.