3 LilyGuts - doco to the internals of GNU LilyPond
7 This page documents some aspects of the internals of GNU LilyPond. Some of
8 this stuff comes from e-mail I wrote, some from e-mail others wrote,
9 some are large comments taken away from the headers
11 You should use doc++ to take a peek at the sources.
13 [have to do more doco; see TODO]
17 GNU LilyPond is a "5-pass" system:
23 No difficult algorithms. Associated datastructures have prefix Input
24 (eg Input_score, Input_command)
28 Requests are processed and granted. This is done by three cooperating
29 structeres: Staff, Staff_walker and Staff_column. In this step
30 data-structures for 3. are created and filled with data: PScore, PCol,
35 This step uses structures which have names starting with 'P'.
36 linebreaks and horizontal positions of PCols are determined. Line_of_*
39 =item 4. Postprocesing:
41 Some items and all spanners need computation after the PCol positions
46 Very simple, just walk all Line_of_* and follow the links over there
50 Some of the important requests are:
56 Checks during music processing if start of this voice element
57 coincides with the start of a measure. Handy to check if you left out
62 Staff has to decide if the ball should be hanging left or right. This
63 influences the horizontal dimensions of a column, and this is why
64 request processing should be done before horizontal spacing.
66 Other voices' frivolities may cause the need for accidentals, so this
67 is also for the C<Staff> to decide. The C<Staff> can decide on positioning
68 based on ottava commands and the appropriate clef.
76 This type of request typically results in the creation of a C<Spanner>
82 Staff has to combine this request with the stem_request, since the
83 number of flags that a stem wants to carry will determine the
88 Each dynamic is bound to one note (a crescendo spanning multiple
89 notes is thought to be made of two "dynamics": a start and a stop).
90 Dynamic changes can occur in a smaller time than the length of its
91 note, therefore fore each C<Dynamic> request carries a time, measured
92 from the start of its note.
103 The result of a request will be an C<Item> or a C<Spanner>, which
104 will be put on a C<PStaff>. Note that the C<PStaff> and the original
105 C<Staff> need not have anything in common. For example, the
106 ``double'' piano Staff could interpret commands which juggle
107 melodies across the left and right hand, and may put the result in
108 two five-line PStaffs (maybe with extra PStaffs to carry the dynamic
111 The class C<Staff> should be thought as a container for the
112 C<Voice>s, and an interpreter for C<Request>s.
113 Different staffs can produce different outputs; a melodious voice
114 which is put into a percussion-Staff, will be typeset as the rythm of
117 After C<Staff> made up her mind, the resultant items and
118 spanners are put on the PScore.
121 =head1 Request_register
123 In the previous section the idea of Request has been explained, but
124 this only solves one half of the problem. The other half is
125 deciding which requests should be honored, which should merged with
126 other requests, and which should be ignored. Consider this (pseudo)input
133 Both the c and e are part of a chord (they are in the same
134 Voice_group), so they should share the beams, and the two [ ] pairs
135 should be merged. The slurs OTOH are specific for each voice, so they
136 should not be shared.
138 The judge in this "allocation" problem is Staff (actually, it's child
139 C<Complex_staff>). It uses the C<Request_register> to do most of the
140 work. For each request C<Complex_staff> queries so-called
141 C<Request_register>s if they want to accept a request eg, the
142 C<Notehead_register> will accept C<Note_req>s, and turn down
143 C<Slur_req>s. If C<Complex_staff> cannot find a register that wants
144 the request, it is junked (with a warning message).
146 After all requests have been either assigned, or junked, the Register
147 will process the requests (which usually means creating an C<Item> or
148 C<Spanner>). If a C<Request_register> creates something, it tells
149 C<Complex_staff>. If all requests have been processed, then each
150 Register is notified of any created Staff_element.
158 note_request (duration 1/4)
159 stem_request (duration 1/4)
161 note_request will be taken by a C<Notehead_register>, stem_request
162 will be taken by a C<Stem_beam_register>. C<Notehead_register> creates
163 a C<Notehead>, C<Stem_beam_register> creates a C<Stem>. Both announce
164 this to the Staff. Staff will tell C<Stem_beam_register> about the
165 C<Notehead>, which will add the C<Notehead> to the C<Stem> it just
168 To decide on merging, C<Complex_staff> has grouped several
169 registers. There are a few groups:
183 Voice group, contains
202 [Source files: F<command.hh>, F<scommands.cc>]
204 BREAKING, PREBREAK POSTBREAK, etc.
206 So what's the deal with PREBREAK and POSTBREAK and all this
209 Let's take text as an example. In German some compound
210 words change their spelling if they are broken: "backen" becomes
211 "bak-ken". TeX has a mechanism to deal with this, you would define
212 the spelling of "backen" in TeX in this way
214 \discretionary{bak-}{ken}{backen}
216 These 3 arguments are called "prebreak", "postbreak" and "nobreak"
219 The same problem exists when typesetting music. If a line of music is
220 broken, the next line usually gets a clef. So in TeX terms, the clef
221 is a postbreak. The same thing happens with meter signs: Normally the
222 meter follows the bar. If a line is broken at that bar, the bar along
223 with the meter stays on the "last" line, but the next line also gets a
224 meter sign after the clef. Using the previous notation,
226 \discretionary{bar meter}{clef meter}{ bar meter }
228 In GNU Lilypond, we have the same concepts (and the same
229 terminology). Each (nonrhythmic) symbol is typeset using a Command
230 (code: TYPESET). At a breakpoint, TYPESET commands can be grouped
231 using separators (in lower case):
233 BREAK_PRE, typeset(bar), typeset(meter),
234 BREAK_MID, typeset(bar), typeset(meter),
235 BREAK_POST, typeset(clef), typeset(meter), BREAK_END
237 The BREAK command sequence is terminated with BREAK_END, so other
238 commands (like INTERPRET) may follow this sequence.
242 I think my method is the most elegant algorithm i've seen so far.
243 Some terminology: I call a vertical group of symbols (notes) which
244 start at the same time a "column". Each line of a score has notes in
245 it, grouped in columns. The difference in starting time between those
246 columns makes it possible to determine ideal distances between those
261 (1 is a whole note, 2 a half note.)
263 time_difference (col1 , col2) = 0.5 wholes,
264 time_difference (col1 , col3) = 1 wholes,
265 time_difference (col2 , col3) = 0.5 wholes,
268 these differences are translated into ideal distances (these translations
269 have been the subject of discussion in this thread).
271 distance (col1,col2) = 10 pt
272 distance (col1,col3) = 14.1 pt
273 distance (col2,col3) = 10 pt
276 as you can see, these distance are conflicting. So instead of
277 satisfying all those ideals simultaneously, a compromise is sought.
279 This is Columbus' egg: GNU LilyPond attaches "springs" to each
280 column-pair. each spring has an equilibrium-position which is equal to
281 the above mentioned distance, so
283 spring (col1, col2) and spring (col2,col3) try to push column 1
284 and 3 away (to a distance of 20pt) from each other, whereas the spring
285 between col 1 and col 3 tries to pull those two together (to a
286 distance of 14.1 pt). The net result of this pushing and pulling is an
287 equilibrium situation (the pushing cancels the pulling), which can be
288 calculated as the solution of Quadratic program: it is the solution
289 with minimum potential energy, for you physicists out there.
291 This algorithm for doing one line, gives a "badness" parameter for
292 each line (the potential energy). Now one can use TeX's algorithm for
293 making paragraphs (using this new version of "badness"): one should
294 try to minimise the overall badness of a paragraph. GNU LilyPond also
295 uses the concept of pre- and post-breaks.
297 (actually, it is a bit more complicated: each column also has a
298 minimum distance to other columns, to prevent symbols from running
299 into symbols of other columns.)
305 [partly by Mark Basinski <basinski@arizona.edu>]
307 Herbert Chlapik, Die Praxis des Notengraphikers. Doblinger, 1987.
309 Maxwell Weaner and Walter Boelke, Standard Music Notation Practice,
310 revised edition by Arnold Broido and Daniel Dorff. Music Publisher's
311 Association of the United States Inc., 1993.
313 W.A. Hegazy and J. S. Gourlay. Optimal line breaking in music. In
314 ``Document Manipulation and Typography'', J.C. van Vliet (ed) 1988.
316 Ross, Ted. ``Teach yourself the art of music engraving and processing''
317 (3rd edition). Hansen House, Miami Beach, FL.
324 [This is about I<engraving> i.e. professional music typesetting, and includes
325 some good spacing tables]
327 Read, Gardner. ``Modern Rhythmic Notation.'' Indiana University Press, 1978.
329 Read, Gardner. ``Music Notation'' (2nd edition). Taplinger Publishing,
332 [This is as close to the ``standard'' reference work for music notation issues
333 as one is likely to get.]
336 =head2 Further reading
338 (of varying usefulness):
340 Donato, Anthony. Preparing Music Manuscript. Englewood Cliffs:
343 Donemus. "Uitgeven van muziek". Donemus Amsterdam, 1900
345 Heussenstamm, George. The Norton Manual of Music Notation. New York:
348 Karkoshka, Erdhard. Notation in New Music. Trans. Ruth Koenig. New York:
349 Praeger Publishers, 1972. Out of print.
351 Roelofs, Ren\'e. ``Een Geautomatiseerd Systeem voor het Afdrukken van
352 Muziek'' afstudeerscriptie Bestuurlijke informatica, no 45327, Erasmus
353 universiteit Rotterdam, 1991. (``An automated system for printing
354 music'' Master's Thesis Management and Computer Science.)
356 C. Roemer, The Art of Music Copying. Roerick music co., Sherman Oaks
359 Rosecrans, Glen. Music Notation Primer. New York: Passantino, 1979.
361 Stone, Kurt. Music Notation in the Twentieth Century. New York: Norton, 1980.
364 =head2 On typesettig programs
366 From: Miguel Filgueiras <mig@ncc.up.pt>
368 ... as well as other systems. I contribute with some references:
371 D. Blostein, L. Haken, The Lime Music Editor: a Diagram Editor
372 Involving Complex Translations. {\em
373 Software --- Practice and Experience}, Vol. 24(3), 289--306, 1994.
375 Alexander Brinkman, {\em PASCAL Programming for Music Research}.
376 The University of Chicago Press, 1990.
378 Miguel Filgueiras, Implementing a Symbolic Music Processing
379 System. LIACC, Universidade do Porto, 1996; submitted.
381 Miguel Filgueiras, Some Music Typesetting Algorithms. LIACC,
382 Universidade do Porto, {\em forthcoming}.
384 Miguel Filgueiras and Jos\'e Paulo Leal, A First Formulation of
385 \SceX, a Music Typesetting System. Centro de Inform\'atica da
386 Universidade do Porto, 1993.
388 Miguel Filgueiras and Jos\'e Paulo Leal. Representation and
389 manipulation of music documents in \SceX. {\em Electronic Publishing},
390 vol. 6 (4), 507--518, 1993.
392 Eric Foxley, Music --- A language for typesetting music scores. {\em
393 Software --- Practice and Experience}, Vol. 17(8), 485--502, 1987.
395 John S. Gourlay, A language for music printing. {\em Communications of
396 the ACM}, Vol. 29(5), 388--401, 1986.
398 Cindy Grande, NIFF6a Notation Interchange File Format.
399 Grande Software Inc., 1995. {\tt ftp:blackbox.cartah.washington.edu}
401 Fran\c{c}ois Jalbert, Mu\TeX\ User's Guide (Version $1.1$). Computer
402 Science Department, University of British Columbia, 1989.
404 Peter S. Langston, Unix music tools at Bellcore. {\em
405 Software --- Practice and Experience}, Vol. 20(S1), S1/47--S1/61, 1990.
407 Andreas Mahling, J. Herczeg, M. Herczeg and S<H.-D.> B\"ocker, Beyond
408 visualization: knowing and understanding. In P.~Gorny, M.~J. Tauber
409 (eds.), {\em Visualization in Human-Computer Interaction}, Lecture
410 Notes in Computer Science, 439, 16--26, Springer-Verlag, 1990.
412 Jan Nieuwenhuizen, Using \TeX\ and the MusiX\TeX\ macro package to
413 write parts and scores of music. Department of Physics, Eindhoven
414 University of Technology, 1995.
416 Don Simons, PMX, A Preprocessor for MusiX\TeX\ (Version 1.04).
419 Daniel Taupin. Music\TeX: Using \TeX\ to Write Polyphonic or
420 Instrumental Music (Version 5.17). Laboratoire de Physique des
421 Solides, Centre Universitaire, Orsay, 1996.
423 Daniel Taupin, Ross Mitchell and Andreas Egler, Musix\TeX: Using \TeX\
424 to Write Polyphonic or Instrumental Music (Version T.64). Laboratoire
425 de Physique des Solides, Centre Universitaire, Orsay, 1993.
427 Barry Vercoe, Csound --- A Manual for the Audio Processing System and
428 Supporting Programs with Tutorials. Media Lab, M.I.T., Cambridge,
429 Massachusetts, 1986 (rev. 1992).
431 Chris Walshaw, {\tt ABC2M\TeX} --- An easy way of transcribing folk
432 and traditional music. School of Maths, University of Greenwich, 1993.