USENIX Conference Policies
A Domain-Specific Language for Regular Sets of Strings and Trees
Nils Klarlund, AT&T Labs - Research and Michael I. Schwartzbach, University of Aarhus
We propose a new high-level progr amming notation, called FIDO, that we have designed to concisely express regular sets of strings or trees. In particular, it can be viewed as a domain-specific language for the expression of finite-state automata on large alphabets (of sometimes astronomical size).
FIDO is based on a combination of mathematical logic and programming language concepts. This combination shares no similarities with usual logic programming languages. FIDO compiles into finite-state string or tree automata, so there is no concept of run-time. It has already been applied to a variety of problems of consider able complexity and practical interest.
In the present paper, we motivate the need for a language like FIDO, and discuss our design and its implementation.
We show how recursive data types, unification, implicit coercions, and subtyping can be merged with a variation of predicate logic, called the Monadic Second-order Logic (M2L) on trees. FIDO is translated first into pure M2L via suitable encodings, and finally into finite-state automata through the MONA tool.
author = {Nils Klarlund and Michael I. Schwartzbach},
title = {A {Domain-Specific} Language for Regular Sets of Strings and Trees},
booktitle = {Conference on Domain-Specific Languages (DSL 97)},
year = {1997},
address = {Santa Barbara, CA },
url = {https://www.usenix.org/conference/dsl-97/domain-specific-language-regular-sets-strings-and-trees},
publisher = {USENIX Association},
month = oct
}