\chapter{Examples\label{examples}}

The following sections give some examples of pretty-printing rules for a
variety of `languages':

\begin{itemize}
\item{\HOL\ terms}
\item{Lisp}
\item{Pascal}
\item{ELLA: A hardware description language}
\item{Arithmetical expressions}
\end{itemize}


\section{HOL terms}

At the most basic level, \HOL\ terms are built up from constants, variables,
function applications and abstractions. Terms also contain type information,
but we shall not concern ourselves with the printing of types.

Suppose we are representing terms as trees with one of the following forms:

\begin{small}\begin{verbatim}
             CONST            VAR            COMB           ABS
             /   \            / \            /  \           / \
          name   type      name type     rator  rand      bv  body
\end{verbatim}\end{small}

\noindent
where the nodes in capital letters are constant node names and the other nodes
represent sub-trees.

Consider variables. We simply want the name of the variable to be printed.
A rule to do this might be:

\begin{small}\begin{verbatim}
   ''::VAR(***name(),*) -> [<h 0> ***name];
\end{verbatim}\end{small}

\noindent
The rule consists of a {\it pattern\/} followed by {\small\verb%->%} followed
by a {\it format}. The pattern begins with a character string which in this
case is empty. This represents a {\it context\/} in which the rule is to
apply. The empty string is special in that the rule applies in any context.

The remainder of the pattern following the {\small\verb%::%} represents the
tree to be `matched'. Identifiers preceded by one or more asterisks are
variables. One asterisk indicates a variable which can match any tree. Three
asterisks indicates a variable which can match a node-name. In the example,
the \HOL\ variable name is bound to {\small\verb%***name%} and the type of the
\HOL\ variable is matched by {\small\verb%*%}, but is not bound to anything.
The {\small\verb%()%} following {\small\verb%***name%} indicates that the name
node is to have no children.

The format consists of a single {\it box}. The box contains the single item
{\small\verb%***name%}. {\small\verb%<h%}~{\small\verb%0>%} indicates that the
box is a {\it horizontal\/} box, the components of which are to be separated
by zero spaces. A horizontal box cannot be split between lines of the output.

Now we shall consider a rule for abstractions.

\begin{small}\begin{verbatim}
   ''::ABS(*bv,*body) ->
       [<hv 1,3,0> [<h 0> "(\" *bv "."] [<h 0> *body ")"]];
\end{verbatim}\end{small}

\noindent
The format in this example consists of a box containing two sub-boxes. The
two sub-boxes both form indivisible units in the output (they are horizontal
boxes). The top-level box is a horizontal/vertical box. The components of such
a box will appear on a single line of output if there is space. If not the
excess will go on the next line until that is full, and so on. The numbers in
the box (1,3,0 in the example) are the separation of components if composed
horizontally, the indentation if composed vertically, and the number of blank
lines separating the components if composed vertically. So, in our example
with {\small\verb%*bv%} and {\small\verb%*body%} both bound to
{\small\verb%var%}, the output will appear as:

\begin{small}\begin{verbatim}
   (\var. var)
\end{verbatim}\end{small}

\noindent
or (if there is insufficient space for the above) as:

\begin{small}\begin{verbatim}
   (\var.
      var)
\end{verbatim}\end{small}

\noindent
As can be seen from the example, items enclosed in double quotation-marks are
constant strings to appear in the output.

It is not difficult to see how function applications can be pretty-printed in
a similar way to abstractions. One only needs to change the pattern slightly
and to omit the `{\small\verb%\%}' and `{\small\verb%.%}' from the format.

If we are printing function applications so that infixes as well as prefixes
appear prefixed, then constants which are infixes or binders should be prefixed
by a dollar sign. This is dealt with in the following rule for constants:

\begin{small}\begin{verbatim}
   ''::CONST(***name(),*) ->
       [<h 0> {
               \s. if ((is_infix s) or (is_binder s))
                   then (`$` ^ s)
                   else s
              } (***name)];
\end{verbatim}\end{small}

\noindent
The pattern is similar to the one used for variables. The format differs in
containing a function application. The function is a piece of \ML\ code
enclosed in braces. It is applied to the node-name bound to
{\small\verb%***name%}. The \ML\ code is textually substituted directly into
the \ML\ data structure declaration generated by the pretty-printing language
compiler. It is not checked in any way by the pretty-printing language
compiler.

In the example, the code is a function of type
{\small\verb%string%}~{\small\verb%->%} {\small\verb%string%}. The function
prefixes the constant name with a dollar sign if the constant is an infix or a
binder. Observe that following the leading brace, the rest of that line is
blank. This is a restriction imposed by the compiler to enable it to tidily
lay out the generated \ML\ code.

The rules given so far are very basic. For example we would like infixes to
appear as such. A rule to detect and print equalities is given below.

\begin{small}\begin{verbatim}
   ''::COMB(COMB(CONST(#=#(),*),*left),*right) ->
       [<hv 1,2,0> [<h 1> *left "="] *right];
\end{verbatim}\end{small}

\noindent
The name of the constant is not alphanumeric, and so is not a valid identifier.
It must therefore be forced to be an identifier by enclosing it within sharp
signs ({\small\verb%#%}).

We have chosen to indent by two characters if the outer box has to be broken.
This is purely a matter of taste, but the larger the value is, the harder it
will be for the pretty-printer to keep the output within the specified line
width. The left sub-tree and the equality sign cannot be broken across lines.

Rules are tried in order. If more than one rule is applicable to a tree, the
first applicable one in the list will be used. So, we must place the rule just
described before the previous rules (which are less specific).

Using the rules described so far, an abstraction of more than one variable
such as {\small\verb%"\x%}~{\small\verb%y.%}
{\small\verb%x%}~{\small\verb%/\%}~{\small\verb%y"%} will appear as:

\begin{small}\begin{verbatim}
   (\x. (\y. (($/\ x) y)))
\end{verbatim}\end{small}

\noindent
Ignoring any need for parentheses around the abstraction, we would prefer this
term to appear as:

\begin{small}\begin{verbatim}
   \x y. (($/\ x) y)
\end{verbatim}\end{small}

\noindent
We can achieve this using the following rule:

\begin{small}\begin{verbatim}
   ''::[ABS(*bvs,<1..>)]*body ->
       [<hv 1,3,0> [<h 0> "\" [<h 1> **[<h 0> *bvs]] "."] *body];
\end{verbatim}\end{small}

\noindent
The first new thing about this rule is the use of square brackets in the
pattern. This denotes a repeated match or `loop'. The pattern within the
brackets is matched against the tree to be printed. If there is no match, the
rule is not used. If there is a match, a further match is attempted. The
{\small\verb%<1..>%} matches any tree. The sub-tree it matches to is used as
the tree to be matched on the following loop. The {\small\verb%1..%} indicates
that the looping match should succeed at least once.

The looping continues until there is no match. At this point
{\small\verb%*body%} is bound to the sub-tree for which the match failed.
{\small\verb%*bvs%} is not bound to just one sub-tree, but to a list of
sub-trees, one for each successful match.

The only new thing in the format is the appearance of {\small\verb%**[...]%}.
This denotes a box which is to be expanded. The pretty-printer duplicates this
box within the enclosing box. The number of duplicates is determined by the
variables in the {\it expansion-box}. If a variable within the expansion-box is
bound to a list, there will be one duplicate for each element of the list.
So, in our example the format is expanded to something of the form:

\begin{small}\begin{verbatim}
   ... [<h 1> [<h 0> *bv1] [<h 0> *bv2] ... [<h 0> *bvn]] ...
\end{verbatim}\end{small}

\noindent
where {\small\verb%*bv1%},{\ldots},{\small\verb%*bvn%} denote the elements of
the list to which {\small\verb%*bvs%} is bound. If there is more than one
variable bound to a list, the number of duplicates will be the largest
list-length. This is explained in more detail in Chapter~\ref{language}.

So, in our example, each of the bound variables in a multi-variable abstraction
will appear in an unbreakable box separated by one space. This is what we want.

As a matter of interest, if the pretty-printer encounters a variable bound to
a list but not within an expansion-box, it still expands, but in a different
way. The list is expanded within the box. The box is not expanded. So, we
could have written our rule as:

\begin{small}\begin{verbatim}
   ''::[ABS(*bvs,<1..>)]*body ->
       [<hv 1,3,0> [<h 0> "\" [<h 1> *bvs] "."] *body];
\end{verbatim}\end{small}

\noindent
In this case the format expands to:

\begin{small}\begin{verbatim}
   ... [<h 1> *bv1 *bv2 ... *bvn] ...
\end{verbatim}\end{small}


\section{Lisp}

In this section we shall consider rules for pretty-printing Lisp expressions.
We assume that the expressions are represented as trees with two kinds of node.
A node labelled with {\small\verb%ATOM%} has a leaf node labelled with the
name of the atom as its only child. A node labelled with {\small\verb%CONS%}
has two children which represent the sub-expressions.

A rule for pretty-printing atoms:

\begin{small}\begin{verbatim}
   ''::ATOM(***atom()) -> [<h 0> ***atom];
\end{verbatim}\end{small}

\noindent
The rule matches in any context. The name of the atom is bound to
{\small\verb%***atom%}. The name appears unchanged in the output.

Representing atoms by only their names for a moment, the list
{\small\verb%(1 2 3)%} has the form:

\begin{small}\begin{verbatim}
   CONS(1,CONS(2,CONS(3,nil)))
\end{verbatim}\end{small}

\noindent
The expression {\small\verb%(1 2 3 . 4)%} has the form:

\begin{small}\begin{verbatim}
   CONS(1,CONS(2,CONS(3,4)))
\end{verbatim}\end{small}

\noindent
Pretty-printing such expressions with nice line-breaks requires the components
to go in the same box. For the list, which is terminated by
{\small\verb%nil%}, we can use a repeating (`looping') pattern to bind the
{\small\verb%1%}, {\small\verb%2%} and {\small\verb%3%} to a single variable.

\begin{small}\begin{verbatim}
   ''::[CONS(*sexps,<>)]ATOM(nil()) ->
       [<h 0> "(" [<hov 1,0,0> *sexps] ")"];
\end{verbatim}\end{small}

\noindent
The loop-link ({\small\verb%<>%}) in the pattern is empty, so the limits on
the number of times the loop can match are taken to be the defaults. The
default minimum is zero and the default maximum is any number. So, the pattern
can match {\small\verb%nil%} alone, by looping zero times.

For the other expression, the {\small\verb%4%} should appear as
{`}~{\small\verb%.%}~{\small\verb%4%}{'}. However, if the {\small\verb%1%} and
{\small\verb%2%} are not present we would prefer the {\small\verb%3%} and the
{\small\verb%4%} to be considered as a unit. To do this we must only use a
`list' rule if the loop matches at least twice.

\begin{small}\begin{verbatim}
   ''::[CONS(*sexps,<2..>)]*sexp ->
       [<h 0> "(" [<hov 1,0,0> *sexps [<h 1> "." *sexp]] ")"];
\end{verbatim}\end{small}

\noindent
If the pattern matches, {\small\verb%*sexps%} must be bound to at least two
elements. For our example it will be bound to {\small\verb%1%},
{\small\verb%2%}, and {\small\verb%3%}, and {\small\verb%*sexp%} will be bound
to {\small\verb%4%}. So the output will either be:

\begin{small}\begin{verbatim}
   (1 2 3 . 4)
\end{verbatim}\end{small}

\noindent
or if the box has to be broken:

\begin{small}\begin{verbatim}
   (1
    2
    3
    . 4)
\end{verbatim}\end{small}

\noindent
depending on the line width.

We deal with a pair using the following rule.

\begin{small}\begin{verbatim}
   ''::CONS(*sexp1,*sexp2) ->
       [<h 0> "(" [<hv 1,3,0> [<h 1> *sexp1 "."] *sexp2] ")"];
\end{verbatim}\end{small}

\noindent
The rule prints the two sub-expressions separated by a dot. The dot has to
follow the first expression on the same line. The second expression can follow
on the same line if there is sufficient space, but if not it will appear on the
next line, beginning three spaces further to the right than the first
expression.

The three rules that deal with {\small\verb%CONS%} should be placed in a
pretty-printer in the order in which they have been given, so that they have
the appropriate priorities.


\section{Pascal}

This example is intended to illustrate pretty-printing of imperative languages.
It is not our intention to describe a pretty-printer for the whole of the
Pascal language, but only for a small subset of it. Hopefully the subset chosen
is a good selection and syntactically correct Pascal, but we make no guarantees
about either of these issues.

The subset investigated includes identifiers, integer and Boolean constants,
assignment statements, procedure calls, conditionals, loops, and blocks. The
Pascal code is represented as a tree with nodes taken from the following:

\begin{small}\begin{verbatim}
                ID  INT  BOOL  ASSIGN  PROC  IF2  WHILE  BLOCK
\end{verbatim}\end{small}

\noindent
{\small\verb%ID%}, {\small\verb%INT%} and {\small\verb%BOOL%} each have one
child, a string, which represents the name of the identifier or the constant.
{\small\verb%ASSIGN%} has two children, the variable to be assigned to, and an
expression. Expressions are restricted to being simply constants or variables.
{\small\verb%PROC%} has one or more children. The first is an identifier (the
procedure name). The other children are expressions (the arguments to the
procedure call).

{\small\verb%IF2%} has three children, a Boolean expression and two commands
or blocks of commands. {\small\verb%WHILE%} is similar but has only one
command sub-tree. {\small\verb%BLOCK%} has one or more children each of which
represents a command or a block of commands. A parse-tree for Pascal should
look similar to the tree structure just described.

Firstly, we deal with the three basic node types. The rule is:

\begin{small}\begin{verbatim}
   ''::***name(***string())
          where {`name` is_a_member_of [`ID`;`INT`;`BOOL`]} ->
       [<h 0> ***string];
\end{verbatim}\end{small}

\noindent
The pattern matches the tree if the root node of the tree is {\small\verb%ID%},
{\small\verb%INT%}, or {\small\verb%BOOL%}, and it has one child which itself
has no children. If there is a match, the name of the child node is printed.
An embedded \ML\ function is used to test whether {\small\verb%***name%} is
bound to one of the three names we want.

The next rule matches an {\small\verb%ASSIGN%} node with two children. The
children are displayed by recursive calls. The first child appears in an
unbreakable (horizontal) box followed by the symbol {`}{\small\verb%:=%}{'}.
The separation is one space. The second child either appears on the same line
separated by one space, or it appears on the next line (vertical spacing of
zero) beginning three characters after the start of the first child.

\begin{small}\begin{verbatim}
   ''::ASSIGN(*var,*exp) -> [<hv 1,3,0> [<h 1> *var ":="] *exp];
\end{verbatim}\end{small}

\noindent
Procedure calls may have zero or more arguments. If there are no arguments,
only the name of the procedure is displayed.

\begin{small}\begin{verbatim}
   ''::PROC(*proc) -> [<h 0> *proc];
\end{verbatim}\end{small}

\noindent
For one or more arguments, the arguments appear within parentheses after the
procedure name. They are separated by commas.

\begin{small}\begin{verbatim}
   ''::PROC(*proc,**args,*arg) ->
       [<hv 0,3,0> *proc
                   [<h 0> "("
                          [<hv 0,+3,0> **[<h 0> **args ","] *arg]
                          ")"]];
\end{verbatim}\end{small}

\noindent
The pattern in the above rule matches any {\small\verb%PROC%} node with two or
more children. {\small\verb%*proc%} is bound to the first child.
{\small\verb%*arg%} is bound to the last child. {\small\verb%**args%} is bound
to a list of the remaining children (which may be null).

The arguments will appear either immediately after the procedure name, or on
the next line indented by three spaces. The leading bracket will always appear
on the same line as the first argument, and the trailing bracket will always
appear on the same line as the last argument. Every argument except the last
is followed by a comma which has to appear on the same line as the argument.
If necessary, the argument list will be split onto several lines, each line
beginning three spaces further to the right than the previous one. If the 
{\small\verb%+3%} in {\small\verb%<hv%}~{\small\verb%0,+3,0>%} appeared
without the {\small\verb%+%}, the second, third, etc. lines of parameters
would all begin three spaces further to the right than the first. So, using
the rule in the form shown above, we might obtain output similar to the
following:

\begin{small}\begin{verbatim}
   line(xcoord1,ycoord1,
           xcoord2,
              ycoord2)
\end{verbatim}\end{small}

\noindent
Without the {\small\verb%+%} before the {\small\verb%3%}, the same tree would
produce:

\begin{small}\begin{verbatim}
   line(xcoord1,ycoord1,
           xcoord2,
           ycoord2)
\end{verbatim}\end{small}

\noindent
The rule for a two-armed conditional statement is:

\begin{small}\begin{verbatim}
   ''::IF2(*cond,*com1,*com2) ->
       [<hov 1,3,0> [<h 1> "if" *cond]
                    [<hv 1,3,0> "then" *com1]
                    [<hv 1,3,0> "else" *com2]];
\end{verbatim}\end{small}

\noindent
This rule will normally produce output either of the form:

\begin{small}\begin{verbatim}
   if true then x := 1 else x := 0
\end{verbatim}\end{small}

\noindent
or if there is insufficient space on the line:

\begin{small}\begin{verbatim}
   if true
      then x := 1
      else x := 0
\end{verbatim}\end{small}

\noindent
If the line width were to be reduced even more, we would get:

\begin{small}\begin{verbatim}
   if true
      then
         x := 1
      else
         x := 0
\end{verbatim}\end{small}

\noindent
This would not occur if the occurrences of
{\small\verb%<hv%}~{\small\verb%1,3,0>%} were changed to
{\small\verb%<h%}~{\small\verb%1>%}. The {\small\verb%if%} and its argument
are already treated like this, since if we insist on an indentation of
{\small\verb%3%}, there is no benefit in splitting them between lines.

The rule for {\small\verb%WHILE%} is very similar to the one for
{\small\verb%IF2%}.

\begin{small}\begin{verbatim}
   ''::WHILE(*cond,*com) ->
       [<hov 1,3,0> [<hv 1,3,0> "while" *cond] [<h 1> "do" *com]];
\end{verbatim}\end{small}

\noindent
This only leaves blocks to be dealt with. Suppose we want a block to appear
either as:

\begin{small}\begin{verbatim}
   begin x := 1;y := 2;z := 3 end
\end{verbatim}\end{small}

\noindent
or if there is insufficient width as:

\begin{small}\begin{verbatim}
   begin
      x := 1;
      y := 2;
      z := 3
   end
\end{verbatim}\end{small}

\noindent
For this to happen, the {\small\verb%begin%}, the {\small\verb%end%}, and all
three assignment statements must appear in the same horizontal-or-vertical
box. If we do not do this, the block may be broken between lines in other ways
such as:

\begin{small}\begin{verbatim}
   begin
      x := 1;y := 2;z := 3
   end
\end{verbatim}\end{small}

\noindent
Observe that the separation and indentation parameters for the
{\small\verb%end%} have to be different to those for the assignment
statements. So we need to override the default parameters specified at the
beginning of the box. This is done in the following rule:

\begin{small}\begin{verbatim}
   ''::BLOCK(*first,**middle,*last) ->
       [<hov 1,0,0> "begin"
                    <1,3,0> [<h 0> *first ";"]
                    <0,3,0> **[<h 0> **middle ";"]
                    <0,3,0> *last
                    "end"];
\end{verbatim}\end{small}

\noindent
The pattern matches a block with two or more children. If the
horizontal-or-vertical box is built horizontally, the first child appears one
space after the {\small\verb%begin%}, followed immediately by a semi-colon.
Any children bound to {\small\verb%**middle%} appear zero spaces after their
predecessor, followed immediately by a semi-colon. The last child appears zero
spaces after its predecessor. The parameters for the {\small\verb%end%} are
obtained from the default which in this case is {\small\verb%(1,0,0)%}. So,
the {\small\verb%end%} appears one space after the last child.

If the box is built vertically, the first child appears on the line after the
one containing the {\small\verb%begin%}. It starts three spaces to the right
of the start of the {\small\verb%begin%}. The children bound to
{\small\verb%**middle%} each appear on a new line three spaces to the right of
the start of {\small\verb%begin%} and are followed immediately by a
semi-colon. The last child also appears on a new line indented by three
spaces. The {\small\verb%end%} appears on a new line with the same horizontal
offset as the {\small\verb%begin%} (the indentation is zero).

Finally we need a rule to deal with a block with only one child:

\begin{small}\begin{verbatim}
   ''::BLOCK(*com) -> [<h 0> *com];
\end{verbatim}\end{small}

\noindent
We do not enclose the child within {\small\verb%begin%} and
{\small\verb%end%}, and no semi-colon appears.


\section{ELLA: A hardware description language}

This example considers only one particular construct of the ELLA language,
and a highly simplified version of it at that. The intention is to illustrate
pretty-printing of a construct peculiar to a hardware description language. The
construct in question is called a {\it series}, and it is used to describe the
interconnection of hardware components.

The circuit:

\begin{center}
\setlength{\unitlength}{1pt}
\begin{picture}(330,55)

\put(175,0){\framebox(25,15){{\tt AND}}}
\put(175,40){\framebox(25,15){{\tt AND}}}
\put(100,20){\framebox(25,15){{\tt INV}}}
\put(250,20){\framebox(25,15){{\tt OR}}}

\put(25,5){\line(1,0){150}}
\put(0,2){{\tt in2}}

\put(25,50){\line(1,0){150}}
\put(0,47){{\tt in1}}

\put(45,28){\line(1,0){55}}
\put(75,28){\circle*{2}}
\put(75,28){\line(0,1){17}}
\put(75,45){\line(1,0){100}}
\put(0,25){{\tt select}}

\put(125,28){\line(1,0){25}}
\put(150,10){\line(0,1){18}}
\put(150,10){\line(1,0){25}}
\put(156,13){{\tt l1}}

\put(200,8){\line(1,0){25}}
\put(225,8){\line(0,1){17}}
\put(225,25){\line(1,0){25}}
\put(206,11){{\tt l3}}

\put(200,48){\line(1,0){25}}
\put(225,30){\line(0,1){18}}
\put(225,30){\line(1,0){25}}
\put(231,33){{\tt l2}}

\put(275,28){\line(1,0){25}}
\put(305,25){{\tt out}}

\end{picture}
\end{center}

\noindent
can be expressed as an ELLA series as follows:

\begin{small}\begin{verbatim}
   BEGIN
      MAKE INV: l1,
           AND: l2 l3,
           OR: out.
      JOIN select -> l1,
           (in1, select) -> l2,
           (l1, in2) -> l3,
           (l2, l3) -> out.
      OUTPUT out
   END
\end{verbatim}\end{small}

\noindent
It is this text that we aim to pretty-print, from its parse-tree. The
parse-tree is assumed to be constructed from the following nodes:

\begin{small}\begin{verbatim}
                  NAME               FNNAME              UNIT
                   |                   |                 /..\
                 string              string           name  name

                       JOIN_ITEM                  JOIN
                         /   \                    /..\
                      unit   name         join_item  join_item

                       MAKE_ITEM                  MAKE
                      /     /..\                  /..\
                 fnname  name  name       make_item  make_item

                         STEP                    SERIES
                          |                     /..\   \
                     make or join            step  step unit
\end{verbatim}\end{small}

\noindent
where the uppercase names are the actual node-names, and lowercase names
represent sub-trees. The {\small\verb%/..\%} notation means a list of
sub-trees.

The rules for {\small\verb%NAME%} and {\small\verb%FNNAME%} nodes are simple.
The name is displayed unchanged.

\begin{small}\begin{verbatim}
   ''::NAME(***string()) -> [<h 0> ***string];

   ''::FNNAME(***string()) -> [<h 0> ***string];
\end{verbatim}\end{small}

\noindent
There are two rules for the node {\small\verb%UNIT%}. One deals with nodes
which have more than one child (sub-tree). The rule binds the last child to a
separate metavariable, since it is not to be followed by a comma in the
output. The children either appear on the same line, or in a column, depending
on the space available. The whole thing is enclosed within parentheses. Since
we do not want parentheses when the {\small\verb%UNIT%} node has only one
child, a separate rule is required to deal with this case. It must come before
the other rule, so that it takes priority.

\begin{small}\begin{verbatim}
   ''::UNIT(*name) -> [<h 0> *name];

   ''::UNIT(**names,*name) ->
       [<h 0> "(" [<hov 1,0,0> **[<h 0> **names ","] *name] ")"];
\end{verbatim}\end{small}

\noindent
A {\small\verb%JOIN_ITEM%} is a {\small\verb%UNIT%} followed by an arrow,
followed by a {\small\verb%NAME%}. We choose to break the expression before
the arrow if it has to be broken between lines, and indent the arrow by three
spaces:

\begin{small}\begin{verbatim}
   ''::JOIN_ITEM(*unit,*name) ->
       [<hv 1,3,0> *unit [<h 1> "->" *name]];
\end{verbatim}\end{small}

\noindent
{\small\verb%JOIN%} can have any number of children, each of which is a
{\small\verb%JOIN_ITEM%}. The {\small\verb%JOIN_ITEM%}s are printed as a
vertical list which either begins one space to the right of the end of the
keyword {\small\verb%JOIN%}, or on the following line, three spaces to the
right of the beginning of the keyword.

\begin{small}\begin{verbatim}
   ''::JOIN(**join_items,*join_item) ->
       [<hv 1,3,0> "JOIN" [<v 0,0> **[<h 0> **join_items ","]
                                   *join_item]];
\end{verbatim}\end{small}

\noindent
The first child of a {\small\verb%MAKE_ITEM%} node is a {\small\verb%FNNAME%}.
The remaining children form a list of {\small\verb%NAME%}s. The
{\small\verb%NAME%}s are all displayed in the same way, so they can all be
bound to the same metavariable. They are displayed either horizontally
separated by a space, or in a vertical column.

\begin{small}\begin{verbatim}
   ''::MAKE_ITEM(*fnname,**names) ->
       [<hv 1,3,0> [<h 0> *fnname ":"] [<hov 1,0,0> **names]];
\end{verbatim}\end{small}

\noindent
The rule for {\small\verb%MAKE%} is analogous to the one for
{\small\verb%JOIN%}:

\begin{small}\begin{verbatim}
   ''::MAKE(**make_items,*make_item) ->
       [<hv 1,3,0> "MAKE" [<v 0,0> **[<h 0> **make_items ","]
                                   *make_item]];
\end{verbatim}\end{small}

\noindent
The {\small\verb%STEP%} node is redundant as far as pretty-printing is
concerned. The rule reflects this by throwing the node away.

\begin{small}\begin{verbatim}
   ''::STEP(*x) -> [<h 0> *x];
\end{verbatim}\end{small}

\noindent
The rule for {\small\verb%SERIES%} is probably the most interesting.

\begin{small}\begin{verbatim}
   ''::SERIES(**steps,*unit) ->
       [<v 0,0> "BEGIN"
                <3,0> **[<h 0> **steps "."]
                <3,0> [<hv 1,3,0> "OUTPUT" *unit]
                "END"];
\end{verbatim}\end{small}

\noindent
The last (rightmost) child of the node is a {\small\verb%UNIT%}. The pattern
binds the {\small\verb%UNIT%} to the metavariable {\small\verb%*unit%}. All
the other children of the node are bound as a list to the metavariable
{\small\verb%**steps%}. The outermost box of the format contains four objects,
one of which can expand to a list of objects. The objects are displayed
vertically beneath one another with no blank lines between them. The first
object is the constant string {\small\verb%BEGIN%}. The last is
{\small\verb%END%}. All of the intermediate objects are indented by three
spaces. There is one object for each {\small\verb%STEP%} and these are
terminated by a dot. The {\small\verb%UNIT%} appears preceded by the keyword
{\small\verb%OUTPUT%}, either as:

\begin{small}\begin{verbatim}
   OUTPUT unit
\end{verbatim}\end{small}

\noindent
or if there is insufficient space for this, as:

\begin{small}\begin{verbatim}
   OUTPUT
      unit
\end{verbatim}\end{small}

\noindent
This example illustrates how straightforward pretty-printing can be when the
trees to be printed closely follow the syntax.


\section{Arithmetical expressions}

\index{precedence}
The main purpose of this example is to demonstrate a method for dealing with
the precedence of operators. We consider expressions consisting of numbers
combined with six operators of arithmetic: monadic minus (negation), plus,
minus, multiplication, division and exponentiation. The expressions are
represented as trees with nodes taken from the following:

\begin{small}\begin{verbatim}
                    NUM  NEG  PLUS  MINUS  MULT  DIV  POWER
\end{verbatim}\end{small}

\noindent
{\small\verb%NUM%} has one child, a leaf node labelled with a string
representing a natural number. {\small\verb%NEG%} has a single child, an
expression-tree. The other types of node all have two expression-trees as
their children.

We assign a precedence to each of the operators. The lowest value is the
highest precedence:

\begin{small}\begin{verbatim}
   0   NEG
   1   POWER
   2   MULT, DIV
   3   PLUS, MINUS
\end{verbatim}\end{small}

\noindent
We begin with a rule for pretty-printing the {\small\verb%NUM%} nodes:

\begin{small}\begin{verbatim}
   ''::NUM(***num()) -> [<h 0> ***num];
\end{verbatim}\end{small}

\noindent
This rule matches a {\small\verb%NUM%} node in any context. The string on the
leaf node is bound to {\small\verb%***num%} and output in a box.

A {\small\verb%NEG%} node is also quite simple:

\begin{small}\begin{verbatim}
   ''::NEG(*exp1) -> [<h 0> "-" *exp1];
\end{verbatim}\end{small}

\noindent
The child of the {\small\verb%NEG%} node is bound to {\small\verb%*exp1%}. It
is then output (by a recursive method) preceded immediately by
{`}{\small\verb%-%}{'}, i.e.~there is no space between them.

The remaining nodes can be dealt with by a single rule:

\begin{small}\begin{verbatim}
   ''::***op(*exp1,*exp2) ->
       [<hv 1,0,0> [<h 1> *exp1 symb(***op)] *exp2];
\end{verbatim}\end{small}

\noindent
The pattern matches any node with two children. The format constructs an
unbreakable box containing the first child and the operator separated by a
single space. This box is then composed with the second child with a single
space separation, except when there is insufficient room on the line. In that
case the second child goes on a new line, lined up with the start of the
first expression.

The operator is transformed before it is output. This is done using the
`function' {\small\verb%symb%}. This is really just an abbreviation for some
\ML\ code for a function of type {\small\verb%string%}~{\small\verb%->%}
{\small\verb%string%}. The abbreviation appears in the pretty-printing
`program' before the rules. The definition is:

\begin{small}\begin{verbatim}
   abbreviations
      symb = {
              \symb. case symb
                     of `NEG`   . `-`
                      | `PLUS`  . `+`
                      | `MINUS` . `-`
                      | `MULT`  . `*`
                      | `DIV`   . `/`
                      | `POWER` . `^`
             };

   end abbreviations
\end{verbatim}\end{small}

\noindent
We do not really need to define the symbol used for {\small\verb%NEG%}, but we
shall need to shortly.

The rules given so far do not output parentheses. This is unsatisfactory as
the output may be ambiguous. To rectify this we need to make use of the
parameter passing facility of the pretty-printer. This facility is rather
messy to use, but provides all the power of \ML.

No change is required to the rule for {\small\verb%NUM%}. The rule for
{\small\verb%NEG%} is replaced by a more general rule to deal with all
prefixed monadic operators:

\begin{small}\begin{verbatim}
   ''::***op(*exp1) ->
       [<h 0> if {prec_test `op`} then [] else [<h 0> "("]
              [<h 0> symb(***op)
                     *exp1 with
                              prec := {prec_of `op`}
                           end with]
              if {prec_test `op`} then [] else [<h 0> ")"]];
\end{verbatim}\end{small}

\noindent
The format part of this rule is a box similar to the one in the old rule,
enclosed within two conditional sub-formats. If the test in the conditionals
is true, an empty box is inserted. Otherwise a left or right bracket is
inserted. The conditional test is a piece of \ML\ code which will be explained
shortly.

The main box outputs a transformed operator followed by the sub-expression.
The sub-expression is evaluated in an environment in which the parameter
{\small\verb%prec%} has a value given by the \ML\ code {\small\verb%prec_of%}
{\small\verb%`op`%}.

The \ML\ code used in this rule may make use of any identifiers available at
the top-level of \ML. In addition locally declared identifiers can be used.
The identifiers used in the example are local and are declared before the
rules (and before any abbreviations) as follows:

\begin{small}\begin{verbatim}
   declarations
      prec_val = {
                  \symb. case symb
                         of `NEG`   . 0
                          | `PLUS`  . 3
                          | `MINUS` . 3
                          | `MULT`  . 2
                          | `DIV`   . 2
                          | `POWER` . 1
                 };

      prec = {bound_number `prec`};

      prec_of = {\meta. apply1 prec_val (bound_name meta)};

      prec_test = {\meta. apply2 (curry $<) (prec_of meta) prec};

   end declarations
\end{verbatim}\end{small}

\noindent
\ml{prec\_val} is a function which given the name of an operator returns the
precedence of that operator. Note that this function assumes that it will not
be passed rogue arguments.

\ml{prec} is a function which given the current pretty-printing environment
via two arguments, returns the integer associated with the string
{\small\verb%`prec`%}. Note that if {\small\verb%`prec`%} cannot be found the
function will fail. \ml{bound\_number} is a built-in \ML\ function. It is
described, along with the other built-in functions used above, in
Chapter~\ref{functions}.

When \ml{prec\_of} is applied to the name of a metavariable, it evaluates to
a function. Given an environment this function computes the precedence of the
operator to which the metavariable name is bound.

When given the name of a metavariable, and a pretty-printing environment,
\ml{prec\_test} computes a Boolean value. The result is true if and only if
the operator bound to the metavariable name is of a higher precedence (smaller
numerical value) than the parent node. The precedence of the parent node is
bound to the parameter {\small\verb%prec%}. The declarations may be mutually
recursive.

A rule for diadic operators can be written in a similar way to the one for
monadic operators. The precedence parameter must be updated for both the
sub-expressions.

So we now have a set of rules for expressions. Observe though that parentheses
are included `between' two operators of the same precedence, e.g.,

\begin{small}\begin{verbatim}
   1 - (2 - (3 - 4))
\end{verbatim}\end{small}

\noindent
This is what we want for {\small\verb%MINUS%}, but for associative operators
the parentheses are unnecessary. We shall make such operators associate to the
right, so:

\begin{small}\begin{verbatim}
   (1 + 2) + (3 + 4)
\end{verbatim}\end{small}

\noindent
will be printed as:

\begin{small}\begin{verbatim}
   (1 + 2) + 3 + 4
\end{verbatim}\end{small}

\noindent
Different operators of the same precedence will be dealt with as before, e.g.

\begin{small}\begin{verbatim}
   (1 - 2) + (3 - 4)
\end{verbatim}\end{small}

\noindent
The rule for associative operators is:

\begin{small}\begin{verbatim}
   ''::[***op(*exps,<1..:***op>)]*exp
          where {`op` is_a_member_of [`PLUS`;`MULT`;`POWER`]} ->
       [<h 0> if {prec_test `op`} then [] else [<h 0> "("]
              [<hov 1,0,0> **[<h 1> *exps with
                                             prec := {prec_of `op`}
                                          end with
                                    symb(***op)]
                           *exp with
                                   prec := {prec_of `op`}
                                end with]
              if {prec_test `op`} then [] else [<h 0> ")"]];
\end{verbatim}\end{small}

\noindent
This rule must appear before the normal rule for diadic operators so that it
takes priority.

The pattern loops down a right-hand chain of operators,
binding the left-hand sub-expressions to {\small\verb%*exps%}. The
{\small\verb%<1..:***op>%} matches any sub-tree and indicates that the root of
the tree it matches is the node to loop on. It also indicates that the looping
pattern must match at least once and that {\small\verb%***op%} must match to
the same name each time round the loop. The pattern is restricted further by
the `where' clause. This clause uses the \ML\ function \ml{is\_a\_member\_of}
to test whether or not {\small\verb%***op%} is bound to one of the three
associative operators.

So, for the expression:

\begin{small}\begin{verbatim}
   1 + (2 + (3 + 4))
\end{verbatim}\end{small}

\noindent
{\small\verb%***op%} would be bound to {\small\verb%PLUS%}.
{\small\verb%*exps%} would be bound to a list of sub-trees representing
{\small\verb%1%}, {\small\verb%2%}, {\small\verb%3%}. {\small\verb%*exp%}
would be bound to the sub-tree representing {\small\verb%4%}.

The format is very similar to ones we have seen previously. The box containing
{\small\verb%*exps%} begins with {\small\verb%**[%} rather than
{\small\verb%[%}. This indicates that it is an expansion-box. The whole box
will be duplicated inside the enclosing box as many times as there are items
in the list bound to {\small\verb%*exps%}. The enclosing box is
horizontal-or-vertical, which means that if it has to be broken, each of the
sub-boxes will begin on a new line. So, if our example has to be broken it
will appear as:

\begin{small}\begin{verbatim}
   1 +
   2 +
   3 +
   4
\end{verbatim}\end{small}

\noindent
rather than as:

\begin{small}\begin{verbatim}
   1 + 2 +
   3 + 4
\end{verbatim}\end{small}

\noindent
or some other form in which two or three numbers appear on the same line. This
may not seem such a good idea, but when the numbers are replaced by large
expressions (which will almost certainly be the case if the expression has to
be broken across lines) it is arguably more readable.

There is one final thing we must consider. The parameter {\small\verb%prec%}
must be initialised. This can be done when the pretty-printer is invoked, but
it is probably safer to do it within the rules. To do this we need to
introduce a new node name, say {\small\verb%ARITH%}, which has an expression
as its single child. {\small\verb%ARITH%} can only appear at the root of a
tree. We also need to add the following rule to the {\em beginning\/} of the
rules:

\begin{small}\begin{verbatim}
   ''::ARITH(*exp) ->
       [<h 0> *exp with prec := max_prec end with];
\end{verbatim}\end{small}

\noindent
and also:

\begin{small}\begin{verbatim}
   max_prec = {apply0 4};
\end{verbatim}\end{small}

\noindent
to the abbreviations.

The rule does not output anything for the {\small\verb%ARITH%} node, but it
does initialise {\small\verb%prec%} to be {\small\verb%max_prec%}, i.e.~a
lower precedence than the precedence of any operator. This will prevent the
entire expression being enclosed in parentheses. Setting {\small\verb%prec%}
to zero would produce parentheses. The rule can be modified so that the
expression is enclosed in quotes:

\begin{small}\begin{verbatim}
   ''::ARITH(*exp) ->
       [<h 0> """" *exp with prec := max_prec end with """"];
\end{verbatim}\end{small}

\noindent
The four consequtive quotes are interpreted by the compiler as one quote to
appear as a constant in the output.