INTRODUCTION

Il est nécessaire de définir exactement ce qu’est un ordinateur avant de pouvoir déterminer dans quelle mesure il est capable de résoudre tel ou tel problème. Le célèbre mathématicien et informaticien Alan Turing publia une étude à ce sujet en 1936, bien avant que le premier ordinateur digital programmable n’existe. La machine de Turing, baptisée ainsi en l’honneur de Turing, passe successivement par différents états de manière programmée sur la base de données lues sur une bande et écrites sur cette même bande. Cette notion fondamentale qui touche au fonctionnement de l’ordinateur est encore valable actuellement puisque tous les processeurs présents dans nos ordinateurs sont en fait des machines de Turing qui passent d’un état à l’autre à la cadence de l’horloge. Cependant, les machines à états qui peuvent être modélisées par un graphe de transition se prêtent mieux aux application pratiques. Du fait qu’elles ne disposent que d’un nombre fini d’états, on les appelle des automates finis (finite-state machines en anglais).

LA MACHINE ESPRESSO COMME MACHINE DE MEALY

Chaque jour, nous sommes tous confrontés à des appareils et machines qui peuvent être considérés comme des automates parmi lesquels on trouve les distributeurs automatiques de boissons ou de billets de banque, les machines à laver et tant d’autres. Un ingénieur ou un informaticien développant de telles machines se doit de comprendre clairement qu’elles effectuent leur tâche en passant de l’état courant à un état successeur. Ces transitions d’état sont déterminées par les entrées de l’automate, à savoir les données en provenance des capteurs ou des interrupteurs formant l’interface de commande. En fonction des données en entrée, l’opérateur actionne certains actuateurs lors de chaque transition d’états tels que des moteurs, des pompes, des témoins lumineux qui constituent les sorties de l’automate.

Dans le cas présent, nous allons développer une machine à café espresso pouvant se trouver dans trois états différents : elle peut être éteinte (OFF), allumée et en attente (STANDBY) ou en train de pomper et chauffer de l’eau pour préparer un espresso (WORKING). L’interface de contrôle de la machine comporte quatre boutons-poussoirs : turnOn, turnOff, work, et stop.

Bien qu’il soit possible de décrire le fonctionnement d’une machine à café espresso en prose, un graphe de transition est bien plus clair et explicite. Un tel graphe est formé de cercles représentant les différents états (nœuds du graphe) et de flèches (arête orientée) passant d’un état à l’autre et formalisant les transitions d’états. Les flèches sont étiquetées par les entrées / sorties qui causent la transition en question. Il est également important de définir l’état initial de la machine lorsqu’elle est mise en fonction. Du fait que n’importe quelle touche peut être actionnée dans n’importe lequel des états, toutes les entrées doivent être envisagées à chaque état. Si aucune action n’est effectuée, la sortie est omise.

Graphe de transition :

On résume souvent le comportement de la machine dans un tableau qui spécifie pour chaque état s et chaque entrée t (ici les boutons actionnés) l’état successeur s'. L’état initial est dénoté par une étoile.

Table de transition:

En termes mathématiques, on peut dire que l’état successeur s' est une fonction de l’état courant et de l’entrée t : s' = F(s, t). La fonction F est appelée fonction de transition.

On peut également spécifier dans un tel tableau les sorties correspondant à chaque état et chaque donnée en entrée :

Table de sortie:

À nouveau, on peut dire que, mathématiquement, la sortie g est une fonction de l’état courant et des entrées : g = G(s, t). G est appelée fonction de sortie.

MEMENTO

IMPLÉMENTATION DE LA MACHINE ESPRESSO AVEC DES CHAÎNES DE CARACTÈRES

La pression d’un bouton devrait engendrer une transition d’un état à l’état suivant. Les 4 touches directionnelles du clavier serviront à simuler les boutons de la machine et spécifient les valeurs en entrée. L’implémentation est relativement triviale : le programme attend qu’une touche soit enfoncée au sein d’une boucle d’événements (event loop) infinie avec getKeyEvent(). Selon la valeur de retour de getKeyEvent(), l’état courant est modifié d’après la table de transition et les sorties sont calculées en fonction de la table de sortie.

from gconsole import *

def getEntry():
    keyCode = getKeyCodeWait()
    if keyCode == 38: # up  
        return "stop"
    if keyCode == 40: # down
        return "work"
    if keyCode == 37: # left
        return "turnOff"
    if keyCode == 39: # right
        return "turnOn"
    return ""
    
state = "OFF"  # Start state
makeConsole()
while True:
    gprintln("State: " + state)
    entry = getEntry()
    if entry == "turnOff":
       if state == "STANDBY":
            state = "OFF"
            gprintln("LED off")
       if state == "WORKING":
            state = "OFF"
            gprintln("LED and pump off")
    elif entry == "turnOn":
        if state == "OFF":
            state = "STANDBY"
            gprintln("LED enabled")
    elif entry == "stop":
        if state == "WORKING":
            state = "STANDBY"
            gprintln("Pumpe off")
    elif entry == "work":
        if state == "STANDBY":
            state = "WORKING"
            gprintln("Pumpe enabled")

MEMENTO

TYPES ÉNUMÉRÉS COMME ÉTATS ET IDENTIFIANTS D’ÉVÉNEMENTS

Puisque les automates fonctionnent sur la base d’états, de valeurs en entrée et de valeurs en sortie, il serait avantageux d’introduire une structure de données particulière spécialement adaptée. De nombreux langages de programmation mettent à disposition un type de données particulier pour les énumérations. Malheureusement, ce type de données n’est pas présent dans la syntaxe du langage Python standard. Heureusement, il a été ajouté à TigerJython grâce au mot-clé additionnel enum() qui permet de définir des valeurs énumérées à partir de chaines de caractères respectant les contraintes et conventions de nommage en vigueur pour les noms de variables.

from gconsole import *

def getEvent():
    keyCode = getKeyCodeWait()
    if keyCode == 38: # up  
        return Events.stop
    if keyCode == 40: # down
        return Events.work
    if keyCode == 37: # left
        return Events.turnOff
    if keyCode == 39: # right
        return Events.turnOn
    return None
    
State = enum("OFF", "STANDBY", "WORKING")
state = State.OFF
Events = enum("turnOn", "turnOff", "stop", "work")
makeConsole()
while True:
    gprintln("State: " + str(state))
    event = getEvent()
    if event == Events.turnOn:
        if state == State.OFF:
            state = State.STANDBY
    elif event == Events.turnOff:
            state = State.OFF
    elif event == Events.work:
        if state == State.STANDBY:
            state = State.WORKING
    elif event == Events.stop:
        if state == State.WORKING:
            state = State.STANDBY

MEMENTO

IMPLÉMENTATION DE LA MACHINE ESPRESSO AVEC CONTRÔLE DE LA SOURIS

MEMENTO

PENSER LES INTERFACES GRAPHIQUES EN TERMES D’ÉTATS

À première vue, les machines de Mealy semblent être confinées au monde des théories fumeuses. Mais il faut, bien au contraire, toujours penser en termes d’états lors du développement de programmes événementiels comportant une interface utilisateur graphique. En guise d’exemple, écrivons un petit programme tortue contrôlé par 3 boutons. Le bouton start_button démarre le mouvement de la tortue, le bouton stop_button l’interrompt et le bouton quit_button termine le programme. Afin d’implémenter ce programme correctement, il est nécessaire de garder en tête le graphe de transition:

Comme nous l’avons déjà vu à maintes reprises, il ne faut jamais effectuer le rendu d’une animation au sein des gestionnaires d’événements de l’interface graphique car ces derniers ne supportent que l’exécution d’un code très rapide. Cela vient du fait que le rendu à l’écran n’est effectué qu’à la fin de la fonction de rappel. C’est la raison pour laquelle on se contente, au sein du gestionnaire de clic sur les boutons, de modifier l’état de sorte que le mouvement de la tortue est effectué dans la partie principale du programme.

(Vous pouvez en apprendre davantage au sujet de ce problème dans l’annexe 4 Traitement parallèleg)

from javax.swing import JButton
from gturtle import *

def buttonCallback(evt):
    global state
    source = evt.getSource()
    if source == runBtn:
        state = State.RUNNING
        setTitle("State: RUNNING")
    if source == stopBtn:
        state = State.STOPPED
        setTitle("State: STOPPED")
    if source == quitBtn:
        state = State.QUITTING
        setTitle("State: QUITTING")

State = enum("STOPPED", "RUNNING", "QUITTING")
state = State.STOPPED

runBtn = JButton("Run", actionPerformed = buttonCallback)
stopBtn = JButton("Stop", actionPerformed = buttonCallback)
quitBtn = JButton("Quit", actionPerformed = buttonCallback)
makeTurtle()
setTitle("State: STOPPED")
back(100)

pg = getPlayground()
pg.add(runBtn)
pg.add(stopBtn)
pg.add(quitBtn)
pg.validate()

while state != State.QUITTING and not isDisposed():
    if state == State.RUNNING:
          forward(200).left(127)
dispose()         

MEMENTO

EXERCICES

MATÉRIEL SUPPLÉMENTAIRE

ACCEPTEURS POUR LANGAGES RATIONNELS (RÉGULIERS)

Un langage formel est constitué d’un alphabet de symboles et d’un jeu de règles permettant de déterminer de manière univoque si une séquence de symboles particulière appartient ou non au langage en question. S’il est possible d’implémenter les règles en utilisant un automate, on parle de langage régulier ou langage rationnel.

Comme exemple, considérons un langage très simple dont l’alphabet est constitué uniquement des lettres A et B. On peut considérer le jeu de règles comme une machine de Mealy spéciale qui n’engendre aucune valeur de sortie. En l’occurrence, la machine lit l’expression caractère après caractère en partant d’un état initial et effectue une transition vers l’état successeur sur la base du caractère lu. Si l’automate se trouve dans l’un des états finaux prédéterminés après la lecture de la séquence de caractères, l’expression en question appartient au langage. Considérons le graphe de transition suivant (S: état initial, A: état final):

Dans l’implémentation ci-dessous, le changement d’état est déclenché par la pression de la touche A ou B du clavier. Le programme imprime ensuite l’état courant et le mot saisi dans la console.

from gconsole import *

def getKeyEvent():
    global word
    keyCode = getKeyCodeWait(True)
    if keyCode == KeyEvent.VK_A:
        return Events.a
    if keyCode == KeyEvent.VK_B:
        return Events.b
    return None

State = enum("S", "A", "B")
state = State.S
Events = enum("a", "b")
makeConsole()
word = ""
gprintln("State: " + str(state))
while True:
    entry = getKeyEvent()
    if entry == Events.a:
        if state == State.A:
            state = State.S
        elif state == State.B:
            state = State.S
        word += "a"
        gprint("Word: " + word + " -> ")
        gprintln("State: " + str(state))
    elif entry == Events.b:
        if state == State.S:
            state = State.B
        elif state == State.B:
            state = State.A
        word += "b"
        gprint("Word: " + word + " -> ")
        gprintln("State: " + str(state))

MEMENTO

EXERCICES