Network Working Group D. Arnon Request for Comments: 1019 Xerox PARC September 1987
This memo is a report on the discussion of the representation of equations in a workshop at the ACM SIGGRAPH Conference held in Anaheim, California on 30 July 1987. Distribution of this memo is unlimited.
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. 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 such systems. However, the growth of separate Mathematical Typesetting, Multimedia Electronic Mail, Numerical Computation, and Computer Algebra communities, each with its own conventions, threatens to prevent these systems from being built.
To be specific, little thought has been given to unifying the different expression representations currently used in the different communities. This must take place if there is to be interchange of mathematical expressions among Document, Display, and Computation systems. Also, tools that are wanted in several communities (e.g., WYSIWYG mathematical expression editors), are being built independently by each, with little awareness of the duplication of effort that thereby occurs. Worst of all, the ample opportunities for cross-fertilization among the different communities are not being exploited. For example, some Computer Algebra systems explicitly
associate a type with a mathematical expression (e.g., 3 x 3 matrix of polynomials with complex number coefficients), which could enable automated math proofreaders, analogous to spelling checkers.
The goal of the Workshop on Environments for Computational Mathematics was to open a dialogue among representatives of the
Computer Algebra, Numerical Computation, Multimedia Electronic Mail, and Mathematical Typesetting communities. In July 1986, during the Computers and Mathematics Conference at Stanford University, a subset of this year's participants met at Xerox PARC to discuss User Interfaces for Computer Algebra Systems. This group agreed to hold future meetings, of which the present Workshop is the first. Alan Katz's recent essay, "Issues in Defining an Equations Representation Standard", RFC-1003, DDN Network Information Center, March 1987 (reprinted in the ACM SIGSAM Bulletin May 1987, pp. 19-24), influenced the discussion at the Workshop, especially since it discusses the interchange of mathematical expressions.
This report does not aim to be a transcript of the Workshop, but rather tries to extract the major points upon which (in the Editor's view) rough consensus was reached. It is the Editor's view that the Workshop discussion can be summarized in the form of a basic architecture for "Standard Mathematical Systems", presented in Section II below. Meeting participants seemed to agree that: (1) existing mathematical systems should be augmented or modified to conform to this architecture, and (2) future systems should be built in accordance with it.
The Talks and Panel-Audience discussions at the Workshop were videotaped. Currently, these tapes are being edited for submission to the SIGGRAPH Video Review, to form a "Video Proceedings". If accepted by SIGGRAPH, the Video Proceedings will be publicly available for a nominal distribution charge.
One aspect of the mathematical systems vision that we explicitly left out of this Workshop is the question of "intelligence" in mathematical systems. This has been a powerful motivation to systems builders since the early days. Despite its importance, we do not expect intelligent behavior in mathematical systems to be realized in the short term, and so we leave it aside. Computer Assisted Instruction for mathematics also lies beyond the scope of the Workshop. And although it might have been appropriate to invite representatives of the Spreadsheets and Graphics communities, we did not. Many of those who were at the Workshop have given considerable thought to Spreadsheets and Graphics in mathematical systems.
Financial support from the Xerox Corporation for AudioVisual equipment rental at SIGGRAPH is gratefully acknowledged. Thanks are due to Kevin McIsaac for serving as chief cameraman, providing critical comments on this report, and contributing in diverse other ways to the Workshop. Thanks also to Richard Fateman, Michael Spivak, and Neil Soiffer for critical comments on this report. Subhana Menis and Erin Foley have helped with logistics and documentation at several points along the way.
Information on the Video Proceedings, and any other aspect of the Workshop can be obtained from the author of this report.
The Workshop had four parts: (1) Talks, (2) Panel Discussion, (3) Panel and Audience discussion, (4) and Live demos. Only a few of the systems presented in the talks were demonstrated live. However, many of the talks contained videotapes of the systems being discussed.
The talks, each 15 minutes in length, were:
The Panel discussion lasted 45 minutes. The panelists were:
Richard Fateman, University of California at Berkeley
Richard Jenks, IBM Yorktown Heights
Michael Spivak, Personal TeX
Ronald Whitney, American Mathematical Society
The panelists were asked to consider the following issues in planning their presentations:
A Panel-Audience discussion lasted another 45 minutes, and the Demos lasted about one hour.
Other Workshop participants, besides those named above, included:
We postulate that there is an "Abstract Syntax" for any mathematical
expression. A piece of Abstract Syntax consists of an Operator and
an (ordered) list of Arguments, where each Argument is (recursively)
a piece of Abstract Syntax. Functional Notation, Lisp SExpressions,
Directed Acyclic Graphs, and N-ary Trees are equivalent
representations of Abstract Syntax, in the sense of being equally
expressive, although one or another might be considered preferable
from the standpoint of computation and algorithms. 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".
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.
We 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.
1) EDs - Math Editors
These edit Abstract Syntax to Abstract Syntax. A particular system may have editors that work on some other representations of mathematics (e.g., bitmaps, or particular formatting languages), however they do not qualify as an ED components of a SMS. An ED may be WYSIWYG or language-oriented.
2) DISPs - Math Displayers
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, fix 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(s) in Abstract Syntax. We are not attempting here to foresee, or limit, the selection mechanisms that different DISPs may offer, but only to require that a DISP be able to communicate its selections in Abstract Syntax.
3) COMPs - Computation systems
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.
4) DOCs - Document systems
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.
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.
The boundaries between the component types are not hard and fast. For
example, 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 module to qualify as an SMC is its ability
to read and write Abstract Syntax.
Matrix[ [1,0,0], [0,1,0], [0,0,1] ]
while the Abstract Syntax expression:
Matrix[5, 5, DiagonalRow[1, ThreeDots[], 1],
BelowDiagonalTriangle[FlexZero[]],
AboveDiagonalTriangle[FlexZero[]]]
might encode a 5 x 5 matrix which is to be displayed with a "1" in the (1,1) position, a "1" in the (5,5) position, three dots between them on the diagonal, a big fat zero in the lower triangle indicating the presence of zeros there, and a big fat zero in the upper triangle indicating zeros.
express themselves in standard Abstract Syntax.
Plus[a,b,...]
Minus[a]
Minus[a,b]
Times[a,b,...]
Divide[<numerator>, <denominator>]
Power[<base>, <exponent>]
PartialDerivative[<expr>, <var>]
Integral[<expr>, <var>, <lowerLimit>,<upperLimit>] (limits optional)
Summation[<<summand>, <lowerLimit>, <upperLimit>] (limits optional)
A particular algebra system may read and write nonstandard Abstract Syntax. For example:
Polynomial[Variables[x, y, z], List[Term[coeff, xExp, yExp, zExp], ...
but, it should be able to translate this to an equivalent standard representation. For example:
Plus[Times[coeff, Power[x, xExp], ...
The paradigm we wish to follow is that of the genetic code: A mathematical expression is like a particular instance of DNA, and upon receiving it a DISP consults the appropriate formatting database to see if it understands it. If not, the DISP just
"passed it through unchanged". The expression sent over the wire may be accompanied by directives or explanatory information, which again may or may not be meaningful to a particular DISP. In reality, formatting databases may need to contain Expert System-level sophistication to be able to produce professional quality typesetting results, but we believe that useful results can be achieved even without such sophistication.