Défonctionnalisation - Defunctionalization

Dans les langages de programmation , la défonctionnalisation est une transformation au moment de la compilation qui élimine les fonctions d'ordre supérieur , en les remplaçant par une seule fonction d' application de premier ordre . La technique a été décrite pour la première fois par John C. Reynolds dans son article de 1972, "Definitional Interpreters for Higher-Order Programming Languages". L'observation de Reynolds était qu'un programme donné ne contient qu'un nombre fini d'abstractions de fonctions, de sorte que chacune peut être affectée et remplacée par un identifiant unique. Chaque application de fonction dans le programme est ensuite remplacée par un appel à la fonction apply avec l'identifiant de fonction comme premier argument. Le seul travail de la fonction apply consiste à répartir sur ce premier argument, puis à exécuter les instructions indiquées par l'identifiant de la fonction sur les arguments restants.

Une complication de cette idée de base est que les abstractions de fonctions peuvent référencer des variables libres . Dans de telles situations, la défonctionnalisation doit être précédée d'une conversion de fermeture (levage lambda) , de sorte que toutes les variables libres d'une abstraction de fonction soient passées en tant qu'arguments supplémentaires à appliquer . De plus, si les fermetures sont prises en charge en tant que valeurs de première classe , il devient nécessaire de représenter ces liaisons capturées en créant des structures de données.

Au lieu d'avoir une seule répartition de fonction d' application sur toutes les abstractions de fonction dans un programme, divers types d' analyse de flux de contrôle (y compris des distinctions simples basées sur l' arité ou la signature de type ) peuvent être utilisés pour déterminer quelle(s) fonction(s) peuvent être appelées à chaque application de fonction site, et une fonction d' application spécialisée peut être référencée à la place. Alternativement, le langage cible peut prendre en charge les appels indirects via des pointeurs de fonction , ce qui peut être plus efficace et extensible qu'une approche basée sur la répartition.

Outre son utilisation comme technique de compilation de langages fonctionnels d' ordre supérieur , la défonctionnalisation a été étudiée (notamment par Olivier Danvy et ses collaborateurs) comme moyen de transformer mécaniquement les interpréteurs en machines abstraites . La défonctionnalisation est également liée à la technique issue de la programmation orientée objet de représentation des fonctions par des objets fonction (comme alternative aux fermetures).

Exemple

Voici un exemple donné par Olivier Danvy , traduit en Haskell :

Étant donné le type de données Tree : 

data Tree a = Leaf a
            | Node (Tree a) (Tree a)

Nous allons défonctionnaliser le programme suivant : 

cons :: a -> [a] -> [a]
cons x xs = x : xs

o :: (b -> c) -> (a -> b) -> a -> c
o f g x = f (g x)

flatten :: Tree t -> [t]
flatten t = walk t []

walk :: Tree t -> [t] -> [t]
walk (Leaf x)     = cons x
walk (Node t1 t2) = o (walk t1) (walk t2)

Nous défonctionnalisons en remplaçant toutes les fonctions d'ordre supérieur (dans ce cas, oc'est la seule fonction d'ordre supérieur) par une valeur du Lamtype de données, et au lieu de les appeler directement, nous introduisons une applyfonction qui interprète le type de données : 

data Lam a = LamCons a
           | LamO (Lam a) (Lam a)

apply :: Lam a -> [a] -> [a]
apply (LamCons x)  xs = x : xs
apply (LamO f1 f2) xs = apply f1 (apply f2 xs)

cons_def :: a -> Lam a
cons_def x  = LamCons x

o_def :: Lam a -> Lam a -> Lam a
o_def f1 f2 = LamO f1 f2

flatten_def :: Tree t -> [t]
flatten_def t = apply (walk_def t) []

walk_def :: Tree t -> Lam t
walk_def (Leaf x)     = cons_def x
walk_def (Node t1 t2) = o_def (walk_def t1) (walk_def t2)

Voir également

Les références

  • Reynolds, John (août 1972). "Les interprètes définis pour les langages de programmation d'ordre supérieur". Actes de la conférence annuelle de l'ACM . Boston, Massachusetts. p. 717-740. doi : 10.1145/800194.805852 .
  • Danvy, Olivier ; Nielsen, Lasse R. (2001). "Défonctionnalisation au travail" (PDF) . Actes de la conférence ACM SIGPLAN sur les principes et la pratique de la programmation déclarative . p. 162–174. doi : 10.1145/773184.773202 .(Version plus complète : Rapport technique BRICS-RS-01-23 )
  • Danvy, Olivier ; Millikin, Kevin R. (juin 2009). "La refonctionnalisation au travail" . Science de la programmation informatique . 74 (8) : 534-549. doi : 10.1016/j.scico.2007.10.007 .(Également disponible sous forme de rapport technique BRICS-RS-07-7 )

Liens externes