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