Programming macro tree transducers

Patrick Bahr, Laurence E. Day

    Research output: Conference Article in Proceeding or Book/Report chapterBook chapterResearchpeer-review

    Abstract

    A tree transducer is a set of mutually recursive functions transforming an input tree into an output tree. Macro tree transducers extend this recursion scheme by allowing each function to be defined in terms of an arbitrary number of accumulation parameters. In this paper, we show how macro tree transducers can be concisely represented in Haskell, and demonstrate the benefits of utilising such an approach with a number of examples. In particular, tree transducers afford a modular programming style as they can be easily composed and manipulated. Our Haskell representation generalises the original definition of (macro) tree transducers, abolishing a restriction on finite state spaces. However, as we demonstrate, this generalisation does not affect compositionality.
    Original languageUndefined/Unknown
    Title of host publicationProceedings of the 9th ACM SIGPLAN Workshop on Generic Programming
    Number of pages12
    Place of PublicationNew York, NY, USA
    PublisherAssociation for Computing Machinery
    Publication date1 Sept 2013
    Pages61-72
    ISBN (Print)978-1-4503-2389-5
    DOIs
    Publication statusPublished - 1 Sept 2013

    Keywords

    • tree automaton, transducer, accumulation, composition, deforestation, Haskell, recursion scheme, nested recursion, polymorphism

    Cite this