Using Circular Programs to Deforest in Accumulating Parameters

Author: J. Voigtländer
Published: Higher-Order and Symbolic Computation, volume 17(1-2), pages 129-163, Kluwer, 2004.
DOI: 10.1023/B:LISP.0000029450.36668.cb
BibTeX: Voi04a.bib
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.
Download: UsingCircularProgramsToDeforestInAccumulatingParameters_HOSC.pdf
Rights: Copyright held by Kluwer, now Springer. The definitive version of this work is available from
Slides: Slides of my corresponding conference talk are here.