M1) MIDI sous le microscope formel

Un protocole au pied de la hiérarchie de Chomsky

Que révèle l’analyse formelle du standard musical le plus déployé au monde ?

Où se situe cet article ?

Cet article ouvre la série Musique (M). Si vous avez lu I4, vous savez comment MIDI fonctionne — messages, canaux, vélocité, timing. Ici, on change de perspective : on ne demande plus « comment ça marche » mais « qu’est-ce que c’est, formellement ? »

Pour cela, on utilise les outils des langages formels introduits dans L1 : la hiérarchie de Chomsky, les automates, les grammaires. L’objectif est de situer MIDI dans cette hiérarchie, de comprendre ce que cette position implique, et de découvrir un fait surprenant : après 40 ans d’existence et des milliards de fichiers produits, MIDI n’a jamais reçu de spécification formelle complète — seulement des fragments dispersés.

MIDI vu par les langages formels

Un protocole = un langage

Tout protocole de communication peut être analysé comme un langage formel. Il a :

Un alphabet : l’ensemble des symboles possibles. Pour MIDI, ce sont les 256 valeurs d’un octet (0x00 à 0xFF).
Une syntaxe : les règles qui déterminent quelles séquences d’octets sont valides. Pour MIDI, un message Note On doit avoir un status byte suivi de deux data bytes.
Une sémantique : la signification des messages. Pour MIDI, le status byte 0x90 signifie « début de note sur le canal 1 ».

La question est : quel type de langage est MIDI ? Peut-on écrire une grammaire qui le décrit ? Si oui, à quel niveau de la hiérarchie de Chomsky (L1) se situe cette grammaire ?

Deux niveaux d’abstraction

Avant de plonger, notons que MIDI peut être analysé à deux niveaux d’abstraction syntaxique :

Le niveau binaire : les octets bruts sur le câble — status bytes, data bytes, encodages VLQ. C’est le niveau du format.
Le niveau commandes : les messages structurés — Note On(canal, note, vélocité), Control Change(canal, contrôleur, valeur), Program Change(canal, programme). C’est le niveau du protocole.

La spécification MIDI (MMA) définit la correspondance entre les deux : tel pattern d’octets correspond à telle commande. On peut écrire une grammaire à chaque niveau — mais les questions posées sont différentes.

Au niveau binaire, le problème est bien compris : status bytes, data bytes, running status. C’est l’objet de cet article, et la conclusion est nette : langage régulier (Type 3).

Au niveau commandes, la situation est plus riche et plus ouverte. Chaque commande individuelle a un vocabulaire fini et une arité fixe — jusque-là, c’est régulier. Mais le protocole impose aussi des contraintes de séquencement entre commandes :

Un Note On devrait être suivi (éventuellement) d’un Note Off correspondant (même canal, même note) — un problème d’appariement.
Les séquences NRPN exigent un ordre précis : CC 99 → CC 98 → CC 6 (→ CC 38).
Un changement de banque requiert CC 0 → CC 32 → Program Change.
Les messages SysEx encapsulent des sous-protocoles propriétaires avec leurs propres structures internes.

Ces contraintes de séquencement forment-elles un langage régulier, context-free, ou davantage ? L’appariement Note On/Off, par exemple, reste techniquement régulier (128 notes × 16 canaux = état fini), mais l’automate serait immense. Pour les sous-protocoles SysEx, la question est ouverte. Personne n’a formellement étudié MIDI à ce niveau d’abstraction — ni posé la question de sa position dans la hiérarchie, ni proposé de grammaire. C’est un aspect du gap que nous identifions dans la suite de cet article.

L’alphabet MIDI : status bytes et data bytes

MIDI fait une distinction binaire élégante entre deux types d’octets :

Status bytes : bit de poids fort à 1 (1xxxxxxx, valeurs 128-255). Ils identifient le type de message et le canal.
Data bytes : bit de poids fort à 0 (0xxxxxxx, valeurs 0-127). Ils portent les paramètres du message.

Un seul bit suffit à distinguer « je suis une commande » de « je suis une donnée ». C’est une structure remarquablement simple — et c’est cette simplicité qui va déterminer la position de MIDI dans la hiérarchie.

Trois niveaux d’analyse

MIDI peut être analysé à trois niveaux d’abstraction croissante, chacun correspondant à une question différente :

Les messages — le flux d’octets sur le câble. Quel type de langage formel forme ce flux ?
Le fichier SMF — la structure qui stocke ces messages sur disque. Que dit-elle sur la hiérarchie de Chomsky ?
Le contenu musical — ce que ces messages représentent musicalement. Quel pouvoir expressif en résulte ?

Parcourons ces trois niveaux.

Niveau 1 : les messages — un langage régulier

Un automate fini suffit

Prenons un message MIDI individuel, par exemple un Note On. Sa structure est :

[Status byte: 1001cccc] [Data byte 1: 0nnnnnnn] [Data byte 2: 0vvvvvvv]
     type + canal            note (0-127)          vélocité (0-127)

C’est une séquence de longueur fixe, déterminée par le status byte. Il n’y a pas de récursion, pas d’imbrication, pas de contexte complexe. Un automate fini (la machine la plus simple de la hiérarchie de Chomsky) peut reconnaître n’importe quel message MIDI.

Rappel (L1) : Un automate fini est une machine avec un nombre fini d’états qui lit une entrée symbole par symbole et décide si la séquence est valide. Pas de mémoire externe, pas de pile, pas de bande — juste des états et des transitions.

Le running status : une machine à états

Le running status est une optimisation du protocole MIDI (I4) : si le status byte est identique au précédent, il peut être omis. Le parseur doit donc « se souvenir » du dernier status reçu.

Cela ajoute un état interne à l’automate. Mais puisqu’il n’y a qu’un nombre fini de status bytes possibles (environ 128 types de messages × 16 canaux), cet état peut être encodé directement dans les états de l’automate. L’automate résultant est plus grand (environ 1000 états au lieu de 10), mais il reste fini.

État : IDLE
  → Reçoit status byte 0x90 → État : NOTE_ON_CH1_ATTENTE_NOTE
  → Reçoit data byte (running status actif) → utilise dernier status mémorisé

État : NOTE_ON_CH1_ATTENTE_NOTE
  → Reçoit data byte (note) → État : NOTE_ON_CH1_ATTENTE_VELOCITE

État : NOTE_ON_CH1_ATTENTE_VELOCITE
  → Reçoit data byte (vélocité) → État : MESSAGE_COMPLET → retour IDLE

Conclusion : Le langage des messages MIDI est un langage régulier — Type 3 dans la hiérarchie de Chomsky. C’est le niveau le plus bas, celui des expressions régulières et des automates finis.

Niveau 2 : le fichier SMF — une structure context-free ?

La structure en blocs

Un fichier MIDI Standard (SMF, Standard MIDI File) ajoute une couche structurelle :

Fichier = En-tête + Piste 1 + Piste 2 + ... + Piste n

En-tête : "MThd" + longueur + format + nombre de pistes + division
Piste  : "MTrk" + longueur + séquence d'événements

Cette structure imbriquée (un fichier contient des pistes, chaque piste contient des événements) ressemble à une grammaire context-free (Type 2, L1). La spécification SMF 1.1 donne d’ailleurs une pseudo-BNF (Backus-Naur Form) :

<midi-file>     = <header-chunk> <track-chunk>+
<header-chunk>  = "MThd" <length=6> <format> <ntrks> <division>
<track-chunk>   = "MTrk" <length> <track-event>+

Variable-length quantities : un détail qui complique

Les delta-times (intervalles entre événements) utilisent un encodage à longueur variable (VLQ, Variable-Length Quantity) : le bit de poids fort de chaque octet indique si l’octet suivant fait partie de la même valeur. C’est comme un système où « 1 » en début d’octet signifie « continue de lire » et « 0 » signifie « c’est le dernier ».

Techniquement, le VLQ dépasse les capacités d’un automate fini simple (il faut « compter » les octets de continuation). Mais un automate à pile (le modèle associé aux grammaires context-free) gère cela sans problème.

Pas de récursion réelle

Cependant, la structure SMF n’a pas de récursion : une piste ne contient pas d’autres pistes, un événement ne contient pas d’autres événements. C’est une structure plate à deux niveaux (fichier → pistes → événements), pas un arbre arbitrairement profond.

Conclusion : Le format SMF est au plus context-free (Type 2), mais c’est un Type 2 très faible — analysable par un parseur LL(1) trivial, sans la puissance récursive qui rend les grammaires context-free intéressantes.

Niveau 3 : le contenu musical — zéro pouvoir génératif

Voici le point crucial pour notre projet : MIDI en tant que représentation musicale n’a aucun pouvoir génératif.

Un fichier MIDI décrit une séquence d’événements spécifique : « à t=0, joue Do ; à t=480, joue Mi ; à t=960, joue Sol ». Il ne peut pas dire :

« Joue ce motif 3 fois » (il faut copier-coller les événements)
« Choisis aléatoirement entre deux variations » (pas de stochasticité)
« Imbrique ces deux flux temporels en ratio 3:4 » (pas de polymétrie)

En termes de langages formels, un fichier MIDI est un mot du langage, pas une grammaire. Il décrit un résultat, pas un processus qui génère des résultats.

Le contraste avec BP3

Aspect	MIDI (Type 3)	BP3 (Type 2 → Turing)
Nature	Mot (séquence finie)	Grammaire (ensemble de règles)
Récursion	Aucune	Oui (règles récursives)
Stochasticité	Aucune	Oui (poids, modes RND/SUB)
Polymétrie	Impossible	Native (ratio + parallèle)
Structure	Plate (séquence d’événements)	Hiérarchique (arbre de dérivation)
Pouvoir	Description	Génération
Hiérarchie	Type 3 (régulier)	Type 2 → Turing-complet (L1, L9)

Le passage BP3 → MIDI est une projection : l’arbre de dérivation est aplati en une séquence linéaire. On perd deux choses :

L’information structurelle : quelle règle a produit quelle note, quels motifs sont récurrents, comment les flux temporels s’articulent — tout cela disparaît.
Le pouvoir expressif : un fichier MIDI est une réalisation particulière. La stochasticité (poids, mode RND), la récursion contrôlée (mode SUB), les alternatives probabilistes — tout ce qui fait de BP3 un espace de musiques possibles est réduit à un seul point de cet espace. Rejouer le fichier MIDI donne toujours le même résultat ; relancer la grammaire BP3 peut en donner un différent.

C’est comme passer d’un programme Python (qui contient des boucles, des fonctions, des conditions, et des tirages aléatoires) à une trace d’exécution particulière. La trace ne permet ni de reconstituer le programme, ni de reproduire sa variabilité.

L’état des formalisations : un terrain presque vierge

La pseudo-BNF du SMF : le seul fragment formel officiel

La spécification SMF 1.1 (MMA, 1999) contient quelques lignes de pseudo-BNF — c’est la seule tentative de formalisation dans la spécification officielle. Elle couvre la structure du fichier, mais pas la syntaxe des messages MIDI eux-mêmes, et certainement pas leur sémantique.

Kaitai Struct : le plus proche d’une spec formelle

Le projet Kaitai Struct propose une description déclarative complète du format SMF en YAML. C’est probablement la spécification la plus rigoureuse qui existe : elle couvre l’intégralité du format binaire et peut générer des parseurs dans 11 langages. Mais Kaitai décrit la structure binaire, pas le langage au sens de Chomsky.

Euterpea/Haskore : formalisation algébrique en Haskell

Le projet Euterpea (Hudak, 2014) définit la musique comme un type de données algébrique récursif en Haskell, avec un opérateur séquentiel (:+:) et un opérateur parallèle (:=:). L’export vers MIDI est une fonction qui aplatit cette structure récursive en événements MIDI. Euterpea ne formalise pas MIDI — il formalise une abstraction au-dessus de MIDI. C’est exactement l’approche de BP3.

MIDI Linked Data : 10 milliards de triples RDF, mais pas le protocole

Le projet MIDI-LD (Meroño-Peñuela & Hoekstra, 2017) a converti 170 000 fichiers MIDI en 10.2 milliards de triples RDF — des triplets sujet–prédicat–objet (par exemple : <Note42> <aPourHauteur> <Do4>) qui forment la brique de base du Web sémantique. C’est une formalisation ontologique (qu’est-ce qu’un événement MIDI signifie ?) mais pas syntaxique (comment un message MIDI est-il structuré ?).

RFC 6295 : une grammaire ABNF… au service du réseau

La RFC 6295 (Lazzaro & Wawrzynek, 2011) spécifie l’encapsulation de MIDI dans des paquets réseau (RTP). Pour ce faire, elle inclut une grammaire ABNF (Augmented BNF) des messages MIDI — la description syntaxique la plus rigoureuse qui existe. Mais cette grammaire n’a pas été écrite pour formaliser MIDI : c’est un sous-produit d’une spécification réseau. Elle couvre la structure des messages, pas la sémantique du protocole (que signifie un Control Change 64 ?), et elle est enterrée dans une RFC que personne dans la communauté musicale ne consulte.

En d’autres termes : il existe un fragment de spécification formelle, mais il est partiel, décontextualisé, et n’a jamais été reconnu ni adopté comme spécification de référence pour MIDI lui-même.

Pourquoi ce gap ?

Quatre raisons convergent :

Origine industrielle : MIDI vient de l’industrie musicale, pas de l’académie. Pas de tradition de formalisation.
Simplicité syntaxique : Un langage régulier est si simple qu’une grammaire formelle semble superflue.
Format binaire : Les formalismes classiques (BNF, EBNF) sont conçus pour des langages textuels, pas binaires.
Absence de criticité : Une erreur de parsing MIDI produit une fausse note, pas une faille de sécurité. Pas de motivation pour la vérification formelle.

Ce que ça révèle

La simplicité = la force ET la limite

La position de MIDI au pied de la hiérarchie de Chomsky explique à la fois son universalité et ses limitations :

Universalité : Un langage régulier est trivial à parser. N’importe quel microcontrôleur 8 bits de 1983 peut lire du MIDI. C’est pourquoi le protocole a été adopté partout, des synthétiseurs aux DAWs en passant par les contrôleurs de lumière et les installations artistiques.

Limitation : Un langage régulier ne peut pas exprimer de hiérarchie. MIDI ne peut pas représenter une « phrase musicale » composée de « motifs » eux-mêmes composés de « notes » — il ne voit que des notes individuelles dans le temps. C’est pourquoi les systèmes qui cherchent à analyser ou générer de la musique structurée (GTTM, BP3, TidalCycles) opèrent au-dessus de MIDI.

Ce n’est pas un défaut de conception — c’est une conséquence structurelle du choix d’un langage régulier. Un choix délibéré, pragmatique, et brillamment adapté à la contrainte de 1983 : faire communiquer des synthétiseurs avec un microprocesseur 8 bits et un câble série.

Pour aller plus loin dans la série

M2 (à venir) — MusicXML sous le microscope formel : un format context-free (Type 2) avec grammaire complète
M5 — La polymétrie : le concept que MIDI ne peut structurellement pas exprimer
M7 — Le paysage des DSL musicaux : comment d’autres systèmes contournent les limites de MIDI
B1 — BP3 : un système génératif qui opère au-delà du Type 2

Ce qu’il faut retenir

MIDI est un langage régulier (Type 3) : ses messages peuvent être reconnus par un automate fini, la machine la plus simple de la hiérarchie de Chomsky.
Le format SMF est au plus context-free (Type 2) : la structure en chunks ajoute un niveau, mais sans récursion réelle.
MIDI n’a aucun pouvoir génératif : il décrit des séquences, il ne les génère pas. C’est un mot, pas une grammaire.
MIDI n’a jamais été formellement spécifié en tant que tel : malgré 40 ans d’existence, il n’existe pas de grammaire complète ni de sémantique formelle du protocole. Des fragments existent (pseudo-BNF du SMF, ABNF de la RFC 6295), mais aucun n’a été conçu comme spécification de référence pour MIDI. C’est un gap de recherche identifié.
La simplicité de MIDI est à la fois sa force et sa limite : un langage régulier est universel et trivial à parser, mais il ne peut pas exprimer de structure hiérarchique.
BP3 opère à un niveau fondamentalement supérieur : là où MIDI décrit, BP3 génère. L’export BP3 → MIDI est une projection qui perd l’information structurelle.

Glossaire

Automate fini (finite automaton) : machine avec un nombre fini d’états qui lit une entrée symbole par symbole. Reconnaît exactement les langages réguliers (Type 3). Voir L1.
BNF / EBNF (Backus-Naur Form / Extended BNF) : notation pour écrire des grammaires formelles. Utilisée pour spécifier la syntaxe des langages de programmation. Voir L3.
Context-free (hors-contexte) : type de grammaire (Type 2) où chaque règle remplace un seul symbole, indépendamment du contexte. Permet la récursion et l’imbrication. Voir L2.
Data byte : octet MIDI dont le bit de poids fort est 0 (valeurs 0-127). Porte les paramètres des messages (note, vélocité, valeur CC…).
Grammaire : ensemble de règles de réécriture qui définissent un langage. À ne pas confondre avec un mot du langage.
Hiérarchie de Chomsky : classification des langages formels en 4 types (Type 3 → Type 0) selon le pouvoir expressif croissant des grammaires nécessaires. Voir L1.
Langage régulier : langage reconnaissable par un automate fini (Type 3). Les messages MIDI individuels forment un langage régulier.
Running status : optimisation MIDI où le status byte peut être omis s’il est identique au précédent. Nécessite que le parseur mémorise le dernier status.
SMF (Standard MIDI File) : format de fichier MIDI (.mid). Structure en chunks (en-tête + pistes).
Status byte : octet MIDI dont le bit de poids fort est 1 (valeurs 128-255). Identifie le type de message et le canal.
VLQ (Variable-Length Quantity) : encodage de nombres entiers à longueur variable utilisé dans le format SMF pour les delta-times.

Liens dans la série

Série Introduction (prérequis) :

I4 — Introduction au MIDI : le protocole qui fait parler les instruments

Série Langages formels (outils théoriques) :

L1 — Hiérarchie de Chomsky : le cadre de classification utilisé ici
L2 — Grammaires context-free : le niveau que MIDI n’atteint pas vraiment
L3 — EBNF : la notation que MIDI n’a jamais eue

Suite de la série Musique :

M2 — MusicXML sous le microscope formel
M3 — Les trois paradigmes de représentation musicale
M5 — La polymétrie : ce que MIDI ne peut pas exprimer

Série BP3 :

B1 — Grammaires probabilistes : BP3 commence au Type 2

Glossaire :

Glossaire — Glossaire général de la série

Prérequis : I4, L1
Temps de lecture : 15 min
Tags : #midi #langages-formels #chomsky #automate #grammaire #formalisation

Prochain article : M2 — MusicXML sous le microscope formel