.c	Wednesday  Nov 18,1981  17:30  FM+7D.3H.9M.52S.  -*- Bolio -*-

.chapter "The WRITE Package"

The lan{write} package is a notation and text formatting utility.
It is particularly designed to support (and facilitate the programming
of) efficient, high-quality, mutually-compatible prettyprinters for
arbitrary programming languages and similar systems of notation.

The lan{write} package has the following characteristics. 
.table 2 175 400
.item (1)
It provides fast and essentially linear prettyprint
formatting algorithms.  A prettyprinter built on lan{write} never
backs up (except perhaps while parsing an 2input* object): a
control path that is followed always corresponds to some
particular structure assigned to the 2output*.

.item (2)
It is designed for variable-width fonts, though it will take
time-saving shortcuts in the uniform-character-width case.

.item (3)
It will print any initial portion of its eventual output as soon
as the precise format of that initial portion can be determined.
This is important for online printing, since it improves
response time and lets the user know when printing is in
progress (especially helpful if an exception condition or
failure occurs during printing).

.item (4)
It can put out in running text anything it can prettyprint.
Also, it can project the size of anything it can print.  Thus a
user need write only a single printer for his notation, not
separate ones for separate purposes.

.item (5)
It does not typically create any structures that later need to
be garbage-collected.  In most implementations, it will recycle
or itself reclaim any buffer structures it has allocated.  In some
implementations it may produce small quantities of garbage, such as
fixnums (in lan{maclisp} only).  Certain constructs may
produce small quantities of garbage structures which are used
internally to record formats.

.item (6)
It provides special-purpose control operations that normally
make it possible for the "driving" part of a prettyprinter based
upon it to function without creating any structures at all.  In
particular, there is no need for intermediate structures between
the driving part and the formatting routines in lan{write}: a simple
and efficient "control interface" suffices.

.item (7)
It is responsible for all of the formatting decisions and most
of the detail work involved in prettyprinting.  The driving part
of a lan{write}-based prettyprinter need only (a) initialize format
control variables to taste, (b) establish and set up "writing
environments", (c) produce terminal elements of outputs in
order, (d) follow control paths that serve to assign structure
to outputs, and (e) supply parameters to the formatting routines
in lan{write}.

.item (8)
It does prettyprint formatting extremely well, though not
perfectly.  Formatting decisions are often made heuristically
and are sensitive to such aesthetic points as approximate
balancing of line lengths and due apportionment of squeezing
when squeezing is necessary.  The formatting algorithms are
well-parameterized and are not difficult to revise.

.item (9)
It has an automatic line-numbering feature that coordinates with
features for recording where objects appear in the output.
.end_table

In the jargon of the lan{write} package, "writing" differs
from "printing" only in that "writing" does not 2imply*
output.  "Writing" does include generation and formatting and
2may* include output.

.section "The Art of Prettyprinting"
	Prettyprinting is the art and practice of formatting a
formal expression as a series of lines, partly so as to
facilitate its parsing and interpretation, and partly so that it
will fit within some given measure.  Prettyprinting is
essentially, though not in detail, a language-independent art,
as evidenced by the ease with which human skill at it can be
transferred from one language to another.

The art of prettyprinting was perhaps first captured with any degree
of formality in the form of rules for arranging a large mathematical
expression as a series of lines, typically with suggestions about
preferred "breakpoints" (places where a line break may occur).  [Refer
to Chicago Manual of Style and AMS Memo....]  [etc.]

A more abstract and general formalization of the art of prettyprinting
involves assigning structure to any formal expression to be
prettyprinted 2as if it were an expression in some universal
prettyprinting language*.  One particular such language, lan{upp} (for
"Universal Prettyprinting"), may be defined partially in BNF as
follows.

.lisp 500 7
2expression* ::=
      2identifier* | 2number* | 2string* | 2symbol* |
      2expression-with-prefix* | 2expression-with-suffix* |
      2expression-with-brackets* | 2head-then-body* | 2series*
.end_lisp

.lisp 500 7
2expression-with-prefix* ::= 2prefix-symbol* 2expression*
.end_lisp

.lisp 500 7
2expression-with-suffix* ::= 2expression* 2suffix-symbol*
.end_lisp

.lisp 500 7
2expression-with-brackets* ::=
      2opening-bracket-symbol* 2body* 2closing-bracket-symbol*
.end_lisp

.lisp 500 7
2head-then-body* ::= 2head* 2breakpoint* 2body*
.end_lisp

.lisp 500 7
2series* ::=
      2element* | 2element* 2breakpoint* 2series* |
      2element* 2separation-suffix-symbol* 2breakpoint* 2series*
.end_lisp

.lisp 500 7
2head* ::= 2expression*
.end_lisp

.lisp 500 7
2body* ::= 2expression*
.end_lisp

.lisp 500 7
2element* ::= 2expression*
.end_lisp

.lisp 500 7
2breakpoint* ::= 2space* | 2line-break* | 2null*
.end_lisp

.lisp 500 7
2null* ::=
.end_lisp

	Any non-terminal not defined in the above equations may
be taken as if it were defined as an enumeration of alternative
terminals.  Note that spaces and line breaks that are 2not*
within terminals may appear in lan{upp} expressions only where
indicated explicitly in the grammar above.

	The "semantics" of lan{upp} are meager.  By implication, the
elements of a series all play essentially the same role in some
larger construct, whereas the head and body of a
"head-then-body" do not.  A pair of bracketing symbols "nests"
its body, whereas a prefix or suffix symbol does not.

	Figures [1-n] show particular lan{upp} parses (in the form of
parse trees) of some typical programming language expressions.
Each parse tree node is labeled to indicate the type of lan{upp}
construct it represents an instance of: PREF for an
expression-with-prefix, SUFF for an expression-with-suffix,
BRACK for an expression-with-brackets, HB for a head-then-body,
and SERIES for a series.  The parses given are not intended to
be definitive.

	It may be surmised from the figures that elements of
formal expressions typically end up more branching levels down
in lan{upp} parse trees than they would in corresponding
language-specific parse trees.  Note from figure [2], for
instance, that the plus signs in
.lisp 500 2
a = b + c + d
.end_lisp
are five levels down in the lan{upp} parse given!

	An appropriate lan{upp} parse of a mathematical expression
can adequately describe its structure for purposes of
prettyprinting, though it does not address the formatting issues
related to subscripting, superscripting, built-up fractions,
vector notation, matrix notation, accents, over-bars, etc.

.section "Writing Facilities"
	The lan{write} package offers facilities at three distinct
levels.  At the highest level are environment establishment and
set-up operations, format control variables, and construct
writing operations.  At the middle level are elementary writing
operations.  At the lowest level are buffer operations and
elementary printing operations.  (A prettyprinter built on the
lan{write} package would normally not make direct use of facilities
at the lowest level.)

.subsection "Environment Establishment and Set-Up Operations"
	The writing facilities in lan{write} all implicitly operate
on "the current writing environment".  A writing environment
behaves like a binding of a Maclisp special variables: its scope
is "fluid", i.e., carried along the control (flow) path of the
program; its lifetime is the same as the lifetime of the newest
part of the control environment at the time of its creation; and
it is "current" when, and only when, it is the newest of all the
writing environments within the current control environment.
Not surprisingly, a writing environment is implemented in
lan{lisp} as a set of special variables bound in parallel.

.defmac write-afresh {form}*
This is the form for establishing the outer environment for
3write*.  Specific printing applications which add additional
facilities and extend the writing environment normally define a
similar form, which should be used instead;  for instance, the
lan{lisp} pretty-printer built from lan{write} supplies
3pp-environment* ((pp-environment-fun).
.end_defmac


.subsection "Construct Writing Operations"
	A prettyprinter built on the lan{write} package, when
producing a particular formal expression, must follow a control
path that corresponds to a particular lan{upp} parse (structural
decomposition) of that expression.

.subsection "Elementary Writing Operations"

.section "Format Control Facilities"
	[control variables, flatsizing]

.section "Low-Level Facilities"

.subsection "Write Buffers"

.subsection "Elementary Printing Operations"

.section "More of the Art"

.subsection "What's Pretty"

.subsection "Prettyprint Formatting Algorithms"

