Composition of Functions with Accumulating Parameters

Authors: J. Voigtländer and A. Kühnemann
Published: Technical Report TUD-FI01-08, Technische Universität Dresden, August 2001.
BibTeX: VK01.bib
Abstract: A class of recursive functions with accumulating parameters can be modeled by macro tree transducers. We present a program transformation technique that can be used to solve the efficiency problems due to creation and consumption of intermediate data structures in compositions of such functions, where classical deforestation techniques fail. In order to do so, we construct for two given macro tree transducers, under appropriate restrictions, a single macro tree transducer that implements the composition of the two original ones. The imposed restrictions are more liberal than those in the literature on macro tree transducer composition, thus generalizing previous results.

A much revised version of this work appeared in Journal of Functional Programming, see here.