PhD thesis on the FNC-2 system

[1]

Didier Parigot. Mise en oe uvre des grammaires attribuées: transformation, évaluation incrémentale, optimisations. thèse de 3ème cycle, University de Paris-Sud, Orsay, September 1987.

[2]

Didier Parigot. Transformations, Évaluation Incrémentale et Optimisations des Grammaires Attribués: Le Système FNC-2. PhD thesis, Université de Paris-Sud, Orsay, 1988.

[3]

Catherine Julié. Optimisation de l'espace mémoire pour l'évaluation de grammaires attribuées. PhD thesis, Université d'Orléans, September 1989.

[4]

Aziz Souah. Contribution à la sémantique déclarative des systèmes de transformation d'arbres attribués. PhD thesis, Universitéd'Orléans, November 1990.

[5]

Martin Jourdan. Des bienfaits de l'analyse statique sur la mise en oe uvre des grammaires attribuées. Mémoire d'habilitation, Département de Mathématiques et d'Informatique, Université d'Orléans, 1992. (Gzipped PostScript, 64 pages, 253337 bytes)

[6]

Carole Le Bellec. La généricité et les grammaires attribuées. PhD thesis, Département de Mathématiques et d'Informatique, Université d'Orléans, 1993. (Gzipped PostScript, 211 pages, 343858 bytes)

[7]

Gilles Roussel. Algorithmes de base pour la modularité et la réutilisabilité des grammaires attribuées. PhD thesis, Département d'Informatique, Université de Paris 6, March 1994. (Gzipped PostScript, 148 pages, 461010 bytes)

[8]

Bruno Marmol. La parallélisation et l'optimisation mémoire dans l'évaluation des grammaires attribuées. PhD thesis, Universitéd'Orléans, 1994. (Gzipped PostScript, 126 pages, 343283 bytes)

[9]

Etienne Duris. Contribution aux relations entre les grammaires attribuées et la programmation fonctionnelle. PhD thesis, Université d'Orléans, 1998. (Gzipped PostScript, 208 pages, 553590 bytes)

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.