J'ai effectué cette thèse de l'Université d'Orléans dans le projet OSCAR à l'INRIA-Rocquencourt, sous la direction de Martin Jourdan, aujourd'hui chez MetaWare et encadré par Didier Parigot et par Gilles Roussel.
Je l'ai obtenu le 5 octobre 1998 avec la mention très
honorable devant le jury composé de:
Président | Martin Jourdan | MetaWare Technologies |
Rapporteurs | Françoise Bellegarde | université de Franche-Comté |
Bernard Lorho | université d'Évry Val d'Essonne | |
Examinateurs | Charles Consel | université de Rennes I |
Gaétan Hains | université d'Orléans | |
Didier Parigot | INRIA - Rocquencourt |
La thèse est disponible au format Postscript compressé (ps.gz). Pour d'autres formats, contactez Etienne.Duris[at]univ-mlv.fr.
Mots-clés: Grammaires attribuées, programmation fonctionnelle, programmation dirigée par la structure, formalismes algébriques, transformations de programmes, déforestation, généricité, analyses statiques.
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.