The main goal of this article is to show that it is possible to translate (interpret) attribute grammars transformation techniques in functional programs transformation terms.
More precisely, we show that thanks to the fundamental algorithm of the symbolic composition, our deforestation achieves better results than other techniques developed in the functional community. This result reinforces our conviction that the attribute grammar formalism is simple and powerful for this kind of transformation. The FP-to-AG translation (presented here in its simpler form) together with the reciprocal Johnsson's transformation should be viewed as auxiliary tools. For a practical use of this deforestation, FP-to-AG could be improved and extended, but this will not question the intrinsic power of our symbolic composition. Furthermore, this problem is not specific to our attribute grammar-based deforestation since it arises also in calculational systems, such as HYLO (see for example [26]).
Moreover, we extend the basic descriptional composition into a more powerful one: the symbolic composition. This extension allows it on the one hand to be used as a partial evaluation and on the other hand to be more widely usable. Henceforth, it could be applied to terms with function compositions, and not only to one composition of two distinct attribute grammars (grammar couple [14]) that are isolated of all context. From the point of view of the attribute grammars community, this should stand as the main contribution of this article.
This work is a part of a more general study, that is the genericity with attribute grammars. The principle of this kind of genericity, whose basic tool is the symbolic composition, is to abstract a program, to be able to specialize it in several contexts. Similar approaches are being studying in different programming paradigms (polytypic programming [17], adaptive programming [28]). We just begin to compare [5] these approaches with our genericity tools [23, 24, 32, 31, 4], that have been implemented in our FNC-2 system. It appears also in this context that attribute grammars, particularly suitable for program transformations, should be viewed more as an abstract representation of a specification than as a programming language.