Music Functions 4: Recursion

Today we’ll come to an end with a series of posts demonstrating how to write a comparably simple music function in LilyPond. I deliberately chose to describe the stuff with such verbosity and at that gentle pace because I think that’s what is missing in LilyPond’s (otherwise excellent) documentation. At least I think I would have greatly benefitted from that kind of explanation …

In the first part we started considering how to insert a Scheme music function in a LilyPond input file, and in the second part we started writing a function that colors an arbitrary function with an arbitrary color. While this was more or less hard-coded and exposed lots of redundant code we wanted to improve it in the third part through refactoring and list processing. Unfortunately this didn’t work out as easily as expected, and finally we’ll be solving the task through recursion today.

In a comment to the previous post Jay Anderson pointed out that there is another solution that doesn’t require using recursion. However I decided not to change the post that I had already written. So just keep in mind that the following post does not demonstrate the only approach but rather one of several different options. Apart from that I think that while Jay’s solution is actually more straightforward as a programming construct it would require considerably more previous knowledge and understanding. Using local variables with Scheme is completely different from other languages’ behaviour, so it would warrant a dedicated post or even series of posts.

Recursion

Scheme is a dialect of the LISP family of programming languages. “LISP” is derived from “LISt Processing”, and therefore lists are an ubiquituos concept in Scheme as in all other LISP languages. By now I can see some of the benefits of that approach, but I do insist on saying that it can be quite difficult to get into the spirit of things with Scheme. And until you have achieved this nearly everything about it can be extremely confusing. List handling is one of these things.

To solve our task of calling the coloring function for each grob type you would write something like this in Python:

for grob in my_grob_list:
    color_grob(grob, my_color)

which can be directly translated to English as “For each grob in the list my_grob_list please call the function color_grob, passing it the current grob and the general color my_color as arguments”. In Scheme you have to take a completely different approach by calling a function recursively.

Recursive functions are functions that call themselves with a modified argument list. A very important thing is to insert a check for a state to end the recursion because otherwise the program would get stuck in an infinite loop. The general outline for such a function is:

  • check for the exit state and leave the function if this is true
  • do something with the arguments and recursively call the function itself with modified arguments.

When using recursion to iterate over lists this usually means you will do something with the first element of the list and call the function with the remaining part of the list. The exit check can then determine if there are still list elements present to be processed.

Since our current case of a LilyPond music function complicates matters we’ll have a look at a generic Scheme function first:

#(define (display-names my-names-list)
   (if 
    ;; check if there still is a list element left
    (null? my-names-list)
      ;; no: we're at the end of the recursion
      ;; simply issue a new line and exit
      (newline)
      ;; yes: we still have elements to process
      ;; begin a compound expression
      (begin
       ;; display the first element and insert a new line
       (display (car my-names-list))
       (newline)
       ;; recursively call the function 
       ;; with the rest of the list
       (display-names (cdr my-names-list))) ;; end of begin
      ) ;; end of the if expression
   )

This defines a Scheme function with the name display-names and an argument my-names-list). Other than LilyPond’s music functions this doesn’t check the type of the argument, but the function body expexts it to be a list. Actually the code comments say it all, and it’s the implementation of what has been said above. The only thing to notice is that in LilyPond’s Scheme you have to give a “then” and an “else” expression to the if clause. In other Scheme dialects this may be omitted. And you should be very familiar with the car and cdr operators and their relatives. car returns the first element of a pair or list. cdr returns the second element of a pair, or with a list it returns a new list with all the elements of the list except for the first one (the “rest” of the list). (Or with Scheme lists you can consider a list to be a pair with one first element (the car) and the second element (the cdr) being a list on its own.)

Now you can call that function with #(display-names '(NoteHead Slur Flag Beam)) and see your list of grob types printed nicely in the console output.

Applying It To Our Task

You will recall that we wanted to write a function \colorGrobs that takes a list of grob names and a color as its arguments. In the last post we already wrote the function signature and now we can apply our recursion experience to write the body of that function. Finally it looks quite concise too:

colorGrobs =
#(define-music-function (parser location my-grob-list my-color)
   (symbol-list? color?)
   (if (null? my-grob-list)
       ;; issue an empty music expression
       #{ #}
       #{
         % color the first grob type of the current list
         \colorGrob #(car my-grob-list) #my-color
         % recursively call itself with the remainder
         % of the current list.
         \colorGrobs #(cdr my-grob-list) #my-color
       #}))

We define a music function that takes a list of grob names and a color as its arguments. When the list is empty the recursion stops by issuing an empty music expression. This is very handy as this way you can write an empty part for the if clause, something you can’t do in pure Scheme code in LilyPond. If there is an element left we call \colorGrob passing it the first list element as the grob name argument and then recursively call \colorGrobsitself with the grob name list stripped of its first element. That’s what we do with the car and cdr operators.

Now we have to write a corresponding \uncolorGrobs function and put everything togehter that we have done so far. I won’t spend all the screen estate to quote it all once more, but you can download the complete LilyPond file to run and inspect.

More Cleaning Up

OK, we have achieved our goal, a function that colors an arbitrary music expression in an arbitrary color. But I won’t let you go home now because there are still some things that can be improved with regard to “code hygiene”. The first issue will be some more factoring out to get rid of redundant code, the second will make the function still more generic.

Factoring Out Even More

One thing I don’t like about our solution so far is that we have to write several things twice, for coloring and uncoloring. It would make sense to merge the respective functions into one by providing yet another argument telling which direction we are going to do.

First we update our \colorGrob function to take an additional boolean color-on argument. If that is set to #t (true) we apply the \override, otherwise we \revert it:

colorGrob =
#(define-music-function (parser location my-grob my-color color-on)
   (symbol? color? boolean?)
   (if color-on
       #{
         \temporary \override #my-grob #'color = #my-color
       #}
       #{
         \revert #my-grob #'color
       #}))

The necessary change to our outer function \colorGrobs is even smaller. We don’t need to add a new conditional clause here but can simply extend the argument list by the boolean argument color-on and pass this on to \colorGrob unchanged.

colorGrobs =
#(define-music-function (parser location my-grob-list my-color color-on)
   (symbol-list? color? boolean?)
   (if (null? my-grob-list)
       ;; issue an empty music expression
       #{ #}
       #{
         % color the first grob type of the current list
         \colorGrob #(car my-grob-list) #my-color #color-on
         % recursively call itself with the remainder
         % of the current list.
         \colorGrobs #(cdr my-grob-list) #my-color #color-on
       #}))

Now we have to update our entry function \colorMusic to call the new internal function accordingly. Here we get a little inconsistency: Instead of calling \uncolorGrobs we now call \colorGrobs and have to pass a color as an argument although uncoloring doesn’t need a color information at all. I will accept this for today because it doesn’t add too much redundancy and because it is in code that the user won’t ever have to enter. The clean solution would be to work with optional arguments but we’ll defer this topic to a future post. As before I won’t copy all the stuff but provide the complete file for download.

Use a Generic Grob List

One last thing we will improve in our function is the list of grob names that has to be passed into the function. This requires some typing and especially it makes it somewhat random whether all relevant grobs have been taken care of. Fortunately LilyPond provides a means that can give us all we need to make this really generic: the all-grob-descriptions function. This produces a nested list of pairs, where each pair consists of a grob name and a list of its properties. Now we can make use of several things we learnt during this tutorial series: map, lambda, car and cdr.

What we need is a list of all grob names, that is the first element of all pairs that make up the all-grob-descriptions list. In other words we need to map the cars of all elements of this list to a new list. You should remember that map takes the elements of a list and passes it to a function and creates a new list of the results of that function, and we can use lambda to create this inner function ad-hoc.

(map (lambda (gd) (car gd)) all-grob-descriptions)

is all we need to perform this. The inner function will produce the car of all elements it is passed, map provides the elements of the all-grob-descriptions list and will produce the new list containing all grob names that LilyPond knows. You may check the result of this by displaying it. Just put

#(display (map (lambda (gd) (car gd)) all-grob-descriptions))

in an otherwise empty LilyPond file and compile it. This won’t produce a PDF but instead lists all available grob names in the console output.

The last step to do is to enclose this line in a newly written Scheme function and call this function when we need the list of grob names:

allGrobNames =
#(define-scheme-function (parser location)()
   (map (lambda (gd) (car gd)) all-grob-descriptions))

colorMusic =
#(define-music-function (parser location my-color music)
   (color? ly:music?)
   #{
     \colorGrobs \allGrobNames #my-color ##t

     #music

     \colorGrobs \allGrobNames #my-color ##f
   #})

One thing to note with this is that using \allGrobNames significantly slows down the compilation of our test music. I didn’t check the impact on large scores, but in the end you may have to evaluate the tradeoff between a generically comprehensive solution and processing speed in the context of your own concrete project.


As a final listing I will now print the whole file – which has become comparably short by now – and the resulting score – now the accidentals and dynamics are colored as well.

\version "2.18.0"

colorGrob =
#(define-music-function (parser location my-grob my-color color-on)
   (symbol? color? boolean?)
   ;; check for the boolean argument
   (if color-on
       ;; either set the color for the grob type
       #{
         \temporary \override #my-grob #'color = #my-color
       #}
       ;; or revert it
       #{
         \revert #my-grob #'color
       #}))

colorGrobs =
#(define-music-function (parser location my-grob-list my-color color-on)
   (symbol-list? color? boolean?)
   (if (null? my-grob-list)
       ;; issue an empty music expression
       #{ #}
       #{
         % color the first grob type of the current list
         \colorGrob #(car my-grob-list) #my-color #color-on
         % recursively call itself with the remainder
         % of the current list.
         \colorGrobs #(cdr my-grob-list) #my-color #color-on
       #}))

allGrobNames =
#(define-scheme-function (parser location)()
   ;; create a list with all grob names from LilyPond
   (map (lambda (gd) (car gd)) all-grob-descriptions))

colorMusic =
#(define-music-function (parser location my-color music)
   (color? ly:music?)
   #{
     \colorGrobs \allGrobNames #my-color ##t

     #music

     \colorGrobs \allGrobNames #my-color ##f
   #})

music = \relative c' {
  c4. d8 e16 d r cis( d4) ~ | d1 \fermata
}

\relative c' {
  \colorMusic #blue \music
  \colorMusic #red { c4 c } d \colorMusic #green e\f
  \colorMusic #magenta \music
}
(Click to enlarge)

(Click to enlarge)

As you can see our project has turned into a number of short functions (they could have been formatted even more concisely, and some of the comments could be left out in real life). It is characteristic when using Scheme to have many functions that are defined somewhat pyramidal: from the most broad functions at the bottom up to ever more specific and small functions at the top of the file. This is due to the nature of Scheme consisting of expressions that are evaluated rather than of commands that are executed. With Scheme you don’t generally write a chain of commands or loops within one function but rather replace any compound statement with a function call.

Of course – and explicitly pointing this out may be important to a significant share of the readers – I would now put all code above the music variable definition in a library file and \include this. So using the \colorMusic function doesn’t have any bigger impact on the structure and readability of the actual music input files.


We have come to the conclusion of our little series of tutorial posts. I hope you enjoyed them and have learned something along the way. Maybe writing Scheme functions isn’t all that daunting to you anymore – that would be a great outcome of my efforts. At least for me this was the case. I think I’ve taken the next step in tackling Scheme – of course I’m now waiting for the next occasion where I feel stupid not managing to cope with seemingly simple tasks …

Feel free to improve the tutorials by asking questions or adding examples in the comments. And if you have something to say on the matter or on other Scheme related topics don’t hesitate to contribute your own tutorial.

16 thoughts on “Music Functions 4: Recursion

  1. ming

    Urs:
    Thank you for the wonderful colorMusic scheme code. Now that I understand how scheme code works, it will helps me tremendously next time when I look at a scheme code and understand them.
    Jay Anderson: I am interested on another solution that no recursion. Can you post sample scheme code to the user list or Score of Beauty for us beginners to learn?

    Reply
  2. Paul Morris

    Nice series of posts. Here are a few points:

    1. This can be simplified:

    (map (lambda (gd) (car gd)) all-grob-descriptions)

    to:

    (map car all-grob-descriptions)

    You can just pass car directly to map so no need to wrap it in a lambda expression.

    2. This also can be simplified:

    allGrobNames =
      #(define-scheme-function (parser location)()
      (map (lambda (gd) (car gd)) all-grob-descriptions))

    to:

    allGrobNames = #(map car all-grob-descriptions)

    3. You say: “in LilyPond’s Scheme you have to give a “then” and an “else” expression to the if clause.” But is that right? The following works and has no “else” expression:

    \version "2.18.0"
      #(if (= 0 0)
          (display "yes"))
    Reply
    1. Urs Liska

      ad 1) and 2):
      Hm, I verified that it works, but I don’t understand why it does.
      As far as I understand (car all-grob-descriptions) is a pair consisting of the grob name and a list with all properties and interfaces. The car of that pair is the grob name itself. So I thought I pass the pair to the lambda function, which then returns the grobname.

      ad 3): later …

      Reply
      1. Jay Anderson

        For (2) notice that car is already a function. So (lambda (gd) (car gd)) and car are equivalent. So (map (lambda (gd) (car gd)) all-grob-descriptions)) and (map car all-grob-descriptions)) produce the same result. Also note that this sets the result of this computation once. So your performance concerns may also be fixed by this change.

        Reply
        1. Urs Liska

          Well, I might say what we have here is a “live example” of how reluctant Scheme may be to be understood 😉

          I was tricked by the fact that (car all-grob-descriptions) is itself a pair:

          (car all-grob-descriptions)
          (Accidental (alteration . #<procedure accidental-interface::calc-alteration (grob)>) (avoid-slur . inside) (glyph-name . #<procedure accidental-interface::glyph-name (grob)>) (glyph-name-alist (0 . "accidentals.natural") (-1/2 . "accidentals.flat") (1/2 . "accidentals.sharp") (1 . "accidentals.doublesharp") (-1 . "accidentals.flatflat") (3/4 . "accidentals.sharp.slashslash.stemstemstem") (1/4 . "accidentals.sharp.slashslash.stem") (-1/4 . "accidentals.mirroredflat") (-3/4 . "accidentals.mirroredflat.flat")) (stencil . #<primitive-procedure ly:accidental-interface::print>) (horizontal-skylines . #<unpure-pure-container #<primitive-procedure ly:accidental-interface::horizontal-skylines> >) (vertical-skylines . #<unpure-pure-container #<primitive-procedure ly:grob::vertical-skylines-from-stencil> #<primitive-procedure ly:grob::pure-simple-vertical-skylines-from-extents> >) (X-extent . #<primitive-procedure ly:accidental-interface::width>) (Y-extent . #<unpure-pure-container #<primitive-procedure ly:accidental-interface::height> #<primitive-procedure ly:accidental-interface::pure-height> >) (meta (name . Accidental) (class . Item) (interfaces grob-interface accidental-interface font-interface inline-accidental-interface item-interface)))

          And I thought that if that would be passed to map I would get the car of that once more. But what happens in fact is: map processes all elements of the input list and passes each element to the given function. So map passes all the pairs like the above to car, and car will extract the first element of the pair – i.e. the grob name.

          Didn’t I introduce the post series as a documentation of my own thorny learning path? 😉

          Reply
          1. Urs Liska

            OK, thanks to these comments I could remove the allGrobNames function and replace it by writing #(map car all-grob-descriptions) directly inside colorMusic. In fact this significantly reduces the compilation time.

            But then I realized that this list will be generated twice which is still redundant and takes unnecessery calculation time. Using let I could remove this too. For an explanation I refer to Jay’s upcoming post 🙂

            The function now looks like this:

            colorMusic =
            #(define-music-function (parser location my-color music)
               (color? ly:music?)
               (let ((gd (map car all-grob-descriptions)))
                 #{
                   \colorGrobs #gd #my-color ##t
            
                   #music
            
                   \colorGrobs #gd #my-color ##f
                 #}))

            One more idea now would be to define the list of grob names as a global variable that gets calculated the first time colorMusic is called. In the current form it will be built from scratch each time colorMusic is run.

            Reply
            1. Ralf Mattes

              To avoid recreating the list of grob names every time colorMusic gets called you can use calculate it once during function definition and then close over it (so your music function is actually a closure)

              colorMusic =
              #(let ((grob-names (map car all-grob-descriptions)))
                 (define-music-function (parser location my-color music)
                   (color? ly:music?)
                      #{
                        \colorGrobs #grob-names #my-color ##t
                        #music
                        \colorGrobs #grob-names #my-color ##f
                        #}))

              That way you avoid cluttering the global namespace (just imagine you name your global GNames and then someone defines his/her own function called GNames as well).

              Reply
              1. Urs Liska

                Thanks for that suggestion. Looks like a good idea. But could you expand a little bit on what actually happens there? I see that you create a local variable grob-names and inside its scope define the actual music function.

                But I don’t see what happens with that code and variables once your outside of the function definition.

                Reply
  3. Pingback: Local Variables in Scheme / LilyPond | Scores of Beauty

  4. Pingback: Les fonctions musicales 4. La récursivité | Scores of Beauty

  5. gohier frederic

    Hello,

    I am a newbie in scheme in lilypond, however use informatic program languages ( perl, python, pascal, C ) .

    I just read – probably need another time to understand all – the scheme documentation in lilypond, why don’t you use the ability of scheme provided in http://www.schemers.org/Documents/Standards/R5RS/ , like ‘do’ or ‘let loop’ ?
    Are they prohibited in lilypond or only not explained and probably not tested in this latest case ?

    Thanks for your feedbacks

    Reply
  6. Peter Gentry

    I find with 2.19.15 the following works without warning messages

    colorMusic =
    #(let ((grob-names (map car all-grob-descriptions)))
       (define-music-function (parser location my-color music)
         (color? ly:music?)
         #{
           \colorGrobs #grob-names #my-color
           #music
         #}))
    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *