A domain-specific language for regular sets of strings and trees
| Autor: | Nils Klarlund, Michael I. Schwartzbach |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
Domain-specific language
Theoretical computer science Finite automaton Unification Computer science computer.software_genre Data type Set theory Tree automaton Logic programming Predicate logic Mathematical logic Finite-state machine Recursion Programming language String (computer science) Domain specific language Expression (computer science) Monad (functional programming) Finite state machine Subtyping TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Type theory High-level programming language Chain Computer Science::Programming Languages computer Software |
| Zdroj: | DSL Schwartzbach, M I & Klarlund, N 1999, ' A Domain-Specific Languane for Regular Sets of Strings and Trees ', I E E E Transactions on Software Engineering, vol. 25, no. 3, pp. 378-386 . https://doi.org/10.1109/32.798326 |
| ISSN: | 0098-5589 |
| DOI: | 10.1109/32.798326 |
| Popis: | We propose a novel high level programming 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 considerable complexity and practical interest. We motivate the need for a language like FIDO, and discuss our design and its implementation. Also, we briefly discuss design criteria for domain-specific languages that we have learned from the work with FIDO. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|