What research papers exist about TeX and friends?

Question

Some time ago there was a question on this site Are there any open research problems in the world of TeX?

In a similar spirit, I'd like to ask, whether there are any research articles out there in the peer-reviewed scientific literature which deal with TeX/LaTeX. This could be on different levels

• TeX as a typesetting engine, i.e. low-level development. There is for example the work by Hàn Thế Thành, who implemented pdfTeX and the microtypographical extensions: PhD Thesis (PDF).

• TeX as a macro language. Programming TeX macros is quite different from other programming languages. I am not (yet) aware of any research in this direction.

Searching Google Scholar for “LaTeX typesetting” yields mostly introductory books about LaTeX. What are the correct keywords to look for or which journals do I have to scan?

Answer 1

Line-breaking

The classic paper about TeX, what (IIRC) DEK once called the main research output produced by the TeX project, is the paper:

• “Breaking Paragraphs into Lines” (1981), by Donald E. Knuth and Michael F. Plass, Software: Practice and Experience, Vol. 11, 1119–1184.

[Reprinted in Digital Typography (1999), with some updates to notation etc. If you get an old printing of the book make sure to read the errata; there were unfortunately some significant typos.]

IMO even if you never use TeX or LaTeX, you ought to read this paper. It's a tour de force. In 66 pages, it introduces the line-breaking problem, formulates it mathematically, defines desirability criteria (badness, etc.), compares approaches, shows the power of this model (lots of sophisticated examples), then goes into the TeX algorithm with all its “bells and whistles”, before concluding with an inspiring history.

At heart, this paper is basically about TeX's elegant and powerful boxes-and-glue (or box-glue-penalty) model. By specifying an appropriate sequence of boxes, glue and penalties (to the same algorithm), we can elegantly solve many typesetting problems: not just for typical text (fully justified paragraphs) but things like centered text, hanging indentation, ragged-right text, typesetting program source code, book indices, quotations and author lines and blocks that should look different at different widths, paragraphs in various “shapes”, etc. After showing off these solutions, there is some theory developed (a kind of "algebra") that helps you come up with similar constructions yourself.

Many of these problems are also given in The TeXbook as double dangerous-bend exercises and in Appendix D: Dirty Tricks, but in the paper it's more expository. And most of these problems arose from real life, out of practical needs:

We wish to thank Barbara Beeton of the American Mathematical Society for numerous discussions about ‘real world’ applications;

An abridged version of this paper also exists:

• “Choosing better line breaks” (1982) by Michael F. Plass and Donald E. Knuth, in Document Preparation Systems, Nievergelt et al., eds. (Amsterdam: North-Holland, 1982), 221–242.

This paper, harder to find, has a lot of overlap with the previous one, except for some new terminology introduced (it uses boxes, glue and “kerfs” instead).

Answer 2

Page-breaking

Michael Plass's PhD thesis. (Plass and Liang wrote the first (proto-)TeX; see other answer.)

• “Optimal Pagination Techniques for Automatic Typesetting Systems” (1981), by Michael Frederick Plass, Department of Computer Science, Stanford University

The problem considered is page-breaking: given a list of figures and lines of text, what is the best way to place these figures and text, to minimize “badness”? The solution is a dynamic-programming algorithm similar to that used in TeX for line-breaking, but the solution is not used in TeX (which does page-breaking the “dumb” way)—mostly because of the memory constraints of the time. The thesis also shows that for certain badness functions, the problem is NP-complete, and unfortunately many people remember only this part, and there are citations to the effect that “Plass showed that page-breaking cannot be solved because it's NP-complete”. (But it's not, it depends on the badness function.)

Answer 3

Hyphenation

Frank Liang's PhD thesis. (Liang and Plass were the first people to work on TeX; together they had implemented a “proto-TeX” over the summer from Knuth's specifications, before Knuth wrote a single line of code.)

• “Word Hy-phen-a-tion by Com-put-er” (1983), by Franklin Mark Liang, Department of Computer Science, Stanford University

This solves the following problem: in natural language, there is a (somewhat) agreed-upon set of conventions for how certain words should be hyphenated: for example, new-spaper, ho-meowners, Re-agan are all bad hyphenations. So suppose we are given a dictionary of hyphenations: a huge set of words, along with how each is supposed to be hyphenated. How can we boil down this data to something small (within the constraints of machines at the time), and use this in our program, to get reasonably accurate hyphenation?

The solution that Liang came up with (and which is used in TeX) is to use hyphenating and inhibiting patterns. (Along with some careful usage of the trie data structure, etc.) For example, (using a program called patgen) suppose we have generated and stored the following patterns 4m1p, pu2t, 5pute, put3er. (Even numbers inhibit, larger numbers are “stronger”.) Then when the word computer is encountered, our program (TeX) uses these patterns and combines them, to get co4m5pu2t3er, which yields the hyphenation com-put-er.

Answer 4

LaTeX, Unicode, Optimal pagination, and others

There are a number of research papers collected over the years from members of the LaTeX Project Team at

https://www.latex-project.org/publications

Among those the peer-reviewed articles are

• Mittelbach F. A general LuaTeX framework for globally optimized pagination. Computational Intelligence. 2018;1–43. https://doi.org/10.1111/coin.12165

• Frank Mittelbach. 2017. Effective Floating Strategies. In Proceedings of the 2017 ACM Symposium on Document Engineering (DocEng '17). ACM, New York, NY, USA, 29-38. DOI: https://doi.org/10.1145/3103010.3103015

• Frank Mittelbach. 2016. A General Framework for Globally Optimized Pagination. In Proceedings of the 2016 ACM Symposium on Document Engineering (DocEng '16). ACM, New York, NY, USA, 11-20. DOI: http://dx.doi.org/10.1145/2960811.2960820

This is more recent work on globally optimized pagaination with and without involvement of floats. On the website there are further articles from that space.

• Frank Mittelbach and Chris Rowley. “Language Information in Structured Documents: Markup and rendering—Concepts and problems”. In “International Symposium on Multilingual Information Processing”, pp. 93–104. Tsukuba, Japan, 1997. Invited paper. Republished in TUGboat 18(3):199–205, 1997.

This paper discusses the structure and processing of multilingual documents, both at a general level and in relation to a proposed extension to standard LaTeX.

• Frank Mittelbach and Chris Rowley. 1997. Application-independent representation of text for document processing——will Unicode suffice? Tenth International Unicode Conference, Mainz, Germany.

• Frank Mittelbach and Chris Rowley. “The pursuit of quality: How can automated typesetting achieve the highest standards of craft typography?” In C. Vanoirbeek and G. Coray, editors, “EP92—Proceedings of Electronic Publishing, ’92, International Conference on Electronic Publishing, Document Manipulation, and Typography, Swiss Federal Institute of Technology, Lausanne, Switzerland, April 7–10, 1992”, pp. 261–273. Cambridge University Press, New York, 1992. ISBN 0-521-43277-4.

---

Just noticed that the last one is actually not available from the link above, should probably fix that.

In addition there are many more papers available from that link that have been published in TUGboat or through other means. They too contain research results and or development reports on different aspects of typesetting (with TeX).

Answer 5

TeX was introduced to the world through Knuth's Gibbs lecture. Knuth was invited to give the Gibbs Lecture to the American Mathematical Society in January 1978 (he had won the Turing Award in 1974, etc.), and he chose to talk about what he was working on at the time, which was TeX and METAFONT (started in mid-1977).

• “Mathematical Typography”, by Donald E. Knuth, Bulletin of the American Mathematical Society (N.S.), Volume 1, Number 2 (1979), 337–372.

First he described the history of mathematical typesetting (how typography can help mathematics), then described his TEX (sic) system and the mathematical problem of line-breaking, then METAFONT (how mathematics can help typography) with its “most pleasing curves”, etc. Many people became enthusiastic about this new system after the lecture, AMS became involved, etc., which was pretty significant in the history of TeX. (This paper was bound along with the TeX78 manual (precursor of The TeXbook) and the METAFONT manual, and published by the AMS as TeX and METAFONT: New Directions in Typesetting.) And when the lecture was published in 1979 in the Bulletin of the AMS, it was with the use of TeX.

Answer 6

The errors of TeX

I haven't read many papers about TeX, but I find this one particularly good. As ShreevatsaR mentioned, this paper is part Donald Knuth's Literate Programming, which includes other papers by him, some excerpts of the TeX and METAFONT sources, and other contents (I'm not paid for merchandising :)).

In this paper Knuth talks about some of the history of the development of TeX. He first classifies these errors by letters in the same fashion of the TeXbook's appendices (A -- an algorithm awry; B -- a blunder or botch). Then Knuth tells a little about the timeline of the development of TeX, since its first version.

Knuth then shows the timeline of found/solved errors and contextualizes these errors with the state of development and utilization of TeX. He finally tells a little about each type of error according to his classification and then shows the complete error log that he kept while writing and debugging TeX.

This paper isn't only for people interested in TeX but, for the legendary programmer that Knuth is, this paper serves as a lesson for anyone writing computer programs.

And finally, the history of TeX is very interesting and Knuth's excellent storytelling make it a pleasant read :)

Answer 7

Metafont

Some great papers on TeX's mate, METAFONT. Many were written for an audience of typographers and font designers rather than mathematicians or computer scientists.

• “The Concept of a Meta-Font” (1982), by Donald E. Knuth, Visible Language, Volume 16 Issue 1 (January 1982), 3–27. Reprinted as Chapter 15 of Digital Typography.
  This is not just a paper, it is a virtuoso performance! Read it to see why.

• “Metafont, Metamathematics, and Metaphysics” (1982) by Douglas Hofstadter, Visible Language, Volume 16 Issue 4 (October 1982), 309–338.
  Attacks a strawman despite being aware of it, and might have hurt METAFONT's chances of adoption—see for example this article by a typographer that perpetuates the misunderstanding—but entertaining nevertheless, if you forget that it's claimed to be about METAFONT (which IMO it is not), and just take the point it makes.

• “The Letter S” (1980), by Donald E. Knuth, The Mathematical Intelligencer, Volume 2, 114–122. Reprinted with corrections as Chapter 13 of Digital Typography.
  With METAFONT, Knuth wanted to describe the shape of each letter to the computer: instead of simply writing down a set of pixels for each letter, he wanted to capture in a program an “understanding” of how to draw it. The letter S gave him several sleepless nights, and in this paper he describes previous attempts to describe S mathematically, and his solution in METAFONT. (He touches on it in this video.)

Some articles on the experience of designing with METAFONT:

• “Lessons Learned from Metafont” (1985), by Donald E. Knuth, Visible Language, Volume 19 Issue 1 (December 1985), 35–53. Reprinted as Chapter 16 of Digital Typography.
  A subdued article compared to his earlier one. Describes not the general idea of a meta-font, but the specifics of METAFONT itself: its history, its philosophy, etc.

• “Designing a new typeface with METAFONT” (1986), by Richard Southall, in Désarménien J. (eds) TeX for Scientific Documentation, LNCS, Springer.
  Southall explains why METAFONT is so hard and unnatural for type designers.

• “Opening Pandora's Box” (1989), by Neenie Billawala, TUGboat, Volume 10 No. 4 (1989 Conference Proceedings)
  Billawala describes her experiences during the making of Pandora.

• “Metafont in the Rockies: The Colorado Typemaking Project” (1998), by Richard Southall, Springer LNCS 1375, 167–180.
  Did you know that METAFONT was used to typeset US West phonebooks (telephone directories)? It's true (see also this answer on Quora where it pops up in a history of phone-book typesetting), and this article (republished a couple of times in other places) describes it.

• “A Punk Meta-Font” (1988) by Donald E. Knuth, TUGboat, Volume 9, No. 2. Reprinted as Chapter 20 of Digital Typography.
  A dazzling bit of heroics: while attending a series of lectures, Knuth had an idea for a new font, went to the computer at 1pm, typeset “The quick brown fox…” by 4pm, and was able to give a printed sheet to other people by 7pm, while squeezing in going home for supper and dealing with a bug in the printer driver.

See also the lecture 32 Years of Metafont from 2016, which touches on some of these.

Answer 8

Heckmann and Wilhelm of Saarland University described TeX's formula layout in term of functional programming.

• “A Functional Description of TeX's Formula Layout”, by Reinhold Heckmann and Reinhard Wilhelm, Journal of Functional Programming, Volume 7 Issue 5, September 1997, Pages 451-485

  Abstract

  While the quality of the results of TeX's mathematical formula layout algorithm is convincing, its original description is hard to understand since it is presented as an imperative program with complex control flow and destructive manipulations of the data structures representing formulae. In this paper, we present a re-implementation of TeX's formula layout algorithm in the functional language SML, thereby providing a more readable description of the algorithm, extracted from the monolithical TeX system.

Answer 9

An important paper for METAFONT:

The work of John D. Hobby seems to be missing in the given answers. His work influences the implementation of METAFONT in several ways; here is his Ph.D. thesis which is mentioned in mf.web.

Page breaking:

Pagination reconsidered by Anne Brüggemann-Klein, Rolf Klein, and Stefan Wohlfeil published in Electronic Publishing, vol. 8(2&3), 139--152 (June & September 1995).

Or a paper of 1998 by the same authors: On the pagination of complex documents.

Line breaking:

Global multiple objective line breaking by Alex Holkner. The running time is problematic. We shall never forget that TeX implements practical solutions. That's why page breaking has a simpler algorithm than line breaking.