react0.tex 2.86 KB
 huet committed May 04, 2017 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. \subsection{Dispatching} 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} implementation.