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.

Utiliser les bookmarks dans Vim

J’utilise Vim en tant qu’IDE pour développer et j’utiliser depuis peu de temps les Bookmarks que je trouve très pratique. Je vais vous présenter ici l’utilisation de ces derniers. Ils permettent d’enregistrer un emplacement précis dans un fichier (ligne et colonne), afin d’y revenir facilement par la suite.

Une fois cette fonctionnalité maîtrisé, vous allez gagner en productivité. Dans Vim les Bookmarks s’appellent des « Marks« , mais pour des raisons de simplicité, j’appellerai ça des bookmarks.

Il existe deux types de bookmarks dans Vim :

  • les locaux
  • les globaux

Les bookmarks locaux sont destinés à être utilisés quand vous travaillez sur qu’un seul fichiers à la fois. Les bookrmarks globaux sont eux destinés à être utilisés quand vous travaillez sur plusieurs fichiers en même temps.

Vous allez voir, c’est beaucoup plus simple que ça en a l’air.

Bookmark local dans Vim

Si vous travaillez avec un seul fichier et souhaitez enregistrer une position spécifique (ligne) alors vous pouvez utiliser les Bookmarks locaux. Les noms des Bookmarks locaux sont en minuscules.

Comment créer un Bookmark dans Vim

Dans Vim en mode commande, tapez m{name} , name est le nom du bookmark. 

Par exemple si vous tapez « ma », cela va créer un bookmark sur la ligne courante nommé « a ».

Dans l’exemple suivant via la commande « ma » vous pouvez créer un bookmark nommé « a » qui se trouve à la ligne et à la colonne où se trouve le curseur. 

Bookmark de la position courante dans Vim via la commande ma

 

Accéder aux bookmarks dans Vim

Pour utiliser les bookmarks créés dans Vim, il existe deux méthodes : 

  1. La première méthode consiste à utiliser la commande suivante :  `{name}  

    Ceci à pour conséquence d’aller directement sur le Bookmark nommé, en positionnant le curseur sur la ligne et la colonne qui correspondent à celles enregistrées lors de la création du Bookmark.
    Par exemple, si vous tapez la commande `a  cela va positionner le curseur sur la ligne et la colonne qui correspondent à celles où se trouvait le curseur lors de la création du Bookmark.

  2. La deuxième méthode consiste à utiliser la commande : '{name}   

    La commande vous emmène sur le Bookmark enregistré, mais positionne cette fois-ci le curseur au début de la ligne.

Bookmark globaux dans Vim

Quand vous avez plusieurs fichiers ouverts dans Vim et souhaitez travailler à des lignes spécifiques sur chacun de ces fichiers, alors vous pouvez utiliser les Bookmarks globaux.

Un Bookmark global a un nom en majuscule.

La commande « mA » créé un bookmark global nommé « A ».

Afficher l’ensemble des Bookmarks

Ci-dessus, la commande :marks  indique que j’ai créé :

  • un bookmark local, nommé « b » à la ligne 10, colonne 12. Ca nous affiche aussi un extrait de la ligne 10.
  • un bookmark global, nommé « G » à la ligne 56, colonne 0. 

En dehors des bookmarks ci-dessus, Vim gère des bookmarks par défauts sur lesquels vous n’avez pas de contrôle. 

Si vous utilisez  la commande marks vous devriez avoir les informations suivantes qui s’affichent.

Le bookmark « . » indique la position où la dernière modification a été effectuée. Donc si vous utilisez la commande `.  vim vous positionnera à l’endroit où la dernière modification a eu lieu.

 

Bref récapitulatif

  • ma  – création d’un bookmark nommé « a »
  • `a  – Aller sur la position exacte (ligne et colonne) du bookmark nommé « a »
  • 'a  – Aller au début de la ligne du bookmark nommé « a »
  • :marks  – Afficher tous les bookmarks
  • :marks a  – Afficher les détails du bookmarks nommé « a »
  • '.  – Aller à la position exacte (ligne et colonne) où la dernière modification a eu lieu
  • '.   – Aller au début de la dernière ligne modifiée

 

 

 

 

 

Avoir une corbeille avec la commande rm

Quand on est un adepte de la ligne de commande, on aime manipuler nos fichiers de travail avec les commandes usuelles (cd, ls, mv, rm). Seulement voilà, si vous êtes comme moi, vous savez qu’il arrive parfois de supprimer un fichier par erreur, ou de vouloir recuperer un fichier qu’on avait supprimer il y a quelque jour.

Alors, là, on se dit que Linux n’est pas si puissant que ça. Quel dommage ne ne pas avoir une corbeille permettant de contenir les fichiers dont on veut se debarrasser.

J’ai décidé ce matin de creer dans mon bashrc un alias de la commande rm afin que cette derniere ne supprime plus mes fichiers mais les deplaces dans un repertoire « Poubelle ».

An commençant mon alis, j’ai rencontré rapidement quelques soucis, j’ai donc du creer une fonction appellée rm dans mon fichier bashrc. Cette fonction va être appelée à chaque fois que la commande rm est tapée dans le terminal.

Cette fonction, vérifie s’il y a des options passées à l’appelle de la commande, si c’est le cas, alors elle verifie s’il y a l’option force (-f), si ce n’est pas le cas alors le ou les fichiers (ou repertoires) sont deplacés dans le repertoire POUBELLE défini dans la variable POUBELLE_DIRECTORY. Vous pouvez mettre le chemin du repertoire que vous souhaitez utiliser comme corbeille. Si le repertoire n’existe pas alors la fonction le creera automatiquement. Pas belle la vie?

J’oubliais de vous dire, si l’option -f est utilisée avec l’appelle de la commande rm, alors le ou les fichiers seront reelements surpprimés.

Interfaces C++ (classes abstraites)

Une interface décrit le comportement ou les capacités d’une classe C++ sans pour autant imposer une implémentation spécifique à cette dernière. 

Les interfaces C++ sont faites à l’aide des classes abstraites.

Nous sommes faces à une classe abstraite dès qu’une des fonctions est déclarée virtuelle pure. Une fonction est virtuelle lorsqu’on ajoute « =0 » après sa déclaration.

Ci-dessou, voici un exemple de déclaration d’une méthode virtuelle pure :

L’objectif d’une classe abstraite est de fournir aux autres classes une classe de base appropriée dont elles pourront hériter. Les classes abstraites ne peuvent être instanciées, ni servir seulement d’interface. Tenter d’instancier un objet à partir d’une classe abstraite cause une erreur de compilation.

L’objet d’une classe abstraite est de fournir une classe de base appropriée à partir de laquelle les autres classes pourront hériter. Les classes abstraites ne peuvent pas être utilisées pour instancier des objets. Si vous essayez d’instancier un objet à partir d’une classe abstraite, vous aurez une erreur de compilation.

Par conséquent, si vous souhaitez instancier la sous classe (d’une classe abstraite) il est nécessaire que vous implémentiez chacune des fonctions virtuelles. Sinon vous aurez une erreur de compilation.

On appelle classes concrètes les classes pouvant être utilisées pour instancier des objets.

Exemple d’une Classe Abstraite

Considérons l’exemple suivant dans lequel une classe mère fournit une interface à la classe de base pour implémenter une fonction appelée getSurface().

 

Lorsque le code ci-dessus est compilé et exécuté il produit le résultat suivant :

Vous pouvez voir dans l’exemple ci-dessus comment une classe abstraite définit une interface avec getSurface() et comment deux autres classes implémentent cette même fonction mais avec un algorithme différent pour calculer la surface spécifique à la forme géométrique.

Stratégie de conception

Une architecture orientée objet doit utiliser des classes de base abstraites pour fournir des interfaces standards et communes aux applications utilisatrices. 

Donc, par héritage de ces classe abstraites, les classes dérivées sont construites pour fonctionner toutes de la même façon. 

Les possibilités (e.g. fonctions publiques) offertes aux fonctions externes sont fournies en tant que méthodes virtuelles pures dans la classe de base abstraite. Les implémentations de ces méthodes virtuelles pures sont fournies dans les classes dérivées qui sont conformes au genre spécifique du programme.

De plus cette architecture permet à de nouvelles fonctions d’être ajoutées facilement au système.

 

Librairie C Fonction – strcmp()

Syntax

Description

La fonction strcmp compare deux chaines de caractères str1 et str2. La fonction commence en comparant les deux premiers caractères de chaque chaîne. S’ils sont égaux, la fonction prend la pair de caractères suivante et continue tant que les caractères ne sont pas différents ou tant que le caractère de fin ‘\0’ n’est pas détecté.
 

Valeurs de retour

Retourne un entier indiquant les différences détectées.

<0Le premier caractère qui est différent a une valeur plus petite dans str1 que str2 
0Le contenu des deux chaines est le même
>0Le premier caractère différent trouvé a une valeur plus grande dans str1 que str2

 

 

 

Exemple

Sortie

 

Librairie C Fonction – strcpy()

Syntax

Description

La fonction strcpy() copie la chaine pointée par source, sur le tampon pointé par destination. La copie comprend le caractère de terminaison ‘\0’. Attention, le tampon de destination doit être suffisamment grand afin de pouvoir recevoir la chaîne de caractères.

Exemple

Dans l’exemple ci-dessus, on copie la chaîne s1 dans s2.

Lire un fichier en C avec fgetc

Nous allons au travers de ce tutoriel expliquer comment programmer en C  la lecture d’un fichier texte. Nous expliquerons chaque ligne de code ajoutée afin d’arriver à un programme fonctionnel.

Tout d’abord, afin de faire des opérations d’entrées sorties, commençons par inclure le fichier d’entête stdio.h (Standard Input/Ouuput Header).

Tout programme écrit en C doit contenir une fonction principale appelée main, c’est à partir de cette dernière que débute un programme.

Comme vous pouvez le voir ci-dessus, à la ligne 3, le mot clé int précède la fonction main pour indiquer que cette dernière retourne un entier.

Nous ajoutons la primitive return à la fin de notre fonction afin de retourner une valeur.

Habituellement un programme retourne 1 en cas d’erreur sinon 0. Considérons que si notre programme arrive à la fin de la fonction main c’est qu’il n’y a pas eu d’erreur.

Afin de pouvoir lire notre fichier nous avons besoin du pointeur de fichier :

FILE* pFichier

Pour stocker les caractères nous utilisons la variable (type entier) :

int c

Nous ouvrons le fichier avec la fonction fopen qui retourne un pointeur sur le fichier. En cas d’échec elle retourne NULL.

La valeur de retour de la fonction fopen est utilisée afin d’initialiser notre pointeur pFichier .

La fonction fopen attend deux paramètres qui sont respectivement, le nom du fichier et mode d’ouverture.

Nous ouvrons un fichier nommé fichier.txt et utilisons le mode d’ouverture « r » pour read (accès en lecture).

Si un echec a eu lieu lors de l’ouverture du fichier, le pointeur pFichier est égal à NULL, dans ce cas nous affichons un message d’erreur à l’aide de la fonction  perror.

La fonction fgetc lit le fichier et retourne le caractère courant, la position dans le fichier est modifiée.

Affichons sur la sortie standard le caractère lu à l’aide de la fonction printf. Nous indiquons que nous souhaitons afficher un caractère avec %c et nous lui fournissons le caractère à afficher c en paramètre.

Notre programme n’est pas encore fini, il lit pour l’instant que le premier caractère du fichier avant de se terminer.

Implémentons une boucle afin d’appeler la fonction fgetc tant que des caractères sont présents. Nous pouvons savoir lorsque nous sommes à la fin du fichier grâce à la fonction fgetc qui retournera dans ce cas EOF.

Ajoutons une boucle infinie while depuis laquelle nous sortirons si le caractère EOF est détecté.

Si le caractère courant est égal à EOF (End Of File – Fin du fichier) nous sortons de la boucle  à l’aide de l’instruction break .

Ajoutons l’instruction fclose afin de fermer correctement le fichier une fois la lecture terminée.

Ne plus répondre au ping

Vous pourriez avoir envie de configurer votre machine pour ne plus qu’elle réponde aux ping pour de multiples raisons, comme par exemple des raisons de sécurité ou éviter de congestionner le réseau.

Quelqu’un pourrait par exemple nuire s’il inondait (flood) le réseau avec la commande ping -f.

En désactivant, sur votre machine Linux, la réponse au ping, ce genre de problème est éviter.

Ne plus répondre au ping temporairement

Vous pouvez dire au système de ne plus répondre au ping temporairement à l’aide de la méthode suivante :

Notez que cette modification est temporaire et qu’elle sera automatiquement perdue après un simple redémarrage de votre système.

Pour que votre système réponde au ping à nouveau (sans le redémarrer) mettez la valeur « 0 » comme dans l’exemple ci-dessous :

Ne plus répondre au ping de manière permanente

Il est possible de configurer votre système afin qu’il ne réponde plus au ping de manière permanente. En utilisant la méthode ci-dessous, votre machine Linux ne répondra plus au ping et ce même après un redémarrage.

Etape 1 : Editez le fichier sysctl.conf et ajouter la ligne suivante.

Etape 2 : Exécutez la commande sysctl -p pour que la modification soit prise en compte immédiatement.

La commande ci-dessus recharge la configuration de systcl à partir du fichier de configuration « systcl.conf ».

 

 

Après avoir utilisé l’une des méthodes ci-dessus qui comme nous l’avons vu permet de désactivé la réponse au ping sur un système Linux, si une personne ping votre machine, ce dernier n’aura aucune réponse. Votre système ne répondra plus aux requêtes Ping.

 

 

Afficher le nombre d’arguments en C

Ci-dessous un morceau de code en langage c qui affiche simplement le nombre d’arguments passés en paramètre au programme.

Ci-dessus, notre code source.

Maintenant compilons…

Et lançons notre programme.

Tiens!! bizarre?!? Il affiche 1 alors que je n’ai fourni aucun parametre. Je vais lui donné un paramètre pour voir ce que cela donne.

Ah ben, ca y est, je crois avoir compris. Vous aussi? Le nom du programme est lui aussi comptabilisé.

 

Hello world en langage C

Dans cet article je vais vous montrer comment faire un hello world en langage C sous Linux.