|
Something's been nagging at the edge of my mind. Knuth–Plass, the algorithm that breaks TeX's paragraphs into lines, has been adapted for music at least once, by Hegazy and Gourlay, and I ought to look at what they did. If there's prior art, so much the better: that's a strength, and something to build on.
For musicians, the underlying question is an old one: where should each system end? A score has to be cut into lines, and where the cuts fall decides whether the spacing is even, whether a crammed system sits next to a loose one, and where a page can be turned. The simplest method, and a common one, fills a system bar by bar, moves on when the next bar won't fit, and stretches whatever is there to the width of the page. It's quick, it never looks ahead, and it leaves the engraver forcing breaks by hand. Programmers call this greedy filling, and it doesn't produce optimal breaks. Knuth's algorithm, written for paragraphs of text, does the opposite: it weighs every possible set of breaks and picks the best. This matters because a player judges a page at a glance, before reading a note of it. And it's technical because that glance is decided here, in the model, long before anything is drawn. The questions were harder to settle than I'd expected. Was Hegazy and Gourlay's algorithm, and whatever descended from it, really Knuth–Plass, or something merely inspired by it or adapted from it? If adapted, was it still provably optimal, as the original is? And had the real algorithm ever been used to engrave music at all? The last question has the clearest answer: yes, in 1987. MuTeX, a master's thesis at Bonn by Andrea Steinbach and Angelika Schofer, set music with TeX's own glue and line breaking. The MusiXTeX manual later explained why that struggles: a line of text holds dozens of words and a system only a handful of bars, so the stretch piles up as gaps before the barlines. Hegazy and Gourlay's paper, from the same year, isn't online, so exactly what they did I can't say. What can be read is its descendant, described in ADR-0037. LilyPond's first line breaker, written ten years later, names their report in its source as its origin, and it's a dynamic program in Knuth–Plass's family. Later versions added a term for the evenness of consecutive systems, judged against a single stored predecessor, which makes the result an approximation of their own cost rather than its exact minimum. The other half of Ooloi's model, fixed space for clefs and signatures with one scale factor for everything else, is what Daniel Taupin, Ross Mitchell and Andreas Egler built into MusiXTeX in the mid-nineties. ADR-0037 now sets all of this out. Ooloi's own algorithm had been specified as Knuth–Plass from the start. What I hadn't expected was that it could be aligned with the original exactly. The atoms are the boxes, the spacing between them is the glue, and Ooloi's baseline is simply the case in which every piece of glue stretches in proportion to its natural width. So I aligned it fully, down to TeX's badness and demerits, with TeX's constants as starting points, and it's optimal in precisely Knuth's sense: the dynamic program finds the exact minimum of its own cost. That turned out to have real advantages. One of them I hadn't foreseen at all. Claude reasons far better about a forty-five-year-old algorithm, documented down to its last constant, than about anything bespoke. Once the cost had Knuth's shape, whole classes of question could be settled by reference instead of argument. None of this makes the algorithm Ooloi's; it's textbook, and the ADR says so. What Ooloi supplies is the conditions it needs. Knuth's algorithm wants stable inputs, and by the time Ooloi's pipeline reaches the breaking stage it has them, because information only flows forward. It's fast for a related reason: the earlier stages have already reduced the music to a very small set of numbers, a handful per bar, which are trivial to process even when the score runs to 800 pages and is set in Valhalla. The best layout can be recomputed while you type. For the person reading the part, the result should simply look right: systems evenly spaced from first to last, no cramped system beside a loose one, fewer breaks to force by hand. Stopping that layout from jumping about while you edit is a different problem, and the ADR deals with it in its own right. The glue has a further implication, one I haven't finished thinking through. The space after a whole note and the space after a sixteenth want different things. One is mostly air and can give a good deal in either direction. The other sits close to its neighbour: squeeze it and rhythm becomes collision, stretch it and a beamed group falls apart. Under the glue model the space after each note can have its own idea of how far it will stretch and how far it will give, and the two needn't match. The system then stops giving way in simple proportion, and if Knuth–Plass does what it should, the breaks are still optimal. That seems to me very close to how a human engraver reasons about whitespace.
3 Comments
Peter Bengtson
28/9/2026 11:12:06
A postscript on the lineage. Two descendants of Hegazy and Gourlay's work can now be traced. LilyPond's breaker, adapted from their report, was a straightforward dynamic program until October 1999 (release 1.2.14), when a term comparing each system with its predecessor was added; with a single predecessor stored per breakpoint, the result became an approximation of its own cost. That term survives in LilyPond's current breaker. And in April 2026, Daniel Spreadbury wrote on the Steinberg forum that the paper informed Dorico's casting off, which takes a greedy approach with separate handling of the remainder at the end of each flow, rather than a global optimum.
Reply
Magnus Johansson
5/10/2026 07:57:16
How is it going, Peter? Have you had the opportunity to study the work of Hegazy and Gourlay?
Reply
Peter Bengtson
5/10/2026 09:33:53
Indeed I have! Blog post upcoming.
Reply
Leave a Reply. |
AuthorPeter Bengtson – SearchArchives
November 2026
Categories
All
|
|
|
Ooloi is an open-source desktop music notation system for musicians who need stable, precise engraving and the freedom to notate complex music without workarounds. Scores and parts are handled consistently, remain responsive at scale, and support collaborative work without semantic compromise. They are not tied to proprietary formats or licensing.
Ooloi is currently under development. No release date has been announced.
|
RSS Feed