% Content-encoding: UTF-8
% Dummy
\documentclass[ngerman,a4wide]{article}
\usepackage[utf8]{inputenc}
\usepackage{multicol,babel}
\setcounter{secnumdepth}{0}
\setcounter{tocdepth}{0}

\begin{document}
\renewcommand{\figurename}{Tabelle}

\title{Recognizer -- Interpreter dynamisch verändern}
\ifx\shorttitle\undefined\else
\shorttitle{Recognizer}
\fi
\author{Matthias Trute}
\maketitle

\begin{abstract}
Der Artikel beschreibt ein Konzept, um applikationsspezifische 
Daten mit einem modifizierbaren Interpreter zu verarbeiten. Dabei werden spezialisierte Parsing Words aus der jeweiligen Applikation über eine Standard-API dynamisch einbezogen.
\end{abstract}

\begin{multicols}{2}

\section{Anlass und Idee}

Amforth ist ein Forth für (sehr) kleine Systeme. Nichtsdestotrotz gibt es eine Gleitkommazahlbibliothek. Um sie nutzen zu können, sollte man die Gleitkommazahlen auch am Kommandoprompt eingeben können. Soweit so einfach. Nur, wie bringt man dem bestehenden Interpreter bei, Gleitkommazahlen zu verarbeiten? Der Unterschied zwischen "`1000"' und "`1E3"' ist eine Herausforderung nicht nur für den Parser. Es werden auch verschiedene Daten auf dem Stack  abgelegt: 1 Zelle für den Integer und 2 Zellen für das Float.

Die auf den ersten Blick einfachste Methode ist, das
passende \emph{parsing word} aus der Gleitkommabibliothek 
in den Code des Interpreters zu integrieren, ein neues 
System zu generieren und auf den Controller zu übertragen.

Das erfordert Anpassungen am Quellcode von amforth,
was, wie sich herausgestellt hat, eine große Hürde sein
kann.

Besser wäre eine dynamische Erweiterung des laufenden Interpreters,  die nach einigen wenigen Codezeilen die neuen Eingabeformate \emph{native} nutzbar macht.

Der erste Schritt ist die Erkenntnis, dass die neuen Formate 
dem Interpreter zunächst unbekannt sind. Er wird sie nicht
im Dictionary finden und als (Integer-) Zahl sind sie
auch nicht erkennbar.

Amforth bietet schon lange die Not-Found-Exception, die der 
Interpreter generiert, sobald ein Wort nicht verarbeitet
werden kann.

Es ist jedoch nicht trivial, die Reaktion auf die Exception 
so zu gestalten, dass der Interpreter mit Sonderaktionen reagiert und danach weitermacht, als wäre nichts gewesen. Methodisch ist es zudem wenig elegant, einen Fehlermechanismus für einen normalen Ablauf zu nutzen.

Ulrich Hoffmann hat auf der EuroForth 2008 ein System vorgestellt, das eine Vielzahl redefinierbarer Stellen im Interpreter vorsieht. Diese kann man umbiegen und so auf alle Eventualitäten reagieren. Auf den ersten Blick sehr reizvoll. Wenn man aber an die Details geht, kommt die Ernüchterung. So richtig \emph{einfach} ist das auch nicht.

Es ist eine Lösung gefragt, mit der man einen Interpreter 
erweitern kann, so dass er Worte in einer neuen Syntax verarbeiten kann. Da Mikrocontroller notorisch knapp an allen Ressourcen sind,hei"st das zudem, dass das Kernsystem nicht größer werden darf. Wer die Flexibilität nicht braucht, soll nicht bestraft werden. Unterschiedliche Codeabschnitte mit bedingter Assemblierung sind ebenfalls unzweckmäßig, da der Testaufwand steigt.

Das nachfolgend vorgestellte Konzept wird in amforth ab Version 
4.3 umgesetzt und hei"st Recognizer\footnote{Ja, amforth kann nicht nur Assembler, der Eindruck mag entstanden sein.}. Die grundlegende Idee  hierfür basiert auf einem Posting in der Usenetgroup \texttt{comp.lang.forth}, in dem Anton Ertl \emph{Number Parsing Hooks} vorstellt: 
\url{https://groups.google.com/group/comp.lang.forth/msg/f70a9ea205b5b75a}

\begin{quote}
Essentially the program has to provide a word (let's call it a
recognizer) that takes a string (for the "`word"' that was not found), and returns a flag that indicates whether the string was recognized or not.  In addition, the word may do things to the stack below the string/flag (e.g., push literal numbers) or compile things (e.g., literal numbers).  So, such a recognizer would have the stack effect:

( i*x c-addr u -- j*x f )

[Yes, let's not design counted strings into this interface]

In addition, the interface should support stacking of recognizers, so that one library can provide support for recognizing time syntax, while another library provides support for complex numbers.  The program should be able to specify in which order the recognizers should be processed (for cases where the recognized syntax overlaps). 
\end{quote}

Seine Ideen habe ich auf die bestehenden Strukturen im Interpreter verallgemeinert\footnote{Die Diskussion ging damals nur um Zahlenpräfixe}  und den Interpreter zu einem generischen Werkzeug umgebaut, das wesentliche Teile der Arbeit den Recognizern überlässt.

Ein Recognizer analysiert das vorliegende Wort und versucht, es zu "`verstehen"'. Ist das erfolgreich, wird das Wort komplett verarbeitet und dem  Interpreter signalisiert, dass dieser mit dem nächsten Wort fortfahren kann. Anderenfalls wird der nächste Recognizer aus der Liste aufgerufen.

Die Idee ist ähnlich zur SEARCH ORDER. Auch dort wird eine Reihe von word lists bis zum ersten Treffer abgearbeitet.

Zum Standardfunktionsumfang zählen drei Recognizer: \texttt{rec-find}, \texttt{rec-intnum} und \texttt{rec-notfound}. Was die ersten beiden machen, sollte unmittelbar einleuchten. Letzterer wird das Word im Eingabedatenstrom nicht verstehen, aber einen geordneten Ausstieg ermöglichen, indem er die Exception NOT-FOUND (-13) wirft.

\section{Umsetzung}

Die Umsetzung ist erstaunlich einfach. Der bereits existierende Interpretercode wird in seine Elemente zerlegt und in eine Iteration mit Abbruchbedingung über einer Liste umgebaut. 

Ein "`normaler"' Interpreter wird etwa wie folgt aussehen\footnote{Quelle: Hoffmann, Euroforth2008}:

{\small
\begin{verbatim}
: interpret ( -- )
  BEGIN
    BL WORD DUP COUNT DUP C@
  WHILE ( c-addr )
    FIND ?DUP
    IF OVER STATE @ 0<> = 
      IF COMPILE, ELSE
      EXECUTE THEN
    ELSE
      COUNT NUMBER? ?DUP IF 0< IF ?literal
      ELSE
        notfound
      THEN
    THEN
  REPEAT
  DROP ;
\end{verbatim}
}

Hier ist die Reihenfolge der Elemente FIND und NUMBER unveränderbar festgelegt. Demgegenüber steht der folgende Code. 

{\small
\begin{verbatim}
: interpret
  BEGIN
    \ Nur Worte mit mind. 1 Zeichen auswerten.
    BL WORD DUP C@ 0> IF
      \ EE_RECOGNIZER verweisst auf ein Array 
      \ im EEPROM: Erstes Feld ist die Länge des 
      \ Arrays, danach folgen die einzelnen Execution 
      \ Tokens der Recognizerworte
      EE_RECOGNIZERS DUP @E 0 ?DO 
        \ Auf dem Datenstack darf nichts ausser 
        \ dem Zugang zum Wort stehen, alles andere 
        \ muss weg, damit der Recognizer freie Bahn 
        \ hat
        OVER >R CELL+ DUP >R  
        \ Execution Token des Recognizers lesen 
        \ und ausführen
        @E EXECUTE
        \ Rückkehrcode prüfen und entweder 
        \ weiter mit dem nächsten Wort ...
        IF R> R> DROP DROP LEAVE THEN
        \ ... oder mit dem nächsten 
        \ Recognizer.
        R> R> SWAP
      LOOP
      \ Housekeeping
      ?STACK
    REPEAT
    DROP ;
\end{verbatim}
}

Dieser Interpreter zerlegt den Input in einzelne Worte\footnote{Aus pragmatischen Gründen basiert die Implementierung noch auf Counted Strings und \texttt{word}, das soll sich jedoch noch ändern.} und arbeitet anschließend eine Liste von Aktionen ab. Was die Aktionen machen, ist für den Interpreter nicht wichtig, er muss nur wissen: Hats geklappt oder nicht.

Das hei"st bei Worten aus dem Dictionary (FIND), dass das Execution Token ausgeführt bzw. compiliert wird. Analog muss der Integer-Recognizer den Wert auf dem Stack hinterlassen bzw ins Dictionary compilieren. In jedem Fall wird ein Flag zurückgegeben, das den Erfolg oder Misserfolg kommuniziert.

Beispielhaft der FIND Recognizer.

{\small
\begin{verbatim}
: rec-find
    \ Suche in allen Wordlisten
    FIND
    ?DUP IF
      \ gefunden, jetzt verarbeiten
      \ immediate?
      0> IF EXECUTE
      ELSE
        STATE @ 
        IF COMMA, ELSE EXECUTE THEN
      THEN
      \ Signal für den Interpreter: 
      \ habs gemacht
      -1
    ELSE
      \ Aufräumen und Signal: 
      \ Habs nicht gemacht
      DROP 0
    THEN ;
\end{verbatim}
}

Einfacher ist der Not-Found-Recognizer. Da er eine Exception generiert, muss er keinen eigentlichen Returncode bereitstellen\footnote{Eigentlich liefert der Recognizer immer -1 aka TRUE zurück.}. Das funktioniert, da der Interpreter  keine Exceptions auffängt, sondern dies der darüberliegenden Schicht überlässt (QUIT).

{\small
\begin{verbatim}
: rec-notfound
    COUNT TYPE
    -13 THROW
;
\end{verbatim}
}

Im Terminal sieht das dann so aus

{\small
\begin{verbatim}
> ver cr 1 2 + . cr huhu
amforth 4.4 ATmega16
3 
huhu ?? -13 23 
> 
\end{verbatim}
}

Der Text \verb|?? -13 23| stammt vom Exception Catcher in \texttt{quit}, der die beiden Fragezeichen, die Exceptionnummer und die Position im durch \texttt{source} bezeichneten Buffer ausgibt, an dem das Problem erkannt wurde (bei -13 ist das die Stelle nach dem betreffenden Wort).

Die eingangs erwähnte Gleitkommabibliothek enthält ein Wort \verb|>float|, mit dem sich eine Zeichenkette in ein Float konvertieren lässt und obendrauf ein Flag über den Erfolg der Aktion liefert. Damit wird der Recognizer \verb|rec-float| sehr einfach:

{\small
\begin{verbatim}
> 123e4 fs.
123e4 ?? -13 6
> : rec-float count >float 
 ok if state @ if postpone fliteral then -1 else 0 
 ok then ;
 ok
> ' rec-float place-rec 
ok
> 123e4 fs.
1.2299999E6 ok
>
\end{verbatim}
}

\section{Verwaltung}

Wie werden die Recognizer verwaltet? Da die Idee nicht auf kleine Systeme beschränkt bleiben muss, ist auch die Implementierung als Array im EEPROM alles andere als zwingend.

Hierfür habe ich zwei Worte vorgesehen: \texttt{set-recognizer} und \texttt{get-recognizer}. Beide stehen in Analogie zu \texttt{set-order} und \texttt{get-order}. \texttt{Get-recognizer} hinterlässt genau wie \texttt{get-order} eine Liste samt Anzahl der Elemente auf dem Datenstack. Diese Liste wird mittels \texttt{set-recognizer} gespeichert und unmittelbar aktiviert. Eine portable Version des obigen INTERPRET-Codes wird natürlich hierauf aufsetzen.

Die konzeptionelle Ähnlichkeit zum Search Order Wordset lässt weitere Worte in Analogie zu diesem sinnvoll erscheinen: \texttt{order}- und \texttt{only}-Analoga fallen zuerst ein. Welche konkret nützlich sind, wird hoffentlich eine Diskussion ergeben.

Ein derartiges Wort ist sicher das bereits benutzte \texttt{place-rec}. Es baut den übergebenen Recognizer unmittelbar \emph{vor} dem letzten derzeit aktiven ein. Damit bleibt die Recognizerliste inklusive dem abschließenden not-found intakt.

{\small
\begin{verbatim}
: place-rec ( xt -- )
    get-recognizer
    \ Anzahl sichern
    dup >r 
    \ Alle außer dem Letzten weg
    1-  n>r  
    \ den neuen einbauen
    swap
    \ und alles wieder aufbauen
    nr> drop r> 1+  
    set-recognizer
;
\end{verbatim}
}

Ein weiterer Punkt ist der \texttt{rec-notfound}-Recognizer selbst. Man kann darüber diskutieren, ob er nicht als Standard-Aktion \emph{immer} an das Ende der Liste angefügt wird. Die gegenwärtige Lösung lässt hingegen alle Freiheit.

\section{Spielereien}

Die Idee des Recognizers erlaubt Anwendungen, die zunächst erst einmal die Portabilität des Sourcecodes beeinträchtigen.

{\small
\begin{verbatim}
wordlist constant foo
... definiere wort(e) in foo
wordlist constant bar
... definiere wort(e) in bar
\end{verbatim}
}

Ein Recognizer ist darauf spezialisiert, anhand des Schemas \verb|<wordlist-id>::<wortname>| die Zuordnung der Worte in den entsprechenden Wordlists zu finden und zu verarbeiten.

\begin{itemize}
\item \verb|foo::wort| Suche in der Wortliste identifiziert durch \verb|foo| nach dem Wort \verb|wort| und verarbeite es \item \verb|bar::wort| Suche das Wort \verb|wort| in der Wortliste \verb|bar| und verarbeite es.
\end{itemize}

Syntaktische Feinheiten, wie \verb|$foo->wort,| %$ keep the editor happy
wobei \texttt{foo} eine Variable ist, die auf die zu nutzende Wordlist verweist, werden bei Forthianern sicher Schaudern hervorrufen, aber OO-Anhänger, die von anderen Sprachen kommen, begeistern\dots

Ein anderer Einsatzfall ist das Verarbeiten von vielen Zahlen bei wenig Code (Tabellen). Vertauscht man die beiden Recognizer für FIND und INTNUM, geht das spürbar schneller, da die nutzlose Suche im Dictionary entfällt.

Ein dritter denkbarer Einsatzfall könnten die zahlreichen neuen Worte aus dem Memory-Access-Standard sein, die regelbasiert gebildet, aber wohl nur selten im vollen Umfang implementiert werden. Hier ist eine Wort-Factory hilfreich, die als Recognizer eingebunden werden könnte.

Und wer wei"s, vielleicht lernt auch gforth irgendwann, dass die IP Adresse des \url{www.forth-ev.de} Servers (85.214.243.249, 3 Punkte in einer Zahl) nicht den numerischen Wert 85214243249. (double cell), als vielmehr 1440150521 (passt in eine 32bit Zelle) hat\dots

\section{Finale}

Das vorgestellte Konzept ist in Gänze im (aktuellen) amforth implementiert und funktioniert. Die Codegröße hat sich durch den Umbau nicht verändert, einzig der Platzbedarf im EEPROM für die Recognizerliste ist hinzugekommen. 

Mein Dank geht an alle, die mit mir in den letzten Monaten über das Thema im Chat \#forth-ev diskutiert haben, Feedback gaben oder einfach nur zugehört haben. Nicht alle werden so wirklich verstanden haben, was ich mit meinen Fragen bezweckt habe, jetzt werden sie es hoffentlich wissen.
\end{multicols}
\end{document}
