I’ve been trying to think of the best way of characterizing the basic classes of typesetting engines. Here’s roughly where I am up to.
There are basically three approaches used by typesetting systems:
- The oldest approach. The page is divided up into grids, and paragraph gets injected line by line to fit between various gridlines. Further gridlines may be placed relative to positions in the paragraph (e.g. the end). In a grid system, tables and lists are really just an arrangement of paragraphs with particular grid relationships rather than being objects in their own right. Troff and Word 1.0 and XSL-FO regions are examples of this kind of approach.
- The page is divided into linked (typically rectangular) areas and the text is poured into them. A table would be considered a frame of frames. Adobe FrameMaker and ISO DSSSL are examples of this approach.
- Cells are objects which have certain fixed and variable properties, such as size etc, and have various relationships between other cells: TeX’s box and glue metaphor is a good example, but ideas of gravity or magnetism are also appropriate. Typesetting involves finding an optimal solution from a system or subsystem of cells. Cells may contain other cells, allowing hierarchical properties. The cell approach can allow very dynamic typesetting.
Each kind of typesetting engine has different ways to get the same kind of effect. Take the example of how a system knows when to break a paragraph at the bottom of the page, or move it to the next. A primitive grid system would have some kind of “requires” attribute on the paragraph, for example to say “This paragraph requires at least two lines free at the bottom of the page, otherwise cast off the page and start the paragraph on a new one.” A primitive frame system might have “widow and orphan” controls, which looked at how the text was spread between the frames. A cell system might have “keep with next” and “keep with previous” properties for each paragraph, and sort out which kind of breaking resulted in the least penalty.
Modern typesetting systems are rarely pure versions of each, of course: the needs for extra features, convenience and interoperability leads developers to graft or cherry pick approaches. For example, a copy-fitting system might be basically grid-based, but use a penalty system and feedback to rejiggle the grid settings for better fit. The extent (how many paragraphs, columns, pages, etc) and granularity (which objects, frames or grids can be rejiggled) plays a large role in determining how much human intervention will be required to achieve high quality typesetting. Think of a Yellow Pages directory: to get good results for these, you need to go beyond what is on the immediate spread but to previous (and therefore following) spreads as well, for optimal the placement of floating display material that keeps in sync with the current running heads.
And even within the same approach of system, there are many possible variations, which page designers will be very aware of. For example, when a paragraph says “Keep 1cm space after me” and the next paragraph says “Keep 2 cm space before me” some systems will work by adopting the greater (2cm) while others will adopt the sum (3cm). We might imagine that primitive grid systems could tend to the latter, while frame systems could tend to the former (and cell systems might do some negotiation or compromise: 1.5cm?) But at this level, it is every man for himself.
One feature of typesetting systems that dominates their design and capabilities is whether they are streaming or in-memory. A streaming implementation has very little lookahead (and probably very little memory of recent pages), and complicated typesetting will be performed by mixes of diversions (where text perhaps in some semi-processed state is stored for later use) or by multiple passes or by checkpoints (a range is read in-memory to allow various typesetting options to be tried and the optimal one put out, the range being discarded: to overcome the limitations of stream-based processing). It is quite rare to find systems that have typesetting rules allowing or using very significant lookahead: even cell-based systems try to localize properties to being object-properties (e.g. paragraph properties) or immediate-location properties (e.g. frame or page properties).
[UPDATE: I am removing any comments not on the topic of typesetting engines. Though of course I really appreciate the readers who defend me, please don’t post comments about individuals. There may be malicious hypocrites at loose in the world, but they can be exposed on other blog items! ]