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.

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

Send mail to the author : (krc@uclink.berkeley.edu)


Edit this abstract