Here is a short program that can print 152831 pages with no indication of memory problems.
\documentclass{article}
\usepackage{lipsum}
\begin{document}
\newcount\n
\n=0
\def\message{I can count to }
\loop
\ifnum\n<37000
\advance\n by1
\message\number\n : \lipsum[1-2]
\repeat
\end{document}
You can increase the \lipsum[1-2] and test both your patience as well as TeX's limits! As long as you allow TeX to break a page easily you are unlikely to hit any memory problems.
Knuth created a very efficient memory management system. The details can be found at the TeX source. A somewhat limited explanation of how memory and strings are handled can be found in my answer for Delimiting a macro argument with the macro itself. Check also for TEXPOOL on your distribution.
Not only Knuth but Lamport and all the LaTeX contributors took extreme care to preserve memory as well as to provide proper garbage collection. IMHO studying the TeX source should be required reading at all Computer Science classes. In the link above check the Dynamic Memory allocation section and note Knuth's comments (clause 119), which is the most common problem encountered with TeX new users:
If memory is exhausted, it might mean that the user has forgotten a
right brace...
On a last note TeX does not keep your "book" in memory. It always works on a page at a time ... well almost. If you do not close with a right brace it will continue scanning, potentially until the end of the source and so it cannot de-allocate memory. Knuth introduced a lot of checks and special commands to avoid these issues (long, outer etc...).
1 Exercise for the reader, change the page height to half and see if you can double the pages.
There's no linear programming involved.
TeX stores items in lists (vertical, horizontal or math lists). Math lists are converted to horizontal lists, so only the first two must be discussed, but they are alike when setting the glue is involved.
Glue is stored as a glue item, represented with its natural width, stretch component and shrink component.
When TeX has to build a box having a certain width from a horizontal list or a certain height from a vertical list (lines in a paragraph or a page, for instance), it sums up all the natural widths, adds the width of the non-glue items and computes how much the glue has to be stretched or shrinked.
If stretching s is required and t total stretch is available, TeX computes the "stretch ratio" r = s/t; and if a glue item has x stretch component, TeX adds rx to the natural width.
The situation is similar for shrinking, with the difference that TeX will never go below the stated shrinking and will output an overfull box if the total shrinking available is not sufficient.
There is a little complication because stretching or shrinking can be expressed in "infinite units". Well, the computation of the total stretching or shrinking available keeps the higher order of infinity resulting from the computation and adds (or removes) from the natural width only to the glue items which match that order of infinity in their specification.
These are very easy and fast operations on any computer.
The paragraph making algorithm takes into account stretchability and shrinkability of the glue items in the horizontal list it has built only in an indirect way.
Glue items mark feasible line break points, provided they are preceded by a non-discardable item (also other items mark feasible breaks). During this phase TeX looks at the natural widths of the items and, to put it simply, chooses a sequence of break points such that no line will exceed the current \hsize.
Actually this choice is based on many parameters, on penalties found in the list (or implicit penalties) and on computed demerits. Possible break points are also discretionary hyphens that may have been automatically inserted during the process.
For each feasible break point, TeX computes the glue ratio for the line that would result, which assigns a badness to the line that will be used in the computation of the total demerits. However glue is not set at this point, but only when TeX has chosen the best sequence of break points (the best according to its rules and the values of the various involved parameters): the lines are put in hboxes of width \hsize, essentially \hbox to \hsize{...} and now the glue is set as explained above.
Best Answer
TeX's glue dimensions, including the infinite dimensions
fil,fill, andfilll, lack the following structure/properties:Cancellation: since
1pt + 1fil = 1filaccording to the rules, glue is not even an additive group. You can of course write1pt plus 1fil, but that means something entirely different, as Heiko explains.Multiplication: you cannot multiply glue by other glue. Well, you can down-convert a
skipinto adimenand, interpreted as a multiple of1sp, you can multiply another skip (glue) by that integer. Under this interpretation, by the way,1fil = 0, since an infinite stretch is impossible in the base value of glue, which is what is converted.I don't know of any mathematical structure including "infinities" that lacks cancellation but allows real numbers as values. For example, hyperreal numbers have infinite quantities but
1 + \omega \neq \omega. Ordinals are closer, but addition is not commutative (though we do have1 + \omega = \omega), and in the version that is commutative (natural addition) we have1 + \omega \neq \omega.One system of, er, quantities that I hesitate to call a structure is the catalog of asymptotics given by big-O notation. It appears that Knuth's glue does adhere to the first four levels of the polynomial hierarchy:
pt = O(1),fil = O(n),fill = O(n^2), andfilll = O(n^3). We keep track of the multipliers but not of lower-order terms when adding. Under this identification we would havefil * fill = filll, or at least isO(filll), but that andfil^2are the only products we could take, so it hardly seems worth it.This is probably the most likely, given Knuth's fame as the pioneer of analysis of algorithms, but I wouldn't overthink it even so. He clearly implemented the grade-school arithmetic of infinity: you know, "infinity = infinity plus one" and "infinity squared > infinity", which are endlessly debated in third-grade cafeterias.