% 2012-04-08 % % für die Vorbereitung des Kurses am Linuxhotel habe ich die "finite state % machines" von Julian Noble gelesen und nachprogrammiert. Daraus kann man % ja ganz locker mal ein Artikelchen basteln. Schwerpunkt Portierung, nicht % die state machine selbst. \documentclass[11pt,a4paper]{article} % save as utf-8-emacs-unix % 2006-07-07 EW Adventures-1.tex % 2006-07-22 EW Adventures-2.tex % 2006-08-14 EW Adventures-2a.tex % 2007-01-10 EW Adventures-3.tex % 2007-01-13 EW Adventures-4.tex % 2008-11-14 EW Adventures-5.tex % 2011-01-07 EW Adventures-6.tex: rs485+mpc % 2011-02-14 EW Adventures-7.tex: list % 2011-04-30 EW Adventures-8.tex: vocabulary % Adventures-9.tex: rfm12 Grundlagen % 2011-12-04 EW Adventures-10.tex: rfm12, ook + technoline Sensoren % 2012-04-15 EW Adventures-11.tex: finite state machine % % language support \usepackage[german]{babel} %\usepackage{german} \usepackage[utf8]{inputenc} % can use Umlauts now ü instead of "u %\usepackage{lmodern} % better fonts %\usepackage{pslatex} % use native PostScript fonts %\usepackage{cm-super} \usepackage{url} % \url{} \path{} with correct "hyphenation" \usepackage{paralist} % env compactenum, compactitem % \voffset-10mm % \pagestyle{empty} % \pagestyle{plain} % \pagestyle{headings} % \renewcommand{\baselinestretch}{1.08} %\usepackage{xspace} \parindent=0pt %\newcommand{\amforth}{\texttt{amforth}} %\newcommand{\zB}{z.\,B.\ } \begin{document} \title{Adventures 11: Finite State Machine} %\ifx\shorttitle\undefined\else %\shorttitle{xx} %\fi \author{Erich Wälde} \maketitle %\begin{multicols}{2} % -------------------------------------------------------------------- %\section{Intro} %\label{sec:intro} \begin{abstract}\itshape In einem nicht--forthigen Zusammenhang sind mir neulich \emph{endliche Automaten} (finite state machines) über den Weg gelaufen. Da erinnerte ich mich daran, daß ich noch eine Dokument hatte, welches ich irgendwann einmal lesen wollte: \emph{Julian V.\,Noble --- Finite State Machines in Forth} [\ref{ref:noble:fsm}]. Das traf sich bestens, denn so hatte ich einen Grund, den darin vorgestellten Code auf amforth [\ref{amforth}] zu portieren. \end{abstract} \begin{multicols}{2} % -------------------------------------------------------------------- \section{Eingabefunktion für Dezimalzahlen} Eine Dezimalzahl soll folgenden Regeln in der Darstellung genügen: \begin{compactenum} \item Nur die Zeichen \verb+0123456789.-+ sind erlaubt \item Das erste Zeichen darf eine Ziffer, das negative Vorzeichen \verb+-+ sowie der Dezimalpunkt \verb+.+ sein \item Nach dem ersten Zeichen ist kein Vorzeichen \verb+-+ mehr erlaubt \item Nach dem ersten Dezimalpunkt \verb+.+ sind keine weiteren Dezimalpunkte erlaubt \end{compactenum} Also sind beispielsweise folgende Zahlen gültig: \texttt{0.123 .123 1.23 -1.23 123 -.123}. Die Programmieraufgabe besteht nun darin, die Eingabe solcher Dezimalzahlen zu ermöglichen. Allerdings soll z.\,B.\ nach dem ersten Dezimalpunkt kein weiterer mehr angenommen werden. Die Eingaberoutine ist zu jeder Zeit über die weiterhin erlaubten Zeichen im Bild. Das Drücken der Eingabetaste beendet die Routine. Selbstverständlich kann dieses Problem auch prozedural gelöst werden (siehe Anhang Listings). Allerdings sieht der Kern der Angelegenheit, das Wort \verb+legal?+ doch einigermaßen unübersichtlich aus. \begin{small} \begin{verbatim} include tempbuffer.fs \ reset append show variable prev.minus? variable prev.dpoint? : digit? [char] 0 [char] 9 within ; : dpoint? [char] . = ; : minus? [char] - = ; : first.minus? minus? prev.minus? @ not and ; : first.dpoint? dpoint? prev.dpoint? @ not and ; : false true not ; : legal? ( c -- f ) dup digit? if \ no '-' allowed afther first digit drop true dup p.minus? ! else dup first.minus? if drop true dup p.minus? ! else first.dpoint? if true dup p.dpoint? ! else false then then then ; \end{verbatim} \end{small} Es handelt sich um eine geschachtelte \verb+if+ --- \verb+else+ --- \verb+then+ Konstruktion, welche die komplette Logik enthält. Dabei sollte man beachten, daß es sich hier um ein ziemlich einfaches Problem handelt. Bei einem komplexeren Problem wird das schnell sehr unübersichtlich. Das Wort \verb+legal?+ wird in der Eingabeschleife für jedes Zeichen aufgerufen. \begin{small} \begin{verbatim} : getafix reset false p.minus? ! false p.dpoint? ! begin key dup emit dup $0D <> \ exit on CR while dup legal? if append else drop then repeat drop \ CR cr show cr ; \end{verbatim} \end{small} Statt der direkten Ausgabe (\verb+emit+) habe ich einen Puffer angelegt, in den die gültigen Zeichen hineinkopiert werden (\verb+append+). Nach der Eingabe wird die akzeptierte Zeichenkette ausgegeben. So sieht man sowohl die Eingabe, als auch was davon übrig geblieben ist. \begin{small} \begin{verbatim} > getafix ---234900x9er.2-304 -2349009.2304 ok \end{verbatim} \end{small} % -------------------------------------------------------------------- \section{Endlicher Automat} Diese Art Probleme können sehr schön mit einem endlichen Automaten (\textit{finite state machine}) gelöst werden. Die Zustände des Automaten können als Gedächtnis benutzt werden: Im Zustand \verb+0+ wurde noch kein Zeichen verarbeitet. Ist das erste Zeichen gültig, dann wird dadurch der Übergang in den Zustände \verb+1+ (keine Minuszeichen erlaubt) oder \verb+2+ (zusätzlich keine Dezimalpunkte erlaubt) ausgelöst. In der nachfolgenden Tabelle steht ein \verb+X+ in den Feldern, in denen das eingegeben Zeichen nicht erlaubt ist und folglich verworfen wird. Ein \verb+E+ steht für die Ausgabe des Zeichen --- ursprünglich ein \verb+emit+, in diesen Beispielen durch ein \verb+append+ ersetzt. Hinter den Aktionen \verb+X+ und \verb+E+ sind die gewünschten nachfolgenden Zustände angegeben. Die Eingabe eines Dezimalpunkts (Spalte \verb+DP?+) führt immer zu einem Übergang in den Zustand \verb+2+. \begin{table} \begin{small} \begin{verbatim} \ Input: other? digit? minus? dpoint? \ State| Does Trans Does Trans Does Trans Does Trans \ 0 | X -> 0 E -> 1 E -> 1 E -> 2 \ 1 | X -> 1 E -> 1 X -> 1 E -> 2 \ 2 | X -> 2 E -> 2 X -> 2 X -> 2 \ \ E == echo or append \ X == drop \end{verbatim} \end{small} \caption{Zustände und Übergänge des endlichen Automaten} \end{table} Der Zustand \verb+0+ ist der initiale Zustand. Wird eine Ziffer oder ein (negatives) Vorzeichen eingegeben, dann wechselt der Automat in den Zustand \verb+1+. Der Zustand \verb+1+ sagt sinngemäß: \textit{Es wurde schon ein Zeichen eingegeben, ein weiteres Vorzeichen ist jetzt nicht mehr erlaubt}. Wird ein Dezimalpunkt eingegeben, dann wechselt der Automat auf jeden Fall in den Zustand \verb+2+. Dieser heißt sinngemäß: \textit{Es ist kein weiterer Dezimalpunkt erlaubt}. Man kann in der Tabelle sehen, daß in allen Zuständen ein ungültiges Zeichen schlicht verworfen wird (Spalte \verb+other?+ enthält nur \verb+X+), der Zustand ändert sich nicht. Ebenso kann man sehen, daß ein Vorzeichen nur in Zustand \verb+0+ erlaubt ist, also als erstes Zeichen (Spalte \verb+minus?+). Der Zustand \verb+0+ wird immer nach dem ersten gültigen Zeichen verlassen. Im folgenden benutze ich die Abkürzung FSM, um den endlichen Automaten zu benennen. % -------------------------------------------------------------------- \section{Version 1} Wir brauchen für die erste Version der FSM das Wort \verb+case+, welches seinerseits \verb+postpone+ verlangt. Die Tests der Zeichen sind gleich geblieben. \begin{small} \begin{verbatim} include lib/ans94/postpone.frt include case.fs include tempbuffer.fs variable mystate : digit? [char] 0 [char] 9 within ; : dpoint? [char] . = ; : minus? [char] - = ; \end{verbatim} \end{small} Das Wissen, welches zuvor in dem Wort \verb+legal?+ versammelt war, wird in drei verschiedene Worte aufgeteilt. Jeder Zustand bekommt ein eigenes Wort, welches sämtliche Aktionen und Übergänge dieses einen Zustands kennt. \begin{small} \begin{verbatim} : (0) ( c -- ) dup digit? over minus? or if append 1 mystate ! else dup dpoint? if append 2 mystate ! else drop then then ; : (1) ( c -- ) dup digit? if append ( 1 mystate ! ) else dup minus? if drop ( 1 mystate ! ) else dup dpoint? if append 2 mystate ! else drop then then then ; : (2) ( c -- ) dup digit? if append ( 2 mystate ! ) else drop then ; \end{verbatim} \end{small} Superübersichtlich ist das vielleicht auch noch nicht, aber mit etwas Einrücken kann man zumindest die Aktionen und die gewünschten Übergänge sehen. Der Vergleich mit der Tabelle fällt jetzt leichter. Diese Worte werden in einen \verb+case+--Block gesteckt, welcher dann die FSM bildet. \begin{small} \begin{verbatim} : ( char state -- ) case 0 of (0) endof 1 of (1) endof 2 of (2) endof default: endcase ; \end{verbatim} \end{small} In der Schleife von \verb+getafix+ wird für jedes eingegebene Zeichen der momentane Zustand auf den Stapel gelegt und dann die FSM aufgerufen. \begin{small} \begin{verbatim} : getafix reset 0 mystate ! begin key dup emit dup $0D <> \ exit on CR while mystate @ repeat drop \ CR cr show cr ; \end{verbatim} \end{small} J.\,Noble nennt diese Version der FSM \textit{brute force fsm}. Zwar funktioniert das Programm, aber schön ist diese Lösung noch nicht. \begin{small} \begin{verbatim} > getafix 0234.234 0234.234 ok > getafix -324.234 -324.234 ok > getafix 0-.234.234-234 0.234234234 ok \end{verbatim} \end{small} % \begin{small} % \begin{verbatim} % x % \end{verbatim} % \end{small} % -------------------------------------------------------------------- \section{Version 2} Der oben gezeigte \verb+case+--Block enthält eine Zeile für jeden Zustand der FSM. Für die Übereinstimmung mit der Tabelle müssen die Worte \verb+(0)+ etc.\ einzeln inspiziert werden. Eine Definition, welche die Tabelle in lesbarer Form im Quelltext enthält, wäre einfacher zu verstehen. Um das zu realisieren, schreiben wir zunächst eine Funktion, die zu einem beliebigen Zeichen die Nummer der zugehörige Tabellenspalte (\verb+other?+ \verb+digit?+ \verb+minus?+ \verb+dpoint?+ ) berechnet. Die genaue Reihenfolge der Spalten wird in diesem Wort festgelegt. \begin{small} \begin{verbatim} : cat->col# ( n -- n' ) \ other? 0 dup digit? 1 and over minus? 2 and + swap dpoint? 3 and + ; \end{verbatim} \end{small} \begin{small} \begin{verbatim} > char a cat->col# . 0 ok > char 3 cat->col# . 1 ok > char - cat->col# . 2 ok > char . cat->col# . 3 ok \end{verbatim} \end{small} Die neue FSM wird durch ein Definitions--Wort generiert. Zuerst wird ein Eintrag im Wörterbuch für die zu generierende FSM angelegt. Die Anzahl der Spalten in der Tabelle wird an dieser Stelle vom Programmierer übergeben und als Parameter gespeichert. Dann wird der Übersetzung--Modus eingeschaltet --- damit wird der Rest der Definition bis zum schließenden Semikolon schlicht kompiliert und dem angefangenen Parameterfeld hinzugefügt. In jedem Feld der Tabelle befindet sich dann ein \verb+xt+, eine Einsprungadresse für das Wort, welches die für diese bestimmte Kombination aus Zeichen und Zustand vorgesehene Arbeit erledigt und ggf.\ einen Zustandswechsel herbeiführt. \begin{small} \begin{verbatim} : fsm: ( width -- ) create , \ store width in flash ] \ switch compiler on to \ consume state table does> ( char col# -- ) \ -- char col# pfa swap over \ -- char pfa col# pfa @i \ -- char pfa C width mystate @ * \ -- char pfa C W*state + \ -- char pfa C+W*state 1+ \ pfa[0] is width, move 1 up \ cells \ no cells, we are in flash + \ -- char pfa[C+W*state] @i \ -- char xt execute \ -- ( xt consumes char! ) ; \end{verbatim} \end{small} \textbf{Einschränkung:} Diese sehr simple Lösung, \verb+]+ im Kompilier--Zweig des neuen Wortes einzusetzen, funktioniert nur bei \textit{indirect--threaded} Forths --- also nicht in gforth. Der Laufzeitanteil der Definition berechnet aus Spaltennummer, Breite der Tabelle und Zustand der FSM das zuständige Feld in der Tabelle, besorgt das dort abgelegte \verb+xt+ und führt es aus. Die Definition der Zustandstabelle wird jetzt tatsächlich im Quelltext sichtbar. Man muß sich nur klarmachen, daß lediglich drei verschiedene Aktionen/Übergänge stattfinden: Annehmen des Zeichens und Übergang nach Zustand \verb+1+ oder Zustand \verb+2+ einerseits, sowie Verwerfen des Zeichens ohne einen Übergang andererseits. \begin{small} \begin{verbatim} : (>1) append 1 mystate ! ; : (>2) append 2 mystate ! ; 4 wide fsm: ( action# -- ) \ 0 1 2 3 \ column# \ other 0-9 - . \ state \ ------------------------------------ drop (>1) (>1) (>2) \ 0 drop (>1) drop (>2) \ 1 drop (>2) drop drop \ 2 ; \end{verbatim} \end{small} Das Wort \verb+getafix+ ändert sich nicht. Das Programm tut immer noch das gleiche, aber \verb+case+ benötigen wir nicht mehr, und die Darstellung ist besser zu lesen. Das Wort \verb+wide+ tut nichts und dient ausschließlich der besseren Lesbarkeit. % \begin{small} % \begin{verbatim} % x % \end{verbatim} % \end{small} % -------------------------------------------------------------------- \section{Version 3} Die Worte \verb+(>1)+ und \verb+(>2)+ zeigen zwar den gewünschten Übergang an, aber nicht unbedingt die auszuführende Aktion. Das lässt sich verbessern, wenn man in jedem Feld der Tabelle zwei Einträge hinterlegt: (a.) das \verb+xt+ der gewünschten Aktion und (b.) die Nummer des gewünschten, nächsten Zustands, etwa so: \begin{small} \begin{verbatim} 0 constant >0 1 constant >1 2 constant >2 4 wide fsm: ( char action# -- ) \ 0 1 2 3 \ other 0-9 - . \ state drop >0 append >1 append >1 append >2 \ 0 drop >1 append >1 drop >1 append >2 \ 1 drop >2 append >2 drop >2 drop >2 \ 2 ; \end{verbatim} \end{small} Die Definition der Konstanten ist nötig, weil der Kompiler die Worte einliest. Man könnte natürlich auch \texttt{drop [ 0 , ]} statt \texttt{drop >0} schreiben. Andererseit ermöglichen Konstanten die Bezeichnung der Zustände mit sprechenden Namen. Die zugehörige Definition von \verb+fsm:+ sieht dann so aus: \begin{small} \begin{verbatim} : fsm: ( width -- ) create , \ store width in flash ] \ switch compiler on to \ consume state table does> ( char col# -- ) \ -- char col# pfs swap over \ -- char pfa col# pfa @i \ -- char pfa C width mystate @ * \ -- char pfa C W*state + \ -- char pfa C+W*state 1+ \ pfa[0] is width, move 1 up \ cells \ no, we are in flash 2* \ we have 2 xt per field now. + \ update state first dup @i execute mystate ! \ call action ( xt consumes char! ) 1- @i execute ; \end{verbatim} \end{small} Die Reihenfolge von Aktion und Änderung des Zustands ist willkürlich und kann selbstverständlich auch geändert werden. Der Vorteil dieser Version besteht darin, daß die Worte der Aktionen (\verb+drop+ und \verb+append+) im Gegensatz zu den alten Worten \verb+(>1)+ und \verb+(>2)+ nichts mehr über das Ändern der Zustände wissen müssen. % -------------------------------------------------------------------- \section{Version 4} Zwei weitere Verbesserungen sollen noch vorgenommen werden. (a.) Geschachtelte oder gar rekursive FSMs sind nicht möglich, solange die Variable \verb+mystate+ global für alle FSMs einer Sorte gilt. Die Lösung ist aber naheliegend: man allokiert eine Zelle im RAM und speichert die zugehörige Adresse im Parameterfeld der FSM. (b.) Es soll zuerst die Aktion ausgeführt und dann der Zustand geändert werden. Dabei soll der Datenstapel frei sein, so daß Aktion auch etwas auf dem Datenstapel hinterlassen könnte. Die Adresse des Zeigers auf den Status (\verb+pfa[0]+) und die Adresse der zu Zustand und Eingabe passenden Tabellenzelle (\verb+pfa[col#,state]+) werden auf dem Return--Stapel zwischengeparkt. Leider wird der Laufzeitteil des Wortes \verb+fsm:+ davon nicht besser lesbar. \begin{small} \begin{verbatim} : fsm: ( width -- ) create here , 2 allot \ p->state , \ store width in flash ] \ switch compiler on to \ consume state table does> ( char col# -- ? ) \ -- char col# pfa dup >r \ -- char col# pfa \ r: pfa 1+ @i \ -- char col# width r@ @i @ * \ -- char C W*state + \ -- char C+W*state 2* \ we have 2 xts per field now. r@ + \ -- char p->action 1+ \ pfa[0] is p->state, move 1 up 1+ \ pfa[1] is width, move 1 up dup >r \ -- char p->action \ r: pfa p->action \ call action ( xt consumes char! ) @i execute \ -- ( ? ) \ update state r> 1+ \ -- ( ? ) p->update @i execute \ -- ( ? ) r> @i ! \ -- ( ? ) ; \end{verbatim} \end{small} Der Rest des Programms bleibt aber unverändert. Alle Versionen finden sich in den Listings und können von der VD Webseite heruntergeladen werden. % \begin{small} % \begin{verbatim} % x % \end{verbatim} % \end{small} % % -------------------------------------------------------------------- % \section{Version x} % % {\itshape % x % } % -------------------------------------------------------------------- \section{Ausblick} Der Aufsatz von J.\,Noble geht weiter mit einer \textit{nicht deterministischen} Variante einer FSM, die FORTRAN Identifier prüft, sowie einer anderen FSM, die Gleitkommazahlen mit Exponenten entgegennimmt. Vielleicht gibt es daher eine Fortsetzung des Artikels. Möglicherweise könnte so eine FSM als recognizer zusammen mit dem \verb+float+ Modul zum Verarbeiten von Gleitkommazahlen dienen. Selbstverständlich sind alle aufgerufen, Probleme, die sich mit einer FSM lösen lassen, anhand der vorgestellten Lösungen umzusetzen. % -------------------------------------------------------------------- \section{So Sachen} \textbf{1.} % Bei der Aktion habe ich natürlich prompt eine Unzulänglichkeit (Fehler wäre schon zu hoch gegriffen) in amforth gefunden, der verhinderte, daß die frisch angelegte FSM \verb++ in der Wortliste auftauchte. Matthias Trute hat das sehr zügig repariert. Die gezeigten Programme funktionieren ab der Version 4.9. \textbf{2.} % Und nochmal zur Wiederholung: die hier gezeigten Lösungen funktionieren nur mit \textit{indirect--threaded} Forths. %\textbf{3.} % \end{multicols} % -------------------------------------------------------------------- \section{Referenzen} \begin{enumerate} \item \label{amforth} \url{http://amforth.sourceforge.net/} \item \label{ref:noble:fsm} J.\,V.\,Noble --- Finite State Machines in Forth, \url{http://www.forth.org/literature/noble.html} \end{enumerate} % -------------------------------------------------------------------- \section{Listings} \begin{quote} \begin{small} \begin{multicols}{2} \textbf{Prozedural programmierte Lösung}\par \listinginput[1]{1}{2012-02/adv11/fsm1.fs} \textbf{Puffer für die Zeichenkette}\par \listinginput[1]{1}{2012-02/adv11/tempbuffer.fs} \textbf{Automat Version 1}\par \listinginput[1]{1}{2012-02/adv11/fsm2.fs} \textbf{case}\par \listinginput[1]{1}{2012-02/adv11/case.fs} \textbf{Automat Version 2}\par \listinginput[1]{1}{2012-02/adv11/fsm3.fs} \textbf{Automat Version 3}\par \listinginput[1]{1}{2012-02/adv11/fsm4.fs} \textbf{Automat Version 4}\par \listinginput[1]{1}{2012-02/adv11/fsm5.fs} \end{multicols} \end{small} \end{quote} \end{document}