summaryrefslogtreecommitdiff
path: root/usergrps/uktug/baskervi/7_1/lout.tex
blob: abee52f0592e72fa27a2054599d959559f8cba31 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
\title{The Future of Document Formatting (Working Paper)}

\begin{Article}

\section{Abstract}
Document formatting systems have reached a plateau.  Although existing
systems are being steadily enhanced, the next major step forward will
require a union of the best features of batch formatters, interactive
document editors, and page description languages.  This paper draws
on its author's twelve years of experience designing, implementing,
and enhancing the Lout document formatting system to identify the
remaining problems in document formatting and explore some possible
solutions.

\section{Introduction}

Document formatting is one of the most widespread applications of
computers.  Improvements in document formatting software and the
hardware on which it is based have revolutionized the production
of documents and enlarged our conception of what a document might be.

Any attempt at this point to define `document' would run a risk of
being overtaken by events; already documents commonly include moving
images, sound, and dynamic updating as their sources of information
change in real time.  It is perhaps safe to say that a document
is information arranged for presentation to a person; the information may
be called the \emph{content}, and the arrangement its \emph{layout}.  Document
formatting is essentially about mapping content to layout, although functions
that do not exactly fit this definition, such as spelling and grammar
checking, or even creation and editing of content, are often found in
document formatting systems.

Document formatting systems fall into two camps.  In one camp are
the interactive document editors, ranging from word processing systems
such as Microsoft Word~\cite {microsoft1996word} up to desktop
publishing systems such as FrameMaker~\cite {adobe1995frame} and
Interleaf~\cite {interleaf1996}.  These offer an editable screen image
of the document layout.  In the other camp are the batch formatters, such as
troff~\cite {ossanna1976troff}, Scribe~\cite {reid1980scribe},
\TeX~\cite {knuth1984tex}, and Lout~\cite {kingston1995lout.program},
which process text files with embedded markup to produce non-editable
layout.  In this paper the above names will stand for the entire
software family; \TeX\ includes \LaTeX~\cite {lamport1986latex},
FrameMaker includes FrameMaker+SGML, and so on.  Somewhere in between
are the hypertext~\cite {goldfarb1991hytime} net browsers, based on
HTML, which are primitive batch formatters offering limited interactivity
such as the ability to click on a hyperlink or fill in a form.

All of these systems are being actively enhanced by their developers,
with new versions appearing regularly.  For example, FrameMaker and
Interleaf have responded to the World-Wide Web phenomenon by adding
support for SGML~\cite {goldfarb1990sgml} and HTML.  Nevertheless,
viewed from a wider perspective, they all appear to have reached a plateau,
in the sense that each has fundamental limitations that are not
likely to be overcome.  For example, troff, \TeX\ and Lout are batch
formatters% (except for Lyx~\cite {ettrich1996lyx})
and are not likely to become interactive; FrameMaker and Interleaf
are not as extensible as the batch formatters and, again, are not
likely to become so.

One frequently hears arguments for or against these systems, but the
truth is that none of them is ideal yet all have something to offer
to the future of document formatting.  What is needed now is a
synthesis of the best features of all of these systems.

Papers which reflect on document formatting seem to be very rare.  The
survey paper by Furuta, Scofield and Shaw~\cite {furuta1982survey}
is still well worth reading; Kernighan~\cite {kernighan1989retro}
reflects on the troff family; this author has described the design
and implementation of Lout~\cite {kingston1993lout.design}.  But for
the most part one has to infer principles from the systems themselves,
and to look among the specialized applications such as music
formatting~\cite {foxley1987music}, graph
drawing \cite {kernighan1982pic, vanwyk1980, krishnamurthy1995unix},
or non-European languages for requirements.

This paper draws on its author's twelve years of experience in
designing, implementing, and enhancing the Lout document formatting
system, plus his more limited experience of the systems mentioned
above, to identify a set of requirements for a document formatting
system that would be a significant advance on all current systems, and
to explore their interactions.


\section{Requirements}


This section identifies the most significant requirements for a document
formatting system.  Efficiency in space will cease to be a requirement
in the next few years.  Efficiency in time is of course essential, as
are other requirements that apply to any large software system, such
as robustness, openness, and an interface that permits users of varying
levels of expertise to work productively.

The other requirements are editability, extensibility, generality, and
optimality.  Each of these requirements is discussed in turn in the sections
that follow, together with problems that it presents either alone
or in conjunction with previous requirements.

It is not possible to prove that this list of requirements is complete, but
the author has carefully compared it against the features of most of the
document formatting systems listed earlier.  The only major omission has
been the convenience features commonly found in interactive systems,
such as spelling and grammar checkers, input and output in a variety of
data formats, version control, and so on.  These are valuable features,
but they have little to do with document formatting in the core sense
of mapping content to layout.


\subsection{Editability}


Editability, the ability to edit content while viewing layout, is the
strong suit of word processing and desktop publishing systems.  Fairly
or not fairly, many users will not accept batch formatting.  Also, the
batch formatting edit-format-view cycle is too slow when the
layout rule is `what pleases the eye,' such as in diagrams, or when
content must be altered to achieve a good layout, for example in
paragraphs containing long unbreakable inline equations.

Interactive interfaces also have an advantage when the logical structure
does not follow a tree pattern.  A good example is the editing of
graphs (the combinatorial kind).  Users of an interactive system can
click on any pair of nodes to indicate that they are to be joined by
an edge.  In a batch system, because the structure is not tree-like,
it is necessary for the user to invent names for the nodes and use the
names when creating edges, which is considerably more error-prone.  By
contrast, equations do follow a tree pattern and so there is never any
need to attach names to subexpressions.

Critics of interactive systems typically complain about the lack
of content structure in interactive editors, and also about their
weakness as editors compared with good text editors.  Neither problem
would seem to be inherent, and in fact recent versions of high-end
document editors (FrameMaker+SGML for example) are addressing the
content structure problem.

Openness to such auxiliary applications as free-text search and
retrieval and creation of documents by computer programs requires
that an archive format based on marked-up text be included in any
interactive system.  It only takes a little care to make such a
format readable by humans.  Thus an interactive system is automatically
also a batch system.


\subsection{Extensibility}


Extensibility in a document formatting system means the easy addition
of new features.  It is the strong suit of batch formatters.  For
example, this author's Lout system has no built-in knowledge of
equations, tables, or page layout (not even the concept of a page is
built-in); these are all added by means of packages of definitions
written in the Lout language, which is sufficiently high-level to
make them fairly easy to produce.

Extensibility implies some initial kernel of primitive features upon
which the extensions are built.  These would include horizontal and
vertical stacking, rotation, and so on.  The most interesting such
feature is the mechanism for getting floating figures and footnotes
into their places:  diversions and traps in troff, floating insertions
in \TeX, galleys in Lout.  There must also be ways of combining and
packaging the primitives into features useful to the end user.

Although a system not built on such a kernel is conceivable, it seems
scarcely possible to this author that such a system could supply all
the features demanded by end users.  The list is so vast -- equations,
tables, graphs, chemical molecules, music, and so on -- that some
kind of high-level kernel language seems essential to achieving them
in any reasonable time and with any consistency, just as high-level
programming languages are essential to large software projects.

Typography generates requirements for many features, such as hyphenation,
spacing and kerning, ligatures, and so on.  A document formatting system
must produce good typography, because end users cannot be expected to
do it themselves.  Many of these features are dependent on the current
language, and many English or European-oriented systems have failed to
be extensible to the typography of languages outside that sphere.  A good
source of features needed in world-wide typography is Apple Computer's
QuickDraw GX~\cite {apple1996quickdraw}, although their approach of
implementing the features in C is relatively non-extensible since it
requires recompilation.

When an interactive system is extended with a new feature, it must be
possible to continue editing in its vicinity.

Ultimately, the layout of a document is a function of its content, so we
may identify features with functions.  In extreme cases, such as optimal
layout, a function may take the entire document as its parameter; but
usually it has small, clearly delimited parameters as in
\[\mathit{ built\_up\_fraction(numerator, denominator)}\]
There may also be implicit parameters inherited from the context, such
as the current font size.

It is quite reasonable to insist that within any editing session the
collection of features be immutable.  Thus it is not essential to be
able to edit the definition of any function while viewing any
layout.  In some cases, such as simple abbreviations, editing of
definitions is quite simple and could easily be supported.  But more
complex functions, such as optimal layout or graph layout, are defined by
computer programs and so are not amenable to editing in this way.

In a similar vein, it is correct to insist that those parts of the
layout originating within definitions be immutable.  For example, the
bar in a built-up fraction should not be editable.  This does not
preclude the addition of parameters to $\mathit{ built\_up\_fraction}$ to
control the appearance of the bar if desired, but to allow the user to
arbitrarily change the bar would produce a layout whose origin as a
built-up fraction must be lost.

Thus, editability of features really only means editability of their
parameters.

The most favourable case occurs when the function displays a parameter
in a form similar to that which it would have taken if it had been
entered outside the function.  For example, $\mathit{ built\_up\_fraction}$
displays both its parameters, changing their appearance only slightly
(by squeezing vertical spacing within them, and possibly changing the
font size).  The user can edit such a parameter as though
it was not a parameter at all, and so (inductively) can edit parameters
of parameters and so on without limit.  This is essentially how equation
editors work, and the Lilac system~\cite {brooks1991lilac} has
demonstrated it in an extensible framework, although using a kernel
language too incomplete to support the full range of features required
by users.  A function may display a parameter more than once, in
which case editing one display must change them all.

Preserving editability of displayed parameters is a difficult problem
when the function is implemented externally to the document editing
system.  For example, if an external graph layout
program~\cite {krishnamurthy1995unix} is employed,
the result cannot be returned as a bitmap or PostScript file; rather
a set of coordinate pairs or something similar is required so that the
document formatter can place the nodes itself and hence understand
where they ended up.

It has been suggested that a non-editable result is acceptable in such
cases if a click in the region it occupies signals the opening of a separate
editor that does undertand what is going on in that region.  This is the
interactive equivalent of the preprocessor approach used by troff, and
it has the same drawbacks of lack of consistency, duplication of
features, and loss of generality (since even if every editor may
invoke every other editor, the communication channels between them typically
cannot convey such information as the current font, available space, and
so on).  An architecture based on a single master editor with slave
non-interactive formatting programs is preferable.

Parameters which are not displayed are a nightmare, and are responsible
for much of what is ad-hoc in existing interactive systems.  Two main
approaches are in use.  The first is the `style sheet' or `dialogue box'
approach, in which the user who selects a feature with non-displayed
parameters is presented with a box listing them and asked to supply
values:  a font name, a location to place a figure, a style of
numbering, or whatever.  This is the most general method, easily adapted
for use in an extensible system.  It works particularly well when the
parameters have sensible default values, for then use of the box is
optional, and when they have only a small range of possible values, for
then the values may be displayed in a menu.

Second is the `inference' method.  Every parameter has some effect on
layout, otherwise it would be useless.  So the user is offered a means
of manipulating layout, and the parameter's value is
inferred from it.  For example, most editors permit an included graphic
to be clipped by clicking on its boundary and moving the mouse; scaling
and even rotation may be set by such means.  Drawing programs allow
nodes to be dragged about in the drawing area.  `Master pages' or
`template pages,' which allow the user to specify entire page layouts
involving many parameters simultaneously, demonstrate the value
of the inference method.

The great drawback of the inference method is that an inference
interface has to be invented for every non-displayed parameter, and this is
difficult in an extensible system.  However, it should at least be
possible to implement an inference interface for all suitable non-displayed
parameters of kernel features, such as the $\mathit{ boundary}$ parameter
of $\mathit{ clip()}$, and in cases such as
\begin{eqnarray*}
\lefteqn{
   \mathit{define\ user\_level\_feature}(\mathit{\dots,boundary,\dots}) =
         }\\
&&  \dots  \mathit{clip}(\mathit{\dots, boundary, \dots}) \dots
\end{eqnarray*}
to propagate this interface upwards from kernel features to user level
features.  Then every user level feature that offers clipping as a
parameter, for example, will do so in the same way.


\subsection{Generality}


By generality we will mean the absence of illogical restrictions on the
use of features, either in the contexts in which they may be used, or
in the values that may be assigned to their parameters.  (These are
formally the same thing, but the distinction is useful.)

Examples of illogical context restrictions are extremely common in
document formatting systems.  FrameMaker permits objects to be
rotated in certain contexts (when they are table entries, for example)
but not others.  In troff it is very easy to include an equation within
a table, but very much harder to include a table in an equation.  Not
all context restrictions are illogical, of course:  a chapter should
not begin within a table, for example.

Lack of context generality takes a severe toll, because it means that
implementation code, possibly highly sophisticated and with a great deal
to offer, is locked into a few limited contexts.  For example, FrameMaker
has a very interesting equation editor, but there seems to be no hope
that its code can be used for such tasks as editing tree diagrams or
diagrams of chemical molecules, despite the technical similarities
among these tasks.

Examples of illogical domain restrictions are particularly common among
geometrical functions.  For example, \LaTeX\ will produce lines only at
certain fixed angles, and most systems only really understand rectangular
shapes.  The PostScript page description language~\cite {adobe1990ps}
is far ahead of everything else in geometrical
generality:  in PostScript, arbitrary curves (even disconnected ones)
made of lines, arcs, and Bezier curves may be drawn and filled, and
arbitrary combinations of rotation, scaling and translation may be
applied to arbitrarily complex fragments of documents lying within one page.

The abandonment of rectangles in favour of arbitrary shapes would have
widespread beneficial effects if done in full generality.  Text could fill
arbitrary shapes and run around arbitrary graphics.  Fonts could be defined
(as they are in PostScript) as collections of arbitrary shapes, permitting
kerning of arbitrary pairs of glyphs, not just glyphs of equal font and
font size as at present, thus solving the subscript kerning problem.  Line
spacing could reflect the true appearance of lines, not be crudely based on
the highest ascender and lowest descender.  Optimizations based on bounding
boxes and caching should be able to solve the efficiency problems.


\subsection{Optimality}


By optimality is meant the ability to find the best possible layout for
the given content.  An optimal layout is not necessarily a good layout,
because some documents have no good layout.  Optimal layout thus cannot
remove the burden of rewriting content to achieve good layout, but in
practice it does greatly reduce that burden, and this is why it is has
been included.

The idea that layout could be optimal seems to be due to Knuth and
Plass~\cite {knuth1981bpl}, who presented an algorithm for the optimal
breaking of a paragraph into lines which is used in Knuth's \TeX\
system.  Research work was done on more general optimality as
well~\cite {plass1981}, although this author is unsure how much of this
work was incorporated into \TeX.

Suitably generalized, their paragraph breaking algorithm is as follows.  The
first step is to deduce from the content a sequence of atomic formatting
steps.  For example, the content
\[\mathit{The\ cat\ sat\ on\ the\ mat}\]
might have sequence
\[\begin{array}{l}
\mathit{create\_empty\_paragraph}\\
\mathit{add\_word\_to\_paragraph(The)}\\
\mathit{add\_word\_to\_paragraph(cat)}\\
\dots
\end{array}\]
Every prefix of this sequence should define a legal document in its own
right; the whole sequence defines the document we wish to format.  The
question as to what constitutes an atomic operation is not of fundamental
importance; one could choose to add one letter at a time, or an entire
paragraph.

Define a \emph{badness} function from layouts to integers.  Small values
indicate good layouts, large values indicate poor ones.  There are no
restrictions on how this function is defined, except the practical one
of being computable in a reasonable time.

Now there will be several ways in which each atomic step may be
performed.  For example,
$\mathit{ add\_word\_to\_paragraph}$ could add its word to the end of the
current line, or it could start a new line, or it could even start a
new page or column.  This leads to a tree structure:

\begin{picture}(160,100)

\put(45,40){\framebox(24,12)[l]{\ The}}

\put(105,34){\framebox(22,22){}}
\put(105,40){\makebox(21,20)[l]{\ The}}
\put(105,30){\makebox(21,20)[l]{\ cat}}

\put(105,77){\framebox(41,14)[l]{\ The cat}}


\put(105,0){\framebox(46,14)[l]{\ The $|$ cat}}

\put(69,52){\vector(1,1){36}}
\put(69,46){\vector(1,0){36}}
\put(69,40){\vector(1,-1){36}}
\end{picture}

\noindent
Each node is a layout of a partial document, each edge is one atomic
operation.

The next atomic operation is applied to each leaf node, creating more
partial documents, and so on until the sequence ends and the leaf
nodes represent all layouts of the document of interest.  The leaf node
of minimum badness is the optimal layout.

This model can incorporate diverging operation sequences caused by
layout dependencies.  For example, suppose the word \emph{abacus} has an
index entry attached to it, and that along one path in the tree this
word appears on page 99, while along another it appears on page
100.  Then, in the sequence of operations defining the index, we will
find
%@ID @OneRow lines @Break @Eq {
\[
\begin{array}{l}
\ldots\\
\mathit{add\_word\_to\_paragraph(abacus)}\\
\mathit{add\_word\_to\_paragraph(99)}\\
\ldots
\end{array}
\]
along one path, and
%@ID @OneRow lines @Break @Eq {
\[
\begin{array}{l}
\ldots\\
\mathit{add\_word\_to\_paragraph(abacus)}\\
\mathit{add\_word\_to\_paragraph(100)}\\
\ldots
\end{array}
\]
along the other.  However, forward references create cyclic dependencies
which cannot be handled in this way.  For them, it seems to be necessary to
add operations which change the value of words that have already been
laid out, and to propagate the resulting changes until they die out.  In
rare cases this method will cycle forever, but in practice it is probably
not difficult to avoid this problem using tricks such as refusing to
allow a revision to reduce the number of lines allocated to a paragraph.

The algorithm as expressed has exponential time complexity.  In practice,
however, the number of different layouts of a document that are close
enough to optimal to deserve examination is likely to be quite small.  The
challenge, then, is to find ways to prune the layout tree severely while
retaining enough of it to discover, for example, that setting a sequence
of paragraphs tight or loose will avoid a bad page break further on.  This
is an area needing detailed research; we can only glance at a few obvious
possibilities here.

If the badness function is monotone increasing along every operation
sequence, then a bad node can only have worse successors, and this
justifies pruning its entire subtree.  Monotonicity is not guaranteed
(for example, adding one word to a paragraph which has a widow word will
reduce its badness) but it is probable that tricks such as ignoring
widow words in incomplete paragraphs can bring us near enough to
monotonicity to justify pruning bad nodes.

One immediate application is to prune nodes whose layouts are obviously
terrible, such as nodes containing clearly premature line endings or
page endings.  Indeed, it should be possible to avoid even generating
such nodes.

When it can be established that two nodes are equivalent, in the sense
that they lay out the same subsequence and their layouts occupy the same
space, their future careers must be identical and the worst of the two
may be pruned.  The tree structure becomes a graph, and the optimal
layout algorithm may be viewed as a shortest path algorithm, as described
by Knuth~\cite {knuth1984tex}.

Establishing the equivalence of two nodes may not be easy.  There certainly
is not time for complex comparisons of all pairs of layouts
of a given subsequence.  Knuth and Plass's
algorithm recognises that two nodes are equivalent when they lay out
the same subsequence and the most recent choice on the path to each was
to start a new line.  This same idea may be used to equivalence all
paths into one at the new-page operation preceding a new chapter.

Another useful idea is to group operations together, find optimal layouts
for the group separately, then introduce an atomic operation at a higher level
which represents the entire group.  Grouping the operations that define
one paragraph in this way is very beneficial, for example.  In
isolation, optimal pragraph breaking explores many options, but in the
end it is likely to return only at most two reasonable distinct results,
of~$n$ and ${ n+1}$ lines respectively for some~${ n}$, and
these become the only choices for the atomic $\mathit{add\_paragraph}$
operation that represents the whole group at the higher level.  Furthermore,
these two results may be cached and used without recalculation on every
path containing that particular \emph{ add\_paragraph} operation whenever
the margins have the same width.

With care, suppressing tiny variations introduced by ascenders and descenders
on letters, the layout tree might be induced to contain only as many paths as
the difference in the total number of lines between the loosest and
tightest settings of the paragraphs inserted so far, and over the course of one
chapter this might be a manageable number.  For safety, a fixed upper limit
could be placed on the number of nodes kept, producing a beam
search~\cite {winston1992} which would definitely bound the time complexity
to a fixed multiple of the cost of non-optimal layout, while sacrificing
guaranteed optimality.

There do not seem to be any extra problems in incorporating optimality
into an extensible system.  Users would certainly welcome options to
user-level features such as `insert this figure either following the
current line, or at the top of the next page, whichever looks
best.'  Whether an editable system can offer optimal layout without
exceeding response time bounds is a matter for further research.  There
should be time to maintain optimality of the current paragraph at least,
and if the current chapter is set within constant-width margins, it should
be no more time-consuming to maintain optimal layout in a twenty page chapter
than it is in a twenty line paragraph, provided the two alternative paragraph
breaks of each non-current paragraph of the chapter are cached.  If the
cost does prove too great, optimality could be relegated to a button that
the user can press just before going for coffee.




\section{Conclusion}


This paper has demonstrated that a next-generation document formatting
system, incorporating the best features of current systems in full
generality, is neither logically inconsistent nor likely to be
infeasibily slow.

The major design problem is the identification of a suitable kernel
of primitive features.  Given the massive superstructure that this
kernel will support, its design quality must be of the highest.  This
design was not attempted in this paper, but the author believes that the
kernel of the Lout document formatting system would make a good starting
point, although it is too incomplete, insufficiently general, too
large, and occasionally too imprecisely defined to serve as the kernel
of a next-generation system as it stands.

The major implementation problem is to find optimizations that preserve
generality yet achieve the required response time.  This paper has
pointed out optimizations that seem quite likely to be adequate on
hardware that will be widely available in a few years.

It is also to be hoped that next-generation systems will finally lay to
rest the language issues that bedevil systems created within an English
or European language framework.  Given sufficiently general primitives,
this should be an easy matter.

\section{Acknowledgements}
The author gratefully acknowledges comments on
the first draft of this paper received from
Mike Dowling,
Ted Harding,
Robert Marsa,
and
Basile Starynkevitch.

%\bibliographystyle{plain}
%\bibliography{lout}

\begin{thebibliography}{10}

\bibitem{adobe1990ps}
{Adobe Systems, Inc}.
\newblock {\em PostScript Language Reference Manual, Second Edition}.
\newblock Addison-Wesley, 1990.

\bibitem{adobe1995frame}
{Adobe Systems, Inc}.
\newblock {\em Using FrameMaker+SGML}.
\newblock Adobe Systems, Inc., 1995.

\bibitem{apple1996quickdraw}
{Apple Computer, Inc}.
\newblock {\em Quickdraw GX}.
\newblock 1996.
\newblock Available as \url{http://support.info.apple.com/gx/gx.html}

\bibitem{brooks1991lilac}
Kenneth~P. Brooks.
\newblock Lilac: a two-view document editor.
\newblock {\em IEEE Computer}, pages 7--19, 1991.

%\bibitem{ettrich1996lyx}
%Matthias Ettrich.
%\newblock {\em Lyx}.
%\newblock 1996.
%\newblock available as
%  \url{http://www-ti.informatik.uni-tuebingen.de/~ettrich/}.

\bibitem{foxley1987music}
Eric Foxley.
\newblock Music --- a language for typesetting music scores.
\newblock {\em Software---Practice and Experience}, 17:485--502, 1987.

\bibitem{furuta1982survey}
Richard Furuta, Jeffrey Scofield, and Alan Shaw.
\newblock Document formatting systems: survey, concepts, and issues.
\newblock {\em Computing Surveys}, 14:417--472, 1982.

\bibitem{goldfarb1990sgml}
Charles~F. Goldfarb.
\newblock {\em The SGML Handbook}.
\newblock Oxford University Press, 1990.
\newblock ISBN 0-19-853737-9.

\bibitem{goldfarb1991hytime}
Charles~F. Goldfarb.
\newblock Hytime: a standard for structured hypermedia interchange.
\newblock {\em IEEE Computer}, 24:81--84, 1991.

\bibitem{interleaf1996}
{Interleaf, Inc}.
\newblock {\em Interleaf 6 for Motif: next generation document creation,
  composition and assembly}.
\newblock 1996.
\newblock Available as \url{http://www.interleaf.com/i6motifds.html}

\bibitem{kernighan1982pic}
Brian~W. Kernighan.
\newblock Pic --- a language for typesetting graphics.
\newblock {\em Software--Practice and Experience}, 12:1--21, 1982.

\bibitem{kernighan1989retro}
Brian~W. Kernighan.
\newblock The unix system document preparation tools: a retrospective.
\newblock {\em AT\&T Technical Journal}, 68:5--20, 1989.

\bibitem{kingston1993lout.design}
Jeffrey~H. Kingston.
\newblock The design and implementation of the lout document formatting
  language.
\newblock {\em Software--Practice and Experience}, 23:1001--1041, 1993.

\bibitem{kingston1995lout.program}
Jeffrey~H. Kingston.
\newblock {\em The Lout Document Formatting System (Version 3)}.
\newblock 1995.
\newblock Available as \url{ftp://ftp.cs.usyd.edu.au/jeff/lout/}

\bibitem{knuth1981bpl}
D.~E. Knuth and M.~E. Plass.
\newblock Breaking paragraphs into lines.
\newblock {\em Software--Practice and Experience}, 11:1119--1184, 1981.

\bibitem{knuth1984tex}
Donald~E. Knuth.
\newblock {\em The {\TeX}Book}.
\newblock Addison-Wesley, 1984.

\bibitem{krishnamurthy1995unix}
Balachander Krishnamurthy, editor.
\newblock {\em Practical Reusable UNIX Software}.
\newblock John Wiley, 1995.

\bibitem{lamport1986latex}
Leslie Lamport.
\newblock {\em \LaTeX\ User's Guide and Reference Manual}.
\newblock Addison-Wesley, 1986.

\bibitem{microsoft1996word}
{Microsoft, Inc.}
\newblock {\em Microsoft Word}.
\newblock Microsoft, Inc., 1996.
\newblock Available as \url{http://www.microsoft.com/msword/}

\bibitem{ossanna1976troff}
Joseph~F. Ossanna.
\newblock ``nroff/troff'' user's manual.
\newblock Technical Report~54, Bell Laboratories, Murray Hill, NJ 07974, 1976.

\bibitem{plass1981}
Michael~F. Plass.
\newblock {\em Optimal pagination techniques for automatic typesetting
  systems}.
\newblock PhD thesis, Stanford, CA, 1981.

\bibitem{reid1980scribe}
Brian~K. Reid.
\newblock A high-level approach to computer document production.
\newblock In {\em Proceedings of the 7th Symposium on the Principles of
  Programming Languages (POPL), Las Vegas NV}, pages 24--31, 1980.

\bibitem{winston1992}
P.~H. Winston.
\newblock {\em Artificial Intelligence}.
\newblock Addison-Wesley, third edition edition, 1992.

\bibitem{vanwyk1980}
Christopher J.~Van Wyk.
\newblock {\em A language for typesetting graphics}.
\newblock PhD thesis, Stanford, CA, 1980.

\end{thebibliography}

\author{Jeffrey H. Kingston\\
        \texttt{jeff@cs.usyd.edu.au}}
%\email{jeff@cs.usyd.edu.au }
%\address{Basser Department of Computer Science\\
%         The University of Sydney 2006\\
%         Australia}

\end{Article}