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

Key Concepts

• TeX Module Breakdown: TeX is composed of approximately 1,200 modules, with an estimated 100 bytes of code per module.
• Input Files: TeX reads three types of input files: user source text (Pascal text file), font information (TFM file), and initialization/format files (FMT file).
• FMT File: A format file stored in memory words, not intended for transfer between computers.
• TFM File: A font information file in 8-bit bytes.
• TeX's "Eyes and Mouth": The part of TeX that reads user text files and handles macros.
• Syntax Module: Responsible for parsing input, managing input levels (e.g., nested file inclusions, macro expansions), and recognizing tokens.
• Alignment Program: Contributes to syntax processing.
• Local Variables/Grouping: TeX manages local variables and grouping, with the equivalence table storing counts, dimensions, skips, and pointers to control sequence definitions.
• Text Output: Handles output to terminals, transcript files, or send files.
• Semantics: Processes the input information, with a significant portion dedicated to math formatting.
• Math Formatting: Includes routines for constructing boxes (h-box), handling glue, and building M-lists (math lists).
• H-lists and V-lists: Horizontal and vertical lists used in semantics.
• Dynamic Memory: Where most of TeX is stored; allocation and deallocation are handled here.
• Optimization Routines: Used for breaking lists into lines or pages (paragraph breaking).
• Hyphenation: A module that assists paragraph breaking, but does not directly interact with other modules except for paragraph breaking.
• Page Builder: Asynchronously gathers content for output.
• DVI File Output: Generates output in the DVI (Device Independent) file format.
• Font Information Reader: Reads font data.
• Memory Requirements: TeX's total size is estimated to be between 350,000 and 600,000 bytes, plus Pascal runtime. Dynamic memory can be around 100k bytes for fair typesetting.
• String Handling: TeX uses a custom string mechanism due to Pascal's limitations.
• Pool File (tex.pool): Generated by Tangle, it contains all strings used by TeX. Each line starts with the string length, followed by the string content.
• String Pool Checksum: A special number at the end of the pool file to verify its integrity.
• Pool Type Program: A utility to display the contents of a pool file.
• Character Sets and Internal Codes: TeX uses internal character codes, which can be mapped from external character sets (like ASCII or SAIL's). System-dependent changes are made to handle different character sets.
• TeX Internal Codes: Used in DVI files as character numbers and in checode statements.
• String Pool Array (str.pool): A packed array storing visible characters (ASCII 0-127).
• String Start Array (str.start): A directory into the string pool, indicating the starting position of each string.
• String Vacancies: A compile-time parameter for unused space in the string pool.
• Control Sequences: Multi-letter control sequence names are stored in the string pool.
• Printing Routines: Flexible procedures (print, print.char, print.line) that can direct output to various destinations (terminal, transcript file, string pool).
• Pseudo Printing: A technique for displaying context around errors by using a circular buffer.
• xchr Array: Used for system-dependent character code conversions.

TeX Program Organization and Size

Donald Knuth begins by providing an overview of the TeX program's structure, estimating it to consist of roughly 1,200 modules. He visualizes this breakdown using a diagram, where code is represented by lines and large data tables by areas outside these lines. His estimate of 100 bytes of code per module suggests that 10 modules equate to 1 kilobyte. The diagram indicates that approximately 140 modules are dedicated to syntax.

Knuth also attempts to illustrate the inter-module communication, though acknowledging the diagram's limitations in reflecting all constraints. The organization is further explained by detailing the three types of input files:

1. User Source File: A standard text input file.
2. Font Information: TFM (Teletype Font Metric) files, which are 8-bit byte files.
3. Initialization/Format File: FMT (Format) files, stored in memory words and specific to a local TeX installation. These are generated by TeX and read by other versions.

The "eyes and mouth" of TeX are described as the components that read the user's text file and process defined macros, which are often fed by the FMT file. The syntax module is crucial for interpreting these inputs, managing input levels, and tracking nested file inclusions or macro expansions.

Knuth quantifies the program size allocated to different functions:

• Macros: A significant portion of the program is dedicated to reading and defining macros.
• Text Input: Roughly the same amount of program is used for inputting text from files, including terminal input and handling error messages. Input buffers are relatively small (around 0.5k).
• Alignment: A dedicated program for alignment contributes to syntax.
• Local Variables/Grouping: Program code for managing local variables and grouping, which are associated with right braces and involve saving/restoring equivalences. The equivalence table stores counts, dimensions, skips, parameter values, codes, and pointers to control sequence definitions.
• Text Output: Approximately 40 modules are for text output to terminals, transcript files, or send files.
• Semantics: This is the core processing of input. A large part is for math formatting, with other sections handling non-math aspects like constructing boxes (h-box) and managing glue.
• Math Mode Routines: Build M-lists (math lists), distinct from the H-lists and V-lists built by other semantic routines.
• Dynamic Memory: This is where most of TeX's data resides. A substantial amount of code is devoted to managing this memory, including routines for displaying its contents.
• Optimization Routines: These routines, including paragraph breaking, are activated after a list is gathered to find the best way to break it into lines or pages. They interact with the hyphenation module.
• Hyphenation: A specialized module that only communicates with the paragraph breaking module.
• Page Builder: Asynchronously sends content for output when sufficient data is gathered.
• DVI File Output: The program for generating DVI files is relatively small, with many modules containing comments about DVI files.
• Font Information Reader: A module dedicated to reading font data.

Regarding data tables, Knuth notes:

• Hyphenation Tables: Occupy a certain amount of space.
• Equivalence Table: Takes up roughly the same space as hyphenation tables for registers.
• Font Information: Requires more space than hyphenation tables.
• Strings: A slightly smaller space requirement than font information.

Knuth estimates the total code size to be around 260k bytes. However, he adds the dynamic memory as a significant component, estimating it to be about half the size of the code, or around 100k bytes for fair typesetting. This brings the total size of TeX to be between 350,000 and 600,000 bytes, depending on the Pascal runtime system. He concludes that half a megabyte is sufficient for good typesetting, with a bit more being comfortable.

String Handling in TeX

Knuth then shifts focus to string handling, highlighting Pascal's limitations in this area. He explains that TeX developed its own string mechanism, initially inspired by Luis Pardo's work on an earlier TeX version. This custom approach, he states, turned out to be a "blessing in disguise," solving many problems more effectively than if Pascal's built-in strings had been used.

The Pool File and its Structure

The output of the tangle program, which translates WEB code into Pascal, is a pool file (e.g., tex.pool). This file has specific characteristics:

• Line Length: Maximum of 72 characters per line due to restrictions in weave (the program that generates TeX documentation).
• String Format: Each string appears on its own line.
• Length Prefix: The first two characters of each line indicate the length of the string.
• String Pool Checksum: The last line of the file is a special checksum number. If any string is modified, this number is likely to change, allowing verification of the pool file's integrity. This checksum can be referenced in the WEB program to confirm the correct string pool has been loaded.

Knuth emphasizes that the pool file is not meant to be manually edited. If edited without updating the checksum, TeX might produce garbled output due to out-of-sync strings.

The Pool Type Program

To make the pool file more readable, a utility program called Pool Type is used. This program processes the pool file and outputs its contents in a more understandable format. Knuth demonstrates running this program, showing how it can reveal the strings within the pool.

Character Sets and Internal Codes

A significant portion of the discussion revolves around character sets and TeX's internal character codes.

• Internal Codes: TeX uses a standard set of internal codes for characters. These codes are what get written into the DVI file as character numbers within a specific font.
• External vs. Internal: When TeX reads input from external files (e.g., ASCII, EBCDIC), it converts these characters to its internal codes. On output, it converts back. This ensures consistency within TeX.
• System-Dependent Changes: Different computer systems and character sets (like SAIL's) require system-dependent modifications. The xchr array is central to these conversions.
• Visible vs. Non-Visible Characters: TeX distinguishes between visible characters and control characters (like tab, line feed). Non-visible characters are often represented using escape sequences (e.g., ^^I for tab) or specific symbols.
• character k cannot be printed Module: This module (number 49 in the WEB code) determines which characters are considered non-printable. This setting can be system-dependent. For example, at MIT, certain characters like escape codes and form feeds might be considered non-printable.
• checode Statements: These statements use internal codes, and a reverse apostrophe operator (') can convert a character to its TeX internal code number (e.g., 'A equals 65).
• SAIL's Unusual Code: Knuth recounts how SAIL's character code at Stanford diverged from standard ASCII due to a historical modification, leading to issues like the right brace being in a different position.
• Mapping Foreign Characters: Knuth suggests mapping characters from alphabets with more than 26 letters into codes less than 40 (octal) for easier international exchange.

String Pool Data Structure

The internal representation of strings in TeX is detailed:

• str.pool: A large array (packed array of ASCII code) that stores the actual characters of the strings. Only visible, printable characters (7-bit ASCII, 0-127) are stored here.
• str.start: An array that acts as a directory to str.pool. For each string number k, str.start[k] gives the index in str.pool where string k begins.
• String Length: The length of string k is calculated as str.start[k+1] - str.start[k]. This eliminates the need for a separate "string end" array.
• String Vacancies: A compile-time parameter that reserves space for future strings, such as error messages, help texts, font names, and control sequence names.
• Control Sequence Names: Multi-letter control sequence names are stored directly in the string pool, a significant advantage over older systems that required separate tables. This unified approach simplifies printing and management.
• String Allocation: Strings are generally added to the end of the pool. While strings are usually not removed, the last one read in can sometimes be deleted.

String Handling Subroutines

Several subroutines are used for string manipulation:

• flush (module 44): Destroys the most recently made string.
• string_room (module 44): Checks if there is enough space in the string pool for a string of a given length. If not, it triggers an "TeX memory capacity exceeded" error, indicating that the pool_size compile-time parameter needs to be increased.
• pool_size: A compile-time parameter defining the maximum capacity of the string pool.
• string_vacancies: Another compile-time parameter specifying the minimum amount of free space to maintain in the string pool.

Knuth explains that the custom string implementation provides greater flexibility and efficiency compared to using Pascal's built-in string features, avoiding overhead and memory bloat.

Printing Routines and Destinations

The printing routines in TeX are designed to be highly flexible:

• Destinations: The print procedure can direct output to various destinations, including the terminal, the error transcript file, send files, or even back into the string pool itself (to create new strings).
• print.line and print.char: These are the fundamental printing procedures. print.char takes a TeX internal character code and sends it to the selected destination.
• xchr Array: This array is used within print.char to perform system-dependent conversions from TeX's internal character codes to the codes expected by the output device (e.g., EBCDIC). The setup of xchr is discussed in the "The Character Set" section.
• Pseudo Printing: Used for displaying error contexts. It employs a circular buffer (around 60 characters) to show relevant parts of the input, especially when dealing with large macro expansions. Printing is temporarily halted after a key point to avoid excessive buffer filling.
• print_s (module 58): A procedure to print a string. Knuth explains a change he made to accept an integer parameter (s) instead of a string number. This was to allow debugging routines to print any memory location as a string, even if memory was corrupted, preventing the program from crashing. If s is out of range, it defaults to string 0, which is represented as ^^@ (an up arrow followed by an at sign), serving as an error indicator.

Knuth concludes by reiterating that the homemade string handling and flexible printing routines were crucial for TeX's development, offering advantages over relying on Pascal's built-in features. He emphasizes that these custom solutions, while initially a struggle, ultimately proved to be a significant benefit.