Re: Page and line penalties

[Joe Neeman]

On Wed, 29 Mar 2006 10:16, Han-Wen Nienhuys wrote:
> Joe Neeman wrote:
> > As far as I can tell, page and line penalties are used _only_ for
> > forbidding and forcing page breaks.
>
> correct
>
>  > Is there much chance they will ever be used for
> >
> > anything else? If not, they could be replaced by booleans - this would
> > make
>
> hopefully, we can use inverse durations of rests as penalties to provide
> a somewhat sensible automatic line/page breaking.
>
> One problem that needs to be solved is that the penalties are actually
> forces, but they does not translate to a scale that is sensible for
> users (or it does, but I don't know what scale)

Since you'll be away for a couple weeks, I'd like to bring this up now (the 
next 2 weeks is my mid-semester break so I want to get stuff done then).

My current working copy of lilypond does what you just said (using inverse 
rest durations for penalties). I've done some testing and tweaking and I've 
come to the conclusion that penalties are a bad idea. I think everything to 
do with page breaks, line breaks and page turns should be in terms of ALLOW, 
FORBID and FORCE.

I realise that this seems like a step backwards in terms of flexibility so 
I'll try to justify my reasoning. I'll just argue this for line breaks but 
the situation for page breaks and page turns is essentially the same.

Let f(L) be the force required for a single line of music L. f(L) is positive 
if L is overspaced and negative if L is underspaced. The line-breaking 
problem can be summarized as partitioning the music into lines L_i to 
minimize the sum of (f(L_i)^2. (We can also add things to enforce uniformity 
but that isn't a big detail).

Let F(B) = sum (f(L_i))^2 where B is a partition of the music into lines L_i 
(F(B) is the thing we want to minimize). Then the minimal B is "stable" for 
small changes in the music. What I mean by this is that if B minimizes F, and 
the user makes some small change (forbidding a breakpoint or adding a note 
for example), the new minimum of F will be close to B.

For example, if incrementing the number of breakpoints in B increases F(B) 
then adding 2 to the number of breakpoints in B will only increase F(B) more. 
This is good because it means that the user can change things predictably. If 
the user decides to forbid one particular breakpoint, they can be confident 
that the music won't suddenly blow up to twice the number of pages.


Suppose we add penalties. Let G(B) be the penalty function for a partition 
into lines. G(B) has no nice structure at all. It will probably be zero most 
of the time, with a few very large spikes. And we want to minimize F(B) + 
G(B). Suppose the user makes a small change:

F(B) before the change:
\                     /
 \                   /
  \                _/
   \_             /
     \__      __-/
        \__--/
min      ^^

F(B) + G(B) before the change:
\                     /\         /
 \                   /  \       /
  \                _/    \     /
   \_             /       \   /
     \__      __-/         \ /
        \__--/              - 
min      ^^

(So G(B) is zero except for a downward spike on the right.) The spike isn't 
big enough to make a difference yet. But now the user makes a small change to 
the music which causes a small change to F(B):

F(B) after the change:
\                /
 \              /
  \___        _/
      \_     /
        \___/
min       ^^

F(B) + G(B) after the change:
\                /\         /
 \              /  \       /
  \___        _/    \     /
      \_     /       \   /
        \___/         \ /
                       -
min                   ^^

So now the minimum has moved a long way away and the line breaking is 
drastically changed. All these functions are invisible to the user so they 
have no idea why all their spacing suddenly changed (or how to get the old 
spacing back if that's what they want). This makes two things very hard:

1) determining the default penalties. You can see in the above graphs that a 
small change in the penalty could produce a large change in the spacing. It's 
very difficult to find a nice balance that will work for a large number of 
cases. I've been playing around with different page turning penalties and the 
outputs can very so wildly that it's very hard to pick one.

2) overriding the breaking. I run a piece through lilypond and decide that, in 
one small part of the piece, the breaking isn't quite what I want (but the 
rest of the piece is fine). So I put in a \noBreak or something and my 
problem is solved -- except that lilypond has drastically changed all the 
other spacing in the piece due to some penalties that I couldn't have 
predicted. So I have to put in a lot more overrides to get the rest of the 
piece back to normal. And each of these overrides has more unpredictable 
consequences...

So that's my argument against penalties. I realise that you can make a 
statement like "we should not break beams across lines unless every other 
alternative is worse" which lends weight to the argument for penalties. But I 
think the unpredictability and instability of the result make it not 
worthwhile trying to do this automatically.

Joe

PS: This also solves the problem that the penalties are arbitrary values. 
Currently, Lilypond might conceivably ignore a user-forced \break if it 
causes the forces to work out too badly.