CAMINOREAL
CAMINOREAL
CAMINOREAL
EP88 DRAFT -- August 17, 1987 2:31:23 pm PDT -- EP88 DRAFT
EP88 DRAFT -- August 17, 1987 2:31:23 pm PDT -- EP88 DRAFT
EP88 DRAFT -- August 17, 1987 2:31:23 pm PDT -- EP88 DRAFT
CaminoReal: A User Interface for Mathematics
Dennis Arnon, Carl Waldspurger, Kevin McIsaac, and Richard Beach
© Copyright 1987 Xerox Corporation. All rights reserved.
Some style issues and conventions
avoid capitalization unless proper name
avoid quote marks; perfer to use look-o for examples
computer algebra vs symbolic algebra name for the field
Abstract: Four broad categories of Mathematical Software are Computer Algebra (Symbolic Mathematics), Numerical Computation, Mathematical Typesetting, and "Technical Electronic Mail" (i.e. e-mail that contains 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 system for integrated, interactive, technical documents and computations. 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. Printing and management of other document components, such as text and graphics, is provided by Tioga. For computation, CaminoReal offers a small builtin algebra package based on the notions of Domains and Objects, plus access to "Algebra Servers" on a network. Mathematical expressions are passed between CaminoReal, Tioga, and Algebra Servers in pure functional notation. Our current Algebra Servers are the Reduce, SMP, and SAC-2 Computer Algebra systems.
CaminoReal is structured in accordance with a recently proposed standard architecture for Mathematical Systems. We summarize this architecture in this paper.
This paper combines an exposition of CaminoReal as it currently is, with suggestions for desirable changes or extensions. The current version of CaminoReal has at least touched on most issues we consider to be within our scope, so we will typically describe the existing features, and then how they might be altered.
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 — Preliminary Version — DRAFT
There is no 'royal road' to geometry.
Euclid, said to Ptolemy I
Preface for Cedar Users
To see the mathematical expressions in this document (when reading it online or printing it), be sure you have a running CaminoReal.
1. Introduction
vision of integrated system for mathematics
examples of notebooks and technical papers
four separate developments:
symbolic algebra or computer algebra (Reduce, Macsyma, SMP, etc.)
numerical computation (IMSL libraries)
multimedia electronic mail (Diamond? who has math?)
mathematical typesetting (eqn, TeX)
Since the 1950's, many researchers have worked to realize the vision of natural and powerful computer systems for interactive mathematical work. Nowadays this vision can be expressed as the goal of an integrated system for symbolic, numerical, graphical, and documentational mathematical work. One aspect of this vision of particular interest to us is the idea of "living" notebooks and technical papers. We want a system that supports both the exploration of technical ideas through computations, and the production of an evolving technical document that describes them. Recently the development of personal computers (with high resolution screens, window systems, and mice), high-speed networks, electronic mail, and electronic publishing, have created a technological base that is more than adequate for the realization of these integrated systems. However, the growth of separate Mathematical Typesetting, Multimedia Electronic Mail, Numerical Computation, and Computer Algebra communities, each with its own standards, is tending to impede their realization.
CaminoReal is prototype
instance of an architecture: standard mathematical systems
interchange protocol
CaminoReal is a prototype system for the integration of documents, editing, and computation involving mathematics. Its design is an instance of an architecture for Standard Mathematical Systems that we recommend be adopted by others. The thrust of this architecture is to provide a standard means for combining diverse system components, namely communication by means of mathematical expressions expressed in a pure functional notation.
CaminoReal in Cedar . . .
CaminoReal 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. Actual document production (e.g. printing, management of other document constituents such as text and graphics) is provided by Tioga. The screen, mouse actions and keyboard input is managed by the Cedar viewers package. A viewer is a window that can be scrolled and resized. A viewer can have buttons and pop-up menus that invoke commands. The mouse is used to point and select text or expressions. CaminoReal supports interactive, syntax-directed, two-dimensional, WYSIWYG editing of mathematical expressions, placing/fetching such expressions in/from Tioga documents, and algebraic manipulation of expressions. Algebraic computation can be performed using either a small builtin package, or using well-known algebra systems such as Reduce, SMP, and SAC-2 over a network. The internal algebra package is based on an object-oriented paradigm that supports polymorphic procedures. For example, one can easily create and do simple arithmetic on matrices of polynomials with complex number coefficients, or matrices of such matrices, etc.
notion of interactive technical documents,
or perhaps integrated documents,
or even active electronic documents
examples of extensions to spreadsheets and mathematical form letters or tools for proofreading mathematics notation
CaminoReal supports the creation of "interactive" technical documents. For example, the user can browse a (nicely typeset) draft of a technical document on the workstation screen, select, edit and compute with mathematical expressions in it (besides editing text and graphics, of course), and insert the resulting expressions back into the document. One can extend this to the notion of a "computed document", i.e. a document with imbedded computations. Two particularly useful flavors of computed documents are spreadsheets and mathematical form letters.
2. Standard Mathematical Systems - a Proposed Architecture
This material is adapted form the Report of the Workshop on Environments for Computational Mathematics. (reference, perhaps to Computer Graphics?)
postulate abstract syntax for any mathematical expression
operator and arguments
We postulate that there is an "Abstract Syntax" for any mathematical expression. 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 equivalent representations of Abstract Syntax. For example, the functional expression Plus[Times[a,b],c] represents the Abstract Syntax of an expression that would commonly be written a*b+c.
standard mathematical component of standard mathematical system
A "Standard Mathematical Component" (abbreviated SMC) is a collection of software and hardware modules, with a single function, which if it reads mathematical expressions, reads them as Abstract Syntax, and 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.
four types of components: ED, DISP, COMP, DOC
We may identify at least four possible types of components in an SMS. Any particular SMS may have zero, one, or several instances of each component type. The connection between two particular components of an SMS, of whatever type, is via Abstract Syntax passed over a "wire" joining them.
EDs - Math Editors
edit the abstract syntax
expression editors
retain the mathematical semantics
many existing mathematical notation editors do not qualify (e.g. Viewpoint math!)
These edit Abstract Syntax to Abstract Syntax. It's fine to have an editor in your particular system that works on some other representation, e.g. bitmap, particular formatting language, however it does not qualify as an ED component of an SMS. An ED may be WYSIWYG or language-oriented.
DISPs - Math Displayers
displayers render an abstract syntax
combination of hardware and software
many provide translation to existing math formatters, e.g. TeX or eqn
interactive positioning permitted to select subexpressions
These are suites of software packages, device drivers, and hardware devices that take in an expr in Abstract Syntax and render it. For example, (1) the combination of an Abstract Syntax->TeX translator, TeX itself, and a printer, or (2) a plotting package plus a plotting device. A DISP component may or may not support "pointing" (i.e. selection), within an expression it has displayed, e.g. a printer probably doesn't, but terminal screen may. If pointing is supported, then a DISP component must be able to pass back the selected subexpression in Abstract Syntax. An example of an acceptable Abstract Syntax expression for indicating a subexpression of expr is Child[Child[expr,2],3].
COMPs - Computation systems
are these symbolic computation systems? I assume so
problem of state;
binding of values or expressions to names
setting of global flags that control computation or selection of algorithms
why are we talking about this level of detail now and here?
what should we be talking about?
Examples are numerical libraries and computer algebra systems. There are questions as to the state of a COMP component at the time it receives an expression. For example, what global flags are set or what previous expressions have been computed, that the current expression may refer to. However we don't delve into these hard issues at this time.
DOCs - Document systems
document preparation systems that incorporate mathematical notation
various names
user interface a nontrivial problem
These are what would typically called "text editors", "document editors", or "electronic mail systems". We are interested in their handling of math expressions. In reality they manage other document constituents as well, e.g. text and graphics. The design of the user interface for the interaction of math, text, and graphics is a nontrivial problem, and will doubtless be the subject of further research.
typical SMS: an ED and a DISP
more integration permitted
to support incremental update of expressions from edits
desirable to have program interface (abstract interface)
so ED would accept edit functions in abstract syntax
similarily DISP displays abstract syntax and possibly selects subexpression
A typical SMS will have an ED and a DISP that are much more closely coupled than is suggested here. For example, the ED's internal representation of Abstract Syntax, and the DISP's internal representation (e.g. a tree of boxes), may have pointers back and forth, or perhaps 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. For example, the ED should be able to receive a standard Abstract Syntax representation for an expression, plus an editing command in Abstract Syntax (e.g.. 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.
boundaries between components are not hard and fast
The boundaries between the component types are not hard and fast, e.g. an ED might support simple computations (e.g. simplification, rearrangement of subexpressions, arithmetic), or a DOC might contain a facility for displaying mathematical expressions. The key thing for a given software, or software/hardware module to qualify as an SMS component of one of these four types is its ability to read and write Abstract Syntax.
Miscellaneous notes:
1. COMPs, e.g. Computer Algebra systems, should be able to communicate in Abstract Syntax. Thus existing systems should have translators to/from Abstract Syntax added to them.
To really have this work nicely, we need standard function names. A particular algebra system may recognize nonstandard Abstract Syntax, e.g. Polynomial[Variables[x,y,z], List[Term[coeff,xExp, yExp, zExp], ... but it must know that to truly make this standard, it needs to translate into something like Sum[Product[coeff, Pow[x,xExp], ...
2. A DOC must store the Abstract Syntax representations of the expressions it contains. Thus it's easy for it to pass its expressions to EDs, COMPs, or DISPs. A DOC is free to store additional expression representations, for example, a tree of Boxes, a bitmap, or a TeX description.
3. DISPs will typically have local databases of formatting information. To actually render the Abstract Syntax, the DISP checks for display rules in its database. If none are found, it paints the Abstract Syntax in some standard way. Local formatting databases can be overridden by formatting rules passed over the wire, expressed in Abstract Syntax.
It is these local databases, or knowledge of the display environment in which you happen to be at the moment (e.g. typesetting for a particular journal). The paradigm is the genetic code: a mathematical expression is like a particular instance of DNA. You consult your local database to see if you understand it, and if not, just "pass it through unchanged". An expression sent over the wire may be accompanied by explicit directives or explanatory information. Again, these may or may not be meaningful to a particular DISP.
4. With the use of the SMC's specificed above, it becomes easy to use any DOC as a logging facility for a session with a COMP. Thus improvements in DOCs, e.g. browsers, level structuring, active documents, audit trails, will automatically give us better logging mechanisms for sessions with algebra systems.
5. Note that Abstract Syntax is human-readable. Thus any text editor can be used as an ED. However as M. Spivak said - you shouldn't have to look at it if you don't want to. Many users will only want to interact with mathematics that has a textbook-like appearance; they should not need to know that their system may talk Abstract Syntax within itself, or to the outside world.
6. A. Katz's RFC (cited above) distinguishes the form (i.e. appearance) of a mathematical expression from its content (i.e. meaning, value). We do not agree that such a distinction can be made. We claim that Abstract Syntax can convey form, meaning, or both, and that its interpretation is strictly in the eye of the beholder. Meaning is just a handshake between sender and recipient.
3. Editing Expressions
3.1. The Basics of Editing Expressions
basic requirements:
single incremental parser for editing and computing expressions
single across editor and algebra system
incremental to update display after each keystroke
complication by insertion of templates along with ordinary parsing
<<example?>>
The user interface should have a single incremental parser that can be used to process the user's keyboard input of math, functional expressions from an algebra system, and the "semantics" stored with a math expression in a document (which may or may not just be functional notation). It must be incremental since the user expects the screen to be updated after each keystroke when he's typing. The task is complicated by the editor's need to offer template insertion (e.g. via popup menus) in combination with ordinary parsing, as other syntax-directed editors do, and cursor motions in expression trees. The current CaminoReal parser does not fully meet these specs.
3.1. Character sets
interesting issue, finessed by Xerox character set
complete binding of character codes to positions in large (2- or 3-byte) code space
each font potentially provides all glyphs in Xerox character set
question: how to input symbols beyond keyboard keytops?
modifying key, such as control or meta
visible keyboard selection or menus of selectable characters
name lookup translations
We use the Xerox Character Set, so there are no "special symbols". All the symbols we may have need of are in a single font.
How do we allow input of special symbols such as Pi or Sigma? A tentative solution is the use of a modifying key such as the control key. The roman alphabet is mapped into the greek alphabet through the modifier key. The standard keyboard has at least 49 keys. The greek alphabet has 25 characters which leaves 24*2(Upper and lower case) for other symbols (maths). These special symbols will be converted to a unique ascii token for internal use, ie > -> Gt, p -> Pi.
3.2. Terminology for Editing Expressions
PlaceHolder:
A placeholder is an empty Expression which needs to be filled in, and looks like X in your CaminoReal viewer. It is intended to be similar in appearance and function to placeholders () in Tioga. (jargon)
Template:
An expression containing placeholders.
Replace:
"Replace old with new" means to delete the old Expression and insert a new Expression in its place.
Wrap:
"Wrap a template around an expression" means to replace the expression with the template then replace one of the placeholders in the template with the deleted expression.
3.3. Selecting Expressions
3.3.1 What can you select?
CaminoReal allows you to select arguments but not symbols (expressions?)
some esoterica about which is which
example of summation symbol:
select any of subexpressions or entire expression
cannot select only the sigma symbol
(empirical experiment proves you cannot enter summation with no upper limit in CaminoReal!)
expressions are trees
operators and atoms
selection operations to navigate through tree
four selection types: primary, copy (secondary), move (pending delete), keyboard type-in (caret)
CaminoReal considers each class of Expression (e.g. summation, integral) to be composed of Arguments and Symbols. An Argument is a subExpression, i.e. something which is recursively an Expression; a Symbol is a glyph (e.g. the sigma symbol, the integral sign) which is part of the rendering of that notation, but is not itself an Expression. The basic rule is that you can select Arguments, but not Symbols.
If for example you are editing a summation Expression, you can select any of the summation's subExpressions (lowerlimit, upperlimit, summand) or the entire summation Expression. You cannot, however, select the sigma symbol by itself in the summation (clicking on the sigma will actually select the entire summation Expression).
Expressions can be thought of as trees with operators at the nodes and atoms at the leaves. CaminoReal provides ways to move through the Expression tree with a minimum of fuss. Operations are available which allow you to: extend a selection to include its parent Expression (moving up the tree), narrow a selection to a child Expression (moving down the tree), and change a selection to select a sibling Expression (same level in tree). Thus, both CaminoReal and Tioga have hierarchical tree-like structures and commands for selecting subtrees and leaves.
There are four selection types, similar in appearance and function to Tioga selections:
Primary selection:
Selected Expression is highlighted by rendering it white on black, which is inverted from the normal black on white (just like Tioga).
Copy selection:
Selected Expression is highlighted in dark gray.
Move selection:
Selected Expression is highlighted in light gray.
Keyboard (KB) selection:
This selection type cannot be applied by the user. The selected Expression is highlighted using horizontal gray lines. This selection type is automatically invoked when there is an active keyboard entry for an atom (e.g. a number or a variable). Its purpose is mostly as an indicator. However, when template wrapping is invoked from the keyboard, an active keyboard selection becomes the primary selection.
3.3.2 How can you select?
select with mouse or keyboard
pointing finds smallest selection using bounding box of subexpressions
You can select Expressions using either the mouse or keyboard. To select with the mouse, simply point at the Expression you wish to select and click the appropriate button. The selected Expression will be the smallest Expression (greatest depth in tree) which contains the point specified by the mouse. If you think of each Expression as being enclosed by a bounding box, this is the Expression enclosed by the smallest box which contains the point specified by the mouse.
The following mappings are currently used:
Single Clicks:
Left => Primary Select
Shift Left => Copy Select
Ctrl Left => Move Select
Double Clicks:
Left => Extend Primary Selection to Parent
Shift Left => Extend Copy Selection to Parent
Ctrl Left => Extend Move Selection to Parent
Keyboard selection actions:
), ], }, Ctrl-P => Primary Select the Parent of the current Keyboard or Primary Selection.
Ctrl-I => Primary Select entire Current Expression (entire contents of the viewer in which mouse sits)
Ctrl-K => Primary Select the Hot Child (Kind) of current Primary Selection.
Ctrl-L, ', => Primary Select sibling (Lateral movement) of current Keyboard or Primary Selection.
Ctrl-H => undo previous keystroke; Primary Select entire Current Expression
Ctrl-X => swap Primary and Move selections (can't really use in keyboard input, since mouse required to make Move selection)
Ctrl-M => Convert the Keyboard Selection into the Primary Selection
3.4. Entering Expressions
3.4.1 Using Menus:
expressions created using two schemes: replace and wrap
replaces primary selection with new object, selected from menu
wraps primary selection by deleing selection and replacing with a template and then fill first placeholder with deleted selection
example: select a, wrap with + using template x+x, replace first place holder with a, becomes a+x
ReplaceWithObject:
use pop-up menu for type of object
for some types, value comes from Tioga text selection
for variables, name comes from Tioga text selection
for parseRope option, object comes from parsing Tioga text selection
(useful for command files?)
for objects with dimensions, e.g. matrix, dimension comes from another menu
Replaces the primary selection with a mathematical object. The type of object is chosen from a pop-up menu. Depending on the type of object, the actual expression is either given a default value (rational, complex), obtained from additional pop-up menus, or obtained from a Tioga viewer selection (variable, bool, integer, real). For example, "ReplaceWithObject Integer" tries to get an integer from an active text selection, and "ReplaceWithObject GreekVariable" provides a pop-up menu of choices for the variable.
"ReplaceWithObject Variable" may allow you to get characters into an Expression when no other way seems available. Whatever is in the active text (Tioga) selection, i.e. any valid text string, will be picked up and stuffed when you bug the "Variable" entry of the pop-up menu.
The "parseRope" option will parse the (Tioga)-selected string as though its characters were typed individually at the keyboard.
For sets, sequences, vectors, matrices, and blocks (see below for definition of a block), the dimensions are chosen from pop-up menus. (note: CaminoReal can support arbitrarily big matrices, but the current user interface restricts the maximum dimension to be 10 x 10.)
The matrix is initialized by setting all elements = 0. This is useful when entering sparse matrices, and isn't really a hindarance when you aren't.
ReplaceWithOperator:
Brings up a pop-up menu listing classes of operators. You select a class of operators from these menus, and then get another pop-up menu listing the actual templates. Then the primary selection is replaced by the template for the operator you have selected.
WrapWithOperator:
Similar to ReplaceWithOperator, but wraps a template around the primary selection instead of replacing it. In other words, the primary selection is used to fill in a placeholder in the template. This placeholder is usually the first (e.g. "a" in "a + b") or most important (e.g. integrand in integration) argument to the template.
Using the keyboard:
keyboard input replaces primary selection
some types typed directly: integer, real, variable names
some operators are mapped onto the keyboard
sum, difference, negation, product, subscript/superscript, parens, braces, factorial, exists, for all, logical, relations
CaminoReal allows keyboard input for some of the most common expression types.
Integer, Real, and Variable atoms can be typed directly into a (Primary- or Keyboard-)selected Expression. As mentioned in the section on selections, the active Keyboard selection will be selected and highlighted using horizontal gray lines. This selection is terminated as soon as a Primary selection is made or any editing function is invoked (you can always select outside of an Expression to get rid of the Keyboard selection). A Real number must begin with a digit (e.g. 0), and not just a decimal point.
Typing operator characters into a selected Expression performs a template wrap around the currently active Keyboard or Primary selection. Currently supported keys, with their semantics, are:
+ => binary sum
— => unary difference
- => binary negation
* => binary product
/ => binary fraction
^ => binary pow
← => binary subscript
? => binary function of one argument
( => unary parentheses
{ => unary curlyBrackets
! => unary factorial
$ => unary exists
@ => unary forAll
& => binary and
| => binary or
~ => unary not
= => binary eqFormula
> => binary gtFormula
< => binary ltFormula
# => binary notEqFormula
pseudo infix implies automatic wrapping of templates around expressions
selection operations, especially select parent, very useful to avoid requiring mouse to make suitable selections
example of x^2<CTRL-P>+1<CTRL-P>=0
unary operators have suitable wrapping behavior, either prefix or postfix
example of ($x
For the binary operators, this gives "pseudo-infix" input. For example, to enter "a + b", simply select a placeholder, then type "a", "+", "b". What is really going on is that the operation "+" is wrapped around the Expression "a", and the placeholder for the augend is auto-selected. Typing the "b" fills in the augend placeholder. The ctrl-P "select parent" operation is very useful for keyboard input to avoid switching beteen the keyboard and the mouse. For example, to enter
X,
use the keystrokes "x", "^", "2", ctrl-P, "+", "1", ctrl-P, "=", "0".
For the unary operators, the input paradigm is "prefix" or "postfix", depending on the operator. For example to enter
X,
type the keystrokes "(", "$", "x".
3.5. Editing Expressions
editing paradigms based on Tioga selection operations
selections may exist in any CaminoReal viewer (future: any document fragment that is mathematics)
copy
to primary selection from secondary selection
move
to primary selection from secondary selection and delete secondary selection (replaced by placeholder)
swap
primary and secondary selections exchanged
Copy
Make a Primary selection, hold down the Shift key, make a Copy selection, release Shift, and the Primary selection will be replaced by the Copy selection. The Copy selection is unchanged.
Move
Make a Primary selection, hold down the Control key, make a Move selection, release Control, and the Primary selection will be replaced by the Move selection. The Move selection is replaced by a Placeholder.
Swap
Intended to mimic Tioga's swap. Make a Primary selection, hold down Control, hit and release the "X" key (continue holding down Control) make a Move selection, release the Control key, and the Primary and Move selections will be interchanged.
The selections (i.e. operands) for Copy, Move, and Swap can either lie within a single Camino viewer, or in two different Camino viewers. Note that Copy, Move, and Swap in CaminoReal are performed very much as in Tioga.
4. Expressions and Documents
desire is to integrate mathematical content into document as a document object
CaminoReal implementation limited by Tioga to creating passive artwork objects
strategy is to have several CaminoReal tools for editing and manipulating mathematical objects
convenience operators to deal with math objects in Tioga documents
stuff math object into Tioga document (ToTioga)
extract math object from Tioga document (FromTioga)
[ignore issue of scaling for now]
4.1. ToTioga button
To put an expression into a Tioga doc, make a primary selection in the Camino viewer, make a selection in the Tioga doc, and bug "ToTioga". The expression will be placed in the document immediately preceding the Tioga selection. The value in the ScratchPad will become its PointSize in the document.
The ScratchPad must either contain a REAL constant, or be empty, when you do this. If nonempty, the value it contains will become the PointSize of the expression in the document. 20.0 is the default if the ScratchPad is empty, and in general is a good initial choice.
Note that scaling an expression in a Camino viewer (with the Scale button) has no bearing on the PointSize an expression gets when put into a Tioga document; only the value in the ScratchPad controls that.
4.2. FromTioga button
To fetch an expression from a Tioga doc, make a primary selection in the Camino viewer, (character) select the expression in the Tioga doc, and bug "FromTioga". The ScratchPad will get set to the PointSize.
4.3. SetPtSize button
To adjust the PointSize of an expression in a document, put the value you want in the ScratchPad, (character) select the expr in the doc, and bug "SetPtSize".
4.4. Examples
Here are some sample paragraphs containing Expressions. This is a plain line of text which happens to include an expression X , and is above some Expressions:
X
X
Note that Expressions can easily be moved or copied using Tioga commands.
Let's place this expression here:
X
4.5. Printing the document
Create an interpress file with the command "TiogaToInterpress <doc>.tioga" and print it in any of the standard ways.
4.6. Issues for future work
Should be able to edit expressions in place in the document.
5. Computation
CaminoReal provides algebra service in two ways:
some resident algebra facilities (both a research project and a convenience)
some network-accessible algebra services
Cedar AlgebraStructures package
domain oriented
expressions, variables, integers, booleans, rationals, reals, complex numbers
domain structures
structure of specified domain
set, family of sets, sequences, vectors, matrices, polynomials
therefore, matrix of matrix of polynomials of sequence of variables of rationals
evaluation of mathematical expressions to some domain result
[recording succession of evaluations is the basis of math proofreader and audit trails]
evaluation choices
evaluate selection in place
evaluate Tioga math object in place (does from, eval, to operations)
operator choices
operation choices appropriate for domain displayed in pop-up menu
operation choices for working domain
environment
one global environment for CaminoReal across all documents, sigh!
introduce assignment (name binding operator)
metafunction to kill assignments
Computation from algebra servers
paradigm is: select expression, invoke algebra system, result replaces selection
requires converting selection to abstract syntax (I presume) appropriate for algebra system
example of integral, abstract syntax for SMP and Reduce, result from Reduce
5.1. Computation with the Resident Algebra Facilities
5.1.1 Domains
1. What they are
The Ground Domains are:
Expressions (i.e. general expressions)
Variables
Bools
Integers (Mesa INTs)
Rationals (BigRats)
Reals (Mesa REALs)
Complexes (built from Mesa REALs)
The Domain Structuring Operations are:
SingleSet
FamilyOfSets
Sequences
Vectors
Matrices
Polynomials
2. Creating Domains
Bug the working domain button in the control panel. This will pop-up a menu of choices, including all the Ground Domains and Domain Structuring Operations. You must initially select a Ground Domain; a short name for it (e.g. Z for Integers) will appear in the text viewer next to the Working Domain button.
Matrices
These are rectangular matrices of specified size, whose entries are elements of the current Working Domain. When you select Matrices, you get a pop-up menu to select the size. Similarly for Vectors, Sequences, and Sets.
Polynomials
For any polynomial, we need to keep track of what variables it's a polynomial in. This is accomplished by associating a variable sequence with the polynomial. This is a sequence of Ropes (the variables). In order for scanning to work, variables should be Cedar identifiers. A variable sequence should be written as comma-separated variables enclosed in parentheses (whitespace ok anywhere except within a variable). For example, "(x,y,z)".
What you do is enter the variable sequence into the ScratchPad, then bug WorkingDomain, and bug Polynomials in the menu. The coefficient domain is what was previously in the "WorkingDomain".
5.1.2 Evaluation
This is the most basic way to do algebra with the built in package. Any Expression can be evaluated; if CaminoReal doesn't know enough algebra to do something interesting with it, it just returns it unevaluated.
The result of an evaluation always belongs to some Domain. General Expressions (denoted MExprs) is the catchall if nothing narrower can be determined.
The semantics of Eval are: To evaluate a function of args (which every non-atomic Expression can be viewed as), we first (recursively) evaluate the arguments, then look for the function as a Method in some Domain (typically the Domain to which the first (evaluated) argument belongs), and if we find it, apply it to the evaluated arguments. If not found, then look for it as a Method in some other Domain (e.g. the Domain to which the next evaluated arg), etc. As a catchall we look for the desired Method in all the Domains that the system currently knows about.
Miscellaneous note: polynomial gcd's are currently done by the SAC-2 package on the Vax (via the Bridge). For uninteresting reasons, you'll get an error if the variables of polynomials whose gcd's you try to compute do not consist entirely of upper case letters.
EvalPrimaryInPlace button
Evaluate the Primary selection and replace it by the result. Domain of the result is shown in the "Result Domain" viewer.
EvalTiogaInPlace button
Evaluate the current CaminoReal Expression selected in a Tioga document, and replace it by the result. Domain of the result is shown in the "Result Domain" viewer.
Evaluation from the keyboard (Control-V)
Control-V evaluates the current Primary selection in place. Same as EvalPrimaryInPlace button, except that the Domain of the result is NOT shown in the "Result Domain" viewer.
5.1.3 Operations
OpPrimaryInPlace button
Evaluate the Primary selection, put up a pop-up menu of operations appropriate for that Domain, get the appropriate number of arguments for the selected operation from CaminoReal selections (e.g. for sum, the second arg is the CaminoReal Copy selection), and replace the Primary selection by the result of the operation.
OpWDinPlace button
Put up a pop-up menu of operations appropriate for the current Working Domain, get the appropriate number of arguments for the selected operation from CaminoReal selections, and replace the Primary selection by the result of the operation.
OpPrimary, OpWD buttons
Put the result in a new CaminoReal viewer instead of replacing Primary Selection.
5.1.4 The Environment
Currently there is just one environment in place across all documents and all CaminoReal viewers.
A variable is placed into the environment by evaluating an assignment statement. For example, the evaluation of
X
will place a variable X into the environment with value X .
Evaluation of the functions
X
and
X
will respectively remove the values of all variables, and of the variable X, from the environment. Note the quoting of X in the second example to avoid evaluation.
Do not evaluate self-referential expressions such as X; this will loop.
5.1.5. The type inference problem
"Type inferencing in computer algebra using term rewriting systems and sub-typing relation" by Comon and Lugiez
NYU thesis (cited by Abdali)
Watt's "unification" algorithm
5.2. Computation with Algebra Servers
The general loop is: you make an appropriate Primary selection, LEFT- (for SMP) or MIDDLE-click (for Reduce) the "Algebra" button, and the result of passing the Primary selection as a command line to SMP or Reduce will replace the Primary selection.
CaminoReal Expressions are passed to an algebra system by first converting them to an appropriate linear representation; similarly, the output from an algebra system is received in linear notation and parsed into CaminoReal internal notation.
LEFT-clicking the "ToASRope" button will show you the SMP linear representation that CaminoReal will create for a given expression, and RIGHT-clicking it will show you the Reduce string that CaminoReal will create for it. For example, if the current Primary selection is:
X
then LEFT-clicking ToASRope will give:
Int[Div[Minus[1, Mult[2, Pow[x, 3]]], Pow[( Plus[1, Pow[x, 3]] ), 2]], x]
and MIDDLE-clicking it will give:
int(quotient(difference(1, times(2, expt(x, 3))), expt(( plus(1, expt(x, 3)) ), 2)), x)
If we MIDDLE-click the Algebra button to send this off to Reduce, after about ten seconds we get back
X
in our CaminoReal viewer.
5.3. Issues for future work on computation
extension of CaminoReal to multiple algebra requests outstanding
a potential solution outlined using strips or panes and mulitplexing requests to the algebra server (have we discussed an algebra server?)
Re: implementation of algebra multiprocessing: Assume that CR windows have been improved so that there is one CR tool, and multiple "panes" or "strips", each containing an expr and having a biscroller (such strips could be implemented as separate viewers). The simplest reasonable rule is that when you request some algebra in a strip, that strip blocks until the algebra finishes, but you can go on processing (and perhaps requesting algebra) in the other strips. Assume that a dedicated stream is open throughout a CR session. There is a manager on the Unix end of this stream, who receives algebra requests from Cedar over it, and sends back algebra replies over it. A manager on the Cedar side receives these replies and forwards them to the appropriate strips.
issue of multiple algebra processes
keep them to a minimum (Unix process overhead, I guess)
each process starts with clean state or environment
results returned via stream or file depending on reliability constant: 30 secs
We will permit multiple simultaneous algebra processes in Unix, but we want to keep the number to the minimum. Also, for simplicity, we'll follow the rule that each process starts with a "clean" algebra system (e.g. Reduce) state, although one can imagine supporting state maintenance in a future more sophisticated world. Operation is: Unix manager always has a free algebra process available (either starts a new one if necessary, or wipes clean the state of an existing one). When it gets an algebra request, gives it a lock on the algebra process for 30 seconds. Other requests that come in during this time are queued. If the current request finishes in less than 30 seconds, than the result is sent back over the stream, and we go to the request at the head of the queue. If a request doesn't finish in 30 seconds, then a file is set up to receive its output (so partial results won't be lost in the event of a crash), its priority is niced up so that it goes into the background, and the manager goes on to process the next request in the queue. When a background algebra request finishes, the Unix manager marshalls its output and sends it back over the stream to Cedar.
issue of naming algebra system functions
give job to user interface!
It's irritating to have to remember the different names for the same command in different algebra systems. For example, the command to factor is Fac in SMP and Factorize in Reduce. Seems like the user interface should hide such details from the user.
issue of exception reporting
It would be nice if all algebra systems followed a common paradigm for exception reporting. E.g. there could be separate data and message streams when CaminoReal communicates with a remote algebra system.
issue of user query to status of running algebra process
Actually the message stream should be two-way, so e.g. the user can query the state of the algebra system while his remote command is running, or even change it (e.g. abort his command, which currently there's no way to do).
issue of caching communication streams for conversation
Speaking of streams, one way to do communications between CaminoReal and remote algebra systems would be to open data and message streams the first time a user talks to a particular algebra system, and then keep those streams, as well as the remote algebra process, open as long as CaminoReal is alive. Presumably this would cut the overhead of a remote algebra command from 10 seconds to nil. The Cedar Bridge package can apparently be tweaked to do this; I'm unclear about the tradeoffs of this paradigm vs. RPC.
6. Computed Documents
6.1 Introduction
with assignment we get access to environment
with evaluation we get access to computation
sequence of math objects in Tioga documents gives us compuational documents
mathematics can be assigned to environment and computed on-the-fly
two uses immediately obvious:
spreadsheets or mathematical form letters
mathematical proofreading
CaminoReal's expression language supports an assignment statement. Also, expressions assigned to variables are maintained in a symbol table (the Environment). If desired, the math expressions imbedded in a Tioga document can be evaluated prior to being painted, whenever the document is displayed, and so can be defined as functions of other expressions. This makes possible Tioga documents that are spreadsheets or mathematical form letters, or simply computed documents. Having the math in a technical paper computed on the fly minimizes the introduction of typographical errors, and so reduces the burden of proofreading.
6.2. MathEval on/off
global flag to enable computation before painting Tioga math object
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 Computed Documents. The Cedar CommandTool commands "MathEval on" and "MathEval off" do the toggling.
6.3 SpreadSheets
What is a SpreadSheet
The clasical spreadsheet as typified by Lotus-1-2-3 or Excel has the following major notions.
Cells
A cell has knows four things.
i) Its current value. We will refer to this as its value
ii) How to calculate its value. We will refer to this as its formular. This may be a constant such as $100 or an expression involving other values of other cells.
iii) How to format the current value. We will refer to this as its format. For example right justified.
iv) Its name.
Rectangular layout
Cells are arranged in a rectangular grid. The columns and row are indexed by numbers or integers. Conventional the columns are a-z and the rows are the integers starting at 1. A cell is refered to a by its row and column
Manipulation
One is able to alter the formular and and format of a cell, not its name or its value except through the formular. A cell is refered to either by entering its name in a command window or by pointing to the cell and selecting with the mouse. The mouse selection enters the name of the cell into the command window.
Suppose we wish to give cell B2 the formular A2 + B1. We could type the command "B2 = A2+B1" into the command window. Alternatly we can mouse select the cell B2,type "=" from the keyboard, mouse select the cell A2, type "=" from the keyboard, mouse select the cell B1. The use of mouse selection removes the burden of naming the cell and makes the process more intuitive. This will become more apparent when we progress to algebra where one becomes confused between equation numbers and symbols. It is important to note that we do not specify in which order the cells are to be calculated. In fact this is of centeral importants.
Often one can take a formular from one cell and copy it to another cell. The references to other cells may or may not be changed. For example if we copy the formulae for B2 into B3 we might want he gemotric relationships in the formulae to be preserved. That is the formulae reads "B3 = A3+B2". Is is an interesting notion available in most spreadsheets. An other nice feature is to sum, or perform someother operation, over a row, column or block with out listing all the elements.
Evaluation
The from formulae for the individule cells we can produce a Directed Graph for the evaluation of the spreadsheet. Lets restrict the spreadsheet to Acyclic Directed Graphs, we evaluate the cells in the obvious way by starting at the known cells and working back. If we alter a cell the DAG indicates exactly which cells mut be updated. The spreadsheet evaluation can be nicly described in an object oriented way. We ask a cell to evaluate itself. If the cell depends on other cells they are passed the message to evaluate itself. To display a cell we ask the cells to format their data.
We can relax the Acyclic condition by applying a termination condition to the cycle. This could be a number of cycles, in which case we have a natural method for itteration, or some condition to be met by a cell, in which case we have a natural method for conditional loops. A nice application of the cyclic graph might be newton itteration. The cycle is preformed only once. giving an itteration to the correct solution. If the user select one of the cells and asks it to evaluate itself the the cycle is repeated once giving the next itteration. This continues as long as the user desires.
One condition we have swept under the carpet is that the graph is assumed to be static. That is the formular can't evaluate to a cell name. This seems reasonable but further consideration may show useful interperations for this such as branching. This is an area that needs more thought.
Extensions
Free Form Layout
The first extension is to remove the table like format of the spreadsheet. A cell can be placed anywhere on the screen. There is still a dependancy graph for the spreadsheet but the naming convention must change. A solution is to give the cell a name that is created when the cell is created. Any technique used to lable nodes in a graph would suffice. Note the use of pointing becomes much more important. Clearly the copy formulae and preserve geometric relationship is no longer valid! How ever other notions may take its place.
Algebra.
Instead of just numerical evaluation allow general algebra.
6.4 Audit Trails
The basic audit trail scheme in relation to documents is that you maintain an audit trail as a DAG among mathematical expressions, as a separate data structure from a (Tioga) document in which the expressions may actually reside. There are various unresolved issues about the interaction of these structures, e.g. what happens to the screen display of an expression if you delete the node corresponding to it in the audit trail?
The audit trail DAG, i.e. assuming that your space of algebra expressions is managed as an audit trail DAG, provides a basic discipline for the Cedar user interface for algebra multiprocessing, by thinking of it as a database and using standard DB transaction management. Read and write locks on DAG nodes are available; a read lock locks out writers but not other readers, a write lock locks out everyone. When you request algebra on a DAG node, the appropriate kind of lock is put on it and all other affected nodes in the DAG (e.g. a request to recompute a leaf from scratch will write lock all its ancestors). That request is then forked; you can now move to another node in the DAG and do anything consistent with the lock it has at that time (e.g. factor it, which requires read access, which is available unless it has a write lock on it).
It will usually be meaningful and useful to have system-generated "line numbers", i.e. names for expressions, as distinct from mathematical variables. The names are your hooks to previous results for construction of future expressions.
Typical loop is - you have a current node, containing an expr. You pop up a temp window with a copy of that expr, either by value or by reference. You do some "edits" on it, someone listens and records them, when you're done, the temp window goes away, the result goes back into the "document" as a new node with a transaction number, and the arc from the previous node to it is labeled with the actions that bring about that transition.
The resulting structure is a (directed) tree. Obviously many different outcomes are possible if you alter some expression and replay portions of the audit trail, depending e.g. on whether your copies were by value or reference.
6.5. MultiDocuments
1. There is a database, different scripts can print different "readouts" of it. Thus e.g. I can store my working notes along with the paper for publication, but print out either or both.
7. Acknowledgements
Thanks to Rick Beach and Michael Plass for enlightenment on Tioga and other aspects of Cedar. Thanks to Ken Pier for the "point and stuff" part of the CaminoReal-Tioga interface. Thanks to Christian LeCocq for the BridgeSubmit package that enables communication with the UNIX world. Thanks to those in the Computer Science Lab at PARC who have used CaminoReal for their documents and computations, and suggested improvements (what was the collected experience so far? perhaps an additional section). Thanks to Rick Beach, Alan Perlis, and Alan Demers for inspiration.
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 HP-28C Reference Manual
Report on the Interset 2000 System, Seybold Report on Publishing Systems, February 2, 1987, pp. 1-18.
Selected References on Cedar
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., also ACM Trans. on Programming Lang. and Systems (TOPLAS), 1986.
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.
EP88 Outline
1. Introduction
vision of integrated system for mathematics
extend mathematical content within documents to incorporate the math semantics, not just typography; opportunity to compute with the math, not just look at it
examples of notebooks and technical papers with live mathematics
integrate four separate developments:
symbolic algebra or computer algebra (Reduce, Macsyma, SMP, etc.)
numerical computation (Linpack library, IMSL libraries)
multimedia electronic mail (Diamond and Andrew)
mathematical typesetting (eqn, TeX)
CaminoReal is prototype
instance of an architecture: standard mathematical systems
incorporates math notation editor, displayer, computation, and document formatting system
interchange protocol among components in math systems
CaminoReal in Cedar . . .
briefly explain how Cedar provides foundation for CaminoReal
reference integration paper (Donahue)
notion of interactive technical documents based on computation with mathematical semantics
or perhaps integrated documents,
or even active electronic documents
examples of extensions to spreadsheets and mathematical form letters or tools for proofreading mathematics notation
2. Standard Mathematical Systems - a Proposed Architecture
postulate abstract syntax for any mathematical expression
operator and arguments
postulate an architecture for building an integrated mathematical system
use abstract syntax to communicate between components
each component provides interfaces to mix and match
standard mathematical components of standard mathematical system
four types of components: ED, DISP, COMP, DOC
2.1 EDs - Math Editors
tool to edit the abstract syntax representation of mathematics
typical expression editors
may edit visually or in the abstract syntax directly
goal is to retain the mathematical semantics
many existing mathematical notation editors do not qualify (e.g. Viewpoint math!)
2.2 DISPs - Math Displayers
displayers render an abstract syntax to make it human comprehensible in traditional appearance of mathematical notation
combination of hardware and software
many provide translation to existing math formatters, e.g. TeX or eqn
value of interactive positioning permits selection of subexpressions for use by other parts of mathematical system
2.3 COMPs - Computation systems
computation done on both symbolic and numeric representation of mathematics
encompasses traditional symbolic algebra or computer algebra systems
as a component of an SMS, it must accept the abstract syntax representation and produce results in abstract syntax
as part of an interactive system, there is the problem of maintaining state over a session or a document; two issues include:
binding of values or expressions to names
setting of global flags that control computation or selection of algorithms
2.4 DOCs - Document systems
document preparation systems that incorporate mathematical notation
electronic mail should be considered in this category, mail a document, eh?
various names for the system component
user interface a nontrivial problem
2.6 Miscellaneous notes: (some issues unresolved)
issue of standard names for functions across various COMP
e.g. translation or modification of names accepable to system
issue of mathematical objects within documents retaining sufficient semantics, by retiaining abstract syntax; additional representations permitted
issue of formatting mathematical notation
supplied templates may not be sufficient for new notation or unanticipated appearance problems
DISP may provide these extensions; unclear how abstract syntax is decorated with private formatting hints
must be willing to render abstract syntax that it does not understand!
issue of formatting style for mathematics notation
example of in-line equations with solidus or fraction bar, summation limits above/below or as superscript/subscript to sum operator
opportunity for automatic logging
2.5 ???
configuring a standard mathematical system
typical SMS: an ED and a DISP
more integration permitted
to support incremental update of expressions from edits
desirable to have program interface (abstract interface)
so ED would accept edit functions in abstract syntax
similarily DISP displays abstract syntax and possibly selects subexpression
boundaries between components are not hard and fast
3. CaminoReal as a prototype SMS
goal was to build a prototype of an mathematics sytem integrated into a document processing system
built in the Cedar environment which encourages such architectures
major components of CaminoReal
Meddle -- an interactive mathematics editor (ED and DISP)
AlgebraStructures -- an exploratory domain-based algebra system (COMP)
algebra server -- access to existing algebra systems via distributed network protocols (COMP)
Tioga -- a document formatting system with content extensions (DOC)
major goals . . .
interactive editing of math notation, exploring user interface issues
exploring domain-based algebra systems . . .
integrating formatted mathematics with semantics
active documents as logs of sequence of thoughts, living documents, computed documents
3. Editing Expressions
what are the features, novel or otherwise, of the CaminoReal expression editor?
3.1. The Basics of Editing Expressions
basic requirements:
single incremental parser for editing and computing expressions
single across editor and algebra system
incremental to update display after each keystroke
complication by insertion of templates along with ordinary parsing
<<example?>>
3.1. Character sets
interesting issue, finessed by Xerox character set
complete binding of character codes to positions in large (2- or 3-byte) code space
each font potentially provides all glyphs in Xerox character set
question: how to input symbols beyond keyboard keytops?
modifying key, such as control or meta
visible keyboard selection or menus of selectable characters
name lookup translations
3.2. Terminology for Editing Expressions
placeholder, template, replace, wrap
3.3. Selecting Expressions
CaminoReal allows you to select arguments but not symbols (expressions?)
some esoterica about which is which
example of summation symbol:
select any of subexpressions or entire expression
cannot select only the sigma symbol
(empirical experiment proves you cannot enter summation with no upper limit in CaminoReal!)
current system forces you to have different templates for each example
no editor conversions between notations:
changing operator without changing all of the operands
issue of semantics vs appearance of mathematics
expressions are trees
operators and atoms
selection operations to navigate through tree
four selection types: primary, copy (secondary), move (pending delete), keyboard type-in (caret)
select with mouse or keyboard
pointing finds smallest selection using bounding box of subexpressions
3.4. Entering Expressions
expressions created
using two schemes: replace or wrap
using two devices: mouse or keyboard
replace
replaces primary selection with new object, selected from menu
wraps
wraps primary selection by deleing selection and replacing with a template and then fill first placeholder with deleted selection
example: select a, wrap with + using template x+x, replace first place holder with a, becomes a+x
use pop-up menu for type of object
for some types, value comes from Tioga text selection
for variables, name comes from Tioga text selection
for parseRope option, object comes from parsing Tioga text selection
(useful for command files?)
for objects with dimensions, e.g. matrix, dimension comes from another menu
using keyboard
keyboard input replaces primary selection
some types typed directly: integer, real, variable names
some operators are mapped onto the keyboard
sum, difference, negation, product, subscript/superscript, parens, braces, factorial, exists, for all, logical, relations
pseudo infix implies automatic wrapping of templates around expressions
selection operations, especially select parent, very useful to avoid requiring mouse to make suitable selections
example of x^2<CTRL-P>+1<CTRL-P>=0
unary operators have suitable wrapping behavior, either prefix or postfix
example of ($x
3.5. Editing Expressions
editing paradigms based on Tioga selection operations
selections may exist in any CaminoReal viewer (future: any document fragment that is mathematics)
copy
to primary selection from secondary selection
move
to primary selection from secondary selection and delete secondary selection (replaced by placeholder)
swap
primary and secondary selections exchanged
4. Expressions and Documents
desire is to integrate mathematical content into document as a document object
CaminoReal implementation limited by Tioga to creating passive artwork objects
strategy is to have several CaminoReal tools for editing and manipulating mathematical objects
convenience operators to deal with math objects in Tioga documents
stuff math object into Tioga document (ToTioga)
extract math object from Tioga document (FromTioga)
[ignore issue of scaling for now]
5. Computations
CaminoReal provides algebra service in two ways:
some resident algebra facilities (both a research project and a convenience)
some network-accessible algebra services
5.1 Cedar AlgebraStructures package
domain oriented
expressions, variables, integers, booleans, rationals, reals, complex numbers
domain structures
structure of specified domain
set, family of sets, sequences, vectors, matrices, polynomials
therefore, matrix of matrix of polynomials of sequence of variables of rationals
evaluation of mathematical expressions to some domain result
[recording succession of evaluations is the basis of math proofreader and audit trails]
evaluation choices
evaluate selection in place
evaluate Tioga math object in place (does from, eval, to operations)
operator choices
operation choices appropriate for domain displayed in pop-up menu
operation choices for working domain
environment
one global environment for CaminoReal across all documents, sigh!
introduce assignment (name binding operator)
metafunction to kill assignments
5.2 Computation from algebra servers
paradigm is: select expression, invoke algebra system, result replaces selection
requires converting selection to abstract syntax (I presume) appropriate for algebra system
example of integral, abstract syntax for SMP and Reduce, result from Reduce
5.3. Issues for future work on computation
extension of CaminoReal to multiple algebra requests outstanding
a potential solution outlined using strips or panes and mulitplexing requests to the algebra server (have we discussed an algebra server?)
issue of multiple algebra processes
keep them to a minimum (Unix process overhead, I guess)
each process starts with clean state or environment
results returned via stream or file depending on reliability constant: 30 secs
issue of naming algebra system functions
give job to user interface!
issue of exception reporting
issue of user query to status of running algebra process
issue of caching communication streams for conversation
6. Computed Documents
6.1 Introduction
with assignment we get access to environment
with evaluation we get access to computation
sequence of math objects in Tioga documents gives us compuational documents
mathematics can be assigned to environment and computed on-the-fly
two uses immediately obvious:
spreadsheets or mathematical form letters
mathematical proofreading
6.2. MathEval on/off
global flag to enable computation before painting Tioga math object
6.3 SpreadSheets
6.4 Audit Trails