-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 01/06/2012 07:12 PM, Florian Lonqueu-Brochard wrote:
J'ai bien avanc=E9 sur le projet mais je bloque sur un point particulier : les environnements impl=E9ment=E9 comme des fonctions.
J'ai bien trouv=E9 ce code =E9crit en cours :
http://www-lipn.univ-paris13.fr/~saiu/teaching/PFA-2011/sources/cm4/environ= ment_as_function.ml
Je comprend bien le code de la page ci-dessus ainsi que le fait qu'un environnement est une function qui prend une variable et renvoi une valeur ( X -> C) mais je ne comprend pas la subtilit=E9 de cette implementation. Comment "stocke" t-on les diff=E9rents couples ?
Bonjour, et bonne année. Une question assez profonde, qui nécessite d'une réponse complexe. À mon avis votre problème est dû à la comparaison entre l'implémentation «liste» des environnements, et l'implémentation «fonction». Les deux implémentations sont en réalité plutôt différents, et il ne faut pas penser que en générale une fonction puisse stockers des couples de valeurs de la même façon d'une liste. L'explication du fonctionnement d'un «valeur-fonction» est doublement difficile à suivre, parce qu'elle dépende d'un environnement -- mais pas l'environnment que vous êtes en train de réaliser ! Il s'agit de l'environnment au niveau «méta», implémenté dans le compilateur ou l'interprète OCaml. Et cette implémentation méta est similaire, sinon identique, à cela que nous avons vu dans le cas de trivialML (papier sur trivialML, section 3). Pour prévenir cette confusion, au lieu de parler d'une fonction environnement, j'utilise l'exemple d'une fonction somme à deux paramètres, appliquée partiellement. let f x y = x + y;; (* pareil à let f = fun x -> fun y -> x + y *) let g = f 10;; Vous pouvez vérifier que maintenant l'appel (g 3) va donner le résultat 13, ce qui est le résultat raisonnable (10 + 3). Mais la valeur 10 est stockée où, dans g ? C'est exactement votre question, sur un exemple moins complex. La réponse est : l'association entre la variable x et la valeur 10 est retenue dans l'environnement qui est partie de la clôture (ou «fermeture» : «closure» en anglais) qui est partie de l'object fonction que nous avons nommé g. Je répète : en OCaml (ou en trivialML, en Scheme, ou dans n'importe quel langage fonctionnel moderne ayant scoping statique) une fonction est implémentée par une clôture, c'est-à-dire une triple qui contient le nom du paramètre, le corps de la fonction (ce qui est une expression) et l'environnement local qui contient les associations entre variables et valeurs, à utiliser au moment de l'appel. Donc dans notre exemple g est une fonction qui accepte un paramètre y et retourne x + y, dans un environnement local où x est liée à 10. Dans une bonne implémentation, par exemple OCaml (lorsque on utilise le compilateur natif), l'environnement sera réalisé de façon efficace et compacte, avec un tableau ; mais vous pouvez penser qu'il ait toujours une liste de couples <variable, valeur> : il n'y a aucune différence, sauf l'efficacité. Donc une fonction OCaml contient toujours un environnement. Dans notre implémentation d'un environnement par une fonction, nous utilisons ces liaisons contenues dans les clôtures «méta» (ou «natives» d'OCaml), pour stocker les liaisons des variables de l'interprète. J'explique alors environment_as_function.ml : empty représente l'environnement vide (zéro variables liées) : en fait la fonction empty accepte une variable en tant que paramètre, mais elle échoue toujours. extend_with_binding est probablement la fonction plus difficile à comprendre pour vous : regardez son type : il s'agit d'une fonction qui accepte une variable, une valeur et une autre fonction (en particulier, une autre fonction environnement), et enfin retourne encore une autre fonction environnement. Le résultat de extend_with_binding est défini comme une fonction qui accept le nom de variable «x» et qui (au temps de son appel) contrôle si «x» est égale au nom de variable «variable» donné au temps de l'extension : si oui, la fonction anonyme dans résultat de extend_with_binding va donner la valeur «value» donnée au temps de l'extension ; sinon, on va chercher x dans l'environnment «environment» donné au temps de l'extension. Autrement dit, la fonction retournée par extend_with_binding accepte une variable : si la variable est la variable à laquelle nous avons associé une valeur avec l'extension, le résultat sera quelle valeur ; sinon, on cherchera dans l'environnement que nous avons étendu. Et bien sûr, au niveau méta, lorsque vous appelez extend_with_binding avec trois paramètres vous créez une fermeture qui contient un environnement qui contient les valeurs des variables «variable», «value» et «environment» (mais pas de «x»: «x» est le paramètre, pas encore lié). Donc la réponse finale à votre question est ici : les associations entre variables et valeurs sont stockées dans les environnement des fermetures du niveau méta (il y en a une par association), attachées aux variables du niveau méta «variable» et «valeur». lookup est facile : elle accepte une variable et un environnement, et elle cherche la valeur associée à la variable dans l'environnement en appelant l'environnement avec la variable.
J'ai pu en discuter avec 2 de mes camarades (en copie de ce mail) et nous sommes tous les trois dans la m=EAme impasse. Pourriez-vous nous donner une piste ?
J'espère vous avoir aidé.
Merci d'avance.
Très cordialement, - -- Luca Saiu http://www-lipn.univ-paris13.fr/~saiu GNU epsilon: http://www.gnu.org/software/epsilon Marionnet: http://www.marionnet.org -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk8IS5IACgkQvzOavibF0oajqACfcje+rF0joJkGDqleC+g2+olu cUMAoIH0WPNsO56XHUfMZNLzqf0PiZIF =0/VW -----END PGP SIGNATURE-----