Stanford Lecture: The Internal Details of TeX82 - Session 4 (July 28, 1982)

Key Concepts

• Control Sequences: Commands in TeX, typically starting with a backslash, that control typesetting.
• Macros: User-defined control sequences that represent a sequence of TeX commands.
• Token Lists: Internal representation of TeX commands and characters, stored as one-word items.
• Command Codes: Numbers (1-14) representing the type of token.
• Character Codes: Numbers representing specific characters.
• Active Characters: Characters with a specific chr code (13) that act as single-character control signals.
• Long/Outer Macros: Classifications of macros indicating parameter handling (long) or intended usage context (outer).
• Hash Table: A data structure used to associate control sequences with their definitions.
• Table of Equivalence (eqtb): A central table storing meanings of control sequences and other internal quantities.
• Save Stack: A data structure used to store information for restoring previous states, particularly when exiting groups.
• Equivalence Levels: A mechanism to track the scope of definitions, distinguishing between global and local settings.
• Garbage Collection: The process of reclaiming unused memory, which relies on reference counts for token lists.

Control Sequences and Macros in TeX

The discussion begins by clarifying the terminology used in TeX documentation. "Macro" is the term used for user-defined control sequences, which are essentially shortcuts for longer sequences of commands. The manual might also refer to them as "control sequences" because they control TeX's behavior.

Types of Control Sequences

TeX recognizes three main types of control sequences:

1. One-character long: A backslash followed by a single character.
2. Two or more letters long: A backslash followed by a sequence of characters where each character has a chr code of 11 (indicating it's a letter). Example: \end.
3. Active Characters: Characters with a chr code of 13. These are distinct from backslash-initiated control sequences. For instance, in TeX82, \ followed by & is different from & if & has a chr code of 13.

A key difference between backslash-initiated control sequences and active characters lies in how they handle subsequent spaces. Control sequences starting with a backslash ignore any following spaces, while active characters do not "gobble up" spaces, meaning the space after them will be preserved.

Macro Classification: Long and Outer

Control sequences (macros) can be further classified as:

• Long: Their parameters can span across paragraph breaks (i.e., include the end-of-paragraph symbol).
• Outer: They are intended to be used only in specific "outer" parts of the file, not within other structures like math formulas. This is a mechanism to catch errors, such as a missing closing brace, by preventing these commands from appearing in inappropriate contexts.

These classifications (long, outer, both, or neither) are crucial for error detection and proper parameter handling. For example, a command like \begin{theorem} might be defined as outer because it shouldn't appear within a mathematical formula. A macro expecting multi-paragraph content would be defined as long. If a macro is not long and the end of a paragraph is encountered before its arguments are complete, TeX will attempt to recover and proceed to the next paragraph.

Internal Representation: Token Lists

Internally, TeX represents sequences of commands and characters as token lists. These are stored as one-word items in memory.

Token Structure

A token can be one of two types:

1. Command and Character Pair: This is formed when TeX scans a character. It consists of a command code and a character code.

   • Command Code: A number between 1 and 14, indicating the type of token. For example, command code 11 signifies a "letter."
   • Character Code: A number representing the internal code of the character (e.g., 65 for capital 'A').
   • Example: Scanning the letter 'A' results in a token with command code 11 (letter) and character code 65.

2. Control Sequence Token: This represents a control sequence. Instead of storing the command and character codes directly, it stores a pointer to an entry in a hash table. This is because the meaning of a control sequence can change during processing.

   • Hash Table Pointer: This points to a word in the hash table that contains the definition of the control sequence.
   • CS Token Flag: A specific value (e.g., 2^12) added to the hash table pointer to distinguish control sequence tokens from command/character tokens.

Command Codes and Their Meanings

The lecture details the first 14 command codes, which are crucial for internal processing:

• Code 0 (Escape): Represents the backslash character. It's never passed through the scanner as a token because it initiates a control sequence. It's also used to mean "relax" (do nothing).
• Code 1 (Left Brace): Represents {.
• Code 2 (Right Brace): Represents }.
• Code 5 (Carriage Return): Represents an end-of-line character. It's also used to mean "output a macro parameter" and "backslash CR." It's converted to a space by the scanner.
• Code 13 (Active Character/End of Paragraph): Represents active characters and the end of a paragraph. These are special commands inserted into token lists for parameter handling.

Character Encoding and Token Limits

While fonts can support 256 characters, TeX's internal processing is primarily limited to 7-bit codes (128 possibilities). This is due to keyboard input limitations and the design of internal arrays like xchr and xord. Extending to 8-bit characters would require modifications to these arrays and could lead to incompatibilities with other TeX versions. The web system, used for writing TeX, also uses internal codes identical to TeX's.

Demonstrating Token Lists: The show token list Procedure

The show token list procedure (module 273) is used to interpret and print the contents of a token list. This is what TeX uses to display its internal understanding of macros.

Example: Defining a Macro \mac

A complex example of defining a macro \mac is presented to illustrate the token list representation:

\def\mac#1#2 blah #1 - a ##1 \par

The resulting token list for \mac would conceptually include:

1. Letter 'a': Represented by command code 11 and its character code.
2. Parameter 1 Match: A special token indicating the start of parameter 1. It stores the internal code of the # character used for parameters. The number '1' is implicit.
3. Parameter 2 Match: Similar to parameter 1.
4. Blank Space: Represented by a "spacer" command code and the code for space. All space-like characters (tabs, carriage returns) are converted to a single space token for consistent parameter matching.
5. Control Sequence \b: Represented by the CS token flag plus a pointer to 'b' in the hash table.
6. End Match: A special token (command code 14) signaling the end of macro parameter matching.
7. Output Parameter 1: A token indicating that parameter 1 should be inserted.
8. Control Sequence \a: Represented by the CS token flag plus a pointer to 'a'.
9. Blank Space: As before.
10. Macro Parameter Hash Mark: Represents ##, which is interpreted as a literal #.
11. Parameter 2: Represented by an "output parameter 2" token.
12. Blank Space:
13. Output Parameter 2: Another token for parameter 2.
14. Null Token: Indicates the end of the token list.

When show token list processes this, it translates these internal tokens back into a human-readable format, including a, #1, #2, blank space, \b, and so on. It also handles the display of control sequences, often adding a space after them if they end in a letter to avoid ambiguity.

The Table of Equivalence (eqtb)

The Table of Equivalence (eqtb) is a fundamental data structure in TeX that stores the meanings of all control sequences and other internal quantities. It is divided into six regions:

1. One-character control sequences: For active characters and backslash-prefixed single characters (256 total).
2. Greater than or equal to letter control sequences: For multi-letter control sequences. This region includes a hash table for efficient lookup.
3. Skips and glues: For parameters related to spacing and stretching/shrinking.
4. Half-word entries: Local quantities like font names, paragraph shape pointers, and box pointers.
5. Integers: Full-word integer values.
6. Dimensions: Scaled values representing lengths.

eqtb Entry Structure

For regions 1-4, each entry in eqtb consists of:

• eq_type (quarter word): The command code indicating the type of equivalent (e.g., "defined," "long," "outer," or a primitive command like \def).
• equiv (half word): The actual value or pointer. For defined control sequences, this is a pointer to the token list representing the macro. For other types, it could be a font number, a box pointer, etc.

Regions 5 and 6 store full words (integers or scaled values).

Hashing and Coalescing Lists

Region 2, for multi-letter control sequences, uses a hash table. The process involves:

1. Calculating a hash code for a sequence of letters.
2. Using this hash code to find an entry in the hash table.
3. If multiple control sequences hash to the same value, they are linked together in a coalescing list.
4. A student's thesis refined this method, suggesting that 85% of the table should be for the main entries, with the remaining 15% used for overflows, leading to an average list length of about 1.7.

Defining and Redefining Control Sequences

When a control sequence is defined (e.g., \def \a {something}):

1. TeX finds the control sequence (\a) in eqtb using its hash code.
2. It determines that the eq_type is "define."
3. It then scans the definition ({something}), builds a token list for it, and stores it in memory.
4. The equiv field for \a in eqtb is updated to point to this new token list.
5. Crucially, the previous meaning of \a is saved on the save stack along with the address in eqtb that needs to be restored. This ensures that when TeX exits the current group (e.g., due to a closing brace }), the previous definition can be reinstated.

Save Stack and Equivalence Levels

The save stack is a critical mechanism for managing scope and restoring previous states.

Save Stack Entries

Each entry on the save stack typically consists of two words:

1. The address in eqtb that needs to be restored.
2. The previous value that was stored at that address.

A special "easy fix-up" mechanism exists for common cases (like undefined control sequences) to save space by storing only one word.

Equivalence Levels and Group Management

TeX uses equivalence levels to track the scope of definitions.

• Level 1: Represents the outermost level (outside any braces).
• Level 2 and above: Represent nested groups (inside braces).

When TeX encounters a left brace {, the current level (cur_level) is incremented. When it encounters a right brace }, it processes fix-ups on the save stack until it reaches the boundary corresponding to the start of that group.

Global Definitions (gdef)

Global definitions (gdef) are a special case. When a control sequence is defined globally:

• The old value is not saved on the save stack because it's intended to be permanent within the current scope.
• The eq_level for that definition is set to 1.
• When restoring at the end of a group, if a global definition is encountered (indicated by eq_level being 1), it is not restored, and its reference count is decremented.

Handling Nested Definitions and Scope

The system is designed to correctly handle nested definitions. If a local definition is made within a group, and then another local definition of the same control sequence is made within a deeper nested group, the save stack will store the intermediate definition. Upon exiting the deeper group, the intermediate definition is restored. Upon exiting the outer group, the original definition is restored.

A key invariant is that entries on the save stack have levels strictly less than the current level. This prevents unnecessary saving and restoration.

cur_group and Boundary Words

The cur_group variable tracks the type of group currently being processed (e.g., hbox, vbox). Boundary words on the save stack now store information about the interrupted group type, allowing TeX to correctly resume processing after exiting a group. This was a significant improvement over older versions of TeX.

Garbage Collection and Reference Counts

Token lists have a reference count. When a token list is no longer referenced (e.g., after a global definition overwrites a local one), its reference count is decremented. If the count drops to zero, the token list is "flushed" (memory is reclaimed). This is a form of garbage collection.

Error Messages and Levels

Error messages related to scope often report levels relative to the outermost level. For example, if TeX is at internal level 2 (inside one pair of braces), it might report the error as occurring at "level 1" to the user, as cur_level - level 1.

Studying the TeX Program

The lecture concludes with advice on how to study the TeX source code:

• Start at the beginning: Read comments and familiarize yourself with the index.
• Set specific problems: Look up TeX primitives (like \def) in the index to trace their history and internal representation.
• Peruse the index: Use it to navigate the report and understand the notation.
• Get familiar with the notation: Make the pages "black on the edges" by actively engaging with the code.

The discussion highlights the complexity and subtlety of TeX's internal mechanisms, particularly regarding scope management, equivalence saving and restoring, and garbage collection, emphasizing that these are crucial for the program's correctness and efficiency.