0Stanford Lecture: The Internal Details of TeX82 - Session 5 (July 29, 1982)

Key Concepts

• TEX Syntax: The process of reading input and determining the next action.
• get_next: The core subroutine responsible for fetching the next token of input.
• Token: A fundamental unit of input, consisting of a command code and a character part, potentially with a control sequence pointer.
• EQTB (Equivalence Table): Stores macro definitions and other equivalences.
• Control Sequence: A command starting with a special character (e.g., backslash) followed by an identifier.
• Hash Table: Used for efficient lookup of control sequences.
• State: A variable indicating the current input context (e.g., tokenlist, external file).
• Buffer: An internal storage area for input characters.
• loc, limit: Pointers within the buffer indicating the current position and the end of the current line.
• check_interrupt: A mechanism for interrupting TEX execution.
• cur_chr, cur_cmd: Variables holding the current character and its command code.
• ch_code: A macro to retrieve the command code for a character from EQTB.
• State Machine (for skipping blanks): Three states (midline, new line, skipping blanks) to handle whitespace.
• Token List: An internal sequence of tokens, used for macro expansion, output routines, etc.
• get_nc.token: A subroutine that fetches the next token and expands macros or marks.
• get_token: A subroutine that fetches the next token without expanding macros.
• nc.token: Similar to get_nc.token but used in specific inner loop scenarios.
• Basic Scanning Subroutines: Higher-level routines for parsing specific constructs like integers, dimensions, and keywords.
• scan_left_brace: A subroutine to ensure a left brace is encountered.
• scan_keyword: A subroutine to recognize specific keywords in the input.
• scan_int: A subroutine to parse integer numbers, supporting octal and signed values.
• scan_dimen: A subroutine to parse dimension values, handling units and potential infinity.
• scan_glue: A subroutine to parse glue specifications (dimension + optional stretch/shrink).
• "the" construct: A TEX feature to fetch values from internal tables.
• cur_val, cur_val_level: Global variables to store the result of scanning operations.
• Machine Independence: Designing TEX to produce consistent results across different systems.
• Scaled Points: The internal unit for dimensions in TEX.
• mu: Math units used in math mode.
• fil, fill, filll: Infinite glue specifications.
• Recursive Procedures: Procedures that call themselves or each other (e.g., scan_int and scan_the).
• Labels and goto statements: Used for control flow, particularly in the inner loop for efficiency.
• Web System: The documentation and programming system used for TEX.

Summary of TEX Internal Processing: Syntax and Scanning

This lecture focuses on the "guts" of TEX, specifically the syntax and scanning routines, which are responsible for reading input and preparing it for semantic processing. The overarching goal of syntax is to deliver necessary information to the semantic routines in the form of a command code and a character part (often referred to as chr), along with a cs_pointer if the input was a control sequence.

1. The get_next Subroutine: The Input Fetcher

The core of input processing lies in the get_next subroutine (module 317). While seemingly simple, its job is complex, involving:

• Macro Expansion: Handling macro calls and retrieving their expanded content.
• Argument Reading: Processing arguments passed to macros.
• Control Sequence Recognition: Identifying and looking up control sequences in the hash table.
• Prompting for Input: Requesting input when it's not immediately available.
• End-of-File Handling: Managing the closure of input files.

Historically, get_next was the catalyst for the WEB documentation system, serving as an early test case for structuring code and documentation.

Internal Mechanics of get_next:

• State Management: get_next relies on several state variables, including:
  • state: Indicates the input source (e.g., tokenlist from internal TEX structures, or an external file).
  • loc: The current position within the input buffer.
  • limit: The end of the current line in the buffer.
• Input Branches:
  • External File Input (Module 319): If loc is less than or equal to limit, characters are read directly from the buffer. If loc exceeds limit, it signifies the end of a line, prompting a move to the next line or a restart if no more lines exist. This is also a point where check_interrupt is called.
  • Token List Input: If state is tokenlist, input is drawn from an internal token list, which can represent various sources like output routines, macros, or inserted tokens.
• Character Processing:
  • cur_chr is set to the character at buffer[loc].
  • loc is incremented.
  • cur_cmd is determined by ch_code(cur_chr), which retrieves the command code from the EQTB (Equivalence Table).
• State Machine for Whitespace: A crucial part of get_next is a state machine (module 320) that handles skipping blanks based on three states: midline, new_line, and skipping_blanks. This is implemented as a large case statement for efficiency.

The get_next routine is part of the inner loop of TEX, where most of the processing time is spent. The speaker estimates around 100 machine instructions per character of text.

2. Token Handling Routines: get_nc.token, get_token, and nc.token

While get_next is fundamental, other routines provide more specialized token fetching:

• get_nc.token (Non-Call Token): This routine is similar to get_next but ensures that the returned token is not a macro or a mark that needs further expansion. It also sets cur_tok, a packed representation of cur_cmd, cur_chr, and cs_pointer, which is useful for storing or backing up tokens. get_nc.token handles undefined control sequences by issuing an error and fetching the next valid token.
• get_token (Module 339): This routine fetches the next token without expanding macros. This is essential when building definitions, as expanding a macro during definition would be incorrect. It uses a flag no_new_control_sequence to control whether new, undefined control sequences are added to the hash table.
• nc.token: A specialized version of get_nc.token used in the inner loop when a macro is unexpectedly encountered after get_next was called.

3. Basic Scanning Subroutines: Parsing Higher-Level Constructs

These routines parse more complex input elements:

• scan_left_brace (Module 363): Ensures that the next non-blank, non-call token is a left brace. If a space is encountered, it continues scanning until a non-space character is found. If a left brace is still missing, it inserts one and reports an error with a helpful message.
• scan_keyword: Recognizes specific keywords (e.g., "plus", "minus", "for") in the input, allowing for case-insensitive matching. It backtracks if the keyword is not found.
• scan_int: Parses integer numbers. It supports:
  • Decimal notation (e.g., 123).
  • Octal notation (prefixed with an apostrophe, e.g., '12 which is 10 in decimal).
  • Signed integers (with + or -).
  • Fetching values from TEX registers (e.g., \count5).
  • The "the" construct (in TEX82, not present in current TEX) to fetch values from internal tables. The result is stored in cur_val.
• scan_dimen (Module 400): Parses dimension values. It handles:
  • Units like points, inches, centimeters, etc.
  • The mu unit for math mode.
  • Infinite glue (fil, fill, filll) when preceded by plus or minus.
  • The "the" construct to fetch dimensions from internal tables. It stores the result in cur_val as a scaled quantity (2 to the power of -16th points) and uses cur_val_level to indicate whether an integer, dimension, or glue was parsed.
  • Parameters to scan_dimen:
    • mu: Boolean, indicates if mu units are allowed.
    • inf: Boolean, indicates if infinite glue is allowed.
    • shortcut: Boolean, used when part of the dimension has already been scanned.
  • Machine Independence: scan_dimen is carefully designed to ensure machine independence by performing fixed-point arithmetic within 32-bit limits and checking for overflow.
  • Unit Conversion: It includes logic to convert various units (e.g., inches) to points using a defined conversion factor (72.27/100 for inches to points).
• scan_glue (Module 413): Parses glue specifications, which consist of a dimension followed by optional plus and minus dimensions for stretchability and shrinkability. It utilizes scan_keyword and scan_dimen.

4. The "the" Construct and Recursive Scanning

The "the" construct is a powerful feature that allows fetching values from various internal TEX tables. This leads to mutually recursive procedures, where scan_the might call scan_int or scan_dimen, and vice versa. This recursion is safe because it always progresses further into the input, preventing infinite loops.

5. Error Handling and Help Messages

The lecture highlights the design of error messages and help messages in TEX.

• Help Messages: These are designed to be informative and user-friendly, often using first-person ("I" and "you") to create a more conversational tone. They are limited to 60 characters per line and aim to provide explanations in different terms than the primary error message.
• back.error: A routine that puts the current token back into the input stream so it can be re-read, useful for error recovery.

6. Programming Philosophy and Efficiency

The speaker defends the use of global variables and goto statements in the inner loop of TEX for performance reasons.

• Global Variables: While generally discouraged, they are used in TEX to avoid the overhead of passing parameters repeatedly in performance-critical sections.
• Labels and goto: Used extensively in the inner loop to achieve efficiency that might be lost with more structured control flow constructs in Pascal. The speaker believes this approach makes the code more readable and faster.
• Module Structure: The code is organized into modules, with labels defined at the beginning of subroutines and used for common control flow patterns like exit and continue.

Conclusion

The lecture delves into the intricate workings of TEX's syntax and scanning mechanisms, emphasizing the get_next subroutine as the primary input handler. It details the various token fetching routines and the sophisticated parsing capabilities of basic scanning subroutines like scan_int, scan_dimen, and scan_glue. The discussion also touches upon the design philosophy behind TEX, prioritizing efficiency and machine independence, even at the cost of some conventional programming practices. The recursive nature of scanning and the careful design of error handling are also key takeaways.