Avec ÉTIENNE DURIS et GILLES ROUSSEL Les GA dynamiques nous permettent d'atteindre le même pouvoir d'expression que les langages fonctionnels du premier ordre. Dans ceux-ci, le problème de l'élimination des structures intermédiaires (déforestation) est abordé à l'aide de l'opérateur de contrôle générique fold, qui permet de rendre la structure des données plus explicite (programmation dirigée par la structure). Cette propriété structurelle étant intrinsèque aux GA, nous avons été amenés à comparer les GA et les folds, tant sur le plan du pouvoir d'expression que sur celui de leurs méthodes de ``composition optimisante'' (composition descriptionnelle et fusion, respectivement).
Dans [DPRJ96a,DPRJ96b,DPRJ97], nous présentons nos premiers résultats. Les folds du premier ordre sont équivalents aux GAs purement synthétisées. Dans ce cadre, la fusion des folds et la composition descriptionnelle aboutissent au même résultat, mais cette dernière est complètement indépendante de l'évaluation (transformation de source à source) tandis que la fusion nécessite la connaissance de la méthode d'évaluation. De plus, beaucoup de programmes qui nécessitent l'usage de folds d'ordre supérieur peuvent être traités avec des GA du premier ordre, grâce à la notion d'attribut hérité. Les approches différentes de ce problème dans ces deux formalismes permettent d'envisager des fertilisations croisées entre GA et programmation fonctionnelle.
Plus généralement, les folds étant des catamorphismes [FJMM91], nous avons commencé à étudier les GA en termes algébriques, afin de comparer plus facilement les résultats obtenus en GA et en programmation fonctionnelle et de faciliter le passage de connaissances d'un domaine à l'autre. En particulier, nous commençons à étudier notre notion de généricité structurelle dans le monde fonctionnel [DPRJ97].