Attribute grammars, and particularly those generated by symbolic composition, may contain many unnecessary attribute copy rules. They are only carrying values or constants around the input structure. However, a simple static global analysis on the attribute grammar can eliminate them in most cases [31].
In the case of the revflat example, the deforestation is due to the
fact that the result is already evaluated in the attribute
and then passed alone the tree via attribute
to
. At
this point, the symbolic composition is completely semantic preserving, even in
the case of partially defined tree, with one infinite branch, for instance. The
deforestation is complete in the sense of intermediate data structure
elimination. Nevertheless, in safe cases, i.e. totally defined trees without
infinite or undefined branch, the last traversal can be removed. In each node,
the equality between attributes
,
and
can be proven by structural induction over a tree. So, for
this example, the copy rules elimination [31] leads to the
attribute grammar below. This last version only constructs the list of the
leaves from right to left without useless traversal around the
tree. Finally, generating a functional evaluator [18, 29]
for this attribute grammar will lead to the deforested function
revflat expected in introduction.