Embed Size (px)
Citation preview
OO-Modellierung und Implementierung eines endlichen Zustandsautomaten
VL MRT-2, SS 2013 Professur für Prozessleittechnik
Übersicht
• Anwendungsbeispiel: Endlicher Zustandsautomat
• C++ Konzepte:
– Vertiefung const
– Freundkonzept
– Spezialisierung von Klassen
– virtuelle Methoden und abstrakte Klassen
• Entwurfsmuster:
– Strategiemuster
18.04.2013 Folie 2 MRT2 (c) 2013, UR
Anwendung: Endlicher Zustandsautomat (finite state machine)
• Modell zur mathematischen Beschreibung von Verhalten, beispielsweise für die Steuerung von Anlagen, Robotern, NPC
– Vorlesung Prof. Janschek: Steuerung diskreter Systeme
– Hauptseminar AMR: Einparkhilfe VIDEO
• Komponenten eines Automaten (generalisiert, UML)
– Zustand: Endlich viele, zu jedem Zeitpunkt ist der Automat in genau einem Zustand
– Startzustand: Zustand zum Zeitpunkt t=0
– Übergang(Transition): Übergang zwischen zwei Zuständen
– Bedingung(Wächter): Voraussetzung für das Ausführen eines Übergangs (Ereignisse, Eingaben, ...)
– Verhalten: wird beim Betreten, Verharren und Verlassen eines Zustands oder bei einem Übergang ausgeführt
18.04.2013 MRT2 (c) 2013, UR Folie 3
Verhaltensspezifikationen
• am Zustand
– Eingangsaktion (entry behaviour)
• Wird bei Eintreten in Zustand ausgeführt
– Ausgangsaktion (exit behaviour):
• wird bei Verlassen des Zustands ausgeführt
– Zustandsaktion (doActivity) :
• wird ausgeführt während sich Automat in Zustand befindet
• am Übergang:
– Übergangsaktion (effect)
• Wird ausgeführt, wenn Zustandsübergang durchlaufen wird
• Je nach Automatenart werden nur Teilmengen benötigt, beispielsweise nur Effekte oder Zustandsaktionen
18.04.2013 MRT2 (c) 2013, UR Folie 4
Anwendungsbeispiel: Baustellenampeln mit Übergangsaktionen
18.04.2013 MRT2 (c) 2013, UR Folie 5
[IS-links] [t>30s] / l-g
[IS-rechts] [t>30s] / r-g
[t>60s &&
IS-rechts] / l-r
[t>60s &&
IS-links] / r-r
UML Aktivitätsdiagramm
18.04.2013 MRT2 (c) 2013, UR Folie 6
Objektorientierte Analyse
• Erste Idee für Klassenstruktur
– Automat
• aktueller Zustand (= Startzustand bei t=0)
• Methode zum Ausführen des Automaten
– Zustand
• Liste aller Transitionen aus diesem Zustand
• Methoden für enter, do, exit
– Transition
• Methoden für Wächterfunktion (guard) und Übergangsverhalten (effect)
• Zielzustand der Transition
18.04.2013 MRT2 (c) 2013, UR Folie 7
Diskussion des Entwurfs
• Zeitoptimal
– bei jedem Schritt wird nur über die Menge der Ausgangstransitionen des aktuellen Zustands iteriert
• Aber: Zirkuläre Abhängigkeit Zustand / Transition
– State.h: #include "Transition.h"
class State { ... }
– Transition.h #include "State.h"
class State; // forward declaration
class Transition { ... }
• Schlechtes Design! – Bei Änderungen in einer Klasse muss auch die andere übersetzt werden,
– Schwierigkeiten bei Freigabe von dynamisch angelegtem Speicher,
– ...
18.04.2013 MRT2 (c) 2013, UR Folie 8
Neuer Ansatz Transitionstabelle
18.04.2013 MRT2 (c) 2013, UR Folie 9
• Transition kennt start und ziel
• Zustand braucht Transition nicht zu kennen
• Direkt aus Graph ablesbar
Start Wächter Effekt Ziel
AlleRot IS-Links LinksLeeren
LinksLeeren z>30 LinksGrün
LinksGrün IS-Rechts && z>60 RechtsLeeren
AlleRot IS-Rechts RechtsLeeren
RechtsLeeren z>30 RechtsGrün
RechtsGrün IS-Links && z>60 LinksLeeren
Deklaration State
#include <string> // Zeichenketten-template aus STL
using namespace std;
class State {
private:
const string id; // Identifier
public:
State(const string& id) : id(id) { }; // Konstruktor
void enter() const; // Verhaltensspezifikation Eintritt
void stay() const; // Verhaltensspezifikation Aufenthalt
void exit() const; // Verhaltensspezifikation Ausgang
const string& getID(); // Zugriff auf Identifier
};
18.04.2013 MRT2 (c) 2013, UR Folie 10
Nicht veränderliches
Objekt
Soll beim Anlegen
einer Instanz aber
gesetzt werden?
Lösung: Element-
initialisierungsliste
C++: Elementinitialisierungsliste
• Liste von Konstruktoren für die Elemente zwischen Kopf und Körper der Konstruktormethode
State::State(const string& id) : id(id) { };
• Anweisungen der Elementinitialisierungsliste werden ausgeführt bevor das Objekt „lebt“
– Klassentypen ohne Standardkonstruktoren und const Elemente müssen in der Elementinitialisierungsliste definiert werden!
• Die Reihenfolge der Elementinitialisierung wird durch die Reihenfolge der Definition der Elemente bestimmt.
– Moderne Compiler warnen, wenn Sie eine Diskrepanz zwischen Elementinitialisierungsliste und Definitionsreihenfolge finden
• Kein Überdecken bei Namensgleichheit von Argument und Element
18.04.2013 MRT2 (c) 2013, UR Folie 11
C++: const (Teil 1)
• Anweisung ab den Compiler Konstrukte zurückzuweisen, die potentiell zu einer (unbeabsichtigten) Änderung führen können.
• Fall 1: Konstante Objektinstanzen
– das Objekt und seine Elemente werden nach Initialisierung nicht mehr verändert!
– const string id; // Identifier
• Fall 2: Nichtmodifizierende Methoden
– die Methode soll die Objektinstanz nicht ändern
– void exit() const;
• Fall 3: Referenz auf ein konstantes Objekt
– Das Objekt soll auch an anderer Stelle nicht geändert werden
– const string& getID();
18.04.2013 MRT2 (c) 2013, UR Folie 12
Nichtelementmethoden zu State Ausgabe auf Strom: operator<<
[...]
class State {
friend ostream& operator<<(ostream& lhs, State& rhs);
friend ostream& operator<<(ostream& lhs, const State& rhs);
private:
const string id; // Identifier
State(const string& id) : id(id) { }
[...]
};
inline ostream& operator<<(ostream& lhs, State& rhs) {
return lhs << rhs.id; }
inline ostream& operator<<(ostream& lhs, const State& rhs) {
return lhs << rhs.id; }
18.04.2013 MRT2 (c) 2013, UR Folie 13
Mit friend deklarierte
Methoden dürfen auf
private Daten
zugreifen
Keine Doppelung
der Methode!
Unterschiedliche
Signaturen
C++: friend
• Ein-/Ausgabeoperatoren und andere überladene Operatoren sollen häufig auf geschützte (private, protected) Attribute zugreifen, dürfen aber nicht Elementfunktionen sein.
• Der Freundmechanismus erlaubt festgelegten Funktionen oder Klassen Zugang zu den nichtöffentlichen Elementen
• Jede überladene Nichtelementfunktion, die Zugang zu den Elementen haben soll, muss als Freund deklariert sein. Die Signatur muss exakt übereinstimmen!
friend ostream& operator<<(ostream& lhs, State& rhs);
friend ostream& operator<<(ostream& lhs, const State&
rhs);
18.04.2013 MRT2 (c) 2013, UR Folie 14
Deklaration Transition
#include <iostream>
using namespace std;
#include "State.h"
class Transition {
public:
const State& start; // Ausgangszustand
const State& target; // Endzustand
Transition(const State& start, const State& target) :
start(start), target(target) { }
bool guard() const; // Wächterfunktion
void effect() const; // Übergangsverhalten
};
18.04.2013 MRT2 (c) 2013, UR Folie 15
Definition der Struktur des Automaten (Mockup, ohne spezifisches Verhalten)
// states
State ar("ar"), ll("ll"), lg("lg"), rl("rl"),
rg("rg");
// transitions
Transition t[] = {
Transition(ar, ll),
Transition(ll, lg),
Transition(lg, rl),
Transition(ar, rl),
Transition(rl, rg),
Transition(rg, ll)
};
18.04.2013 MRT2 (c) 2013, UR Folie 16
Ausführungslogik des Automaten in jedem Schritt – Beschreibung in Pseudo Code
// Prüfe ausgehende Transitionen
ÜBER ALLE ausgehenden Transitionen des aktuellen Zustands
WENN Transition durch Wächter freigegeben ist DANN
- Ausgangsverhalten des aktuellen Zustands
- Übergangsverhalten der Transition
- Eingangsverhalten des Zielzustand der Transition
- aktueller Zustand = Zielzustand der Transition
- RÜCKSPRUNG
ENDE WENN
ENDE ÜBER ALLE
// Wenn keine Transition geschaltet hat
- Beharrungsverhalten des aktuellen Zustands
18.04.2013 MRT2 (c) 2013, UR Folie 17
Deklaration Automaton
#include "State.h"
#include "Transition.h„
class Automaton {
private:
const State* pCurrentState;
const Transition* const pTT;
const int TTlength; int currentStateTicks;
public:
Automaton(State& startState, Transition* const pTT, const int
TTlength) : pCurrentState(&startState), pTT(pTT),
TTlength(TTlength), currentStateTicks(0) {
pCurrentState->enter(); }
void run();
int getCurrentStateTicks();
};
18.04.2013 MRT2 (c) 2013, UR Folie 18
const x*:
Veränderliche
Adresse eines
unveränderlichen
Objekts
const x* const:
Unveränderliche
Adresse eines
unveränderlichen
Objekts
->: Elementzugriffs-
operator für einen
Zeiger auf ein Objekt
analog zur Definition
in C
() ist der
Methodenaufruf-
operator mit
Argumentliste
C++: const (Teil 2)
• Konstante Zeiger auf Objekte - was ist konstant?
• Fall 1: Objektinstanz
– das Objekt dessen Adresse im Zeiger verwaltet wird darf nicht geändert werden
– const links von * bezieht sich auf Objekt (wie const double)
const State* pCurrentState;
State const * pCurrentState;
• Fall 2: Adresse
– Adresse soll nicht geändert werden
– const rechts von * bezieht sich auf Adresse
State* const pCurrentState;
• Fall 3: Adresse und Objektinstanz(en) unveränderlich
const Transition* const pTT;
18.04.2013 MRT2 (c) 2013, UR Folie 19
Die nächsten Schritte zum vollständig spezifizierten Automaten
• Spezialisierung
– Ableitung von spezialisierten Klassen aus den Basisklassen
– diese implementieren die konkreten Verhaltensspezifikationen von State
• enter(), hold(), exit()
– sowie Verhaltensspezifikationen und Wächter der Transition
• effect(), guard()
• C++: frühes und spätes Binden
– virtuelle Methoden (spätes Binden)
– abstrakte Klassen (können nicht versehentlich instanziiert werden)
18.04.2013 MRT2 (c) 2013, UR Folie 20
StateAlleRot ist_ein State (mit einem spezifizierten Eingangsverhalten)
// Spezialisierter Zustand
class StateAlleRot : public State {
public:
StateAlleRot(const string& id) : State(id) { }
void enter() const { cout << "state " << id
<< ": links=rot, rechts=rot" << endl; }
};
StateAlleRot("ar"); ...
• Leider funktioniert das in unserem Kontext so nicht zuverlässig!
18.04.2013 MRT2 (c) 2013, UR Folie 21
nach : wird eine
Liste von
Basisklassen
erwartet, die wir
spezialisieren
public: Zugriff auf
die Methoden der
Basisklasse wird
nicht modifiziert
Konstrukturen der
Basisklasse mit
Argumenten
müssen in der
Element-
initialisierungsliste
aufgerufen werden!!!
Die Methode enter() der
Basisklasse wird überschrieben
Frühes und spätes Binden
• Frühes (statisches) Binden
– Der Compiler bestimmt bereits zur Übersetzungszeit die konkret aufzurufende Methode
– Effizienter Code, Optimierung, ...
• Spätes (dynamisches) Binden
– Der Compiler erzeugt Code, der zur Laufzeit den Typ des Objekts und die konkret aufzurufende Methode bestimmt
• run-Methode des Automaten: pCurrentState->enter()
– State::enter() oder StateAlleRot::enter() ?
• Regeln
– Frühe Bindung: Typ des Zeigers State::enter()
– Späte Bindung: Typ des Objects StateAlleRot::enter()
18.04.2013 MRT2 (c) 2013, UR Folie 22
Spätes Binden „anordnen“: virtual
class State {
private:
const string id; // Identifier
public:
State(const string& id) : id(id) { }
virtual void enter() const;
virtual void exit() const;
virtual void stay() const;
inline const string& getID() const { return id; }
virtual ~State() { }
};
18.04.2013 MRT2 (c) 2013, UR Folie 23
virtuelle Methoden
werden spät
gebunden
Es ist fast immer
richtig auch einen
virtuellen Destruktor
zu definieren
Implementierung
class StateAlleRot : public State {
public:
StateAlleRot(const string& id) : State(id) { }
void enter() const { cout << "execute spezialisiertes
enter von " << getID() << ":links=rot, rechts=rot" <<
endl;}
};
class StateLinksLeeren : public State {
public:
StateLinksLeeren(const string& id) : State(id) { }
void enter() const { cout << "execute spezialisiertes
enter von " << getID() << ":rechts=rot" << endl;; }
};
18.04.2013 MRT2 (c) 2013, UR Folie 24
Nicht-Leere
Konstruktoren
müssen neu
angelegt werden
Alternative: Strategie-Muster
• Die Logik der Ausführung einer Methode einer Klasse wird an die Methode einer Strategieklasse ausgelagert
• Hier: Nutzung von Funktionszeigern
– Das Ausführen einer Methode werden bestimmte extern definierte Funktionen ausgeführt
• Vorteile:
– Kein Überladen von virtuellen Methoden notwendig
– Statisches Binden möglich
– Objekte von unterschiedlichen Typ können gleiche Strategien haben
• Nachteil:
– Externe Methoden haben keinen Zugriff auf die Klasse,
– Aufweichen der Kapselung über public bzw. freund konzepte nicht sinnvoll
18.04.2013 MRT2 (c) 2013, UR Folie 25
Strategie als Funktionszeiger
• Definition in State.h class State; // forward declaration
// Definition des Funktionszeigers Behavior
typedef void (*Behavior)(const State&, const string&);
// Deklaration der Defaultfunktion (nix tun)
void defaultBehavior(const State&, const string&);
• Nutzung in Klasse State private:
Behavior enterFunc;
public:
explicit State(const string& id,
Behavior enterFunc=defaultBehavior,
Behavior stayFunc= defaultBehavior,
Behavior exitFunc=defaultBehavior);
inline void enter() const { enterFunc(*this, "enter"); }
18.04.2013 MRT2 (c) 2013, UR Folie 26
Zum Komfort: Typ
für Funktionszeiger
rückgabe (*name)
(argumentliste)
Funktionsprototyp,
Implementierung an
anderer Stelle
„kleiner“ zirkulärer
Bezug, deshalb
forward declaration
notwendig
Defaultargumente –
wenn nicht
angegeben „nichts
tun“
Restrukturierung Automat
• Das Strategiemuster auf Transitionen angewandt
– doppelte Definition der defaultBehaviours notwendig neues
Design!
• Frage: Welche Elemente und Methoden haben State und Transition gemeinsam?
– string id, const string& getID()
• Lösungsansatz:
– Verlagern dieser Methoden in Basisklasse AutomatonElement, State und Transition werden abgeleitete Klassen
– Behaviours bekommen als Argument Referenz auf Basisklasse, statisches Binding sinnvoll, da nur Methoden der Basisklasse verwendet werden sollen
– AutomatonElement soll eine abstrakte Klasse werden, die nicht instanziiert werden kann
18.04.2013 MRT2 (c) 2013, UR Folie 27
Neues Klassendiagramm Automaton
18.04.2013 MRT2 (c) 2013, UR Folie 28
Automaton
Zustand Transition
Automaton-
Element
Strategie
1
1..*
1
1
2 1
AutomatonElement
class AutomatonElement; // forward
typedef void (*Behavior)(const AutomatonElement&, const string&);
void defaultBehavior(const AutomatonElement&, const string&);
typedef bool (*Guard)(const AutomatonElement&, const string&);
bool defaultGuard(const AutomatonElement&, const string&);
class AutomatonElement {
protected:
const string id; // identifier
public:
AutomatonElement(const string&);
virtual ~AutomatonElement() { };
inline const string& getID() const { return id; }
virtual const string& getType() const = 0;
};
18.04.2013 MRT2 (c) 2013, UR Folie 29
„kleiner“ zirkulärer
Bezug, deshalb
forward declaration
notwendig
prototyp = 0: pure
virtual Method
AutomatonElement
ist eine abstrakte
Klasse, die nicht
instanziiert werden
kann.
Eclipse: Library anlegen
1. Neues Projekt vom Typ Library anlegen
File / New / C++ Project
Project Name: Automaton
Project Type: Static Library / Empty Project
Toolchain: Linux GCC
2. Dateien aus Alt-Projekt kopieren und in neues Projekt einfügen
3. Build
Ergebnis: libAutomaton.a im Projektunterverzeichnis Debug und/oder Release
18.04.2013 MRT2 (c) 2013, UR Folie 30
Eclipse: Library verwenden
1. Referenz anlegen
Project / Properties Project References dort Automaton auswählen
2. Pfad zu Include-Datei für Compiler
Project / Properties C/C++ Build / Settings
Tool Settings: GCC C++ Compiler / Includes
Include paths (-l): Add, Workspace, Automaton auswählen
3. Library für Linker
Project / Properties C/C++ Build / Settings
Tool Settings: GCC C++ Linker / Libraries
Libraries (-l): Add, Automaton eingeben
Library search path (-L): Add, Workspace, Automaton/Debug auswählen
18.04.2013 MRT2 (c) 2013, UR Folie 31
Implementierung Ampelsteuerung
typedef AE AutomatonElement; // zu wenig Platz auf der Folie
const int ROT=0, GRUEN=1; // Signale für die Ampelsteuerung
int links = ROT, rechts= ROT; // Signal für Ampel != Zustand Automat!
ostream* aout = &cout; // Ausgabestrom für Visualisierung
void p(const AE& ae) { *aout << links << " " << rechts << " " <<
ae.getID() << endl; }
void behavior_LRRR(const AE& ae, const string& x) {
links=ROT;rechts=ROT;p(ae);}
// [...]
void behavior_RR(const AE& ae, const string& x) {
rechts=GRUEN;p(ae));}
// [...]
int main {
State ar("4", behavior_LRRR), ll("5", behaviorRR), ...;
Transition t[]={ Transition(ar, ll, guardLSL), ... };
18.04.2013 MRT2 (c) 2013, UR Folie 32
Ein Zeiger auf
Ausgabestrom kann
nochmal verändert
werden
Methodenname
ohne Aufrufoperator
(): Adresse der
Funktion
Visualisierung Ampelsteuerung
1. Trennen Debugausgabe, Zustandsausgabe
clog, cerr: Nutzung der Standardströme für Ausgabe von
Debug und Fehlermeldungen in der Library
ostream* aout = &cout; // Zeiger auf den Ausgabestrom für die
Daten, initialisiert mit cout
2. Visualisierung der Ausgabe auf stdout (cout): Programm aus shell starten, Ausgabe in Datei umlenken und gnuplot mrt$ cd MRT2/TrafficLight/Debug
mrt$ ./TrafficLight > q.q
mrt$ gnuplot
gnuplot> set border 0
gnuplot> set key auto col
gnuplot> plot 'q.q' using 1 with steps, 'q.q' u (\$2+2) w st,
'q.q' u 3 w st
18.04.2013 MRT2 (c) 2013, UR Folie 33
Ergebnis
18.04.2013 MRT2 (c) 2013, UR Folie 34
Linke Ampel
Rechte Ampel
Zustandsänderung
des Automaten
Automatisierung: Ausgabe in Datei, Anzeige mit gnuplot
#include <fstream> // für ofstream
#include <stdlib.h> // für system
ofstream fout("q.q");
aout = &fout;
for (int i = 0; i < 20; i++) a.run();
fout.close();
system("gnuplot -p -e \"" //
"set bor 0;"
"set key auto col;"
"set ytics ('grün' 0, 'rot' 1, 'grün' 2, 'rot' 3, 'ar' 4, 'll' 5,
'lg' 6, 'rl' 7, 'rg' 8);"
"plot 'q.q' u 1 w steps, 'q.q' u (\\$2+2) w steps, 'q.q' u 3 w
steps\"");
18.04.2013 MRT2 (c) 2013, UR Folie 35
Ausgabestrom auf
Datei mit Namen q.q
öffnen
ofstream ist_ein
ostream, genauso
wie cout: Gleiche
Schnittstellen für
Ausgabe auf
Konsole und Datei!
Vor Nutzung
schliessen
Automatisierung: Ausgabe in Datei, Anzeige mit gnuplot
#include <fstream> // für ofstream
#include <stdlib.h> // für system
ofstream fout("q.q");
aout = &fout;
for (int i = 0; i < 20; i++) a.run();
fout.close();
system("gnuplot -p -e \"" //
"set border 0;"
"set key autotitle column;"
"set ytics ('grün' 0, 'rot' 1, 'grün' 2, 'rot' 3, 'ar' 4, 'll' 5,
'lg' 6, 'rl' 7, 'rg' 8);"
"plot 'q.q' u 1 w steps, 'q.q' u (\\$2+2) w steps, 'q.q' u 3 w
steps\"");
18.04.2013 MRT2 (c) 2013, UR Folie 36
Kein Rahmen
Beschriftung der
Kurven aus erster
Zeile der Datendatei
Umbenennung der
Ticks der y-Achse
Formel: Wert in 2.ter
Spalte ($2) plus 2
Taschenrechner: Vorzeichenbehaftete Ganzzahlen, kein Vorrang der Operanden
• Start in 0
• 0,1,2: Linker Operand – 0<->1 Negative Vorzeichen
wechseln Vorzeichen
– 2: Zahlenfolge aggregieren
• 2->3: Operator – Operator merken, Wechsel zum
Einlesen des rechten Operanden
• 3,4,5: Rechter Operand – wie Linker Operand
• 3->5: Operator – den zuletzt gemerkten Operator ausführen, Ergebnis in linkem Operand
speichern, rechten Operand auf 0 setzen, neuen Operator merken
• 5->0: Operator – wie 3->5, nur diesmal alles zurücksetzen
18.04.2013 MRT2 (c) 2013, UR Folie 37
Test: --0002*30+-+1234= -1174 ?
18.04.2013 MRT2 (c) 2013, UR Folie 38
