Nachdem ich gerade die Steuerlogik eines RGB-LED-Dimmer damit fertiggestellt habe: Wielleicht interessiert sich hier jemand für einen kleinen (60 Zeilen inkl. Kommentaren in einer Headerdatei), endlichen Automaten. Aufgrund der Größe und Einfachheit eignet er sich gut für die Verwendung in einem Mikrocontroller-Projekt. Der Code ist recht übersichtlich geworden und Compiliert einwandfrei in AVR-GCC. Hier die genaue Beschreibung: http://www.flashsystems.de/articles/1789 Herunterladen kann man die Headerdatei hier: http://www.flashsystems.de/down/files/tiny_fsm.h Viel Spaß damit.
Wozu soll das gut sein? Das ist eine Unsitte mit #defines die Programmiersprache zu vergewaltigen. Die State Machine kann man genauso gut normal in C schreiben und der Code bleibt viel besser lesbar.
Hallo "Schwitzender Fettsack", es ist wohl Ansichtssache ob ein Wald aus if- oder switch-Statements oder dubiose Tabellen übersichtlicher ist als sprechende Makros. Wem's nicht gefällt, der muss es ja nicht verwenden. Aus meiner Sicht hat es nichts mit vergewaltigen zu tun, die Features einer Programmiersprache (in diesem Fall Makros) auch zu verwenden. Es kann aber sein, dass ich hier schon etwas zu ATL- und MFC-geschädigt bin. Diese Bibliotheken machen das nämlich auch (aus meiner Sicht) sehr erfolgreich :)
Daniel G. schrieb: > es ist wohl Ansichtssache ob ein Wald aus if- oder switch-Statements > oder dubiose Tabellen übersichtlicher ist als sprechende Makros. Man kann State Machines viel eleganter Programmieren als mit if oder switch/case. Stichwort Callback. Daniel G. schrieb: > Wem's nicht gefällt, der muss es ja nicht verwenden. Das sag mal jemandem der dann solchen Code pflegen muss.
Hallo "Schwitzender Fettsack", über das Wohl und Wehe von Präprozessormakros sind schon zu viele Forenseiten vollgeschrieben worden ohne eine Einigung zu erzielen... Was ich viel interessanter Finde, ist der erwähnte Callback-Ansatz. Würde es dir etwas ausmachen, hier ein kleines Beispiel zu posten? Evtl. einfach die gleiche Funktion wie das von mir verwendete Beispiel. Dann kann jemand, der auf diesen Artikel stößt, selbst entscheiden welche Variante ihm besser gefällt oder welche für seinen Einsatzzweck besser geeignet ist.
Daniel G. schrieb: > über das Wohl und Wehe von Präprozessormakros sind schon zu viele > Forenseiten vollgeschrieben worden ohne eine Einigung zu erzielen... Das ist falsch, die Einigung ist nur noch nicht bei allen angekommen: Sobald es eine sinnvolle Alternative gibt (also in dem meisten Fällen), sind Makros nur von Übel - insbesondere für funktionsähnliche Makros.
Vielleicht hat der schwitzende Fettsack Makros mit Makronen verwechselt... ;-) MfG Paul
Ok, mag sein, dass der Makro-Ansatz nichts taugt. Wie oben schon geschrieben fände ich es dann interessant, eine bessere Lösung zu sehen. Dann lerne nicht nur ich etwas dazu sondern auch andere, die diesen Thread lesen... Schließlich ist nichts so schlecht, dass es nicht noch als schlechtes Beispiel dienen könnte ;) Die Rahmenbedingungen sind: - Implementiert das beschriebene Beispiel oder was ähnliches - C (kein C++) - keine dynamische Speicherallokation - übersichtlicher/wartungsfreundlicher als der Makro-Ansatz
Bin zwar nicht "Schwitzender Fettsack", aber sowas hab ich schon mal gemacht (LED-Uhr mit 1-Button Interface als State Machine programmiert). Folgenden Code hab ich benutzt um das Konzept zu testen. Sollte auf fast jedem BS als Konsolenprogramm kompilieren:
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 | |
4 | void * state1(void); |
5 | void * state2(void); |
6 | void * quit(void); |
7 | |
8 | void * (*currentstate)(void) = &state1; |
9 | |
10 | void * state1(void) |
11 | {
|
12 | static int a = 1; |
13 | |
14 | printf("we are in state1. a is %d.\n",a); |
15 | |
16 | if (++a<5) |
17 | return &state1; |
18 | else
|
19 | return &state2; |
20 | }
|
21 | |
22 | void * state2(void) |
23 | {
|
24 | printf("now we're in state2. time to quit.\n"); |
25 | return &quit; |
26 | }
|
27 | |
28 | void * quit(void) |
29 | {
|
30 | printf("exiting\n"); |
31 | exit(EXIT_SUCCESS); |
32 | }
|
33 | |
34 | int main(void) |
35 | {
|
36 | for(;;) |
37 | currentstate = currentstate(); |
38 | }
|
und hier die Ausgabe:
1 | we are in state1. a is 1. |
2 | we are in state1. a is 2. |
3 | we are in state1. a is 3. |
4 | we are in state1. a is 4. |
5 | now we're in state2. time to quit. |
6 | exiting |
@glagnar: Uiuiui.... warum Stackplatz vergeuden, obwohl ein DFA doch per Definition gar keinen Stack benötigt?? Warum diese ungewöhnliche, umständliche Implementierungsweise? Eine simple Schleife hätte doch auch gereicht...?!?
Schwitzender Fettsack schrieb: > Wozu soll das gut sein? Das ist eine Unsitte mit #defines die > Programmiersprache zu vergewaltigen. Das ist keine Vergewaltigung der Programmiersprache, sondern eine DSL, genauer gesagt eine embedded DSL: http://de.wikipedia.org/wiki/Dom%C3%A4nenspezifische_Sprache Embedded DSLs sind eine durchaus gängige Methode, um den Abstraktions- grad der Wirtssprache (hier C) für bestimmte Anwendungsbereiche (hier FSMs) zu erhöhen. Ok, C bietet nur wenige Sprachkonstrukte an, die zur Erstellung von DSLs geeignet sind. Eins der wichtigsten ist das Makrosystem (Präprozessor), das allerdings nicht sehr viel kann. In C++ geht da schon mehr, vor allem wegen des sehr mächtigen Template- Systems und der Möglichkeit der Operatorüberladung. Noch mehr in dieser Richtung ist in Python, Ruby und Konsorten möglich. Der Klassiker unter den "DSL-fähigen" Programmiersprachen ist aber Lisp. Lisp hat ein Makrosystem, das mächtiger ist als das aller anderen mir bekannten Programmiersprachen: Es ist so mächtig wie die Sprache selbst. Eine Makroexpansion macht dort nicht — wie in C — nur einfache Text- ersetzungen, sondern praktisch beliebig definierbare (programmierbare) Transformationen von Programmcode. In Lisp ist es fast normal, dass ein Entwickler zu Beginn eines größeren Softwareprojekts erst einmal eine geeignete DSL entwirft und implementiert, um hinterher die eigentliche Anwendung ganz leicht und in übersichtlicher Weise herunterprogrammie- ren zu können. Wie bei allen Dingen sollte man aber klein anfangen, und da ist doch die FSM-DSL von Daniel ein schönes Beispiel :) > Die State Machine kann man genauso gut normal in C schreiben Klar. > und der Code bleibt viel besser lesbar. Hmm, findest du? Ich habe noch kein direkt programmiertes gutes Beispiel gesehen. Es ist generell nicht leicht, die Funktion einer in Textform (also nichtgrafisch) dargestellten FSM zu verstehen. Das gilt bis zu einem gewissen Grad auch für DSLs, nur ist dort der Code meistens kompakter, so dass man einen viel größeren Ausschnitt mit einem Blick erfassen kann, was die Sache sehr viel übersichtlicher macht. Besser für das Verständnis ist es natürlich, wenn man aus der textuellen Beschreibung eine grafische Darstellung generieren kann. Aber auch hier haben DSLs Vorteile: Ein Parser für Daniels FSM-DSL ist recht schnell geschrieben, während es nahezu unmöglich ist, aus einem Stück normalem C-Code, der eine FSM darstellen soll, die FSM-Struktur zu extrahieren. @Daniel: Lass dich von denen nicht entmutigen, du bist auf dem richtigen Weg. In welchen Anwendungen sich deine Methode bewährt und in welchen nicht so sehr, das wirst du von Fall zu Fall selber herausfinden.
Informatikstudent schrieb: > @glagnar: Uiuiui.... warum Stackplatz vergeuden, obwohl ein DFA doch per > Definition gar keinen Stack benötigt?? Warum diese ungewöhnliche, > umständliche Implementierungsweise? Eine simple Schleife hätte doch auch > gereicht...?!? Das muss wohl ironisch gemeint sein. Mein Code hat ein Stacklevel von genau 1. Es gibt keine tieferen Unteraufrufe und auch kein Reentry. Simple Schleife? Ja, man könnte natürlich komplett auf Funktionen verzichten ... Zumindest reichts für eine LED-Uhr mit DCF77 Empfang, mit 7 Helligkeitsstufen und einem komfortablen Bedieninterface mit nur einem Button auf einem ATTiny2313 mit 128 Byte RAM ... Der Vorteil bei meinem Code ist halt, wie ich finde, dass er modular ist und dass die Information für den Programmflow immer schön lokal im passenden Kontext ist. Wenn man Features hinzufügen möchte, muss man nur den vohergehnden und den nachfolgenden State ändern. Ich nenne es Tortellinicode :D
Marko B. schrieb: > Der Vorteil bei meinem Code ist halt, wie ich finde, dass er modular ist > und dass die Information für den Programmflow immer schön lokal im > passenden Kontext ist. Anstelle der Rückgabe der Funktionszeiger für den nächsten Schritt könntest du die jeweiligen Funktionen auch direkt aufrufen:
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 | |
4 | void state1(void); |
5 | void state2(void); |
6 | void quit(void); |
7 | |
8 | void state1(void) |
9 | {
|
10 | static int a = 1; |
11 | |
12 | printf("we are in state1. a is %d.\n",a); |
13 | |
14 | if (++a<5) |
15 | state1(); |
16 | else
|
17 | state2(); |
18 | }
|
19 | |
20 | void state2(void) |
21 | {
|
22 | printf("now we're in state2. time to quit.\n"); |
23 | quit(); |
24 | }
|
25 | |
26 | void quit(void) |
27 | {
|
28 | printf("exiting\n"); |
29 | }
|
30 | |
31 | int main(void) |
32 | {
|
33 | state1(); |
34 | }
|
Da jeder anständige C-Compiler heutzutage Tail-Call-Optimization macht, führt dies zu keinem zusätzlichen Stack-Verbrauch.
Yalu X. schrieb: > Anstelle der Rückgabe der Funktionszeiger für den nächsten Schritt > könntest du die jeweiligen Funktionen auch direkt aufrufen: Hmm. Ich denke es ist kein guter Stil, sich auf eine Optimierung zu verlassen damit ein Programm funktioniert. Spätestens wenn man zum Debuggen die Optimierung ausschaltet ist es vorbei damit. Besonders übel wäre es auch, wenn in irgendeinem Spezialfall die Optimierung nicht angewandt wird und das Programm crasht. Das wäre ein schwer zu lokalisierender Bug. Da schreibe ich lieber die "korrekte" Version mit Funktionspointer.
Marko B. schrieb: >> Anstelle der Rückgabe der Funktionszeiger für den nächsten Schritt >> könntest du die jeweiligen Funktionen auch direkt aufrufen: > > Hmm. Ich denke es ist kein guter Stil, sich auf eine Optimierung zu > verlassen damit ein Programm funktioniert. Hast recht, das sollte man nicht machen :)
Wenn dein anderer Code auch so schlecht ist, wie die Implementation der
FSM,
übe noch weiter. An sich nicht so schlecht, nur die Implementierung
lässt
zu wünschen übrig.
BEGIN_STATE_MACHINE(main, Standby)
STATE(main, Running)
EVENT(main, Done, Standby);
EVENT(main, EnterSettings, Settings);
END_STATE()
Bei einer besseren FSM möchte man folgendes machen, dein Code lässt dies
aber nicht zu.
BEGIN_STATE_MACHINE(main, Standby)
EVENT(main, Timeout, Standby);
EVENT(main, External, Standby);
STATE(main, Running)
EVENT(main, Done, Standby);
EVENT(main, EnterSettings, Settings);
END_STATE()
Weiters sollte die State-Machine eher so lauten:
BEGIN_STATE_MACHINE(main, Reset)
STATE(main, Reset)
do_init();
STATE_NEXT(main, Standby);
END_STATE()
Auch deine Namen sind etwas unvorsichtig.
#define HANDLERFUNC(_MACHINENAME, _EVENTNAME) bool
_MACHINENAME##_##_EVENTNAME()
Was ist, wenn eine state machine den namen "ret" hat und der state
"urn" für Unrecognized Reference Number als Beispiel, dann machst du
daraus return, klingelt da was. Ist natürlich kein gutes Beispiel, es
gibt andere wie gettime, ... .
auch das wiederholte verwenden vom FSM Name ist blöd.
BEGIN_STATE_MACHINE(main, Standby)
EVENT(main, Timeout, Standby);
EVENT(main, External, Standby);
STATE(main, Running)
EVENT(main, Done, Standby);
EVENT(main, EnterSettings, Settings);
END_STATE()
könnte genausogut
BEGIN_STATE_MACHINE(main, Standby)
EVENT(Timeout, Standby);
EVENT(External, Standby);
STATE(Running)
EVENT(Done, Standby);
EVENT(EnterSettings, Settings);
END_STATE()
sein, die Funktion
#define BEGIN_STATE_MACHINE(_MACHINENAME, _STARTSTATE) \
SMFunc_##_MACHINENAME currentStateFunc = _MACHINENAME##_##_STARTSTATE;
\
while (true) \
{ if (false) {}
könnte einfach so definiert sein:
#define BEGIN_STATE_MACHINE(_MACHINENAME, _STARTSTATE) \
while (true) \
{ static FSM_STATE_TYPE state = _MACHINENAME##_##_STARTSTATE; if
(false) {}
und anstelle von
#define EVENT(_MACHINENAME, _EVENTNAME, _STATEFUNC) \
case _EVENTNAME: \
currentStateFunc = _MACHINENAME##_##_STATEFUNC; \
break;
machst du
#define EVENT(_EVENTNAME, _STATEFUNC) \
case _EVENTNAME: \
state = FSM_##_STATEFUNC; \
break;
wobei die Switch anweisungen auch problematisch sind, ...
Chris
Chris schrieb: > Wenn dein anderer Code auch so schlecht ist, wie die Implementation der > FSM, > übe noch weiter. Das musste sein, gell. Ich kommentiere deine Vorschläge doch auch sachlich... [...] > > BEGIN_STATE_MACHINE(main, Standby) > EVENT(main, Timeout, Standby); > EVENT(main, External, Standby); > STATE(main, Running) > EVENT(main, Done, Standby); > EVENT(main, EnterSettings, Settings); > END_STATE() > Sehe ich nicht so: Für jeden State sollten aus meiner Sicht die Events und der daraus resultierende Folgestatus klar definiert sein. Globale Events sind nicht vorgesehen. Ob diese in einer FSM überhaupt sinnvoll sind, kann ich ad hoc nicht beurteilen. Evtl. hat hier jemand eine Meinung dazu... Was, wenn ein neuer State dazu kommt, welcher nicht auf den Timeout reagieren will. Dann muss der Timeout doch manuell bei allen States eingetragen werden. > > Weiters sollte die State-Machine eher so lauten: > > BEGIN_STATE_MACHINE(main, Reset) > STATE(main, Reset) > do_init(); > STATE_NEXT(main, Standby); > END_STATE() > Warum? Wie wird zwischen zwei Folgezuständen ausgewählt? So implementiert das nur eine sequenzielle Fortschaltung. > Auch deine Namen sind etwas unvorsichtig. > #define HANDLERFUNC(_MACHINENAME, _EVENTNAME) bool > _MACHINENAME##_##_EVENTNAME() > > Was ist, wenn eine state machine den namen "ret" hat und der state > "urn" für Unrecognized Reference Number als Beispiel, dann machst du > daraus return, klingelt da was. Ist natürlich kein gutes Beispiel, es > gibt andere wie gettime, ... . So wie ich das sehe hätte ich bei deinem Beispiel einen Handler mit dem Namen ret_urn. Da es in C keine reservierten Schlüsselwörter mit einem _ innerhalb des Schlüsselwortes gibt, sehe ich da kein Problem. Natürlich kann man immer eine Namenskollision konstruieren, das ist aber bei einem selbst gewählten Prefix (dem FSM-Namen) leichter zu vermeiden. Natürlich könnte man auch einen festen Prefix (wie weiter unten von dir vorgeschlagen) verwenden. Dann können aber keine zwei FSM den gleichen State-Namen verwenden. > auch das wiederholte verwenden vom FSM Name ist blöd. Stimmt, hier bin ich für eine elegantere Lösung offen. Wenn man aber einen statischen Prefix vermeiden will, fällt mir keine andere Lösung ein. [...] > #define BEGIN_STATE_MACHINE(_MACHINENAME, _STARTSTATE) \ > while (true) \ > { static FSM_STATE_TYPE state = _MACHINENAME##_##_STARTSTATE; if > (false) {} Werden statische Variablen nicht nur einmal initialisiert? D.h. beim nächsten Aufruf der FSM (z.B. in einer Funktion) läuft diese nicht mit dem Start-State los sondern mit dem State, welchen sie zuletzt hatte? Das wäre - finde ich - "überraschend". Die Idee einen eigenen Gültigkeitsbereich für die State-Variable zu betreten finde ich nicht schlecht. Die Frage ist, welchen Vorteil man davon noch hat (außer etwas Stack zu sparen, wenn mehere FSM in einer Funktion sind). > wobei die Switch anweisungen auch problematisch sind, ... So so...
Beim Namen hast du recht, mein Fehler. Daniel G. schrieb: > Werden statische Variablen nicht nur einmal initialisiert? D.h. beim Ja > nächsten Aufruf der FSM (z.B. in einer Funktion) läuft diese nicht mit > dem Start-State los sondern mit dem State, welchen sie zuletzt hatte? > Das wäre - finde ich - "überraschend". Das ist jetzt zunächst mal eine Grundsatzfrage. Ich ziehe es vor, wenn die State-Machine nicht blockiert. Da kann man dann auch mehrere State- Machines parallel haben und abarbeiten. Deshalb auch mein Ansatz mit der static Variable. Wenn die State-Machine aber wie bei dir blockieren sein soll, dann einfach das static weglassen und es ist dann so wie du es derzeit hast. Ja, das mit dem Switch ist bei elaborierteren state machines problematisch, da ist ein if Konstrukt besser, in dem Sinne, daß wenn eine Variable inizieren will, oder ändern, oder dergleichen das mit einem if funktioniert, mit einem switch nicht. Dasselbe ist mit dem IF construct, if (false) {} #define STATE(_MACHINENAME, _STATENAME) \ else if (currentStateFunc == _MACHINENAME##_##_STATENAME) \ besser ist, weil dann ein Semicolon am ende sein kann. if (false) { #define STATE(_MACHINENAME, _STATENAME) \ } else if (currentStateFunc == _MACHINENAME##_##_STATENAME) \
Chris schrieb: > > Das ist jetzt zunächst mal eine Grundsatzfrage. Ich ziehe es vor, wenn > die State-Machine nicht blockiert. Da kann man dann auch mehrere State- > Machines parallel haben und abarbeiten. Deshalb auch mein Ansatz mit > der static Variable. Wenn die State-Machine aber wie bei dir blockieren > sein soll, dann einfach das static weglassen und es ist dann so wie du > es derzeit hast. > Die Idee die State-Machine immer wieder zu verlassen ist interessant. Für diese kleine FSM war es nicht nötig. Wenn man das möchte, kann man das static rein und die while-Schleife komplett raus machen. Dann hat man eine FSM die nach jedem Schritt zum Hauptprogramm zurückkehrt. Evtl. kann man dann einen State als eine Art yield verwenden... > > Ja, das mit dem Switch ist bei elaborierteren state machines > problematisch, > da ist ein if Konstrukt besser, in dem Sinne, daß wenn eine Variable > inizieren will, oder ändern, oder dergleichen das mit einem if > funktioniert, [...] In diesem Fall ist ein if/elseif-Konstrukt wirklich vorzuziehen. Ich habe mich für das switch entschieden da der Compiler hier (wenige, sequenziell aufeinander folgende Werte durch das Enum) eine Sprungtabelle verwendet und damit die Performance besser und das Binary kleiner ist. Wenn man die FSM weiter ausbaut, könnte sich dass aber in der Tat als weniger Flexibel erweisen. Wer mehr Flexibilität möchte, kann das entsprechende Makro wie von dir geschildert einfach anpassen.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.