Notion d'environnement

Nous voudrions évaluer les expressions booléennes simples ayant des variables. Mais pour ce faire, il faut associer une valeur à chaque variable. Autrement dit, le problème est d'évaluer une expression booléenne bien formée dans un environnement qui est représenté par une liste d'associations (clef valeur). Par exemple,
env:

`a`	->	`@v`
`b`	->	`@f`

si, dans env, la valeur de a est @v et la valeur de b est @f:

(ebs-eval '((@non a) @et (b @ou (@v @et a))) env)

-> @f

Spécification de ebs-eval

;;; ebs-eval : ExprBoolSimple * Environnement -> Booleen ;;; (ebs-eval exp env) rend la valeur de vérité de l'expression exp dans ;;; l'environnement env

Création d'un environnement
Il faut que l'on puisse créer un environnement qui associe à chaque variable une valeur. Pour ce faire, nous pourrions définir une fonction qui aurait comme donnée une liste d'associations variable --- valeur et qui créerait l'environnement voulu. Mais, la plupart du temps, lorsqu'on travaille sous un environnement, au départ, on ne part pas de zéro, mais, au contraire, dans un environnement initial. Aussi, pour créer des environnements, préfère-t-on avoir deux fonctions: la première -- env-initial -- rend l'environnement initial et la seconde -- env-ajouts -- permet de rajouter des associations variable --- valeur. Ainsi, l'exemple précédent s'écrira:

(let((env (env-ajouts (list (list 'a (vrai)) (list 'b (faux))) (env-initial)))) (ebs-eval '((@non a) @et (b @ou (@v @et a))) env))

Implantation de ebs-eval
La définition de la fonction ebs-eval suit toujours le même schéma. Nous ne le détaillons pas :

(define (ebs-eval exp env) (cond ((ebs-atomique? exp) (ebs-eval-atomique exp env)) ((ebs-unaire? exp) (ebs-eval-unaire exp env)) ((ebs-binaire? exp) (ebs-eval-binaire exp env)) (else (erreur 'ebs-eval "expression mal formée"))))

Les fonctions non, et et ou sont des fonctions de la barrière d'interprétation que nous avons déjà utilisées pour évaluer une expression constante. Reste la fonction atomique-val qui doit avoir comme spécification:

;;; ebs-eval-atomique : Atomique * Environnement -> Booleen ;;; (ebs-eval-atomique exp env) rend la valeur de vérité de l'expression ;;; atomique exp dans l'environnement env

Première implantation de ebs-eval-atomique
Il suffit, une fois de plus, de suivre la grammaire: une expression atomique est une constante ou une variable:

;;; ebs-eval-atomique : Atomique * Environnement -> Booleen ;;; (ebs-eval-atomique exp env) rend la valeur de vérité de l'expression ;;; atomique exp dans l'environnement env (define (ebs-eval-atomique exp env) (if (ebs-constante? exp) (if (ebs-constante-vrai? exp) (vrai) (faux)) (env-variable-val exp env)))

pour une constante, c'est soit la constante vraie, soit la constante faux et il suffit d'utiliser les fonctions (de la barrière d'interprétation) vrai et faux,
pour une variable, nous rajoutons, dans la barrière d'abstraction des environnements, la fonction env-variable-val de spécification:

;;; env-variable-val : Variable * Environnement[Variable Domaine] -> Domaine ;;; ERREUR lorsque exp n'est pas définie dans l'environnement ;;; (env-variable-val exp env) rend la valeur de exp dans l'environnement env

Barrière d'abstraction des environnements

Rappelons les différentes fonctions que nous avons utilisées sur les environnements en remarquant que l'environnement initial est vide:

;;; env-initial : -> Environnement[Variable Domaine] ;;; (env-initial) rend l'environnement vide. ;;; env-ajouts : LISTE[N-UPLET[Variable Domaine]] * Environnement[Variable Domaine] ;;; -> Environnement[Variable Domaine] ;;; (env-ajouts L env) rend l'environnement obtenu en étendant ;;; l'environnement env en associant à chaque variable de la liste ;;; d'associations L, la valeur correspondante. ;;; env-variable-val : Variable * Environnement[Variable Domaine] -> Domaine ;;; ERREUR lorsque exp n'est pas définie dans l'environnement ;;; (env-variable-val exp env) rend la valeur de exp dans l'environnement env

Implantation de la barrière d'abstraction des environnements

Nous n'étudierons pas l'implantation qui est facile (en fait, nous avons déjà vu de telles implantations lorsque nous avons étudié les listes d'associations); elle vous est donnée en annexe.

Seconde implantation de ebs-eval-atomique
En fait, il s'agit plutôt d'une seconde vision de l'environnement: au lieu de tester si l'expression atomique est une constante ou une variable, on peut mettre la valeur des constantes dans l'environnement initial et le calcul de ebs-eval-atomique est alors tout simplement le calcul de env-variable-val de la solution précédente. Ainsi, la fonction ebs-eval-atomique n'existe plus et la fonction ebs-eval-atomique, renommée env-atomique-val, est une fonction de la barrière d'abstraction des environnements.

Barrière d'abstraction des environnements

La barrière d'abstraction des environnements est donc:

;;; env-initial : -> Environnement[Symbole Booleen] ;;; (env-initial) rend l'environnement associant aux deux constantes ;;; booléennes leurs valeurs dans Booleen ;;; env-ajouts : LISTE[N-UPLET[Variable Domaine]] * Environnement[Symbole Domaine] ;;; -> Environnement[Symbole Domaine] ;;; (env-ajouts L env) rend l'environnement obtenu en étendant ;;; l'environnement env en associant à chaque variable de la liste ;;; d'associations L, la valeur correspondante. ;;; env-atomique-val : Symbole * Environnement[Symbole Domaine] -> Domaine ;;; ERREUR lorsque exp n'est pas définie dans l'environnement ;;; (env-atomique-val exp env) rend la valeur de exp dans l'environnement env

Implantation de la barrière d'abstraction des environnements

Là encore, l'implantation est facile et elle vous est donnée dans l'annexe.

Différence sémantique entre ces deux visions
Considérons l'environnement env défini comme suit:

(env-ajouts (list (list '@v (faux))) (env-initial))

Quelle est la valeur retournée, dans les deux implantations précédentes, lorsque l'on évalue l'expression réduite à la constante @v dans cet environnement?

Première vision (environnement initial vide)

(let ((env (env-ajouts (list (list '@v (faux))) (env-initial)))) (ebs-eval '@v env))

-> @v

Seconde vision (valeurs constantes dans environnement initial)

(let ((env (env-ajouts (list (list '@v (faux))) (env-initial)))) (ebs-eval '@v env))

-> @f

Constante --- variable prédéfinie

En fait, dans la première vision, @v et @f sont des constantes (leur valeur ne change jamais) alors que dans la seconde vision, @v et @f sont traités comme des variables sauf que, dès le départ, elles ont une valeur: on dit que ce sont des variables prédéfinies.

Ces notions de constantes et de variables prédéfinies se retrouvent dans tous les langages (sous des noms différents, en particulier avec la notion de mot-clef qui correspond à nos constantes. Par exemple, en Scheme, on peut utiliser n'importe quel symbole comme nom de fonction, sauf and, or, define... Ainsi, on peut redéfinir + (qui est bien sûr prédéfini), mais on ne peut pas redéfinir and.