Different classes of typesetting engines

by Rick Jelliffe

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! ]


2008-03-07 09:23:58
Take a look at PrinceXML Jeff
they have a rather nice motivation for using em
as the unit specifier in css based mark-up.
Well I was impressed.
Censored Phil
2008-03-08 17:28:26
You said: "READERS: Any future comments relating to DIS 29500 this
week will be removed."

Hiding the problem won't make it go away. Censor away, if that's the
only way you (and Microsoft) can get this shitty standard approved.
Closing the forums for discussion seems to be a rule here, but it
won't make any of what you say less of a lie.

You also said: "There have been exactly ZERO "proven cases of corruption"."

Computerworld good enough for you?

What's worse is the ten P-members that joined the JTC1 just to vote at
the last minute. Specially considering that P-member means a member
that is supposed to be interested in *DEVELOPING THE STANDARD*. Last
minute joins make no sense whatsoever. It's hard, so hard, oh so hard
to think of this fact and not to think it's not related to corruption
from Microsoft. Come on, even you cannot deny that!

You said: "Shame on you."

Well, I would be ashame if I had been bought by Microsoft to support
their crappy format, but as I didn't, I'm not ashame. Are you???

Gareth Horton
2008-03-09 18:09:15

I suggest your invective would be better directed at Microsoft employees, since, outside the slightly bizarre world that your "movement" inhabits, Rick is a respected expert in his field, mainly known for the invention of Schematron. You just end up sounding like you are raving, rather than making the sort of valid points that even-handed people might want to discuss.

I suppose you are annoyed that Patrick Durusau doesn't have a blog that you can insult him on, so Rick was the next best thing (no offence Rick).

It's a very dangerous world if Patrick Durusau can get ravaged by the ODF crowd, what next, will Rob Weir get a mauling if he says "OOXML is not that bad after all". Who's in charge, or has it descended into Lord of the Flies.

Maybe you could even attack companies like us instead, but of course you can't, since we don't exist. (Implementors of Open XML support since Feb 2007)

It does seem that some of the most sensible comments in this bunfight seem to come from old lags like Len Bullard and Rick. An imperfect spec is better than no spec at all, right?


Rick Jelliffe
2008-03-09 21:20:35
Gareth: Thanks for the kind words. It is being caught between a rock and a hard place: if you respond to the loony fringe to correct technical errors or incorrect presumptions, you then get accused of being a propagandist for one side. If you try to stick to factual articles, they then accuse you of sidestepping or ignoring the issues. When you try to be moderate or take your time forming a conclusion, they accuse you of backtracking. When you are friendly but dare call a spade a spade, they accuse you of backstabbing.

I really don't know if the extreme anti-OOXML side (and everytime I use an expression like that, some insecure whinger says "but we are not all extreme how dare you"...and then I have to point out I was meaning the ranting extremists not the mainstream, perfectly civil people who are perfectly entitled to their perfectly legitimate view) knows how misguided their Karl Rove Playbook strategy has been.

The basic Karl Rove strategy, apparently, is to find the main strength of the opposition and try to make a disadvantage of it. So rather than "6000 pages, that must be pretty complete" we have "6000 pages, how can any single human read that in 30 days?" And rather than "1000 changes agreed on by explicit voting of national standards bodies with 5 and 10? weeks of discussion time, in a system agreed by the national bodies" we have "No discussion time during the meetings! Procedure foisted!"

Rick Jelliffe
2008-03-09 21:25:40
IceBurg: Yes, font-relative measures are often appropriate.
2008-03-12 00:38:21
Rob Weir is still the interesting character in all this. In a recent blog posting he has gone to the extent of insulting his own preferred spec's editor because he strayed from the NOOXML party line. Can a man so bitter, spiteful, and ultimately weak be respected in a group of standards professionals? Will his involvement as co-chair of the OASIS ODF committee portend a good or bad future for that format?

It takes a certain kind of skill to denigrate a competitor's product by blowing up minor issues, impugning the producer's guessed-at motives, and treating differences of opinion as differences of fact. These skills are not necessarily the same ones needed to produce a robust interoperable format (which requires the cooperation of a number of parties). I certainly hope Rob gets his comeuppance, but I wouldn't want to see the ODF format itself suffer in the process.