B13) PolyMake

L’algorithme au cœur de BP3

Le moteur caché

Quand BP3 transforme {drums, bass, melody} en une séquence temporelle où chaque voix est parfaitement synchronisée, une fonction fait tout le travail : PolyMake(), dans Polymetric.c. Elle n’a jamais été formellement documentée. Voici ce que nous savons.

Où se situe cet article ?

B5 a expliqué ce que fait la polymétrie dans BP3. B12 a montré comment _tempo() et le smooth time compliquent le calcul des durées. Ici, nous plongeons dans le comment : l’algorithme qui, à partir d’une expression polymétrique et de contraintes temporelles, produit une séquence d’événements ordonnés dans le temps.

 

Le problème que PolyMake() résout

Soit une expression polymétrique {v1, v2, ..., vk}. Chaque voix est une séquence d’éléments avec des durées (connues ou à calculer). PolyMake() doit produire une séquence unique d’événements horodatés où :

  1. Toutes les voix ont la même durée totale (la durée est fixée par le premier champ — voir B5)
  2. Chaque voix subdivise cette durée selon le nombre et les durées de ses éléments
  3. L’ordre temporel au sein de chaque voix est préservé
  4. Les undetermined rests (...) reçoivent une durée calculée pour remplir l’espace restant
  5. Les _tempo() modifient les durées localement

C’est un problème de constraint-satisfaction (satisfaction de contraintes) : trouver un placement temporel qui satisfait simultanément toutes ces exigences.

L’algorithme de base (sans complications)

Dans le cas le plus simple — pas de _tempo(), pas de ... — l’expansion est directe.

Entrée : {do re mi, fa sol la si}

Étape 1 — Calculer les durées nominales :

  • Voix 1 : 3 éléments → chaque note dure 1 unité symbolique
  • Voix 2 : 4 éléments → chaque note dure 1 unité symbolique

Étape 2 — Normaliser :

  • La durée totale est fixée par la voix 1 : 3 unités
  • La voix 2 (4 éléments, 4 unités nominales) est compressée dans 3 unités → chaque note dure 3/4

Étape 3 — Calculer les temps de début :

Événement Voix Temps début Durée
do 1 0 1
fa 2 0 3/4
sol 2 3/4 3/4
re 1 1 1
la 2 6/4 3/4
mi 1 2 1
si 2 9/4 3/4

Étape 4 — Fusionner et trier : les événements des deux voix sont fusionnés en une seule séquence triée par temps de début.

Les durées sont des rationnels (Q) — pas de flottants, pas d’arrondis (B12). C’est ce qui permet à BP3 de gérer des rapports comme 7 contre 5 sans erreur d’accumulation.

Complication 1 : les undetermined rests

Un repos indéterminé (...) est un silence dont la durée n’est pas fixée à l’avance. PolyMake() la calcule pour que la voix remplisse exactement la durée totale.

Exemple : {do re ..., fa sol la si}

La voix 2 (4 éléments) fixe la durée totale à 4 unités. La voix 1 a 2 notes (2 unités) + un .... Le repos indéterminé reçoit la durée restante : 4 – 2 = 2 unités.

Quand il y a plusieurs ... dans une voix, ils reçoivent des durées égales. Le système rejette les durées nulles — si l’espace restant est zéro, le repos n’est pas placé.

La minimisation (documentée sur bolprocessor.org) est le processus inverse : remplacer des silences déterminés par des ... quand c’est possible, pour simplifier la notation. L’algorithme de minimisation génère des chaînes de repos équivalents, les trie par fréquence, et sélectionne la solution avec le maximum de repos indéterminés.

Complication 2 : _tempo()

Un _tempo(2) dans une voix double la vitesse localement. Ça signifie que la durée réelle d’un élément après le _tempo() n’est plus sa durée nominale — elle est divisée par le facteur de tempo.

Le problème : la durée totale de la voix n’est plus simplement la somme des durées nominales. Il faut parcourir la voix en tenant compte de chaque changement de tempo pour calculer la durée « réelle ».

Si deux voix ont des _tempo() différents, la normalisation devient un système d’équations — les durées réelles dépendent du facteur de normalisation, qui dépend des durées réelles.

Bernard Bel (fév. 2026) : « Cette implémentation complique un peu l’algorithme d’expansion. »

Les deux algorithmes de Bel (1992)

Le paper « Two Algorithms » (Bel 1992, disponible sur bolprocessor.org) formalise le problème en deux étapes :

Algorithme 1 — Interprétation polymétrique

Résout les expressions polymétriques incomplètes en assignant des tempos symboliques. Transforme la notation en une séquence totalement ordonnée dans le temps symbolique.

Algorithme 2 — Time-setting

Un algorithme de constraint-satisfaction qui calcule les temps physiques précis de chaque message. Il prend en compte :

  • L’alignement des pivots (PivBeg, PivCent, etc.)
  • La troncature et l’élasticité des sound-objects
  • La relocalisabilité
  • Les propriétés métriques et topologiques des prototypes

Complexité : $O(n_{\max}^2 \cdot i_{\max}^3)$ dans le pire cas, où $n_{\max}$ est le nombre maximal d’objets et $i_{\max}$ le nombre maximal d’itérations de l’algorithme de backtracking.

C’est le seul endroit dans BP3 où Bernard Bel a utilisé du backtracking — un retour sur trace quand une solution partielle viole une contrainte. L’inspiration vient de Prolog.

PolyMake() comme ordonnanceur

PolyMake() est, dans les faits, un ordonnanceur sous contraintes :

Concept ordonnanceur Équivalent PolyMake()
Agents Éléments de chaque voix (notes, silences)
Ressource La ligne temporelle
Contraintes Durées, _tempo(), ..., synchronisation entre voix
Résultat Séquence d’événements horodatés

Contrairement aux ordonnanceurs temps-réel (EDF, Rate Monotonic), PolyMake() est offline : il calcule tout avant l’exécution. La séquence complète est résolue en mémoire, puis jouée.

Bernard Bel appelle ce processus le « time-setting » — le placement temporel des sound-objects sous contraintes. C’est le concept central de son approche, qui dépasse la simple notion de séquenceur.

Ce qu’il faut retenir

  1. PolyMake() est la fonction dans Polymetric.c qui résout l’expansion polymétrique — le cœur algorithmique de BP3
  2. Cas simple : normaliser les voix à la même durée, fusionner → $O(n \log n)$
  3. Undetermined rests (...) : durée calculée pour remplir l’espace restant
  4. _tempo() : modifie les durées localement → le calcul de normalisation devient un système d’équations
  5. Time-setting (Bel 1992) : constraint-satisfaction avec backtracking pour les sound-objects — $O(n^2 \cdot i^3)$
  6. L’algorithme n’a jamais été formellement documenté — l’extraction et la formalisation restent un travail ouvert

Pour aller plus loin

  • Bel, B. (1992) : « Two algorithms for the instantiation of structures of musical objects » — la formalisation des algorithmes 1 (interprétation polymétrique) et 2 (time-setting). PDF
  • Bel, B. (2001) : « Rationalizing Musical Time » — pourquoi les durées sont en Q (rationnels) et pas en flottants.
  • bolprocessor.org : Polymetric structures — documentation des undetermined rests
  • bolprocessor.org : Minimising a polymetric structure — l’algorithme de minimisation

Glossaire

  • PolyMake() : Fonction C dans Polymetric.c qui implémente l’expansion polymétrique. Non formellement documentée.
  • Expansion polymétrique : Transformation de {v1, v2} en séquence d’événements horodatés
  • Normalisation : Ajustement des durées pour que toutes les voix aient la même durée totale
  • Undetermined rest : Silence ... dont la durée est calculée par PolyMake()
  • Time-setting : Placement temporel des sound-objects sous contraintes (Bel 1992)
  • Constraint-satisfaction : Problème de trouver des valeurs qui satisfont un ensemble de contraintes
  • Backtracking : Technique algorithmique de retour sur trace quand une solution partielle échoue
  • Sound-object : Entité musicale avec propriétés métriques et topologiques, plus générale qu’une note

Liens dans la série

  • B5 — Polymétrie et structures temporelles — le quoi (PolyMake() est le comment)
  • B12 — Smooth time et _tempo() — les complications temporelles
  • B9 — Time-objects — les entités que PolyMake() place dans le temps
  • B11 — L’AST — le nœud Polymetric que PolyMake() résout

Prérequis : B5, B12
Temps de lecture : 14 min
Tags : #bp3 #polymake #polymetrie #algorithme #time-setting #constraint-satisfaction

← Retour à l’index