B6) Homomorphismes, variables et contexte

Quand BP3 dépasse les grammaires context-free

Certaines constructions de BP3 ne peuvent pas s’exprimer dans une grammaire context-free classique. Elles introduisent de la mémoire, du contexte et du contrôle de flux.

Où se situe cet article ?

Après avoir couvert les probabilités (B1), le vocabulaire (B2), les règles de dérivation (B3) et le contrôle dynamique (B4), cet article explore les constructions avancées de BP3 (Bol Processor 3, cf. I2) : variables, homomorphismes, wildcards et marqueurs de contexte. Ces mécanismes font de BP3 un système bien plus puissant qu’une simple grammaire context-free — ils le rapprochent des grammaires context-sensitive (L1), voire des langages Turing-complets. Les détails de la traduction en code SuperCollider sont traités dans B7.

Pourquoi c’est important ?

Une grammaire context-free (CFG, Context-Free Grammar — grammaire hors-contexte) est un outil élégant mais limité. Elle ne peut pas exprimer certaines contraintes pourtant naturelles en musique :

  • Répéter exactement le même motif : si un thème apparaît deux fois dans une pièce, une CFG ne peut pas garantir que les deux occurrences soient identiques. Chaque dérivation est indépendante.
  • Transformer un motif selon une règle externe : transposer une mélodie en mineur, appliquer un renversement — ces opérations nécessitent une mémoire de ce qui a été joué.
  • Réagir au contexte : jouer un motif différent selon ce qui précède ou ce qui suit.

Prenons une analogie avec le kathak, la danse classique du nord de l’Inde, intimement liée au tabla et à BP3. Une CFG, c’est un chorégraphe kathak qui donne des instructions générales : « fais un tatkar (pas rythmique), puis un chakkar (pirouette) ». Mais il ne peut pas dire « refais exactement le même tatkar qu’avant » ou « si le tabliste a joué un dha (bol résonant), réponds par un tin (bol sec) ». Pour cela, il faut de la mémoire et de la sensibilité au contexte — exactement ce qu’apportent les constructions que nous allons explorer. Ce n’est pas un hasard : Bernard Bel et James Kippen ont développé BP3 précisément pour modéliser ces interactions entre tabla et danse dans la tradition de Lucknow [BelKippen1992a].

L’idée en une phrase

BP3 étend les CFG avec des variables (répétition exacte), des homomorphismes (transformation de motifs), des wildcards (pattern matching) et des marqueurs de contexte — des constructions qui font de BP3 un langage context-sensitive.

Expliquons pas à pas

1. Variables : le tihāī et la répétition exacte

Le problème

En musique indienne, le tihāī (cadence où un motif est répété exactement trois fois pour tomber sur sam, le premier temps du cycle tāla — le point de résolution rythmique vers lequel converge toute l’improvisation) exige que les trois répétitions soient identiques. Si j’écris :

 

gram#1[1] S --> A - A - A

 

En mode RND (Random — dérivation aléatoire, cf. B3), chaque A est dérivé indépendamment. Le premier A pourrait donner dha tirakita dhin et le deuxième tin ta ka. Ce n’est pas un tihāī — c’est trois motifs différents, et l’effet de cadence est perdu.

La solution BP3

BP3 introduit la variable avec la notation |x| (identifiant entre pipes) :

 

gram#1[1] S --> |x| - |x| - |x|

 

Cette règle se lit : « dérive quelque chose, appelle-le x, puis joue x deux autres fois — exactement la même chose, séparé par des silences ». La variable capture le résultat de la première dérivation et le réplique partout où elle apparaît. C’est exactement la structure d’un tihāī [BelKippen1992a].

Encart : Variable vs non-terminal

Ne confondez pas |x| (variable) avec un non-terminal. Un non-terminal est une catégorie qui sera dérivée indépendamment à chaque occurrence. Une variable est une liaison : la première occurrence fixe la valeur, les suivantes la réutilisent.

Construction Comportement
Non-terminal A Chaque occurrence dérivée indépendamment
Variable \|x\| Première occurrence fixe la valeur, les suivantes la répliquent

Exemple complet

 

gram#1[1] S --> |x| - |x| - |x|
gram#1[2] |x| --> dha tirakita dhin dhin
gram#1[3] |x| --> tin ta dha ge na

 

Résultat possible : dha tirakita dhin dhin - dha tirakita dhin dhin - dha tirakita dhin dhin — un tihāī parfait, où le même motif de bols est joué trois fois pour atterrir sur sam (premier temps du cycle).

Pourquoi c’est context-sensitive

Le lien avec la hiérarchie de Chomsky (L1) est direct. Le langage $\{ ww \mid w \in \Sigma^* \}$ — l’ensemble de toutes les chaînes formées d’un mot $w$ suivi de sa copie exacte, où $\Sigma^*$ (sigma étoile) désigne l’ensemble de tous les mots possibles sur l’alphabet $\Sigma$ (sigma) — n’est pas context-free. C’est un résultat classique : le pumping lemma (lemme de pompage — un outil de preuve qui montre qu’un langage ne peut pas être engendré par une CFG) l’interdit. Les variables de BP3 permettent d’exprimer exactement ce type de contrainte, ce qui place BP3 au niveau context-sensitive (Type 1) de la hiérarchie.

2. Homomorphismes : patterns et tables de correspondance

[!warning] Correction (mars 2026)

La version précédente de cette section décrivait les homomorphismes comme des « transformations note-à-note (transposition, inversion, rétrogradation) » avec l’exemple inventé (: mineur) (: rétrograde). C’est fondamentalement incorrect. La rétrogradation n’est pas un homomorphisme (elle inverse l’ordre, violant $h(\alpha\beta) = h(\alpha)h(\beta)$), et la syntaxe (: rétrograde) n’existe pas dans BP3. La correction ci-dessous est basée sur la documentation officielle de bolprocessor.org et l’analyse du code source C de BP3.

L’idée

Un homomorphisme en mathématiques est une fonction $h$ qui préserve la structure : $h(\alpha\beta) = h(\alpha)h(\beta)$. Chaque symbole est transformé indépendamment, et l’ordre est préservé. C’est crucial : la rétrogradation (inversion de l’ordre) n’est PAS un homomorphisme.

Dans BP3, les homomorphismes sont des tables de correspondance 1:1 — un symbole d’entrée donne un symbole de sortie. Ils sont définis dans des fichiers externes (-ho.*) et utilisés dans les patterns master/slave.

Le mécanisme master/slave

BP3 utilise deux marqueurs pour les patterns :

Marqueur Syntaxe Rôle
Master (= ...) Définit le motif de référence
Slave (: ...) Doit reproduire la même structure que le master

Exemple (bolprocessor.org) :

 

gram#1[1] S --> (= X) X (: X)

 

Cette règle signifie : le troisième élément (slave (:X)) doit correspondre au premier (master (=X)). Si le master est dérivé en a b, le slave doit aussi être a b. C’est une contrainte d’identité structurelle.

Les homomorphismes dans le fichier d’alphabet (-al.)

Les homomorphismes sont définis dans le fichier d’alphabet (-al.), pas dans un fichier séparé. Historiquement, Bernard Bel utilisait le préfixe -ho. pour un fichier dédié, mais aujourd’hui le fichier -al. contient les deux : la liste des terminaux ET les mappings d’homomorphismes.

 

// Fichier -al.abc : alphabet + homomorphisme "*"
*
a --> a' --> a''
b --> b'
c

 

L’homomorphisme s’appelle *. Les chaînes a --> a' --> a'' sont cycliques : appliquer * une fois → a devient a', a' devient a''. Si on ferme le cycle (a --> a' --> a'' --> a), appliquer 3 fois = revenir au départ.

Un terminal absent de la table reste inchangé : c n’a pas de mapping, donc *(c) = c.

Comment ça fonctionne

L’homomorphisme * apparaît dans les règles devant la parenthèse qu’il transforme :

 

S --> a * (= a') * * (= a) * (= a') * b (= a c)

 

Ici :

  • a → terminal direct
  • * (= a') → applique * au contenu du master → a' devient a''
  • * * (= a) → applique * deux fois → a → a' → a''
  • * (= a') → a' → a''
  • b → terminal direct
  • (= a c) → pas d’homomorphisme → a c reste a c… mais le slave pointe vers les masters, donc a est résolu via les pointeurs → a' et c reste c

Résultat : a a' a'' a'' b a' c

Les homomorphismes s’empilent : * * = appliquer deux fois. * * * = trois fois.

Quand sont-ils appliqués ?

Point crucial confirmé par Bernard Bel (mars 2026) : les terminaux sont remplacés par leurs images à la fin de la production, pour l’affichage — par la fonction SearchOrigin() dans DisplayArg.c. Pendant la dérivation, les parenthèses slaves contiennent des pointeurs vers le master, pas des copies transformées.

Les homomorphismes n’influencent pas le choix des règles pendant la dérivation. Ils ne modifient pas la structure temporelle. Deux grammaires identiques — l’une avec un homomorphisme, l’autre sans — produisent la même séquence temporelle. Seuls les noms des terminaux changent à l’affichage.

Formellement, un homomorphisme BP3 est un morphisme de monoïdes libres : $h : \Sigma^* \to \Sigma^*$ tel que $h(\alpha\beta) = h(\alpha)h(\beta)$. Chaque symbole est transformé indépendamment via la table p_Image[h][j], et l’ordre est toujours préservé.

Encart : Graha bheda — la transposition de raga comme homomorphisme

En musique indienne, le graha bheda (graha = note de départ, bheda = changement) est une technique où l’on redéfinit les correspondances entre degrés. C’est exactement ce que fait un fichier -ho. de BP3 : une table qui associe chaque note de l’alphabet à une autre note. La structure mélodique est préservée, seules les hauteurs changent — la définition même d’un morphisme [Bel1998].

Note : la rétrogradation (jouer la mélodie à l’envers) n’est pas un homomorphisme — elle inverse l’ordre, ce qui viole $h(\alpha\beta) = h(\alpha)h(\beta)$. BP3 la gère par d’autres mécanismes (la directive _retro).

3. Wildcards : capturer et transformer sans définir

Les wildcards (jokers) — notés ? (anonyme), ?1, ?2 (nommés) — introduisent du pattern matching (correspondance de motifs) dans les règles de grammaire. Ils sont analogues aux groupes de capture des expressions régulières (regex) : sur le côté gauche d’une règle, ?1 capture une portion arbitraire de la chaîne ; sur le côté droit, ?1 la réinjecte.

Les wildcards sont historiquement associés au mode ANAL (reconnaissance). En mode PROD, ils fonctionnent via les grammaires transformationnelles en couches : une première sous-grammaire génère une séquence avec des marqueurs, une seconde utilise les wildcards pour transformer cette séquence. Le wildcard opère sur la sortie d’une sous-grammaire précédente — c’est une réécriture inter-couches, pas de la génération directe.

En mode PROD : la réécriture context-sensitive

Imaginons une grammaire en deux étages. La première grammaire (GRAM#1) génère une séquence avec des marqueurs :

 

gram#1[1] S --> R1 dha tirakita dhin dhin R2

 

La seconde grammaire (GRAM#2) utilise des wildcards pour transformer cette séquence :

 

gram#2[1] R1 ?1 R2 --> ?1 ?1

 

Cette règle se lit : « trouve le motif R1…R2, capture tout ce qu’il y a entre les deux marqueurs (ici dha tirakita dhin dhin), et remplace le tout par deux copies de ce contenu capturé ». Résultat :

 

dha tirakita dhin dhin dha tirakita dhin dhin

 

Le wildcard ?1 a capturé le contenu entre les marqueurs (côté gauche) puis l’a réinjecté deux fois (côté droit) — sans jamais savoir ce que ce contenu était. C’est de la réécriture context-sensitive : la règle dépend du contexte (les marqueurs R1 et R2) et opère sur un contenu qu’elle ne définit pas.

Encart : Manipuler des objets sans les définir

C’est l’insight fondamental des wildcards en mode PROD : ils permettent de manipuler des structures sans les nommer. La règle R1 ?1 R2 --> ?1 ?1 ne sait pas si ?1 contient des bols de tabla, des notes de sitar ou des commandes de robot — elle sait seulement qu’il y a « quelque chose » entre deux bornes, et elle le duplique.

On touche ici à une forme primitive de la notion d’objet en programmation : une entité manipulable par ses interfaces (les marqueurs) plutôt que par sa structure interne. C’est aussi ce qui rend les wildcards si puissants — et si différents des variables.

Wildcards vs variables : deux mécanismes de copie

Les deux capturent et répliquent, mais à des niveaux différents :

Variable \|x\| Wildcard ?1
Portée Au sein d’une même règle
Capture quoi Le résultat d’une dérivation
Quand Pendant la dérivation
Analogie musicale « Joue ce thème, puis rejoue-le à l’identique » (tihāī)

Les variables créent de la répétition (le tihāī). Les wildcards créent de la transformation (extraire un motif et le recontextualiser).

En mode ANAL : le test d’appartenance

En mode analytique, les wildcards retrouvent leur rôle classique de pattern matching. La règle :

 

gram#1[1] ?1 - ?1 - ?1 --> #

 

signifie : « vérifie que la séquence à analyser est un tihāī — trois répétitions du même motif séparées par des silences ». Si la séquence dha tirakita dhin - dha tirakita dhin - dha tirakita dhin est soumise en entrée, le wildcard ?1 capture dha tirakita dhin et vérifie que les trois occurrences sont identiques.

C’est le dual du mode PROD : en production, le wildcard transforme ; en analyse, il reconnaît. Les deux faces d’une même pièce — un sujet développé dans B8.

4. Marqueurs de contexte : la grammaire regarde autour d’elle

Le problème des CFG

Dans une CFG, quand on remplace $A$ par $x\,y\,z$, la décision ne dépend jamais de ce qui entoure $A$. C’est la définition même de « context-free ». Mais en musique, le contexte est fondamental : on ne joue pas la même chose après un crescendo qu’après un silence.

Les marqueurs BP3

BP3 introduit des marqueurs de contexte qui rendent les règles sensibles à leur environnement. Le plus important est le marqueur distant :

 

gram#1[1] |Resolution| --> (|sam|) dha tirakita dhin dhin

 

Cette règle joue le motif dha tirakita dhin dhin seulement si le marqueur sam est présent quelque part dans la chaîne courante — exactement comme un tabliste « vise » sam pour conclure une improvisation [BelKippen1992a].

Une règle qui dit « remplace $A$ par $xyz$ seulement si $B$ est présent quelque part » ne peut pas s’exprimer dans une CFG. C’est une règle context-sensitive (Type 1) :

 

En CFG (Type 2) :  A --> xyz         (toujours applicable)
En CSG (Type 1) :  B A --> B xyz     (seulement si B précède A)

 

BP3 généralise ce principe avec ses marqueurs, permettant des conditions à distance, pas seulement sur les voisins immédiats.

Encart : L’ālāp — le cas d’école des marqueurs de contexte

L’ālāp est l’ouverture d’un raga où les notes sont introduites une par une : d’abord Sa seul, puis Sa-Re, puis Sa-Re-Ga, et ainsi de suite. Cette structure d’accumulation progressive est impossible à exprimer proprement avec les 5 modes de dérivation (B3) ou même les flags (B4), qui nécessiteraient une règle par étape (voir l’encart ālāp de B4).

Les marqueurs de contexte offrent une solution élégante :

gram#1[1]                    |Phrase| --> Sa |Ornement_Sa|
gram#1[2] (|Re_introduit|)  |Phrase| --> Re |Ornement_Re| |Phrase|
gram#1[3] (|Ga_introduit|)  |Phrase| --> Ga |Ornement_Ga| |Phrase|

La règle 2 n’est applicable que si le marqueur Re_introduit est présent dans le contexte — c’est-à-dire si Re a déjà été « déverrouillé » dans une phrase précédente. La grammaire accumule progressivement son vocabulaire de notes, exactement comme un musicien explore un raga.

C’est un argument fort pour expliquer pourquoi Bel a ajouté les extensions context-sensitive à BP3 : les structures combinatoires du tabla (kayda, tihāī) s’expriment bien avec les modes et les flags, mais les structures accumulatives du raga (ālāp, barhat) exigent une sensibilité au contexte. Les deux traditions — tabla et raga — demandent des extensions différentes.

5. Contrôle de flux et productions vides

Deux constructions supplémentaires complètent l’arsenal :

_goto(gram, rule) — le saut arbitraire. Cette instruction saute à une règle spécifique dans une grammaire spécifique, comme un goto en programmation. C’est un mécanisme de contrôle de flux qui va bien au-delà des CFG — il permet des boucles et des branchements arbitraires.

_lambda() — la production vide. Le non-terminal disparaît purement et simplement, sans laisser de trace. En théorie formelle, on écrit $A \to \varepsilon$ (epsilon, la chaîne vide). C’est utile pour les structures optionnelles : « il peut y avoir un ornement ici, ou rien du tout ».

Encart : Le prix de la puissance

Plus un langage est expressif, plus il est difficile à analyser automatiquement. Les CFG (Type 2) se parsent en temps polynomial. Les CSG (Type 1) sont décidables mais potentiellement exponentielles. Les constructions context-sensitive de BP3 apportent une puissance compositionnelle remarquable, mais au prix de la complexité : certaines (wildcards, marqueurs de contexte, goto) ne peuvent pas être résolues par un transpileur statique — elles nécessitent un moteur de dérivation complet (voir B7).

Position dans la hiérarchie de Chomsky

Situons ces constructions dans la hiérarchie (L1) :

Niveau Type Constructions BP3
Type 3 Régulier Séquences simples de notes
Type 2 Context-free Non-terminaux, règles de dérivation, modes (B1-B3)
Type 2+ Mildly context-sensitive Flags bornés (B4) — même zone que TAG, CCG
Type 1 Context-sensitive Variables, marqueurs de contexte, wildcards
Type 0 Récursivement énumérable _goto (saut arbitraire), flags non bornés

Les articles B1-B3 couvrent le noyau context-free. B4 (flags) pousse vers le mildly context-sensitive. Cet article montre comment les constructions avancées propulsent BP3 jusqu’au niveau context-sensitive, voire au-delà. C’est cette gradation paramétrable — du Type 2 au Type 0 selon les mécanismes activés — qui fait l’originalité formelle de BP3.

Ce qu’il faut retenir

  • Les variables (|x|) permettent de répéter exactement le même motif dérivé — le tihāī en est l’application parfaite. Cette capacité est impossible dans les CFG pures.
  • Les homomorphismes ((= ...), (: ...)) transforment des motifs selon des mappages note-à-note — le graha bheda (transposition de raga) en est l’exemple musical naturel.
  • Les wildcards (?1, ?2) capturent et réinjectent des fragments de chaîne — en mode PROD pour transformer (réécriture context-sensitive), en mode ANAL pour reconnaître (test d’appartenance). Ils permettent de manipuler des structures sans les définir.
  • Les marqueurs de contexte rendent les règles sensibles à leur environnement — l’ālāp (introduction progressive des notes) est le cas d’école.
  • Le contrôle de flux (_goto) et les productions vides (_lambda) complètent l’arsenal au-delà des grammaires classiques.
  • BP3 est un formalisme paramétrable : selon les constructions utilisées, il se situe entre Type 2 (CFG) et Type 0 (Turing-complet).

Pour aller plus loin

  • Grammaires context-sensitive : Hopcroft, Motwani & Ullman, Introduction to Automata Theory, chapitre 9
  • Homomorphismes formels : Rozenberg & Salomaa, Handbook of Formal Languages, volume 1, chapitre sur les morphismes
  • Bel, B. & Kippen, J. (1992). « Modelling Music with Grammars: Formal Language Representation in the Bol Processor » — l’article fondateur, incluant variables et homomorphismes appliqués au tabla.
  • Bel, B. (1998). « Migrating Musical Concepts — An Overview of the Bol Processor », Computer Music Journal 22(3) — comment les concepts musicaux « migrent » entre traditions via les homomorphismes.
  • Documentation BP3 : Bol Processor – Pattern Grammars
  • Variables et contexte BP3 : Bol Processor – Context-sensitive grammars
  • Traduction en SuperCollider : B7 — comment le transpileur gère (ou ne gère pas) ces constructions avancées.
  • Les trois directions de BP3 : B8 — wildcards en contexte génératif et analytique, modes PROD/ANAL/TEMP, QAVAID.

Glossaire

  • Ālāp : Ouverture d’un raga où les notes sont introduites progressivement. Sa structure accumulative nécessite les marqueurs de contexte — les flags seuls (B4) ne suffisent pas.
  • Bol : Syllabe mnémonique du tabla (ex : dha, dhin, tin, ta). Le « Bol » dans « Bol Processor ».
  • Context-sensitive (sensible au contexte) : Propriété d’une grammaire où le remplacement d’un symbole dépend de son environnement. Correspond au Type 1 de la hiérarchie de Chomsky.
  • Graha bheda : Technique de transposition de raga par déplacement de la note fondamentale (Sa), faisant émerger un nouveau raga. Formalisable comme un homomorphisme BP3.
  • Homomorphisme : Fonction qui transforme chaque symbole d’une chaîne selon un mappage fixe, en préservant la structure (morphisme de monoïdes libres).
  • Kathak : Danse classique du nord de l’Inde, liée au tabla. Les interactions tabliste-danseur sont un cas d’étude fondateur de BP3.
  • Lambda (production vide) : Règle qui réécrit un non-terminal en la chaîne vide ($\varepsilon$). Le symbole disparaît sans laisser de trace.
  • Marqueur de contexte : Construction BP3 qui conditionne l’application d’une règle à la présence d’un symbole dans le contexte.
  • Pattern matching : Mécanisme de correspondance de motifs. Les wildcards de BP3 capturent des portions de chaînes dérivées pour les réutiliser.
  • Pumping lemma (lemme de pompage) : Outil de preuve en théorie des langages qui permet de montrer qu’un langage n’est pas context-free.
  • Sam : Premier temps du cycle tāla — point de résolution vers lequel convergent les tihāī.
  • Tihāī : Cadence indienne où un motif est répété trois fois pour tomber sur sam. Formalisable en BP3 via les variables : |x| - |x| - |x|.
  • Variable : Construction |x| dont la première occurrence fixe une valeur et les suivantes la répliquent. Permet d’exprimer des contraintes de répétition exacte impossibles en CFG.
  • Wildcard (joker) : Construction ?N qui capture une portion arbitraire de la chaîne. En mode PROD : capture sur le côté gauche, réinjection sur le côté droit (réécriture context-sensitive entre grammaires). En mode ANAL : pattern matching pour tester l’appartenance. Fonctionne dans les deux directions — voir B8.

Prérequis : L1, B2, B3
Temps de lecture : 14 min
Tags : #homomorphismes #variables #contexte #BP3 #context-sensitive

← Retour à l’index