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

Key Concepts

• Memory Word: The fundamental unit of memory in TeX, a Pascal variant record designed to efficiently store different data types.
• Variant Record: A Pascal data structure that can hold different types of data within the same memory location, with a tag to indicate the current type.
• Packed Record: A Pascal record that is optimized for space by packing its fields as tightly as possible.
• Scaled Quantity (sc): An integer that represents a physical distance with units, where 2^16 scaled points equal one point.
• Glue Ratio: A real number used to determine how much glue (space) in a box should stretch or shrink.
• Two Halves: A memory word structure that divides the word into two halves, typically a right half (rh) and a left half (lh), or two quarter words.
• Four Quarters: A memory word structure that divides the word into four quarter words (B0, B1, B2, B3).
• Min/Max Quarter Word/Half Word: Constants defining the range of values that can be stored in quarter and half words, crucial for memory packing and portability.
• Memory Base (mem base) / Memory Max (mem max): The start and end addresses of the main memory array in TeX.
• High Memory Base (high mem base): A boundary that divides memory into two areas: one for one-word records and one for multi-word records.
• Dynamic Memory Allocation: The process of allocating memory as needed during program execution, managed by TeX's custom memory management system.
• Avail: A pointer to the first available free memory word in the one-word node area.
• Mem End: A pointer to the highest memory location that has been used.
• Runaway Procedure: An error handling procedure called when memory allocation fails, often due to missing braces in macros.
• Circular Doubly Linked List: A data structure used for managing free variable-size memory blocks, where each free block points to the next and previous free block, forming a circle.
• Node Types: Different categories of data structures used in TeX, such as hlist nodes, vlist nodes, box nodes, glue nodes, etc., each with specific fields and purposes.
• Info Field: The left half (lh) of a one-word node, typically storing a token or type information.
• Link Field: The right half (rh) of a one-word node, used as a pointer to the next node in a list.
• L Link / R Link: Fields in the second word of a multi-word node, used for linking.
• Whatsit Node: A node type used for extensions and special purposes in TeX.

Personal Reflections on Publishing the Program

The speaker shares a personal anecdote about learning programming by reading others' code. He hopes that publishing this program will inspire young people to write their best software, whether by providing a model of good code or by motivating them to improve upon less ideal examples. He is unsure if the program will be used in a formal curriculum or for self-study but emphasizes his goal of inspiring high-quality software development.

Data Structures: Boxes and Glue

This section delves into the core data structures used in TeX for representing horizontal and vertical lists, which are composed of boxes, glue, and other elements. A significant portion of TeX's dynamic memory is dedicated to storing these structures.

Memory Word Structure

• Definition: Each item addressed in the memory array is a memory word, implemented as a Pascal record (specifically, a variant record).
• Pascal Compiler Importance: The efficiency of memory usage heavily relies on the Pascal compiler's ability to pack memory word correctly. A poor compiler can lead to a four-fold waste of memory.
• Variant Record Types: A memory word is a packed record with four primary variants:
  • int: For integers.
  • gr: For glue ratios (real numbers).
  • hh: For two halves.
  • qqqq: For four quarters.
• Fifth Type: sc (Scaled Quantity):
  • Used for representing physical distances with units.
  • An integer where the decimal point is 16 bits from the right edge (2^16 scaled points = 1 point).
  • Distinguished from int to provide a comment to the reader about its intended meaning, though Pascal itself doesn't see this distinction.
• Integer Size: TeX limits user-provided integer constants to the range of 32-bit signed integers (-(2^31) to 2^31 - 1). Larger integers can arise from arithmetic operations and may overflow on smaller machines. The program is designed to work on 32-bit machines.
• Glue Ratio (gr):
  • Defined as real in this implementation.
  • Used to determine the proportion by which glue stretches or shrinks in a box.
  • The speaker chose real for glue ratios because their computation only affects the final output (DVI file) and doesn't impact TeX's decision-making process, thus avoiding machine-dependent floating-point arithmetic issues that could lead to different typesetting results.
  • A reference is provided to a TUGboat article (Vol. 3, 1982, pp. 10-27) for implementing glue ratio calculations using fixed-point arithmetic on microcomputers without good floating-point support.
• Two Halves (hh):
  • A packed record with a rh (right half) and either an lh (left half) or two quarter words (B0, B1).
  • The rh is always a half word.
  • This structure is commonly used, particularly in the upper part of the mem array.
• Four Quarters (qqqq):
  • A structure consisting of four quarter words (B0, B1, B2, B3).
  • The packing of quarter words depends on the machine's architecture (e.g., 0-255 for some, -128 to 127 for others).
• Portability and Customization:
  • quarter word and half word are defined as subranges (min quarter word to max quarter word, min half word to max half word) to allow for redefinition and ensure portability across different Pascal compilers and machines.
  • The program checks specific conditions on these constants to ensure correct packing and prevent errors. These conditions are listed in module 106 and include:
    • min quarter word must be 0 or negative.
    • max quarter word must be at least 127.
    • min half word must be 0 or negative.
    • max half word must be at least the largest 15-bit number.
    • Quarter words must be storable in half words.
    • Memory addresses (mem base, mem max) must fit within half words.
    • Internal font numbers must fit within quarter words.
    • Other values like save size and input buffer size must fit within half words.
• Macros for Packing/Unpacking: To optimize performance, especially in the inner loop of TeX, macros like QI (quarter in) and QO (quarter out) are used for adding and subtracting min quarter word when packing/unpacking values. This avoids redundant operations if min quarter word is 0.

Debugging and Memory Inspection

• TeX Debugger: A built-in debugger is available when TeX is compiled with a debug switch.
• Secret Option 'D': Typing 'D' after an undefined control sequence (when in error stop mode) activates the TeX debugger.
• Debugger Commands: The debugger provides a prompt (#) and various commands, including:
  • 11: Checks memory for linked list integrity.
  • 1 n: Prints memory word at location n.
• print memory word Command: This command displays a memory word in all its possible interpretations (integer, scaled, glue ratio, two halves, four quarters), illustrating how the Pascal compiler packs data.
• "Dirty Pascal": The speaker mentions using "dirty Pascal" (reading a memory word in a different format than it was stored) in the debugger as a last resort for inspection. However, he notes that the Pascal debugger itself can provide similar information more conveniently.

Format File (.FMT)

• The format file, which stores strings, macros, and font information for quick preloading, is composed entirely of memory words. This is why .FMT files are not generally readable across different machine architectures.

Memory Layout and Allocation

• mem Array: The primary dynamic memory area, ranging from mem base to mem max.
• high mem base: Divides mem into two regions:
  • Below high mem base: Used for records requiring two or more words (e.g., boxes, paragraph nodes).
  • Above high mem base: Used exclusively for one-word records (e.g., macros, character nodes).
• Custom Memory Management: TeX does not use Pascal's heap; instead, it implements its own memory management for greater control, portability, and efficiency.
• One-Word Nodes: Stored above high mem base. The rh part is the link, and the lh part contains a token or a 16-bit representation of a macro definition token.
• Multi-Word Nodes: Stored below high mem base.
• Memory Overflow Example: The speaker recounts an instance where printing a 430-page book caused a memory overflow below high mem base due to the creation of large break nodes for index entries related to the word "type."
• TeX82 Improvements: Paragraph nodes were reduced in size from 10 to 3 words, and they are generated less often, reducing memory pressure below high mem base.
• Compile-Time Constants:
  • mem max can be changed at compile time without affecting the .FMT file.
  • high mem base is a critical compile-time constant. Changing it requires recompiling TeX and regenerating the .FMT file because the .FMT file relies on high mem base for loading macros and other memory computations.
  • Other constants like hash size, number of fonts, parameters, buffer size, and string pool size can be changed without recompiling TeX, and the .FMT file will still work.
• Fixed vs. Dynamic Locations:
  • Fixed Locations: A few words at fixed addresses within mem are reserved for frequently needed items like specifications for fill glue (e.g., hfill) and heads of lists. These are typically one-word nodes.
  • Dynamic Locations: The rest of the memory is dynamically allocated.
• One-Word Node Allocation (Above high mem base):
  • Uses a free list managed by avail (pointer to the first available word) and mem end (highest used location).
  • When a new word is needed, avail is used. If avail is null, mem end is incremented. If mem end reaches mem max, the runaway procedure is called.
  • Recycled nodes are added to the front of the avail list.
  • null is defined as mem base (the address of the first word in memory), which also happens to be where 0 glue is stored.
  • The get avail function allocates a single word node.
  • The free avail macro returns a node to the free list.
• Variable-Size Node Allocation (Below high mem base):
  • Uses a circular doubly linked list of free cells.
  • Available blocks are flagged by having max half word (all 1s) in their first word's link field, followed by the size of the free area.
  • When allocating, the algorithm searches for a free block large enough. It also checks the next block to see if it's also free and merges them if possible (collapsing adjacent free blocks).
  • If a block is exactly the right size, it's allocated.
  • If a block is too large (more than 1 word larger than needed), the top part is allocated, and the size of the remaining free block is reduced.
  • A key restriction for implementing extensions is to ensure the link field in the first word of any allocated block can never be max half word.

Node Structure and Fields

• One-Word Nodes:
  • info field (lh): Token or type information.
  • link field (rh): Pointer to the next node.
• Multi-Word Nodes:
  • l link and r link: Fields in the second word, referring to the info and link parts of the second word.
• Distinguishing Node Types:
  • Address-Based Distinction: If a pointer's address is above high mem base, it's known to be a one-word node containing font and character information (stored in B0 and B1 of the two halves structure).
  • Type and Subtype Fields: For nodes below high mem base, a type field (up to 256 possibilities, ~30 used) indicates the kind of node (e.g., hlist, vlist, box, glue). A subtype field provides further information.
• Common Node Types:
  • hlist node, vlist node, root node
  • ins node (insertion nodes)
  • marked node
  • adjustment node (for V adjust operation)
  • ligature node
  • discretionary node
  • whatsit node (type 8, for extensions, subtype indicates specific type)
  • math node (begins/ends math formulas)
  • glue node (pointer to glue specification)
  • current node
  • penalty node
  • set node
• Displaying Nodes: The program includes routines for displaying nodes symbolically, which also serve as examples of how to access data structures correctly using macros. This is crucial for understanding the internal representation of boxes and glue.
• Box Node Fields:
  • Width: mem of that plus width offset.sc (scaled number).
  • Depth, Height, Shift Amount: Explained in subsequent words.

Conclusion

This session provides a deep dive into TeX's memory management and data structures, focusing on the memory word as the fundamental unit. It explains how different data types are packed, the importance of compiler optimization, and the design choices made for portability and efficiency. The distinction between one-word and multi-word nodes, the dynamic allocation strategies for both, and the various node types used to represent typesetting elements are detailed. The speaker emphasizes the role of these low-level structures in enabling TeX's complex typesetting capabilities.