(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.
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$