Les fonctions musicales 4. La récursivité

Traduction d’un article de Urs Liska

Nous conclurons aujourd’hui cette série d’articles sur les fonctions musicales avec LilyPond. J’ai pris soin de prendre mon temps dans les explications, parce que c’est justement ce qui manque à la documentation de Lilypond – par ailleurs excellente. Disons qu’en son temps, j’aurais aimé avoir ce genre d’explications…

Dans le premier article, nous avons vu comment insérer une fonction musicale dans les fichiers source LilyPond. Dans le second, nous avons commencé à écrire une fonction qui colorie une expression musicale donnée avec une couleur de notre choix, en ayant toutefois pratiqué du codage en dur et beaucoup de redondance. Le troisième article a été l’occasion d’aborder la factorisation et l’utilisation des listes. Nous n’avons pas pu atteindre notre but comme souhaité, ce qui sera fait dans ce quatrième article.

Dans un commentaire sur l’article précédent, Jay Anderson nous a montré une solution qui ne nécessite pas le recours à la récursivité : j’ai toutefois décidé de continuer sur la lancée qui était la mienne, mais gardez en mémoire que ce que je propose dans ce quatrième billet n’est pas LA solution, mais une parmi d’autres. La solution de Jay est sans doute la plus concise bien que requierant de nombreuses autres connaissances, en particulier l’utilisation de variables locales, qui diffère complètement d’autres langages de programmation. L’utilisation de variables locales en Scheme devrait faire l’objet d’un article à part, voire d’une autre série d’articles.

 La récursivité

Scheme est un dérivé du langage LISP – qui signifie « LISt Processing ». Le concept de listes, en Scheme comme dans tous les dérivés de LISP, est absolument incontournable. Aujourd’hui, je commence à en entrevoir les avantages, mais j’insiste sur le fait qu’il faut s’accrocher pour comprendre l’esprit de Scheme et, tant que vous n’avez pas intégré certains aspects spécifiques à ce langage, il vous sera difficile de vous en sortir. L’utilisation des listes fait partie de ceux-là.

Pour résoudre le problème en cours, appeler la fonction colorierDesSymboles pour chaque symbole de la liste, nous ferions ceci en Python :

for symbole in ma-liste-de-symboles:
    colorierSymbole(symbole, ma-couleur)

ce qui peut être directement traduit en français par : Pour chaque symbole de la liste ma-liste-de-symboles, passer à la fonction colorierSymbole les paramètres symbole et ma-couleur. En Scheme, vous allez faire tout autre chose en passant la fonction récursivement.

Les fonctions récursives sont des fonctions qui s’appellent elles-mêmes avec les paramètres modifiés. Le point très important est d’insérer dans le processus un point d’arrivée, sans quoi la boucle tourne indéfiniment. Le squelette d’une telle fonction est le suivant :

  • tester si on est arrivé à la fin et s’arrêter si cela est vrai ;
  • faire quelque chose avec les paramètres et appeler la fonction avec les paramètres modifiés.

Utiliser la récursivité sur une liste, c’est la plupart du temps faire quelque chose avec le premier élément de cette liste et appeler la fonction sur le reste de la liste. Le test du point d’arrivée est là pour vérifier s’il y a encore des éléments dans la liste.

Comme notre problème actuel est un peu complexe, étudions d’abord une fonction Scheme générique :

#(define (affiche-noms ma-liste-de-noms)
   (if 
    ;; vérifions s'il y a encore des noms dans la liste
    (null? ma-liste-de-noms)
      ;; non : nous sommes en fin de liste.
      ;; on laisse une ligne vide et on arrête
      (newline)
      ;; oui : il y a encore des éléments à traiter
      ;; fabriquons une expression composée
      (begin
       ;; affichons le premier élément et insérons une nouvelle ligne
       (display (car ma-liste-de-noms))
       (newline)
       ;; appelons récursivement la fonction 
       ;; avec le reste de la liste
       (affiche-noms (cdr ma-liste-de-noms))) ;; fin de la section "begin"
      ) ;; fin de la section "if"
   )

Voici donc une fonction Scheme nommée affiche-noms et qui a pour paramètre ma-liste-de-noms. Vous aurez noté que, contrairement aux autres fonctions que nous avons vues, celle-ci ne comporte pas de typage de paramètre ; c’est que le corps de cette fonction récursive sait qu’elle attend une liste. Les commentaires dans le code vous expliquent tout et complètent ce qui a été dit plus haut. Quelques remarques supplémentaires : pour que la section if puisse être fermée en Scheme/LilyPond, il faut lui ajouter des sections then et else, ce qui peut être omis dans d’autres dérivés Scheme. Aussi faut-il que vous soyez familiers avec les opérateurs car et cdr, ainsi qu’avec leur dérivés. car retourne le premier élément d’une paire ou d’une liste ; cdr retourne le second élément d’une paire, ou tous les éléments d’une liste excepté le premier – autrement dit le reste de la liste. En Scheme, on peut considérer qu’une liste est une paire avec comme premier élément le premier élément de la liste (car), et en second élément la liste des éléments restants de la liste (cdr).

On peut maintenant appeler la fonction ainsi : #(afficher-noms '(NoteHead Slur Flag Beam)) et voir une jolie liste affichée dans la console.

 Application à notre problème

Rappelez-vous, nous souhaitons écrire une fonction \colorierDesSymboles qui prend comme paramètre une liste de noms de symboles et une couleur. Dans l’article précédent, nous avons écrit le début de la fonction, sa signature. Nous allons maintenant profiter de ce qui est dit plus haut pour en compléter le corps. Cela donne :

colorierDesSymboles =
#(define-music-function (parser location ma-liste-de-symboles ma-couleur)
   (symbol-list? color?)
   (if (null? ma-liste-de-symboles)
       ;; donne une expression vide
       #{ #}
       #{
         % colorie le premier symbole de la liste restante (car)
         \colorierSymbole #(car ma-liste-de-symboles) #ma-couleur
         % appelle récursivement la fonction sur le reste de la liste (cdr)
         \colorierDesSymboles #(cdr ma-liste-de-symboles) #ma-couleur
       #}))

Nous écrivons donc une fonction qui prend pour paramètres une liste de symboles et une couleur. Quand la liste à traiter est vide, elle renvoit une expression vide et la boucle s’arrête (c’est très pratique : on peut ainsi écrire une expression vide pour arrêter la boucle, ce que nous ne pouvons pas faire en pur Scheme/LilyPond). S’il y a encore au moins un élément dans la liste, elle appelle la fonction \colorierSymbole en lui passant le premier élément de la liste restante (opérateur car) et la couleur en paramètres, et appelle ensuite récursivement la fonction \colorierSymbole sur la liste restante privée de son premier élément (opérateur cdr).

Il nous suffit maintenant d’écrire la fonction récursive \decolorierDesSymboles de la même façon. Je ne vais pas consacrer le reste de l’article à détailler cette fonction une nouvelle fois, mais vous pouvez télécharger l’exemple complet et inspecter le code.

 Nettoyons encore !

Bien ! Nous avons réussi à créer cette fonction qui prend en paramètre une expression musicale quelconque et lui applique une couleur de votre choix. Mais je ne vous lache pas encore : il y a encore quelques améliorations à apporter concernant les bonnes pratiques de codage. Le premier point concerne encore un peu de factorisation, le second permettra de rendre la fonction un peu plus générique.

 Factorisons encore un peu plus

Une chose qui me chagrine encore dans ce que nous venons d’écrire, c’est la répétition de certains bouts de code pour colorier et décolorer. Il serait judicieux de les regrouper en une fonction unique à laquelle on rajoutera un paramètre indiquant si l’on souhaite ajouter ou retirer la couleur.

Tout d’abord, modifions \colorierSymbole en lui ajoutant un paramètre couleur-plus de type booléen. S’il prend pour valeur #t (True), c’est \override qui s’applique, sinon c’est \revert :

colorierSymbole =
#(define-music-function (parser location symbole ma-couleur couleur-plus)
   (symbol? color? boolean?)
   (if couleur-plus
       #{
         \temporary \override #symbole #'color = #ma-couleur
       #}
       #{
         \revert #symbole #'ma-couleur
       #}))

La modification de \colorierDesSymboles est encore plus simple. Nous n’aurons pas besoin d’ajouter une nouvelle condition, mais juste de compléter la liste des paramètres avec le booléen couleur-plus, que nous passerons à \colorierSymbole.

colorierDesSymboles =
#(define-music-function (parser location ma-liste-de-symboles ma-couleur couleur-plus)
   (symbol-list? color? boolean?)
   (if (null? ma-liste-de-symboles)
       ;; donne une expression vide
       #{ #}
       #{
         % colorie le premier symbole de la liste restante (car)
         \colorierSymbole #(car ma-liste-de-symboles) #ma-couleur #couleur-plus
         % appelle récursivement la fonction sur le reste de la liste (cdr)
         \colorierSymbole #(cdr ma-liste-de-symboles) #ma-couleur #couleur-plus
       #}))

Voilà, notre fonction générale appelle correctement la sous-fonction. Cela dit, pour enlever la couleur, nous appelons aussi \colorierSymbole avec le paramètre ma-couleur, alors que \decolorierSymbole n’utilisait pas ce paramètre ; ceci est incohérent. Normalement, il ne faut pas introduire d’incohérence en programmation, mais laissons cela pour aujourd’hui, d’abord parce que ce n’est pas très grave dans ce cas, et ensuite parce que cela ne va pas gêner l’utilisateur (il ne voit pas ce code). Une solution propre serait d’utiliser des paramètres optionnels qui feront l’objet d’un article ultérieur. Comme d’habitude, je vous fournis le code complet en téléchargement, et vous pourrez voir comment il faut faire.

 Utilisation d’une liste générique de symboles (grobs)

La dernière chose à faire pour améliorer notre fonction concerne la liste d’objets musicaux à passer en paramètre. Elle n’est pas pratique à utiliser : il faut taper beaucoup de noms, et nous en oublions. Heureusement, LilyPond fournit un moyen de rendre tout cela générique : la fonction all-grob-descriptions. Elle retourne une liste de paires, chaque paire étant constituée d’un nom de symbole et d’une liste de ses propriétés. Utilisons maintenant ce que nous avons appris : map, lambda, car et cdr.

Nous avons besoin de la liste complète des symboles, c’est-à-dire de la liste des premiers éléments de la liste all-grob-descriptions. Il nous faut donc faire map sur cette liste, et transférer les car dans une autre liste. C’est justement ce que fait map, souvenez-vous. Nous allons aussi utiliser lambda pour créer une telle fonction.

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

C’est tout ! La fonction passée en paramètre de lambda récupère tous les premiers éléments de all-grob-descriptions et map fournit la liste de ces éléments. Nous avons donc récupéré la liste des noms de tous les symboles (grobs) de Lilypond ! Vérifiez cela en plaçant dans un fichier .ly :

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

et en compilant ce fichier. Vous n’obtiendrez pas un PDF, mais juste la liste dans la console.

La dernière étape consiste à insérer cette ligne dans une nouvelle fonction Scheme et à l’appeler quand nous aurons besoin de cette liste de symboles :

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

colorierMusique =
#(define-music-function (parser location ma-couleur ma-musique)
   (color? ly:music?)
   #{
     \colorierDesSymboles \tousLesSymboles #ma-couleur ##t

     #ma-musique

     \colorierDesSymboles \tousLesSymboles #ma-couleur ##f
   #})

Une remarque importante : l’utilisation de \tousLesSymboles ralentit significativement la compilation de notre fichier test. Je n’ai pas vérifié pour un fichier musique plus lourd, mais il vous faudra étudier, dans le cadre d’un projet plus vaste, s’il ne vaut pas mieux écrire une liste de symboles à la main plutôt qu’utiliser all-grob-descriptions.

Voici donc le fichier final – bien plus concis que le premier ! – et la partition qui en résulte (identique à celle précédemment rencontrée, ce qui est normal !).

\version "2.18.0"

colorierSymbole =
#(define-music-function (parser location symbole ma-couleur couleur-plus)
   (symbol? color? boolean?)
   (if couleur-plus
       ;; ou bien appliquer la couleur au symbole
       #{
         \temporary \override #symbole #'color = #ma-couleur
       #}
       ;; ou la retirer
       #{
         \revert #symbole #'ma-couleur
       #}))

colorierDesSymboles =
#(define-music-function (parser location ma-liste-de-symboles ma-couleur couleur-plus)
   (symbol-list? color? boolean?)
   (if (null? ma-liste-de-symboles)
       ;; donne une expression vide
       #{ #}
       #{
         % colorie le premier symbole de la liste restante (car)
         \colorierSymbole #(car ma-liste-de-symboles) #ma-couleur #couleur-plus
         % appelle récursivement la fonction sur le reste de la liste (cdr)
         \colorierSymbole #(cdr ma-liste-de-symboles) #ma-couleur #couleur-plus
       #}))

tousLesSymboles =
#(define-scheme-function (parser location)()
   ;; crée une liste avec tous les noms de symboles de Lilypond
   (map (lambda (gd) (car gd)) all-grob-descriptions))

colorierMusique =
#(define-music-function (parser location ma-couleur ma-musique)
   (color? ly:music?)
   #{
     \colorierDesSymboles \tousLesSymboles #ma-couleur ##t

     #ma-musique

     \colorierDesSymboles \tousLesSymboles #ma-couleur ##f
   #})


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

\relative c' {
  \colorierMusique #blue \ma-musique
  \colorierMusique #red { c4 c } d \colorierMusique #green e\f
  \colorierMusique #magenta \ma-musique
}
(Click to enlarge)

(Cliquez pour agrandir)

Comme vous pouvez le voir, notre projet initial, monolithique, s’est transformé en une série de petites fonctions ; nous pourrions encore factoriser et enlever les commentaires code. Ce procédé est courant avec Scheme : définir des fonctions de façon pyramidale, avec la plus générale à la base et les plus petites en tête de fichier. Cela est dû à la nature de Scheme qui manipule des expressions évaluées plutôt que des commandes exécutées. En Scheme, on n’écrit généralement pas des successions de commandes ou des boucles au sein d’une même fonction, mais plutôt une fonction qui appelle d’autres composants plus petits.

Bien entendu – et cela est important aux yeux de bon nombre des lecteurs – cette fonction va par la suite être isolée dans un fichier à part ; le fichiers musical source y fera appel grâce à \include, de façon à ce que le code musical ne soit pas pollué par de nombreuses lignes de Scheme.

Voilà, nous sommes arrivés à la fin de cette série d’articles. J’espère que vous avez eu plaisir à les lire et que vous avez appris quelque chose. Peut-être qu’écrire des fonctions Scheme vous fait moins peur désormais – ce sera en tous cas ma récompense ! Cela a été le cas pour moi, du moins. Personnellement, j’ai passé un cap dans
l’utilisation de Scheme – et j’attends maintenant le prochain moment où je n’arriverai plus à coder des fonctions apparemment simples…

N’hésitez pas à faire évoluer ces tutoriels grâce à vos commentaires, en posant des questions ou en ajoutant vos propres exemples. Et si vous avez des choses à dire sur ce sujet ou d’autres aspects de Scheme, contribuez en écrivant votre propre tuto !


Commentaires après la version anglaise

ming April 4, 2014 at 11:30

Urs : Merci pour ce code très bien fait. Maintenant, je comprends mieux
comment Scheme fonctionne, et cela va m’aider énormément la prochaine
fois que je lirai du Scheme.

Jay Anderson : les solutions n’utilisant pas la récursivité
m’intéressent. Peux-tu nous donner un exemple soit par la liste de
diffusion, soit sur le blog, pour expliquer aux débutants comment faire ?


Réponse ↓
Urs Liska April 4, 2014 at 11:31

Jay a donné un exemple dans l’article précédent.


Réponse ↓
ming April 4, 2014 at 11:45

Jay Anderson:
Désolé je n’avais pas vu. Merci pour l’exemple en commentaire de l’article 3 !


Réponse ↓
Paul Morris April 4, 2014 at 17:14

Belle série d’articles ! Quelques commentaires :

1 — On peut simplifier :

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

en écrivant :

(map car all-grob-descriptions)

on peut passer car directement à map sans l’envelopper dans une fonction lambda.

2 — Cela aussi peut être simplifié :

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

en faisant :

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

3 — Tu écris :

pour que la section if puisse être fermée en Scheme/Lilypond, il faut lui ajouter une section then et else, ce qui peut être omis dans d’autres dérivés Scheme.

Mais est-ce vrai ? Le code suivant fonctionne correctement sans section else :

\version "2.18.0"
  #(if (= 0 0)
      (display "yes"))

Réponse ↓
Urs Liska April 5, 2014 at 13:47

pour 1) et 2): Effectivement, j’ai constaté que cela marche, mais je ne comprends pas pourquoi. Si j’ai bien compris, (car all-grob-descriptions) est une paire constituée du nom de symbole et d’une liste comportant toutes ses propriétés et interfaces. Le car de cette paire est le nom du symbole. Je pensais donc passer la paire à la fonction lambda qui retourne le nom du symbole.

pour 3): un peu plus tard…


Réponse ↓
Jay Anderson April 6, 2014 at 02:16
pour (2) il faut savoir que car est déjà une fonction. Donc (lambda (gd) (car gd)) et car sont équivalents. il est donc normal que (map (lambda (gd) (car gd)) all-grob-descriptions)) et (map car all-grob-descriptions)) donnent le même résultat. Note aussi que cela définit le résultat de ce calcul en une passe. Tes problèmes de performance en seraient-ils résolus ?


Réponse : ↓
Urs Liska April 6, 2014 at 05:26
Eh bien nous avons ici un bon exemple de la difficulté à comprendre Scheme en profondeur 😉
Ce qui m’a mis dedans, c’est que (car all-grob-descriptions) est lui-même une paire :

(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)))

Et je pensais qu’en le passant directement à map, je retrouverais à nouveau une paire. Mais ce qui se produit réellement est que map récupère chaque élément de la liste en paramètre et renvoie en paramètre à la fonction chacun de ces éléments. Donc map envoie toutes ces paires à car, et car se charge d’extraire les premiers éléments de chaque paire, donc le nom de symbole.


Réponse ↓
Urs Liska April 6, 2014 at 05:49
OK ! grâce à tous ces renseignements je vais retirer tous les appels à allGrobNames et les remplacer par #(map car all-grob-descriptions) directement dans colorierMusique. De fait, le temps de compilation est réduit très significativement.

Cela dit, j’ai réalisé que cette liste est générée deux fois et qu’il y a encore redondance et donc allongement du temps de compilation. Je devrais utiliser let. Pour ceux qui veulent comprendre, voyez le commentaire de Jay dans un futur article 🙂

La fonction principale ressemble maintenant à ça :

colorierMusique =
#(define-music-function (parser location ma-couleur ma-musique)
   (color? ly:music?)
   (let ((gd (map car all-grob-descriptions)))
     #{
       \colorierDesSymboles #gd #ma-couleur ##t

       #ma-musique

       \colorierDesSymboles #gd #ma-couleur ##f
     #}))

Une autre piste serait de définir la liste des symboles comme variable globale calculée au premier appel de la fonction colorierMusique. Pour l’instant, elle est recalculée à chaque appel.


Réponse ↓
Ralf Mattes April 6, 2014 at 21:12

Pour éviter de recréer la liste à chaque appel de colorierMusique, tu peux la calculer une bonne fois pour toutes lors de la définition de la fonction et la clôturer, de telle sorte que ta fonction musicale devienne une fermeture (closure).

colorierMusique =
#(let ((noms-de-symboles (map car all-grob-descriptions)))
   (define-music-function (parser location ma-couleur ma-musique)
     (color? ly:music?)
     #{
       \colorierDesSymboles #noms-de-symboles #ma-couleur ##t
       #ma-musique
       \colorierDesSymboles #noms-de-symboles #ma-couleur ##f
     #}))

Tu éviteras ainsi de polluer l’espace de nommage global. Imagine que tu appelles ta variable GNoms etque quelqu’un définisse sa propre fonction qu’il appelle GNoms lui aussi.


Réponse ↓
Urs Liska April 6, 2014 at 22:12
Merci pour cette solution. Cela semble être une bonne idée. Mais pourrais-tu expliquer plus en détail ce qui se passe ? J’ai compris que tu as créé une variable locale noms-de-symboles et que tu as défini la fonction à l’intérieur de sa définition. Mais je ne comprends pas ce qui se passe en dehors de la fonction avec
ces variables et ce code.


Réponse ↓
Paul Morris April 7, 2014 at 21:41
Belle technique ! Voici ce que j’aicompris : let est évalué, mais que retourne-t-il ? Il renvoie une fonction musicale. Dans cette fonction, noms-de-symboles a déjà été évalué quand let l’a été. Ainsi, la valeur de noms-de-symboles est donc effectivement incluse dans la fonction retournée et stockée dans la variable colorierMusique.

Voir La fermeture informatique

Leave a Reply

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