TUGboat, Volume 34 (2013), No. 1

47
is an adequate answer to the typesetting requirements of the nineties.

E-TEX: Guidelines for Future TEX
Extensions — revisited

Output produced by TEX has higher standards than output generated automatically bymost other typesetting systems. Therefore, inthis paper we will focus on the quality standards set by typographers for hand-typeset
documents and ask to what extent they areachieved by TEX. Limitations of TEX’s algorithms are analyzed; and missing features aswell as new concepts are outlined.

Frank MittelbachContents
1

Introduction

47

2

A short history of “Extended”-TEX engines
2.1 pTEX . . . . . . . . . . . . . . . . . .
2.2 ML-TEX . . . . . . . . . . . . . . . .
2.3 NT S/εXTEX . . . . . . . . . . . . . .
2.4 ε-TEX . . . . . . . . . . . . . . . . .
2.5 Omega/Aleph . . . . . . . . . . . . .
2.6 pdfTEX . . . . . . . . . . . . . . . .
2.7 XETEX . . . . . . . . . . . . . . . . .
2.8 LuaTEX . . . . . . . . . . . . . . . .
2.9 iTEX . . . . . . . . . . . . . . . . . .

48
48
48
49
49
49
49
49
50
50

Review of the issues raised in 1990
3.1 Line breaking . . . . . . . . . . . . .
3.1.1 Line-breaking parameters . .
3.2 Spacing . . . . . . . . . . . . . . . .
3.3 Page breaking . . . . . . . . . . . . .
3.4 Page layout . . . . . . . . . . . . . .
3.5 Penalties — measurement for decisions
3.6 Hyphenation . . . . . . . . . . . . .
3.7 Box rotation . . . . . . . . . . . . .
3.8 Fonts . . . . . . . . . . . . . . . . . .
3.9 Tables . . . . . . . . . . . . . . . . .
3.10 Math . . . . . . . . . . . . . . . . . .
3.11 TEX’s language . . . . . . . . . . . .

50
50
51
51
52
54
55
55
56
56
57
57
58

3

4

Overcoming the mouth/stomach separation 59
4.1 A standard TEX solution . . . . . . .
60
4.2 A LuaTEX solution . . . . . . . . . .
61

5Conclusions

61

List of Figures
1
2
3
4
5
6

TEX-like engines evolution . . . . . .
Areas of concern in original article .
Interword spacing . . . . . . . . . . .
TEX’s box/glue/penalty model . . .
Baseline to baseline spacing . . . . .
The expl3 logo . . . . . . . . . . . .

48
50
52
53
55
58

Abstract
Shortly after Don Knuth announced TEX 3.0 I gave
a paper analyzing TEX’s abilities as a typesetting
engine. The abstract back then said:
Now it is time, after ten years’ experience, tostep back and consider whether or not TEX 3.0

Now — two decades later — it is time to take anotherlook and see what has been achieved since then, andperhaps more importantly, what can be achieved
now with computer power having multiplied by ahuge factor and, last but not least, by the arrival ofa number of successors to TEX that have lifted someof the limitations identified back then.
1

Introduction

When I was asked by the organizers of the TUG 2012conference to give a talk, I asked myself
What am I currently working on that could
be of interest?
The answer I gave myself was: I’m working on ideas
to resolve or at least lessen the issues around complex
page layout; in particular mechanisms to re-break
textual material in different ways so that you can,for example, evaluate different float placements inconjunction with different caption formats, or to float
galley text in different ways around floats protruding
into the galley.
All that goes way back in time: the issues were
formulated more than 20 years ago in a paper I gavein 1990 in Texas: “E-TEX: Guidelines for future TEX
extensions” [26]. Back then there were no answers to
the issues raised. However, that was a long time ago;computers got faster and people invented various
TEX extensions since then — and once in a while
there are even new ideas.
So when I reread my paper from that time I
thought that it would be a good idea to analyze theissues listed from the 1990 paper again and see what
has been achieved since then.
This paper starts with a short overview of thehistory of TEX’s successor engines and the capabilities they added or improved. We will then re-analyze
issues discussed two decades ago and evaluate theirstatus.
We conclude with a summary of the findings
and a suggestion for a way forward.

E-TEX: Guidelines for Future TEX Extensions — revisited

48

TUGboat, Volume 34 (2013), No. 1

Figure 1: TEX-like engines evolution

2

A short history of “Extended”-TEX
engines

Professor Donald Knuth developed the first versionof the TEX program in 1978–79 [16, 17]. (The first
specifications in writing date back to 1977; see [21].)
Over the course of the next two years he improvedand changed the program further and it then became
known as TEX 82. This was the first widespreadversion of TEX, with documented source code [19]and a published manual [18], and people all over theworld started using it.
Back then TEX used 7-bit fonts and typesetting in languages that required diacritics (as most
European languages do) was difficult because, forexample, hyphenation didn’t work properly in thatcase. Also, mixing of several languages in one document was impossible, at least if one wanted them tobe hyphenated automatically.
Therefore, in 1989 a delegation of TEX users
from Europe came to the Stanford meeting and presented Don with a proposal to extend TEX in several ways [31]. After several meetings and public
discussions, Don recognized that he did not originally foresee a need for 8-bit input, and he agreed
to extend TEX slightly to account for the needs ofFrank Mittelbach

the extended user base [20]. However, he only accepted those proposals that could be achieved withminimal adjustments to the existing program. If
you compare The TEXbook before and after, youwill have difficulty spotting the differences, because
apart from the introduction of language support,
nothing much changed. For example, my request
for \holdinginserts was added because that wastrivial to implement, but the suggestion for providing \reconsiderparagraph (to allow undoing theparagraph breaking to re-typeset it under different
conditions) was rejected, as it would have meant more
drastic updates to the paragraph-breaking algorithm.
This new version of TEX was called TEX 3.0,
and shortly afterwards Don publicly announced that
there would be no further version of TEX (except for
bug fixes) and that his involvement in any future
development of typesetting engines has ended withthat version [20]. That announcement prompted me
to analyze TEX’s abilities compared to high quality
hand-typeset documents resulting in the paper given
at the conference in Texas.
While TEX was thus officially frozen with version 3.0, other people started to build TEX engine
variants to resolve one or another issue. The mostinfluential ones are briefly outlined below; a nice overview of the more complete picture is given in [40],from which Figure 1 was taken with kind permission.
In the following we only discuss the major developments that contributed in one way or the otherto an enriched feature set of the engine or have been
influential in other ways.
2.1

pTEX
Typesetting in Japanese requires support of a hugecharacter set and the ability to handle different typesetting directions. Thus early on developers in Japan
created an extension to TEX that supports both Kanji(two-byte fonts) and proper vertical typesetting, inaddition to TEX’s horizontally oriented approach.
Early versions of pTEX predate TEX 3.0 [11, 32].
2.2

ML-TEXOne of the earliest attempts to modify TEX itself
to handle the problem of multilingual typesetting
was Michael Ferguson’s work on ML-TEX. Amongst
other things it added a \charsubdef primitive thatprovided substitutions for accented characters. This
way TEX’s hyphenation algorithm would be able
to correctly hyphenate words with diacritics, even
if the fonts used did not contain the characters as
individual glyphs.
With the availability of T1-encoded fonts (containing most of the accented characters used in

TUGboat, Volume 34 (2013), No. 1

49“Western” languages as individual glyphs) ML-TEX
was no longer necessary for these languages. Nevertheless, it is still available in most engines, but needs
to be explicitly enabled on the command line.
NT S/εXTEXThe NT S project (New Typesetting System) was
inaugurated by DANTE (the German TEX Users
Group) in 1992. Its objective was to re-implement
TEX in a 100% compatible way in Java. While TEX
was frozen, NT S was to remain flexible and extensible. The project completed successfully in 2000,
passing the trip test, and thus proving that a reimplementation of TEX in a different language waspossible. As it turned out though, full compatibility
with TEX resulted in code that was less modular thaninitially hoped for, so that adding any extensions
or providing modifications of algorithms turned out
to be far more difficult than initially anticipated.
For this and a number of other reasons, NT S itself
wasn’t developed any further.
εXTEX is a spin-off started around 2003 with
the intention of developing a new Java-based system incorporating the experiences from NT S, ε-TEX,
pdfTEX and Omega. The project is represented on
the web [1], but as of today it hasn’t left alpha stage.
2.3

2.4

ε-TEX
ε-TEX started out in 1992 as a project by Peter
Breitenlohner reimplementing ideas by Knuth [15] fora bi-directional extension but avoiding the need forspecial DVI drivers. Ideas for additional extensions
then were added, and in 1994 the first version of
ε-TEX was published.
Around that time members from the NT S teamjoined the effort and during 1994–98 ε-TEX was run as
an NT S-project in order to provide a small numberof useful extensions to TEX to fill the gap while
NT S was still under development. As it turned out,
however, this set of extensions took on a life of its
own and over time was incorporated into all major
TEX-based engines. As a result, nowadays one canassume that all engines support the original TEX
primitives plus the extensions offered by ε-TEX.
The new features offered by ε-TEX are a number of additional programming primitives and better
tracing facilities, support for mixed-direction typesetting, and an increase in the number of most registertypes. In the area of micro-typography enhancements, it offers a generalization of \orphanpenalty
and \widowpenalty by supporting special penalty
values for the first or last n lines. It also added amethod to adjust the spacing in the last line of a para-graph to be close to that of the preceding line (insteadof being set tight as standard TEX normally does).
2.5

Omega/Aleph

Omega, developed by John Plaice with Yannis Haralambous contributing ideas and developing fonts,
was the first extension of the TEX program that supported Unicode instead of 8-bit input encodings. The
driving force behind its development was to enhance
TEX’s multilingual typesetting abilities and bettersupport for complex scripts.
Aleph is a spin-off of Omega that was started
to include ε-TEX capabilities and stabilize the codebase. Neither project is being developed any more,
but most of Aleph’s and thus Omega’s functionality
has been integrated into LuaTEX.
2.6

pdfTEX
The pdfTEX engine started as a Master’s thesis byHàn Thê´ Thành in the mid-nineties and initiallyoffered PDF output, support for embedded Type 1
fonts, virtual fonts, hyper-links, and compression.
For his PhD thesis [37], Hàn Thê´ Thành experimented with various micro-typography algorithms
including the hz approach [42] and several of themwere implemented in pdfTEX [38, 39].
Today, pdfTEX (with the ε-TEX extensions included) is the dominant TEX-based engine in practical use, i.e., all major distributions use this programas the default TEX engine.
2.7

XETEX
XETEX is one of the more recent additions to the TEX
engine successors [6]. It was created by Jonathan
Kew and provides as one of its major distinguishingfeatures extensive support for modern font technologies such as OpenType, Graphite and Apple Advanced Typography (AAT). It can make direct useof the advanced typographic features offered by thesefont technologies, such as alternative glyphs, swashes,
optional ligatures, variant weights, etc. These fonts
can be used without the need for configuring TEX
font metrics for them.1
XETEX natively supports Unicode both for input(UTF-8 encoding) as well as for accessing font glyphs.
It can also typeset mathematics using Unicode fonts
such as Cambria Math or Asana Math [3], provided
they contain special mathematical features.
1. The downside of this is that it can’t be guaranteed thatthe formatting of a source document does not change overtime (when libraries are updated on the host system) andthere is no way to freeze all components of a document, as ispossible with traditional TEX.

E-TEX: Guidelines for Future TEX Extensions — revisited

50

TUGboat, Volume 34 (2013), No. 1

Figure 2: Areas of concern in original article

2.8

LuaTEXLuaTEX made its first public appearance in 2005
at the TUG conference in China, as a version of
pdfTEX with an embedded Lua scripting engine. The
first public beta was presented in 2007. It is being
developed by a core team of Hans Hagen, Hartmut
Henkel and Taco Hoekwater [4].
Important project objectives are merging of engines (combining ideas from Aleph and pdfTEX),
support for OpenType fonts, and access to all TEX
internals from Lua. Through various callbacks it ispossible to hook into TEX’s typesetting algorithms
and adjust or even replace them.
2.9

iTEX
Finally, as the ultimate successor engine we have or
will have iTEX, a fictitious XML-based successor to
TEX announced by Donald Knuth at the TUG 2010conference in San Francisco [14]. According to its
author this program will resolve all issues related tohigh quality typesetting, including those that aren’t
yet discovered — we can only hope that it doesn’ttake Don too much time to finish it.
3

Review of the issues raised in 1990

With the knowledge of what today’s successors of
the TEX engine are capable of, we are now ready tore-analyze the issues discussed two decades ago andevaluate which of them are nowadays:
1. resolved (best case, denoted byU

below), or

2. could now be resolved using the improved
features of modern engines (hopeful case,denoted by
), or

R

Frank MittelbachD

3. is still out there waiting for a resolution(bad case, denoted by).
We follow the order of the original paper (see Figure 2) to help people looking up additional details
on the problems outlined. It is available in facsimile
on the web [26].
3.1Line breaking

TEX’s line-breaking algorithm is clearly a central partof the TEX system. Instead of finding breaks line
by line, the algorithm regards paragraphs as a unit
and searches for an ‘optimal solution’ based on thecurrent values of several parameters. Consequently,
a comparison of results produced by TEX and othersystems will normally favor TEX’s methods.
Such an approach, however, has its drawbacks,
especially in situations requiring more than blockstyle text with a fixed width.

R

Issue: No post-processing of final lines based on
their content
The final line breaks are determined at a time when
information about the content of the current line has
been lost (at least for the eyes of TEX, i.e., its own
macro language), so that TEX provides no support
for post-processing of the final lines based on theircontent.
For example, the last line of a paragraph isusually typeset using normal spacing between words,
even if the previous line has been set loosely or tightly.
(ε-TEX can now handle this to some extent, with its\lastlinefit primitive.)
Another example is that the tallest object in aline determines its height or depth so that lines might

TUGboat, Volume 34 (2013), No. 1

51

get spread apart, even if they would fit perfectly.
In theory these issues could now be cateredto with the LuaTEX program, because it offers theability to post-process the lines and modify the final
appearance.

DR

Issue: No way to influence the paragraphshape with regard to the current position on the page
TEX and all its successors break paragraph text intolines at a time where they do not know where thistext will eventually appear on a page. Consequently,
there is no possibility within the model of catering
to special paragraph shape requirements based onthat position.
The only way to work around this is a complex
feedback loop, using placement information from aprevious run to calculate the necessary \parshape.
Because this requires multi-pass formatting (withmany passes), it is impractical. A simpler, thoughstill complicated, approach is to assume a strict linear
formatting, in which case one can build the paragraph shapes one after the other.
A new approach, that we are currently exploringfor LATEX3, involves storing paragraph data in a data
structure that allows re-breaking the material fortrial typesetting. This is outlined in Section 4.
3.1.1

Line-breaking parameters

While the algorithm provides a wide variety of parameters to influence layout, some important ones
for high-quality typesetting are missing. To resolve
some of these issues, we need only (slightly) modify
or extend the current algorithm. For others, serious research is required just to understand how asolution might be approached.
None of the engines has modified the TEX algorithm, so all of the problems are still unsolved.
LuaTEX offers a way to replace the whole algorithm, but for most of these problems, that would
be overkill, because it would require reprogramming
everything from scratch in Lua.

R

Issue: Zero-width indentation box

When TEX breaks text into individual lines it discards whitespace and kerns at both sides of eachline except for the first. On the left side of the firstline (in left-to-right formatting) the existence of theparagraph indentation box prevents this from happening. Normally this is not noticeable, but in thecase of layouts without paragraph indentation it canlead to problems, e.g., when \mathsurround has apositive value.
In LuaTEX this could now be resolved by defining code that preprocesses the paragraph material

and removes discardable items following the indentation box.

D

Issue: Managing consecutive hyphens in a
general way
In TEX it is possible to discourage two consecutive
hyphens, but there is no way to prohibit or strongly
discourage three or more. Technically, this would
mean a slight extension of the current algorithm bykeeping track of the number of hyphens in a row.
None of today’s engines supports that concept.

R

Issue: Only four types of line quality

To implement good-looking paragraphs, TEX classifies each line into one of four categories based on theline’s glue setting (tight, decent, loose, very loose). It
then uses that classification to avoid abrupt changes
in spacing (if possible). However, the small numberof classes results in grouping of fairly incompatible
settings in a single class (especially, loose and veryloose are affected). Technically, it would be simple
to extend the number of classes to support better
granularity.

D

Issue: Rivers and identical words across lines

If interword spaces from different lines happen tofall close to each other, they form noticeable stripes(rivers) through the paragraph that can be quite
disconcerting. TEX’s line-breaking algorithm is unable to detect such situations. Resolving this would
require serious research into the question on how
to detect rivers and how to classify the “badness”
of different scenarios in order to programmaticallyhandle it through an algorithm.
A somewhat related issue (but rather easier toresolve) is the placement of the same word at thesame position in consecutive lines, especially at the
beginnings of lines, which is likely to disrupt thereading flow.
3.2

Spacing

Micro-typography deals with methods for improving the readability and appearance of text; see forexample [5]. While TEX already does a great job inthis area, some of the finer controls and methods are
not available in the original program.
However, most of them have been implemented
in some of the successor engines and an interface for
LATEX to these micro-typography features is provided
through the package microtype [33].

R

Issue: No flexible interword spacing

In order to produce justified text, a line-breaking
algorithm has to stretch or shrink the interword

E-TEX: Guidelines for Future TEX Extensions — revisited

52

TUGboat, Volume 34 (2013), No. 1
2

6

7 5

3

4

1

Das Aus kam in der letzten Runde, wobei
Das Aus kam in der letzten Runde, wobei
Das Aus kam in der letzten Runde, wobei
Das Aus kam in der letzten Runde, wobei
Das Aus kam in der letzten Runde,wobei
DasAus kam in der letzten Runde,wobei
Das Aus kam in der letzten Runde, wobei
Figure 3: Interword spacing
The interword spaces are numbered in a way sothat higher numbers denote spaces which should
shrink less using the rules given by Siemoneit [34].
The last line shows the resulting overfull box
which would be produced by standard TEX in
this situation.

space starting from some optimal value (e.g., givenby the font designer) until the final word positions
are determined. TEX has a well-designed algorithm
to take such stretchability into account. It can also
alter spacing depending on the character in front of
the space to change the behavior after punctuation,for example.
There is no provision, however, for influencing
the interword spaces in relation to the current characters on both word boundaries. Ideally, shrinking
or stretching should depend on the character shapes
on both sides of the space as exemplified in Figure 3.
None of the TEX successors provides any additional support for controlling the interword spacing above and beyond TEX’s capabilities. But withLuaTEX’s callback interfaces it is possible to analyze
and modify textual material just before it is passed
to the line-breaking algorithm. This allows for ways
to resolve this issue either as a table-based solution(one size fits all), or on a more granular level where
the chosen adjustments are tied to the current font.

U

Issue: No flexible intercharacter spacing

Instead of, or in addition to, stretching or shrinking
the interword spaces to produce justified text, there
are also the methods of tracking (increasing or decreasing inter-letter spaces) and expansion (changing
the width of glyphs). There are debates by designers
whether such distortions are acceptable approaches,
but there is not much doubt that, if used with careand not excessively, they can help to successfully
resolve difficult typesetting scenarios.2
pdfTEX provides both methods, the latter byimplementing a version of the hz algorithm originallydeveloped by Hermann Zapf and Peter Karow [42].

U

Issue: No native support for hanging punctuation

Don Knuth [18, pp. 394–395] gave an example of how
to achieve hanging punctuation but it required theFrank Mittelbachuse of specially adjusted fonts and it also interferedwith the ligature mechanism. In other words, it is
only a partial solution for restricted scenarios.
Fortunately, a fully general solution was implemented in pdfTEX and later also incorporated
into LuaTEX, so nowadays this can be considered resolved. The remainder of the article is typeset using
hanging punctuation to allow for a comparison.
3.3

Page breaking

In 1990 I wrote “The main contribution of TEX 82
to computer-based typesetting was the step takenfrom a line-by-line paragraph-breaking algorithm toa global optimizing algorithm. The main goal fora future system should be to solve the similar, butmore complex, problem of global page breaking”.
Unfortunately in the TEX world no serious attempt
was made since then to address the fundamental
limitation in TEX’s algorithm, let alone designing andimplementing a globally optimizing page-breaking
algorithm.3

D

Issue: TEX generates pages based on
precompiled paragraph data
This issue describes the fundamental problem in
TEX’s approach: the program builds optimized paragraph shapes without any knowledge about their final
placement on a page. The result is a “galley” fromwhich columns are cut to a specified vertical size. A
consequence of this is that one can’t have the shapeof a paragraph depend on its final position on thepage when using TEX’s page builder algorithm.
To some extent, it is possible to program aroundthis limitation, e.g., by measuring the remaining
space on a page and explicitly changing paragraphshapes after determining where the current textual
material will finally appear. However, besides being
complicated to implement, it requires accounting for
all kinds of special situations that normally would
be automatically managed by TEX, and providing“programmed” solutions for them.
As a result, all attempts so far to provide suchfunctionality had to impose strong limitations on
the allowed input material, i.e., they worked only
in restricted setups and even then, the results were
often not satisfactory.
2. On page 54 one paragraph was typeset with a negative
expansion of 3% to avoid an overfull line. See if you can spot
it without peeking at the end of the article where we reveal
which it was.
3. In the wider document engineering research community
some research was carried out in the last thirty years, e.g.,[7, 9, 22, 41], but so far none has led to a production system.

TUGboat, Volume 34 (2013), No. 1

RU

53

Figure 4: TEX’s box/glue/penalty model

Issue: Paragraphs already broken intocolumns can’t be reformatted based on page/column
break decisions

The main operations possible in TEX’s box/glue/
penalty-model are shown in Figure 4. All macro processing that acts on the level of tokens (characters/
symbols, spaces, etc.) is only possible before TEX
builds the so-called “unset horizontal lists” in whichcharacter tokens change their nature into glyphs
from fonts. From that point on, the manipulation
possibilities are reduced to the level of box manipu-

lations that only allow relatively few actions, suchas removal of the last item in a box. However, those
operations have severe limitations, e.g., one can’t
remove glyphs from a horizontal list nor is there any
possibility to convert the data back to character tokens, etc. that could be directly reprocessed by themacro processor.
The moment TEX turns an “unset horizontallist” into an “unset vertical list”, i.e., when it applies
line breaking, we move to the bottom half of themodel and from there, there is no fully general way

E-TEX: Guidelines for Future TEX Extensions — revisited

54

TUGboat, Volume 34 (2013), No. 1

to get back to the upper half. At the line breaks, wepotentially lose spaces that can’t be recovered. Thus,
it is not possible to reconstruct the original “unset
horizontal list” even if we would recursively take off
items from the end of the “unset vertical list” in theattempt to reassemble it.
As a consequence it is not possible to safely reusetextual material once it has been manipulated by
TEX’s paragraph builder. Instead one needs to find away to record the “unset horizontal list”. That this iseasily possible in LuaTEX (but also in standard TEX
with somewhat more effort) will be demonstrated in
Section 4 on page 59, which is the reason why wegive this issue a combined
rating.

RU

3.4

Page layout

For the tasks of page makeup, TEX provides theconcept of output routines together with insertions
and marks. The concepts of insertions and marks are
tailored to the needs of a relatively simple page layout
model involving only one column output, footnotes,
and at the most, simple figures once in a while.4
The mark mechanism provides information aboutcertain objects and their relative order on the current page, or more specifically, information about thefirst and last of these objects on the current page
and about the last of these objects on any of thepreceding pages. However, being a global concept
only one class of objects can take advantage of thewhole mechanism.5

DU

Issue: Only a single type of marks isfully supported
In the original paper, I suggested extending this tosupport multiple independent mark registers; thatidea was later implemented in the ε-TEX program.
As it turned out, however, this did not really solve
the issue. Whenever the page layout gets more complicated and output routines are used to inspect thecurrent state without actually shipping out pages
in a linear fashion, the information maintained in\topmark is always lost.
In the end, we abandoned the whole mechanism
for LATEX3 and used only TEX’s \botmark registerto put marks on the page and kept track of all otherinformation (class of mark and content of the mark)externally [27]. This solves the issue, but at a fairly
high programming cost with complex data management.

D

Issue: Missing built-in support for complex
float management
Float placement across different types of publications
is governed by rules of high complexity: placement
Frank Mittelbach

options may depend on aesthetic requirements, captions and legends might require different formatting
depending on placement, positioning of floats may
influence options available for other floats, etc.
Unfortunately, out of the box, TEX offers only asimplistic mechanism derived as an extension to thefootnote concept. LATEX extended this to a slightly
more flexible algorithm but only with respect tosupporting different classes of floats (where the floats
of one class have to stay in sequence) and by adding
a few parameters to add limits for the number offloats in a float area or the maximum size of an area.
More complex rules or arrangements with varying
formatting depending on placements, support for
floats across multiple columns (other than a simple
two-column mode) are not supported.
To some extent, this is not that surprising, because codification of placement rules and effective
algorithms for computing complex layouts is an areathat is not well understood, and at the same timehasn’t attracted much attention by the research community. Only a handful of publications in three
decades approach one or another aspect of this topic[7, 12, 25, 27, 30]. For the same reason, none of thenewer engines offers any additional built-in support
that would ease the implementation of more complex algorithms. Using an early version of expl3, anattempt was made [27] to design and implement acustomizable float algorithm that supports a richer
set of rules. Unfortunately this has not yet gone
beyond a proof-of-concept implementation.6

D

Issue: No conceptual support for baseline tobaseline spacing
For designers, TEX’s way of specifying interline glue isa rather foreign concept; they typically use baselineto-baseline spacing instructions in their specifications.
Unfortunately, those prescriptions are not directly
possible in TEX because of the way TEX determinesthe “current” \baselineskip value: see Figure 5 on
the next page. Only with rigorous control on the
4. The term ‘one column output’ means that all text is
assembled using the same line width. Problems with variable
line width are discussed in Section 3.3. Of course, this alreadycovers a wide range of possible multi-column layouts, e.g.,
the footnote handling in this article. But a similar range ofinteresting layouts is not definable in TEX’s box-glue-penalty
model.
5. The LATEX implementation provides an extended markmechanism with two kinds of independent marks with theresult that one always behaves like a \firstmark and the otherlike a \botmark. The information contained in the primitive\topmark is lost.
6. A new implementation of these ideas using the current
expl3 language is high on the current LATEX3 road map.

TUGboat, Volume 34 (2013), No. 1

6
?

?

6
?
6
?
6
?
6
?
6
?

55

\baselineskip 1

data structures. If and how this could be usefully
deployed remains to be seen. To my knowledge, no
LuaTEX-specific code for grid design yet exists.

\baselineskip 1\parskip

3.5\baselineskip 2\baselineskip 2

Figure 5: Baseline to baseline spacing
To implement a baseline to baseline dimension,for example between a paragraph and a heading(denoted by the question mark), the value for\parskip has to be determined depending on the\baselineskip of the second paragraph. Unfortunately, the value of \baselineskip used willbe the one current at the end of the second paragraph while the \parskip has to be computed atits beginning.

programming level (i.e., by preventing the users andpackage writer from accessing the full power of TEX)
can one provide an interface supporting baseline-tobaseline spacing specification.
Because the interline glue concept is deeply
buried in TEX algorithms, it is not surprising thatnone of today’s engines (including LuaTEX) addresses
this area.

D

Penalties — measurement for decisions

Line and page breaks in TEX are determined chiefly
by weighing the “badness” of the resulting output7
and the penalty for breaking at the current point.
This works very well in most situations but there is
one severe problem with the concept of penalties.

D

Issue: Consecutive penalties behave
as min(p1 , p2 )The problem is that an implicit penalty (e.g., fordiscouraging but not prohibiting orphans or widows)
will always allow a break at this particular point even
if an explicit penalty by the user attempts to disallow a break there. Changing the algorithm to usemax(p1 , p2 ) instead would resolve the problem. With
this approach an explicit breakpoint could still beinserted by interrupting the sequence of consecutive
penalties, e.g., through \kern0pt.
With LuaTEX this could probably be implemented, but would most likely require very complicated parsing and manipulation of internal TEX
data structures, unless LuaTEX itself gets extended,i.e., by making the code that handles consecutive
penalties directly accessible.

Issue: No built-in support for grid-based design

TEX’s concepts that conflict with baseline to baseline spacing also make grid-based design difficult, as
this strongly depends on text baselines appearing inpredictable positions.
Nevertheless, over the last three decades there
have been a number of attempts to provide support
for grid based-design on top of standard LATEX. Noneof them has been particularly successful — due to themissing support from the engine, all of them worked
only with subsets of the many LATEX packages. To
make things work, it is necessary to adjust behaviorof various commands, and thus any package notexplicitly considered is a likely candidate for disaster.
The xor package for LATEX3 offers a structured
interface on the code level for grid-design. Unfortunately, it isn’t production ready and awaits a major refactoring based on the new expl3 language for
LATEX3. But even then it would suffer from the limitations listed above as long as it is used together
with LATEX 2ε packages that do not interface with its
grid support.
From an engine perspective, LuaTEX is the only
engine that offers some additional possibilities that
may help with grid design, through additional hooks
provided, and through access to the internal TEX

3.6

Hyphenation

Whentypesetting
text,
especiallyinnarrow
columns,
hyphenation
isoften
inevitable in order to avoid unreadable,
spacedoutlines.
TEX’s pattern-based hyphenation algorithm [23] isquite good at identifying correct hyphenation points
to avoid such situations.
However, hyphenation is a second-best solution
and, if applied, there are a number of guidelines thatan algorithm should follow to improve the overall
result. Several of them cannot be specified with
TEX’s algorithm. In fact, all of the ones below are
unresolved with today’s engines, if we disregard thatin LuaTEX one could in principle replace the fullparagraph-breaking algorithm with a new routine.

D

Issue: Prevent more than two consecutive
hyphens
Hyphenation of two consecutive lines is controlled by the algorithm (\doublehyphendemerits),
7. The badness is a function of the white space used in aline in comparison to the optimal amount, e.g., if the space
between words needs to stretch or shrink, the badness of thesolution increases.

E-TEX: Guidelines for Future TEX Extensions — revisited

56

TUGboat, Volume 34 (2013), No. 1

but there is no possibility of avoiding paragraphs like the current one, in certain circumstances. As one can easily observe, the number of hyphens in this paragraph has been artificially increased by setting relevant line-breaking parameters to unusual values. In languages that have
longer average word lengths than English, such situations present real-life problems.

D

Issue: Assigning weights to hyphenation points

TEX’s hyphenation algorithm knows only two states:
a place in a word can or cannot act as a hyphenation point. However, in real life certain hyphenation
points are preferable over others. For example, “Nonnenkloster” (abbey of nuns) should preferably not
be hyphenated as “Nonnenklo-ster” (as that would
leave the word “nun’s toilet” on the first line).

D

Issue: More generally, support other approaches
to hyphenation
Liang’s pattern-based approach works very well for
languages for which the hyphenation rules can be
expressed as patterns of adjacent characters next tohyphenation points. Such patterns may not be easy
to detect but once determined they will hyphenate
reasonably well. For the approach to be usable, thenecessary set of patterns should be be reasonably
small, as each discrepancy needs one or more exception patterns with the result that the pattern set
would either become very large or the hyphenation
results would have many errors.
To improve the situation for the latter type of
languages one would need to implement and potentially first develop other types of approaches. For
now Liang’s algorithm is hardwired in all engines,
though in theory LuaTEX offers possibilities of dropping in some replacement.
3.7

Box rotation

TEX’s concept of document representation is strictly
horizontal and left-to-right oriented. Any further
manipulation is left to the capabilities of the output
device using \special commands in the language ofthe device.

U

Issue: No built-in support for rotation

Because of the lack of a common interface for suchoperations, any document making use of \special
commands is processable only in a specific environment, so that exchange of such documents is only
possible in a limited fashion.
With the event of LATEX 2ε the LATEX project
team resolved this issue by providing an abstract
interface layer that (in the form of the graphics andFrank Mittelbach

color packages) hides the device peculiarities internally so that documents using these interfaces became portable again.

R
3.8

Fonts
Issue: Available font information (non-issue)

In the Texas paper, I suggested that additional fontcharacteristics should be made available as font parameters to enable smarter layout algorithms. Looking at this from today’s perspective I think it waslargely a misguided idea, at least until recently. Manyof the fonts that have been made accessible to the
TEX engines in the last decades (mainly PostScript
Type 1 fonts) do indeed have various additional attributes defined by their designers but alas withlargely non-comparable values between different fonts
making any interpretation difficult if not impossible.
With OpenType fonts, this may change again,and engines like XETEX or LuaTEX allow access tosuch additional attributes.

UR

Issue: Encoding standardization

By default, TEX translates the input encoding (representation of characters in the document) one to
one into the output encoding (glyph positions in
the current font). E.g., if you put a “b” into yourdocument then this is understood as “typeset thecharacter in position 96 (ascii code for “b”) in thecurrent font”. This tight coupling between encodingof data in different places required that fonts usedby TEX always stored the glyphs in the same position (which they did only partially) or that the user
understood the subtle differences and adjusted the
document input accordingly. For example, in plain
TEX the command \$ produces a $-sign — unless you
are typesetting in Computer Modern Text Italic, inwhich case your output suddenly shows £-signs.
With more and more fonts (with different fontencodings) becoming available and TEX entering the
8-bit world (with numerous input encodings interpreting the document source differently), such issues
got worse.
These problems were resolved for LATEX throughthree developments. Don Knuth developed the ideaof virtual fonts [13] and that concept was quickly
adopted by nearly all major output-device drivers, sothat it became usable in practical terms.8 With thisconcept available the TEX community agreed in Cork
on a special virtual font encoding [2]. Finally wedesigned and implemented the LATEX Internal Char8. In 1990 I expressed my hope that these ideas would help
to simplify matters [26, p. 342] and as it turned out, that was
indeed the case.

TUGboat, Volume 34 (2013), No. 1

57

acter Encoding for LATEX 2ε (LICR) [29, chap. 7] thattransparently maps between different input encodings and arbitrary font encodings. This is perhaps
not a perfect solution, but for the 8-bit world it
effectively resolved the issues.
Unicode support was also addressed (throughthe inputenc package) but here better support fromthe engines is required to come to a fully satisfactory solution. As mentioned above, explicit Unicode
support was first added by Omega, and from there
made its way into Aleph and LuaTEX. XETEX also
natively supports Unicode.

R

Issue: Ligature and kerning table manipulation

In TEX, ligatures and kerns are properties of fonts,
i.e., they apply to all text in a document. However,different languages use different rules about what toapply or not to apply in this case. Thus to model
this in TEX, one would need to define private fonts
per language, each differing only in their ligature andkerning tables. While this would be a theoreticalpossibility, in practical terms it would be a logisticalnightmare and so nobody has ever tried to implement
such fine points of micro-typography.
With pdfTEX this situation changed somewhat
as pdfTEX supports suppressing all ligatures or all
ligatures that start with a certain character. This
alone does not help much though, as it does notallow, for example, prohibiting the “ffl” ligature (notused in the German language) while allowing for theother ligatures starting with “f”, nor does it support
implementing new ligatures, such as “ft” or “ck”,
through negative kerning.
LuaTEX takes this a huge step forward and provides the necessary controls to improve the situation considerably. While I was writing this article(and asking around), the first experimental packages
started to appear, e.g., selnolig [24] by Mico Loretan,so it will be interesting to see what happens in thenear future.

D
3.9

TablesIssue: Combining horizontally- andvertically-spanned columns is impossible
TEX’s input format is inherently linear, and so it is
not surprising that any TEX interface to inherently
two-dimensional table data is somewhat limited. Outof the box TEX supports column formatting, e.g., it
can calculate the necessary column width and apply a default formatting per column. It also allows
for horizontally-spanned cells with their own formatting. However, there is no provision for providing
cells whose content is able to reflow depending on
the available space nor is there any mechanism toprovide vertically-spanned cells. Both are essential
formatting requirements.
LATEX offers a higher-level document syntax tothe low-level capabilities that TEX provides, and overtime, many packages appeared that enhanced thesolution in one way or the other. However, without
any underlying direct support for the more complex
concepts all these efforts show limitations and areoften difficult to use. So far none of the existing
engines addresses this area.
3.10

Math

Mathematical typesetting is one of TEX’s major domains where — even today after thirty years — noother automatic typesetting system has been able
fully to catch up. But even in this area several things
could be improved.

DU

Issue: Some mathematical constructs are
not naturally available in TEX, e.g., double accents,
under-accents, equation number placement, . . .
For many of these problems workarounds have been
implemented as (fairly complex) plain TEX macros
by Michael Spivak in the AMS-TEX format [35, 36].
Most of this code plus further extensions were ported
to LATEX and are nowadays available as the LATEX
package amsmath.
For this reason this issue can be largely regarded
as solved, even though native support for most ofthese constructs would improve the situation further.

U

Issue: Spacing rules and parameters are all
hardwired in the engine or the math fonts
TEX’s spacing rules for math are quite good, but incases where they needed adjustments, it was either
impossible or quite difficult to do. This restriction
has been finally lifted with LuaTEX, because thatengine offers access to all internal parameters of TEX.

D

Issue: Sub-formulas are always typeset at theirnatural width
No engine so far provided any alteration to the corealgorithms of TEX that format a formula. Thus subformulas (for example from \left . . . \right) arestill boxed at natural width even if the top level
math-list is subject to stretching or shrinking. This
also means that there is no way to automaticallybreak such constructs across lines.

R

Issue: Line breaking in formulas (not listed inoriginal paper)
Don declared line breaking in math too hard for
TEX to do automatically and as a result countlessusers struggled with manually formatting displayed

E-TEX: Guidelines for Future TEX Extensions — revisited

58
equations to fit a given measure. For a long time it
looked as if that problem was indeed too difficult totackle within the constraints of a formatting engine.
However, in the late nineties Michael Downes proved
everybody wrong by designing and implementing afirst version of the breqn package for LATEX.
This package — further improved by Morten
Høgholm after Michael’s untimely death — gets us
already quite a way toward the goal of high-quality
automatic line breaking in formulas [10]. However,with the increased processing power now available
and with LuaTEX’s access to TEX internals, it should
be possible to solve most or all of the remaining problems identified.
3.11

TEX’s language
In 1990 I made the bold statement: “TEX’s language
is suitable for simple programming jobs. It is likethe step taken from machine language to assembler”.
Since then the new engines added one or the otherprimitive, but with the exception of LuaTEX, which
added an interface to Lua as an additional programming language, the situation hasn’t improved withrespect to core engine support.

U

Issue: Incompleteness with respect to standard
programming constructs
While this statement is still true with respect to mostengines, the situation has nevertheless improved.
With expl3 the LATEX Project team has provided
a programming layer that offers a large set of datatypes and programming constructs. The development of expl3 started in fact long ago: initial implementations date back to 1992. However, backthen, the processing power of machines was not goodenough to allow executing code written in expl3 at
a reasonable speed. For that reason, the ideas andconcepts were put on the shelf, and the project teaminstead concentrated on providing, and later on maintaining, LATEX 2ε .
Since then processor speed has increased tremendously, and as a result it became feasible to finally
use the ideas that had been initially developed nearly
two decades ago. The core of expl3 has been reimplemented (again) and its stable release is now gaining
more and more friends — it even got its own logo
designed as shown in Figure 6.

TUGboat, Volume 34 (2013), No. 1

Figure 6: The expl3 logo (courtesy of Paulo Cereda)

despite this grumbling, nobody came up with a workable alternative model that successfully combinesneed for simple and easy input of document material(which makes up the bulk of a TEX document) andthe special needs of a programming environment thatavoids the complexity of programming by macro expansion (which indeed becomes complex and difficult
to understand if used for non-trivial tasks).
That the TEX language can be used to produce
truly obfuscated code was nicely demonstrated byDavid Carlisle’s seasonal puzzle [8] which is worth
taking a look at, but even normal coding practice will
easily lead to code that is difficult to understand (andto maintain) as demonstrated by many of today’s
packages. Part of the reason for this is that allcoding practice around LATEX 2ε (and other macro
formats) is based on concepts and ideas originated inplain TEX, with more and more complexity layeredon top but without fundamentally questioning thecore approach which was never intended for complex
programming tasks.
So why? Largely because with expl3 we now
have a foundation layer available, that — while stillbased on macro expansion — provides a comfortable
programming environment. From the engine side
LuaTEX nicely sidesteps the question by providing aseparate programming language in addition.

U

U

Issue: A macro language . . . good or bad? /Difficulty of managing expansion-based code

Issue: Inability to access and manipulate certain
internal TEX data structures
Many of TEX’s internal data structures are inaccessible to the programmer or only observable indirectly.9
Thus, whenever an adjustment to one of TEX’s internal algorithms is needed it becomes necessary to
bypass the algorithm completely and reimplement
it on the macro level. This means accepting hugeinefficiencies and in many cases makes such implementations unusable in real-life applications.

Since the first implementation of TEX people havevoiced their concern about the fact that the TEX language is a macro language that works by expansion
and not a “proper” programming language. However,

9. In the 1990 paper I gave the example of measuring thelength of the last line in a paragraph by artificially following itby an invisible displayed formula as only within such a display
is the desired information made available.

U

Frank Mittelbach

TUGboat, Volume 34 (2013), No. 1

59

For more than two decades this was the situation with all engines. Finally LuaTEX broke thisrestriction by offering access to all (or nearly all)internals including the ability to modify them (withthe danger of breaking the system in unforeseen ways,
but that comes with the territory).

UR

Issue: The problem of mouth andstomach separation
This is perhaps one of most fundamental issues: notso much with the language but with the underlying
data structure. A special case of this issue — andperhaps the most important one — was already discussed in Section 3.3 on page 53: the inability toreformat paragraph data that is already broken into
individual lines.
TEX divides its internal processing into twoparts: the token parsing and manipulation where
expansion happens (termed the “mouth”) and thebox generation and manipulation processes that build
up the elements on the page (called the “stomach”).
Figure 4 on page 53 depicts the operations available
in the “stomach” with the two main entry points
from the “mouth”on the far left. And, as in real
life, this is largely a one-way street, i.e., once tokens
have been transformed into boxes and glue there is
no way of getting back to tokens. Furthermore, manipulation possibilities of already-processed material
are limited and usually result in loss of information,
so that one has to ensure staying at the token level
until the very last moment.
Unfortunately there are also issues with staying
at the token level. For one, only the typesetting stage
will provide the necessary information to successfully
position material on the page, e.g., to find out how
much space some text will occupy or where and on
which page a reference to a float will fall. Thus
trial typesetting is necessary and the source material
would need to be stored on the token level.
However, reprocessing token material meansthat the same macro processing happens several
times when you are doing the trial typesetting. If
this processing has side effects, such as incrementing
a counter, one needs to keep track of all such changes
and undo them before restarting a trial.
From the engine perspective the best approach
would be to either• provide access and manipulation possibilities
from the “mouth” to an intermediate data structure that holds character data plus attributes
before they are turned into glyphs, or• provide additional manipulation possibilities of“stomach” material, or• offer conversion of typeset material back to token
data similar to what \showbox offers as symbolic
information in the transcript file.
Sadly, none of the engines offers any direct support
in this area. However, we will see that, with today’s
increase in processing power, it becomes feasible toimplement a strictly TEX-based solution. This solution has some (acceptable) limitations for boundary
cases, but a variant implementation using LuaTEX’s
callback interface can even get rid of those, as we’ll
see in the next section. For this reason we give thisissue arating today.

UR

4

Overcoming the mouth/stomach
separation

If we look back to Figure 4 on page 53 we can see thatthe best data structure available for use in trial typesetting is the “unset horizontal list”. The moment
we apply line breaking we would lose informationand if we store the information at an earlier stage(i.e., as token data) we would have to deal with theside effects of repetitive token processing.
Unfortunately, the “unset horizontal list” is nota data structure made available by TEX. What is
possible though (looking at the right side of the
diagram), is to store it in a horizontal box. At alater stage this box can then be transformed backinto an “unset horizontal list” and that could thenbe typeset into a “trial” paragraph shape.
However, simply storing the content of one ormore paragraphs into an \hbox for later processing
is not a workable option either, because:• TEX applies some “optimizations” in restrictedhorizontal mode to save some processing time.10
Under the assumption that text in an \hbox
cannot be broken into several lines, it drops
all break penalties from in-line formulas (i.e.,
those normally added after binaries and relational symbols) and also doesn’t add any implicit \discretionary hyphens in place of “-”.
For the same reason it also ignores changes to\language.
• If we save each paragraph into one \hbox thenwe effectively surround each paragraph by a TEX
group. Thus local changes, such as modifications
to fonts or language would suddenly end at theparagraph boundary.
While these restrictions can be overcome, it means a
far more elaborate approach needs to be taken.
10. While such optimizations have been important at thetime TEX was originally developed, the speed gain they offer
nowadays is negligible. What remains are inconsistencies inprocessing that should get removed in today’s engines such as
pdfTEX and LuaTEX.

E-TEX: Guidelines for Future TEX Extensions — revisited

60
4.1

TUGboat, Volume 34 (2013), No. 1
A standard TEX solution

If storing the “unset horizontal list” directly in an\hbox is not an option, what alternative is available
according to our Figure 4? The only other path that
results in an \hbox is to transform the list into an“unset vertical list” and then remove the last box fromthat list (i.e., a circular path in clockwise direction
around the center of the diagram). To make thiswork we have to overcome the limitations listed atvarious places along the path:
1. Transforming an “unset horizontal list” into an“unset vertical list” loses glues and penalties atline breaks.
2. Decomposition of the “unset vertical list” is notpossible on the main galley.
3. Decomposition of the “unset vertical list” stops
at the first node that is not a box, glue, penalty,or kern item.
To alleviate issue 1 we will build our “unset verticallist” using the largest possible \hsize available in
TEX. We remove the indentation box whenever westart a paragraph. In addition, we trap any forced
break penalty, record it, and prematurely end theparagraph at this point to stay in control. As aresult each \hbox in the resulting “unset vertical list”
will contain exactly the paragraph material from one
forced break to the next (considering the paragraphboundaries as forced breaks).
What happens if the paragraph material exceeds
the largest possible dimension available in TEX? In
that case (which means that the paragraph is noticeably longer than a page) we will end up withuncontrolled line breaks. In TEX it is impossible
to prevent this from happening, but at least it ispossible to detect that it happened. One can thenwarn the user and request that the paragraph beartificially split somewhere in the middle using a
special command.
Issue 2 is easily resolved: as we initially want
to store the data, we can simply scan the material
within a \vbox. This box, which is later thrown
away, will form a boundary for local changes, but
this is okay, as we can scan as many paragraphs asnecessary in one go.11 This would solve the problem
if only portions of a document (e.g., float captions)
are subject to trial typesetting. If the intention isto process the whole document in this manner thena slightly different approach is needed. In that case
we would use the main vertical list for collection anddevise a special output routine that is triggered at
the end of each paragraph. The \hboxes holding theparagraph fragments would then be retrieved within
the output routine. Once everything is collected as
Frank Mittelbach

far as necessary, the output routine could then bechanged to do trial typesetting.
To avoid issue 3 it is necessary to ensure thatmaterial from \insert and \vadjust is not migrated
out of the horizontal material. If they were, theywould appear after our “paragraph line”. On the one
hand, this is the wrong place if we later rebreak thematerial into several lines, and on the other hand
it would prevent us from disassembling the materialand storing it away. Therefore the solution is to end
the paragraph (generating one line for the current
fragment that we can save away), then start an \hbox
into which we scan the \insert or \vadjust andthen restart the scanning for the remainder of the“real” paragraph.
With these preparations, the algorithm thenworks as follows:• When we start (or restart) scanning paragraphmaterial we ensure that there is no indentation
box at the beginning.
• When we reach the end of the paragraph (or aparagraph fragment where we have artificiallyforced a paragraph end) TEX will typeset thematerial and because of the large line length
it will (normally) result in a single-line paragraph. We then pick up this line via \lastbox
and repackage it by removing the glue (from\parfillskip) and penalty at its end. Then we
save this box and an accessing function away insome data structure and restart scanning until
we reach the end.
• If we see an \insert or \vadjust we interrupt
and add the scanned material to the data structure. Then scan and store the vertical material
as outlined above.
• If we see a forced penalty we interrupt andsave the scanned material and then also record
the value of the penalty in the data structure.
Note that any non-forcing penalty could just be
scanned as normal paragraph material becauseof the large \hsize.
• Once we are finished parsing we end up with adata structure that looks conceptually as follows:\dobox box1 \dopenalty {10000}\dobox box2 \doinsert boxx
\dobox box3 \dovadjust boxy . . .
box1 to box3 are \hboxes holding paragraph text
fragments; boxx and boxy are also \hboxes containing just an \insert or \vadjust, respectively, i.e., they are generated basically by:\setbox boxx =\hbox{\insert{...}}
11. The limit is available memory, which is huge these days.

TUGboat, Volume 34 (2013), No. 1

61

With the right definitions for \dobox and friends(e.g., \unhcopy, etc.) this data structure can then be
used to “pour” the saved paragraph(s) into various
molds for trial typesetting.
This algorithm works with any TEX engine andits only restriction is the maximum allowed size of asingle paragraph. This is acceptable, as it normally
would not happen unless somebody is typesetting
a document in James Joyce style. If it does, it will
be detected and the user can be asked to artificiallysplit the paragraph at a suitable point.
4.2

A LuaTEX solution

Using the LuaTEX engine, it is possible to simplify
the algorithm considerably. LuaTEX offers the possibility of replacing the line breaking algorithm with
arbitrary Lua code and we can use this fact to temporarily replace it with a very trivial function: onethat simply packages the “unset horizontal list” intoan \hbox and returns that. This would look as follows:
function hpack_paragraph (head)
local h = node.hpack(head)return hend
callback.register("linebreak_filter",
hpack_paragraph)

The beauty of this is that it automatically resolves
issues 1 and 3 listed above. Issue 1 is fully resolved,
because node.hpack is able to build \hboxes of any
size, even wider than \maxdimen (as long as you do
not try to access the \wd of the resulting box). So
even Joycean paragraphs are no longer any problem.
Issue 3 is gone because we do not need to decompose
material. With the simple code above any penalties,\inserts, or \vadjusts simply end up within thebox; in contrast to the normal line breaking algorithm, the hpack_paragraph code does not touchthem. For the same reason, we do not have to takeoff any \parfillskip from the end, as it isn’t addedin the first place.
The only problem found so far is a bug in thecurrent implementation of the linebreak_filter
callback rendering \lastbox (which is needed by
our algorithm) unusable the moment the callback is
installed. This is due to some missing settings in
the semantic nest of TEX that are not fully carriedout. Eventually this will most certainly get corrected
in a future LuaTEX version. For now it is possible
to implement the correction ourselves in a second
callback:function fix_nest_tail (head)tex.nest[tex.nest.ptr].tail = node.tail(head)tex.nest[tex.nest.ptr].prevgraf = 1

tex.nest[tex.nest.ptr].prevdepth = head.depth
return true
end
callback.register("post_linebreak_filter",
fix_nest_tail)That is enough for our use case to work. For somebody interested in implementing a real replacement
for the line breaking algorithm, additional adjustments are necessary; see the discussion in [28].
5Conclusions

In 1990 the author attested that “the current” TEX
system is not powerful enough to meet all the challenges of high quality (hand) typesetting.
Two decades later the successors offer significant improvements in that they provide machinery
to resolve most of the issues identified.
However, having the tools does not mean
having the solutions and on the algorithmic level
most questions are still unsolved.
So if they haven’t been solved for so long, aresolutions truly needed?
In the author’s opinion, the answer is clearly yes.
The fact that for nearly all issues people struggled
again and again with inadequate ad hoc solutions
shows that there is interest in better and easier ways
to achieve the desired results. Or, to paraphrase
Frank Zappa, “High-quality typography is not dead,it just smells funny”.
The task now is to put the new
possibilities to use and work on solving the open
questions with their help.

U
R

RRR

∗ ∗ ∗
The author wants to thank Nelson Beebe, Karl
Berry, and Barbara Beeton for their invaluable help
in improving the paper through thorough copy-editing
and numerous suggestions.
References[1] Anonymous. εXTEX. Website.
http://www.extex.org.
[2] Anonymous. Extended TEX font encoding
scheme — Latin, Cork, September 12,
1990. TUGboat, 11(4):516–516, November
1990. http://tug.org/TUGboat/tb11-4/
tb30ferguson.pdf.
[3] Anonymous. Cambria (typeface). Wikipedia,
2012. http://en.wikipedia.org/wiki/
Cambria_(typeface).
[4] Anonymous. LuaTEX on the Web. Website,
2012. http://luatex.org.
[5] Anonymous. Microtypography. Wikipedia,
2012. http://en.wikipedia.org/wiki/
Microtypography.

E-TEX: Guidelines for Future TEX Extensions — revisited

62[6] Anonymous. XETEX on the Web. Website,
2012. http://tug.org/xetex.
[7] Anne Brüggeman-Klein, Rolf Klein, andStefan Wohlfeil. Pagination reconsidered.
Electronic Publishing, 8(2&3):139–152,
September 1995. http://cajun.cs.nott.ac.
uk/compsci/epo/papers/volume8/issue2/
2point9.pdf.
[8] David Carlisle. A seasonal puzzle: XII.
TUGboat, 19(4):348–348, December 1998. http://tug.org/TUGboat/tb19-4/tb61carl.pdf.
[9] Paolo Ciancarini, Angelo Di Iorio, Luca
Furini, and Fabio Vitali. High-quality
pagination for publishing. Software—Practiceand Experience, 42(6):733–751, June 2012.
[10] Michael Downes and Morten Høgholm.
The breqn package. CTAN, 2008. http://www.ctan.org/pkg/breqn.
[11] Hisato Hamano. Vertical typesetting with
TEX. TUGboat, 11(3):346–352, September
1990. http://tug.org/TUGboat/tb11-3/
tb29hamano.pdf.
[12] Charles Jacobs, Wilmot Li, Evan Schrier,David Bargeron, and David Salesin. Adaptive
grid-based document layout. In ACM
SIGGRAPH 2003 Papers, SIGGRAPH’03,
pages 838–847, New York, NY, USA, 2003.
ACM. http://grail.cs.washington.edu/
pub/papers/Jacobs2003.pdf.
[13] Donald Knuth. Virtual Fonts: More Fun forGrand Wizards. TUGboat, 11(1):13–23, April
1990. http://tug.org/TUGboat/tb11-1/
tb27knut.pdf.
[14] Donald Knuth. An earthshaking
announcement. TUGboat, 31(2):121–124,
2010. http://tug.org/TUGboat/tb31-2/
tb98knut.pdf. Also available as video
at http://river-valley.tv/tug-2010/
an-earthshaking-announcement.
[15] Donald Knuth and Pierre MacKay. Mixing
right-to-left texts with left-to-right texts.
TUGboat, 8(1):14–25, April 1987. http://tug.
org/TUGboat/tb08-1/tb17knutmix.pdf.
[16] Donald E. Knuth. TAU EPSILON CHI.
A system for technical text. Report
STAN-CS-78-675, Stanford University,
Department of Computer Science, Stanford,
CA, USA, 1978.
[17] Donald E. Knuth. TEX and METAFONT—New
Directions in Typesetting. Digital Press,
12 Crosby Drive, Bedford, MA 01730, USA,
1979.
Frank Mittelbach

TUGboat, Volume 34 (2013), No. 1[18] Donald E. Knuth. The TEXbook.
Addison-Wesley, Reading, MA, USA,1984.
[19] Donald E. Knuth. TEX: The Program,volume B of Computers and Typesetting.
Addison-Wesley, Reading, MA, USA, 1986.
[20] Donald E. Knuth. The new versionsof TEX and METAFONT. TUGboat,
10(3):325–328, November 1989. http://tug.org/TUGboat/tb10-3/tb25knut.pdf.
[21] Donald E. Knuth. Digital Typography. CSLI
Publications, Stanford, CA, USA, 1999.
[22] Krista Lagus. Automated pagination of
the generalized newspaper using simulated
annealing. Master’s thesis, Helsinki Universityof Technology, Helsinki, Finland, 1995.
http://users.ics.aalto.fi/krista/
personal/dippa/DITYO.ps.gz.
[23] Franklin Mark Liang. Word Hy-phen-a-tion
by Com-pu-ter. Ph.D. dissertation,
Computer Science Department, Stanford
University, Stanford, CA, USA, March 1984.
http://tug.org/docs/liang.
[24] Mico Loretan. The selnolig package: Selective
suppression of typographic ligatures. Website,
2012. http://meta.tex.stackexchange.com/
questions/2884.
[25] Kim Marriott, Peter Moulder, and Nathan
Hurst. Automatic float placement in
multi-column documents. In Proceedingsof the 2007 ACM symposium on Document
engineering, DocEng’07, pages 125–134,
New York, NY, USA, 2007. ACM. http://bowman.infotech.monash.edu.au/~pmoulder/examples/float-placement.pdf.
[26] Frank Mittelbach. E-TEX: Guidelines
for future TEX extensions. TUGboat,11(3):337–345, September 1990. http://tug.org/TUGboat/tb11-3/tb29mitt.pdf.
[27] Frank Mittelbach. Formatting documentswith floats: A new algorithm for LATEX 2ε .
TUGboat, 21(3):278–290, September
2000. http://tug.org/TUGboat/tb21-3/
tb68mittel.pdf.
[28] Frank Mittelbach. \lastnodetype not working
as expected in LuaTEX. Website, 2012.
http://tex.stackexchange.com/questions/
59176.
[29] Frank Mittelbach, Michel Goossens, Johannes
Braams, David Carlisle, Chris Rowley,
Christine Detig, and Joachim Schrod. The
LATEX Companion. Tools and Techniques

TUGboat, Volume 34 (2013), No. 1

63

for Computer Typesetting. Addison-Wesley,
Reading, MA, USA, second edition, 2004.
[30] Michael F. Plass. Optimal pagination
techniques for automatic typesetting systems.
Ph.D. dissertation, Computer Science
Department, Stanford University, Stanford,
CA, USA, 1981.
[31] Jan Michael Rynning. Proposal to the TUG
meeting at Stanford. TEXline, 10:10–13, May
1990. Reprint of the paper that triggered
TEX 3.0.
[32] Yasuki Saito. Report on JTEX: A Japanese
TEX. TUGboat, 8(2):103–116, July 1987. http://tug.org/TUGboat/tb08-2/tb18saito.pdf.
[33] Robert Schlicht. Microtype; an interface to themicro-typographic extensions of pdfTEX, 2010.
http://ctan.org/pkg/microtype.
[34] Manfred Siemoneit. Typographisches Gestalten.
Polygraph-Verlag, Frankfurt am Main,
Germany, second edition, 1989.
[35] Michael Spivak. amstex.doc, 1990. Comments
to [36].
[36] Michael Spivak. amstex.tex, 1990.
[37] Hán Thê´ Thánh. Microtypographic
extensions to the TeX typesetting system.
(Dissertation an der Fakultät Informatik,
Masaryk University, Brno, Oktober 2000).
TUGboat, 21(4):317–434, 2000. http://tug.org/TUGboat/tb21-4/tb69thanh.pdf.
[38] Hán Thê´ Thánh. Margin kerning andfont expansion with pdfTEX. TUGboat,22(3):146–148, September 2001. http://tug.org/TUGboat/tb22-3/tb72thanh.pdf.
´ Thánh. Micro-typographic extensions[39] Hán Thêof pdfTEX in practice. TUGboat, 25(1):35–38,
2004. http://tug.org/TUGboat/tb25-1/
thanh.pdf.
[40] Arno Trautmann. An overview of TEX, its
children and their friends. Website, 2012.
http://github.com/alt/tex-overview.
[41] Stefan Wohlfeil. On the Pagination of Complex,
Book-Like Documents. Shaker Verlag, Aachen
and Maastricht, The Netherlands, 1998.
[42] Hermann Zapf. About micro-typography
and the hz-program. Electronic Publishing,
6(3):283–288, September 1993. http://cajun.cs.nott.ac.uk/compsci/epo/
papers/volume6/issue3/zapf.pdf.

* * *Finally, to answer the question posed in footnote 2:
The paragraph typeset with negative expansion was
the second one in Section 3.4. Without it, it would
have looked like this:The mark mechanism provides information aboutcertain objects and their relative order on the current page, or more specifically, information about
the first and last of these objects on the current page
and about the last of these objects on any of thepreceding pages. However, being a global concept
only one class of objects can take advantage of thewhole mechanism.
 Frank Mittelbach
Mainz, Germany
frank.mittelbach (at)latex-project dot org
http://www.latex-project.org/
latex3.html

E-TEX: Guidelines for Future TEX Extensions — revisited