Why isn't everything expandable?

Question

TeX's macro processor does its work in a process called expansion. For an input stream of tokens, the macro processor repeatedly expands them until non-expandable tokens remain. The resulting stream of non-expandable tokens is passed to the TeX's execution processor. The process of expansion can be viewed as calling a function that expands to its result.

Macros absorb their arguments from the input stream and expand to their replacement text, with arguments in-place. Other types of tokens can be expanded differently: for example, conditionals test their arguments (possibly expanding them, too) and skip the branch for which the condition is false.

But there are also non-trivial tokens that are not expandable: most notably, \def and (not actually a token, but see below) register assignments. This means that they can't be used in a macro to obtain a result through expansion: they will be just passed through untouched.

For example,

\edef\test{\def\a{x}\a}

will fail with ! Undefined control sequence., because \def was not expanded and then \a was examined, which proved to be undefined.

Likewise,

\newcount\count
\edef\test{\count=1}
\showthe\count

will show 0, not 1, because, again, none of \count=1 were expandable.

One can imagine a system where such operations are expandable. More precisely, expanding \def would absorb a control sequence name, parameter text and replacement text from the input stream, define the new macro and expand to nothing. Similarly, an operation named \assign would read a register name and a value from the input, do the assignment and expand to nothing. This can be also extended to \let, \advance etc.

Thus the above examples would now behave differently: in the first \edef, \def would read in \a{x}, define \a and expand to empty text. After this expansion the token list would contain \a, which would then expand to x.

In the second example (let it be

\edef\test{\assign\count1}

now) \assign would set \count to 1, and expand to nothing. In the result \test would be defined to be empty, but the value of \count would have been altered.

This new system would allow to achieve some things in a more straightward manner. For example, the problem of defining a macro expanding to n asterisks could now be solved with

\newcount\c
\def\asterisks#1{%
  \assign\c0
  \loop\ifnum\c<#1
    *%
    \advance\c by 1
  \repeat}

, because (see the definitions of \loop and \iterate) \def, \let and assignments are now expandable. Another substantial consequence would be that many more things could be done in macros whose result is passed as an argument to another macro. Observe how e-TeX's \numexpr and friends are already a considerable step in this direction.

The question is: Why doesn't TeX implement such an approach, leaving instead some important operations non-expandable? What are the shortcomings of this approach and the advantages of TeX's implementation?

One possible reason might be that Knuth wanted macros to act as pure functions, incapable of changing the context they are being expanded in. A similar hint can be found in the TeXbook on the matter:

The expansion of expandable tokens takes place in TeX's "mouth," but primitive commands (including assignments) are done in TeX's "stomach." One important consequence of this structure is that it is impossible to redefine a control sequence or to advance a register while TeX is expanding the token list of, say, a \message or \write command; assignment operations are done only when TeX is building a vertical or horizontal or math list.

Another reason might be that nested and/or recursive macro calls could interfere with each other if they had write access to "external" data available to them.

Note: the question is not about what is permitted and what is not by the architecture of TeX, but about why such architecture was designed in the first place.

Answer 1

While a definitive answer can only come from the Stanford team involved in development of TeX, and from Professor Knuth in particular, I think we can see some possible reasons.

First, Knuth designed TeX primarily to solve a particular problem (typesetting The Art of Computer Programming). He made TeX sufficiently powerful to solve the typesetting problems he faced, plus the more general case he decided to address. However, he also kept TeX (almost) as simple as necessary to achieve this. While expandable macros are useful, they are not required to solve many issues.

Secondly, there are cases where an expandable approach would be at least potentially ambiguous. Bruno's \edef\foo{\def\foo{abc}} is a good case. I'd say that here the expected result with an expandable \def is that \foo expands to nothing, but I'd also say this is not totally clear. There is the much more common case where you want something like

\begingroup
\edef\x{%
 \endgroup
 \def\noexpand\foo{\csname some-macro-to-fully-expand\endcsname}%
 }
 \x

which would be made more complex with expandable primitives.

The above example points to another grey area: what would happen about things like \begingroup and more importantly \relax. The fact that the later is a non-expandable no-op is often important in TeX programming. (Indeed, the fact that \numexpr, etc., gobble an optional trailing \relax is sometimes regarded as a bad thing.)

Finally, I suspect that ease of implementation is important. The approach of having separate expansion and execution steps makes the flow relatively easy to understand, and I also suspect to implement. An approach which mixes expansion and execution requires a more complex architecture. Here, we have to remember when Knuth was writing TeX, and the fact that programming ideas which we take for granted today were not necessarily applicable in the late 1970s. A fully-expandable approach would I suspect have made the code more complex and slower. The speed impact is one that was important when TeX was running on 'big' computers.

Answer 2

Every time I see this question I feel like there should be something more to say, so let me take a shot now.

From my perspective, the intent of TeX's design vis à vis expansion is that it should provide a means for transforming simple input into complex typesetting directives. It is a programming language only insofar as it programs the virtual printing press, but not the internal workings of that machine. It is Turing complete only insofar as one could (if one were insane/Bruno Le Floch :) ) reimplement that printing press within TeX using only expandable macros (as it has indeed been shown (see the lambda package) that this is capable of implementing the lambda calculus).

According to this, the correct mental model of TeX is of a crazy-looking computerized printing press reading a long stream of punch cards (remember in what era Knuth first saw a computer, and for that matter in what era he wrote TeX) that fill its registers, access its fonts, and build its horizontal and vertical and math lists. These punch cards come from an earlier machine that reads your file and encodes it as TeX primitives, occasionally receiving back from the printing press some more text to encode (such as inside an \hbox). The card-generating machine, called the "mouth" in the more organic metaphor of the TeXbook, does nothing but render your .tex file as suitable input for the printing press; it (perhaps more analogously to a card-sorting machine) simply receives some instructions as to what to do with control sequences, and arranges the input accordingly.

(Edit: The shorter version of this is that "mouth = syntax" and "stomach = semantics", where "mouth = expandable" and "stomach = executable" as well. This is spelled out in the interesting historical comment in errorlog.pdf of 18 September 1982: "Make \expandafter more powerful by moving it from semantics to syntax [i.e., from stomach to mouth].")

This picture is complicated by the fact that the printing press can change its instructions in mid-stream, and that expandable control sequences are visually identical to unexpandable primitives. I believe, however, that it is supported by the similar metaphor of the "mouth" and "stomach" and the quote you give from the TeXbook: the "language-based" programming of expansion and the "machine-based" programming of execution are really two entirely different and not symmetric facilities in TeX. It is the needs of the latter that shape the course of the former, which is entirely subordinate.

Answer 3

Knuth didn’t want to make a whole new programming language, he just wanted to have a typesetting language. Making TeX a Turing complete language was lobbied by Guy Steele [TEXTURING]. The word “Turing complete” gets thrown around a lot for some reason.

Guy Steele is known for, among other things, as the co-author of the so-called Lambda papers [LAMBDA] which lead to the programming language Scheme. As an aside, that language was used in the computer science textbook “Structure and Interpretation of Computer Programs” [SICP] which has been used, and continues to be used, as the basis of CS courses in universities around the world [ADOPT].

In the original CS course at MIT, the authors Harold Abelson and Gerald Jay Sussman introduce many programming paradigms along the way. It isn’t until the middle of the course that they introduce program state [STATE]. It is important to note how they stress the complications of introducing state (/assignment/time/side-effects) in a language.

CS is still a young thing, and there hasn’t been but ~30 years from the making of the above videos. In between then and now, there has been a lot of research effort put into so-called “pure functional languages”. One of which is especially active is called Haskell [HASKELL].

The reason why I mention Haskell is because it was from one of the talks of its founding fathers, Simon Peyton Jones, that it hit me that any kind of I/O needs state. And as such, even the usage of Scheme’s REPL (Read-Eval-Print-Loop) in the MIT CS videos wasn’t, strictly speaking, pure functional programming because you cannot have any kind of output without state. In other words, a purely functional expression, in the strict sense of the word, is just some execution in some machine and the only way to know it’s doing something is that the machine gets hotter (paraphrasing mr. Jones [SPJ] here).

In that same way, anything that TeX – or, in fact, any other language – outputs, cannot be “pure” as as long as you want something output, you need state. The trick is to have those side-effects in check.

The way I like to think of TeX, even if it may not be entirely accurate, is to think of the so-called “mouth” as the functional part, and the “stomach” as the imperative, “having state” -part where assignments happen. I think it was Ryan or Andrew who said at some point that sometimes it feels like TeX was built as this giant puzzle. And I must agree; it’s as if there must be a way, by putting together everything we know about CS, to get those TeX’s side-effects in check in a controlled manner to achieve a more easily programmable environment.