Programming macro tree transducers

Patrick Bahr; Laurence E. Day

doi:10.1145/2502488.2502489

Programming macro tree transducers

Patrick Bahr, Laurence E. Day

Department of Computer Science

4 Citations (Scopus)

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 language	English
Title of host publication	Proceedings of the 9th ACM SIGPLAN Workshop on Generic Programming
Number of pages	12
Publisher	Association for Computing Machinery
Publication date	2013
Pages	61-72
ISBN (Print)	978-1-4503-2389-5
DOIs	https://doi.org/10.1145/2502488.2502489
Publication status	Published - 2013
Event	9th ACM SIGPLAN Workshop on Generic Programming - Boston, United States Duration: 28 Sept 2013 → 28 Sept 2013 Conference number: 9

Conference

Conference	9th ACM SIGPLAN Workshop on Generic Programming
Number	9
Country/Territory	United States
City	Boston
Period	28/09/2013 → 28/09/2013

Access to Document

10.1145/2502488.2502489

Cite this

@inproceedings{1ac7683656e04b059fd64ecbc749b46a,

title = "Programming macro tree transducers",

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.",

keywords = "deforestation, modularity, recursion schemes",

author = "Patrick Bahr and Day, {Laurence E.}",

year = "2013",

doi = "10.1145/2502488.2502489",

language = "English",

isbn = "978-1-4503-2389-5",

pages = "61--72",

booktitle = "Proceedings of the 9th ACM SIGPLAN Workshop on Generic Programming",

publisher = "Association for Computing Machinery",

note = "9th ACM SIGPLAN Workshop on Generic Programming, WGP '13 ; Conference date: 28-09-2013 Through 28-09-2013",

}

TY - GEN

T1 - Programming macro tree transducers

AU - Bahr, Patrick

AU - Day, Laurence E.

N1 - Conference code: 9

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - deforestation, modularity, recursion schemes

U2 - 10.1145/2502488.2502489

DO - 10.1145/2502488.2502489

M3 - Article in proceedings

SN - 978-1-4503-2389-5

SP - 61

EP - 72

BT - Proceedings of the 9th ACM SIGPLAN Workshop on Generic Programming

PB - Association for Computing Machinery

T2 - 9th ACM SIGPLAN Workshop on Generic Programming

Y2 - 28 September 2013 through 28 September 2013

ER -

Programming macro tree transducers

Abstract

Conference

Access to Document

Fingerprint

Cite this