|
Conference on Domain-Specific Languages, 1997
A Domain-Specific Language for Regular Sets of Strings and Trees
Nils Klarlund
AT&T Labs - Research
Michael I. Schwartzbach
University of Aarhus
Abstract
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.
- View the full text of this paper in
PDF form.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
- To become a USENIX Member, please see our Membership Information.
|
Need help? Use our Contacts page.
Technical Program