De Forestation

Program-Transformation.Org: The Program Transformation Wiki
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


Transform.DeForestation moved from Transform.DeforestationTransformation on 02 Dec 2001 - 09:08 by EelcoVisser - put it back