De Forestation

Deforestation is a ProgramTransformation that eliminates intermediate data-structures (trees). The technique was invented by PhilipWadler for optimization of functional programs.

The idea is to fuse the composition of two functions f(g(x)) into a new function h(x) such that the data-structure that is passed from g to f is never constructed. This is achieved by creating a new function

  h(x) = f(g(x))

and inlining the definitions of f and g. If everything works out the data deconstructors of f can be fused with the data constructors of g and no data are constructed. Recursive invocations f(g(y)) of the fused functions can be replaced with a call to the new function h(y).

Algorithms for deforestation

• ShortCutFusion^?
• WarmFusion^?

-- EelcoVisser - 02 Dec 2001