Quelqu'un a-t-il utilisé la défonctionnalisation polymorphe de Pottier et Gauthier dans un compilateur modulaire?

15

La défonctionnalisation est une transformation de programme qui convertit des programmes d'ordre supérieur en programmes de premier ordre. L'idée est que, compte tenu d'un programme, il n'y a qu'un nombre fini d'abstractions lambda, vous pouvez donc remplacer chaque lambda par un identifiant et chaque application de fonction par un appel à une procédure apply qui se ramifie sur cet identifiant. Ceci est parfois utilisé dans les compilateurs pour les langages fonctionnels, mais son applicabilité est limitée par le fait que la défonctionnalisation est une transformation de programme entier (vous devez connaître statiquement toutes les fonctions du programme), et donc seuls les compilateurs de programme complet utilisent il.

Cependant, Pottier et Gauthier ont donné un algorithme de défonctionnalisation typé polymorphe utilisant un typage plus sophistiqué impliquant des GADT. Maintenant, étant donné leur encodage, il est possible d'ajouter un casier fourre-tout à leur type de données lambda qui n'est pas une balise, mais qui contient une fonction d'ordre supérieur. Cela signifie qu'il devrait être possible d'utiliser leur codage pour un dysfonctionnement module par module.

Quelqu'un a-t-il fait cela et m'a dirigé vers un compilateur utilisant cette idée? (Les compilateurs de jouets sont corrects et en fait préférés.)

pl.programming-languages compilers Neel Krishnaswami
la source

Réponses:

4

Maintenant, étant donné leur encodage, il est possible d'ajouter un casier fourre-tout à leur type de données lambda qui n'est pas une balise, mais qui contient une fonction d'ordre supérieur. Cela signifie qu'il devrait être possible d'utiliser leur codage pour un dysfonctionnement module par module.

Pourriez-vous nous en dire un peu plus sur ce que vous voulez dire ici? Je ne comprends pas comment l'ajout d'un cas de base (serait-ce au type de données, à la correspondance de modèle de la fonction de répartition, ou aux deux?) Aide la modularité de la manière que vous avez décrite; au fait, pourquoi voulez-vous dire exactement par "module par module"?

Je peux imaginer un "cas de base" utilisé, à l'intérieur d'un module / programme donné, pour une défonctionnalisation sélective : vous auriez un constructeur supplémentaire à votre type de fonction réifiée qui n'est pas une balise, mais qui incorpore simplement toutes les 'a -> 'bfonctions, de sorte que le conditionnement d'une fonction dans ce constructeur, au lieu de lui donner une balise réifiée, empêcherait sa défonctionnalisation.

Une approche différente du problème serait de considérer que chaque module peut définir son propre type de "fonctions défonctionnalisées" et répartiteur / gestionnaire. Les fonctions du module M1auraient du type M1.arrowet seraient appliquées en utilisant M1.apply, etc. Bien que cela fonctionne bien pour les utilisations de premier ordre des fonctions, je ne vois pas très bien comment vous pouvez l'étendre à une fonction d'ordre supérieur (qui ne devrait pas avoir à savoir d'où vient leur argument fonctionnel): si vous regroupez une fonction avec son répartiteur, vous rentrez dans le domaine des appels de fonction indirects.

Enfin, il y a dans le document que vous avez fait référence à une brève mention de l'approche globale par rapport à l'approche modulaire, mais je ne vois pas en quoi elle est liée à votre proposition. Ce qu'ils décrivent est exprimé en termes d '"extensions ouvertes" à la fois de fonctions et de types de données (fonctions et types qui pourraient être définis sur plusieurs modules indépendants). Il s'agit principalement d'une méthode ML pour décrire le fait que vous pouvez différer la combinaison d'analyse / transformations de modules indépendants au moment de la liaison, assouplissant la nécessité d'une transformation de programme entier.

gasche
la source