
% 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}
: <fixed.point#> ( 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 @  <fixed.point#>
  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: <fixed.point#> ( 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: <fixed.point#> ( 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+<fixed.point#>+ 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}
