Are there any open research problems in the world of TeX?

Question

For a year-long capstone project in computer science, I have to do some 'original research.' I'm still not entirely sure what this entails, but it just struck me that perhaps I can do research and simultaneously help the only open source project I truly believe in.

Are there any open problems in TeX or LaTeX that I could attempt to solve over the course of a year?

If possible, one problem per answer. (Note you can still post multiple answers.)

---

To clarify, I'm not looking for ideas that would make cool packages per se. I'm not looking to add some neat package on CTAN; that isn't nearly fundamental enough. I'm not even looking for high-scale programming project either; those are things you can just truck through (with the possible exception of a BibLaTeX style editor; I understand that's a doosie). I'm looking for problems that

• have (or need) a clear definition of the problem
• are fundamentally applicable to the core of TeX's typesetting (To clarify, I'm not expecting to re-code TeX for this, but it's not out of the question. The 'rivers' problem may have to lead to this, whoever does it.)
• are within the scope of an undergraduate/graduate final year. (I go to a weird school; we have some pretty amazing research going on at the undergraduate level. See the project's official specification, keeping in mind that each department has its own spin.)

---

I ended up going with 're-evaluating and improving Knuth-Plass for modern hardware' as my proposal, and my adviser was enthusiastic about it (at least upon realizing I wasn't wanting to extend the language of TeX). So I began my research and, lo and behold, it's already been looked at! (This isn't surprising, but it's definitely depressing.) Perhaps this algorithm could be implemented in one of the newer TeX engines, but that is beyond the scope of CS research. (For example, it could be applied to avoid rivers and stacks, to improve pagination, etc.) Thanks for all of your suggestions!

Answer 1

I don't know whether these are open problems or not, but since you are looking for a capstone project, you might be interested to explore if the basic algorithmic aspects of TeX can be improved.

1. Line-breaking algorithm. The current line breaking algorithm is a gold standard that all line-breaking software emulate, but is it the best way to break lines? Knuth and Plass's algorithm made specific premature optimization choices (pun intended!) like separating page-break from line break, assigning badness based on the raggedness of line but not accounting for rivers, etc. The only real advance since then has been character protrusion, and from what I understand, it still follows the same basic line-breaking algorithm. Now don't get me wrong. I am not saying that these choices were wrong. But a lot of these choices were made because the computational resources of that time could not really handle anything more sophisticated. But now that we have computers that are 1000 times more powerful than those in the 70s, it should be possible to explore other options to see if the line breaking algorithm can be improved by taking into account more factors, especially page-breaking, footnotes, side-notes, and floats. What is better, perfect line breaks but huge vertical spaces to balance the page, or slightly underfull lines but no vertical spaces? There is no way to play around with these in the current framework (please correct me if I am wrong).

2. Automatic breaking of display equations. Currently the breqn package implements the ideas of Michael J Downes, but AFAIK, the algorithmic aspects are not as well understood as that of line-breaking of text. Is it possible to case line-breaking of display equations as an optimization problem and determine a solution based on penalties and badness?

3. Parsing natural math. There are recurring questions asking if it is possible to automatically translate <= to \le, sin(x/y) to \sin\left(\frac{x}{y}\right), etc. Although it is possible to do so to a varying degree of success with TeX and LuaTeX (e.g., the calcmath module in ConTeXt), I haven't seen any work that tries to understand how to parse math without markup. Given how sophisticated the current NLP techniques are, it should be possible to do better than simple heuristics for parsing natural math.

Answer 2

I think that the river-problem could be quite interesting to take up on. I am not 100% sure where this project is in its current state.

How to define the badness of a river?

But this would be an immense improvement to TeX capabilities (and a quite interesting mathematical challenge, I think). @Raphink has looked a great deal into it, you might consider talking to him if this has any interest.

Answer 3

Typesetting in a fixed baseline grid.

I know there are few packages that can help on this but it’s still a lot of manual editiong to get the lines on a grid. A fully automated solution, supporting headlines, multi columns, floats, footnotes, margin notes etc., would be great.

What does that mean? And why is it important?

Typesetting in a fixed baseline grid means that every single line (or at least the ones of the main text, i.e. sometimes headlines are excluded from that) must stick to a fixed and equidistant grid, that is the same for every page. If the text is interrupted by a figure, a table, an equation, (a headline) or something like that the spacing around this element must be in a way that the following line of the main text lays on the grid again. The main reason for using a fixed grid is that it improves the readability: nearly always the lines form the back of a page shine through and are visible on the front, the more or less depending on the grammage of the paper. If the lines aren’t fixed on a grid, the back lines disturb the visibility and traceability of the front lines.

For both images I used the same settings (color and blur) for the back verses, but you can see that your eye can follow the lower example (with grid) much better then the upper one. Although this example is a little artificial to demonstrate what I mean, it’s not that much exaggerated …

Beside that it has aesthetic reasons, especially in multicolumn layouts. I simply looks better when the lines of multiple columns stick to the same baseline grid.

An for that using a fixed grid is considered as good typography.

Image source: http://de.wikipedia.org/wiki/Grundlinienraster

Answer 4

In the early 90's I gave a paper on open issues with TeX and directions for research called "E-TeX: Guidelines to future TeX extensions" and just last year I revisited it and presented a paper in Boston on the current status of the original problems identified: E-TeX: Guidelines for Future TeX Extensions --- revisited. In there you should find some ideas I hope.

Maybe a word of caution, when looking through some of the suggestions in the answers: some are fairly trivial and some could gain you a PhD and it will not be always easy from the outside to say which belong in which category. So when you start zeroing in on anything get advice on what you are in for ;-)

Answer 5

A LaTeX (macro) debugger

Amongst some unmentionables, it could allow one to step through one's code sequentially in order to identify macro arguments and contents, thus avoiding the use of \typeout and \def-to-\show for verification, or making sense of the sometimes elaborate tracing function output.

Answer 6

If you typeset a document page by page, almost anything is possible. Most of the difficult problems in LaTeX have to do with the automating production of documents.

A problem in seek of an algorithm is the placements of marginpars (especially with a view to include figure captions in margins).

This image from Unusual graphics and caption placement, has no solution so far (I have accepted the answer out of courtesy).

Problem Definition: If an image extends into margins allow captions to float to the previous page or to the forward page.

In general marginpar placements are problematic and LaTeX's algorithm is in need of improvements. This problem in a way extends the pagination algorithm of Knuth-Plass and should be interesting both from a purely Computer Science perspective as well as coding. (Caveat: It might take longer than a year).

Answer 7

Make accessible PDF documents that conform to standards

Figure out how to make PDF documents that:

2. Can be read out loud by a PDF reader, and
3. Can be reflowed automatically for different screen and font sizes, and
4. Pass automated tests for accessibility

using just core TeX, and without requiring the author to do anything other than compile the document.

See some of the questions tagged accessibility for examples of the issues.

Answer 8

Using LaTeX to render e-books

I prefer reading documents on the tablet for some time now, basically because I don't have to carry around paper (and because I don't usually annotate even printed documents). However, most PDFs around are prepared for printing, and have to be zoomed to be read on the tablet.

It doesn't seem to be too simple even to manually generate e-book friendly versions of existing LaTeX documents, see Effort to make (La)TeX eBook-friendly and Creating Kindle-friendly versions of existing LaTeX documents. It might be challenging to create a fully automated solution that provides the beauty of LaTeX typesetting to a mobile device with its particular screen dimensions and the font size chosen by the user.

Some ideas:

• An input filter to pandoc that accepts ePub and other popular formats, perhaps FictionBook.

• A robust preamble (that includes microtype), adjustable to screen dimensions and with the ability to choose font size. Or, automatic choice of font size so that a line has a user-defined number of characters on average, say, 62.

• Robust compilation of any (syntactically correct) input without overfull boxes -- it's good enough if the output looks perfect only 99% of the time. Possible solutions: Scaling of overly wide contents or allowing for very sloppy breaking where necessary.

• Images pre-rendered at the resolution of the target device.

• Splitting the document into pages is fine -- books do have pages, too.

• Output is a PDF that just fits the screen of the target device, perhaps with navigation buttons as in the beamer or pdfscreen packages.

For the sake of completeness, references to questions that ask for conversion "the other way round":

LaTeX document to epub or mobi ebook formats (with mathematical formulas)

Conversion XeTeX -> EPUB

Answer 9

Make LaTeX a modern programming language

I'm not an expert on LaTeX like some of the people here, but I have many times run into LaTeX's limitations compared with modern programming languages (that I am very familiar with). I believe that in the long term, LaTeX should not be a macro language for exactly the reason that it is very hard to apply the straightforward programming concepts that other languages take for granted: abstraction, inheritance, polymorphism, dynamic programming, etc.

Memoization of section compilation

Why is the whole document recompiled every time? Why can't some of the work for each paragraph (or section or figure) be kept if the context (font, spacing, block width, etc.) in which the paragraph is recompiled does not change? LaTeX should memoize the result of compilation for each section based on the context in which it is compiled. This would eliminate the need for breaking your document into various tex files and recompiling them yourself (doing the job of the compiler), and it would supplant tikzexternalize.

Context-based symbols

Allow LaTeX “macros” to be programs that interact with the context in which they're invoked. I think there are problems with footnotes in captions, or footnotes in table notes. I don't remember, but I know I've run into them. My guess is that these problems would be mitigated by having both the context in which something is invoked (table, bibliography, figure caption) and the embedded element (footnote, another figure, etc.) be able to answer questions to each other to come to some conclusion about how to be rendered. I don't understand \protect and \DeclareRobustCommand, but hopefully this would eliminate them.

Full programming abstractions

Many of my diagrams are coded in Python that generates Tikz code. Tikz looks great, but its programming features are severely limited compared to the freedom you have in Python. Even if you can do something, it is hard to read and hard to debug. Wouldn't it be great Tikz were a Python module?

Type safety

So many errors can be avoided by ensuring that when a color is requested, it is in the right format xcolor, #122314, and so on… Regular programming languages can verify the types of their arguments.

Debugging

It would be much easier to write a debugger as Werner suggests if LaTeX were a regular programming language.

Suggested approach

My suggestion would be to make a Python module that implements the various internal latex compilation routines.

Programmatic access

This module would provide programmatic access to a “latex context object” and a “compiled latex element”. Inspecting these would let you see all of the relevant settings in relevant subobjects. This would be much more useful than any LaTeX debugger.

Early versions are still useful

You don't have to worry if you can't complete a whole latex replacement. Even the early versions of such a module would still be very useful. Just a module that provides pythonic access to Tikz would be extremely useful to me.

Debugger

Python already has a great debugger.

Speed?

Python already has the ability to transparently incorporate fast C++ versions of methods, and with development of pypy, regular python may one day be comparable in speed to hand-coded C++. Anyway, the benefit of cached compilation far outweighs faster compilation in my opinion.

LaTeX macros should be regular Python objects

Besides Python's excellent object model, it has amazing metaprogramming facilities. If you ever find yourself writing the same code twice, in Python, you don't have to. It can be very useful to write code that writes code.

I doubt that latex module development is not hampered by the fact that everything is a macro. Take a look, for example, at tikz.code.tex. Try to make sense of anything. This code looks like it was written 30 years ago. Software engineering has come a long way since then: encapsulation, abstraction,… separation of concerns. You don't realize the value of these things until your code is a couple thousand lines and you can't keep it all in your head. Imagine how much faster latex modules would be developed if it were a modern programming language.

Separation of syntax from compilation

All of this can be done without deciding what LaTeX code should look like. Someone can use the Python module to interpret existing LaTeX code, or design a new variant of LaTeX code. Other people can use the Python module directly within Python to generate figures or programmatically generate documents.

Answer 10

Text streams / parallel typesetting with arbitrary split layouts, full featured multi-footnote and margindata support. Not even Context can do it. While there are a couple solutions to this, they appear hackish and unflexible to me, and aren’t exactly Luatex aware (please correct me if I’m wrong).

Answer 11

Breaking the paragraph hold

TeX sets paragraphs as a whole by collecting horizontal lines one after the other and stacking them. These horizontal lists that are stacked usually have the same width. If you wish to break the monotony, \parshape comes to the rescue. However, it's very cumbersome to use if you want text to flow naturally from one block to another. Here a block could refer to the break from one column to another, or from one page to another.

An example of this is properly given in How to change \hsize in the middle of a paragraph at page break, especially for two-column? While the example is given in a two-column document, it pertains to single-column documents with a page break, or multi-column varied-width documents with a page break. Single-page solutions exist; see Different column widths using multicol and the implementation of vwcol.

Ultimately one can use \parshape to adjust the shape of a paragraph to flow better from one width to another within a paragraph, but this has not been automated AFAIK.

Possible solution 1: A multi-pass approach where the remaining portions of a paragraph is unboxed and reset at a different width, removing any implications of counter stepping or labelling.

Possible solution 2: Construct a paragraph shape iteratively by capturing the available width of each horizontal list being stacked vertically. Reset the paragraph every time there is a change required, until no further changes are required (of course, also taking into consideration that no counters are multi-stepped or labels multiply defined.

Answer 12

Parallel Compilation

It's just sad to sit and watch a Quadcore machine spend minutes on a single document, only ever using one core. This is likely to become worse: the trend seems to be towards having more weaker cores (e.g. for better control over energy usage). So, if TeX and friends want to be competetive, arguably, they have to be able to make use of multi-/many-core architectures to some extent.

Since TeX seems to be inherently tied to a sequential execution model (I really don't know too much about it), this may be very challenging or even impossible without changing some aspects of TeX.

Maybe it is possible to quickly assign parts of the stream to pages and filter out parts with global effect, and then lay out pages in parallel? I don't know, but I'd love to see work on this.

Answer 13

Implement TeX in TeX. Thanks in advance. :-)

Answer 14

I would like to see more power given to the hyphenation system. Currently, there's just so much you can do with babel, like specifying hyphenation for particular words with \hyphenate{ba-bel} or {ba\-bel}, and the \discretionary{}{}{} command.

However, \discretionary{}{}{} is quite verbose. And languages such as Portuguese will soon require heavy usage of it. We are just waiting a new set of ortographic rules to be fully implemented in all Portuguese-sepaking countries.

To give an example of how this will be a future problem, translineation of compound words will demand the hyphen to be duplicated when it is involved in the translineation. I'll show this in the following snippet of text:

Aqui temos uma palavra como contra-
-ataque que exige duplicação do hí-
fen.

Notice how hyphenation happens twice here, but the hyphen in contra-ataque is duplicated in the second line of text.

You can obtain that with at least two solutions:

Aqui temos uma palavra como con\-tra\discretionary{-}{-}{-}a\-ta\-que
que exige duplicação do hífen.

Aqui temos uma palavra como con\-tra\-\mbox{-a}\-ta\-que que exige
duplicação do hífen.

Both are very verbose and break TeX hyphenation (you need to manually hyphenate each of the words in the compound).

Of course, you can defined a shorthand with \defineshorthand so you can write things like "- instead of the two samples above for compound words. However, this is counter-intuitive and is somewhat troublesome to automatic ortography correction. Not to mention most editors will automatically replace " with `` as you type, and you can't defined a shorthand with other characters such as '- or simply -.

I have seen many attempts to allow text to be normally written with proper translineation in Portuguese, but all seem to fail. I think you'll need to go deep into TeX's core to allow more robust hyphenation rules to be written.

This seems to me like a nice project as it involves not only programming, but also some linguistics research, as it affects many languages besides Portuguese.

Answer 15

The idea of a wysiwyg editor for biblatex Is there a WYSIWYG editor for biblatex styles? seems like it might make a challenging project. Even a non wysiwyg solution like makebst would be helpful.

Answer 16

Writing a LaTeX compiler based on the LLVM Compiler Infrastructure.

Probable benefits would be:

• Much faster compilation
• Lower memory usage
• Expressive diagnostics
• Cleaner separation between Front- and Backend

Answer 17

Align floats side by side automatically

Sure, I know that I can use {minipage}s to align floats beside each other. But as far as I can see there is no way that LaTeX places two nodes in a row if they are narrow enough.

For example the following code should give two images next to each other automatically.

\documentclass{article}

\usepackage{graphicx}
\usepackage{lipsum}

\begin{document}
\section*{Current result}
\lipsum[1]
\begin{figure}
    \centering
    \includegraphics[width=5cm]{example-image-a}
    \caption{First caption.}
\end{figure}
\lipsum[2]
\begin{figure}
    \centering
    \includegraphics[width=4.5cm]{example-image-b}
    \caption{This is the caption of the second image.}
\end{figure}
\lipsum[3]
\end{document}

will arrange the first image above the second one.

but the result should look like this

This can be reproduced manually with {minipages}s.

\lipsum[1]
\begin{figure}
    \begin{minipage}[t]{0.45\textwidth}
        \centering
        \includegraphics[width=5cm]{example-image-a}
        \caption{First caption.}
    \end{minipage}\hfill
    \begin{minipage}[t]{0.45\textwidth}
        \centering
        \includegraphics[width=4.5cm]{example-image-b}
        \caption{This is the caption of the second image.}
    \end{minipage}
\end{figure}
\lipsum[2]

Answer 18

Removing the token expansion mechanism from TeX.

Edit:

In other words, creating an interface or high-level abstraction to let us write TeX code without thinking about the token expansion.

Answer 19

Rewrite TeX in a modern programming language. Java or C# would be the obvious choices. Tim Murphy tried with JavaTex, and his code is available. As far as I can see, the only problem was performance, but computers are faster now than in 1999, and Java is much faster.

The interesting/important parts are:

1. You'd surely learn a lot by reading/understanding code written by one of the world's leading computer scientists

2. You might learn something about software quality -- TeX has a remarkably low density of bugs. Why is that? Partly, it's a result of Knuth's talent and care, I suppose, but maybe there are structural reasons, too.

3. It's a large system, and the re-architecting and modularization issues would be interesting

4. You create a foundation for the future.

5. The rewritten code would be easier to understand (I hope) and more accessible to others who might want to make future improvements.

6. It should be possible to expose pieces of it in a public API, rather than it being a monolithic black box. I guess LuaTex has done this, too, but only for people who like programming in Lua. Something more mainstream would be valuable.

7. You'd (perhaps) need to find/build a modern substitute for web. If so, this would be interesting.

8. The comparison between 1980's technology and 201x technology would be interesting. How do more modern languages and tools and computers change things? Is the job easier now? If so, why?

You don't have to do the whole job (it would be too large a task, I expect). Automatic translation would give you a working mess, and then you could then incrementally clean it up, starting with the low-hanging fruit.

Answer 20

A package for two-column-pages, which allows to print marginnotes for the left column in the left margin and for the right column in the right margin.

Even more important would be a feature to get corresponding »two column footnotes«: Footnotes, which have the footnote mark in the left (right) column are printed below the left (right) column. If a pagebreak occurs, the footnote will be contiued under the left (right) column of the next pages. This refers to text e.g. in the multicols environment.

Binding footnotes to a column would as well be very helpfull for all documents having two parallel columns, let's say in English on the left and in Chinese on the right side. Packages: parcolumns, parallel.

And something different: often footnotes are printed in a smaller size, because on each page of a sientific work there is a immense number of references. I'm thinking of jurisprudential books called »commentary« in Germany. However, it is difficult to read a long line in 8pt letters and I sometimes wish I could print my text in one column, but the footnote text in two column mode.

Answer 21

P vs. NP

• Typesetting is for some badness functions in NPC (see iii in Optimal Pagination Techniques for Automatic Typesetting Systems)
• P vs. NP is a Millennium Prize Problem

Answer 22

A multipage tabular environment, which can calculate and display a subtotal in each last row of the page and in the first row of the next page (carry forward).

I suggest to realise it using LuaLaTeX, because calculating in TeX is a pain.

Answer 23

Graph Drawing in TikZ by Till Tantau