CHARYBDIS: A LISP PROGRAM TO DISPLAY
MATHEMATICAL EXPRESSIONS ON TYPEWRITER-LIKE DEVICES

        

J. K. Millen
AUGUST 1967

THE: MITRE
CORPORATION
BOX 208
BEDFORD, MASSACHUSETTS

This document has been
released for public dissemination.

Project 9515

ACKNOWLEDGMENTS
This project was sponsored by The
MITRE Corporation's Dependent Research Program.

It was also supported,
in part, through access to its computer facilities, by Project MAC, an M. I. T.
Research Program sponsored by the Advanced Research Projects Agency, Department
of Defense, under Office of Naval Research Contract No. NONR-4102(01).
The
author wishes to thank C. Engelman for his many helpful comments and
suggestions.

ABSTRACT

Charybdis is a LISP program that accepts, as input,
mathematical expressions written in LISP prefix notation, and displays them in
familiar two-dimensional form on devices with a small fixed character set. It is
a simply organized, modular program whose structure is based on the recursive
structure of mathematical expressions. Changes and additions to the repertory of
Charybdis can be made easily and independently of one another by LISP
programmers familiar win little more than its conceptual basis.        
        


TABLE OF CONTENTS Page


LIST OF ILLUSTRATIONS .....
viii
SECTION I INTRODUCTION ..... 1
SECTION II DESCRIPTION OF THE DISPLAYS
..... 3

THE CHARACTER SET AND ITS LIMITATIONS ..... 3
LINE OVERFLOW
..... 8
SPECIAL SYMBOLISM ..... 10
OTHER DISPLAYS .....10

SECTION
III PROGRAM STRUCTURE .....14

INTRODUCTION .....14
CHARYBDIS
.....14
PROGRAM STRUCTURE ..... 15
CONCEPTUAL BASIS .....16
THE EXAMPLE
.....19

SECTION IV SUMMARY .....22
REFERENCES .....23

LIST OF ILLUSTRATIONS


Figure No. Page
1 Some Displays
(a)
Continued Fraction ..... 3
(b) MATHLAB: Differentiation Result ..... 4
(c)
MATHLAB: Integration Result ..... 5

2 Parentheses
(a) Single Line
..... 7
(b) Stacked ..... 7

3 Splitting Across Lines
(a) A
Differential Equation ..... 9
(b) Its Solution ..... 9

4 Extended
Summation ..... 11

5 Other Displays
(a) Matrix ..... 12
(b) Binary
Trees ..... 13

6 Block Diagram of Charybdis ..... 15

7
Illustration of Terms ..... 18

SECTION I  - INTRODUCTION

SECTION II DESCRIPTION OF THE
DISPLAYS    

THE CHARACTER SET AND ITS LIMITATIONS

Charybdis assumes a character set containing the upper case
alphabet, the decimal digits, and these additional symbols: + - = / .,: ( ) * .
One notices immediately that the capital sigma representing summation, and other
common mathematical operators, are missing; but even more basic problems exist.
What about the horizontal bar in a quotient? Where are exponents and subscripts,
and where are tall parentheses (to match the size of the parenthesized
expression)? Charybdis& quot;solutions to some of these problems are
illustrated in Figures l(a) - l(c). With a little reflection, it becomes evident
that there is really only one possible way to handle most of these initial
problems. The resulting displays are somewhat alien at first glance, but are
readable and easy to get used to.


    
  Figure l(a). Some Displays- Continued Fraction
[omitted] 
      Figure l(b) Some
Displays-MATHLAB Differentiation Result [omitted]
  
    Figure l(c). Some Displays- MATHLAB:
Integration Result [omitted]

Figures l(b) and l(c) are in the context of MATHLAB, which
reads expressions in a FORTRAN-like form but prints them out using Charybdis. A
complete explanation of the meaning of the commands and replies shown would be
too lengthy to include here, but the conversation is not hard to follow, even
without the explanation.

Notice in the figures that variables in a
product are separated from neighboring variables by asterisks. Although
multiplication is usually signified by adjacency, that could lead to ambiguity.
The ambiguous situations are those in which a single variable is represented by
a string of more than one character. With a character set not containing Greek
letters, for example, one often writes PI for p, THETA for ?, etc. Now, if
adjacency signifies multiplication, PI could be either a variable or a product.
Context might resolve the difficulty, or it might not. An equally acceptable
solution would be the interposition of a blank instead of a star; familiarity
with FORTRAN prompted the choice that was made.

Tall parentheses can be
simulated as in Figure 2(b). The same expressions can also be displayed as in
Figure 2(a), in which parentheses are always single. The Charybdis user has his
choice, made known to the program by setting a switch (the global variable
TALLPAR).

Parentheses which match the height of the parenthesized
expression are easier to pair, but tend to clutter the display. Single-line
parentheses are harder to pair, but are never actually ambiguous. (This remark
is not quite as obvious as it appears; recall that tall parentheses also
indicate the top and bottom of an expression)

Because of the bias of the
author, the switch is set initially for single-line parentheses.

Figure 2.
Parentheses (a) Single Line (b) Stacked [omitted]   
          
  

Expressions too long for a single line are a problem for any
display program using a device with a fixed line length -- even textbooks.
Charybdis splits such expressions over several lines in an unconventional way,
as illustrated in Figure 3(b). The expression shown is the solution, as computed
by MATH LAB [ 3 ] , of the differential equation in Figure 3(a)
The algorithm
for splitting the expression is as follows: if the expression is a quotient,
exponential, or equation, the two subexpressions are displayed, indented three
spaces, above and below the main connective (/, **, or =, respectively). If the
expression is a sum or product, it is split into as many parts as necessary, and
the parts displayed one after another indented three spaces, separated by the
main connective + or * on intervening lines.

In all other cases, the
keyword is displayed, and then the individual arguments, indented three spaces,
with commas on intervening lines.

If any of the parts which are to be
displayed is still too long, the process is applied recursively to split the
part.

Future development of the program should include more
sophisticated splitting of some expressions currently in the'in all other
cases'category.

The net effect is that the expression is spread out into
a tree-like structure, with its root at the left. Looking again at Figure 3(b),
and reading from the'/'at the left, one sees that the expression is a quotient
whose denominator is (a+b+c) &sqrt{4ca-b2};, and whose numerator is the sum
of two products, etc.

A drawback of this method of presentation is that
it assumes a bottomless display surface. Appropriate though this may be for line
printers and teletypes, a scope screen might not be able to show the entire
display of an extremely complicated expression. Charybdis would have to be
modified to handle such situations. Martin's system takes care of this by naming
sufficiently many subexpressions, and substituting their names for the
subexpressions themselves in the whole expression, so that the result will fit
on the screen. The named expressions can then be displayed later at will. Such a
solution must clearly be undertaken hand in hand with the background
mathematical manipulation program.


face='MS PGothic'>    
  Figure3(a). Splitting Across Lines-A Differential Equation [omitted]

      Figure 3(b). Splitting Across
Lines - Its Solution [omitted]

SPECIAL SYMBOLISM

OTHER DISPLAYS

SECTION III PROGRAM
STRUCTURE

INTRODUCTION

CHARYBDIS

PROGRAM STRUCTURE

CONCEPTUAL BASIS

In order to add a new kind
of display to Charybdis, one must first understand the notion of the origin of
the display of an expression. The reason is that the purposes of three out of
the four LISP functions which must be defined to accomplish the addition are
stated in terms of the origin.
The origin is a distinguished location within
a display, whose coordinates are determined as follows:

1) The abscissa
of the origin is that of the leftmost character in the display. 2) If the
expression, call it a, were written as the argument of an arbitrary function F.
as F(a), the ordinate of the origin would be that of the'F'.
Property 2) is
meant to be a precise way of describing the'middle line'of an expression -- not
the measured middle line, but the natural one. In this sense, the middle line of
a quotient, for instance, is the one in which the horizontal bar lies --
regardless of how tall the numerator and how short the denominator, or vice
versa. Thus the origin of a quotient is the location of the leftmost dash in the
bar. The origin of (the display of) an atom is easily seen to be the location of
its initial character.

Property 2), as it is stated, applies to
mathematical expressions in only the narrowest sense of the word Recall that the
capital sigma, for example, does not occur alone as the argument of any
function. If one wishes to deal with an arbitrary display, the looser definition
of the origin -- as on the'natural middle line'-- is more appropriate; for, the
less mathematical the display, the more free the choice of an origin can afford
to be. In fact, if the display will not occur as a subexpression of any
expression, the ordinate of the origin may be chosen arbitrarily.

After
defining three more terms, we shall be in a position to describe the entire
process of adding displays, and give an example.

The width of a display
is the number of columns from the extreme left of the display to the extreme
right.

The superspan of a display is the number of lines it extends
above the origin. An atom has a superspan of zero.

The subspan of a
display is the number of lines it extends below the origin. An atom has subspan
zero.
These
attributes are illustrated in Figure 7.
      
A corollary of the
definitions above is that the height of a display can be expressed by this
formula: superspan + 1 + subspan.

The four functions which constitute an
individual module for handling expressions of a particular type are:
1) a
function whose four arguments are: an expression, the two coordinates x, y of
the desired origin, and a partial display list; and whose value is the new
display list obtained from the one given by appending to it the description of
the display of the input expression; (this function does the work for APP, which
derives its name from the fact that it appends to the display list. );
2) a
function of one argument whose value is its width;
3) a function of one
argument whose value is its superspan;
4)
a function of one argument whose value is its subspan.

Figure
7. Illustration of Terms [omitted]         
  

These functions are made known to the executive module by placing their names
on the property list of the keyword under the indicators APP, WIDTH, SUPERSPAN,
and SUBSPAN, respectively.

Now for an example.

THE EXAMPLE

Let us suppose that we wish to specify the display of a sum of
two terms. The first step, of course, is to specify the input expression: (SUM
term1 terms2) The only restrictions on our choice are that it must have the
proper keyword-argument form, and it must agree with the form used in the
underlying mathematical manipulation program.
The sum is made up out of two
variable subexpressions -- the terms -- and a plus sign. The plus sign is a
character, a fortiori an atom, and may be viewed as just another subexpression.
Our job is to specify the positions of these three subexpressions relative to
one another, and place the whole at some given location. Restated in the
framework of the subsection, 'CONCEPTUAL BASIS', the task is as follows: given
the coordinates (x, y) of the origin of the whole expression, specify the
coordinates of the origins of the subexpressions.

Let us place the origin
of
a) the first term at (x, y),
b) the plus sign at (x + w, y) (where wis
the width of the first term),
c) the second term at (x + w + 1,
y)

These statements completely describe the display of the sum. It is
clear that the origin of the new display satisfies the defining properties 1)
and 2). But we are not done yet; how do we know that this display is
satisfactory, i. e., looks like a sum should? Because of property 1), concerning
the abscissas of the origins of the subexpressions, and the use of the width of
the first term, the display will have the plus sign between the two terms, as
desired Furthermore, since the origin of each term is on the line on which an
applied function would be placed (property 2)), and since the exterior plus sign
belongs on that same line, the vertical placement of the terms is
correct.

In other words, it is on this particular definition of an
origin, together with the availability of functions to compute the width and
(for other displays) the superspan and subspan, that our confidence in the
ability of Charybdis to handle the new display properly rests.

Note that
any other choice for the abscissa of the origin, except for the right-hand end
of the display, would result in more arithmetic for computing the width, The
advantage of the left side over the right is that it indulges our predilection
for constructing expressions as we would write them, from left to right.


As for the ordinate of the origin, the value chosen is necessary
information in the example, as in most displays. Another choice of origin would
necessitate extra computation to find that value.

Having abstractly
specified the display, we can now write the four LISP functions to handle the
jobs of APP, WIDTH, SUPERSPAN, and SUBSPAN. Note the parallel between the
definition of the APP and the description of the display given
above.

face='MS Mincho' color=#008080>appsum [ u; x; y; d ] = prog [ [ newd; w ] ;
newd := d;
w: =
width [ cadr [ u ] ;
newd: = app [ cadr [ u ] ; x; y; newd ] ;
newd: = app
[ pluss; x+w; y; newd ] ;
newd: = app [ caddr [ u ] ; x +w + 1; y; newd ]
;
return [ newd ] ]

widthsum [ u ] = width [ cadr [ u ] ] +1+width [
caddr [ u ] ] superspansum [ u ] = max [ superspan [ cadr [ u ] ] ; superspan [
caddr [ u ] ] ]
subspansum [ u ] = max L subspan [ cadr [ u ] ;
subspan L caddr [ u ] ] ]

SECTION IV SUMMARY

REFERENCES