Pourquoi les développeurs n'utilisent pas plus de machines à état ?

Posté par  (site web personnel) . Édité par baud123, rootix et NeoX. Modéré par rootix. Licence CC By‑SA.
Étiquettes :
63
1
fév.
2013
Technologie

Les langages de programmations, de quelques paradigmes qu'ils soient (bien qu'un peu moins pour le paradigme logique), sont basés sur le concept de liste d'instructions exécutées à la suite par la machine. La machine exécutant ce code est une machine à état, mais le programme n'est pas formellement pensé comme tel.

Les machines à état semblent pourtant un bon outil pour la programmation des logiciels que nous avons l'habitude de développer : facile à dessiner sur papier, permettant un découpage clair du fonctionnement de l'application.
Sans compter qu'une machine à état se patche plus facilement qu'un code classique où l'effet spaghetti peut vite impliquer des effets indésirables.
Les designers de Qt l'ont bien compris en permettant de définir des machines à état pour décrire le comportement du contrôleur.

C'est pourquoi certains se sont demandés si la programmation en machine à état ne devrait pas être plus pratiquée et aimée des programmeurs. C'est, par exemple, ce que se demande Willem van Bergen, carrément enthousiaste.
Celui-ci pense que c'est le stockage de l'historique qui est essentiel.

Plus circonspect, Alan Skorkin étudie la problématique de reprise de code, afin de comparer les approches, pour conclure que si les machines à états ne sont pas la panacée, elles sont très intéressantes si on conçoit le code avec.

Un très intéressant débat est né de cette polémique sur Hacker News.

Le point de vue du vieux singe (s/in/a/)

Un point de vue très intéressant d'un vieux programmeur nous racontant son expérience de HACMP en 1993. Il utilisait intensivement des machines à état pour gérer ses problèmes de protocoles gérant le cluster.
Selon lui les machines à état sont essentiellement boudées car mal codées à la base.
Pour être facile à utiliser il leur faudrait (traduction non littérale) :

  • Une manière simple de gérer les contextes entre états, ce qui doit être fait le plus souvent à la main
  • Un historique, dans les stacktrace, qui permette en particulier de connaître les changements d'états
  • La manière de coder les FSM implique que l'on contourne la vérification de typage, il faut donc mieux utiliser de la génération de code qui permettra de générer un code propre

Il conclue que si davantage de bonnes machines à états étaient implémentées, avec une gestion de contexte, un historique, et une machinerie de test, d'avantages de programmeurs les utiliseraient.

Machines à état fini hiérarchiques

La définition d'une machine à état peut vite devenir lourde à mesure que se complexifie le comportement. C'est pourquoi, on est amené à utiliser des machines à état hiérarchiques : chaque état peut comporter une machine à état (récursivement) qui s'active lorsqu'on passe dans l'état la contenant. Cela permet de définir des macro-comportement composés de micro-comportements.

Dans une telle machine, à chaque cycle, on va d'abord tester qu'une transition n'est pas à effectuer dans un état père. En l'occurrence, on part du père de plus haut degré, pour tester les transitions possibles. S'il n'y en a pas, on descend à son fils (dans la direction de l'état duquel on part à la base) et ainsi de suite, jusqu'à tester la transition de l'état courant vers un autre état auquel il est lié.

De même, si on effectue une transition sur l'un des père de cet état, on doit choisir son fils le plus "profond".
C'est un type de machine un peu plus difficile tant à écrire, qu'à vérifier la validité de son graphe, mais ce type de machine à état offre une facilité de conceptualisation : on retrouve l'effet "empilement de boîtes noires" qui a fait le succès du logiciel.

Une solution ?

Un agent (un objet, par exemple) dont le cycle de vie est géré par une machine à état. Chaque transition est basée sur une équation booléenne de conditions et d'évènements :

type 'event transition = 
  | Condition    of (unit -> bool) 
  | Event        of 'event * (unit -> 'event list ) 
  | EventOr      of 'event * (unit -> 'event list ) * 'event transition
  | EventAnd     of 'event * (unit -> 'event list ) * 'event transition
  | EventXor     of 'event * (unit -> 'event list ) * 'event transition
  | EventNot     of 'event * (unit -> 'event list ) 
  | ConditionOr  of (unit -> bool)   * 'event transition 
  | ConditionAnd of (unit -> bool)   * 'event transition
  | ConditionXor of (unit -> bool)   * 'event transition
  | ConditionNot of (unit -> bool);;

L'agent possède un historique de ses transitions (et donc des évènements extérieurs).

Ainsi, les données restent dans l'objet, ce qui résout les problèmes de contexte. En effet, les état/transitions s'appliquant sur un objet, tout ce qui est relatif au contexte reste au même endroit et non coincé dans chaque état.

Gestion d'historique

La gestion d'historique peut sembler gadget, mais il peut devenir utile lorsqu'il va servir d'élément pour décider une transition. On acquiert ainsi une proto sémantique logique temporelle à peu de frais.

Conclusion

Les machines à état sont certainement discréditées du fait de leur présentation trop théorique qui est assénée aux étudiants lors de leur études. C'est néanmoins un outil puissant qui nécessite que l'on réfléchisse un peu plus sérieusement à son intérêt.

Aller plus loin

  • # Quote

    Posté par  . Évalué à 10.

    Et comme on parlait d'Alan Cox il y a quelques temps:

    "A Computer is a state machine. Threads are for people who can't program state machines"

    -- Alan Cox

    • [^] # Re: Quote

      Posté par  . Évalué à 8.

      Sauf que c'est faux: un ordinateur multi-coeur, c'est plusieurs machines à états (une par coeur).

      • [^] # Re: Quote

        Posté par  . Évalué à 0.

        Hmmm… Et le produit de ces automates donnent l'etat global de la machine.

        • [^] # Re: Quote

          Posté par  . Évalué à 6.

          D'un point de vue théorique oui, mais à moins de disposer d'un générateur de code (bon courage pour débugger le résultat), si tu veux exploiter les n coeurs, tu vas écrire n-FSM.

          • [^] # Re: Quote

            Posté par  . Évalué à 0.

            Comme tu dis : d'un point de vue theorique si on ne prend pas en compte les interactions des langages. En effet, tes processeurs touchent a une memoire globale. D'ou des interactions entres tes differents automates. Cela se traduit assez facilement : il n'y a un seul langage quelques que soit le nombre de processeurs de ta machine (et on ne parle pas de connection entre ordinateurs via des cables reseaux). D'un point de vue theorique le produit de tes n automates est different de l'automate prennant en compte directement tous les processeurs d'un seul coup.

            Certain vont se poser la question de pourquoi il peut y avoir des interactions entre les processeurs. La reponse suppose un petit bagage theorique sur le fonctionnement des systemes d'exploitations. Le systeme d'exploitation gere les processus des programmes. Ces processus sont un ensemble d'element tel que le programme source (le programme charge en memoire), la memoire utilise, mais egalement un certain nombre de threads. Ces threads s'ils sont geres par le processeur peuvent tourner de facon parallele sur des processeurs differents. Comme chacun sait, des threads peuvent avoir un commun une memoire partage. Voici une des interactions que peuvent avoir les processeurs.

  • # Un peu plus de détail ?

    Posté par  . Évalué à 10.

    Bonjour,

    Je pense qu'il aurait été intéressant de rajouter à cette article une introduction sur le concept de machine a états (pour faciliter la compréhension par le lectorat).

    Point de réflexions très intéressants en tout cas.

  • # Historique

    Posté par  . Évalué à 10. Dernière modification le 01 février 2013 à 12:57.

    Gestion d'historique

    La gestion d'historique peut sembler gadget, mais il peut devenir utile lorsqu'il va servir d'élément pour décider une transition.

    Un automate a état fini n'a pas besoin de l'historique pour déterminer une transition. Il lui faut :

    • un état
    • un évènement

    Si dans l'état tu met l'historique des états, tu n'es plus dans un automate à état fini.

    À mon humble avis, c'est surtout utile pour pouvoir débuger le comportement.

    Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

    • [^] # Re: Historique

      Posté par  . Évalué à 2.

      Tu as plusieurs raisons utiles a la conservation de l'historique: audit, debug, analyses statistiques. Le premier de la dépêche l'explique bien. En particulier, j'ai bossé sur une application ou tout (ou presque) devait être audité: chaque objet métier avait un "statut" qui était la machine a état du pauvre. Et bien c'est super utile pour retracer l'historique de ton objet métier (audit) voire comprendre comment ton objet est arrivé dans l'état actuel (a quelle date, a recouper avec les logs). C'est une min d'or d'informations. D'ailleurs, on ne faisait pas un "delete" sur les objets en base de donnée: on les marquait comme inactifs, complétés, annulés, etc. (en plus, ça améliorait les perfs en évitant un table lock)

      • [^] # Re: Historique

        Posté par  . Évalué à 2.

        On ne parle alors pas d'automates finis au sens de la theorie (si tu nous donnes pas plus d'information). Pour information, un automate a une memoire mais bornee.

      • [^] # Re: Historique

        Posté par  (site web personnel) . Évalué à 4.

        Et après, tu peux même appliquer des suites de tests à tes logs de machine à état. J'avais lu un article intéressant sur le sujet et pour une application complexe, ça peut être une assez bonne idée. Tu définis des prédicats et tu les vérifies sur l'ensemble des logs. Ca permet d'auditer un certain nombre d'assertion en production. Il y a des langages et des outils dédiés bien sur pour faire tout ça.

  • # Question

    Posté par  . Évalué à 3.

    La manière de coder les FSM implique que l'on contourne la vérification de typage, il faut donc mieux utiliser de la génération de code qui permettra de générer un code propre

    Je ne comprend pas je n'ai jamais eu l'impression de leurrer le typage en écrivant un automate.

    Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

    • [^] # Re:

      Posté par  . Évalué à 1.

      La programmation par FSM est très intéressante, et particulièrement utile en réseaux. Mon expérience, l'implémentation du protocole réseau Rapid Spanning Tree, décrit par une 10ene de FSM collaboratives dans sa documentation. Assez complexe, mais une fois que la bibliothèque de gestion des FSM est codée et bien testée, le reste est purement de la recopie de spécification d'un graphique à un fichier de description etat/action/transition…, un bonheur à débugger ;)

      • [^] # Re:

        Posté par  . Évalué à 4.

        Là c'est un peu facile comme cas d'utilisation: il faut que tu recopie une machine à états déjà faite qui marche et qui ne peut pas changée. Dans la vraie vie, ils y a des normes qui ont des machines à état buggées, et c'est marrant de voir comment les implémenteur se vautrent une fois qu'ils ont découvert que la machine à état ne peut pas marcher. Le problème, c'est que généralement, ils ne changent pas la structure de la machine à état.

        Et surtout, le problème des machines à états dans les réseaux, c'est que tu ne sais pas quoi faire d'événements qui ne sont pas censés arriver, et donc tu n'a pas deux implémentations qui font la même chose. Les protocoles qui sont spécifiés par du code asynchrones ne permettent pas d'ambiguïtés.

  • # excellent post

    Posté par  (site web personnel) . Évalué à 10.

    Si t'as pas développé ta "machine à état" avant 50ans, c'est que t'as raté ta vie de dev ;-)

    Sans blagues, je connaissais le concept, mais comme beaucoup de dev, ça ne me parlait pas beaucoup.

    Sous l'impulsion d'un projet PRO, qui consiste à virer JBPM d'un projet (*). Je me suis beaucoup pencher dessus, et j'ai trouvé le concept plus qu'intéressant, au point de m'opposer à sa suppression ;-).
    Pour garder le concept de "machine à état" dans le projet, j'ai tenté de re-développer la "mienne" … Conceptualisé en python, et recodé en java : elle fonctionne parfaitement, en se basant sur des descriptifs de nodes en YAML (plus lisible que du xml).
    J'ai fait un convertisseur de "process def jbpm" en yaml. Et sans beaucoup de changements, ça fonctionne "out of the box" (sans toucher au fonctionnel). ça fait une 100aine de lignes de codes, et ça marche.
    Mais ça m'a surtout permis de rentrer dans le fonctionnement d'une machine à état.

    Les avantages sont énormes:
    - dans notre cas : on reprends la main sur la machine, et on l'adapte à nos besoins sans soucis.
    - On peut générer des beaux graphiques, pour les décideurs pressés (via yapgvb/graphviz). Ce qui permet également de bien comprendre les enchainements, le fonctionnel.
    - on peut changer de "moteur" (ce n'est que des conversions de process, et des adaptations de code … on ne change pas le "fonctionnel") : en gros, ça permet d'abstraire le fonctionnel du technique.

    Bref, je suis devenu un fervent défenseur des "machines à état". Et merci pour ce post, qui m'amène encore un peu plus loin dans leurs compréhensions. (ça donnerait presque envi de re-tenter QT (on est vendredi, hein ?))

    (*) : brique proprio, et probs d'empreintes mémoires en jvm.

  • # GRAFCET

    Posté par  . Évalué à 5.

    Machine à état fini, ça me rappelle le grafcet de mes études : http://fr.wikipedia.org/wiki/Grafcet
    Il y a une possibilité de transformer le dessin en code.
    de mémoire chaque état étant un booleen égal à (étape antérieur et condition entrante )ou (état et pas étape suivante), le tout calculé à rebours du parcours
    Il me semble même que les automaticiens arrivaient à fournir un temps d’exécution de la boucle prédictif.
    Je vous renvoie au cours d’algorithme d'automatique…

    • [^] # Re: GRAFCET

      Posté par  . Évalué à 1.

      ah oui moi aussi j'ai fait du grafcet au lycée, j'étais pas très fan, j'ai été amené à en faire un énorme sur un ordinateur goupil (trop bon…)
      je croyais que c'en était fini entre moi et les automates, car ça m'avait bien gavé, mais en lisant des articles sur les compilateurs j'ai vu que ça pouvait être vachement intéressant.

      sinon à part le grafcet, il y a les réseaux de pétri, j'ai eu des cours là dessus à l'école. A ce que je m'en souviens c'est un genre de grafcet avec des jetons.

      • [^] # Re: GRAFCET

        Posté par  (site web personnel) . Évalué à 3.

        sur un ordinateur goupil (trop bon

        je confirme, c'était top, et comme il n'y avait pas de détrompeur, tu avais une chance sur deux de le cramer en le branchant !

        ウィズコロナ

  • # une raison

    Posté par  (site web personnel) . Évalué à 4.

    Les FSM sont peu utilisés car la plupart des langages de programmation ne les supportent pas nativement.

    Une rare exception est mbeddr C qui est construit sous forme d'extension au langage C (pour le domaine de l'embarqué).

    Hormis cette exception, on est obligé de passer par un DSL et le compilateur/générateur associé pour obtenir le code de l'application. Cela complexifie le processus de construction surtout si on utilise un IDE dédié à un langage (vive make et tous les outils qui laissent la liberté aux développeurs).
    L'article cite comme exemple, l'outil CHSM, j'ajouterai SMC car il permet de cibler une quinzaine de langage (mais je suis partial en tant que contributeur).

  • # mi homme mi machine, il peut survivre 3 mois dans la jungle en mangeant ses propres états

    Posté par  (site web personnel) . Évalué à 5.

    J'utilise une sorte de machine à états dans Newton Adventure, mais j'ai du faire pas mal d'exception au principe pour:

    • gérer des choses globales comme la sauvegarde de la progression dans le jeu.
    • permettre la séquence pause => menu de configuration => reprise du jeu.
    • permettre la séquence passage au niveau bonus => reprise du jeu normal.
    • gérer le chargement de données multithreadé.

    Je n'est pas trop réfléchi à la bonne façon de gérer ces problèmes…

    Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.

  • # Y a pas que moi quand même ?

    Posté par  (site web personnel, Mastodon) . Évalué à 3.

    Dites, je suis quand même pas le seul à utiliser le patron de conception des états, si ?
    Ok, faut l'adapter pour chaque projet.
    Ok, ça gère pas le hiérarchique (enfin, avec un peu de jugeotte, ça se fait).

    Mais bon, globalement, ça peut le faire.

    • [^] # Re: Y a pas que moi quand même ?

      Posté par  (site web personnel) . Évalué à 3.

      Non, non, tu n'es pas le seul :-)

      On avait un processus qui était simple a départ et qui de verrue en verrue était devenu une sorte de Shoggoth immonde qu'on n'avait pas envie de toucher.
      Et un jour, après avoir lu un tutoriel OpenGL (qui est, à la base, une machine à états) j'ai eu une révélation : en fait, on pouvait parfaitement recoder notre monstre en machine à états toute simple.
      Ça a été un peu de boulot pour éviter les régressions, mais au final le résultat est maintenant beaucoup plus petit. On sait clairement ce que fait chaque étape et quel est l'état du "dossier" en cours. Et ajouter des étapes intermédiaires n'est plus un calvaire.

      Ce n'est pas une solution magique, dans le sens où rien n'empêche d'avoir un état qui fait n'importe quoi. Mais c'est une aide pour organiser et maintenir les choses sous contrôle.

    • [^] # Re: Y a pas que moi quand même ?

      Posté par  . Évalué à 3.

      Ça dépende de la taille, pour parser (avec une API type SAX) un fichier xml ou html, non. Ce serait comme sortir les orgues de Staline pour planter un clou dans un mur.

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

  • # automates à pile

    Posté par  . Évalué à 2.

    une petite question comme ça, quelqu'un n'aurait pas un lien vers un "cours" sur les automates à pile qui soit pas trop compliqué ?

    • [^] # Re: automates à pile

      Posté par  (site web personnel) . Évalué à 2.

      Un peu comme une machine d'état ou tu tiens compte aussi de l'état précédent?

      "La première sécurité est la liberté"

      • [^] # Re: automates à pile

        Posté par  . Évalué à 3.

        Les automates a pile ne sont pas beaucoup plus compliques quel les FSM. Tu as des operations sur chaque etat qui push ou qui pop l'etat courant dans la pile (donc globale) de l'automate. De meme, les transitions doivent supporter des testes sur l'etat de la pile (Est-elle vide ? Quel est le dernier etat ? Quels sont les n derniers etats ?). Ainsi tu peux reconnaitre des langages du type anbn alors que tu ne pouvais pas avec des automates finis.

        L'automates pour ce dernier exemple est construit facilement. On lit des a en pushant l'etat dans la pile. Puis on lit que des b en poppant la pile. On acceptera le mot si la pile est vide et qu'il n'y a plus de lettre a lire.

  • # Un article qui m'a mis le pied à l'étrier

    Posté par  (site web personnel) . Évalué à 5. Dernière modification le 01 février 2013 à 22:39.

    J'avais besoin de multi-tâches mais pas les moyens en mémoire embarquée pour un OS. À partir de cet article j'ai développé une machine d'état pour gérer l'enregistrement de données sur SDCard formatée FAT.

    Voici quelques macros en C facilitant l'implémentation de la machine et un fichier qui les utilise.

    « J'ai pas Word, j'ai pas Windows, et j'ai pas la télé ! »

  • # VFSM

    Posté par  . Évalué à 1.

    S'il est vrai que l'on ne croise pas beaucoup d'automates (machine à état) dans le monde du "gros" logiciel, en revanche, c'est très utilisé en électronique.

    Pour le boulot j'ai réalisé un projet (service de traitement d'images) avec au départ un nombre limité de fonctionnalité. Face au résultat encourageant, on m'a vite demandé d'ajouter telle ou telle fonctionnalités dont certaines sortaient largement du cadre de départ. J'ai vite compris qu'il me faudrait un moyen de gérer des ajouts/exceptions fonctionnels importants si je ne voulais pas tout re-coder (ou presque) à chaque fois.
    Pour la v2, j'ai choisi de coder ma propre VFSM (machine à état fini virtuel) et de lui déléguer toute l'intelligence fonctionnelle. En dehors des avantages "techniques" à utiliser des automates, ça m'a aussi permis de pouvoir m'adapter très vite au changement SANS générer de complexité, puisque seul la description formelle de l'automate change.
    Aujourd'hui je me demande encore pourquoi je n'ai pas utilisé d'automate plus souvent :)

  • # Commentaire supprimé

    Posté par  . Évalué à 6.

    Ce commentaire a été supprimé par l’équipe de modération.

  • # sous titre ambigu

    Posté par  (site web personnel) . Évalué à 10. Dernière modification le 02 février 2013 à 13:53.

    Le point de vue du vieux singe (s/in/a/)

    c'est moi ou ça donne : "Le poat de vue du vieux singe"
    c'est très poatique tout ça :-D

    kentoc'h mervel eget bezan saotred

    • [^] # Re: sous titre ambigu

      Posté par  . Évalué à 2.

      Il manque des options sur LinuxFR : j'aurais voulu cliquer sur le bouton "Ce commentaire est inutile mas augmente-lui sa note quand même" :D

  • # Paradoxe temporel

    Posté par  . Évalué à 7.

    On acquiert ainsi une proto sémantique logique temporelle à peu de frais.

    On t'a reconnu Doc ! Elle est garée où ta Delorean ?

  • # Un exemple marrant : le wireless MAC processor

    Posté par  . Évalué à 2.

    J'ai vu ya quelques temps une conf de Giuseppe Bianchi qui présentait un travail de son équipe : le Wireless MAC Processor, un firmware pour carte wifi Broadcom qui interprète un automate à état fini (un peu étendu) qui définit le protocole de controle d'accès au média (MAC) utilisé ! Ainsi, on peut très facilement changer le MAC sans devoir connaître l'assembleur ARM/MIPS.

    J'ai souvenir qu'ainsi, le DCF (utilisé en wifi) était défini en quelques centaines d'octets.

    Les liens :
    http://wmp.tti.unipa.it/index.php/8-infos/20-introduction
    http://euronf.enst.fr/archive/185/2012_02_13_slides_5.pff

    Pour info, c'est l'équipe qui avait déjà reverse engineeré le firmware broadcom afin d'en faire un libre, openFWWF http://www.ing.unibs.it/~openfwwf/

    • [^] # Re: Un exemple marrant : le wireless MAC processor

      Posté par  . Évalué à 3. Dernière modification le 03 février 2013 à 10:33.

      Comme ils le disent si bien, ça ne supporte pas le rts/cts et la qos. Si on rajoute ça et toutes les combinaisons possibles en 802.11n du genre protection HT/green field et la plétore d'*ifs, la machine à état, même hiérarchique, va devenir un joyeux bordel.

      Le problème des machines à états, c'est que tout rajout de fonctionnalité produit des patches très invasifs.

    • [^] # Re: Un exemple marrant : le wireless MAC processor

      Posté par  . Évalué à 2.

      À noter, l'erreur dans le deuxième lien : l'extension est bien « pdf » et non « pff ».

  • # exemple en C

    Posté par  . Évalué à 3.

    Une machine à états, ça peut être aussi simple que ça, en C, si j'ai bien compris :

    void traiterMessage(...)
    ...
    switch (etat) {
    case READY:
        ...
    case REQUEST_PENDING:
        ...
    case STOPPED:
        ...
    }
}

    J'ai bon ?

    • [^] # Re: exemple en C

      Posté par  . Évalué à 1.

      De façon minimaliste, oui. C'est avec des machines à états (mais pas uniquement) que l'on implémente des parseurs à expressions rationnelles. Mais là, c'est un peu plus "complet" ;)

  • # Ragel

    Posté par  (site web personnel) . Évalué à 0.

    Il y a quand même pas mal de code qui utilise des automates, et des outils bien conçus pour ça. Je vais juste laisser ce petit lien ici : http://www.complang.org/ragel/ ;)

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.