NA Digest Monday, August 31, 1987 Volume 87 : Issue 68

This weeks Editor: Cleve Moler

Today's Topics:

Report of Workshop on Environments for Computational Mathematics

----------------------------------------------------------------------

Date: Mon, 31 Aug 87 17:47:30 PDT
From: Arnon.pa@Xerox.COM
Subject: Report of Workshop on Environments for Computational Mathematics
To: NA@SCORE.STANFORD.EDU

REPORT of the
Workshop on Environments for Computational Mathematics
held July 30, 1987
during the ACM SIGGRAPH Conference
Anaheim Convention Center, Los Angeles, California

Dennis S. Arnon
Xerox PARC
3333 Coyote Hill Road
Palo Alto, California 94304
(415) 494-4425
ARNON.PA@XEROX.COM

I. Introduction

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", RFC1003, Arpa 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 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 III 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.

II. Particulars of the meeting

The Workshop had four parts (1) Talks, (2) Panel Discussion, (3) Panel
and Audience discussion, (4) 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:

1. "The MathCad System: a Graphical Interface for Computer Mathematics",
Richard Smaby, MathSOFT Inc.

2. "MATLAB - an Interactive Matrix Laboratory", Cleve Moler, MathWorks
Inc.

3. "Milo: A Macintosh System for Students", Ron Avitzur, Free Lance
Developer, Palo Alto, CA

4. "MathScribe: A User Interface for Computer Algebra systems", Neil
Soiffer, Tektronix Labs

5. "INFOR: an Interactive WYSIWYG System for Technical Text" , William
Schelter, University of Texas

6. "Iris User Interface for Computer Algebra Systems", Benton Leong,
University of Waterloo

7. "CaminoReal: A Direct Manipulation Style User Interface for
Mathematical Software", Dennis Arnon, Xerox PARC

8. "Domain-Driven Expression Display in Scratchpad II", Stephen Watt,
IBM Yorktown Heights

9. "Internal and External Representations of Valid Mathematical
Reasoning", Tryg Ager, Stanford University

10. "Presentation and Interchange of Mathematical Expressions in the
Andrew System", Maria Wadlow, Carnegie-Mellon University

The Panel discussion lasted 45 minutes. The panelists were:
Richard Fateman, University of California-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:
1. Should we try to build integrated documentation/computation systems?
2: WYSIWYG editing of mathematical expressions
3. Interchange representation of mathematics
4. User interface design for integrated documentation/computation
systems
5. Coping with large mathematical expressions

Panel-Audience discussion lasted another 45 minutes, and the Demos
lasted about one hour.

Other Workshop participants, besides those named above, included:
S. Kamal Abdali, Tektronix Labs
George Allen, Design Science
Alan Katz, ISI
J. Robert Cooke, Cornell University and Cooke Publications
Larry Lesser, Inference Corporation
Tom Libert, University of Michigan
Kevin McIsaac, Xerox PARC and University of Western Australia
Elizabeth Ralston, Inference Corporation

III. Standard Mathematical Systems - a Proposed Architecture

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 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
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 an SMS. An ED may be WYSIWYG or
language-oriented.

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, 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(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.

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.

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, 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 module to qualify as an SMC is its ability to read and write
Abstract Syntax.

IV. Recommendations and Qualifications

1. It is our hypothesis that it will be feasible to encode a rich
variety of other languages in Abstract Syntax, for example, programming
constructs. Thus we intend it to be possible to pass such things as
Lisp formatting programs, plot programs, TeX macros, etc. over the wire
in Abstract Syntax. We also hypothesize that it will be possible to
encode all present and future mathematical notations in Abstract Syntax,
for example commutative diagrams in two or three dimensions. Thus, for
example, the 3 x 3 identify matrix might be encoded as:

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.

2. We assume the use of the ASCII character set for Abstract Syntax
expressions. Thus Greek letters, for example, would need to be encoded
with expressions like Greek[alpha], or Alpha[]. Similarly, font encoding
is achieved by the use of Abstract Syntax such as the following for 12pt
bold Times Roman:
Font[timesRoman, 12, bold, <expression>]
Two SMCs are free to communicate in a larger character set, or pass font
specifications in other ways, but they should always be able to express
themselves in standard Abstract Syntax.

3. 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.
If in addition we can establish a collection of standard names and
argument lists for common functions, and get all COMP's to read and
write them, then any Computer Algebra system will be able to talk to any
other.
Some examples of possible standard names and argument lists for common
functions:

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, e.g.

Polynomial[Variables[x, y, z], List[Term[coeff, xExp, yExp, zExp], ...

but it should be able to translate this to an equivalent standard
representation, e.g.

Plus[Times[coeff, Power[x, xExp], ...

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

5. 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 formatting databases that store knowledge of particular display
environments, for example, "typesetting for Journal X". 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 "passes 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.

6. With the use of the SMC's specified 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.

7. Note that Abstract Syntax is human-readable. Thus any text editor
can be used as an ED. Of course, in a typical SMS, users should have
no need to look at the Abstract Syntax flowing through the internal
"wires" if they don't care to. Many will want to interact only with
mathematics that has a textbook-like appearance, and they should be able
to do so.

8. 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(s). Meaning is
just a handshake between sender and recipient.

9. Help and status queries, the replies to help and status queries, and
error messages should be read and written by SMC's in Abstract Syntax.

10. In general, it is permissible for two SMC's to use private protocols
for communication. Our example of a tightly coupled ED and DISP above is
one example; two instances of a Macsyma COMP would be another: they
might agree to pass Macsyma internal representations back and forth. To
qualify as SMC's, however, they should be able to translate all such
exchanges into equivalent exchanges in Abstract Syntax.

------------------------------

End of NA Digest

**************************
-------