react0.tex 2.86 KB
Newer Older
huet's avatar
huet committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
\subsection{From automata to reactive processes}

We consider finite state automata and transducers as data structures representing the
states and their transitions. Such automata are interpreted by a computational process,
which will manage the input tape, possibly an output tape in the case of transducers,
and a backtrack stack used to manage non-deterministic search through fair backtracking. 
This is the point of view of finite-state control as presented in the reactive programming
methodology, and thus we shall speak of this interpretative process as a {\sl reactive engine}.
In our first level of automata, this engine will be a simple recognizer for its input string:
il will successfully terminate when this input string is a word belonging to the language,
and raise the exception {\sl Finished} otherwise.

Our methodology is {\sl modular}, in the sense that it allows the composition of automata
by layers - at the upper level, we consider a regular expression over a finite alphabet of 
{\sl phases}, while at the lower level each phase corresponds to a finite automaton over
letters of the global language. The global language corresponds to the substitution of
each phase language in the given regular expression. The handling of control from the automaton
of some phase into the automaton of the next phase is effected by the reactive engine through
a scheduling switch implemented as a {\sl Dispatch} module. 


We compile our regular expressions using the Berry-Sethi method, which
linearizes the expression, and computes the local automaton associated
to this linearization \cite{berrysethi,berstelpin}. We call {\em phases}
the morphology categories, defining the alphabet of the regular expression.
The local automaton is described by an {\sl initial} phase, 
a set of {\sl terminal} phases, here represented as
a boolean function over phases, and a {\sl dispatch} transition function,
mapping each phase to a set of following phases, sequentialized here as a list.
In terms of Berry-Sethi \cite{berrysethi}, {\sl initial} is called {\sl 1}, 
{\sl dispatch} is called {\sl follow}, and {\sl terminal} is implicit from
use of an endmarker symbol.
In the terminology of Eilenberg \cite{eilenberg}, the phase language
presented by Dispatch is a local set over phases. 

The Dispatch module is generated by meta-programming from the regular 
expression, as we shall explain in section \ref{macro}.

\subsection{Scheduling and React}

We are now ready to start the description of the reactive engine, as
a functor {\sl React} taking a module {\sl Dispatch} as parameter, and using the
{\sl Dispatch.dispatch} function as a local scheduler. 
We assume the utility programming functions {\sl fold\_right},
{\sl assoc}, {\sl length}, {\sl mem}, etc. from the {\sl List}
standard library.

Corresponding to simplistic aums {\sl Aum0}, we have a simplified {\sl React0}