Les fermetures ============== Portée statique (lexicale): La valeur d'une variable est celle de son lieur englobant le plus proche *dans le texte source*. Exemple: let x = 1 let f z = x+z let g x = x + f 2 g 2 En portée statique: x vaut 1 dans f, même s'il vaut 2 dans g. Cf. la règle (beta) du lambda-calcul: (lambda x. a) b --> a{x <- b} (avec substitution correcte). Mais: en pratique, on ne travaille pas par substitution textuelle. Le code est immuable. Comment faire? Implémentation naïve (les systèmes Lisp classiques): - une case mémoire globale par nom de variable - quand on lie localement une variable: * on empile son ancienne valeur sur une pile * on écrit la nouvelle valeur dans la case mémoire associée * à la fin de la fonction (ou à la sortie du lieur): on poppe l'ancienne valeur et on la réécrit. Conséquence: quand on entre dans f depuis g, x vaut 2 et non pas 1. C'est ce qu'on appelle la portée dynamique. Implémentations de la portée statique: -------------------------------------- 1- Fonctions simples (à la C: pas d'emboîtement, les seules variables libres d'une fonction sont des variables globales) - pour les variables globales: des cases mémoires globales - pour les variables locales: chaque fonction s'alloue un bloc d'activation (stack frame) sur la pile, dans lequel elle stocke les valeurs de ses variables locales Passage et renvoi de fonctions: on passe le pointeur vers le code de la fonction. 2- Fonctions à la Pascal (emboîtement permis, mais on ne renvoie pas une fonction en résultat): let h x = let rec f n = if n < 0 then 1 else x * f(n-1) in f 10 Les fonctions locales à une autre fonction reçoivent en paramètre supplémentaire un pointeur vers le bloc d'activation de la fonction englobante. Via ce pointeur, elle accède aux variables ni locales ni globales. Ceci s'étend aux fonctions emboîtées à plusieurs niveaux: let h x = let g y = let f z = x+y+z in f 1 in g 2 Une solution est de chaîner entre eux les blocs d'activation des fonctions englobantes. Pour passer une fonction en argument: on passe son pointeur de code + son argument supplémentaire. let integrale f a b h = .... f x .... let f x = let g y = x*y in integrale g 0 1 0.01 Mais: pas possible de renvoyer une fonction en résultat (car le bloc d'activation du père va être déalloué): let f x = let g y = x*y in g 3- Variante: le lambda-lifting On ajoute des paramètres supplémentaires pour les variables libres. let h x = let rec f n = if n < 0 then 1 else x * f(n-1) in f 10 devient let rec f x n = if n < 0 then 1 else x * f x (n-1) let h x = f x 10 Mais problème pour passer les fonctions en argument ou en résultat: comment représenter les applications partielles? let g x y = x*y in let f x = integrale (g x) 0 1 0.01 4- Traitement des fonctions comme valeurs de première classe: - chaque fonction doit recevoir comme argument supplémentaire un environnement contenant les valeurs des variables libres dans la fonction; - une valeur fonctionnelle = un pointeur de code + un environnement; - en général: l'environnement ne suit pas une discipline de pile et doit être alloué dans le tas comme toute autre structure de donnée Un couple (pointeur de code, environnement) s'appelle une fermeture. let f x = ===> let g y = x*y in let code_g env y = env.var_x * y in integrale g 0 1 0.01 let val_g = fermeture(code_g, {var_x=x}) in integrale val_g 0 1 0.01 let integrale f a b h = .... f x .... ===> .... (code(f)) (env(f)) x .... Première apparition dans la littérature: P. J. Landin, "The mechanical evaluation of expressions", The Computer Journal, 1964. Transformation générale d'introduction des fermetures: [ e1 (e2) ] = let clos = e1 in (code(clos)) (env(clos)) (e2) [ fun x -> e ] = let code env x = e{v1 <- env.var_v1 ... vN <- env.var_vN} in fermeture(code, {var_v1 = v1; ...; var_vN = vN}) où {v1...vN} contient au moins toutes les variables libres de la fonction fun x -> e, et peut contenir davantage de variables. Remarque: la fonction "code" ci-dessus est close; sa valeur (dans l'expression fermeture(code, ...)) est donc juste un pointeur vers son code, comme en C. Remarque: autant les fonctions code() et env() doivent opérer uniformément sur toutes les fermetures, autant la représentation de l'environnement lui-même (position des variables, etc) n'est connue que du code de la fonction elle-même et du code qui construit la fermeture. En particulier, on peut choisir des représentations différentes de l'environnement pour chaque fonction. Stratégies de représentation des fermetures: -------------------------------------------- De manière générale, la structure de l'environnement est connue uniquement par le code de la fonction (pour les accès) et par le code qui construit la fermeture (pour la création) ==> beaucoup de flexibilité pour représenter l'environnement. En revanche, le pointeur de code doit être à une position fixe pour toutes les fermetures (appel inconnu). 1- Complètes (contient les valeurs de toutes les variables liées au moment de la création de la fermeture) ou minimale (contient juste les valeurs des variables vraiment libres dans la fonction fermée) ou intermédiaire. Exple: let f x y = let z = x*y in fun t -> t+z ------------ fermeture complète: contient x, y, z fermeture minimale: contient z seulement 2- Copiées (un seul bloc en mémoire contient les valeurs de toutes les variables libres) ou chaînées (plusieurs blocs de variables, chaînés) Exple: let f x y = let g u v = let h t = x+y+u+v+t in ... --------------- fermeture copiée: un bloc contenant x,y,u,v fermeture liée: un bloc contenant u,v, et un pointeur vers l'environnement de g, qui contient x,y 3- En deux blocs: un bloc (code, ptr env) et un bloc pour l'env: fermeture(code, {var_i = vi}) = (code, {var_i = vi}) code(f) = #1(f) env(f) = #2(f) ou en un bloc: un seul bloc avec le pointeur de code en champ 1 et les variables libres ensuite: fermeture(code, {var_i = vi}) = {c = code; var_i = vi} code(f) = #1(f) env(f) = f) Critères de choix: * Vitesse d'exécution: fermetures copiées: accès plus rapide, construction plus lente fermetures chaînées: accès lent, construction rapide * Occupation mémoire: si pas de partage entre fermetures, la solution la plus compacte est: fermetures minimales, copiées, en un bloc * Possibilités de partage: en deux blocs (si fonctions avec le même env) fermetures chaînées partageant la queue fermetures non minimales (pour avoir plus de possibilités de partage) * Pour éviter les fuites de mémoires: faire des fermetures minimales. Une fuite de mémoire, dans un langage muni d'un GC, se produit lorsqu'on garde un pointeur vers une structure de donnée qui n'est plus utilisée par la suite. Le pointeur en question peut être gardé dans la pile, ou dans une autre structure de donnée qui elle est vivante (utilisée par la suite). Dans les deux cas, la structure de donnée inutilisée reste accessible à partir des données utilisées, et le GC ne la libère donc pas. Exemple: let f l = let len = list_length l in fun x -> x+len let g = f (une tres longue liste) Si la fermeture de fun x -> x+len n'est pas minimale, elle va contenir la valeur de l, c'est-à-dire un pointeur vers la très longue liste. Cette fermeture reste accessible puisqu'elle est liée à l'identificateur global g. Donc, la très longue liste ne sera pas désallouée, même si le programme ne s'en sert pas par la suite. Si la fermeture de fun x -> x+len est minimale, elle contient uniquement len, et donc la très longue liste devient inaccessible et désallouable dès que la fonction f retourne. La tendance actuelle (SML/NJ, Objective Caml, la plupart des compilateurs Scheme): - fermetures copiées; - minimales; - en un bloc. Avec éventuellement des astuces supplémentaires pour le partage. Fonctions récursives et mutuellement récursives: ----------------------------------------------- let rec norm t = match t with Var v -> ... | Term(c, l) -> Term(c, map norm l) and norm_aux x = ... norm ... la fonction récursive doit pouvoir retrouver sa fermeture (et celle des autres fonctions mutuellement récursives avec elle) à partir de son environnement. Autrement dit: la fonction récursive et les autres fonctions mutuellement récursives avec elle sont (moralement) libres dans la fonction elle-même. Solutions: 1- Reconstruire la fermeture à partir de l'environnement et des pointeurs de code let rec code_norm env t = match t with Var v -> ... | Term(c, l) -> Term(c, map (fermeture(code_norm, env)) l) and code_norm_aux env x = ... (fermeture(code_norm, env)) ... Rque: les fonctions mutuellement recursives doivent avoir le même environnement dans leurs fermetures (l'union des variables libres de chaque fonction); c'est non minimal, mais ça n'introduit pas de fuite de mémoire. Très coûteux si fermetures en un bloc; encore trop coûteux si fermetures en deux blocs. 2- Mettre les fermetures dans les environnements (i.e. les traiter vraiment comme des variables libres) ==> cycles. let rec code_norm env t = match t with Var v -> ... | Term(c, l) -> Term(c, map env.norm l) and code_norm_aux env x = ... env.norm ... in let norm = fermeture(code_norm, {norm=nil; norm_aux=nil; v1=v1; v2=v2}) in let norm_aux = fermeture(code_norm_aux, {norm=nil; v3=v3}) in env(norm).norm <- norm; env(norm).norm_aux <- norm_aux; env(norm_aux).norm <- norm; ... La construction du cycle peut coûter cher (surtout avec un GC à générations). 3- Si fermetures en un bloc et pas de récursion mutuelle: le paramètre env est la fermeture de la fonction elle-même! let rec code_norm env t = match t with Var v -> ... | Term(c, l) -> Term(c, map env l) in (* env = norm *) let norm = fermeture(code_norm, {v1=v1, v2=v2}) in ... Efficacité maximale. Pour étendre ça aux fonctions mutuellement récursives: l'astuce d'Andrew Appel ("Compiling with continuations", Cambridge University Press, pages 107-108). On construit une fermeture en 1 bloc commune à plusieurs fonctions. Ce bloc contient un pointeur de code pour chaque fonction. La valeur de chaque fonction est un pointeur vers le champ du bloc qui contient son propre code (pointeurs infixes). let rec code_norm env t = match t with Var v -> ... | Term(c, l) -> Term(c, map env l) and code_norm_aux env x = ... (offset env -1) ... in let norm = fermeture(code_norm, code_norm_aux, v1, v2, v3) in let norm_aux = offset norm +1 in ... Efficace aussi bien à l'accès qu'à la construction. Complique le GC à cause des pointeurs infixes. Fusion et déplacement des fermetures: ------------------------------------- Lorsque plusieurs fonctions définies au même endroit ont le même ensemble de variables libres, elles peuvent partager une fermeture: let f x = e1 in ---> let rec f x = e1 and g y = e2 in let g y = e2 in ... ... Si pas exactement les mêmes variables libres: attention aux fuites! let l = une tres grande liste in let f x = x + list_length l in let g y = y + 1 in ... (seule g survit longtemps) ... Pour augmenter les opportunités de fusion: déplacement des constructions de fermetures. (On suppose qu'elles sont toutes nommées par un let.) - vers le bas: retarde la création des fermetures; utile si ça lui fait franchir une conditionnelle let f x = e in if cond then e1 else e2 [f pas libre ds e2] ---> if cond then let f x = e in e1 else e2 Transformation sûre: n'augmente jamais le coût d'exécution du programme. - vers le haut: factorise des invariants de fonctions récursives let rec f x = ... map (fun x -> x + 1) l ... devient let rec f x = ... map g l ... and g x = x + 1 Transformation sûre si la fonction déplacée vers le haut s'est fondue dans un autre let rec. Sinon, ça peut coûter plus cher. Autres codages des fonctions comme valeurs de première classe: -------------------------------------------------------------- 1- Si le langage cible ne permet pas de manipuler de pointeurs vers le code d'une fonction (p.ex. Ada): On associe à chaque fonction un numéro unique. Dans les fermetures, on stocke ce numéro à la place du pointeur vers le code de la fonction. Pour l'application, on passe par une fonction "apply" de la forme suivante: let apply ferm arg = match code(ferm) with Numéro_f -> f (env(ferm)) arg | Numéro_g -> g (env(ferm)) arg | ... (Un cas pour chaque fonction définie dans le programme.) 2- Si le langage cible a des objets et des classes (p.ex. C++, Java): À chaque fonction let f x = e on associe une classe (en C++): class fermeture_f { private: int v1, ..., vN; /* une variable d'instance pour chaque variable libre de fun x -> e */ public: /* Le constructeur de la classe prend en argument les valeurs des variables libres */ fermeture_f(int val_v1, ..., int val_vN) { v1 = val_v1; ...; vN = val_vN; } /* La methode "apply" calcule la valeur de [e]. Les occurrences de v1...vN dans e font référence aux valeurs des variables d'instance */ int apply(int x) { return [e]; } } La construction de la fermeture pour v1 = x1 ... vN = xN s'obtient par fermeture_f c = new fermeture_c (x1, ..., xN); et l'application à y par res = c->apply(y); Des fermetures aux objets: -------------------------- Un objet = des variables d'instances + des méthodes. Lorsqu'on appelle une méthode d'un objet, elle s'exécute dans le contexte des variables d'instance de cet objet: class point x_init = val mutable x = x_init method get_x = x method move d = x <- x + d end let p = new point 0 let q = new point 1 p#move 3 modifie la variable x de p p#get_x renvoie 3 q#get_x renvoie 1 (variable x de q non modifiée) Ceci s'obtient par la sémantique d'auto-application (self-application semantics): le code des méthodes prend l'objet lui-même en paramètre supplémentaire. [ obj#meth arg ] = (code(obj, meth)) obj arg code(obj, meth) est une primitive qui renvoie le pointeur de code associé à la méthode meth dans l'objet obj. De manière générale, on ne sait pas statiquement quel code implémente une méthode d'un objet. En Objective Caml, on peut faire obj#meth sur n'importe quel objet possédant au moins une méthode nommée meth et ayant le bon type, quel que soit la classe de laquelle obj provient. Même dans des langages à classes plus stricts (C++, Java), la présence de méthodes virtuelles avec héritage et sous-typage fait que la classe effective à laquelle appartient un objet (et qui détermine le code de ses méthodes) n'est pas déterminable à la compilation. Comparaison avec les fermetures: fermetures objets argument supplémentaire l'environnement l'objet qui contient la valeur des variables libres variables d'instance et aussi 1 pointeur de code N pointeurs de code en position fixe indexés par le nom des méthodes Principale différence: il n'y a qu'une action possible sur une fermeture, qui est de l'appliquer, d'où un seul pointeur vers du code, stocké en position fixe dans la fermeture. En revanche, pour un objet, il y a plusieurs actions possibles, une par méthode de sa classe. Remarque: le code des méthodes est le même pour tous les objets d'une même classe. Donc on regroupe tous les pointeurs vers les méthodes d'une classe dans une table (appelée ``method suite'' ou encore ``V-table'' en C++), et tous les objets de cette classe contiennent juste un pointeur vers la table de méthodes. Représentation de la table de méthodes et implémentation de l'opération code(obj, meth): Dans le cas général: - on numérote toutes les méthodes du programme de manière unique (au linking) - une table de méthodes = un tableau de pointeurs de code indexé par le numéro de la méthode - on prend code(obj, meth) = (method_suite(obj)).(num_meth) où num_meth est le numéro de la méthode meth Coût de l'appel de méthode: 2 indirections + 1 saut indirect (à comparer à 1 indirection + 1 saut pour l'appel de fonction). Problème de la taille des table de méthodes: si beaucoup de classes dans le système, on peut avoir beaucoup de méthodes mais peu de méthodes pour chaque classe -> la table de méthodes est un tableau creux. Solutions classiques pour compacter les tableaux creux: - Les couper en sous-tableaux de tailles fixe (Objective C) code(obj, meth) = (method_suite(obj)).(num_meth / 32).(num_meth mod 32) Surcoût: une indirection supplémentaire. - Recouvrir plusieurs tableaux creux (de manière à ce que les "pleins" d'un tableau tombent dans les "creux" des autres) (cf. Aho Sethi Ullman, "Compilers - Principles, Techniques and Tools", section 3.9) Pas de surcoût. Certaines restrictions du langage orienté-objet permettent des implémentations plus efficaces: - héritage simple uniquement (Modula-3) - héritage multiple mais pas de classes abstraites (C++) Cf. Ellis-Stroustrup, "The annotated C++ reference manual".