§1  TEX82  PART 1: INTRODUCTION 3

1. Introduction. This is TEX, a document compiler intended to produce typesetting of high quality. The Pascal program that follows is the definition of TEX82, a standard version of TEX that is designed to be highly portable so that identical output will be obtainable on a great variety of computers.

The main purpose of the following program is to explain the algorithms of TEX as clearly as possible. As a result, the program will not necessarily be very efficient when a particular Pascal compiler has translated it into a particular machine language. However, the program has been written so that it can be tuned to run efficiently in a wide variety of operating environments by making comparatively few changes. Such flexibility is possible because the documentation that follows is written in the language, which is at a higher level than Pascal; the preprocessing step that converts to Pascal is able to introduce most of the necessary refinements. Semi-automatic translation to other languages is also feasible, because the program below does not make extensive use of features that are peculiar to Pascal.

A large piece of software like TEX has inherent complexity that cannot be reduced below a certain level of difficulty, although each individual part is fairly simple by itself. The language is intended to make the algorithms as readable as possible, by reflecting the way the individual program pieces fit together and by providing the cross-references that connect different parts. Detailed comments about what is going on, and about why things were done in certain ways, have been liberally sprinkled throughout the program. These comments explain features of the implementation, but they rarely attempt to explain the TEX language itself, since the reader is supposed to be familiar with The TEXbook.

2. The present implementation has a long ancestry, beginning in the summer of 1977, when Michael F. Plass and Frank M. Liang designed and coded a prototype based on some specifications that the author had made in May of that year. This original protoTEX included macro definitions and elementary manipulations on boxes and glue, but it did not have line-breaking, page-breaking, mathematical formulas, alignment routines, error recovery, or the present semantic nest; furthermore, it used character lists instead of token lists, so that a control sequence like was represented by a list of seven characters. A complete version of TEX was designed and coded by the author in late 1977 and early 1978; that program, like its prototype, was written in the SAIL language, for which an excellent debugging system was available. Preliminary plans to convert the SAIL code into a form somewhat like the present “web” were developed by Luis Trabb Pardo and the author at the beginning of 1979, and a complete implementation was created by Ignacio A. Zabala in 1979 and 1980. The TEX82 program, which was written by the author during the latter part of 1981 and the early part of 1982, also incorporates ideas from the 1979 implementation of TEX in MESA that was written by Leonidas Guibas, Robert Sedgewick, and Douglas Wyatt at the Xerox Palo Alto Research Center. Several hundred refinements were introduced into TEX82 based on the experiences gained with the original implementations, so that essentially every part of the system has been substantially improved. After the appearance of “Version 0” in September 1982, this program benefited greatly from the comments of many other people, notably David R. Fuchs and Howard W. Trickey. A final revision in September 1989 extended the input character set to eight-bit codes and introduced the ability to hyphenate words from different languages, based on some ideas of Michael J. Ferguson.

No doubt there still is plenty of room for improvement, but the author is firmly committed to keeping TEX82 “frozen” from now on; stability and reliability are to be its main virtues.

On the other hand, the description can be extended without changing the core of TEX82 itself, and the program has been designed so that such extensions are not extremely difficult to make. The banner string defined here should be changed whenever TEX undergoes any modifications, so that it will be clear which version of TEX might be the guilty party when a problem arises.

If this program is changed, the resulting system should not be called ‘TEX’; the official name ‘TEX’ by itself is reserved for software systems that are fully compatible with each other. A special test suite called the “ test” is available for helping to determine whether a particular implementation deserves to be known as ‘TEX’ [cf. Stanford Computer Science report CS1027, November 1984].

define banner ≡ ´ ␣  ␣    ␣       ␣  ´  { printed when TEX starts }

4  PART 1: INTRODUCTION  TEX82 §3

3. Different Pascals have slightly different conventions, and the present program expresses TEX in terms of the Pascal that was available to the author in 1982. Constructions that apply to this particular compiler, which we shall call Pascal-H, should help the reader see how to make an appropriate interface for other systems if necessary. (Pascal-H is Charles Hedrick’s modification of a compiler for the DECsystem-10 that was originally developed at the University of Hamburg; cf. SOFTWARE—Practice & Experience 6 (1976), 29–42. The TEX program below is intended to be adaptable, without extensive changes, to most other versions of Pascal, so it does not fully use the admirable features of Pascal-H. Indeed, a conscious effort has been made here to avoid using several idiosyncratic features of standard Pascal itself, so that most of the code can be translated mechanically into other high-level languages. For example, the ‘with’ and ‘new ’ features are not used, nor are pointer types, set types, or enumerated scalar types; there are no ‘var’ parameters, except in the case of files; there are no tag fields on variant records; there are no assignments real ← integer ; no procedures are declared local to other procedures.)

The portions of this program that involve system-dependent code, where changes might be necessary because of differences between Pascal compilers and/or differences between operating systems, can be identified by looking at the sections whose numbers are listed under ‘system dependencies’ in the index. Furthermore, the index entries for ‘dirty Pascal’ list all places where the restrictions of Pascal have not been followed perfectly, for one reason or another.

4. The program begins with a normal Pascal program heading, whose components will be filled in later, using the conventions of . For example, the portion of the program called ‘⟨ Global variables 13 ⟩’ below will be replaced by a sequence of variable declarations that starts in §13 of this documentation. In this way, we are able to define each individual global variable when we are prepared to understand what it means; we do not have to define all of the globals at once. Cross references in §13, where it says “See also sections 20, 26, …,” also make it possible to look at the set of all global variables, if desired. Similar remarks apply to the other portions of the program heading.

Actually the heading shown here is not quite normal: The program line does not mention any output file, because Pascal-H would ask the TEX user to specify a file name if output were specified here.

define mtype ≡ t y p e { this is a coding trick: }

format mtype ≡ type { ‘mtype’ will be equivalent to ‘type’ }

format type ≡ true { but ‘type’ will not be treated as a reserved word } ⟨ Compiler directives 9 ⟩ program TEX ; { all file names are defined dynamically }

label ⟨ Labels in the outer block 6 ⟩

const ⟨ Constants in the outer block 11 ⟩

mtype ⟨ Types in the outer block 18 ⟩

var ⟨ Global variables 13 ⟩

procedure initialize; { this procedure gets things started properly } var ⟨ Local variables for initialization 19 ⟩ begin ⟨ Initialize whatever TEX might access 8 ⟩ end;

⟨ Basic printing procedures 57 ⟩

⟨ Error handling procedures 78 ⟩

5. The overall TEX program begins with the heading just shown, after which comes a bunch of procedure declarations and function declarations. Finally we will get to the main program, which begins with the comment ‘start here’. If you want to skip down to the main program now, you can look up ‘start here’ in the index. But the author suggests that the best way to understand this program is to follow pretty much the order of TEX’s components as they appear in the description you are now reading, since the present ordering is intended to combine the advantages of the “bottom up” and “top down” approaches to the problem of understanding a somewhat complicated system.

6. Three labels must be declared in the main program, so we give them symbolic names.

define start of TEX = 1 { go here when TEX’s variables are initialized } define end of TEX = 9998 { go here to close files and terminate gracefully } define final end = 9999 { this label marks the ending of the program }

⟨ Labels in the outer block 6 ⟩ ≡

start of TEX, end of TEX, final end ; { key control points }

This code is used in section 4.

7. Some of the code below is intended to be used only when diagnosing the strange behavior that sometimes occurs when TEX is being installed or when system wizards are fooling around with TEX without quite knowing what they are doing. Such code will not normally be compiled; it is delimited by the codewords ‘debug … gubed’, with apologies to people who wish to preserve the purity of English.

Similarly, there is some conditional code delimited by ‘stat … tats’ that is intended for use when statistics are to be kept about TEX’s memory usage. The stat … tats code also implements diagnostic information for and .

define debug ≡ { change this to ‘debug ≡ ’ when debugging } define gubed ≡ { change this to ‘gubed ≡ ’ when debugging } format debug ≡ begin format gubed ≡ end define stat ≡ { change this to ‘stat ≡ ’ when gathering usage statistics } define tats ≡ { change this to ‘tats ≡ ’ when gathering usage statistics } format stat ≡ begin format tats ≡ end

8. This program has two important variations: (1) There is a long and slow version called , which does the extra calculations needed to initialize TEX’s internal tables; and (2) there is a shorter and faster production version, which cuts the initialization to a bare minimum. Parts of the program that are needed in (1) but not in (2) are delimited by the codewords ‘init … tini’.

define init ≡ { change this to ‘init ≡ ’ in the production version } define tini ≡ { change this to ‘tini ≡ ’ in the production version } format init ≡ begin format tini ≡ end

⟨ Initialize whatever TEX might access 8 ⟩ ≡ ⟨ Set initial values of key variables 21 ⟩ init ⟨ Initialize table entries (done by only) 164 ⟩ tini

This code is used in section 4.

9. If the first character of a Pascal comment is a dollar sign, Pascal-H treats the comment as a list of “compiler directives” that will affect the translation of this program into machine language. The directives shown below specify full checking and inclusion of the Pascal debugger when TEX is being debugged, but they cause range checking and other redundant code to be eliminated when the production system is being generated. Arithmetic overflow will be detected in all cases. ⟨ Compiler directives 9 ⟩ ≡

$C−, A+, D− { no range check, catch arithmetic overflow, no debug overhead } debug $C+, D+ gubed { but turn everything on when debugging }

This code is used in section 4.

10. This TEX implementation conforms to the rules of the Pascal User Manual published by Jensen and Wirth in 1975, except where system-dependent code is necessary to make a useful system program, and except in another respect where such conformity would unnecessarily obscure the meaning and clutter up the code: We assume that case statements may include a default case that applies if no matching label is found. Thus, we shall use constructions like

case x of

1: ⟨ code for x = 1 ⟩; 3: ⟨ code for x = 3 ⟩; othercases ⟨ code for x ≠ 1 and x ≠ 3 ⟩ endcases

since most Pascal compilers have plugged this hole in the language by incorporating some sort of default mechanism. For example, the Pascal-H compiler allows ‘others :’ as a default label, and other Pascals allow syntaxes like ‘else’ or ‘otherwise’ or ‘otherwise:’, etc. The definitions of othercases and endcases should be changed to agree with local conventions. Note that no semicolon appears before endcases in this program, so the definition of endcases should include a semicolon if the compiler wants one. (Of course, if no default mechanism is available, the case statements of TEX will have to be laboriously extended by listing all remaining cases. People who are stuck with such Pascals have, in fact, done this, successfully but not happily!)

define othercases ≡ others : { default for cases not listed explicitly }

define endcases ≡ end { follows the default case in an extended case statement } format othercases ≡ else format endcases ≡ end 11. The following parameters can be changed at compile time to extend or reduce TEX’s capacity. They may have different values in and in production versions of TEX. ⟨ Constants in the outer block 11 ⟩ ≡

mem max = 30000; { greatest index in TEX’s internal mem array; must be strictly less than max halfword ; must be equal to mem top in , otherwise ≥ mem top }

mem min = 0; { smallest index in TEX’s internal mem array; must be min halfword or more; must be

equal to mem bot in , otherwise ≤ mem bot } buf size = 500; { maximum number of characters simultaneously present in current lines of open files

and in control sequences between and ; must not exceed max halfword } error line = 72; { width of context lines on terminal error messages } half error line = 42; { width of first lines of contexts in terminal error messages; should be between 30

and error line − 15 } max print line = 79; { width of longest text lines output; should be at least 60 } stack size = 200; { maximum number of simultaneous input sources } max in open = 6;

{ maximum number of input files and error insertions that can be going on simultaneously } font max = 75; { maximum internal font number; must not exceed max quarterword and must be at

most font base + 256 } font mem size = 20000; { number of words of font info for all fonts } param size = 60; { maximum number of simultaneous macro parameters } nest size = 40; { maximum number of semantic levels simultaneously active } max strings = 3000; { maximum number of strings; must not exceed max halfword } string vacancies = 8000; { the minimum number of characters that should be available for the user’s

control sequences and font names, after TEX’s own error messages are stored } pool size = 32000; { maximum number of characters in strings, including all error messages and help

texts, and the names of all fonts and control sequences; must exceed string vacancies by the total length of TEX’s own strings, which is currently about 23000 }

save size = 600; { space for saving values outside of current group; must be at most max halfword } trie size = 8000; { space for hyphenation patterns; should be larger for than it is in production

versions of TEX } trie op size = 500; { space for “opcodes” in the hyphenation patterns } dvi buf size = 800; { size of the output buffer; must be a multiple of 8 } file name size = 40; { file names shouldn’t be longer than this }

pool name = ´ ␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣´ ;

{ string of length file name size; tells where the string pool appears }

This code is used in section 4.

12. Like the preceding parameters, the following quantities can be changed at compile time to extend or reduce TEX’s capacity. But if they are changed, it is necessary to rerun the initialization program to generate new tables for the production TEX program. One can’t simply make helter-skelter changes to the following constants, since certain rather complex initialization numbers are computed from them. They are defined here using macros, instead of being put into Pascal’s const list, in order to emphasize this distinction.

define mem bot = 0

{ smallest index in the mem array dumped by ; must not be less than mem min }

define mem top ≡ 30000 { largest index in the mem array dumped by ; must be substantially

larger than mem bot and not greater than mem max }

define font base = 0 { smallest internal font number; must not be less than min quarterword } define hash size = 2100 { maximum number of control sequences; it should be at most about

(mem max − mem min)/10 }

define hash prime = 1777 { a prime number equal to about 85% of hash size } define hyph size = 307 { another prime; the number of exceptions }

13. In case somebody has inadvertently made bad settings of the “constants,” TEX checks them using a global variable called bad .

This is the first of many sections of TEX where global variables are defined. ⟨ Global variables 13 ⟩ ≡ bad : integer ; { is some “constant” wrong? }

See also sections 20, 26, 30, 32, 39, 50, 54, 73, 76, 79, 96, 104, 115, 116, 117, 118, 124, 165, 173, 181, 213, 246, 253, 256, 271, 286, 297, 301, 304, 305, 308, 309, 310, 333, 361, 382, 387, 388, 410, 438, 447, 480, 489, 493, 512, 513, 520, 527, 532, 539, 549, 550, 555, 592, 595, 605, 616, 646, 647, 661, 684, 719, 724, 764, 770, 814, 821, 823, 825, 828, 833, 839, 847, 872, 892, 900, 905, 907, 921, 926, 943, 947, 950, 971, 980, 982, 989, 1032, 1074, 1266, 1281, 1299, 1305, 1331, 1342, and 1345.

This code is used in section 4.

14. Later on we will say ‘if mem max ≥ max halfword then bad ← 14’, or something similar. (We can’t do that until max halfword has been defined.) ⟨ Check the “constant” values for consistency 14 ⟩ ≡

bad ← 0; if (half error line < 30) ∨ (half error line > error line − 15) then bad ← 1; if max print line < 60 then bad ← 2; if dvi buf size mod 8 ≠ 0 then bad ← 3; if mem bot + 1100 > mem top then bad ← 4; if hash prime > hash size then bad ← 5; if max in open ≥ 128 then bad ← 6; if mem top < 256 + 11 then bad ← 7; { we will want null list > 255 }

See also sections 111, 290, 522, and 1249. This code is used in section 1332.

15. Labels are given symbolic names by the following definitions, so that occasional goto statements will be meaningful. We insert the label ‘exit :’ just before the ‘end’ of a procedure in which we have used the ‘return’ statement defined below; the label ‘restart ’ is occasionally used at the very beginning of a procedure; and the label ‘reswitch’ is occasionally used just prior to a case statement in which some cases change the conditions and we wish to branch to the newly applicable case. Loops that are set up with the loop construction defined below are commonly exited by going to ‘done’ or to ‘found ’ or to ‘not found ’, and they are sometimes repeated by going to ‘continue’. If two or more parts of a subroutine start differently but end up the same, the shared code may be gathered together at ‘common ending ’.

Incidentally, this program never declares a label that isn’t actually used, because some fussy Pascal compilers will complain about redundant labels.

define exit = 10 { go here to leave a procedure } define restart = 20 { go here to start a procedure again } define reswitch = 21 { go here to start a case statement again } define continue = 22 { go here to resume a loop } define done = 30 { go here to exit a loop } define done1 = 31 { like done, when there is more than one loop } define done2 = 32 { for exiting the second loop in a long block } define done3 = 33 { for exiting the third loop in a very long block } define done4 = 34 { for exiting the fourth loop in an extremely long block } define done5 = 35 { for exiting the fifth loop in an immense block } define done6 = 36 { for exiting the sixth loop in a block } define found = 40 { go here when you’ve found it } define found1 = 41 { like found , when there’s more than one per routine } define found2 = 42 { like found , when there’s more than two per routine } define not found = 45 { go here when you’ve found nothing } define common ending = 50 { go here when you want to merge with another branch }

16. Here are some macros for common programming idioms.

define incr (#) ≡ # ← # + 1 { increase a variable by unity } define decr (#) ≡ # ← # − 1 { decrease a variable by unity } define negate(#) ≡ # ← −# { change the sign of a variable } define loop ≡ while true do { repeat over and over until a goto happens } format loop ≡ xclause { ’s xclause acts like ‘while true do’ } define do nothing ≡ { empty statement } define return ≡ goto exit { terminate a procedure call } format return ≡ nil define empty = 0 { symbolic name for a null constant }