release: 0.0.62

[lilypond.git] / Documentation / lilygut.pod

=head1 NAME

LilyGuts - doco to the internals of GNU LilyPond

=head1 DESCRIPTION

This page documents some aspects of the internals of GNU LilyPond. Some of
this stuff comes from e-mail I wrote, some from e-mail others wrote,
some are large comments taken away from the headers

You should use doc++ to take a peek at the sources.

[have to do more doco; see TODO]

=head1 OVERVIEW

GNU LilyPond is a "5-pass" system:

=over 4

=item 1. Parsing:

No difficult algorithms. Associated datastructures have prefix Input
(eg Input_score, Input_command)

=item 2. Processing:

Requests are processed and granted. This is done by three cooperating
structeres: Staff, Staff_walker and Staff_column.  In this step
data-structures for 3. are created and filled with data: PScore, PCol,
PStaff

=item 3. Calculation:

This step uses structures which have names starting with 'P'.
linebreaks and horizontal positions of PCols are determined. Line_of_*
generated.

=item 4. Postprocesing:

Some items and all spanners need computation after the PCol positions
are determined.

=item 5. Output

Very simple, just walk all Line_of_* and follow the links over there

=back

Some of the important requests are:

=over 4

=item C<Barcheck_req>

Checks during music processing if start of this voice element
coincides with the start of a measure. Handy to check if you left out
some voice elts.

=item C<Note_req>

Staff has to decide if the ball should be hanging left or right. This
influences the horizontal dimensions of a column, and this  is why
request processing should be done before horizontal spacing.

Other voices' frivolities may cause the need for accidentals, so this
is also for the  C<Staff> to decide. The  C<Staff> can decide on positioning
based on ottava commands and the appropriate clef.

=item C<Rest_req>

Typeset a rest.

=item C<Span_req>

This type of request typically results in the creation of a C<Spanner>

=item C<Beam_req>

Start/stop a beam.

Staff has to combine this request with the stem_request, since the
number of flags that a stem wants to carry will determine the
number of beams.

=item  C<Dynamic>

Each dynamic is bound to one note (a crescendo spanning multiple
notes is thought to be made of two "dynamics": a start and a stop).
Dynamic changes can occur in a smaller time than the length of its
note, therefore fore each  C<Dynamic> request carries a time, measured
from the start of its note.

=head2 Voice

=head2 Voice_element

=head2 Voice groups

=head1 Requests

inc
The result of a request will be an C<Item> or a C<Spanner>, which
will be put on a C<PStaff>. Note that the C<PStaff> and the original
C<Staff> need not have anything in common. For example, the
``double'' piano Staff could interpret commands which juggle
melodies across the left and right hand, and may put the result in
two five-line PStaffs (maybe with extra PStaffs to carry the dynamic
signs and any lyric.

The class C<Staff> should be thought as a container for the
C<Voice>s, and an interpreter for C<Request>s.
Different staffs can produce different outputs; a melodious voice
which is put into a percussion-Staff, will be typeset as the rythm of
that voice.

After C<Staff> made up her mind, the resultant items and
spanners are put on the PScore.


=head1 Request_register

In the previous section the idea of Request has been explained, but
this only solves one half of the problem. The other half is
deciding which requests should be honored, which should merged with
other requests, and which should be ignored. Consider this (pseudo)input

        < % chord
                \music { [c() c] }
                \music { [e() e] }
        >

Both the c and e are part of a chord (they are in the same
Voice_group), so they should share the beams, and the two [ ] pairs
should be merged. The slurs OTOH are specific for each voice, so they
should not be shared.

The judge in this "allocation" problem is Staff (actually, it's child
C<Complex_staff>). It uses the C<Request_register> to do most of the
work.  For each request C<Complex_staff> queries so-called
C<Request_register>s if they want to accept a request eg, the
C<Notehead_register> will accept C<Note_req>s, and turn down
C<Slur_req>s. If C<Complex_staff> cannot find a register that wants
the request, it is junked (with a warning message).

After all requests have been either assigned, or junked, the Register
will process the requests (which usually means creating an C<Item> or
C<Spanner>). If a C<Request_register> creates something, it tells
C<Complex_staff>. If all requests have been processed, then each
Register is notified of any created Staff_element.

=head2 example:

        c4

produces:

        note_request (duration 1/4)
        stem_request (duration 1/4)

note_request will be taken by a C<Notehead_register>, stem_request
will be taken by a C<Stem_beam_register>. C<Notehead_register> creates
a C<Notehead>, C<Stem_beam_register> creates a C<Stem>. Both announce
this to the Staff. Staff will tell C<Stem_beam_register> about the
C<Notehead>, which will add the C<Notehead> to the C<Stem> it just
created.

To decide on merging, C<Complex_staff> has grouped several
registers. There are a few groups:

=item *

Staff wide, contains

        Local_key_register
        Bar_register
        Key_register
        Meter_register
        Clef_register

=item *

Voice group, contains

        Stem_beam_register
        Script_register
        Text_register

=item *

Voice, contains
        
        Slur_register
        Notehead_register


=item 1


=head1 BREAKING

[Source files: F<command.hh>, F<scommands.cc>]

BREAKING, PREBREAK POSTBREAK, etc.

So what's the deal with PREBREAK and POSTBREAK and all this
stuff?

Let's take text as an example. In German some compound
words change their spelling if they are broken: "backen" becomes
"bak-ken".  TeX has a mechanism to deal with this, you would define
the spelling of "backen" in TeX in this way

        \discretionary{bak-}{ken}{backen}

These 3 arguments are called "prebreak", "postbreak" and "nobreak"
text.

The same problem exists when typesetting music. If a line of music is
broken, the next line usually gets a clef. So in TeX terms, the clef
is a postbreak. The same thing happens with meter signs: Normally the
meter follows the bar. If a line is broken at that bar, the bar along
with the meter stays on the "last" line, but the next line also gets a
meter sign after the clef. Using the previous notation,

        \discretionary{bar meter}{clef meter}{ bar meter }

In GNU Lilypond, we have the same concepts (and the same
terminology). Each (nonrhythmic) symbol is typeset using a Command
(code: TYPESET). At a breakpoint, TYPESET commands can be grouped
using separators (in lower case):

        BREAK_PRE, typeset(bar), typeset(meter),
        BREAK_MID, typeset(bar), typeset(meter),
        BREAK_POST, typeset(clef), typeset(meter), BREAK_END 

The BREAK command sequence is terminated with BREAK_END, so other
commands (like INTERPRET) may follow this sequence.

=head1 SPACING

I think my method is the most elegant algorithm i've seen so far.
Some terminology: I call a vertical group of symbols (notes) which
start at the same time a "column".  Each line of a score has notes in
it, grouped in columns. The difference in starting time between those
columns makes it possible to determine ideal distances between those
columns.

Example:

                time ----->

                col1    col2    col3    col4


        voice1  1               1

        voice2  2       2       2       2


        (1 is a whole note, 2 a half note.)

        time_difference (col1 , col2) = 0.5 wholes,
        time_difference (col1 , col3) = 1 wholes,
        time_difference (col2 , col3) = 0.5 wholes,
        etc.

these differences are translated into ideal distances (these translations
have been the subject of discussion in this thread).

        distance (col1,col2) = 10 pt
        distance (col1,col3) = 14.1 pt
        distance (col2,col3) = 10 pt
        etc.

as you can see, these distance are conflicting. So instead of
satisfying all those ideals simultaneously, a compromise is sought.

This is Columbus' egg: GNU LilyPond attaches "springs" to each
column-pair.  each spring has an equilibrium-position which is equal to
the above mentioned distance, so

spring (col1, col2) and spring (col2,col3) try to push column 1
and 3 away (to a distance of 20pt) from each other, whereas the spring
between col 1 and col 3 tries to pull those two together (to a
distance of 14.1 pt). The net result of this pushing and pulling is an
equilibrium situation (the pushing cancels the pulling), which can be
calculated as the solution of Quadratic program: it is the solution
with minimum potential energy, for you physicists out there.

This algorithm for doing one line, gives a "badness" parameter for
each line (the potential energy). Now one can use TeX's algorithm for
making paragraphs (using this new version of "badness"): one should
try to minimise the overall badness of a paragraph. GNU LilyPond also
uses the concept of pre- and post-breaks.

(actually, it is a bit more complicated: each column also has a
minimum distance to other columns, to prevent symbols from running
into symbols of other columns.)

=head1 SEE ALSO

=head2 References

[partly by Mark Basinski <basinski@arizona.edu>]

Herbert Chlapik, Die Praxis des Notengraphikers. Doblinger, 1987.

Helene Wanske, ?, Schott-Verlag Mainz.

Maxwell Weaner and Walter Boelke, Standard Music Notation Practice,
revised edition by Arnold Broido and Daniel Dorff. Music Publisher's
Association of the United States Inc., 1993.
 
W.A. Hegazy and J. S. Gourlay. Optimal line breaking in music. In
``Document Manipulation and Typography'', J.C. van Vliet (ed) 1988.

Ross, Ted. ``Teach yourself the art of music engraving and processing'' 
(3rd edition). Hansen House, Miami Beach, FL.

        Hansen House
        1820 West Ave.
        Miami, FL  33139
        (305) 532-5461

[This is about I<engraving> i.e. professional music typesetting, and includes 
some good spacing tables]
 
Read, Gardner. ``Modern Rhythmic Notation.'' Indiana University Press, 1978.

Read, Gardner. ``Music Notation'' (2nd edition). Taplinger Publishing,
New York.
 
[This is as close to the ``standard'' reference work for music notation issues
as one is likely to get.]


=head2  Further reading

(of varying usefulness):

Donato, Anthony. Preparing Music Manuscript. Englewood Cliffs:
Prentice-Hall, 1963.

Donemus. "Uitgeven van muziek". Donemus Amsterdam, 1900
 
Heussenstamm, George. The Norton Manual of Music Notation. New York:
Norton, 1987.
 
Karkoshka, Erdhard. Notation in New Music. Trans. Ruth Koenig. New York:
Praeger    Publishers, 1972.  Out of print.

Roelofs, Ren\'e. ``Een Geautomatiseerd Systeem voor het Afdrukken van
Muziek'' afstudeerscriptie Bestuurlijke informatica, no 45327, Erasmus
universiteit Rotterdam, 1991.  (``An automated system for printing
music'' Master's Thesis Management and Computer Science.)

C. Roemer, The Art of Music Copying. Roerick music co., Sherman Oaks
(CA), 1973.

Rosecrans, Glen. Music Notation Primer. New York: Passantino, 1979.
 
Stone, Kurt. Music Notation in the Twentieth Century. New York: Norton, 1980.


=head2 On typesettig programs

From: Miguel Filgueiras <mig@ncc.up.pt>

... as well as other systems. I contribute with some references:


D. Blostein, L. Haken, The Lime Music Editor: a Diagram Editor
Involving Complex Translations. {\em
Software --- Practice and Experience}, Vol. 24(3), 289--306, 1994.

Alexander Brinkman, {\em PASCAL Programming for Music Research}.
The University of Chicago Press, 1990.

Miguel Filgueiras, Implementing a Symbolic Music Processing
System. LIACC, Universidade do Porto, 1996; submitted.

Miguel Filgueiras, Some Music Typesetting Algorithms. LIACC,
Universidade do Porto, {\em forthcoming}.

 Miguel Filgueiras and Jos\'e Paulo Leal, A First Formulation of
\SceX, a Music Typesetting System. Centro de Inform\'atica da
Universidade do Porto, 1993.

Miguel Filgueiras and Jos\'e Paulo Leal. Representation and
manipulation of music documents in \SceX. {\em Electronic Publishing},
vol. 6 (4), 507--518, 1993.

Eric Foxley, Music --- A language for typesetting music scores. {\em
Software --- Practice and Experience}, Vol. 17(8), 485--502, 1987.

John S. Gourlay, A language for music printing. {\em Communications of
the ACM}, Vol. 29(5), 388--401, 1986.

Cindy Grande, NIFF6a Notation Interchange File Format.
Grande Software Inc., 1995. {\tt ftp:blackbox.cartah.washington.edu}

Fran\c{c}ois Jalbert, Mu\TeX\  User's Guide (Version $1.1$). Computer
Science Department, University of British Columbia, 1989.

Peter S. Langston, Unix music tools at Bellcore. {\em
Software --- Practice and Experience}, Vol. 20(S1), S1/47--S1/61, 1990.

Andreas Mahling, J. Herczeg, M. Herczeg and S<H.-D.> B\"ocker, Beyond
visualization: knowing and understanding. In P.~Gorny, M.~J. Tauber
(eds.), {\em Visualization in Human-Computer Interaction}, Lecture
Notes in Computer Science, 439, 16--26, Springer-Verlag, 1990.

Jan Nieuwenhuizen, Using \TeX\ and the MusiX\TeX\  macro package to
write parts and scores of music. Department of Physics, Eindhoven
University of Technology, 1995.

Don Simons, PMX, A Preprocessor for MusiX\TeX\  (Version 1.04).
dsimons@logicon.com.

Daniel Taupin. Music\TeX: Using \TeX\  to Write Polyphonic or
Instrumental Music (Version 5.17). Laboratoire de Physique des
Solides, Centre Universitaire, Orsay, 1996.

Daniel Taupin, Ross Mitchell and Andreas Egler, Musix\TeX: Using \TeX\
to Write Polyphonic or Instrumental Music (Version T.64). Laboratoire
de Physique des Solides, Centre Universitaire, Orsay, 1993.

Barry Vercoe, Csound --- A Manual for the Audio Processing System and
Supporting Programs with Tutorials. Media Lab, M.I.T., Cambridge,
Massachusetts, 1986 (rev. 1992).

Chris Walshaw, {\tt ABC2M\TeX} --- An easy way of transcribing folk
and traditional music. School of Maths, University of Greenwich, 1993.