Intermediate data-structures are both the basis and the bane of modular programming. If they allow functions to be composed, they also have a harmful cost from efficiency point of view (allocation and deallocation). To get the best of both worlds, deforestation transformations were introduced. These transformations fuse two pieces of a program into another one, where intermediate data-structure constructions have been eliminated. The first approach dealing with such transformations is Wadler's [35]. It is based on the ``fold and unfold'' transformation [2].
There is another interesting approach based on algebraic notions and often called deforestation in calculational form [15, 33, 22, 34, 16]. The idea of this approach is to capture both the function and the data-type patterns of recursion [25]. The goal is to drive deforestation transformations with respect to these recursion schemes.
In attribute grammars area, descriptional composition [12, 14, 10, 1, 31] is a well known and powerful deforestation method which eliminates intermediate data-structure constructions in compositions. Attribute grammars [21, 27] are declarative and structure-directed specifications. They specify on each data-type pattern what is to be computed instead of how it is computed.
In [8, 9, 7, 6], we have been studying
similarities and differences between descriptional composition and a large
subset of deforestation methods in calculational
form [15, 33, 16]. For particular
first-order functions, we have shown
that both techniques lead to equivalent results in their respective domain. But
we were also convinced that, at least for a class of programs, descriptional
composition could be the basis of a more powerful tool than category-flavored
deforestation methods.
As a striking example, let us consider the two following functions: rev reverses a list, and for a given binary tree, flat builds the list of its leaves from left to right (See Figure 1). In both functions, parameter l is initialized with nil:
The classical functional composition of these two functions leads to
where the list built by flat is the intermediate data structure consumed by rev (See Figure 1). Translating rev and flat into attribute grammars, our deforestation method produces a new attribute grammar that directly builds the reversed list. No longer intermediate list is constructed as presented in Figure 1.
Figure 1: Example of rev and flat composition, before and after
deforestation
Furthermore, it is possible to apply a copy rule
elimination to this deforested attribute grammar, corresponding
to the following revflat function definition:
This function directly constructs the list of leaves from right to left. The intermediate list built by the initial function flat is no longer constructed. As far as we know, such a deforestation cannot be achieved by any functional deforestation method.