PhD thesis,
Contribution aux relations entre les grammaires attribu�es et la programmation fonctionnelle
Universit� d'Orl�ans, (1998)ftp://ftp-sop.inria.fr/smartool/Didier.Parigot/publications/theses/Duris98.ps.gz.
Abstract
Software engineering has to reconcile modularity, that is required
for development and maintenance phases, with efficiency, obviously
essential in the practical implementation of applications. This dilemma
implies that methods and techniques must be developed in order to
increase the efficiency of modular programs. The aim of deforestation
transformations is to discard intermediate data structures that appear
when software components are composed. Thus, these transformations
are of great interest, especially to attribute grammar and functional
programming communities. In spite of the variety of formalisms they
used, this thesis compares several existing techniques and develops
a new general deforestation method drawn from their advantages. First,
a natural attribute grammar extension is introduced, allowing a larger
functional programming class to be expressed. Then, dynamic attribute
grammars are no more tied to concrete trees, to direct computations
and transformations. Nevertheless, they could always be evaluated
with classical attribute grammar evaluation methods. Next, the main
functional deforestation methods (Wadler's algorithm, elimination
of foldr/build rule, normalization of folds, fusion of hylomorphisms)
are studied and compared with the descriptional composition of attribute
grammars. Limitations of each method are established and allow suitable
features for these program transformations to be determined. Finally,
a new deforestation method is introduced. The symbolic composition
uses the power of attribute grammar formalism and also includes a
partial evaluation mechanism. This general technique can be applied
to attribute grammars or to functional programs and it deforests
programs for which existing methods were insufficient.
