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

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!

• @dustin: Meta is only for questions about this website, not for questions about more abstract aspects of TeX. – Jake Aug 16 '13 at 6:57
• C'mon people, the 24 upvotes and 5 stars at the time of this writing should be enough to tell you not to vote for close! – morbusg Aug 16 '13 at 10:10
• Might be interesting in this context: Guidelines for Future TeX Extensions – Marco Aug 16 '13 at 10:22
• Should this be Community Wiki? – Joseph Wright Aug 16 '13 at 22:03

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.

• +1. I think Automatic breaking of display equations is the one. breqn package still have some issues with it, so I do not use it because of that. see tex.stackexchange.com/questions/119334/…, and this is one of the most important problems that needs to be completed. This problem becomes more important to solve when one uses 2 columns class for example, and equations starts to overflow and have to be manually broken. So may be a good project for OP would be to study this package more and make recommendations. – Nasser Aug 17 '13 at 2:41
• After giving this the attention it deserves, I agree with @Nasser that 'equation breaking' is a nice, researchable issue. I also think that improving upon Knuth-Plass with the realization of modern hardware could be an interesting exercise as well---it'd be skirting the line, but I'll ask my supervisor. Thanks! – Sean Allred Aug 17 '13 at 5:09
• See the edit to my question. – Sean Allred Sep 21 '13 at 14:17

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.

• I believe this is the best answer so far (when the question is 4 hours old) that meets the 'original research' condition and is doable in a year-long project. A LaTeX debugger (the current top answer) would be great, but it is more of a programming challenge than research. "Writing a LaTeX compiler based on the LLVM Compiler Infrastructure" would be amazing, but would be quite a challenge to complete in a year if you weren't already up to speed on compiler writing (and I'm not even sure it is possible for TeX in this context). – Chris Gregg Aug 16 '13 at 9:11

## 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

• Can you explain the problem a bit more? I don't understand it from just the image... – Canageek Aug 17 '13 at 3:35
• Isn't this solved in ConTeXt? – Martin Schröder Aug 17 '13 at 20:55
• @Tobi I had to look into it more, but ConTeXt does solve this problem (I don't know how or how suitably). Thanks for the explanation!! I feel like I've learned something :) Given that ConTeXt is just a format, I wonder how it solves this problem. – Sean Allred Aug 19 '13 at 0:22
• @SeanAllred: Grid typesetting requires that you do not use any vertical glue anywhere, and adapt anything this is bigger than lineheight (section headings, floats, etc) so that their height is a multiple of lineheight. Grep for \ifgridsnapping in the ConTeXt files. – Aditya Aug 19 '13 at 6:12
• @SeanAllred: IIUC, the glue model in TeX does not work in multiples of \lineheight. You specify a maximum and minimum strechability and TeX figures out a good value. This get more complicated if the lineheight changes (consider, for example, lines with large math expression). So the only way to get grid typesetting in current TeX is to kill glue completely and manually (well, using macros) take care of the rest. See Chapters 1, 4, and 8 of the It's in the details manual. – Aditya Aug 21 '13 at 14:30

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

• +1 for not leaving iTeX (bing) out of the figure. :) I'll add this to the very top my growing reading list on my desk. – Sean Allred Aug 16 '13 at 19:41
• @Frank Mittelbach: Your warning seems appropriate. So easy to choose the wrong project. You have how many years experience with TeX? 20? More? So would you mind to appraise the suggestions here, one by one, by giving a short comment to each (ok, nearly each) of them! Especially if mine were easy or impossible to realise, I'd be very glad to know that. Probably the lot here as well is curious. – Keks Dose Aug 17 '13 at 11:05
• @KeksDose frank’s had more than 20 years’ experience, i think. i started in the late 80s, and by the time i got to look at other people’s stuff, frank was already in the list. – wasteofspace Jan 9 '14 at 13:32

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

• This answer might be useful for anyone interested in (working on) this problem. – jon Aug 16 '13 at 5:51
• Isn't pdfTeX in C? I feel like this wouldn't be too bad to do. (Not immediately recognizeable as original research, but definitely worth looking into for anyone looking for a project.) – Sean Allred Aug 17 '13 at 1:19

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

## Make accessible PDF documents that conform to standards

Figure out how to make PDF documents that:

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

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

• Point 2 is probably outside the scope of PDF. That would be something for an Ebook, but a reader/format with TeX's expressiveness has yet to be released, so it will never be perfect and may never be decent. Point 1... point 1 is possible, but it isn't research. :( – Sean Allred Aug 17 '13 at 5:04
• Somebody really needs to get on these though; perhaps this is a project for next summer. (Or perhaps Google Summer of Code?) – Sean Allred Aug 17 '13 at 5:04
• Please do this with ConTeXt; it's much easier than with LaTeX. – Martin Schröder Aug 17 '13 at 21:01
• @LostBrit: What do you mean by ConTeXt is not Core TeX. ConTeXt is a macro package written on top of TeX, and it is as much of core TeX as LaTeX. Did you mean that ConTeXt is not as popular as LaTeX? However, that does not change the fact that generating tagged pdf is not an open problem in TeX world. – Aditya Aug 19 '13 at 18:59
• @SeanAllred - some reasonable subset of HTML5 might well make a good target for a Tex engine that aims to support reflowing. Javascript allows work arounds for some of the deficiencies of HTML. – Charles Stewart Oct 25 '13 at 13:54

## 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

• FWIW, ConTeXt can generate epub out of the box (including translating math to mathml). See ConTeXt wiki article for details. – Aditya Aug 16 '13 at 21:41
• I think "render" is the wrong verb here. – Raphael Jan 12 '14 at 11:43

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

• At its core, yes; it is still based upon the core TeX engine (with eTeX extensions) based upon macro expansion. expl3 is, however, a completely object-oriented language at this point; it's just not implemented as such at the moment. (I'm not part of the LaTeX3 team, but I'm working on something that will prove useful for taking advantage of this model: github.com/vermiculus/l3obj) – Sean Allred Aug 17 '13 at 22:29
• Seems to me like you want Luatex: it has that programming language and a builtin Metapost interpreter. Lua beats Python in terms of speed any day and there is Luajittex for computation intensive tasks. The only thing still lacking is a decent Latex integration. – Philipp Gesang Aug 18 '13 at 7:48
• To your modernization sugggestions, the wizards always reply with this : Many have tried, many have failed. You can nevertheless start from the Pascal code and implement it in your favorite language. But I think you are underestimating the the functional advantages of TeX over others for typesetting. Word, Open Office etc. are coded in very contemporary tools and we see how things are handled.It would not matter that much (in my opinion) had they been compilation-based-typesetters. Regarding the Tikz details, they are bound to PS, PDF specifications not to TeX. – percusse Aug 18 '13 at 21:17
• @NeilG: Lua does provide programmatic access to TeX internals. It is possible to directly generate PDF from a Lua program using ConTeXt Lua Documents. I use that to directly generate documents from XML files (e.g., CV with publications stored in an XML file). The difference between Lua and Python basically boils down to personal preference. – Aditya Aug 19 '13 at 6:19
• @NeilG: There are alternatives to TikZ which are closer to a sane programming language, e.g., Asymptote and ePiX. TeX World != LaTeX + TiKZ. – Aditya Aug 19 '13 at 6:20

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

### 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 which 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.

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

• A self-hosting TeX compiler? Is that possible on account of TeX being Turing complete? – jub0bs Aug 16 '13 at 8:01
• @Jubobs: In theory it's possible. It might be easier to write an llvm backend for TeX to create an emscripten for TeX. :-) – Martin Schröder Aug 16 '13 at 8:34
• This would be horrifying. +1! It would definitely show TeX's Turing-completeness, but my TeXpert skills are no where near the level of considering thinking about attempting this. XD – Sean Allred Aug 16 '13 at 12:33
• @SeanAllred: As an aside: no, it would not. That said, thanks for the brain teaser. – Raphael Jan 16 '14 at 23:04
• @Raphael Interesting, and honestly surprising! Thanks for the link! (edit: and apparently, for asking the Q!) – Sean Allred Jan 17 '14 at 2:04

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

• You know, I've never thought of that. The trend you speak of is very real. As it sits right now though, I'm not sure it's possible to adapt tex to a parallel architecture. I wasn't cleared for research in this area, unfortunately (even with all of these excellent ideas!), but I'd love to read up on the topic to see if this is doable. I fear the trend toward weaker cores will only continue to isolate TeX. – Sean Allred Jan 9 '14 at 9:16
• You could get a pretty easy setup for this, actually, since TeX already runs multiple times on any document with citations, table of contents, etc. Just start up the 2nd pass while the 1st is still running, but finished the first page. – Canageek Jan 12 '14 at 4:28
• @Canageek: I don't know enough about TeX to say that this would work; in particular, are all temporary files (resp. their fragments) written after page one in so far as they regard page one? (I'd guess no.) If that where true, you'd still have to synchronise the runs. That is to say, it's probably impossible to do using TeX as a black box, but it may be a feasible feature for a reimplementation. – Raphael Jan 12 '14 at 11:41
• @Raphael You are likely correct; you'd have to modify things a bit, for that reason and to make sure the 2nd pass doesn't catch up to the first, but at a core level it does things page-by-page, so it doesn't seem too hard compared to going into the LaTeX code and working out what can be done in parallel. – Canageek Jan 13 '14 at 5:35
• As mentioned here, it shouldn’t be too hard to lay out paragraphs in parallel using speculative rendering. This would imply discarding and redoing paragraphs if any of its definitions or counters are changed by preceding paragraphs (rendered in parallel), or if its subsequently calculated initial position would imply that it had to be broken across pages or was affected by floats. I think it’s likely that most paragraphs would only have to be rendered once. – Konrad Rudolph Aug 23 '18 at 9:40

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.

• It would be a challenging project (and someone needs to do it). I fear this just may not fly as original research, but I will definitely be asking (about all of these)! – Sean Allred Aug 16 '13 at 12:34

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.

• There’s also the idea of preferred and secondary hyphenation points. IIRC, the hyphenation dictionaries being shipped have that information, but TeX has no way to use it. – J. C. Salomon Aug 20 '13 at 8:07

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
• Could you elaborate a bit how LLVM could speed up the compilation? I thought the modern TeX implementations are written in C and interpret TeX files. Which parts can be replaced by LLVM in the toolchain? – Alexander Aug 16 '13 at 8:10
• @Reza I don't think you can parse tex with lex/bison as the lexical analysis has to be intertwined with execution. \foo\catcodeo=12 \foo the first \foo is one token but the second one is three. – David Carlisle Aug 16 '13 at 14:48
• This is so wrong: You don't need a LaTeX "compiler", but a TeX interpreter. – Martin Schröder Aug 17 '13 at 20:59
• @MartinSchröder: But do we really need code that changes the lexer during interpretation? If we had "proper" abstractions/PL features, could we not do without such? – Raphael Jan 9 '14 at 8:43
• @MartinSchröder Of course, that would not only enable but force package writers to design proper user interfaces (TikZ comes close even today, imho) which are separate from the implementation. I think that would be a good thing. – Raphael Jan 9 '14 at 11:30

# 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]

• many funny things with automatic placement of content are possible with luatex, see tex.stackexchange.com/a/65601/2891 - I think it shouldn't be hard to achieve what you want with this library – michal.h21 Aug 25 '13 at 10:45
• @michal.h21: Thanks. I’ll have a look at this :-) – Tobi Aug 29 '13 at 21:32

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.

• Could you elaborate on this? I'm not sure what you mean. – Sean Allred Aug 16 '13 at 14:24
• You want to write TeX without writing TeX? ;) – clemens Aug 16 '13 at 15:42
• Do you mean, redesign the syntax so it can be parsed without needing to execute the code, and base evaluation on lambda calculus – basically, functional TeX? That would sound like a good idea to me, but I suppose it just wouldn't be TeX anymore, but something completely different. – leftaroundabout Aug 16 '13 at 18:38
• IMHO, expl3 is this abstraction. – Sean Allred Aug 16 '13 at 19:45
• – Philipp Gesang Aug 24 '13 at 9:39

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.

• I'm not sure I fully understand how you want the footnotes delivered, I could think of two ways to interpret the above statement, but in either case that request appears to me a 1-2 weekends worth of effort. – Frank Mittelbach Aug 17 '13 at 12:13
• @FrankMittelbach Encouraged by your patience I edited my suggestion. More or less: any better support of the different mulitcols (parallel, running text, footnote in multicols) would be appreciated very much. – Keks Dose Aug 17 '13 at 20:48

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.

• For a one year capstone project, do not attempt to rewrite TeX. it will take much more than a year. – Aditya Aug 23 '13 at 2:39
• Also, C# would be a dismal choice for cross-platform compatibility and Java would be a dismal choice for anything you wanted to actually start ;). Many people have attempted this though, in languages such as Python, but C is simply a better choice. – Sean Allred Aug 23 '13 at 3:25
• (Plus, the day C becomes 'antiquated' is the day I am too old to be in CS.) – Sean Allred Aug 23 '13 at 3:26
• @bubba A complete, functional reimplementation of TeX in Java has been around since the late 90s: NTS. Turns out the various attemps of evolving TeX (Omega, pdfTeX) were more valuable than a -- no intention to belittle the work of the NTS authors -- “mere remake” in a different language. – Philipp Gesang Aug 24 '13 at 9:35
• Please never ever introduce Java to the peaceful world of TeX we have enough problems. – percusse Aug 25 '13 at 10:14

# P vs. NP

• I think this might be a bit beyond what is feasible for a one-year undergraduate research project ;) I'll have to read Plass' thesis more carefully; I didn't know it had such theoretical background. (Then again, he was Knuth's supervisee.) – Sean Allred Aug 21 '13 at 18:57
• @SeanAllred: Yes, of course. Nevertheless, I think it is very interesting that Typesetting is NPC. – Martin Thoma Aug 21 '13 at 19:34

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.

• pgfplotstable` can do this. – percusse Aug 19 '13 at 15:14
• @percusse I had a quick look through the manual, but without luck: there seems no way how pgfplotstable can notice that a certain row is the last one on this page and therefore a subtotal has to be calculated from the above numbers and printed in that cell. – Keks Dose Aug 19 '13 at 15:46
• @percusse : Subtotals and carry forward are important for business letters and every commercial software can deal with them. I suggested this issue, because to solve it is not trivial: You have to get a hook when TeX writes the last line of a page, and then calculate the subtotal and insert it. I 've been asking around for any solution for quite some years. – Keks Dose Aug 19 '13 at 15:54
• Let's see then :) Can you make that a question? It will probably trigger @DavidCarlisle anyway – percusse Aug 19 '13 at 15:59
• @percusse Later (soccer team calling...) – Keks Dose Aug 19 '13 at 16:01
• Could you explain why this is a problem (I don’t even understand what the problem is, actually …) so a bit more text would be nice ;-) – Tobi Jan 9 '14 at 23:48