attribute grammars (that can be computed with only one
synthesized attribute), descriptional composition and functional deforestation
led to equivalent results.
We have already shown in [8, 9] that for simple programs,
and particularly attribute grammars (that can be computed with only one
synthesized attribute), descriptional composition and functional deforestation
led to equivalent results.
In spite of the restrictions associated with our FP-to-AG translation, this
paper shows that programs like 
or 
are deforested by symbolic composition while they are not by
functional deforestations in calculational form. So we can formulate our main
result as:
In section 4.1, we try to point out some reasons to explain why symbolic composition seems intrinsically stronger than the various category-flavored methods.
In fact, most structure-directed methods in functional programming are based on categorical notions such as functors, catamorphisms and hylomorphisms. These methods are supported by fundamental laws like Promotion Theorem [25], and use generic control operators to capture both the function and the type definition patterns of recursion. First, shortcut deforestation [15] with foldr/buildr elimination rule made this possible for the type list. Then, the Normalization Algorithm [33, 11, 22] generalized it to work on any type, thanks to an automatic generation of functors from algebraic type definitions. But these functors were too much isomorphic to the types. To relax this constraint, hylomorphisms in triplet form [34] were introduced but they still deal with functors. Systems like ADL and HYLO [26, 20] are based on this formalism and deforest some complex functional programs using an automatic process.