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


CategoryOptimization

Revision: r1.3 - 04 Dec 2001 - 10:45 - EelcoVisser
Transform > ProgramOptimization > DeForestation
Copyright © 1999-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback