Deriving Modular Recursion Schemes from Tree Automata

Patrick Bahr
Talk, Computing Science Colloquium, Utrecht University, The Netherlands, 12/04/2012.


In this talk I present various kinds of well-known tree automata and show how to implement these automata in Haskell. Subsequently, I refine the thus obtained recursion schemes in order to derive modular and extensible recursion schemes. Functions that are specified in terms of these recursion schemes can be combined, reused and transformed in many ways. This flexibility facilitates the specification of complex transformations in a concise manner, which I illustrate with a number of examples.

Category: Recursion Schemes

Tags: Tree Automaton, Transducer, Acceptor, Modularity, Attribute Grammar, Recursion, Compiler, Haskell