Contribution aux relations entre les grammaires attribuées et la programmation fonctionnelle

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 comp onents 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 comp osition 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.L'ingénierie du logiciel doit concilier, d'une part, la modularité requise par les phases de développement et de maintenance et, d'autre part, l'efficacité indispensable dans la mise en oeuvre des applications. Ce dilemme nécessite des méthodes et des techniques de transformation permettant d'accroître l'efficacité des programmes modulaires. La déforestation, qui consiste à éliminer les structures intermédiaires apparaissant lors de la composition des différentes parties d'un programme, a suscité beaucoup d'intérêt, notamment en grammaires attribuées et en programmation fonctionnelle. En dépit de la diversité des formalismes utilisés, cette thèse compare les différentes techniques existantes et s'inspire de leurs atouts pour développer une nouvelle méthode de déforestation plus générale. Tout d'abord, une extension naturelle des grammaires attribuées est introduite pour permettre de représenter une plus large classe de programmes fonctionnels. Les grammaires attribuées dynamiques peuvent se passer de la présence physique d'un arbre pour guider les calculs et les transformations, mais bénéficient des méthodes classiques d'évaluation des grammaires attribuées. Ensuite, les principales méthodes fonctionnelles de déforestation (algorithme de Wadler, règle d'élimination foldr/build, normalisation des folds, fusion d'hylomorphismes) sont étudiées et comparées avec la composition descriptionnelle des grammaires attribuées. Les limitations de chaque méthode sont établies et permettent de déterminer les atouts nécessaires pour ces transformations de programmes. Finalement, une nouvelle méthode de déforestation est proposée. La composition symbolique utilise la puissance du formalisme des grammaires attribuées et incorpore un mécanisme d'évaluation partielle. Cette technique générale peut être appliquée sur des grammaires attribuées ou sur des programmes fonctionnels et permet de déforester des programmes pour lesquelles les méthodes existantes restaient impuissantes