TeX Finally Made Functional

This is more of a computer programming post than a math post, but since we all use TeX, I thought it might be of general interest. I came across this paper by Heckman and Wilhelm, which describes how to implement TeX’s algorithm for typesetting math formulas in a functional language (namely, ML). We see the output of this algorithm every time we look at a math paper, but until now it lacked a precise formal description other than what was embedded Knuth’s Pascal code. Since Knuth wrote TeX back when computers were much slower and compilers were much dumber, the code contains many hand optimizations that make the logic hard to follow. (The algorithm itself is too complicated to lend itself to a purely verbal description.) By rewriting it in a functional language, the authors are able to turn the algorithm into a well-defined mathematical function.