Composition of Functions with Accumulating Parameters#

Abstract A class of recursive functions with accumulating parameters can be modeled bymacro tree transducers. We present a program transformation technique that can be used to solve the efficiency problems due to creation and consumption of intermedi-ate 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 appro-priate restrictions, a single macro tree transducer that implements the compositio