Implementing Type-Inference-based Deforestation

Kirsten Chevalier
(Professor Alexander Aiken)
NSF Graduate Research Fellowship

Many lazy functional programs are modular collections of small functions that communicate via tree-like data structures. The advantages of this style include expressiveness and readability [1], but its disadvantage is inefficiency: lazy functional programs often use more time and space than equivalent imperative programs, partly due to the overhead of creating and destroying intermediate data structures. Deforestation is a program transformation that eliminates intermediate trees [2].

A particular strategy is shortcut deforestation, which exploits a simple programming pattern [3]. Using this pattern forces programmers to clutter their code with hints to the deforestation engine. Type-inference-based deforestation [4] builds on shortcut deforestation and removes the need for these annotations, making deforestation applicable to programs written without deforestation in mind. I am currently completing my implementation of type-inference-based deforestation for Haskell programs. Once it is finished, I plan to analyze the performance of type-inference-based deforestation on various benchmarks and compare its performance with that of other deforestation techniques.

A better practical understanding of deforestation will further the goal of making lazy functional programming languages useful for real-world applications, thus narrowing the gulf that exists between languages that can be efficiently compiled and languages that allow programmers to concisely express ideas.

J. Hughes, "Why Functional Programming Matters," Computer Journal, Vol. 32, No. 2, 1989.
P. Wadler, "Deforestation: Transforming Programs to Eliminate Trees," Theoretical Computer Science, Vol. 73, 1990.
A. Gill, J. Launchbury, and S. Peyton Jones, "A Short Cut to Deforestation," Proc. Conf. Functional Programming Languages and Computer Architecture, 1993.
O. Chitil, "Type Inference Builds a Short Cut to Deforestation," Proc. ACM SIGPLAN Int. Conf. Functional Programming, 1999.

Send mail to the author : (

Edit this abstract