Refactorisation de programmes fonctionnels par les ornements

Ornaments provide a way to express transformations of inductive datatypes that reorganize, specialize, and add fields to already existing datatypes. From such a transformation, we consider the problem of semi-automatically refactoring an already existing ML program operating on the base type into a program operating on the ornamented type. We describe a framework for such transformations by decomposing them in two phases: first, the base term is maximally generalized by abstracting over the details of the manipulated datatypes. This generic term is subsequently specialized to operate only on the ornamented type. We describe an intermediate language providing the necessary abstractions to present the generic term. This language notably includes dependent abstractions, allows representing the equalities learned from pattern matching, and provide a way to refer to the opaque result of previous computations. We exploit the parametricity of the generic term to derive a coherence relation between the base term and the ornamented term, guaranteeing the correctness of the ornamented term. We present an implementation of this transformation on a core ML language, and illustrate its usefulness in many common cases of program transformation: pure refactoring, adding new data and specialization. We also present a new unfolding technique afforded by our transformation and present its use for optimizing certain data representation and for generic programming.Les ornements fournissent un moyen de définir des transformations de définitions de types de données inductifs réorganisant, spécialisant et ajoutant des champs à des types de données déjà existants. À partir d’une telle transformation, nous nous intéressons à la refactorisation semi-automatique d’un code déjà existant, écrit en ML et opérant sur le type de base pour le faire opérer sur le type ornementé. Nous décrivons un cadre pour de telles transformations, basé sur deux phases: tout d’abord, le terme de base est généralisé au maximum en ajoutant des abstractions sur les détails des types de données utilisés. Le terme est ensuite spécialisé pour opérer uniquement sur le type ornementé. Nous décrivons un langage intermédiaire fournissant les abstractions nécessaires pour présenter le terme générique, et garantissant qu’il est possible de simplifier le terme spécialisé pour ne présenter à l’utilisateur que des termes du langage de base. Le langage intermédiaire permet notamment d’exprimer des abstractions dépendantes, de représenter les égalités apprises par le filtrage de motifs, et fournit une construction permettant de se référer de façon opaque au résultats de calculs déjà effectués. Nous exploitons la paramétricité du terme généralisé pour prouver une relation de cohérence entre le terme de base et le terme ornementé, garantissant la correction de la refactorisation. Nous présentons une implémentation de cette transformation sur un langage ML noyau, et justifions de son utilité dans de nombreux cas courants de transformation de programme: refactorisation pure, ajout de nouvelles données et spécialisation. Nous présentons aussi une nouvelle technique de dépliage permise par notre transformation qui autorise à changer la structure récursive des fonctions, et illustrons son utilité pour optimiser certaines représentations de données et pour la programmation générique