LeDevNovice apprend XState - Semaine 3

Salut,

Semaine 1, Turing nous a appris que le calcul est un processus de changement d'état. Semaine 2, McCulloch et Pitts nous ont montré que le cerveau lui-même fonctionne comme un réseau de machines à état binaires.

Six principes dans ma besace, zéro ligne de code. Je sais que vous êtes impatient les ami(e)s codeurs, mais je pense que c’est bien de se créer des fondamentaux avant même de partir sur du code. Bientôt, c’est promis.

Cette semaine, un troisième personnage entre en scène. Et celui-là va nous offrir quelque chose que les deux précédents n'avaient pas donné. Un langage pour décrire les machines à état. Ce langage, vous le connaissez déjà. Vous l'utilisez peut-être tous les jours sans savoir d'où il vient. Vous avez même tendance a le maudire au premier abord.

Ce sont les expressions régulières.

On est désormais en 1956.

Stephen Cole Kleene (prononcé "KLAY-nee", pas "clean". Même moi je le prononçais mal mais bon un peu de respect quand même) est un mathématicien logicien formé par Alonzo Church à Princeton. Church, si vous avez bonne mémoire, c'est l'autre géant des années 1930 avec Turing qu’on a rencontré en première semaine. Celui qui a cherché à résoudre également le problème de l’indécidabilité mais avec des concepts mathématiques de fou furieux a base de lambda calcul et autre étrangeté pour nous mortel des maths. Kleene a grandi dans le sillage direct de ces fondateurs.

Il tombe sur le papier de McCulloch et Pitts de 1943. Tu sais, cette fois celui de la semaine dernière, les réseaux de neurones formels qui se comportent comme des automates finis. Et il se pose une question très précise :

McCulloch et Pitts avaient montré que leurs réseaux pouvaient calculer. Par cette déclaration, Kleene veut en fait caractériser précisément ce qu'ils peuvent calculer. Pas juste "ils peuvent faire des trucs". Exactement quels trucs.

C'est une question de mathématicien. Et la réponse va quand même pas mal changer notre quotidien de développeur.

Avant d'arriver aux regex, il faut que je vous montre ce que Kleene formalise comme point de départ. L'automate fini, c'est la machine à état réduite à son essence les ami(e)s codeurs.

Imaginez le dispositif le plus simple que vous puissiez concevoir :

Pas de mémoire. Pas de pile. Pas de registres. Juste des états et des transitions. C'est la version radicalement minimale de la Machine de Turing, sans le ruban infini.

Formellement, c'est ce qu’ils appellent un quintuple (Q, Σ, δ, q₀, F) : un ensemble fini d'états, un alphabet d'entrée, une fonction de transition, un état initial, et un ensemble d'états acceptants. On retrouve exactement la structure de Turing, en plus contraint, avec deux éléments en moins.

Prenons un automate qui reconnaît les chaînes binaires contenant un nombre pair de 1.

Deux états suffisent : pair et impair. On démarre en pair (zéro 1, c'est pair). À chaque 0, on reste dans le même état. À chaque 1, on bascule.

Déroulons sur "11011" : pair → 1 → impair → 1 → pair → 0 → pair → 1 → impair → 1 → pair. Fin en pair → accepté. Quatre 1, c'est pair. Correct.

Encore une fois on retrouve une notion qu’on pouvait observer avec la Machine de Turing. A savoir que l'automate ne compte pas. Il n'a aucune idée de combien de 1 il a vus. Il ne retient que la parité, pair ou impair. Et cette information suffit.

C'est vraiment le cœur de la philosophie des machines à état les ami(e)s codeurs ! L'état capture l'essence de ce qui est pertinent, pas les détails exhaustifs. L'état pair ne dit pas "j'ai vu 0, 2, 4 ou 6 fois un 1". Il dit "quoi qu'il se soit passé, la propriété qui compte est satisfaite."

En XState, ça donnerait quelque chose comme :

Chaque état définit un comportement face aux événements. C'est le principe 1 de Turing en action.

OK, on a un automate fini qui reconnaît un certain type de séquences. Mais comment décrire ce qu'il reconnaît de manière compacte ?

On peut le dire en français : "les chaînes binaires avec un nombre pair de 1". Mais pour des automates plus complexes, le langage naturel devient vite ambigu. On pourrait lister les éléments reconnus : "", "0", "00", "11", "011", "110"... Mais la liste est infinie. On pourrait dessiner le diagramme. C'est visuel, mais on ne peut pas le manipuler algébriquement.

Ce qu'il faudrait, c'est un langage formel. Compact, précis, et manipulable mathématiquement.

C'est exactement ce que Kleene invente en 1956 dans son papier "Representation of Events in Nerve Nets and Finite Automata". Regardez le titre, il parle de "nerve nets", les réseaux de neurones de McCulloch et Pitts. ET d'automates finis. Il fait le pont entre les deux.

Il appelle sa notation les "événements réguliers". Nous, on les appelle désormais expressions régulières. Les regex.

Kleene construit son langage à partir de presque rien. Trois briques de base et trois opérations. C'est tout.

Les briques : le symbole vide (ε), le symbole individuel (a, b, 0, 1...), et l'ensemble vide (∅).

Les trois opérations :

L'union ( | ), "ceci OU cela". L'expression a|b reconnaît soit "a", soit "b". En termes de machine à état, un choix, un branchement. (Les connaisseurs de TypeScript y verront ici des choses familières)

La concaténation ( · ), "ceci PUIS cela". L'expression ab reconnaît "a" suivi de "b". En termes de machine à état, une séquence, un enchaînement d'états.

L'étoile de Kleene ( * ), "zéro ou plusieurs fois". L'expression a* reconnaît "", "a", "aa", "aaa"... En termes de machine à état : une boucle, un retour au point de départ.

C'est tout. Ces trois opérations correspondent aux trois structures fondamentales qu'on retrouve partout en programmation.

Choix, séquence, répétition. Les trois piliers de tout programme structuré. Kleene les a identifiés dans un contexte mathématique pur, vingt ans avant que la programmation structurée ne devienne un paradigme.

Et ce qu’il est bien important de comprendre ici c’est que ces trois opérations sont exactement les trois types de chemins possibles dans un diagramme d'états. Tu peux aller de A vers B ou vers C (choix). Tu peux passer par A puis B (séquence). Tu peux revenir en boucle à A (répétition). Il n'y a rien d'autre.

Prenons l'alphabet binaire {0, 1}.

0* → zéro ou plusieurs 0 : "", "0", "00", "000"...

0*10* → des 0, un 1, des 0 : les chaînes contenant exactement un seul 1.

(0|1)* → n'importe quel symbole, répété : toutes les chaînes binaires.

(0|1)*1 → n'importe quoi suivi d'un 1 : toutes les chaînes qui finissent par 1.

Et maintenant, la plus belle : (0*10*10*)*. Décomposons. 0*10*10* c'est "des 0, un 1, des 0, un 1, des 0", une chaîne avec exactement deux 1. L'étoile extérieure dit "répéter ça zéro ou plusieurs fois", 0, 2, 4, 6... occurrences de 1. C'est-à-dire, les chaînes avec un nombre pair de 1.

C'est exactement le langage de notre automate à deux états. La regex et l'automate reconnaissent la même chose. Et ça, ce n'est pas une coïncidence.

Voilà le résultat central de Kleene, celui qui a tout changé :

Les deux formalismes sont exactement équivalents en puissance. Ils définissent la même classe de langages, a savoir les langages réguliers.

Et c'est là que j'ai quand même eu personnellement un déclic sur la profondeur du truc les ami(e)s codeurs.

Un automate fini, c'est un objet opérationnel. Il décrit un processus étape par étape. "Je suis dans cet état, je reçois ce signal, je vais là." C'est un mécanisme. Un comment.

Une expression régulière, c'est un objet déclaratif. Elle décrit un résultat sans expliquer comment l'obtenir. "Je veux les chaînes qui matchent ce pattern." C'est une spécification. Un quoi.

Le théorème de Kleene dit que ces deux perspectives sont exactement aussi puissantes. Tout ce que tu peux exécuter avec un automate, tu peux le décrire avec une regex, et inversement.

Pour XState, c'est exactement ça en fait ! Quand tu définis une machine, tu fais les deux en même temps. Tu décris les états (l’aspect déclaratif) ET tu spécifies les transitions (l’aspect procédural). C'est cette double nature qui rend les machines à état si puissantes, et si bonnes pour la communication en équipe, parce que le diagramme est la spec ET l'implémentation.

On va entrer dans une partie qui est, je pense, une de celle qui m’a le plus appris pour la pratique future.

Kleene ne montre pas seulement ce que les automates finis peuvent faire. Il caractérise aussi ce qu'ils ne peuvent pas faire. Et comprendre ces limites, c'est comprendre pourquoi XState a un context. (Comme nous le verrons bientôt)

Un automate fini ne peut pas compter de manière illimitée. Il ne peut pas reconnaître "n fois 'a' suivi d'exactement n fois 'b'" (comme "aabb", "aaabbb"). Parce que n peut être arbitrairement grand, et l'automate n'a qu'un nombre fini d'états. Donc une mémoire finie.

Un automate fini ne peut pas vérifier les paires imbriquées. Les parenthèses correctement imbriquées, "((()))", lui sont inaccessibles. Il faudrait compter la profondeur. Et compter, il ne peut pas. C'est pour ça que les parseurs de langages de programmation ne sont pas de simples automates finis.

Un automate fini ne peut pas reconnaître les palindromes. "abba", "abacaba" par exemple. Pour vérifier, il faudrait se souvenir de la première moitié et la comparer à la seconde. Mémoire illimitée requise.

Ces limitations sont exactement la raison pour laquelle XState a un contexte étendu (context). Un automate fini pur ne peut pas compter. Mais dans une vraie appli, tu as besoin de compter. Le nombre de tentatives de connexion, le score, les articles dans un panier.

La solution, c’est de séparer l'état fini (le mode, le comportement qualitatif) de l'état étendu (les données quantitatives). C'est le principe 5 de Turing, "séparer ce qui est fini de ce qui est variable". En fait maintenant je comprends pourquoi c'est nécessaire. Et j’espère que vous aussi les ami(e)s codeurs. Pas juste parce que c'est élégant. Mais parce que sans ça, l'automate fini seul est trop limité pour une application réelle.

La combinaison des deux est bien plus puissante que l'automate seul. C'est ce qui fait de XState un outil praticable là où un automate fini pur serait en fait finalement insuffisant.

J’aime bien faire ces petits apartés, parce que la chaîne est assez fascinante a explorer.

1956, Kleene publie son théorème en étudiant les réseaux de McCulloch-Pitts.

1968, Ken Thompson (futur créateur d'Unix) implémente les expressions régulières dans un éditeur de texte. Il utilise ce que l’on appellera la "construction de Thompson" pour convertir les regex en automates finis. Première implémentation informatique des résultats de Kleene.

1973, Les outils grep, sed, awk intègrent les regex dans Unix. Le nom grep signifie littéralement "Global Regular Expression Print". Chaque fois que vous faites un grep, vous invoquez le théorème de Kleene.

1986 et au-delà, Les regex se diffusent dans Perl, Python, Java, JavaScript, et tous les langages qu'on utilise.

Et petit détail qui m'a amusé, les regex modernes que tu tapes dans ton IDE vont en fait au-delà de ce que Kleene avait défini. Les backreferences (\1, \2), les relookage, les lookbehind, etc… Tout ça dépasse les expressions régulières au sens mathématique. Les "regex" de JavaScript sont par exemple un superset des expressions régulières de Kleene. Mais le cœur, union, concaténation, étoile, reste identique à ce qu'il a formalisé en 1956.

Avec cette semaine, la boucle se boucle (sans mauvais jeu de mots). Les trois premières leçons convergent :

Trois langages différents pour décrire la même réalité mathématique. C'est le résultat unifié de Kleene. Les réseaux de neurones finis de McCulloch-Pitts sont exactement aussi puissants que les automates finis, qui sont exactement aussi puissants que les expressions régulières. Ce sont trois faces de la même pièce.

Avec Turing, j'avais 5 principes. McCulloch-Pitts m'avait donné le 6ème. Kleene m'en donne deux de plus :

1. L'état détermine le comportement (Turing)

2. Le calcul est une série de transitions (Turing)

3. La finitude est une force (Turing), enrichi par Kleene, c'est aussi une limite qu'il faut connaître. Savoir ce que l'automate fini ne peut pas faire, c'est savoir quand on a besoin du contexte étendu.

4. Le déterminisme est un super-pouvoir (Turing)

5. Séparer ce qui est fini de ce qui est variable (Turing), justifié par Kleene, sans cette séparation, l'automate fini est trop limité pour les applications réelles.

6. La puissance émerge de la composition d'unités simples (McCulloch-Pitts)

7. Un système peut être décrit par son mécanisme OU par sa spécification, les deux sont équivalents (Kleene), la dualité procédural/déclaratif. En XState, le diagramme est la spec ET l'implémentation.

8. Choix, séquence, répétition : trois opérations suffisent (Kleene), tout chemin dans un diagramme d'états se ramène à ces trois structures.

On passe aux modèles de Mealy (1955) et Moore (1956), les automates qui ne se contentent plus de dire "oui" ou "non", mais qui produisent des sorties. C'est le dernier pas avant l'application pratique. Les machines cessent d'être des concepts théoriques et commencent à faire des choses.

On se rapproche sérieusement du code. Derrière, on fera notre première application pratique avec XState. Accrochez-vous.

À vendredi prochain,

@LeDevNovice

Je code, je galère, je comprends, je partage.