OOLOI.ORG
Menu

OOLOI

OVERVIEW

FAQ

DOCUMENTATION

NEWSLETTER

​Boxes & Glue

27/9/2026

3 Comments

 
Picture
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.

The same thread has a post by Basil Crow, author of the Neanes editor for Byzantine notation, on keeping Knuth–Plass optimal and linear-time when a break changes the width of neighbouring elements, which bears directly on the glue question above: https://forums.steinberg.net/t/optimal-line-breaking-algorithm/1028999

The original paper remains out of print; if anyone has a copy of the 1988 EP proceedings or the OSU report, I'd be glad to hear from them.

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.

    Author

    Peter Bengtson –
    Cloud architect, Clojure advocate, concert organist, opera composer. Craft over commodity. Still windsurfing through parentheses.

    Search

    Archives

    November 2026
    October 2026
    September 2026
    August 2026
    July 2026
    June 2026
    May 2026
    April 2026
    March 2026
    February 2026
    January 2026
    December 2025
    November 2025
    October 2025
    September 2025
    August 2025
    July 2025
    June 2025
    April 2025
    March 2025
    September 2024
    August 2024
    July 2024

    Categories

    All
    Accidentals
    Alfred Korzybski
    Architecture
    Backend
    Beaming
    Benchmarks
    Casting Off
    Clefs
    Clojure
    CLOS
    Common Lisp
    DDD
    Death Of Igor Engraver
    Documentation
    Donald E Knuth
    Dorico
    Dynamic Programming
    Finale
    Fonts
    FrankenScore
    Franz Kafka
    Frontend
    Functional Programming
    Generative AI
    GRPC
    Hegazy Gourlay
    Hegazy-Gourlay
    Igor Engraver
    Ingmar Bergman
    Instruments
    Jacques Derrida
    JVM
    Knuth Plass
    Knuth-Plass
    License
    LilyPond
    Lisp
    Localisation
    MIDI
    MPL 2.0
    MuseScore
    MusicXML
    Ooloi
    Ortography
    Pitches
    Platforms
    Playback
    Plugins
    Python
    QuickDraw GX
    Rendering
    Rhythm
    Rich Hickey
    Road Map
    Scheme
    Semiotics
    Sibelius
    Silicon Valley
    Site
    Skia
    Sponsorship
    Testing
    Transposition
    UI
    Umberto Eco
    Vertigo
    VST/AU
    Wednesday Addams

    RSS Feed

Home
​Overview
Documentation
About
Contact
Newsletter
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.


  • Home
  • Overview
    • Background and History
    • Project Goals
    • Introduction for Musicians
    • Introduction for Programmers
    • Technical Comparison
  • FAQ
  • Documentation
  • About
  • Contact
  • Workbench
  • Home
  • Overview
    • Background and History
    • Project Goals
    • Introduction for Musicians
    • Introduction for Programmers
    • Technical Comparison
  • FAQ
  • Documentation
  • About
  • Contact
  • Workbench