The Haskell library HaLeX enables us to model, manipulate and animate regular languages. This library was developed in the context of a programming methodology course for undergraduate students, and as a consequence, it was defined mainly for educational purposes. Indeed, it provides a clear, efficient and concise way to define, to understand and to manipulate regular languages in Haskell. Furthermore, the construction of the complete library has been proposed as assignment projects to the students following the course. HaLeX is now being used to support this course.
1- What is HaLeX?
The HaLeX library introduces a number of Haskell datatypes and the respective functions that manipulate them, providing the following facilities:
2- The Library
2.1- Regular Expressions
Regular expressions are modelled in Haskell by the abstract data type RegExp , parameterized with the type of the symbols. We define one data constructor for each "standard" regular expression operator.
and we can write:
2.2- Deterministic Finite Automata
Formally, a Deterministic Finite Automaton (DFA) is a five-tuple A = (V,Q,S,Z,D) . In order to make our code more readable, we prefer to define a new data type, to express the automata's five-tuple, named Dfa with a single constructor, named Dfa as well, rather than using the Haskell built-in tuples. To make our DFA's more general, we parameterize the data type with the types of states and symbols
where sets are modelled through the Haskell built-in lists.
Now, We can define DFA easily in Haskell as follows:
2.3- Non-Deterministic Finite Automata
We define non-deterministic finite automata with epsilon transitions and several initial states.
To epsilon transitions we use the pre-defined datatype Maybe, where the constructor Nothing models epsilon-transitions, while the constructor Just models transitions labeled by its argument symbol.
Next, we show an example of a NDFA.
3- Drawing Finite Automata
Finite automata are more comprehensible in a graphical representation. The following representation is used by HaLeX : states are depicted as the nodes of a graph, final states get a red double circle, and the initial states are explicitly mentioned by using a green circle. The transition function induces arrows connecting the nodes of the graph: for each transition o to d thought symbol s there is an arrow labeled by s from node o to d .
Drawing graphs is a complex task and an intensive area of research. Thus, instead of defining a graph visualization system from scratch, and reinventing the wheel, HaLeX synthesizes a graph representation for an existing high quality graph visualization system: the GraphViz system , developed and available at AT\&T Labs .
GraphViz provides a collection of tools for manipulating graph structures and generating graph layouts. The input is a description of the graph in the Dot language. Next, we present an example of the input Dot text (left) and the outputed graph as displayed by one of GraphViz tools, the dot tool (right).
The HaLeX library includes a pretty-printing function, named toGraphViz that, given a FA, produces its (textual) graph representation in the Dot language. In order to ``beautify'' the graphical representation, we have included options to ignore the sink states and to fuse transitions with the same origin and destination.
4- Reactive Finite Automata
While accepting a sentence, we may wish the automaton to react. For example, we may wish to compute some trace information (for debugging purposes), or to perform some IO operations, or to compute semantic functions (in our example of real numbers, to convert the sequence of characters into its real value). A reactive finite automaton (RFA) is a machine that reacts while moving from one state to another. To add reactions to finite automata we use monads and we define monadic finite automata. Because we wish to associate different effects to finite automata, we parameterize the type of the DFA with the type of the monad. The reactions are defined in the (monadic) transition function. As a result, those functions not only have to indicate the destination state(s), but also the reactions to be performed in the transitions. Reactive deterministic finite automata are defined as follows:
4.1- Communication protocol
We want to construct a program to implement the communication protocol between two electronic components. The communication is established by sending an initial sequence of bits 000 . Then, several 3-bit values are sent in order to configure different parameters of the components. Those values are separated by the special sequence of bits 001 . The communication ends after the sequence of bits 111 is sent. Consider also that to configure the components the program has to compute the integer values transmitted.
5- HaLeX in Education
We started developing the HaLeX library in 2001 in the context of a third year course on programming methodology. This course has a working load of 24 hours of theoretical classes and another 24 hours of laboratory classes, running for 12 weeks (ie, a semester). The theoretical classes introduce the basic concepts of regular expressions, finite automata and context-free languages. HaLeX and HaGLr are used to support such classes. In the laboratory (a two hour class per week) the students have to solve exercises using a computer. We have defined eleven exercise sets (one per week), using literate Haskell, that the students have to complete. Each set of exercises defines a module of the HaLeX library. Thus, at the end of the course the students have a complete documentation of all the exercises and topics covered in the course, and, also, of the HaLeX library.
Furthermore, during the semester the students have to complete two assignment projects. The construction of parts of the HaLeX and HaGLr libraries have been proposed as such projects.
6- Where to get the software
The HaLeX system is public domain and it is available as a gzipped tar file at: HaLeX_1.1.tgz
THe HaLeX API is available here here . This documentation is also being distributed with the tool.
Pagina mantida por:
| Page produced by a Tool generated by
from the XML document
Last Change on Thu Oct 13 14:53:08 2005