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

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 | w ∈ Σ* } — l’ensemble de toutes les chaînes formées d’un mot w suivi de sa copie exacte, où Σ* (sigma étoile) désigne l’ensemble de tous les mots possibles sur l’alphabet Σ (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 : transformer un motif

L’idée

Un homomorphisme en mathématiques est une fonction qui préserve la structure. En musique, c’est une transformation qui s’applique note par note : transposition, inversion, rétrogradation. BP3 intègre ce concept directement dans sa syntaxe.

Encart : Homomorphisme en musique

Pensez à un filtre Instagram pour la musique. Le filtre « sépia » ne change pas la composition de la photo, il transforme chaque pixel. De même, un homomorphisme musical ne change pas la structure de la mélodie, il transforme chaque note : monter d’une tierce, passer en mineur, inverser les intervalles.

Syntaxe BP3

BP3 utilise trois marqueurs :

Marqueur	Syntaxe	Rôle
Master	`(= ...)`	Définit le motif de référence
Slave	`(: ...)`	Réplique le motif avec transformation
Ref	identifiant	Référence un fichier d’homomorphisme externe (`-ho.*`)

Exemple :

gram#1[1] S --> (= Sa Re Ga Ma) (: mineur) (: rétrograde)

Le master définit le motif Sa Re Ga Ma. Le premier slave applique l’homomorphisme « mineur ». Le second applique « rétrograde ». Résultat : trois versions du même motif — l’original, sa version mineure, et sa version rétrograde.

Formellement, un homomorphisme BP3 est un morphisme de monoïdes libres (une transformation qui préserve l’opération de concaténation des mots). Décomposons :

h est la fonction de transformation — la table de mappage (par exemple : Sa → Re, Re → Ga, Ga → Ma, etc.)
Σ* (sigma étoile, déjà rencontré plus haut) désigne l’ensemble de tous les mots possibles sur l’alphabet musical
h : Σ* → Σ* signifie que h prend un mot musical et renvoie un autre mot musical
La propriété fondamentale est h(αβ) = h(α)h(β), où α (alpha) et β (bêta) sont deux fragments musicaux quelconques : transformer la séquence αβ (alpha suivi de bêta) revient à transformer α et β séparément puis concaténer les résultats

En clair : chaque note est transformée indépendamment, et l’ordre est préservé. Si h transpose d’un ton et que la phrase est Sa Re, alors h(Sa Re) = h(Sa) · h(Re) = Re Ga [Bel1998].

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 déplace la note fondamentale (Sa) d’un raga vers un autre degré, faisant émerger un nouveau raga. Par exemple, le raga Kalyāṇ (Sa Re Ga Ma# Pa Dha Ni) devient le raga Bilaval (Sa Re Ga Ma Pa Dha Ni) en abaissant le Ma# d’un demi-ton.

C’est exactement un homomorphisme au sens de BP3 : le master est la phrase originale dans un raga, le slave applique un mappage note-à-note qui produit une phrase dans un autre raga. La structure mélodique est préservée, seules les hauteurs changent — la définition même d’un morphisme [Bel1998].

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.

Contrairement à ce qu’on pourrait croire, les wildcards ne sont pas réservés au mode analytique de BP3. Ils fonctionnent pleinement dans les deux directions — PROD (production) et ANAL (analyse) — avec des sémantiques complémentaires.

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 → ε (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 (ε). 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