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

Key Concepts

• Macro vs. Procedure Calls: Distinguishing between macro calls and procedure calls in code, with a suggestion for typographic symbols (e.g., subscripts for module numbers) to improve clarity.
• Paragraph Maker: The TeX module responsible for breaking horizontal lists into lines of appropriate size, handling ordinary paragraphs and displayed equations.
• State Variables: Key variables maintained by the paragraph maker, including mode, head, tail, space vector, and already (tracking lines set for a paragraph).
• Paragraph Shape: The ability to define custom shapes for paragraphs, requiring knowledge of the number of lines set.
• Displayed Equations: Treated as three lines of equal size, with the middle line being the largest. Equation numbers can occupy the first or last line.
• GELU Ratio: A measure indicating how much spaces are stretched or shrunk relative to their stretchability.
• Badness: A metric quantifying the undesirability of a line break, calculated as the cube of the GELU ratio multiplied by 100.
• Line Penalty: A parameter that penalizes each line break, influencing paragraph length.
• Demerits: The overall cost of a line break, calculated by combining badness, line penalty, and other penalties (e.g., hyphenation penalty).
• Feasible Breakpoint: A potential line break that does not violate specified tolerances.
• Tolerance: A parameter that limits the maximum acceptable badness for a line break.
• Shortest Path Problem: The underlying algorithmic problem solved by the paragraph maker to find the optimal sequence of line breaks.
• Active and Passive Nodes: Data structures used in the shortest path algorithm to track feasible breakpoints and the best paths to reach them.
• Delta Nodes: Used to manage relative distances and avoid floating-point arithmetic issues in calculating line lengths.
• Hyphenation: The process of breaking words at hyphenation points, with specific penalties and conditions.
• Overfull Boxes: An indicator of lines that exceed the available width, often a last resort in the second pass of the algorithm.
• Rivers: Large, undesirable spaces that can appear in justified text, particularly with high looseness settings.
• Page Builder: The module responsible for breaking paragraphs into pages, using a simpler badness calculation than the paragraph builder.

Paragraph Maker Algorithm and Metrics

1. Introduction to the Paragraph Maker

The discussion begins by highlighting a potential ambiguity in distinguishing macro calls from procedure calls in the system's syntax. A suggestion is made to use typographic symbols, such as subscripts indicating the module number where a macro is defined, to improve clarity.

The focus then shifts to the "paragraph maker," a crucial component of the TeX system responsible for formatting text into paragraphs. This module handles the process of breaking a horizontal list of words into lines of appropriate size, considering both ordinary paragraphs and displayed equations.

2. State Management and Paragraph Shapes

The paragraph maker relies on several state variables:

• Mode: The current operational mode.
• Head and Tail: Pointers to the beginning and end of the current text segment.
• Space Vector: Information about available space for stretching or shrinking.
• Already: A counter tracking the number of lines already set for a paragraph. This is particularly important for resuming paragraph formatting after a displayed equation or when dealing with hanging indentation, which can span multiple lines.

The concept of "paragraph shape" is introduced, allowing for customized paragraph layouts. This feature necessitates keeping track of the number of lines set, as it influences how the paragraph is shaped.

3. Handling Displayed Equations

Displayed equations are treated as three lines of equal size, with the middle line being the largest. The first and last of these three lines are typically blank, unless an equation number needs to be placed.

4. Quantifying Line Quality: Badness and Demerits

The core of the paragraph formatting algorithm lies in quantifying the quality of line breaks. This is achieved through a system of "badness" and "demerits."

• GELU Ratio: This ratio, displayed in the margin of example outputs, indicates how much a line's spacing has been stretched or shrunk relative to its "stretchability." A positive ratio means stretching, while a negative ratio indicates shrinking. For example, a GELU ratio of 0.305 means spaces are stretched by 30.5% of their stretchability.

• Badness: This metric measures the undesirability of a line break. In simple cases, it's calculated as the cube of the GELU ratio multiplied by 100. For instance, a GELU ratio of 0.7 would result in approximately 34.3 units of badness (0.7³ * 100). The scaling factor of 100 is arbitrary but ensures that badness rises rapidly as the GELU ratio increases, reflecting a preference for lines that are close to their natural spacing. The calculation is performed using precise integer arithmetic to ensure consistency across different TeX implementations.

• Line Penalty: An additional penalty applied to every line break, regardless of its spacing. In TeX82, this penalty can be adjusted; a higher line penalty makes TeX less likely to create longer paragraphs.

• Other Penalties: Specific penalties are added for certain types of breaks:

  • Hyphenation Penalty: Applied when a line break occurs at a hyphen. There are different penalties for discretionary hyphens (inserted by the hyphenation algorithm) and explicit hyphens (present in the original text).
  • Explicit Penalty: A penalty explicitly set by the user.

• Demerits: The total cost of a line break is calculated as "demerits." The formula for demerits is:

  • (Badness + Line Penalty + Other Penalties)²
  • However, if the total penalty is negative (e.g., a forced break with a negative penalty), the formula becomes: Badness² - Penalty². This adjustment prevents negative penalties from reducing the demerits excessively.

The goal of the paragraph maker is to find a sequence of line breaks that minimizes the total demerits for the entire paragraph.

5. Feasibility and Tolerance

Not all potential line breaks are considered feasible. A line break is deemed feasible if it can be achieved without violating certain "tolerances."

• Tolerance: This parameter limits the maximum acceptable badness for a line. If a line's badness exceeds the tolerance, it is not considered a feasible break. In TeX82, tolerance is given in units of badness. A tolerance of 200, for example, means no line with a badness greater than 200 will be accepted. This corresponds to a GELU ratio such that its cube multiplied by 100 is less than or equal to 200.

Feasible breaks are visually represented by blue lines in diagrams. The algorithm aims to find the shortest path through these feasible breaks, minimizing total demerits.

6. The Shortest Path Algorithm

The problem of finding the optimal line breaks is analogous to the shortest path problem in graph theory. Each feasible breakpoint represents a node in a graph, and the demerits between breakpoints represent the edge weights. A shortest path algorithm is then applied to find the sequence of breaks that minimizes the total demerits from the beginning to the end of the paragraph.

7. Algorithm Implementation: On-the-Fly Processing

The shortest path algorithm is not executed in separate passes. Instead, it's performed "on the fly" as the paragraph is processed. The system maintains a list of "active nodes" (feasible breakpoints) and dynamically updates them.

• Active Nodes: Represent potential breakpoints that are currently being considered.
• Passive Nodes: Store information about completed breakpoints and the best paths to reach them.

When a new potential breakpoint is encountered, the algorithm checks its feasibility against all active breakpoints. The best feasible path to the new breakpoint is then identified and becomes a new active node. Inactive nodes are moved to a passive list. This approach ensures that the algorithm considers the paragraph as a whole for optimal breaking.

8. The Bug in the First TeX Algorithm

A significant bug was discovered in the initial TeX algorithm. It occurred when the linewidth changed within a paragraph. The algorithm, by only storing the best path to a breakpoint without considering the line number, failed to account for alternative feasible paths that might become optimal with a different linewidth. This led to suboptimal or incorrect line breaks. The fix involved storing the best path for each combination of breakpoint and line number.

9. Advanced Demerits and Fitness Classes

The demerits calculation is further refined to include additional penalties:

• Double-Hyphen Demerits: A penalty for having two consecutive hyphenated lines.
• Final-Hyphen Demerits: A penalty if the second-to-last line of a paragraph is hyphenated.
• Adjacency Demerit: A penalty for incompatible line fitness (e.g., a tight line followed by a loose line).

To handle these complexities, the shortest path algorithm's vertices are extended to include not just the breakpoint and line number, but also the "fitness class" (tight or loose). This requires remembering the best way to reach a breakpoint for each combination of breakpoint, line number, and fitness class.

10. Data Structures: Active and Passive Nodes

The algorithm uses a data structure comprising active and passive nodes:

• Passive Nodes: Short, two-word structures that store information about feasible breakpoints, including a pointer to the breakpoint itself and the best previous node. They are recycled for available storage.
• Active Nodes: Longer nodes (three or four words) that store the total demerits to reach that point, the line number, fitness class, and a pointer to the breakpoint. They also point to the corresponding passive node.

11. Avoiding Floating-Point Arithmetic and Overflow

To improve precision and avoid issues like "infinity minus infinity" errors, TeX82 aims to eliminate floating-point arithmetic. This is achieved by keeping track of "relative distances" using delta nodes.

• Delta Nodes: These nodes store the difference between distances to consecutive breakpoints. This allows for calculating line lengths and badness without relying on absolute positions, thus preventing overflow issues with very long paragraphs.

The calculation of line length involves considering the distance "before" the end of one breakpoint and "after" the beginning of the next, accounting for the space between them. This is further complicated by discretionary breaks (like hyphens) and the addition of "left skip" and "right skip" for ragged right and centered text.

12. Hyphenation Algorithm and Two Passes

The hyphenation process is handled in two passes:

• First Pass (No Hyphenation): The algorithm attempts to find the best paragraph breaks without hyphenating any words. It explores all feasible breaks and maintains a list of active nodes. If the active list becomes empty, it means no feasible break was found without hyphenation.

• Second Pass (Hyphenation): If the first pass fails, the algorithm resorts to hyphenation. It considers hyphenating words that meet certain criteria (e.g., at least five letters long, not starting with an uppercase letter unless specified). Every word meeting these conditions is submitted to the hyphenation algorithm.

The efficiency of this approach is demonstrated by the fact that the second pass is rarely needed. For example, in "The Art of Computer Programming, Volume 2," only about 1.2 hyphenations per paragraph were required on average, with the second pass being invoked only once in twelve times.

13. Handling Overfull Boxes and Last Resorts

In the second pass, to prevent the active list from becoming empty (which would lead to losing track of potential breaks), the algorithm has a "last resort" mechanism. It allows for an "overfull box" to be created if no feasible break can be found. This is a deliberate choice to provide visual feedback to the user about how much the line is overfilled, allowing for manual correction. Setting a very high tolerance (e.g., 10,000) can prevent overfull boxes, but may result in underfull ones.

14. End of Paragraph Processing and Reconstructing the Paragraph

At the end of a paragraph, the algorithm reconstructs the optimal line breaks by tracing back through the passive nodes using back-links. These links indicate the best previous breakpoint for each node. The links are reversed to create a forward sequence of breakpoints, which are then used to break the horizontal list into lines.

15. Subtle Bugs and Edge Cases

The discussion highlights several subtle bugs and edge cases encountered during the development of TeX's paragraph breaking algorithm:

• Breakpoint Cancellation: A bug where breaking at a GELU node would incorrectly cancel out subsequent penalties, leading to errors.
• Overfull Box Logic: The logic for creating overfull boxes as a last resort in the second pass was particularly difficult to get right, requiring multiple revisions.
• Final Hyphen Penalty: A mysterious problem on a membership list was traced back to the final hyphen penalty, where a hyphenated last line was avoided due to this penalty.
• Discretionary Breakpoints: Properly defining the meaning of "beta" and "alpha" for discretionary breaks (like hyphens) required several iterations.

16. Page Building and Penalties

The output of the paragraph builder is a vertical list of boxes representing lines. The "page builder" then takes this list and breaks it into pages. This process is simpler than paragraph building, as it primarily considers "badness" and penalties, rather than demerits.

Various penalties are applied during page building:

• Widow Line Penalty: To prevent a single line from appearing at the bottom of a page.
• Display Widow Penalty: A specific penalty for starting a page with a displayed equation.
• Interline Penalty: Recommended for footnotes to penalize their inclusion.

17. Rivers and Their Avoidance

"Rivers," large white spaces that can appear in justified text, are generally avoided by the algorithm through good tolerance settings. However, they can emerge with high "looseness" settings or in specific scenarios like lists of short words. Eliminating rivers completely is theoretically an NP-complete problem. The algorithm does not explicitly address rivers, relying on good parameter settings to minimize their occurrence.

18. Hyphenation Conservatism

The speaker expresses a personal preference for conservative hyphenation, where the fragment of a word before the hyphen should be pronounceable. This influences the hyphenation algorithm's choices.

19. Module Structure and Efficiency

The paragraph breaking algorithm is organized into modules, with section 37 covering the try_break subroutine and delta node management, and section 38 continuing the process with final packaging. The algorithm is designed to be efficient, running in time proportional to the number of breakpoints multiplied by the number of active nodes, which is typically limited by the number of words in a line.

Conclusion

The lecture provides a deep dive into the sophisticated algorithm used by TeX for paragraph breaking. It emphasizes the intricate interplay of metrics like badness and demerits, the application of shortest path algorithms, and the careful management of data structures to achieve globally optimal paragraph formatting. The discussion also highlights the challenges of implementing such a complex system, including the discovery and resolution of subtle bugs and the continuous refinement of algorithms to handle various typographic requirements. The emphasis is on a precise, mathematically grounded approach to typesetting.