Four TeX processors (as described in TeX by Topic)

Question

I started reading TeX by Topic by Victor Eijkhout. He starts from describing four engines:

1. The input processor. This is the piece of TeX that accepts input lines from the file system of whatever computer TeX runs on, and turns them into tokens. Tokens are the internal objects of TeX: there are character tokens that constitute the typeset text, and control sequence tokens that are commands to be processed by the next two levels.

2. The expansion processor. Some but not all of the tokens generated in the first level—macros, conditionals, and a number of primitive TeX commands—are subject to expansion. Expansion is the process that replaces some (sequences of) tokens by other (or no) tokens.

3. The execution processor. Control sequences that are not expandable are executable, and this execution takes place on the third level of the TeX processor. One part of the activity here concerns changes to TeX’s internal state: assignments (including macro definitions) are typical activities in this category. The other major thing happening on this level is the construction of horizontal, vertical, and mathematical lists.

4. The visual processor. In the final level of processing the visual part of TeX processing is performed. Here horizontal lists are broken into paragraphs, vertical lists are broken into pages, and formulas are built out of math lists. Also the output to the dvi file takes place on this level. The algorithms working here are not accessible to the user, but they can be influenced by a number of parameters.

The author makes the following statement: “For many purposes it is most convenient, and most insightful, to consider these four levels of processing as happening after one another, each one accepting the completed output of the previous level.”

I don't understand how “each one accepting the completed output of the previous level” is possible, since the expansion processor (level 2) needs macro definitions that are assigned by the execution processor (level 3). I sent an email to the author of the book with a question how it is possible, there is no reply. Can somebody explain?

Update

I think I can accept the book's model, if we reconsider what completed means. The author later gives an example:

\def\DoAssign{\count42=800}

Given above the call

\DoAssign 0

produces

\count42=8000

This happens because the space was removed after \DoAssign by the input processor. In this sense it was completed before the next stage. Instead of: “\DoAssign gets processed, \count42 is assigned 800, and then the input continues from the last 0.”

Answer 1

Too long for a comment. That is a didactic asset to make comprehension easier. All four processors are coexist in TeX and their execution is interleaved and rather complex to explain step by step, so a simpler “first read then expand then execute then typeset” model is very useful to understand how things work.

For example, a simple line like

\edef\x{\if\string}!{\else a\fi}\x

exercises all four processors. With a minimal knowledge of TeX programming, you can split that line into 5 steps (give or take, depending on how fine-grained you want the explanation):

1. The execution (3) processor starts the \edef and starts expanding what's inside;
2. The expansion (2) processor expands the \if, which is false and skips to the \else and returns a;
3. The execution (3) processor assigns a to \x;
4. The expansion (2) processor expands \x to a;
5. The visual (4) processor typesets a.

which you can see already proves the “completed output” statement to be inaccurate, because the input processor didn't come into play (that's what my biased list tells you, at least), and (2) and (3) were interleaved. Nevertheless, it is correct, to some degree of simplification, and sums up what happened.

A more accurate (yet still lacking some steps) description of the process is:

1. (1) scans \edef;
2. (3) starts an assignment and calls (1) again to scan a control sequence;
3. (1) scans \x;
4. (1) scans {;
5. (2) starts expanding ahead;
6. (1) scans \if;
7. (2) expands \if, which starts expanding looking for two tokens;
8. (1) scans \string;
9. (2) expands \string to turn the next token into a catcode 12 token;
10. (1) scans }₁₂ (\string made it catcode 12 so the input processor never saw a }₁);
11. (1) scans !;
12. (2) \if sees }! and gives false, so TeX's scanner skips until an \else or \fi;
13. (1) {₁ is seen and skipped;
14. (1) \else is seen;
15. (2) \else is removed;
16. (2) a is seen and passed through to (3);
17. (2) \fi is seen;
18. (2) \fi is removed;
19. (1) }₁ is seen and signals the end of the \edef;
20. (3) the equivalent of \def\x{a} is executed;
21. (1) scans \x;
22. (2) expands \x to a;
23. (3) executes a;
24. (4) adds a to the current hlist;

which is a lot harder to understand (and takes a lot longer to read) than the simpler version, proving that the simpler model “is most convenient, and most insightful”.

Answer 2

For a trivial example, consider a line containing just:

a~b

Now we can imagine that this is what happens:

• The input processor converts these three characters into three tokens: (11, 'a'), (13, '~'), and (11, 'b'). (Recall that 11 is the category code for "letter", and 13 for "active character".)

• The expansion processor expands the "~" to \penalty 10000 \ (say), so that we now have the tokens corresponding to a\penalty 10000\ b.

• The execution processor converts that into a horizontal list.

• The visual processor breaks this paragraph (assuming it ends here) into lines, and outputs to DVI, etc.

Here, we pretended that each stage gets the completed output of the previous stage: that the input processor works on the whole line, then that expansion works on tokens produced by the input processor, etc. For many simple cases this understanding suffices.

(Obviously a macro definition that's encountered needs an "assignment" to happen before it's used, but even in such cases a simplistic picture of all these four processors happening in sequence for each line or "block" may suffice.)

In reality, the program internally just has a main control loop like (in Python-like pseudocode):

while True:
  t = get_x_token()
  ...

which "asks" for an expanded token one at a time, so lines are read in from the input file(s) as and when needed (when the current line has ended and another token is asked for, the next line is read), and an input stack is maintained, and expansion happens when necessary, and the character (from current font) "a" has already been put onto a horizontal list by the time "~" is encountered and yet to be expanded, and \penalty is handled by an action procedure, etc—everything is interleaved, but this is a much more complicated picture.

Answer 3

Ok, I feel compelled to post my own answer, since I don't understand why people explaining to me how parsing works and how powerful simplifications are. I've been a software engineer for decades, I know.

The question was about the meaning of the word completed and why it is insightful to think about the stages of parsing this way. I found the answer in an example that the author gives later in the book. My confusion stemmed from the fact that I considered a connotation of completed that means completely processed all the input. It seems like it's not what the author meant. Consider the following (an example from the book):

\def\DoAssign{\count42=800}

Given this definition the following input

\DoAssign 0

will produce the following assignement

\count42=8000

This counterintuitive result happens because the space was removed after \DoAssign by the input processor. In this sense the input processor has completed its job before the next stage. Instead of: “\DoAssign gets processed, \count42 is assigned 800, and then the input continues from the space and the following 0.”