Alternatives à la défonctionnalisation

La défonctionnalisation est une transformation décrite pour la première fois en 1972 par John C. Reynolds pour éliminer les fonctions d'ordre supérieur. Existe-t-il des transformations alternatives (plus efficaces?) Pour éliminer les fonctions d'ordre supérieur?

Il existe trois approches principales (à ma connaissance) pour implémenter des fonctions d'ordre supérieur. Défonctionnalisation, conversion de fermeture / levage lambda et combinateurs.

Write Let pour le type d'une fonction d'ordre supérieur de à et pour le type de pointeurs de fonction de style C de à . (Si nous voulions formaliser cela, nous pourrions dire que l'abstraction du pointeur de fonction n'est autorisée que dans l'environnement vide.)$A \Rightarrow B$$A$$B$$A \to B$$A$$B$

La conversion de fermeture est l'idée que nous choisissons la représentation Le sera généralement le tuple contenant les valeurs des variables libres sur le site de lambda abstraction. Il pourrait cependant s'agir d'une autre représentation.

$$A \Rightarrow B \equiv \exists E.(E, (E, A) \to B)$$ $E$

Le levage lambda adopte une approche quelque peu différente et plus globale où une abstraction lambda est tirée vers l'extérieur pour contenir des étendues en ajoutant des variables libres comme paramètres en cours de route, jusqu'à ce qu'elle atteigne la portée de niveau supérieur. Bien que cela concerne la structuration des blocs, pour gérer réellement les utilisations de fonctions d'ordre supérieur, il faut autoriser une application partielle. Vous pouvez ensuite contourner les fonctions partiellement appliquées, mais il s'agit essentiellement de la même représentation que la conversion de fermeture.

Si vous vouliez éliminer les pointeurs de fonction, nous pouvons utiliser la défonctionnalisation, qui, dans ce cas particulier, produit simplement une énumération. Il n'y a cependant aucune raison de le faire, car les pointeurs de fonction sont des constructions naturelles dans la plupart des langages d'assemblage.

La prochaine approche consiste à utiliser des combinateurs. C'est fondamentalement la même chose que le levage lambda et l'utilisation d'applications partielles, sauf qu'un ensemble fixe de fonctions de niveau supérieur est utilisé, et toutes les autres fonctions sont exprimées sous forme de combinaisons de celles-ci. (S'ils ne disposent pas d'un ensemble fixe prédéfini de combinateurs, il s'agit généralement d'une approche basée sur le levage lambda comme je l'ai décrit ci-dessus.) Une fonction d'ordre supérieur serait alors efficacement représentée par une valeur dans un type de données utilisant la syntaxe Haskell comme ce qui suit (en utilisant des SKcombinateurs ):

data CA = S | K | App CA CA -- plus other things in reality, like primitive values

Une représentation plus proche du calcul de la colonne vertébrale a probablement plus de sens pour l'efficacité. Ou vous pourriez faire quelque chose comme:

data CA = S0 | S1 CA | S2 CA CA | K0 | K1 CA  

L'application d'une fonction d'ordre supérieur se divise en deux cas: soit un combinateur a été entièrement appliqué et doit donc être exécuté, soit nous renvoyons une nouvelle valeur qui représente l'application (partielle).

Je n'ai pas fait d'enquête exhaustive, mais je suis assez confiant que les variations sur la conversion de fermeture sont de loin la stratégie de mise en œuvre la plus courante pour les fonctions d'ordre supérieur (d'où elles sont souvent appelées "fermetures"). Il a les belles propriétés d'être modulaire, simple et raisonnablement efficace, même dans sa forme la plus naïve. Il faut un bon choix de combinateurs de base et un peu d'intelligence pour que les approches basées sur les combinateurs fonctionnent bien. La défonctionnalisation n'est tout simplement pas largement utilisée pour autant que je sache, mais il y a peu de raisons de ne pas profiter des pointeurs de fonction. Dans la mesure où vous le faites, par exemple, au lieu d'une analyse de cas volumineux, vous disposez d'un tableau de pointeurs de fonction dans lequel vous indexez, vous avez essentiellement recréé la conversion de fermeture.

Il existe d'autres approches. L'une est l'instanciation de modèle qui consiste essentiellement à prendre réduction de littéralement, et simplement à remplacer littéralement les termes par d'autres termes. Habituellement, cela nécessite d'avoir et de manipuler une structure arborescente à syntaxe abstraite. Les fonctions d'ordre supérieur sont alors représentées par leurs termes lambda (syntaxiques) ou leurs "modèles" qui peuvent simplifier l'exécution des substitutions.$\beta$