21
$\begingroup$

It seems to me that the macro language employed by $\TeX$ can maybe be seen as some kind of term rewriting system or some kind of programming language with call-by-name scoping.

Even modern implementations of the $\TeX$ engine (e.g. $\mathit{Xe}\TeX$) interpret code in a quite direct way and I'm not aware of any attempt at optimizing the execution (like modern optimizing interpreters can do). However, devising correct optimization passes for a language like $\TeX$ is going to be very difficult because of the "action at a distance" that macro redefinitions can have, and the ability of redefining macros by calling them by name.

So implementing an hypothetical optimizing interpreter for $\TeX$ sounds a very difficult problem in practice but also a very useful one, since $\TeX$ is used all over math and science and slow compilation times are a known drawback of the system. Note that the majority of time is spent interpreting code, not computing the actual typesetting, especially when computationally heavy packages are used (such as tikz).

Maybe a formal semantics for the language could be a start to address the problem. So has the semantics of the $\TeX$ programming language ever been formalized?

$\endgroup$
  • $\begingroup$ Partial answer in tex.stackexchange.com/questions/4201/… $\endgroup$ – Amaury Pouly Feb 26 '18 at 8:09
  • $\begingroup$ Thanks! Although I'm not interested into formalizing TeX's syntax into a context-free grammar, the answer is interesting. However I think it confuses levels a bit. Grammars are never enough to know if a piece of code in any language is wellformed or not, because other passes are needed such as type checking or variables look up. Nevertheless most languages grammars are described with BNFs modulo those aspects. Anyway, I'm more interested into the semantics of the macro language, not the grammar. $\endgroup$ – gigabytes Feb 26 '18 at 8:18
  • $\begingroup$ To be honest the answer's author addresses this concern in the comments of other answers, the point being that in the case of TeX, parsing involves evaluation and thus to know if a piece of code is wellformed you may have to evaluate an arbitrary piece of code. That's again about syntax, anyway. $\endgroup$ – gigabytes Feb 26 '18 at 8:22
  • $\begingroup$ In this blog entry rjlipton.wordpress.com/2011/03/09/tex-is-great-what-is-tex , Lipton relates that Knuth never formally defined $\TeX$. $\endgroup$ – Lamine Feb 26 '18 at 11:07
  • $\begingroup$ Well, the only thing that comes close to what you suggest is initex, which is a "precompiler", basically you can have TeX perform certain operations, then stop its run, save the current state as a "format" (file.fmt) which is then loaded quite fast. This is actually what's going on with LaTeX itself: it's built over TeX core this way, similarly plain TeX, ConTeXt (though that's a bit more complicated), etc. $\endgroup$ – yo' Feb 26 '18 at 14:43
9
$\begingroup$

(With apologies for a long answer that goes in a direction different from the scope of the site: frankly I was surprised to see the question here in the first place….)


TeX was designed for typesetting, not for programming; so it is at best “weird” when considered as a programming language.

— Donald Knuth, Digital Typography, page 235

I have read a lot over the last couple of years about the early history (circa 1977) of TeX, and a lot of what Knuth has written. My conclusion is that the moment we speak about “TeX (as a programming language)”, something is wrong already.

If we look at the early “design documents” for TeX written before (see TEXDR.AFT and TEX.ONE, published in Digital Typography), it is clear that Knuth was designing a system primarily intended for typesetting The Art of Computer Programming (he has said (e.g. here) that the main users he had in mind were himself and his secretary), with the idea that, suitably modified, it may be useful more generally. To save typing, for things one repeatedly had to do (e.g. every time TAOCP needed to include a quotation from an author, you'd want to move vertically by a certain amount, set a certain lineskip, pick up a certain font, typeset the quote right-aligned, pick up another font, typeset the author's name…), there were macros.

You can guess the rest. What we have in TeX is a case of “accidentally Turing-complete” (more), except that it happened in the midst of a community (computer scientists and mathematicians, and DEK himself is to “blame” too) who were (unfortunately) too clever to ignore this. (Legend has it that Michael Spivak had never programmed before he encountered TeX, but he was so taken with it that he ended up writing AMS-TeX, at the time one of the most complicated set of macros in existence.) Because TeX was written to be portable across a large number of systems (which was a big deal at the time), there was always a temptation to do everything in TeX. Besides, because of his compiler-writing experience, Knuth wrote TeX like a compiler, and occasionally described it as one, and if the program that works on your input is a “compiler”, then surely you're programming, right?

You can read a bit more about how Knuth didn't intend for any programming to be done in TeX, and how he “put in many of TeX's programming features only after kicking and screaming”, in this answer. Whatever his intentions were, as I said, people did start to figure out ways to (ab)use the TeX macro system to accomplish surprising feats of programming. Knuth found this fascinating and (in addition to adding some features into TeX itself) included a few of these in Appendix D “Dirty Tricks” of The TeXbook, but it turns out, despite the name, that “nine out of ten examples therein are used in the implementation of LaTeX”.

Let me put it another way: LaTeX, the macro system that Leslie Lamport wrote on top of TeX, as an idea, is a great one. Authoring documents in a semantic, structured, human-oriented way, rather than (Knuth) TeX's page-oriented way, (or as Lamport called it, logical rather than visual) is a great one. But implementing something as complicated as LaTeX using TeX macros rather than in a “proper” programming language is, in my view and at least if it were done today, somewhere between a giant mistake and an act of wanton perversity. Even Knuth is shocked that people don't just extend the TeX program instead of doing everything in TeX macros.

Today there are much better ways to do “programming”; you can use an external program in any of the many languages widely available on most people's computers, or you can use LuaTeX and program in Lua (and do a better job than you ever could with TeX macros alone, because you can manipulate internal structures and algorithms at the right level). And if you do it right, you could have programs that work better or faster than those implemented in TeX macros.

The task of making programs in TeX faster is almost amusing when seen in this light, and reminiscent to me of the final words of the paper describing another “accidentally Turing complete” programming “language”: Tom Wildenhain's lovely “On the Turing Completeness of MS PowerPoint (video) from last year:

While the PPTXTM proves the theoretical possibility of PowerPoint development, […]. Work also needs to be done in PowerPoint application optimization. There is a lot of potential here to exploit PowerPoint's automatic buffering of the next slide, which through careful slide placement may be used to greatly increase application performance.

The anecdote that Lipton describes is illustrative. Not only has there never existed a formal semantics of TeX, there is also unlikely to be one. It is just too “weird” a “language” for that, and (as I hope I have explained above) it is not even intended as a language. For instance, you may think you are writing macros as functions, but introduce a single stray character (even a space) in it, and TeX immediately treats it as a typesetting instruction.

In short: TeX reverts to typesetting at the earliest opportunity, and when it expands macros it does so grudgingly (impatient to get to its “real” work of typesetting), and these expansions can themselves depend on hundreds of kinds of “state” within the TeX program (the values of parameters like \hsize or \baselineskip, the contents of boxes and other registers…), which is why any formal semantics of TeX must necessarily be something that takes into account the entire state of the program and all its memory, until we end up with something like “the meaning of TeX code is whatever TeX does”, in a form more complex than the TeX program itself.


So fine, (if I've convinced you) TeX was not intended as a programming language and does not work like real ones, there is no formal semantics, and there are better ways to program today — but all this does not help with your actual question/problem, which is that in practice, many documents meant for processing by TeX do use complicated macros (like LaTeX and TikZ), stunning edifices of monstrous complexity built on top of each other. How can we make it faster and devise “optimization passes”?

You will not get there with formal semantics IMO. I have thought recently about this, and the following are some preliminary thoughts.

My impression is that Knuth was one of the experienced compiler-writers in the 1960s (that's why he got asked to write the compilers book that turned into The Art of Computer Programming), and TeX is (in many ways) written the way compilers were written in the 1970s, say. Compiler techniques and design have improved since then, and so can the TeX program be. Here are some things that can be done, by way of speeding things up:

  • At heart, TeX is written like an “interpretive routine”, where the TeX “eyes” and “mouth” (its input routines) deliver instructions to its “stomach” (its semantic routines), to be executed one by one. (You can see a list in part 15 of the TeX program.) For example, when TeX's eyes/mouth encounter \hfill or \hskip in its input, the stomach gets a “hskip” command, that it acts on. This is similar to what are called bytecode interpreters today, and there may be value in refactoring the TeX program to emit these bytecodes/opcodes explicitly, so that we may be able to use existing (more conventional today) compiler techniques. Or at least cache them to avoid redoing work. There are of course many challenges:

    • The execution of a command in the “stomach” usually still involves reading the input, i.e. the work of the input routines and semantic routines do not happen in separate phases. E.g. the “hskip” command, if given \hskip (rather than say \hfill) will invoke scan_glue to read a glue specification from the input, which in turn can involve expanding macros and so on until enough tokens are found for the glue, leaving the input stack in a substantially different state.

    • Engines like eTeX and pdfTeX and XeTeX and LuaTeX introduce new commands and primitives (the eTeX / pdfTex primitives are practically used by everyone in practice); you'll need to support them too, not just those in the original Knuth's TeX program.

  • We could do something like “speculative execution”, processing future paragraphs (maybe starting at natural checkpoints like new sections or chapters) in parallel (using multiple cores), keeping track of all the TeX internal state they use (depend on), and throwing away that work (and redoing it) if later we find out that an earlier paragraph ends up changing some of that state. At the moment TeX runs entirely sequentially on 1 processor; typical hardware has moved in a different direction and multiple cores are available.

  • Even simpler, we could simply cache the work (what TeX state was accessed and modified) by a certain section of the input file. (We could do this caching at the level of the input—the net result of expanding all macros—or at the level of what set of boxes were assembled, or all the way to the total state of the program.) E.g. the contents inside a \begin{tikzpicture} … \end{tikzpicture} is unlikely to depend a lot on TeX state like the page number counter, so when we recompile the TeX document we can simply reuse all the work — if we have kept track of enough information to know that it is safe to do so. (Of course TikZ in particular has ways to externalize this and include the results, but the idea is more general.)

  • We can use techniques (e.g. those used in functional programming) to do some TeX processing with “holes” — e.g. right now, when you write \ref{foo} in LaTeX to refer to a (say future) section number, it works only in two compilation passes: first the entire document is processed (all paragraphs typeset, floats positioned on pages, etc.) with the section numbers being written out to an auxiliary file, then on a second pass all the work is done again, with the section number actually available this time. (This kind of hack may have been inevitable at the time, and I know the impact on the running time is “only a constant factor”, but….) Instead, what if we could simply process the document with a “hole” (a box with undetermined contents but some estimated width) left for the section number, then at the end of the document processing populate the box? (Yes, our estimated width may turn out wrong and the paragraph may need reprocessing and consequently even the page, but we could either do the work if necessary, or accept, for speed, a mode in which we'll allow a wrong width for the section number.)

  • Similar techniques can work for interactive editing of a TeX document: when you edit a paragraph it can be processed “live”, with future paragraphs simply moved down the galley (say). We know it's possible, as there already exist (commercial) TeX implementations that do this, e.g. BaKoMaTeX and Texpad and the former Textures. (See the video on the home page of BaKoMa-TeX and similarly TeXpad's, e.g. this video — I tried the latter and it was unbearably buggy in practice though.)

  • Not to be underestimated: the value of showing things to the user, making TeX more debuggable. Right now, users see only their TeX input and have no idea exactly what work TeX is doing, e.g. how much time it's spending on line-breaking for paragraphs, or on macro-expansion (and of which macros), what boxes it's assembling and throwing away, what specials are being written out by which package, etc. I (perhaps optimistically) believe that there exist users who would like to see this information and would find it useful e.g. to know whether the weird package they're using for shading equations with a gradient in the background is cheap (adding little to the processing time) or not. By seeing where a lot of wasteful work is being done, they could throw some of it away (at least until their final print run). (This is somewhat like compilers or other tools inserting profiling information into programs.) Making TeX more transparent and debuggable may be a huge usability improvement, for instance. (TeX is already quite user-friendly and debuggable for its time IMO if we use mostly plain TeX with very few macros, but not with LaTeX or how the bulk of users encounter it today.)

Also, any future work should probably take into account (build on) LuaTeX which is the best modification of TeX we have currently.

All of these are just idle thoughts (I haven't implemented any of them, to know the effort required or how much speedup we'd gain), but I hope this goes some way towards answering your question or giving you ideas for future directions.

$\endgroup$
  • $\begingroup$ I surely agree with you that programming in TeX is masochistic but as you said, people do it anyway and, as you pointed out, the benefits of better tooling would go down to users the most. In the second part of your answer you touch many of the ideas I had in mind before asking the question. I might add that because of \widthof and similar, the termination of a loop might depend on the entire typesetting algorithms and font definitions. So that’s really weird yes XD $\endgroup$ – gigabytes Feb 27 '18 at 1:50
  • $\begingroup$ This answer needs a major rewrite (didn't have time to write a short one!), but super coincidentally, I just now came across this quote from Knuth in Peter Seibel's Coders at Work in answer to a question about formal correctness: “Or TeX, for example, is a formal mess. It was intended to be for human use, not for computer use. To define what it means for TeX to be correct would be incomprehensible. Some methods for formal semantics are so complicated that nobody can comprehend the definition of correctness.” $\endgroup$ – ShreevatsaR Feb 27 '18 at 7:57
  • $\begingroup$ So TeX is a programming language but I had to put in those features kicking and screaming. […] In a way I resent having every language be universal because they’ll be universal in a different way. […] I was really thinking of TeX as something that the more programming it had in it, the less it was doing its real mission of typesetting. When I put in the calculation of prime numbers into the TeX manual I was not thinking of this as the way to use TeX. I was thinking, “Oh, by the way, look at this: dogs can stand on their hind legs and TeX can calculate prime numbers.” $\endgroup$ – ShreevatsaR Feb 27 '18 at 8:15
  • $\begingroup$ Honestly I don’t see Knuth’s reason to add programming facilities to TeX by “kicking and screaming”. TeX programming is not used to do arbitrary computation, but to build abstractions around problems, often coming from TeX syntax itself, so that users can more powerfully use it for typesetting. So I don’t agree with Knuth saying the more programming he put in it the less it would do typesetting. Maybe if he accepted the need for general programmability from the start he could have come up with something way better. The same thing happened with the web, and now the world runs on JavaScript. $\endgroup$ – gigabytes Feb 27 '18 at 9:16
11
$\begingroup$

No, to my knowledge there has been no work on formalizing TeX of the kind you are interested in.

(What follows is a subjective and personal commentary). I think it is an intriguing and well-posed idea, and your motivation of using it to perform optimizations sounds reasonable -- another related question is whether you could define a bytecode format for it to speed up interpretation. On the other hand, the idea has two downsides.

First, it is not clear to me that there is a large potential for optimizations (for example, what kind of program-preserving transformations could one perform to speed up computation?), as it may be that the language semantics is intimately related to parsing the character flow, and thus not very accommodating to the design of optimization-friendly intermediate representations.

Second, the need for improvements in TeX interpretation speed is not well-established: the speed of batch speed building has remained reasonable thanks to hardware improvements. Cases where speedups could be welcome are complex graphics package (beamer presentations can take quite some time to build), packages embedding rich computations (but then another language may be more appropriate), and use cases requiring fast rebuild for instant user feedback (but then incrementality, rather than optimization, may be the point; a formal semantics would certainly help reason about incremental implementations as well).

That is to say: this sounds like a fun, instructive topic, but it is not clear to me that the practical justifications for doing the work are strong. If someone was interested in doing it out of curiosity, that sounds like an excellent adventure, but otherwise there may be other ways to employ the same skillset whose impact would be more sought-after by end-users.

$\endgroup$
  • $\begingroup$ Thanks. As you said, incremental compilation is maybe more interesting that optimisation here, especially if we think about how poorly editors can currently integrate with the language $\endgroup$ – gigabytes Feb 26 '18 at 13:00
  • $\begingroup$ Another application which is related to optimisation is to automatically cleanup code, for example removing useless “\expandafter”s or similar. $\endgroup$ – gigabytes Feb 26 '18 at 13:03
  • $\begingroup$ "complex graphics package" Of course, if you use tikz or pgf graphics, you can always externalize them and save a lot of time on builds when they don't change (which is a lot like incremental compilation, really). $\endgroup$ – JAB Feb 26 '18 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.