perm filename TEXDR.AFT[1,DEK]1 blob sn#282172 filedate 1977-05-13 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00016 PAGES C REC PAGE DESCRIPTION C00001 00001 C00004 00002 Preliminary preliminary description of TEX C00007 00003 In order to explain TEX more fully, I will alternate between very low-level C00013 00004 1 %Example TEX input related to Seminumerical Algorithms using ACPdefs C00028 00005 The first thing that must be emphasized about this example is that it is written C00034 00006 It is time to explain TEX's mechanism for stretching and shrinking. C00043 00007 Now let's look at more of the example. Lines 21 and 32, etc., are blank lines C00049 00008 Line 46 begins a "boxinsert", one of the important features needed in page layout. C00054 00009 The ``big(){...}'' in lines 113, 143, etc. and the ``big/{...}'' in line 152 C00058 00010 The next step in understanding TEX is to go back to the low level and see C00066 00011 Some tokens are not defined as macros but stand for actions to be carried out. C00070 00012 At the outermost level, TEX has implicitly preceded the input by "TEXpublish{", C00078 00013 Now let's consider the page-building routine "nextpage" this gives us a chance C00086 00014 The nextparagraph routine assembles lines of width hsize, pausing to C00094 00015 Besides using the permissible breaks, TEX will try to hyphenate words. C00102 00016 To conclude this memo, I should explain how TEX is going to work on C00103 ENDMK C⊗; Preliminary preliminary description of TEX D Knuth, May 13, 1977 In this memo I will try to explain the TEX system for preparing publishable documents and how it is proposed to implement the system. Even though I don't understand TEX very well myself yet, I think the best way for me to get started is by trying to explain it to somebody else. TEX is for technical text. Insiders pronounce the X as a Greek Chi (cf. the Scottish `ch' sound in `Loch Ness') since the word `technical' stems from a Greek root meaning art as well as technology. I am preparing the system primarily for use in publishing my series The Art of Computer Programming-- the initial system will be tuned for my books, but it will not be difficult to extend it for other purposes if anybody wants to do so. The input to TEX is a file in say TVeditor format at the Stanford AI lab. The output is a sequence of pages, produced in "one pass," suitable for printing on various devices. This report tries to explain how to get from input to output. The main idea is to consider the process as an operation on two-dimensional "boxes"; roughly speaking, the input is a long string of characters culled from a variety of fonts, where each character may be thought of as occupying a small rectangular box, and the output is obtained by gluing these boxes together either horizontally or vertically with various conventions about centering and justification, finally arriving at big rectangular boxes which are the desired pages. While LISP works with one-dimensional character strings, TEX works with two-dimensional box patterns; TEX has both horizontal and vertical `cons' operations. Furthermore, TEX has another important basic concept of elastic glue between boxes, a type of mortar that stretches and shrinks at different specified rates so that box patterns will fit together in flexible ways. In order to explain TEX more fully, I will alternate between very low-level descriptions of exactly how the processing takes place and very high-level descriptions of what you type to get complex effects. First, at the vey lowest level, we must realize that the input to TEX is not really a string of boxes, it is a file of 7-bit characters. This file is called an "external input file". The first ting TEX does is convert it to an "internal input file" by essentially obeying the following rules: 1.Delete the first TVeditor directory page, if it exists. 2.Delete the first line (title line) of every remaining page, and replace the end-of-page marks ('14) by carriage-returns ('15). Delete all line-feed symbols ('12). Delete all % marks and the sequences of characters following them up to (but not including) the next carriage-return. 3.Delete all blank spaces following carriage-returns. 4.If two or more carriage returns occur in sequence, replace all but the first by vertical-tab characters ('13). These are used to specify end of paragraphs in TEX; in other words, the user specifies end of paragraph by hitting two carriage returns in a row, or by a page break following a carriage return. 5.Replace all remaining carriage-returns by blank spaces. 6.If two or more blank spaces occur in a row, replace them by a single blank space. 7.Add infinitely many } symbols at the right. The reason for rule 7 is that TEX uses { and } for grouping, and the trailing }'s will match up with any {'s the user erroneously forgot to match in the external input file. By following the above rules, TEX obtains an internal input file containing no carriage-returns, line-feeds, %'s, or form-feeds (page marks), and with no two blank spaces in a row. Spacing in the output document is controlled by other features of TEX. (Actually TEX changes { and } internally to '14 and '15, but this does not affect the user so I will continue to write this report as if they were { and }.) Now let`s shift to a high level and show how the user can specify complex typesetting requirements to TEX. The following example is rather long and it deserves to be skimmed rather than studied in detail; I devised it mainly to serve as test data during initial development of the system. It is taken from the opening pages of my book Seminumerical Algorithms, skipping over the copy when the typesetting presents no essentially new challenges to the system. The reader might find it most useful to have the book in hand for comparison purposes. The line numbers at the left are not part of the TEX input, they are included only for purposes of cross reference so that I can refer to line so-and-so later on in this document. 1 %Example TEX input related to Seminumerical Algorithms using ACPdefs 2 ACPpages starting at page 1{ 3 titlepage %This tells the page format routine not to put page number at top 4 sectionnumber 3 5 runninglefthead{RANDOM NUMBERS} 6 hexpand 11 pt {fnt cmg11 CHAPTER hskip 10 pt THREE} 7 vskip 1 cm plus 30 pt minus 10 pt 8 rjustline {fnt cmgb20 RANDOM NUMBERS} 9 vskip .5 cm plus 1 pc minus 5 pt 10 quoteformat {Anyone who considers arithmetical \cr 11 methods of producing random digits \cr is, of course, 12 in a state of sin. \cr} author {JOHN VON NEUMANN (1951)} 13 quoteformat {Round numbers are always false.} 14 author{SAMUEL JOHNSON (c. 1750)} 15 vskip 1 cm plus 1 pc minus 5 pt 16 sectionnumber 3.1 17 sectionbegin {3.1. INTRODUCTION} 18 runningrighthead {INTRODUCTION} 19 Numbers which are ``chosen at random'' are useful in a wide variety of 20 applications. For example: 21 %This blank line specifies end of paragraph 22 yskip %This means an extra space between paragraphs 23 textindent{a)}{\sl Simulation.}xskip When a computer is used to simulate natural 24 phenomena, random numbers are required to make things realistic. Simulation 25 covers many fields, from the study of nuclear physics (where particles are 26 subject to random collisions) to systems engineering (where people come into, 27 say, a bank at random intervals). \par 28 yskip textindent{b)}{\sl Sampling.} xskip It is often impractical to examine all 29 cases, but a random sample will provide insight into what constitutes ``typical'' 30 behavior. 31 32 yskip It is not easy to invent a foolproof random-number generator. This fact 33 was convincingly impressed upon the author several years ago, when he attempted 34 to create a fantastically good random-number generator using the following 35 peculiar method: 36 37 yskip yskip noindent {\bf Algorithm K} xskip({\sl ``Super-random'' number 38 generator}). xskip Given a 10-digit decimal number $X$, this algorithm may be 39 used to change $X$ to the number which should come next in a supposedly random 40 40 sequence. \par 41 algstep K1.[Choose number of iterations.]Set $Y←lfloor X/10 sup 9 rfloor$, i.e., 42 the most significant digit of $X$. (We will execute steps K2 through K13 $Y+1$ 43 times; that is, we will randomize the digits a {\sl random} number of times.) 44 45 algstep K10. [99999 modify.] If $X<10 sup 5$, set $X←X sup 2 + 99999$; 46 otherwise set $X ← X - 99999$. xskip blackslug 47 48 boxinsert{ctrline{fnt cmgb10 Table 10} 49 ctrline{fnt cm9 A COLOSSAL COINCIDENCE: THE NUMBER 6065038420} 50 ctrline{fnt cm9 IS TRANSFORMED INTO ITSELF BY ALGORITHM K.} 51 blankline 3 pt vskip ruled 52 hjust to 12 pc{blankline vskip 6 pt 53 tabalign{#⊗quad#⊗quad$#$\cr 54 Step⊗ctr{$X$ (after)}\cr 55 vskip 10 pt plus 10 pt minus 5 pt 56 K1⊗6065038420\cr K12⊗1905867781⊗Y=5\cr 57 vskip 10 pt plus 10 pt minus 5 pt blankline} 58 hskip 3 pc ruled align top 59 hjust to 12 pc{blankline vskip 6 pt 60 tabalign{#⊗quad #⊗quad $#$\cr 61 Step⊗ctr{$X$ (after)}\cr 62 vskip 10 pt plus 10 pt minus 5 pt 63 K10⊗1620063735\cr K11⊗1620063735\cr K12⊗6065038420⊗Y=0\cr 64 vskip 10 pt plus 10 pt minus 5 pt blankline} 65 vskip ruled blankline} %end of the boxinsert 66 yskip yskip The moral to this story is that {\sl random numbers should not be 67 generated with a method chosen at random}. Some theory should be used. 68 69 exbegin 70 exno tr 1. [20] Suppose that you wish to obtain a decimal digit at random, not 71 using a computer. Shifting to exercise 16, let $f(x,y)$ be a function such that 72 if $0≤x,y<m$, then $0≤f(x,y)<m$. The sequence is constructed by selecting 73 $X sub 0$ and $X sub 1$ arbitrarily, and then letting$$ 74 X sub{n+1} = f(X sub n, X sub {n-1}) quad for quad n>0.$$ 75 What is the maximum period conceivably attainable in this case? 76 77 exno 17. [10] Generalize the situation in the previous exercise so that 78 $X sub {n+1}$ depends on the preceding $k$ values of the sequence. 79 \ff 80 sectionnumber 3.2 sectionbegin{3.2. GENERATING UNIFORM RANDOM NUMBERS} 81 runningrighthead {GENERATING UNIFORM RANDOM NUMBERS} 82 In this section we shall consider methods for generating a sequence of random 83 fractions, i.e., random {\sl real numbers $U sub n$, uniformly distributed 84 between zero and one}. Since a computer can represent a real number with only 85 finite accuracy, we shall actually be generating integers $X sub n$ between 86 zero and some number $m$; the fraction$$U sub n=X sub n/m eqno 1$$ will 87 then lie between zero and one. 88 89 vskip .4 in plus .2 in minus .2 in 90 sectionnumber 3.2.1 sectionbegin{3.2.1. The Linear Congruential Method} 91 runningrighthead{THE LINEAR CONGRUENTIAL METHOD} 92 By far the most successful random number generators known today are special 93 cases of thhe following scheme, introduced by D. H. Lehmer in 1948. [See 94 {\sl Annals Harvard Comp. Lab.} {\bf 26} (1951), 141-146.] We choose four 95 ``magic numbers'':$$ 96 tabalign{rjust#⊗quad mathoff # quad⊗rjust #⊗ljust #\cr 97 X sub 0,⊗the starting value;⊗X sub 0⊗≥0. \cr 98 m,⊗the modulus;⊗m⊗>X sub 0, quad m>a, quad m>c. \cr} eqno 1$$ 99 The desired sequence of random numbers $langle X sub n rangle$ is then obtained 100 by setting $$X sub{n+1}=(aX sub n+c)mod m,quad n≥0.eqno 2$$This is called 101 a {\sl linear congruential sequence}. 102 103 Let $w$ be the computer's word size. The following program computes $(aX+c) 104 mod(w+1)$ efficiently:$$tabalign{\it#quad⊗hjust to 50 pt{\tt#}\cr 105 01⊗LDAN⊗X\cr 106 02⊗MUL⊗A\cr 107 05⊗JANN⊗*+3\cr 108 07⊗ADD⊗=W-1= quad blackslug\cr} eqno 2$$ 109 {\sl Proof.} xskip We have $x=1+qp sup e$ for some integer $q$ which is not a 110 multiple of $p$. By the binomial formula$$ 111 eqalign{x sup p⊗=1+{p choose 1}qp sup e + cdots +{p choose p-1}q sup 112 {p-1}p sup{(p-1)e}+q sup p p sup {pe}\cr 113 ⊗=1+qp sup{e+1} big(){1 + 1 over p {p choose 2} q p sup e + 1 over p 114 Op choose 3} q sup 2 p sup {2e} + cdots + 1 over p {p choose p} q sup {p-1} 115 p sup {(p-1)e}.\cr$$ By repeated application of Lemma P, we find that$$ 116 eqalign{(a sup p sup g - 1)/(a-1)⊗equiv 0`(modulo p sup g), \cr 117 (a sup p sup g - 1)/(a-1)⊗inequiv 0`(modulo p sup {g+1}). \cr}eqno 6$$ 118 If $1<k<p$, $p choose k$ is divisible by $p$. {biglpren}{\sl Note:} xskip A 119 generalization of this result appears in exercise 3.2.2-11(a).{bigrpren} By 120 Euler's theorem (exercise 1.2.4-48), $a sup{varphi(p sup{e-f})} equiv 1` 121 (modulo p sup{e-f}); hence $lambda$ is a divisor of$$ 122 lambda(p sub 1 sup e sub 1 ldots p sub t sup e sub t)=lcm paren{lambda(p sub 1 123 sup e sub 1), ldots, lambda(p sub t sup e sub t)}. eqno 9$$ 124 125 This algorithm in MIX is simply$$ 126 tabslign{hjust to 50 pt{\tt#}⊗{\tt#}} quad⊗ \cr 127 J6NN⊗*+2⊗underline{\it A1. j<0?}\cr 128 STA⊗Z⊗quad quad $→Z$.\cr} eqno 7$$ 129 That was on page 26. If we skip to page 49, $Y sub 1 + cdots + Y sub k$ will 130 equal $n$ with probability$$ 131 sum over{y sub 1 + cdots + y sub k = n}atop{y sub 1, ldots, y sub k ≥ 0} 132 prod over {1≤s≤k} 133 {e sup{-np sub s}(np sub s)sup y sub s}over y sub s! 134 ={e sup -n n sup n}over n!.$$ 135 This is not hard to express in terms of $n$-dimensional integrals$$ 136 textsize{int from alpha sub n to n dY sub n int from alpha sub{n-1} to 137 Y sub n dY sub{n-1} ldots int from alpha sub 1 to Y sub 2 dY sub 1} over 138 textsize{int from 0 to n dY sub n int from 0 to Y sub n dY sub{n-1} ldots 139 int from 0 to Y sub 2 dY sub 1}, quad {\rm where} quad alpha sub j = 140 max(j-t,0). eqno 24$$ 141 This together with (25) implies that$$ def rtn{sqrt n} 142 lim over {n→inf} s over rtn 143 sum over{rtn s<k≤n}{n choose k} big(){k over n - s over rtn} sup k 144 big(){s over rtn + 1 - k over n} sup{n-k-1} = e sup {-2s} sup 2, quad s≥0, 145 eqno 27$$ a limiting relationship which appears to be quite difficult to 146 prove directly. 147 148 exbegin exno 17. [HM26] Let $t$ be a fixed real number. For $0≤k≤n$, let$$ 149 P sub nk(x)=int from{n-t}to x dx sub n int from{n-1-t} to x sub n dx sub 150 {n-1}ldots int from {k+1-t} to x sub{k+2} dx sub{k+1} int from 0 to 151 x sub {k+1} dx sub k ldots into from 0 to x sub 2 dx sub 1;$$ 152 Eq. (24) is equal to$$def sumk{sum over{1≤k≤n}} 153 sumk X prime sub k Y prime sub k big/{sqrt{sumk X prime sub k sup 2} 154 sqrt{sumk Y prime sub k sup 2}}.$$ 155 sectionnumber 3.3.3.3 subsectionbegin{3.3.3.3. This subsection doesn't exist} 156 runningrighthead{A BIG MATRIX DISPLAY} Finally, look at page 91.$$ 157 def diagdots{raise . by 10 pt hskip 4 pt raise . by 5 pt hskip 4 pt .} 158 eqalign{U⊗=big(){tabalign{ctr#⊗ctr#⊗ctr#⊗ctr#⊗ctr#⊗ctr#⊗ctr#\cr 159 1\cr⊗diagdots\cr⊗⊗1\cr 160 c sub 1⊗ldots⊗c sub{k-1}⊗1⊗c sub{k+1}⊗c sub n\cr 161 ⊗⊗⊗⊗1\cr⊗⊗⊗⊗⊗diagdots\cr⊗⊗⊗⊗⊗⊗1\cr}},\cr 162 U sup{-1}⊗=big(){tabalign{ctr#⊗ctr#⊗ctr#⊗ctr#⊗ctr#⊗ctr#⊗ctr#\cr 163 1\cr⊗diagdots\cr⊗⊗1\cr 164 -c sub 1⊗ldots⊗-c sub{k-1}⊗1⊗-c sub{k+1}⊗-c sub n\cr 165 ⊗⊗⊗⊗1\cr⊗⊗⊗⊗⊗diagdots\cr⊗⊗⊗⊗⊗⊗1\cr}}$$ 166 This ends the test data, fortunately TEX is working fine.} The first thing that must be emphasized about this example is that it is written in an extension of TEX, not in the basic language itself. For example, "ACPpages" in line 2 is a special routine that calls TEX's basic page-building routine but uses it to prepare pages in the format of The Art of Computer Programming. The words titlepage, sectionnumber, runninglefthead, quoteformat, author, sectionbegin, runningrighthead, xskip, yskip, textindent, algstep, exbegin, exno, and subsectionbegin are specific to my books and they have been defined in terms of lower-level TEX primitives as we shall see below. Furthermore most of the fonts used are embedded in these hidden definitions; for example, "sectionbegin" defines the 10 point fonts used in the text of a section, while "exbegin@ defines the 9 point fonts used in the exercises. Such keywords are chosen so that they do not match English words, since they can appear intermixed with normal text. For example, another definition is that the word MIX always is to be set in the "typewriter type" font; the hidden definition def MIX|{{\tt \{MIX}}} causes this to happen automatically in line 125. We shall study TEX's macro definition mechanism later; three simple examples appear in lines 141, 152, and 157 of the sample program, where a common idiom was given a short definition just to save space. The construction \{string} is used to transmit a string without interpreting its words according to existing definitions; this device is used in the above definition of the keyword MIX. For curious people who want to see a more complex definition, here is the definition of quoteformat: def quoteformat #1 author #2 {lineskip 3 pt plus .5 pt minus 1 pt vskip 6 pt plus 5 pt minus 2 pt def \rm {fnt cmg8} def \sl {fnt cmgi8} {\sl tabalign{rjust##\cr #1}} vskip 6 pt plus 5 pt minus 2 pt \rm rjustline #2 vskip 11 pt plus 5 pt minus 2 pt} Please don't expect to understand this mess now, TEX is really very simple; trust me. The word ``author'' which appears in this definition is given special interpretation only in the context of quoteformat, otherwise it is treated as usual; that is why I didn't use a non-English word like ``quoteauthor'' in lines 12 and 14 of the example. The specifications of sectionnumber and runninglefthead in lines 4 and 5 are to be used in the top lines of pages in the book. Line 6 contains the first actual text to appear on the page; but look first at line 8, which is simpler: Line 8 says to use font cmgb20 (namely, "Computer Modern Gothic Bold 20 point", which I plan to design shortly) for the words RANDOM NUMBERS, and to right-justify them on the line (rjustline). Line 6 is similar but it uses the 11-point font cmg11; ``hskip 10 pt'' stands for 10 points of horizontal space, and ``hexpand 11 pt'' means to take the line and stretch it 11 points wider than it would ordinarily be. Note that font definitions within {...} disappear outside the braces. So do all other definitions. It is time to explain TEX's mechanism for stretching and shrinking. Sizes in TEX can be specified in terms of points, picas, inches, centimeters, or millimeters, using the abbreviations pt, pc, in, cm, mm respectively; these abbreviations are meaningful only in contexts where physical lengths are used, and one of these units must always be supplied in such contexts even when the length is 0. (One inch equals 6 picas equals 72 points equals 2.54 centimeters equal 25.4 millimeters.) The glue between boxes has three components: the fixed component, x the plus component, y the minus component, z The x part is "normal" spacing; when expanding a sequence of boxes to more than their normal length, as on line 6, each x part in the glue is increased by some multiple of the y part. When shrinking, each x part is decreased by some multiple of the corresponding z part. For example, given four boxes bound together by glue of specifications (x1,y1,z1), (x2,y2,z2), (x3,y3,z3), expansion of the line by an amount w is achieved by using the spacing x1 + y1 w', x2 + y2 w', x3 + y3 w', where w' = w/(y1+y2+y3). The expansion is impossible if w>0 and y1+y2+y3=0. The system tries hard to minimize bad-looking expansions, by having a reasonably intelligent justification routine (described below). When shrinking a line, the maximum amount of contraction is the sum of the z's, no tighter fit will be attempted; thus, one should define the z width so that x-z is the minimum space tolerated. The proper setting of y is such that x+y is a reasonable spacing but x+3y is about at the threshold of intolerability. Parameters y and z must be nonnegative, but may be negative (for backspacing and overlap) if care is used. The notation ``hskip 10 pt'' in line 6 means that x = 10 pt, y = 0, and z = 0 in the horizontal glue between CHAPTER and THREE. If this hskip hadn't been used, the normal conventions would have applied. Namely, the glue between CHAPTER and THREE would have had x equal to the normal spacing for the font, and y = x, z = x/2. The glue between letters has (say) x = 0, y = 1/10 of the normal spacing for the font, z = 0; thus the expansion without using hskip would have gone mostly into the space between CHAPTER and THREE, but by using hskip as shown the expansion spreads out the individual letters. Fonts to be used with TEX will have such letter spacing indicated as an additional feature; TEX will also recognize things like the end of sentences, giving slightly more white space after punctuation marks where appropriate. Symbols like + and = conventionally are surrounded by spaces, while symbol pairs like '' and := are moved closer together; the symbols + and = are not surrounded by spaces when they appear in subscripts. Such things are taken care of in the same way that ligatures are handled, by making the fonts a little smarter under TEX's control, as described in more detail later. Much of TEX is symmetrical between horizontal and vertical, although the basic idea of building lines first rather than columns first is asymmetrically built in to the standard routines (because of the way we normally write). The specification ``vskip'' on line 7 specifies vertical glue analogous to horizontal glue. When the page justification routine tries to fill the first page of the example text (by breaking between pages ideally at the end of a paragraph, or in a place where at least two lines of a paragraph appear on both pages), this glue will expand or shrink in the vertical dimension using x = 1 centimeter, y = 30 points, z = 10 points. Further variable glue is specified in the definition of quoteformat: lineskip is the inter-line spacing, and the vskips give special additional spacing between quotation and author lines. In the main text, the printer would refer to the type as "10 on 12", meaning 10 point type with 12 points between corresponding parts of adjacent lines; TEX will use a 10 point font with lineskip 2 pt plus .5 pt minus .25 pt so that its line spacing is somewhat more flexible. Additional spacing between paragraphs is given by parskip 0 pt plus 1 pt minus 0 pt and there is other spacing between exercises, steps in algorithms, etc. The definition def yskip {vskip 3 pt plus 2 pt minus 2 pt} is used for special vertical spacing, for example in lines 22 and 37. A horizontal skip def xskip {hskip 6 pt plus 10 pt minus 3.5 pt} is used in lines 23, 35, etc. in contexts where a larger than normal space is psychologically acceptable; for such purposes, flexible glue is especially useful. A larger horizontal space called ``quad'' is used for example in line 74; this is "two ems" of space, a unit frequently used in mathematical typesetting. Another nice feature of flexible glue occurs when you consider the case def hfill {hskip 0 cm plus 1000 cm minus 0 cm}. In other words, y is essentially infinite (10 meters long). When this symbol appears as an hskip at the beginning of a line, it right justifies that line; when it appears at both the beginning and end, it centers the line; when it appears in the middle it neatly partitions the line; and so on. These features of TEX's variable glue seem to make it superior to existing justification systems, because it provides new features in a rather simple way and at the same time reduces the old features to a common pattern. Once a list of boxes has been justified, all the glue is permanently set and the overall box becomes rigid. Justification is either horizontal or vertical. Horizontal justification of long lines includes some automatic hyphenation; further details about justification appear later in this memo. Now let's look at more of the example. Lines 21 and 32, etc., are blank lines indicating the end of a paragraph; another way to specify this is ``\par'' in line 27. Line 124 is a end of a paragraph that ends with a displayed formula. Paragraphs are normally indented; one of the TEX commands subsumed under "sectionbegin" in line 17 is parindent 20 pt which affect the first line of every paragraph unless ``noindent'' appears as on line 37. The "sectionbegin" routine also specifies ``noindent'' on the very first paragraph of the section, since this is the standard format in my books. On line 23 we have ``textindent{a)}', which creates a box of width parindent containing the characters a) followed by a blank space, right justified in this box. In line 23 the "\sl" means "use slanted font." I have tentatively decided to replace italics by a slanted version of the normal "Roman" typeface, for empahsized words in the text, while variable symbols in math formulas will still be in italics as usual. I will have to experiment with this, but my guess is that it will look a lot better, since typical italic fonts do not tie together into words very beautifully. At any rate I will be distinguishing slanted from italic, in case it becomes desirable to use two different fonts for these different purposes. The "\bf" in line 35 stands for boldface. All these fonts are defined in sectionbegin, whose definition is hidden to you. Mathematical formulas all appear between $...$ pairs, cf. lines 38 and 41, or between $$...$$ pairs (displayed equations). A special syntax is used in formulas, modeled on that of Kernighan and Cherry, Comm. ACM 18 (March 1975), 151-157. For example, ``sup 9'' in line 41 specifies a superscript 9, ``sub {n+1}'' in line 74 specifies a subscript n+1. Keywords like sup and sub are active only with $'s; the same applies to greek letter names like lambda (line 122) and varphi ("variant phi", the rounded version of this letter, which appears in a superscript in line 120), as well as to words like lim (line 142), max (line 140), lcm (line 122). All letters in formulas are set in italics unless they form part of a recognized word or are surrounded by "mathoff{...}" or "{\rm ...}". All spacing within formulas is chosen by TEX, independent of spaces actually typed; the symbol ` (cf. line 117) denotes an inserted space, for cases when TEX's rules are unsatisfactory. In line 117, for example, extra space is wanted before "(modulo...)" since space before parentheses is usually omitted but not here. The later parts of the example text are largely concerned with complicated formulas, which will appear as shown in the corresponding parts of volume 2. The code "eqno 24" (cf. line 140) will insert "(24)" at the right margin, vertically centered on the corresponding displayed formula, if there is roon, otherwise the "(24)" is stuck on a new line at the bottom right. The algorithm-step-format keyword "algstep" used on lines 41 and 45 is defined as follows: def algstep #1. [#2] {vskip 3 pt plus 1 pt minus 1 pt noindent rjust in 20 pt{#1.} [#2] xskip hangindent 20 pt} This sets vertical spacing glue before the text for the algorithm step, and it also set up an appropriate "textindent", etc. The new feature here is the hanging indent, which affects all but the first line of the following paragraph. The keyword "exno" used on lines 70, 77, etc. has a definition somewhat similar to algstep; such definitions of format that are needed frequently in my books will help to ensure consistency. The ``tr'' in line 70 will insert a triangle in the left margin, using negative glue spacing so that the character actually appears to the left of the box it is in. Line 46 begins a "boxinsert", one of the important features needed in page layout. The box defined within the {...} after boxinsert is set aside and placed on top of either the present page or the following page (followed by vertical glue specified by boxskip 20 pt plus 10 pt minus 5 pt, this being another thing subsumed by "sectionbegin"). This is used for figures and tables, in this case a table. The the table caption appears in lines 48-50; the table itself (cf. page 6 of the book) is rather complicated, so we will defer explanation of lines 52-65 until after we have studied the simpler example of tabalign in lines 96-98. In general, a tabalign command takes the form tabalign{ u1#v1 ⊗ ... ⊗ un#vn \cr x11 ⊗ ... ⊗ x1n \cr . . . . . . . . xm1 ⊗ ... ⊗ xmn \cr} Here the ⊗'s represent <TAB>'s on the keyboard and in the input file, but they are shown here explicitly as printed characters to make their appearance plain. The "\cr" is not a carriage-return, however, it is the sequence of three characters \, c, r. The meaning is to form the mn boxes u1{x11}v1 ... un{x1n}vn . . . . . . . . . u1{xm1}v1 ... un{xmn}vn and, for each k, to determine the maximum width of box uk{xik}vk for i = 1,...,m. Then each uk{xik}vk is hjustified to the size of this maximum width, and each line xi1⊗...⊗xin\cr is replaced by the horizontal concatenation of the resulting boxes, separated by tabskip 0 pt plus 1 pt minus 0 pt. If less than n entries appear on any line before the \cr, the remaining entries are left blank. In the example of tabalign on lines 96-98 we have n=4; the first column is to be right justified, the second is to be treated as "mathoff" and surrounded by quad spaces, the third again is right justified, the fourth is simply left-justified. The result is shown on page 9 of the book, although with TEX the formula number "(1)" will be centered. Note: Eventually I will put in an "omittab" feature which will allow portions of a line to span several columns when desired. Now let's look at lines 52-65 and compare with Table 1 on page 6 of the book. A box of width 12 picas is built up using tabalign, and placed beside another such box. The words "ruled" modifying vskip or hskip mean that the glus between boxes also appears with a horizontal or vertical ruled line in its center. The ``eqalign'' feature (cf. lines 111, 116) is used to line up operators in different displayed formulas. Actually this is simply a special case of tabalign: def eqalign #1 {tabalign{rjust##⊗ljust##\cr #1}}. Note that line 113 begins with <TAB>. The ``big(){...}'' in lines 113, 143, etc. and the ``big/{...}'' in line 152 is used to choose suitably large versions of parentheses and slashes, forming ``(...)'' and ``/...'', respectively; the size of the symbols is determined by the height of the enclosed formula box. This type of operation is available for [], <>, ||, and left and right braces signified by \[ and \]. TEX will provide the best size available in its repertoire. Parenthesis, brackets, braces, and vertical lines will be made in arbitrarily large sizes, but slashes will not, at least not in this year's TEX. Some very large parentheses will be generated for the big matrices in lines 158ff. The ``biglpren'' and ``bigrpren'' on lines 118-119 are not really so big, they are simply 12-point parentheses instead of 10-point ones, used o set off the enclosed normal-size parentheses in the text's "(a)". The summation signs produced by ``sum over...'' in lines 131, 143, will be large, since these summations occur in displayed formulas; but between $...$ a smaller sign will be used and the quantity summed over will be attached as a subscript. Similarly, the size of an integral sign will change, and fractions ``...over...'' do too, as does the binomial coefficient (cf. "$p choose k$" in line 118). The keyword ``textsize'' in lines 136 and 138 says to use smaller integral signs in this formula even though it is displayed. The \ff in line 79 means to eject a page (top justified) before continuing. This again is part of the format of my books, a major section always should begin on a new page. I think the above comments on the example give the flavor of TEX. The example was intended to show a veriety of changing constructions of unusual complexity; in general, most of a book will be comparatively routine, and it is only the occasional formula or table which proves intricate. Such intricacies were purposely emphasized in the example. The next step in understanding TEX is to go back to the low level and see what happens to an internal input file as it is being read in. What happens is that it is massaged once again, converted to a sequence of "tokens", which are either single characters or words. In general, adjacent letters and digits are grouped together to form words; also periods and commas immediately followed by digits are treated as letters, as are \ signs that are not preceded by letters or digits. More precisely, the following finite-state machine defines the token-building process. State 0. Let x be the next character of the internal input file. If x is \ or one of the 52 letters or 10 digits, set w←x and go to state 1. If x is period or comma, set y←x, set w←null, go to state 2. Otherwise output x as the next token. State 1. Let x be the next character of the internal input file. If x is a letter or digit, set w←w&x (w followed by x). If x is period or comma, set y←x and go to state 2. If x is \, output w as the next token, set w←x. Otherwise output w as the next token, then output x as the next token, and go to state 0. State 2. Let x be the next character of the internal input file. If x is a digit, set w←w&y&x, go to state 1. Otherwise if w is nonempty, output w as the next token; then output y as the next token; then go to state 0 but without resetting x at the beginning of the instructions for that state. For example, the sequence Abc\de 5,000 plus-or-minus ``2.5 \per cent'' are ... here. would be transformed into a sequence of 28 tokens: Abc \de <space> 5,000 <space> plus - or - minus <space> ` ` 2.5 \per <space> cent ' ' <space> are <space> . . . <space> here . TEX works on sequences of tokens. If a token has been defined (using ``def''), a <space> before this token is removed. The remaining portion of the definition is plugged in; the same process is repeated on the resulting sequence of tokens. Definitions disappear after the } or $ or $$ which closes the group they are in; they also are inoperative between \{ and its matching }. If the keyword MIX had been defined as def MIX{{\tt MIX}} instead of def MIX{{\tt\{MIX}}}, TEX would have looped endlessly while emitting {\tt {\tt {\tt {\tt .... By now the reader will probably understand everything or nothing about the definition process; but anyway I will try to spell out its rules more carefully. Once writes in general def token string0 #1 string1 #2 string2 ... #k stringk {right-hand side} where "token" is any token except { or }, and where string0 ... stringk are strings of zero or more tokens not including { or } or # or |; spaces are ignored in these strings. I am describing the general case; the above definition of MIX is the simplest case of the general form, where k is zero and string0 is empty. When the defined token is recognized, a matching process ensues until the left-hand side is completely matched: tokens in string0...stringk must match exactly with corresponding tokens of the input text (removing all spaces), with error messages if a failure to match occurs. The #j's are matched to tokens or to {...} groups. No expansion is done on the {...} groups, they are merely treated as an uninterrupted sequence of tokens. There is at most one definition active per token at any time. Once the matching process is complete, TEX will have found the ingredients to be substituted for #1 through #k in the right-hand side. These are simply copied into the positions occupied by #1 ... #k in the right-hand sequence. And one further change is made: the first # is removed from any sequence of two or more #'s. This is done so that definitions can be made in the right-hand side without causing confusion with the current definition. For example, consider what happens when the following definition is active: def A #1 B C {def E ##1{##1 #1 #1}}. If the internal input file contains A {X-y} B C D the resulting sequence after expanding the definition will be def E #1{#1{X-Y}{X-Y}} D (note the spacing). If the character | appears just before the { which introduces the right-hand side of a definition, the space if any after the last token matched will be preserved. Thus, in the above example if we had written def A #1 B C|{def E ##1{##1 #1 #1}} the result would have been def E #1{#1{X-Y}{X-Y}}D. This feature was used in our definition of MIX on a previous page, because it will preserve the space that comes after MIX in mid-sentence; on the other hand, most definitions (for example, xskip) would not use this feature. The above is not the most general sort of macro definition facility, but I have applied Occam's razor. A much more general capability is available via TEX "routines" which are explained later; routines are for the more expreienced users. The reader should now be able to look back at the definitions given above for quoteformat, algstep, and eqalign, discovering that they are really quite simple after all. Some tokens are not defined as macros but stand for actions to be carried out. For example, "fnt" means means the following non-space token is to be the name of the current font of type, and "def" means that TEX is supposed to absorb a new definition. Thus we have four mutually exclusive sorts of tokens: defined tokens action tokens { and } other tokens. The { and } denote grouping and separate levels of context; definitions and assignment actions made inside {...} do not have any effect outside. Assignment actions affect TEX's transformation of the input. They are: fnt token to change the current font hsize length normal width of generated lines of text vsize length normal height of generated pages of text hmargin length distance from left edge of paper to generated lines vmargin length distance from top edge of paper to generated pages lineskip glue spacing between generated lines parskip glue additional spacing between paragraphs (added to lineskip) dispskip glue additional spacing above and below displayed formulas boxskip glue additional spacing below an inserted box noteskip glue additional spacing above footnotes tabskip glue horizontal spacing between tabaligned columns parindent length indentation on first line of paragraphs hangindent length indentation on all but first line of paragraph (hangindent reset to zero after every paragraph) All of these quantities will have default values, which I will choose after TEX is up and running; the default values will apply whenever a quantity has not been respecified. In the above, ``length'' is of the form token unit or - token unit where the token is a digit string or a digit string containing a period (decimal point), and where ``unit'' is either pt, pc, in, cm, or mm. Furthermore ``glue'' is of the form length plus length minus length where the plus and minus parts cannot be negative; any of the three lengths can be omitted if zero. For example, standard XGP conventions at the moment are to produce 8 1/2 by 11 inch pages with one-inch margins and interline spacing of 4 pixels; this would be specified by hsize 6.5 in vsize 9 in hmargin 1 in vmargin 1 in lineskip .02 in At the outermost level, TEX has implicitly preceded the input by "TEXpublish{", where TEXpublish is a routine that repeatedly calls on the page-builder, the page-builder is a routine that repeatedly calls on the paragraph-builder, and the paragraph-builder is a routine that reads the input and emits strings of justified lines of text. TEXpublish simply prints each page that it gets; our example text input substitutes the more sophisticated routine ACPpages for TEXpublish. In the first implementation of TEX, routines like ACPpages will be written in SAIL code and loaded with TEX. I have had some notion of adding an interpretive system to TEX and a mini-programming language so that such extensions are easier to make without penetrating into TEX's innards, but on second thought it seems much better to assume that TEX's code will be sufficiently clean that it will best be extended using SAIL code. This will save the implementors considerable time and make the system run faster. Let's continue the outside-in approach by skething the SAIL code for ACPpages. Remember that this is not basic TEX, but the code resembles the internal program of TEX. It is at the moment only an initial approximation to the real SAIL code, since I will have to think more about how TEX will look inside before I can be more specific. if scan("starting") then begin scanreqd("at"); scanreqd("page"); spage←nextnonspacetoken; end else spage←"1"; {Here "scan" is a TEX routine which looks at the next nonspace token from the input; if it equals the specified token, scan returns true and discards the token, otherwise the current input token is not passed over and false is returned. The routine "scanreqd" is similar, but instead of returning false it will produce an error message like "Syntax error, I will insert missing #". The net result of the above code is to set spage to the string representing the specified starting page, or by default to set it to "1".} if spage = "r" then begin rnumeral←true; lop(spage); end; pageno←intscan(spage, brchar); {Roman numeral page numbers are indicated by r1, r2, etc. Now pageno is the integer number of the desired first page and rnumeral is true if and only if roman numeral page numbers are desired.} scanreqd(leftbrace); put_on_stack_something_to_make_matching_right_brace_end_the_input; while true do begin cpage←nextpage; if not cpage then done; {Here cpage is a pointer to a box or the null record pointer when the input has terminated.} if rnumeral then spage←cvrom(pageno) else spage←cvs(pageno); if omithead then {this would be set by "titlepage" routine} begin omithead←false; output_cpage_with_blanks_for_top_headline_and_with_spage_in_ 9_point_type_centered_as_a_new_line_at_the_bottom; end else begin if pageno land 1 then {right-hand page} begin texta←the_running_right_head; textb←attr(sectno,cpage); {texta and textb are record pointers to sequences of tokens; "attr" gets the sectno attribute of box cpage, as explained below} line←pointer_to_box_which_TEX_would_make_from_the_input "{textb} hfill {texta} rjust to .375 in {spage}" end else begin texta←the_running¬left¬head; textb←attr(sectno,first(cpage)); line←pointer_to_box_which_TEX_would_make_from_the_input "ljust to .375 in {spage} texta hfill textb" end; place_line_above_cpage_with_14_pt_glue_and_output_the_result; end; pageno←pageno+1; end; {In other words, odd-numbered pages get the sectionnumber attribute of cpage and the running right headline followed by a right-justified page number, as the title line; even-number pages get a left-justified page number followed by the running left headline followed by the sectionnumber attribute of the first component of cpage. Note that the section number is supposed to represent the top of a left-hand page but the bottom of a right-hand page} The above example indicates that we need to discuss another basic feature of TEX, namely the "attributes" which can be attached to its boxes. One such attribute is the section number; another is the height, another is the width; still others, used in math formulas, are the amounts of space available inside the box, if any, that may be used to attach subscripts and superscripts. For each attribute, two routines are supplied, explaining how to produce the attribute of a box formed from two boxes placed together horizontally or vertically. For example, the height attribute is replaced by max(h1,h2) when two boxes are joined horizontally but by h1+h2 when they are joined vertically. The section-number attribute is s1 if s2 is null, otherwise it is s2; and so on. Now let's consider the page-building routine "nextpage"; this gives us a chance to study the process TEX uses for vertical justification, which introduces some of the concepts we will need in the more complicated routine used for horizontal justification. The first idea is the concept of "badness." This is a number computed on the basis of the amount of stretching or shrinking necessary when setting the glue. Suppose we have a list of n boxes (either a horizontal list or a vertical list), separated by n-1 specifications of glue. The w be the desired total length of the list (i.e., the desired width or height, depending on which dimension we are justifying); let x be the actual total length of boxes and glue; and let y,z be the total amount of glue parameters for expansion and contraction. The badness of this situation is defined to be infinite, if x > w - z + ε, where ε is a small tolerance to compensate for floating-point rounding; 100((x-w)/z)↑3, if w - z + ε ≥ x > w; 0, if x = w; 100((w-x)/3y)↑3, if w > x; plus penalties charged for breaking lines in comparatively undesirable places. According to these formulas, stretching by y has a badness rating of 100/27, or about 3.7; stretching by 2y is rated about 30; stretching by 3y is rated 100 units of badness, and so is shrinking by the maximum amount z. I plan to charge a penalty of something like 80 units for breaking a paragraph or displayed formula in such a way that only one line comes by itself on a page; thus, for instance, a five-line paragraph gets a penalty of 80 if we break after the first or fourth line, but no penalty if we break after two or three lines. I will of course be tuning these formulas to make them correspond as well as I can to me aesthetic perceptions of bad layout. The user will be able to specify his own additional penalty points for undesirable breaking between specific lines (e.g. in a MIX program to break before an instruction that refers to *-1). A penalty is also made for break at "ruled" vertical glue. The nextpage routine forms a list a lines (and the connecting vertical glue) which it receives from the nextparagraph routine; the nextparagraph routine returns a sequence g1 h1 ... gk hk alternating between vertical glue and boxes representing horizontally justified lines of text. The individual h's are not broken up or examined by nextpage, except to look at their attributes. Also \ff and end-of-input codes will be transmitted by nextparagraph to the nextpage routine. The nextpage routine accumulates lines until its previous accumulation plus the new paragraph is greater than or equal to the specified page height, vsize. Then it breaks the new paragraph just after the jth line, for 0≤j≤k, whichever value of j has the minimum badness; if this minimum occurs for more than one j, the largest such j is used. Then the glue g(j+1) is discarded, and the remaining k-j lines are carried over to the next page. (They are immediately checked to ensure that they don't already overfill the new page, and they are broken in the same way if necessary.) A boxinsert interrupts this otherwise straightforward procedure. The box to be inserted is computed, off to the side, and then an attempt is made to place it over the current accumulated page. If it fits, well and good, we leave it there. If not, it is carried over to the next page, and placed in front of any carryover from the present page. Additional box-inserts are inserted below the first one, in a natural but hard-to-explain manner. Footnotes:I have used footnotes only three times in over 2000 pages of The Art of Computer Programming, and personally I believe they should usually be avoided, so I am not planning an elaborate footnoting mechanism (e.g. to break long footnotes between pages or to mark the first footnote per page with an asterisk and the second with a dagger, etc.). They can otherwise be satisfactorily handled by attaching a footnote attribute to any line referring to a footnote, and by requiring the nextpage routine to put the footnote on the page containing that line. This, together with the badness ratings, will solve the problem about footnote references on the bottom line preempting the space needed for the footnote itself, etc. A user will be able to get fancier footnotes if he doesn't mind rewriting a few of TEX's routines. On \ff or end-of-input, the nextpage routine simulates "vfill blankline" and clears its page buffers, unless they were already empty. After end-of-input it returns a null page, to signal the end of its activity; after \ff it asks nextparagraph for more. The nextparagraph routine assembles lines of width hsize, pausing to transmit them a) at end of paragraph ('13); b) at beginning of display formula ($$); c) at end of display formula ($$); d) just before vskip operation; e) just before and after blankline, ctrline, ljustline, rjustline, hjustline; f) at \ff or end-of-input. The operations in (e) produce independent lines of width hsize that are not part of a paragraph, and such lines are merely transmitted without change. Display formulas are also passed without change, except that appropriate glue is attached above and below them. (The glue above a displayed equation is reduced from dispskip to lineskip if the text on the preceding line does not overhand the displayed formula after centering.) The text of a paragraph, or of the portion of a paragraph beginning and/or ending at $$, is indented (if appropriate) and passed to the hjust routine. The hjust routine attempts to break the text into lines of length hsize in the least bad way, taking proper account of hangindent. The "least bad" way is a way which minimizes the maximum badness of any of the breaks made. At this point in the process, the text consists of a possibly long sequence of boxes, separated by glue, and these boxes will not be changed by the hjust routine. The hjust routine has a new feature which makes it superior to existing justification systems, besides the idea of variable-weight glue, namely it effectively "looks ahead" so that the situation in the later lines of a paragraph can influence the breaks in the earlier lines. I have noticed quite a few places where such a justification routine will provide substantially better output. This lookahead is accomplished by applying the principles of "dynamic programming," as I will try to explain below. First let's understand what the boxes precessed by hjust usually look like. They might be large complicated boxes, which are to be treated as black boxes essentially as the nextpage routine treats its lines; but mostly the individual boxes at this point will be individual letters from one or more fonts. When a text token comes along, the current font indicator is attached to it (so that the 7-bit code becomes a 12-bit code), and the token is broken into its individual characters. Pairs of adjacent characters are examined, from left to right, using tables associated with the font; this is used to compute changes in the glue between characters, and to produce ligatures if they are present, etc. For example, on most fonts the sequence `` will want to have specially narrow glue between the two characters. We get ligatures by replacing f f by <ff> f i by <fi> f l by <fl> <ff> i by <ffi> <ff> l by <ffl>. Such ligature formation and glue adjustment takes place when the character boxes are being appended to the current line, before hyphenation etc.; this means that we lose the chance to break "shuffling" into "shuff-ling", but so what. The <space> token is changed into glue between boxes, with y=x and z=x/2 as explained earlier. The hskip and quad actions also produce variable glue. Whenever this glue has x or y greater than or equal to the spacing width of the current font, it is an acceptable place to break the line with no penalty. Another acceptable place is after an explicit hyphen. (Some hskips, used for backspacing, have negative x; they are, of course, unacceptable breaks.) TEX will give double y glue to the first space that follows a period, exclamation point, question mark, or colon, unless letters or digits intervene before this space. A semicolon and comma are treated similarly, but with 1.5 and 1.25 as the relative amounts of y glue. The math formula routine which processes $...$ will yield a sequence of boxes in format compatible with the text strings outside of formulas; acceptable places to break in formulas will be marked just after binary operators and relations. A penalty is attached to such breaks; I will have to tune the parameters, but the following idea appears to be best: Relations like =, ≤, ≡, etc. have only a small penalty, operations like +, -, x, / have a larger penalty, with - larger than the others. Superscripts and subscripts and function arguments and the like will be attached unbreakably to their boxes. There are three "discretionary" symbols used to provide or inhibit breaks: \- OK to hyphenate this word here; \+ do not hyphenate here; \* OK to break here, but insert a times sign not a hyphen. The last of these would be used in a long product like $(n+1)\*(n+2)\*(n+3)\*(n+4)$. Besides using the permissible breaks, TEX will try to hyphenate words. It will do this only in a sequence of lower-case letters than is preceded and followed by anything other than a letter, digit, -, \-, or \+. Note that, for example, already-hyphenated compound words will not be broken. If a permissible hyphenation break is discovered, a penalty of say 30 units of badness will be paid, but this may be better than not hyphenating at all. An additional 20 units of badness is charged for breaking a word or formula in the last line of a paragraph. There is no point in finding all possible places to hyphenate. For one thing, the problem is extremely difficult, since e.g. the word "record" is supposed to be broken as "rec-ord" when it is a noun but "re-cord" when it is a verb. Consider the word "hyphenation" itself, which is rather an exception: hy-phen-a-tion vs. co-or-di-na-tion Why does the n go with the a in one case and not the other? Starting at letter a in the dictionary and trying to find rigorous rules for hyphenation without much knowledge, we come up against a-part vs. ap-er-ture, aph-o-rism vs. a-pha-sia, etc. It becomes clear that what we want is not an accurate but ponderously slow routine that consumes a lo of memory space and processing time, instead we want a set of hyphenation rules that are a) simple; b) almost always safe; c) powerful enough to find say 80% of the words already hyphenated in The Art of Computer Programming. To justify point (c), I find that there are about 2 hyphenated words per page in the books, and the places where the rules I shall propose do not find the identical hyphenation only very rarely would cause a really bad break. The time needed to handle the remaining exceptions is therefore insignificant by comparison with what I already do when proof-reading. So here are the rules I came up with. 1. Consider only breaks in which both parts contain a vowel other than final e. (Vowels are a,e,i,o,u,y.) 2. Subject to 1, break before the following "safe" suffixes: -cious -gion -ly -ment -mial -nary -ness -nomial -sion -tion -ture -vious and also -tive preceded by a vowel, -ed preceded by d or t. Break before -ing except in -bling -pling or when preceded by a double letter other than ll or ss or zz; for other double letters, break between them. If the word ends in s or ly, strip off this ending and apply these rules again. Suffixes recognized by this rule must not be further broken except vi-ous. 3. Subject to 1 and 2, break after the following "safe" prefixes: algo- equi- ex- hyper- ini- intro- lex- lexi- math- mathe- max- maxi- mini- multi- out- over- pseudo- semi- some- sub- super- there- under- Also be- followed by c,h,s,w; dis- followed by anything but h,y; trans- followed by a,f,g,l,m; tri- followed by a,f,p,u. 4. Subject to 1 and 2, combine an h with the previous letter if it is a consonant, treating the combination as a consonant; then it's OK to break between the two consonants in the pattern vc-cv except when the pair of consonants is bl ck cl cr dr ght gl gr lk ll nd ng pl rch rd rm rt sch sp ss st thr zz (I may have to revise this list.) There will be rare exceptions (e.g., equivocate, minister, somersault, triphammer), but these will be so infrequent as to be unimportant. Looking through quite a few pages of volume 3, I found 48 hypenations, and the above rules were satisfactory except in the three cases de-gree hap-hazard re-placement. Of course, these rules are biased toward my vocabulary and subject matter, but a few extensions should make it work well enough for nearly everybody. Now for the dynamic programming algorithm which minimizes the maximum badness of breaks. The badness formula is the same as before; thus for each break after a given point we can compute the resulting badness. In this way, for each permissible break position, we will minimize the maximum badness that can occur counting this and previous breaks. The running time will be approximately linear in the number of possible breaks. However, this will b rather slow since it tries breaking all words when in practice only a few candidate words really need to be considered. Thus the following approximate method should run about ten times faster: Given the best three ways to break the kth line, use these to find the best three ways to break the (k+1)st line. The breaks found will almost certainly be optimum unless the situation is very bad anyway. To conclude this memo, I should explain how TEX is going to work on math formulas. However, I will have to sketch out the code in more detail and it is only fuzzy in my mind at the moment. My plan is to use the top-down precedence parsing approach introduced by Vaughan Pratt in his 1973 POPL paper, and used so successfully by him in CGOL (for example). Further details will be forthcoming; I hope to do the box pasting in one pass, but it may be necessary to build the parse tree first as Kernighan and Cherry do.