Higher-Order and Symbolic Computation, 17(1/2)129-163

Using Circular Programs to Deforest in Accumulating Parameters

Janis Voigtländer, Department of Computer Science, Dresden University of Technology, 01062 Dresden, Germany

Abstract: This paper presents a functional program transformation that removes intermediate data structures in compositions of two members of a class of recursive functions with accumulating parameters. To avoid multiple traversals of the input data structure, the composition algorithm produces circular programs that make essential use of lazy evaluation and local recursion. The resulting programs are simplified using a post-processing phase sketched in the paper. The presented transformation, called lazy composition, is compared with related transformation techniques both on a qualitative level and based on runtime measurements. An alternative use of higher-orderedness instead of circularity is also briefly explored.

Keywords: program transformation, intermediate results, accumulating arguments, circular programs, tupling, unfold/fold, (short cut) deforestation, tree transducers

This article can be downloaded [here]. 		[picture of journal cover]

June 2004 - hosc@brics.dk