The main contribution of this paper is to promote a transformation, based on the descriptional composition mechanism, to an efficient functional programming deforestation method. To do so, our study involves two main issues. At first, the definition of a translation, called FP-to-AG, from a functional program into its attribute grammar notation, with a new symbolic evaluation for attribute grammars; next, a projection transformation -- close to the descriptional composition -- combined with the symbolic evaluation, that defines a new program transformation called symbolic composition.

With FP-to-AG on the one hand and the reciprocal translation based on well-known technique (for instance [18]) on the other hand, the symbolic composition can be fully applied in the functional framework: it transforms a functional program into another one. This allows us to characterize a class of functional programs for which symbolic composition performs more deforestation than other functional methods.

This paper is organized as follows. Section 2 defines the translation from a functional program into its attribute grammar form. Section 3 presents several transformations allowing symbolic composition to be efficiently applied on attribute grammars generated by the previous translation. Finally, section 4 deals with related work and improvements for both functional deforestation methods and attribute grammars transformations.


Web page maintained by Didier Parigot
Fri Feb 27 17:28:38 MET 1998