Implémenter un automate
Ce que ce chapitre apporte
- Écrire une table de transition sous la forme d'un dictionnaire de dictionnaires.
- Écrire une fois pour toutes la boucle de lecture et le verdict, et la réutiliser sans la modifier.
- Modifier le comportement d'un automate en changeant une donnée, jamais une ligne de code.
- Rendre un diagnostic exploitable : l'état atteint et le rang du symbole qui a bloqué la lecture.
- Lire une expression régulière comme un automate compilé, et reconnaître celles qui font s'effondrer un moteur.
Un automate dessiné sur un tableau blanc ne valide aucune trame et ne filtre aucun journal. Pour qu'il serve, il faut qu'il tourne : sur un poste de supervision, dans un script de dépouillement, dans le programme d'un équipement. Ce chapitre fait la traduction, et elle tient en une trentaine de lignes de Python.
Le geste central n'est pas d'écrire du code, c'est d'écrire une donnée. L'automate devient une table, et le programme une boucle qui lit cette table sans rien savoir du protocole qu'elle décrit. Un automate qui change se corrige alors dans la table, pas dans le programme, et c'est toute la différence entre un outil qui vit deux ans et un outil que personne n'ose plus toucher. La table dont il part est celle de la reconnaissance d'une séquence, sur un automate déterministe et complet tel que la déterminisation le produit.
L'automate à coder
Un banc de mesure envoie ses relevés sur une liaison série. Une trame bien formée commence par un octet de début STX, contient un nombre quelconque d'octets de données DATA, puis un octet de contrôle CRC, et se termine par un octet de fin ETX. Tout le reste est du bruit de ligne, et doit être rejeté.
STXDATADATACRCETX
État actif : attente.
La trame proposée est acceptée. La trame STX CRC ETX, sans aucune donnée, l'est également : la boucle DATA sur l'état corps peut être empruntée zéro fois. La trame STX DATA ETX, sans octet de contrôle, se bloque sur ETX.
Le même automate s'écrit en tableau croisé. Une ligne par état, une colonne par symbole, et dans chaque case l'état atteint. Une case vide signifie qu'aucune transition n'existe : la lecture se bloque.
| État | STX | DATA | CRC | ETX |
|---|---|---|---|---|
attente (initial) | corps | |||
corps | corps | controle | ||
controle | complete | |||
complete (acceptant) |
Ce tableau est déjà le programme. Il ne reste qu'à l'écrire dans la syntaxe de Python.
Le réflexe à désapprendre : la cascade de conditions
Traduire un automate dans le premier langage venu donne presque toujours ceci : un if par état, un if imbriqué par symbole.
Le programme est juste, et il est déjà ingérable. Vingt-trois lignes pour quatre états et quatre symboles, sans compter que le protocole tient, lui, en quatre flèches.
Le constructeur du banc ajoute un accusé de réception après la fin de trame. Sur le dessin, c'est une flèche. Dans la cascade, c'est un nouveau bloc elif etat == "complete" à insérer au bon endroit, et le else: return False final à déplacer sans se tromper.
Une modification du protocole devient une modification du code, donc une relecture, un test de non-régression et un déploiement. Le tableau croisé de la page précédente, lui, aurait gagné une case.
La table de transition, en dictionnaire de dictionnaires
Un dictionnaire associe une clé à une valeur. Ici, la clé extérieure est l'état, et la valeur est elle-même un dictionnaire qui associe un symbole à l'état suivant. Le tableau croisé se transcrit case par case, et les cases vides ne s'écrivent pas.
La table de transition d'un automate déterministe est la donnée qui, pour chaque état et chaque symbole, donne l'état suivant. En Python, elle s'écrit naturellement comme un dictionnaire de dictionnaires : TRANSITIONS[etat][symbole] est l'état atteint.
L'état initial et l'ensemble des états acceptants complètent la description. Ces trois objets suffisent : ils décrivent l'automate en entier.
Trois choses méritent d'être remarquées. L'état complete a un dictionnaire vide : aucune transition n'en part, toute lecture qui continue au-delà se bloque. Les états acceptants sont rangés dans un ensemble plutôt qu'une liste, parce que la seule question posée est l'appartenance. Et rien, dans cette table, ne mentionne le protocole du banc de mesure : ce sont des chaînes de caractères, que le programme n'a pas à comprendre.
La boucle de lecture
La boucle de lecture est d'une brièveté qui surprend la première fois. Elle part de l'état initial, et pour chaque symbole elle remplace l'état courant par l'état suivant. À la fin, elle regarde si l'état atteint est acceptant.
Neuf lignes, et elles ne changeront plus. lire ignore tout des trames, du banc de mesure et du protocole : elle sait seulement suivre une table. Le même code validera un protocole réseau, un journal de production ou une saisie d'opérateur, à condition de lui présenter la table correspondante.
Un automate se code en deux morceaux qui ne se mélangent jamais :
- la table, qui décrit un protocole particulier, et qui change à chaque évolution de ce protocole ;
- la boucle, qui décrit ce qu'est un automate, et qui ne change jamais.
Toute modification qui oblige à toucher à la boucle pour changer de protocole est le signe que le partage a été raté.
Le .get(symbole) mérite un mot. Écrire transitions[etat][symbole] directement provoquerait une exception KeyError au premier octet parasite de la liaison, c'est-à-dire au premier orage. .get rend None quand la clé est absente, ce qui transforme un plantage en un verdict de rejet.
Dire où la lecture a échoué
Un booléen suffit à trier, il ne suffit pas à dépanner. Devant une trame refusée, l'exploitant a besoin de deux informations : à quel rang la lecture s'est arrêtée, et dans quel état l'automate se trouvait à ce moment. Ces deux renseignements sont déjà dans la boucle, il suffit de les rendre.
Les trois messages distinguent trois défauts que le booléen confondait : un symbole inattendu en cours de trame, une trame qui s'arrête trop tôt, et une trame qui commence mal. Sur une liaison bruitée, cette distinction est ce qui permet de dire si le problème vient du câble ou de l'équipement d'en face.
Le script qui tournerait vraiment
Reste à mettre le tout en service. Le script suivant dépouille un lot de trames relevées sur la liaison, compte les valides et les refusées, et signale l'endroit exact de chaque défaut.
Le script tient dans un fichier, ne dépend d'aucune bibliothèque, et se poserait tel quel sur un poste de supervision. Remplacer la liste RELEVE par la lecture d'un fichier de capture suffirait à le mettre en production.
Changer d'automate sans changer de programme
La promesse du chapitre se vérifie maintenant. Voici un tout autre besoin : surveiller le journal d'un four industriel, dont les événements sont MESURE, ALERTE et ACQUIT. La règle de sécurité est simple : trois alertes consécutives sans rien entre elles déclenchent une mise en sécurité. Une mesure normale ou un acquittement remettent le compteur à zéro.
MESUREALERTEALERTEMESUREALERTEALERTEALERTE
État actif : calme.
Cet automate est complet : aucune lecture ne se bloque, et l'état anomalie absorbe tout ce qui suit. Le journal proposé déclenche bien l'anomalie, mais seulement au dernier symbole : la MESURE du milieu a remis le compteur à zéro, et la première paire d'alertes n'a servi à rien.
Sa mise en œuvre ne demande aucune ligne de code nouvelle. La même boucle, une autre table.
La fonction lire est identique, au caractère près, à celle de la validation de trames. Deux besoins sans rapport, un seul programme : c'est exactement ce que l'écriture en table achète.
Pour ne conserver que les journaux à examiner, la même fonction sert de filtre. [n for n, j in journaux.items() if lire(SURVEILLANCE, "calme", {"anomalie"}, j)] rend la liste des fours à inspecter, et cette ligne ne changera pas davantage que la boucle.
Une expression régulière est un automate compilé
Le chapitre sur les expressions régulières a construit l'automate d'une expression brique par brique. Le module re de Python fait exactement cela : re.compile prend une expression et en construit une machine, qui est ensuite exécutée sur les chaînes à examiner.
Le protocole du banc de mesure, écrit en expression régulière sur une trame dont les octets sont séparés par des virgules :
Les verdicts sont ceux de l'automate à quatre états du début du chapitre, et l'étoile de (,DATA)* est la boucle sur l'état corps.
re.search cherche l'expression quelque part dans la chaîne ; re.fullmatch exige qu'elle couvre la chaîne entière. Un automate, lui, lit toujours le mot en entier : c'est fullmatch qui lui correspond.
search trouve la trame noyée dans le bruit et rend un résultat, ce qui suffirait à faire passer une ligne corrompue pour valide. fullmatch rend None. Une validation s'écrit avec fullmatch, ou avec les ancres ^ et $ ; une extraction, avec search.
re.compile construit la machine ; la garder dans une variable, hors de la boucle, évite de la reconstruire à chaque ligne du journal. Sur un fichier de capture de plusieurs centaines de milliers de lignes, c'est la seule optimisation qui compte, et elle tient en une ligne déplacée.
Les expressions qui font s'effondrer un moteur
Savoir qu'une expression régulière est une machine change la façon de l'écrire. Le moteur de Python n'exécute pas un automate déterministe : il explore les chemins possibles et revient en arrière quand l'un d'eux échoue, parce qu'il propose des fonctions qui dépassent les automates finis, comme les références arrière. Ce retour en arrière a un prix, et certaines expressions le font exploser.
Chaque caractère ajouté double le temps de calcul. Sept caractères de plus, cent fois plus de travail ; trente de plus, et le processus ne rend plus la main. La cause est la double quantification (A+)+ : le moteur doit essayer toutes les façons de découper une suite de A en groupes, et il y en a un nombre exponentiel. Tant que la chaîne se termine par B, la première tentative réussit et rien ne se voit ; c'est l'échec qui coûte, et c'est donc la donnée malveillante ou corrompue qui déclenche l'effondrement.
Le même contrôle, écrit sans quantification imbriquée, est instantané sur une chaîne cent fois plus longue.
- Un quantificateur dans un quantificateur :
(A+)+,(A*)*,(A+)*, ou la même forme avec un groupe plus long. - Des alternatives qui se recouvrent sous une étoile :
(A|AA)*laisse au moteur plusieurs découpages du même texte. - Une expression appliquée à une donnée reçue de l'extérieur, dont la longueur n'est pas bornée : c'est là qu'une expression fragile devient un déni de service.
Le remède est toujours le même : rendre le découpage unique, en supprimant l'imbrication ou en rendant les alternatives disjointes. Le cas échéant, borner la longueur de la chaîne examinée avant de lancer l'expression.
Où cela débouche
Ce chapitre referme le module, et il le referme sur trois portes déjà ouvertes ailleurs sur la plateforme.
- La boucle de lecture est un organigramme : une initialisation, une boucle sur les symboles, un test, une affectation, un verdict. Le parcours Flowgorithme la dessine avant de la coder, et c'est un bon détour pour qui préfère voir un programme avant de l'écrire.
- L'automate qui tourne sur un équipement s'appelle une machine à états, et le parcours Arduino en fait le cœur d'un programme qui ne bloque jamais : au lieu d'attendre, la carte retient son état et réagit aux événements qui arrivent. La table de ce chapitre et le
switchd'une boucleloop()décrivent la même chose. - Le dictionnaire de dictionnaires n'a rien de propre aux automates : le parcours Python le construit en détail, avec les autres structures de données qui servent à décrire un traitement au lieu de le programmer.
Exercices type
Le constructeur du banc ajoute un accusé de réception : après l'octet de fin `ETX`, l'équipement attend un `ACK` avant de considérer l'échange terminé. Modifier l'automate des trames pour en tenir compte, et vérifier que `STX DATA CRC ETX` n'est plus accepté seul.
Le dessin gagne une flèche et un état. La table gagne une entrée dans complete, et l'ensemble des acceptants change d'élément. Le code, lui, ne bouge pas.
STXDATACRCETXACK
État actif : attente.
La trame sans ACK est refusée : la lecture se termine dans complete, qui n'est plus acceptant. Deux caractères modifiés dans la table, zéro dans la fonction lire : c'est le bénéfice annoncé en début de chapitre.
Le bloc suivant reprend la boucle de lecture, avec `transitions[etat][symbole]` à la place de `.get`. Prévoir ce qui se passe sur une trame contenant un octet parasite, puis proposer les deux corrections possibles.
Le programme s'arrête sur KeyError: 'BRUIT'. Ce n'est pas un détail d'écriture : un script de supervision qui s'interrompt au premier octet parasite d'une liaison bruitée ne surveille plus rien, et le silence qui suit passe facilement pour un fonctionnement normal.
Deux corrections, et elles ne sont pas équivalentes.
La première garde la table telle quelle et interroge avec .get, qui rend None au lieu de lever une exception. L'automate reste incomplet, et l'absence de transition est traitée dans le programme.
La seconde complète la table avec un état puits, qui absorbe tout ce qui ne convient pas. L'automate devient complet, plus aucune lecture ne se bloque, et le programme n'a plus aucun cas particulier à traiter.
La seconde version est celle à préférer sur un équipement : elle ne peut plus lever d'exception, et l'état rebut donne un diagnostic lisible dans les journaux.
La règle de surveillance du four change : désormais, seul un acquittement remet le compteur d'alertes à zéro. Une mesure normale intercalée entre deux alertes ne l'interrompt plus. Écrire la nouvelle table, et vérifier qu'un journal que l'ancienne règle laissait passer déclenche maintenant la mise en sécurité.
Le changement ne touche que trois cases : dans les états alerte1 et alerte2, la colonne MESURE ne renvoie plus vers calme mais laisse l'état inchangé.
L'ancienne règle rend False : la mesure du milieu avait ramené l'automate dans calme, et la dernière alerte ne comptait que pour une. La nouvelle rend True : les trois alertes sont retenues malgré la mesure intercalée.
Deux règles de sécurité différentes, deux tables, et pas une ligne de programme réécrite. Un changement de consigne se relit alors dans un tableau que l'exploitant comprend, au lieu de se chercher dans une cascade de conditions que lui seul ne peut pas relire.
Vérification
1.Comment s'écrit la table de transition d'un automate déterministe en Python ?
2.Pourquoi préférer transitions[etat].get(symbole) à transitions[etat][symbole] ?
3.Le protocole gagne un état et deux transitions. Que faut-il modifier ?
4.Que renvoie la boucle de lecture à la fin d'un mot entièrement lu ?
5.Quelle fonction du module re correspond à la lecture d'un mot entier par un automate ?
6.Pourquoi l'expression (A+)+B s'effondre-t-elle sur une chaîne de A qui ne finit pas par B ?
7.Où placer l'appel à re.compile dans un script qui examine un million de lignes ?
8.Quel est l'effet d'un état puits ajouté à la table ?
La méthode
- Dessiner l'automate d'abord, et le faire tourner sur trois séquences au moins : une conforme, une tronquée, une qui commence mal. Le code ne corrigera pas un modèle faux.
- Écrire le tableau croisé, une ligne par état, une colonne par symbole, avant d'ouvrir un éditeur. Les cases vides se voient, et ce sont elles qui posent question.
- Transcrire le tableau en dictionnaire de dictionnaires, puis déclarer l'état initial et l'ensemble des acceptants juste à côté.
- Reprendre la boucle de lecture telle quelle : état courant,
.getdu symbole, rejet si rien, appartenance aux acceptants à la fin. Elle ne se réécrit pas d'un automate à l'autre. - Rendre un diagnostic, pas un booléen : l'état atteint et le rang du symbole bloquant, pour que le rejet soit exploitable par un exploitant.
- Compléter la table avec un état puits dès que l'entrée vient de l'extérieur, pour qu'aucune donnée ne puisse interrompre le script.
- Relire les expressions régulières du projet en cherchant les quantificateurs imbriqués et les alternatives qui se recouvrent, et compiler chaque expression une seule fois.
Synthèse
- Un automate se code en deux morceaux séparés : une table qui décrit le protocole, et une boucle qui décrit ce qu'est un automate.
- La table de transition s'écrit en dictionnaire de dictionnaires,
TRANSITIONS[etat][symbole], transcription directe du tableau croisé. - La boucle de lecture tient en neuf lignes, ne connaît aucun protocole, et ne se réécrit jamais : changer d'automate revient à changer de table.
- La cascade de
ifeteliffait l'inverse : elle dissout le modèle dans le code, et transforme chaque évolution du protocole en modification de programme. - Un rejet utile dit où : le rang du symbole bloquant et l'état atteint. L'état puits rend l'automate complet et met le script à l'abri d'une exception.
- Une expression régulière est un automate compilé :
re.compileune fois,re.fullmatchpour valider,re.searchpour extraire. - Les quantificateurs imbriqués font exploser le temps de calcul sur un échec, et une expression fragile appliquée à une donnée extérieure devient une panne.
- La même boucle se retrouve en organigramme dans le parcours Flowgorithme, en machine à états dans le parcours Arduino, et en dictionnaire dans le parcours Python.
Le module se referme ici, et son parcours tient en une phrase. Un système s'est d'abord décrit par ses états et ses événements, puis a servi à reconnaître une séquence ; les expressions régulières en ont donné l'écriture d'une ligne, le non-déterminisme la forme commode à écrire, la déterminisation la forme qui s'exécute, la minimisation la forme unique qui permet de comparer, et les limites ont dit où le modèle s'arrête. Il reste à poser la table sur un poste et à la laisser tourner.