Was sind das für Zustände?

Zustandsmaschinen dienen in der Informatik zur Modellierung von Verhalten. Sie werden besonders gerne zur Spezifikation technischer Systeme eingesetzt. Oben im Bild sehen Sie ein einfaches Zustandsdiagramm. Zustandsdiagramme sind eine verbreitete Notation zur Darstellung von Zustandsmaschinen. Die Notation ist in der Unified Modeling Language (UML) standardisiert.

In dem Beispiel geht es um einen Roboterarm. Der Roboterarm ist entweder in dem Zustand "idle", "moving up/down" bzw. "welding" (schweißen); Zustände werden durch Rechtecke mit runden Ecken abgebildet. Der Start- und der Endzustand sind durch besondere Symbole hervorgehoben: durch einen Kreis (Start) bzw. einen Punkt im Kreis (Ende).

Die Pfeile beschreiben Übergänge (Transitionen) von einem Zustand in einen anderen und zwar abhängig von einem Ereignis. Die Ereignisse sind hier durch Buchstaben abgekürzt und stehen immer links vom Schrägstrich "/". Es sind Ereignisse, die der Roboter über seine Sensoren wahrnimmt. Die meisten der Ereignisse werden durch Steuerungssensoren wahrgenommen. Wenn ein Anwender den "down"-Knopf drückt, dann löst er damit das "d"-Ereignis aus. Ein "up" führt zu einem "u"-Ereignis, ein "s" zu "stop" und ein "o" ist die Folge eines "on"- bzw. "off"-Signals. Einzig das "c"-Ereignis wird durch einen Kontakt-Sensor ("contact") im Roboterarm ausgelöst. Dann "fühlt" der Roboterarm einen Widerstand.

Zu jedem Ereignis ist rechts vom Schrägstrich angegeben, was der Roboterarm für eine Aktion folgen lässt. Grundsätzlich möglich sind die Aktionen "move down", "move up", "stop moving", "weld" (schweiße), "initialize" und "shut down".

Befindet sich der Roboterarm im Zustand "idle" und tritt das Ereignis "d" auf (sprich, der Anwender hat den "down"-Knopf gedrückt"), dann bewegt sich der Roboterarm nach unten. Der Zustand wechselt von "idle" auf "moving down". Weitere "d"-Ereignisse bleiben ohne Folge, da sich der Roboterarm bereits in der Abwärtsbewegung befindet. Im Zustand "moving down" bewegt ein "u" den Arm wieder nach oben, ein "c" stößt die Schweiß-Aktivität an. Beim "u"-Ereignis wechselt der Zustand zu "moving up", beim "c"-Ereignis zu "welding".

Eine solche Zustandsmaschine kann man systematisch in Code übertragen. Der Vorgang ist derart schematisch, dass man ihn leicht automatisieren kann. Dafür übertragen wir in einem ersten Schritt das Diagramm in ein maschinenlesbares Format. Ich habe mich für XML entschieden. (Hinweis: Für die nachstehenden Code-Auszüge verwende ich den syntaxhighlighter. Möglicherweise gibt es Darstellungsprobleme, wenn Sie z.B. einen RSS-Reader nutzen. Dann besuchen Sie einfach direkt die Blogseite zum Posting.)

<br /><?xml version="1.0" encoding="utf-8"?><br /><fsm name="Robot" version="1.0" … ><br /> <states><br /> <state name="start" type="init"/><br /> <state name="end" type="final"/><br /> <state name="idle"/><br /> <state name="moving up"/><br /> <state name="moving down"/><br /> <state name="welding"/><br /> </states><br /> <transitions><br /> <transition fromState="start" toState="idle" event="o"><br /> printf(">>> initialize\n");<br /> </transition><br /> <transition fromState="idle" toState="end" event="o"><br /> printf(">>> shut down\n");<br /> </transition><br /> <transition fromState="idle" toState="moving down" event="d"><br /> printf(">>> move down\n");<br /> </transition><br /> <transition fromState="moving down" toState="moving down" event="d"><br /> /* don't do anything */<br /> </transition><br /> <transition fromState="moving down" toState="idle" event="s"><br /> printf(">>> stop moving\n");<br /> </transition><br /> <transition fromState="moving down" toState="moving up" event="u"><br /> printf(">>> move up\n");<br /> </transition><br /> <transition fromState="moving down" toState="welding" event="c"><br /> printf(">>> weld\n");<br /> </transition><br /> <transition fromState="welding" toState="moving up" event="u"><br /> printf(">>> move up\n");<br /> </transition><br /> <transition fromState="moving up" toState="idle" event="s"><br /> printf(">>> stop moving\n");<br /> </transition><br /> <transition fromState="moving up" toState="moving down" event="d"><br /> printf(">>> move down\n");<br /> </transition><br /> </transitions><br /></fsm><br />

Das Eingangstag <fsm> steht für finite state maschine. Es folgt die Liste der (endlich vielen) Zustände, wobei der Start- und der Endzustand beliebig benannt werden können, sie dafür aber mit Hilfe des type-Attributes auszuweisen sind. Die Liste der Transitionen ist nahezu selbsterklärend. Die Aktionen geben wir als Programmcode in der Sprache C an. Das ist in dem Beispiel die Sprache, in der wir den Roboterarm programmieren, was nicht untypisch für Steuergeräte oder eingebettete Systeme ist. Zu Demonstrationszwecken ersetzen einfache printf-Statements "echte" Aktionen.

Das Interface des zu generierenden Codes -- Funktionsprototypen in C -- sieht wie folgt aus. Es ist absichtlich so einfach gehalten.

char * get_initState(void);
char * get_finalState(void);
char * get_toState(char *fromState, char *event);
void do_action(char *fromState, char *event);

Es ist einfach zu erraten, wie der generierte Code zu "get_initState" und "get_finalState" aussieht:

char * get_initState(void) { return "start"; }
char * get_finalState(void) { return "end"; }

Die Funktion "get_toState" liefert auf Angabe von "fromState" und "event" den dazugehörigen "toState" zurück. Ein Beispiel:

char * get_toState(char *fromState, char *event) {
  if (strcmp("idle",fromState) == 0 && strcmp("o",event) == 0)
      return "end";
}

Ein Kinderspiel, nicht wahr? Die Funktion "do_action" arbeitet ganz ähnlich, sie bettet im if-Rumpf den Aktionscode zur Transition ein:

void do_action(char *fromState, char *event) {
  if (strcmp("idle",fromState) == 0 && strcmp("o",event) == 0) {
    printf(">>> shut down\n");
}

Wenn wir einen Code-Generator haben, der die XML-Darstellung in diese Code-Schemata umwandelt, dann benötigen wir nur noch ein Abarbeitungsprogramm, das Steuerprogramm im Roboterarm, das auf Ereignisse wartet (Tastendrücke in unserem Beispiel), gemäß Zustandsmaschine die entsprechenden Aktionen ausführt und in einen neuen Zustand wechselt oder den bisherigen beibehält. (Die Funktion _getch() ist übrigens eine nicht standardgemäße Bibliotheksfunktion aus Pelles C zum Lesen eines Zeichens von der Tastatur.)

<br />#include <stdio.h><br />#include <stdlib.h><br />#include <conio.h> // not C99<br />#include <assert.h><br /><br />#include "fsm.c"<br /><br />int main() {<br /> char event[2] = "?"; // [0]: signal character, [1]: \0 (end of string)<br /> char * currentState;<br /> char * nextState;<br /> char * finalState;<br /><br /> currentState = get_initState();<br /> finalState = get_finalState();<br /><br /> printf("initializing: initState = %s, finalState = %s\n",currentState, finalState);<br /> assert (strcmp(currentState,finalState) != 0);<br /><br /> // CONTROLLER<br /> for (;;) {<br /> printf("scanning ...\n");<br /> event[0] = _getch();<br /> printf("<<< signal %s\n",event);<br /><br /> nextState = get_toState(currentState,event);<br /> if (strcmp(nextState,"") == 0) {<br /> printf("critical situation\n>>> move to safety position\n");<br /> break;<br /> }<br /><br /> do_action(currentState,event); <br /> currentState = nextState;<br /> if (strcmp(currentState,finalState) == 0) break;<br /> }<br /> printf("I'm done\n>>> shut down\n");<br /> return EXIT_SUCCESS;<br />}<br />

Wie aus dem Code ersichtlich ist, ignoriert die Steuerung nicht etwa Ereignisse für die keine Transition in einem Zustand definiert ist, sondern aktiviert eine Safety-Routine. Das ist ein durchaus sinnvolles Vorgehen bei Steuerungsaufgaben, die im Fehlerfall schwerwiegende Folgen nach sich ziehen können.

Stellt sich nur noch die Frage, wie der Code-Generator aussieht. Ich habe ihn in Python programmiert. Das Programm ist nicht sonderlich elegant, erfüllt aber zur Anschauung seinen Zweck.

<br />import sys, time<br />from xml.dom.minidom import parse<br /><br />assert len(sys.argv) > 1, "file needed for code generation"<br />fsm = parse(sys.argv[1])<br /><br />states = fsm.getElementsByTagName("state")<br />transitions = fsm.getElementsByTagName("transition")<br /><br />for state in states:<br /> statename = state.getAttribute("name")<br /> statetype = state.getAttribute("type") <br /> if statetype == "init": initState = statename<br /> elif statetype == "final": finalState = statename<br /> <br />## Assert that inital and final state are given <br />assert initState, "An init state must be given"<br />assert finalState,"A final state must be given"<br /><br />## CodeGeneration: get_initState and get_finalState<br />get_initState = 'char * get_initState(void) { return "%s"; }\n' % initState<br />get_finalState = 'char * get_finalState(void) { return "%s"; }\n' % finalState<br /><br />## Assert constraints on fromState and toState<br />statenames = [state.getAttribute("name") for state in states]<br />for transition in transitions:<br /> assert transition.getAttribute("fromState") in statenames,\<br /> "fromState is given in list of states"<br /> assert transition.getAttribute("toState") in statenames,\<br /> "toState is given in list of states"<br /> <br />## Assert determinism<br />stateevents = []<br />for transition in transitions:<br /> stateevent = (transition.getAttribute("fromState"),<br /> transition.getAttribute("event"))<br /> assert stateevent not in stateevents, "FSM must be deterministic"<br /> stateevents.append(stateevent)<br /><br />## CodeGeneration: get_toState<br />## ~~~~~~~~~~~~~~~~~~~~~~~~~~~<br />code = """<br />char * get_toState(char *fromState, char *event) {<br />"""<br />for state in states:<br /> for transition in transitions:<br /> if transition.getAttribute("fromState") == state.getAttribute("name"):<br /> code += """<br /> if (strcmp("%s",fromState) == 0 && strcmp("%s",event) == 0)<br /> return "%s";<br /> """ % (state.getAttribute("name"),<br /> transition.getAttribute("event"),<br /> transition.getAttribute("toState"))<br />code += """<br /> return "";<br />} // end of function<br />"""<br />get_toState = code<br /><br />## CodeGeneration: do_action<br />## ~~~~~~~~~~~~~~~~~~~~~~~~~<br />code = """<br />void do_action(char *fromState, char *event) {<br />"""<br />for state in states:<br /> for transition in transitions:<br /> if transition.getAttribute("fromState") == state.getAttribute("name"):<br /> code += """<br /> if (strcmp("%s",fromState) == 0 && strcmp("%s",event) == 0) {<br /> // ACTION CODE<br /> %s<br /> }<br /> """ % (state.getAttribute("name"),<br /> transition.getAttribute("event"),<br /> transition.firstChild.data)<br />code += """<br />} // end of function<br />""" <br />do_action = code <br /><br />header = """/* THIS IS GENERATED CODE -- PLEASE DO NOT EDIT THIS FILE */<br />/* CodeGeneration by %s, %s */<br />#include <string.h><br />#include <stdlib.h><br />#include <stdio.h><br /><br />""" % (sys.argv[0], time.ctime())<br /><br />print header + get_initState + get_finalState + get_toState + do_action<br /><br />

Wenn Sie mögen, können Sie nun mit der Ergänzung um weitere Features beginnen. Wie wäre es mit hierachischen Zustandsmaschinen? Timer sind etwas sehr nützliches. Und wie wäre es mit nebenläufigen Zustandsmaschinen? Sehr leicht ist es, die Zustände um Aktionen zu bereichen. Ein Feature aus der UML sind Aktionen beim Eintritt (entry) und beim Verlassen (exit) eines Zustands. Transitionen kann man um Guards erweitern. Guards knüpfen das Ereignis an eine Bedingung, die zusätzlich erfüllt sein muss.

Sie werden feststellen, dass es gar nicht so schwer ist, sich ein XML-Schema für sehr komplexe und mit allen Featuren ausgerüstete Zustandsmaschinen auszudenken und dazu einen Code-Generator zu entwickeln.

(P.S.: Die an dieser Stelle zuvor berichteten Probleme mit dem Syntax-Highlighting haben sich gelöst. Allerdings scheint der Chrome-Browser Schwierigkeiten bei der Darstellung des letzten Code-Auszugs, dem Python-Code, zu haben. Strange! Kennt jemand einen Workaround?)