Stanford Lecture: The Internal Details of TeX82 - Session 12 (July 30, 1982)

Key Concepts

• DVI (DeVice Independent) File Format: A file format used by TeX to represent typeset documents, independent of the output device.
• Initex: A version of TeX used for generating format files. It includes all TeX primitives and can load macros and define hyphenation patterns.
• Virtex (Virgin TeX): A production version of TeX that is a "tabula rasa," meaning it has nothing preloaded and is designed for efficiency in typesetting.
• Format Files (.fmt): Files that contain preloaded macros, font information, and hyphenation patterns, allowing TeX to start up faster.
• Hash Table: A data structure used by TeX to store and quickly retrieve primitives and commands.
• String Pool: A memory area where strings used by TeX are stored.
• Packed Trie: A data structure used for efficient storage and retrieval of hyphenation patterns.
• Machine Independence: The ability of a file format or program to function correctly across different hardware and software environments.
• Rounding Error: In digital systems, the difference between the true mathematical value and its approximation due to finite precision. This is a significant issue in typesetting on low-resolution devices.
• Kerning: The adjustment of space between specific pairs of characters to improve visual appeal.
• Metafont: A program for creating fonts, designed to be machine-independent and capable of generating high-quality typefaces.
• Smoke Mode: A feature in Metafont for generating proofs of characters and their spacing, inspired by traditional font design methods.
• DVI Type: A proposed program for processing DVI files, aiming to address rounding issues on low-resolution devices.

DVI Version 2 and Postamble

The discussion begins with an update on the DVI file format. The official DVI version 2 now includes specific XXX commands (XXX1, XXX2, XXX3, XXX4) and the postamble instruction is numbered 243. The speaker notes a bug in the older definition of version 2 and advises against propagating it.

A key point raised is the utility of pointers connecting BOP (Beginning of Page) commands to the previous one. This allows for efficient skipping to specific pages within large DVI files, a common user request when only a particular page is needed. However, the speaker acknowledges that on systems like IBM Pascal, moving from the end of the file is not as convenient, leading some to write two postambles (one in the main file, one separate) for easier access. For shipping DVI files, the standard format with the postamble at the end is required.

Initializing a Working TeX Production System: Initex vs. Virtex

The core of the lecture focuses on initializing a TeX production system, differentiating between initex and virtex.

• Initex:

  • Generated when the init and [INAUDIBLE] switches in the program code are null.
  • Used for generating format files.
  • Loads all primitives into the hash table.
  • Loads all strings into the string pool.
  • Computes and packs hyphenation patterns into a packed trie.
  • These algorithms are commented out in production versions of TeX to avoid "deadwood."
  • Typically has smaller table sizes as it only needs to read macros, not execute them.
  • Hyphenation tables are increased in size because the number of patterns needed is unknown.

• Virtex (Virgin TeX):

  • Generated when the init and [INAUDIBLE] switches are brackets (escaped).
  • A production version of TeX, described as a "tabula rasa" or "clean slate."
  • Does not have anything preloaded.
  • Hyphenation tables are cut down as the required room is known from format packages.
  • Designed for efficiency in typesetting.

The speaker suggests using different change files to generate initex and virtex, differing only in a few ways, rather than editing a single change file back and forth. This is due to the lack of nested change files in the web system.

Generating and Using Format Files

The process of generating and using format files is explained:

1. Run initex:

   • initex reads in a format file (e.g., basic).
   • It loads fonts, defines hyphenation patterns, macros, and various codes (math, delimiter, UC, SF).
   • Delimiter codes are tied to fonts, defining character positions for operations like finding the next larger delimiter.
   • The basic format file is intended to contain everything that depends on fonts.
   • Historically, TeX had rigid relationships between delimiter positions in different fonts, which is now freed up and specified by tables in basic.

2. dump command:

   • After initex loads the format, the dump command is used.
   • This prints out messages indicating the creation of a .fmt file (e.g., basic.fmt with the date).

3. Running virtex:

   • When virtex starts, it says "This is TeX and no format preloaded."
   • Users then specify a format to load, e.g., basic.
   • virtex uses the .fmt file to load all the necessary information (fonts, etc.) much faster than loading individual TFM files.
   • The time to load primitives into the hash table is negligible.
   • Computing patterns takes about 8 seconds.
   • Loading TFM files can take around 15 seconds, and this is a significant saving.

Saving Core Images for Faster Startup

The concept of saving the "core image" of a running program is introduced for systems that support it.

• If a system allows saving the core image after loading a format (e.g., basic), this saved image can be called TeX.
• This saved TeX program assumes the basic format by default.
• This approach is even faster than using a linking loader.
• The user manual will distinguish between TeX primitives and extensions in the basic format.
• If a different macro package (e.g., AMS-TeX) is used, the saved core image would be named accordingly (e.g., AMS-TeX).
• Users would then run TeX, AMS-TeX, etc., rather than initex or virtex.

Initialization and the ready_already Flag

The internal workings of the Pascal program for initialization are detailed:

• A global variable ready_already is used.
• It's initialized to a specific constant (314159) when the program starts.
• This constant is chosen to be highly unlikely to occur coincidentally from a previous run.
• If ready_already equals this constant upon startup, the program assumes it's a saved core image and jumps directly into the main program.
• Otherwise, it proceeds with the full initialization procedure (prompting for format files, etc.).
• This mechanism is a "hack" that works on many systems, even if it breaks strict Pascal rules.
• Systems with strong protection against using uninitialized variables might require this protection to be turned off for this method to work.

Limitations of Initex and Debugging

• initex cannot load a format file directly. It always loads the string file and string pool.
• To debug initex when it needs to load a format file, the speaker uses a debugger to manually reset a variable format_ident to 0 at a specific point in the code. This bypasses the check that prevents initex from loading formats.
• The code to load format files exists but is inaccessible without this manual intervention.

End Game and Handling Unfinished Pages

The lecture then shifts to the "end game" of a TeX job and how to ensure all pages are outputted.

• dump vs. end: The dump and end commands share the same command code initially. However, at module 1203, they diverge. dump is intended for saving format files, while end is for final cleanup.
• Lost Pages: A common problem is losing pages, especially those with floating insertions that are carried over.
• build_page Procedure: In module 1204, build_page is called to empty contributions to the current page and call the output routine if necessary.
• Forced Page Break: A penalty of -10000 or less triggers a "shipout" (outputting the page).
• Handling Empty Pages: shipout does not occur on empty pages. The speaker checks if page_head equals page_tail (indicating nothing left on the page).
• Ensuring Output Routine Invocation: To guarantee the output routine is invoked, a null box with the correct width (H size) is put out, followed by an "eject penalty" (a forced break penalty). This ensures the page is considered non-empty.
• Avoiding Null Box Issues: Using a null box with the correct width is crucial. A null box with zero width can cause problems in multi-column layouts, leading to columns stretching incorrectly.
• Refining the Termination Condition: The speaker acknowledges a potential flaw in the page_head == page_tail test and plans to make it more complicated to also check if something was actually "shipped out."
• Vertical Lists and Page Building: The debugging of breaking vertical lists into pages (part 43) and the page builder (part 44) is highlighted as a "researchy" and complex part of TeX that is now in "fairly tight shape."

Rounding on Low-Resolution Devices

A significant portion of the lecture is dedicated to the problem of rounding errors on low-resolution devices and the solutions implemented.

• The Problem:

  • On high-resolution devices (e.g., 2 pixels per unit), font widths can be exact integers of pixels.
  • On lower-resolution devices (e.g., 1.8 pixels per unit for 9-point font), rounding is necessary.
  • Early TeX implementations rounded for every character, leading to "glitches" where the horizontal position shifted unpredictably, especially with kerning.
  • This made output look unsatisfactory, even for correspondence.

• Machine Independence vs. Device Dependence:

  • Font designers want machine-independent TFM files, but also need to tune letter widths for specific devices.
  • The goal is to have the cake and eat it too: machine independence with good output on various devices.

• Early Driver Approach: Some DVI drivers rounded only at the beginning of a word, which looked better than rounding every character. This allowed font designers to tune letter spacing within words.

• Kerning's Impact: Kerning, intended to improve spacing, actually exacerbated rounding problems. When a kern occurred, it caused a recalculation and a rounding glitch at that point, worsening the output quality.

• The Solution:

  • Round after large jumps: The DVI Type program rounds only after a "large jump" in horizontal or vertical direction.
  • Relative calculations for small jumps: For smaller movements, calculations are done relatively, sticking with pixel widths derived from the font or rounded character widths.
  • "Large jump" definition: A large jump is defined as a certain percentage of the current "em" in the font.
  • Horizontal Coordinates: Registers h and v store DVI units. Registers hh and vv store pixel values and are updated locally. hh is set to the rounded value of h only after a big jump.
  • Vertical Coordinates: The problem for vertical spacing was with fractions (like 1/2) and line-to-line spacing. The definition of a "big jump" ensures that vertical spacing is relative to something that would be rounded consistently.
  • Example: vv is set to round(v) after a big jump, but for small increments (v = v + a), vv is updated as vv + round(a). Rounding occurs during big jumps where the eye is less likely to notice the error.

• Metafont and Device Widths:

  • Metafont uses char_width (in points) and char_device_width (rounded pixels * width).
  • The char_device_width goes into the pixel file and influences character widths and sidebars.
  • Font designers can adjust the actual character width for finer tuning, even if it's not exactly the device width. For example, adjusting the width of 'M' by one pixel to achieve desired spacing.

• DVI Type Program: This solution is implemented in the DVI Type program, provided as a model for typesetting.

• Discussion on Error Accumulation: A user points out an alternative approach where the size of the indicated motion in DVI is compared with the accumulated error, and the error is picked up only when the motion is significantly larger than the error. This is contrasted with the fixed dimension approach.

• Kerning and Rounding Errors: The speaker admits to having to add extra words to text in the TeX manual to compensate for rounding errors that made the unkerned version appear in the correct position.

• Computer Modern Fonts: The speaker notes that the Computer Modern fonts were designed assuming a resolution of 252 to the inch, and kerns of half a unit would be about half a pixel, which could be noticeable.

Metafont and Future Plans

The lecture concludes with a discussion on Metafont and future plans.

• Metafont Development:

  • Plans include creating a new version of Metafont based on user experience and incorporating better ideas.
  • Experiments will be conducted with conics versus cubic splines, finding intersections between points.
  • ddraw efficiency: A significant improvement will be made to make ddraw (drawing between curves) with a pen size of 1 very efficient, especially for calligraphic fonts.
  • The current ddraw is inefficient, reducing the filling problem to a sequence of slow operations.
  • The new Metafont will use run-length representation of the raster instead of bit representation, using integer variables.
  • This will lead to better algorithms and memory usage (order n instead of n squared).
  • The language will be enhanced for arrays but not record structures, avoiding excessive complexity.

• Book Series: The speaker plans to write three books: "Computer Typography, Volume 1: TeX," "Volume 2: Metafont," and "Volume 3: Computer Modern Fonts." This will be their contribution to the field of typography.

• Font Design and Subtleties:

  • Metafont aims to capture the subtleties of font design in a precise language, moving beyond hand-waving.
  • The goal is to provide hooks for artists to indicate concepts and record the intelligence of font design, not just drawings.
  • Smoke Mode: A new mode in Metafont for generating proofs of characters and their spacing, mimicking traditional font design methods. This involves printing large versions of characters with corners to indicate design boundaries, allowing for visual assessment from a distance.
  • The importance of optical changes at different scales is highlighted, necessitating both large-scale design and testing at actual size.
  • A remark is made about a tool used at Mergenthaler: binoculars used backward to view typeset material from a distance.

• Outputting TeX for Online Viewing:

  • Plans exist for DVI to data disk and DVI to sun terminal at Stanford.
  • David Fuchs's thesis will focus on interactive versions of TeX for immediate feedback.
  • Experiments with outputting TeX to line printers have been successful in indicating bold and italic styles.
  • Users, after experience, can visualize typesetting results, but quick visualization is crucial for final polishing and ensuring fixes don't disrupt page layout.
  • The speaker emphasizes the need for more software to handle interactive editing and selective formatting of modules in a web system.

• Concluding Remarks: The speaker expresses excitement about the large number of people attending and understanding the complexity of the program, calling it "new territory." They also mention the challenge of keeping modules short and the existence of ragged bottom output in the weave output, which can be achieved with TeX.