Bienvenue dans ce premier numéro de LeDevNovice apprend XState avec vous. Depuis quelques temps, je me suis lancé dans l'apprentissage de XState et des machines à état. Pas en surface, pas un tuto de 15 minutes. En profondeur.
Et comme d'habitude avec moi, je code, je galère, je comprends, je partage. Et j’aimerais le faire avec vous cette fois. Que vous appreniez en même temps que moi si vous le souhaitez les ami(e)s codeurs.
Sauf que pour ce premier numéro, c'est pas du code que j'ai à vous partager. Pas encore. Parce que cette semaine, pour vraiment maîtriser les machines à état, il m’a fallu comprendre pourquoi elles existent. Et la réponse à cette question nous emmène en 1936, bien avant le premier ordinateur.
Le problème que personne n'arrivait à résoudre
Début du XXe siècle. Les mathématiciens ont un rêve ambitieux, construire un système parfait. Un truc où on pourrait prendre n'importe quel énoncé mathématique et déterminer mécaniquement, étape par étape, sans réfléchir, s'il est vrai ou faux.
Ce rêve, c'est celui de David Hilbert, le mathématicien le plus influent de l'époque. En 1928, il pose trois questions fondamentales :
Est-ce que tout ce qui est vrai est démontrable ? (la complétude)
Est-ce que le système ne se contredit jamais ? (la cohérence)
Existe-t-il une procédure mécanique universelle pour trancher ? (la décidabilité, l'Entscheidungsproblem, celui qui va nous intéresser cette semaine)
Hilbert était confiant. Il pensait que la réponse serait "oui" aux trois. Il a même déclaré publiquement : "Nous devons savoir, nous saurons."
Il avait tort. Pas de chance. Mauvais move.
En 1931, un logicien autrichien du nom de Kurt Gödel lui met un premier uppercut dans sa face. Ses théorèmes d'incomplétude prouvent que dans tout système formel suffisamment puissant, il existe des vérités qu'on ne peut pas démontrer, et que le système ne peut pas prouver sa propre cohérence.
Deux questions sur trois tombent. Mais la troisième, la décidabilité, reste ouverte. Peut-être que même si on ne peut pas tout prouver, on peut au moins avoir une méthode mécanique pour déterminer ce qui est démontrable ou non ?
C'est là qu'entre Alan Turing.
Un gamin de 23 ans qui observe un mathématicien travailler
Turing est étudiant à Cambridge. Son directeur, Max Newman, expose l'Entscheidungsproblem à ses étudiants et mentionne qu'il reste non résolu. Turing se met alors au travail.
Et son approche est géniale par sa simplicité.
Là où d'autres (comme un certain Alonzo Church) construisent des formalismes mathématiques abstraits, Turing se pose une question toute bête : que fait concrètement un humain quand il calcule ?
Imagine un mathématicien à son bureau, crayon en main. Il fait quoi, exactement ?
Il regarde un symbole sur sa feuille. Il est dans un certain état d'esprit, une sorte de disposition mentale qui influence ce qu'il va faire ensuite. Et en fonction de ce qu'il lit ET de son état d'esprit, il écrit un nouveau symbole, déplace son attention ailleurs sur la feuille, et son état d'esprit change. Et il recommence. Encore et encore, jusqu’à atteindre la finalité désirée.
Et là, Turing réalise un truc profond. Le calcul, c'est un processus mécanique de changement d'état. L'humain qui calcule, au fond, c'est une machine qui lit des symboles, a un état interne, change d'état en fonction de ce qu'elle lit, et écrit des symboles.
C'est de cette observation que naît la Machine de Turing.
La Machine de Turing, concrètement
Turing formalise son idée avec une machine volontairement ultra-simple. Pas parce qu'il manque d'imagination, mais parce que toute la force de son argument repose sur cette simplicité. Si même une machine aussi basique peut tout calculer, alors elle capture l'essence du calcul.
La machine a quatre composants :
Un ruban : une bande infinie de cases. Chaque case contient un symbole. Le ruban, c'est à la fois l'entrée, la sortie, et la mémoire.
Une tête de lecture/écriture : positionnée sur une case à chaque instant. Elle lit ce qu'il y a, peut écrire autre chose à la place, et se déplace d'une case vers la gauche ou la droite.
Un registre d'état : la machine est toujours dans un et un seul état parmi un ensemble fini. Il y a un état de départ, et des états de fin (acceptation ou rejet).
Une table de transition : c'est le "programme". Pour chaque combinaison (état actuel + symbole lu), elle dit exactement quoi faire, quel symbole écrire, dans quelle direction bouger, et vers quel nouvel état passer.
C'est tout. Pas de RAM, pas de GPU, pas de cache. Un ruban, une tête, des états, des règles. Et c'est suffisant pour modéliser tout calcul possible.
Un exemple pour que ça clique
Prenons une machine qui vérifie si un nombre binaire est pair (c'est-à-dire si son dernier chiffre est 0).
L'idée, c’est qu’on parcourt tout le nombre vers la droite jusqu'au bout, puis on revient regarder le dernier chiffre.
On a besoin de trois états de travail : démarrer, parcourir, vérifier, plus deux états finaux : accepté (pair) et rejeté (impair).
Sur l'entrée 10110 :
[1] 0 1 1 0 _ → Je suis en état "démarrer", je lis 1, j'avance → état "parcourir"
1 [0] 1 1 0 _ → Je lis 0, j'avance → je reste en "parcourir"
1 0 [1] 1 0 _ → Je lis 1, j'avance → je reste en "parcourir"
1 0 1 [1] 0 _ → Je lis 1, j'avance → je reste en "parcourir"
1 0 1 1 [0] _ → Je lis 0, j'avance → je reste en "parcourir"
1 0 1 1 0 [_] → Je lis un blanc, je recule → état "vérifier"
1 0 1 1 [0] _ → Je lis 0 → ACCEPTÉ ✓ (c'est pair !)
10110 en binaire, c'est 22 en décimal. Pair. La machine a trouvé le bon résultat.
Et c'est ça le truc assez bluffant en fait les ami(e)s codeurs, la machine n'a aucune intelligence. Elle ne "comprend" pas ce qu'est un nombre pair par exemple. Elle suit juste aveuglément ses règles de transition. Et pourtant, par le jeu mécanique des changements d'état, elle arrive au bon résultat.
Le calcul émerge du changement d'état.
Relisez bien cette phrase. C'est en fait littéralement ce qui va probablement être le fondement de tout ce qu'on va construire avec XState dans les prochaines semaines.
Le programme comme donnée
Turing ne s'arrête pas là. Il pousse l'idée encore plus loin avec la Machine de Turing Universelle, une machine capable de simuler n'importe quelle autre Machine de Turing.
Au lieu de câbler le programme dans la table de transition, on l'écrit sur le ruban, comme des données. La machine universelle lit cette description et l'exécute.
Le programme est une donnée.
Quand tu y réfléchis, c'est exactement ce que fait un ordinateur, le processeur (la machine) lit le programme (les données en mémoire) et l'exécute. L'architecture de von Neumann qu'on utilise tous les jours est une réalisation physique de ce concept.
Et c'est aussi, de manière plus subtile, ce que fait XState. Quand tu lui passes une définition de machine (un objet JavaScript), il l'interprète et la fait tourner. Ta définition est une donnée, l'interpréteur XState est la Machine de Turing Universelle. On y reviendra.
Le coup de grâce, certaines choses sont indécidables
Revenons à la question initiale d'Hilbert. Turing utilise sa machine pour formuler ce qui s’appellera le problème de l'arrêt :
Peut-on construire une machine qui, pour tout programme et toute entrée, détermine si ce programme finira par s'arrêter ou tournera en boucle à l'infini ?
Sa preuve d'impossibilité est redoutable.
Supposons qu'une telle machine H existe. Turing construit alors une machine "diabolique" D qui utilise H pour savoir si un programme s'arrête quand on le lance sur lui-même, et qui fait systématiquement le contraire de ce que H prédit.
Que se passe-t-il quand on donne D à elle-même ?
Si D s'arrête sur D, alors H aurait prédit "il s'arrête", donc D aurait dû boucler, contradiction. Si D boucle sur D, alors H aurait prédit "il boucle", donc D aurait dû s'arrêter, contradiction encore.
Dans les deux cas, ça casse. Donc H ne peut pas exister. Le problème de l'arrêt est indécidable.
Et puisque c'est un cas particulier de l'Entscheidungsproblem, il n'existe pas de procédure mécanique universelle pour déterminer la vérité mathématique. Hilbert avait tort sur les trois tableaux.
OK, et en quoi ça me concerne en tant que dev ?
Très concrètement ?
Il est impossible de créer un programme qui détecte tous les bugs dans tous les programmes. Si c'était possible, on résoudrait le problème de l'arrêt. C'est pour ça que les linters et analyseurs statiques ont des limites.
Il est impossible de créer un système de types parfait. Les systèmes de types font des compromis. C'est pour ça que TypeScript a ses limites et qu'on finit parfois par caster en any (oui, on l'a tous fait).
Les tests ne peuvent jamais garantir l'absence totale de bugs. Ils ne peuvent que démontrer leur présence.
Et voilà le pont vers les machines à état, le truc qui m'a fait tilter et qui doit vous faire tilter cette semaine.
C'est précisément parce que les programmes en général sont indécidables que les machines à état finies sont si précieuses. En restreignant volontairement notre système à un nombre fini d'états, on le rend décidable. On peut prouver des propriétés dessus. On peut vérifier qu'il n'y a pas de deadlock. On peut garantir qu'il se comporte correctement.
C'est un compromis, accepter une limitation (la finitude des états) pour gagner la certitude (la décidabilité).
Le concept d'état : ce que j'en retiens pour la suite
Cette semaine, la notion qui m'a le plus marqué, c'est la richesse du concept d'état.
Chez Turing, l'état d'une machine à un instant donné, c'est tout ce qu'il faut savoir pour prédire son comportement futur. Si tu connais l'état actuel et l'entrée qui arrive, tu sais exactement ce qui va se passer.
Transpose ça à une appli web : l'utilisateur est connecté ou déconnecté ? Le formulaire est en édition, en cours de soumission, en erreur ? Le paiement est en attente, accepté, refusé ? Ce sont des états. Et dans chaque état, le système ne réagit pas pareil aux mêmes événements. Un clic sur "Soumettre" ne fait pas la même chose en état "édition" qu'en état "en cours de soumission".
Turing sépare implicitement deux choses : le registre d'état (un ensemble fini et discret de configurations, tu es dans l'état q₃ ou q₇, jamais entre les deux) et le ruban (des données variables, potentiellement infinies). Le comportement dépend des deux.
Dans XState, cette distinction semble être exactement la même :
État fini → states: { idle, loading, success, error }
État étendu → context: { data: null, retryCount: 0, errorMessage: '' }
Les states, c'est le registre d'état de Turing. Le context, c'est le ruban. Cette séparation, née en 1936, est toujours la base conceptuelle de ce qu'on utilise aujourd'hui.
La Machine de Turing est déterministe : pour un état donné et un symbole lu donné, il y a exactement une action. Pas d'ambiguïté. Pas de "ça dépend". Et XState hérite directement de cette propriété. Même état + même événement = même résultat. Toujours. C'est un rêve pour le debugging, pour la testabilité, et pour dormir tranquille la nuit.
Les 5 principes que je retiens de cette semaine
1. L'état détermine le comportement. Pas les données, pas les variables, pas les flags booléens. Quand je modéliserai mes machines, la première question sera toujours : "Dans quels états distincts mon système peut-il se trouver ?"
2. Le calcul est une série de transitions. Chaque chose qui se passe est une transition d'un état à un autre, déclenchée par un événement. Rien ne se passe "entre" les états.
3. La finitude est une force. En acceptant de restreindre notre système à un nombre fini d'états, on gagne la capacité de le comprendre, le tester, et le prouver.
4. Le déterminisme est un super-pouvoir. Même état + même événement = même résultat. Toujours.
5. État fini et données variables sont deux choses différentes. Les modes d'un côté, les données de l'autre. Turing le savait, XState l'implémente.
La semaine prochaine
On avance sur la frise historique : McCulloch & Pitts (1943) et comment les neurosciences ont repris l'idée d'état de Turing pour modéliser le cerveau. Le premier pont entre biologie, logique et machines à état.
On se rapproche du code, promis. Mais ces fondations, elles vont nous porter pour toute la suite.
À vendredi prochain,
@LeDevNovice
Je code, je galère, je comprends, je partage.