91

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?

8
  • 6
    There were a lot of research papers from when TeX was being actively developed at Stanford, such as the papers of Knuth, Plass, Liang, etc… would those be among the answers you're looking for? Mar 28, 2018 at 1:33
  • 1
    @ShreevatsaR Definitely! Mar 28, 2018 at 2:11
  • 3
    @ShreevatsaR You shouldn't have posted your answers as CW because all the credit for this tremendous literature research should go to you. Mar 28, 2018 at 21:03
  • 2
    @HenriMenke Thanks :-) I'm just happy if people read the papers and absorb the great ideas and gain a better appreciation for what goes into TeX/LaTeX, rather than thinking of (La)TeX as an arcane tool for making PDFs. :-) (Also, more than reputation points, I wanted this question to remain open, and somehow I felt making my answers community-wiki would help the cause more than posting four consecutive non-CW answers.) Mar 29, 2018 at 15:25
  • 1
    i've rephrased the title so that the question does not appear to be asking for an opinion. Mar 31, 2018 at 13:35

9 Answers 9

68

Line-breaking

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

[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).

0
43

Page-breaking

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

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.)

1
  • 1
    For more on page breaking, see the papers by Frank Mittelbach and others, mentioned in this answer. Mar 29, 2018 at 15:12
38

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.)

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.

6
  • 4
    It’s worth pointing out that this only works in English. German, for instance, simply has a fixed set of rules for hyphenation that can be applied (I think) entirely deterministically. Mar 28, 2018 at 10:59
  • 1
    I suspect you misunderstood the problem @KonradRudolph. It's not that English lacks rule that compound word must be hyphenated as news-paper not one letter to the left. The problem is how to explain that to computer without including a dictionary of the words.
    – Džuris
    Mar 28, 2018 at 14:24
  • 1
    @Džuris Maybe I misunderstood, but it’s more likely you did: languages like German have generalisable rules. You don’t need to include a dictionary, and you can produce an exact algorithm rather than a heuristic. And if you “invent” a new German word from scratch, I will be able to tell you how to hyphenate it. Mar 28, 2018 at 15:08
  • 3
    @KonradRudolph Once you have been able to split composite words, the German hyphenation rules are rather deterministic. The problem is to recognize and to split composite words (e.g., "enterben" is "ent+erben", so the hyphenation is "ent-er-ben", whereas the hyphenation of "entern" is "en-tern"). To recognize compounds, you can use exactly the pattern approach implemented in TeX.
    – Uwe
    Mar 28, 2018 at 15:11
  • 1
    @Uwe The difference being that syllabification (and hence hyphenation) in German strictly follows pronounced syllables (unlike in English). Your example is giving me pause though: obviously a correct algorithm wouldn’t be tempted to split “ent-ern” (because the last syllable must be “tern”); but it might be tempted to split “en-ter-ben”: all three are valid syllables. So I’ll concede that at least some cases need to be hardcoded to distinguish prefixes and stems (Wikipedia has more salient examples, e.g. “Fluch-torte” vs “Flucht-orte”). Mar 28, 2018 at 15:21
35

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).

1
  • 1
    Wonderful papers! Thanks for making them available. Mar 28, 2018 at 20:40
33

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).

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.

25

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 :)

2
17

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.

4
  • These papers are excellent. Thanks for finding them :) Mar 28, 2018 at 22:00
  • Any fixed link for "The letter S"? I can find one doi.org/10.1007/BF03023051 but it's paywalled
    – user202729
    Aug 5, 2022 at 0:34
  • Okay looks like it's apps.dtic.mil/sti/pdfs/ADA090470.pdf -- on that note the 3 visiblelanguagejournal links seems to be broken
    – user202729
    Aug 5, 2022 at 1:05
  • @user202729 The most up-to-date version of Knuth's papers are in his collected volumes, e.g. The Letter S has been reprinted with minor corrections as Chapter 13 of the book Digital Typography. Otherwise, if you have the DOI you can use Sci-Hub if you have no moral objections to it (replace "doi.org" with "sci-hub.se" or whatever). And for the Visible Language links above, replace visiblelanguagejournal.com in the link with visiblelanguage.herokuapp.com e.g. visiblelanguagejournal.com/issue/61 -> visiblelanguage.herokuapp.com/issue/61. Aug 5, 2022 at 1:19
15

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.

6

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.

2
  • (Forgot to comment earlier.) Was hoping you (especially) would answer this question. Thank you for this very useful and underappreciated (so far) answer! Apr 13, 2018 at 16:32
  • @ShreevatsaR I improved my answer and put the focus only on the topics of the question. Apr 22, 2018 at 11:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .