machines à états

Introduction

Le but de cet article est de fournir une introduction utile et pratique de la technique des machines à états finis. Dans cet article, l’accent sera mis sur le côté pratique de la définition et de l’explication, plutôt que sur les concepts théoriques et mathématiques lourds qui sous-tendent la technique. 

Une Machine à Etats c’est quoi?

Les développeurs ont besoin aujourd’hui de trouver des astuces leur permettant de réduire les délais de mise sur le marché tout en augmentant la fiabilité et la maintenabilité du code. L’un des outils que beaucoup de développeurs connaissent mais n’utilisent pas souvent est la machine à états. C’est d’autant plus vrai pour les informaticiens autodidactes qui n’ont pas été formés par des professeurs d’informatique. Les machines à états sont l’un des outils les plus simples et utiles que nous avons à notre disposition. Elles permettent de diviser les algorithmes complexes et pénibles en petits éléments faciles à gérer. Les machines à états introduisent une architecture de programmation qui peut être utilisée pour implémenter n’importe quel algorithme qui peut être explicitement décrit par un diagramme d’état ou un organigramme. Les machines à états sont devenues extrêmement populaires et ont aidé les développeurs de jeux à construire des jeux amusants.

La machine à états est un mécanisme abstrait qui possède un certain nombre d’états prédéfinis. Suivant l’usage prévu les données fournies à la machine entraînent un changement d’état. Nous nous intéressons ici aux machines à états finis (qui ont un nombre fini d’états) implémentées dans des logiciels et matériels. Nous examinerons un certain nombre d’exemples.

Les petites machines à états sont représentées par des diagrammes à bulles, chaque bulle représentant un état de repos. Voir Figure 1. Les lignes entre les états sont appelées des transitions. Une machine à états ne peut avoir qu’un seul état à la fois, ne peut passer d’un état à un autre qu’en respectant des transitions prédéfinies et des conditions indiquées. 

Exemple d’une machine à états basique

Dans l’exemple, la machine à états recherche les occurrences des lettres «A» et «B» dans un flux de texte. (D’où vient le texte et comment la machine à états détecte les caractères? Les détails ne sont généralement pas exprimés sur le diagramme).

Lorsqu’un ‘A’ est détecté dans le flux à l’état 0, la machine effectue une transition de l’état 0 à l’état 1, en suivant la direction de la flèche. Si un ‘B’ est détecté dans l’état 1, une transition est faite vers l’état 0. Comme la machine à états ne peut avoir qu’un seul état à la fois, l’état actif indique si le dernier caractère détecté était «A» ou «B». Il est concevable qu’un autre caractère puisse être reçu (‘C’), auquel cas aucune transition ne se produit.

Simple Machines à états

Figure 1 – Machines à états basique

C’est un exemple trivial, bien sûr. Dans la réalité, des actions sont également associées à chaque transition.

Exemple d’une machine à états avec actions associées

Par exemple, allumer une LED verte lorsque « A » est détecté, et une LED rouge lorsque « B » est détecté. Si une condition d’un état devient vraie, l’état est modifié et une action peut être prise en conséquence. L’action est notée sur le bord. Voir la figure 2.

Machines à états avec actions associées

Figure – Machines à états avec actions associées

Les deux principaux types de machines à états sont celles de Mealy et Moore. Les machines de Mealy effectuent : une action lorsqu’une transition se produit, des actions à l’intérieur de chaque état. nous parlons dans cet articles des machines de Mealy. 

Les transitions pour sortir d’un état

Dans chaque état le code examine seulement les conditions liées aux transitions de sortie de l’état. C’est un point très important. Lorsque vous concevez une machine à états et réfléchissez à un état, vous n’avez qu’à vous soucier des transitions qui sortent de ce dernier. Une fois que la machine est dans un état, la façon dont elle y est arrivée n’est pas important. Donc, le programme que vous écrivez doit seulement être préoccupé par les transitions qui sortent d’un état

Exemple avec le Baseball

Examinons un exemple avec du baseball. Les quatre bases sont les états. L’objectif est de passer de la maison (home plate) à la première base, puis à la deuxième base, la troisième base, et de nouveau à la maison. Une fois que vous arrivez à la deuxième base, qui se soucie de comment vous y êtes arrivé? Votre objectif est maintenant de tenter d’aller (transition) à la troisième base. De la même manière, l’état d’une machine ne se préoccupe pas sur la façon dont il est apparu, mais seulement sur ce qu’il doit faire. 

Pourquoi utiliser des machines à états?

Alors, avant de plonger et passer beaucoup de temps dans le codage des machines à états, pourquoi les utiliser? Pour certaines tâches, les machines d’état sont plus faciles à penser et à lire que les méthodes procédurales telles que les organigrammes ou les pseudocodes. Une définition procédurale d’une tâche est habituellement chargée d’une grande partie du détail de l’opération en cours, alors qu’un diagramme d’état vit à un niveau supérieur, laissant de côté une grande partie des détails ennuyeux. Je ne commets pas d’hérésie, en niant l’utilité d’autres méthodes, mais il y a des moments où les machines d’état sont juste le bon outil.

Pour résoudre quels problèmes?

Les machines à états sont appropriées pour tout problème où le système occupe différents états de repos distincts. Les machines à états ne sont généralement pas appropriées pour les algorithmes mathématiques. D’un autre côté, les machines d’état sont appropriées pour les interfaces utilisateur, les protocoles de communication et certaines tâches de reconnaissance de formes car la fonction du système ou du processus peut être décomposée en étapes discrètes.

Diviser les fonctions du système

Un autre avantage des machines d’état est que l’état actuel du système est complètement résumé par un numéro. La machine à états est conçue pour incarner dans chaque état un fonctionnement significatif du système. Ce processus de conception met en lumière les sections (divisions) naturellement présentes dans les fonctions du système

Offre une vue de haut niveau

Il en résulte que l’état de la machine est objectivement significatif pour le concepteur, en tant que vue de haut niveau, plus qu’une valeur de compteur de programme, un numéro de page d’organigramme, un niveau d’imbrication if-then-else ou une valeur variable. Même les systèmes compliqués avec des dizaines de milliers de lignes de code peuvent être rendus dans quelques dizaines d’états; le système fonctionne en petits morceaux qui peuvent être facilement compris

Une conception facile à modifier

Les conceptions de machines d’état sont généralement faciles à modifier. En fonction de votre implémentation spécifique et des restrictions matérielles / logicielles, le câblage d’un autre état dans une machine existante n’est pas difficile. Il s’agit d’une demande fréquente sur les interfaces utilisateur dans les programmes embarqués : « Oui, Romain, cette machine à coiffure automatisée est superbe, mais pouvez-vous ajouter trois actions supplémentaires à la clé? les machines d’état rendent cela facile, et Romain n’a même pas à travailler pendant le déjeuner !

Impact et régression minimiser

Enfin, avec précaution (et vous êtes un programmeur prudent), il est possible dans une machine de modifier le comportement d’un état sans se soucier d’avoir une régression et un impact sur le fonctionnement des autres états et de devoir débogué le code; contrairement aux grands programmes procéduraux entremêlés qui peuvent partager de grandes quantités de code de manière non intuitive et sournoise.

Toujours réticents?

Nous semblons être réticents à l’égard des machines à états en raison d’une mauvaise compréhension de leur complexité et/ou d’une incapacité à quantifier les avantages. Mais, il y a moins de complexité que vous ne le pensez et plus d’avantages qu’on ne s’ y attendrait. Ainsi, la prochaine fois que vous aurez un objet qui suggère même d’avoir qu’un champ « status », n’hésitez pas à y mettre une machine à états, vous serez heureux de l’avoir fait.

Avantages des machines à états

  • Leur simplicité facilite la mise en œuvre par des développeurs inexpérimentés;
  • Compte tenu d’un ensemble d’entrées et de l’état actuel connu, il est possible de prédire la transition entre les états, ce qui facilite les tests;
  • En raison de leur simplicité, les machines à états sont rapides à concevoir, à mettre en œuvre et à exécuter;
  • Les machines à états représente une technique ancienne de modélisation de systèmes qui a fait ses preuves depuis longtemps; et qui a fait ses preuves même en tant que technique d’intelligence artificielle.
  • Les machines à états sont relativement flexibles. Il existe plusieurs façons de mettre en œuvre un système basé sur les machines à états en termes de topologie; 
  • Transfert facile d’une représentation abstraite significative vers une implémentation codée;
  • Faible surcharge processeur; bien adapté aux domaines où le temps d’exécution est partagé entre modules ou sous-systèmes. Seul le code de l’état actuel doit être exécuté, et peut-être un peu de logique pour déterminer l’état actuel;
  • Détermination facile de l’accessibilité d’un état, lorsqu’il est représenté sous une forme abstraite, il est immédiatement évident de savoir si un état est réalisable à partir d’un autre état, et ce qui est nécessaire pour atteindre l’état.

Inconvénients des machines à états

  • La nature prévisible des machines à états déterministes peut être indésirable dans certains domaines tels que les jeux d’ordinateur;
  • Larger systems implemented using FSM can be difficult to manage and maintainwithout a well thought out design. The state transitions can cause a fair degree of “spaghetti- factor” when trying to follow the line of execution;
  • Il peut être difficile de gérer et d’entretenir des systèmes plus grands mis en œuvre à l’aide d’une machine à états sans une conception bien pensée. Les transitions d’état peuvent causer un certain degré de « facteur spaghetti » en essayant de suivre la ligne d’exécution;
  • Ne convient pas à tous les domaines problématiques, ne devrait être utilisé que lorsque le comportement d’un système peut se lier à des états séparés. Cela signifie que tous les états, transitions et conditions doivent être connus d’avance et bien définis;
  • Les conditions pour les transitions d’états sont crénelées, ce qui signifie qu’elles sont fixes.

Machines à états pour quels domaines?

L’heuristique pour déterminer quand et comment implémenter des machines à états finis est et spécifique au problème. Les machines à états sont bien adaptés aux domaines de problèmes qui s’expriment facilement à l’aide d’un organigramme; et qui possèdent un ensemble d’états et de règles bien définis pour gouverner les transitions d’états.

Commentaires
  • jean-louis dit :

    Merci, c’est très intéressant et bien expliqué, ce qui n’est pas forcément facile à faire pour un outil abstrait tel que celui-ci.

    Je ne connaissais pas du tout cette outil et cet article est pour moi une première.

    Merci encore.

    jean-louis

    • Romain dit :

      Merci pour votre commentaire, j’ai pu lors d’un projet conséquent implementé une machine à état, malgré l’ajout de fonctionnalités au fil de l’eau sur les demandes du client, le logiciel est resté toujours tres facile à maintenir. De plus l’ajout des fonctionnalités restaient faciles.

Laisser un commentaire
You must be logged in to comment.