-----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-----
