OCaml-Flat - An OCaml Toolkit for experiment with formal languages theory
Formal languages and automata theory (FLAT) is a core subject in Computer Science, but the formal nature of the matter constitutes a difficulty to many students. It helps to have an interactive environment supporting the definition and testing of language generators and language recognizers. The programming language OCaml is a natural candidate to the implementation of such environment: it is a very clean and elegant language supporting the functional paradigm and with strong symbolic processing abilities.
This MSc Dissertation proposal aims at promoting the use of OCaml in the Portuguese speaking academic community, namely by providing support to teaching approaches and tools. In particular, it aims at extending and consolidating the OCaml software user base and teaching materials in the Portuguese language for Computational Logic and Foundation of Computing courses in undergraduate Computer Science degrees.
Objectives
The MSc student is expected to develop a FLAT toolkit to support the definition of alphabets, order relations and languages. The languages will be mainly defined using language generators and language recognizers. Here are some definitional mechanisms to support: predicates (Boolean functions), regular expressions, finite automata, context-free grammars, push-down automata, Turing machines.
Conversion between mechanisms would also be interesting, for examples rewriting a regular expression in the form of a context-free grammar.
It should also be possible to check a language definition against a set of unit test, to support the integration of the system in an automatic programming evaluation system (such as Mooshak, or other).
Avoiding endless loops will be a concern in the implementation of the nondeterministic definitional mechanisms. It will be necessary to explore all the alternatives in parallel and use a mechanism for detection of repeated configurations.
Expected contributions
A very clear implementation in OCaml of a set of generators and language recognizers. Whenever possible, the code should follow closely the formalization of the concepts as studied by the students. Cater for an extensible design. In particular, it is important to identify shared features among the mechanisms and to factorize the corresponding code. Find reasonable ways to deal with the nondeterminism of some of the mechanisms. The toolkit should present itself as an OCaml module, intended to be used in the context of the OCaml interpreter. Developing a graphical interactive environment is outside the scope of this project.
Results
- Code: https://gitlab.com/releaselab/factor/OCamlFlat
- OCaml-Flat - An OCaml Toolkit for experimenting with formal languages theory - [pdf]