There's no mention of widows or orphans on that page. But presumably the Knuth-Plass algorithm is aware of those and take them into account when breaking lines?
One thing I've often wondered is whether these algorithms treat a page break from even to odd differently from a page break from odd to even: it could make sense to do so, I think, in the case of an ordinary book, particularly when it comes to placing an illustration or table, but perhaps also for widows and orphans.
It's been a while since I wrote this, but I seem to remember that widows are NP-hard at least: fitting them to pages maps onto box-packing.
I really implemented this algorithm so that I could nicely "flow" images in a GUI window. I was working with Sean Parent & Jaakko Järvi on Adam/Eve. My assertion was that there were layout principles (Adam?) for UI similar to the constraint properties for the object model (Eve?). The "other" layout principle was the grid-bag (CSS's box model for grids).
TeX treats the problems of (1) choosing line breaks to turn a stream of words into a stream of lines, and (2) choosing page breaks to turn a stream of lines into a stream of pages, separately; it does #1 and then #2. The Knuth-Plass algorithms addresses #1. I think #2 is done by simpler means; there is some support in it for penalizing widow and orphan lines, but no way for that to feed back to the line-breaking process.
In the common case where your pages are just text with a fixed spacing between lines, the only way for #2 to prevent widows and orphans is to make the page one line taller or shorter, making the margins look weird, which typically also gets penalized, and the only question is which penalty is larger. But if there are any variable spacings on the page, there will be the option of making them slightly larger or smaller in order to push a stray line from one page to another.
There’s a similar problem with paragraphs ending with a very short line. IIRC, nothing special needs to be done about that because the squaring in the formula of the penalty makes the penalty of such a line very high.
If so, nothing special needs to be done about widows and orphans either because
TeX first uses essentially the same algorithm to decide where to put page breaks between lines (with page breaks between paragraphs getting lower penalties than page breaks within paragraphs), and having a single line of a paragraph on the top or bottom of a page leads to a fairly high penalty.
The standard TeX algorithm doesn't penalize the length of the last line, so doesn't solve this. The implementation in Android, based on Minikin[1], applies some penalty to the last line by default, as it's especially unpleasant on mobile. It also has a "balanced" setting[2] which applies the full penalty, as that's often more aesthetically pleasing in UI contexts, though it would not be a good choice for a running text, as it would result in paragraphs of uneven width.
Last month, I submitted a patch to GNU Emacs with an implementation of line breaking inspired by Knuth-Plass and an option to enable it for paragraph filling. (I'm still iterating on the patch.)
My approach to runts was to apply the full penalty to the last line, but only if the number of words was below a threshold (by default, only if it's a single word).
Thanks for the interesting replies to my question.
It sounds as though TeX cannot do anything about widows and orphans in the boring "simple" case of a long prose text with a fixed number of lines per page, because the only way[] to improve page breaks in that case would be to change the line breaks, which have already been decided. Mixing up the line-break and page-break stages presumably gives you an NP-hard optimisation problem, and perhaps Knuth was less interested in working on messy heuristic algorithms.
I've just found a couple of references to work in this area:
[] I'm assuming that moving the margins or changing the line spacing would be unacceptable because it would make the pages of a book look obviously different from each other. So it turns out that the "simple" case is in some ways harder to handle than the "complex" case in which there are figures and footnotes and so on.
One thought that was proposed back in the 80s was that just as line breaks are considered in the paragraph as a whole, page breaks could be considered in the document as a whole (TeX can’t do this—easily—being Turing complete, in theory it can do anything computable, but the speed would be atrocious). This could be managed by doing things like lengthening or shortening pairs of facing pages by a line or trying to tighten or loosen an individual paragraph to change the number of lines in it. A document formatter which comes at page breaks with the right level of abstraction of the data would be able to manage this with minimal or no human intervention (when I was typesetting Serif magazine with TeX in the 90s, I just went through and fixed page breaks manually which is a typical modern workflow as well).
I enjoyed looking at serifmagazine.com just now, and would love to read articles from it if any were available.
I’ll show this to my compsci students later today as an example of what web pages typically used to look like.
10 comments
[ 5.0 ms ] story [ 29.6 ms ] threadhttps://en.wikipedia.org/wiki/River_(typography)
I love typography rabbit holes.
One thing I've often wondered is whether these algorithms treat a page break from even to odd differently from a page break from odd to even: it could make sense to do so, I think, in the case of an ordinary book, particularly when it comes to placing an illustration or table, but perhaps also for widows and orphans.
I really implemented this algorithm so that I could nicely "flow" images in a GUI window. I was working with Sean Parent & Jaakko Järvi on Adam/Eve. My assertion was that there were layout principles (Adam?) for UI similar to the constraint properties for the object model (Eve?). The "other" layout principle was the grid-bag (CSS's box model for grids).
In the common case where your pages are just text with a fixed spacing between lines, the only way for #2 to prevent widows and orphans is to make the page one line taller or shorter, making the margins look weird, which typically also gets penalized, and the only question is which penalty is larger. But if there are any variable spacings on the page, there will be the option of making them slightly larger or smaller in order to push a stray line from one page to another.
If so, nothing special needs to be done about widows and orphans either because TeX first uses essentially the same algorithm to decide where to put page breaks between lines (with page breaks between paragraphs getting lower penalties than page breaks within paragraphs), and having a single line of a paragraph on the top or bottom of a page leads to a fairly high penalty.
[1]: https://raphlinus.github.io/text/2022/11/08/minikin.html
[2]: https://developer.android.com/reference/android/widget/TextV...
My approach to runts was to apply the full penalty to the last line, but only if the number of words was below a threshold (by default, only if it's a single word).
It sounds as though TeX cannot do anything about widows and orphans in the boring "simple" case of a long prose text with a fixed number of lines per page, because the only way[] to improve page breaks in that case would be to change the line breaks, which have already been decided. Mixing up the line-break and page-break stages presumably gives you an NP-hard optimisation problem, and perhaps Knuth was less interested in working on messy heuristic algorithms.
I've just found a couple of references to work in this area:
https://mirrors.mit.edu/CTAN/macros/luatex/generic/lua-widow...
https://onlinelibrary.wiley.com/doi/10.1111/coin.12165
--------
[] I'm assuming that moving the margins or changing the line spacing would be unacceptable because it would make the pages of a book look obviously different from each other. So it turns out that the "simple" case is in some ways harder to handle than the "complex" case in which there are figures and footnotes and so on.