Using Circular Programs to Deforest in Accumulating Parameters
| Author: | J. Voigtländer |
|---|---|
| Published: | In Asian Symposium on Partial Evaluation and Semantics-Based Program Manipulation (ASIA-PEPM'02, acceptance rate 11/21), Aizu, Japan, Proceedings, pages 126-137, ACM, September 2002. |
| DOI: | 10.1145/568173.568187 |
| BibTeX: | Voi02b.bib |
| Abstract: | Functional languages allow a modular programming style by function composition, which however can lead to inefficient runtime behavior due to production and consumption of intermediate results. We present a new mechanizable transformation technique for removing intermediate data structures in the composition of two functions from a class of recursive functions with accumulating parameters, for which classical deforestation techniques fail. In order 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 presented in the paper. |
| Slides: | Slides of my talk at the conference are here. |
An extended version of this work appeared in Higher-Order and Symbolic Computation, see here.