Implantation de la fonction deug-eval  
Comme dans le cas des expressions booléennes, on évalue une expression dans un environnement où des variables (nommant des fonctions ou des données) sont liées à leurs valeurs.
 
Lorsque vous avez écrit des programmes Scheme en TP, vous avez utilisé des fonctions comme +, -, car... Vous étiez donc dans un certain environnement, l'environnement initial.
 
Ainsi la définition de deug-eval est:  

229	;;; deug-eval: Deug-Programme -> Valeur  ;;; (deug-eval p) rend la valeur du programme (de Deug-Scheme) «p».  (define (deug-eval p)   (evaluation p (env-initial) ) )

 
avec:  

234	;;; evaluation: Expression * Environnement -> Valeur  ;;; (evaluation exp env) rend la valeur de l'expression «exp» dans   ;;; l'environnement «env».

624	;;; env-initial: -> Environnement   ;;; (env-initial) rend l'environnement initial, i.e. l'environnement qui  ;;; contient toutes les primitives.

 

 
Implantation de la fonction evaluation  
La définition de la fonction evaluation n'est qu'un aiguillage qui analyse la nature de l'expression à évaluer et appelle une fonction ad-hoc, avec comme arguments le contenu de la forme syntaxique (et non l'expression à analyser):  

237

(define (evaluation exp env)   ;; (discrimine l'expression et invoque l'évaluateur spécialisé)    (cond     ((variable? exp)       (variable-val exp env))    ((citation? exp)       (citation-val exp))    ((alternative? exp)    (alternative-eval                             (alternative-condition exp)                            (alternative-consequence exp)                            (alternative-alternant exp) env))    ((conditionnelle? exp) (conditionnelle-eval                             (conditionnelle-clauses exp) env))    ((sequence? exp)       (sequence-eval (sequence-exps exp) env))    ((bloc? exp)           (bloc-eval (bloc-liaisons exp)                                      (bloc-corps exp) env))    ((application? exp)    (application-eval                             (application-fonction exp)                            (application-arguments exp) env))    (else (deug-erreur 'evaluation "pas un programme" exp))) )

 

 
Ces différentes fonctions sont des évaluateurs spécialisés, dont nous étudions les définitions dans les paragraphes qui suivent, sauf

• la fonction variable-val qui devra être une des fonctions de la barrière des environnements,
• la fonction citation-val qui devra être une des fonctions de la barrière d'interprétation.

 
 
Implantation de la fonction alternative-eval  
La définition de cette fonction ne devrait pas vous poser de problème:  

256

;;; alternative-eval: Expression3 * Environnement -> Valeur  ;;; (alternative-eval condition consequence alternant env) rend la valeur de   ;;; l'expression «(if condition consequence alternant)» dans l'environnement «env».  (define (alternative-eval condition consequence alternant env)   (if (evaluation condition env)       (evaluation consequence env)       (evaluation alternant env)) )

 

 
Implantation de la fonction conditionnelle-eval  
Nous avons dit que la conditionnelle n'était pas essentielle (toute conditionnelle peut être réécrite avec des alternatives), mais que nous la mettions tout de même dans DEUG-Scheme car elle est très pratique (nous nous en sommes déjà servi dans la définition de evaluation).
 
Dans DEUG-Scheme, c'est la seule forme non essentielle. Les formes and et or ont été directement réécrites dans la définition de la fonction deug-eval plutôt que par programme (dans la première version de deug-eval, il y n'en y avait que quelques unes, dans les reconnaisseurs syntaxiques surtout).
 
En fait, dans les vrais évaluateurs, existe une phase dite de macro-expansion qui réduit le nombre de constructions qu'emploie un programme à celles qui sont vraiment essentielles et c'est ce que nous allons faire pour la conditionnelle:  

264

;;; LISTE[Clause] * Environnement -> Valeur  ;;; (conditionnelle-eval clauses env) rend la valeur, dans l'environnement «env»,   ;;; de l'expression «(cond c1 c2 ... cn)», «c1», «c2»... «cn» étant les éléments   ;;; de la liste «clauses».  (define (conditionnelle-eval clauses env)   (evaluation (conditionnelle-expansion clauses) env) )

 

 
la fonction conditionnelle-expansion ayant comme spécification:  

271	;;; conditionnelle-expansion: LISTE[Clause] -> Expression  ;;; (conditionnelle-expansion clauses) rend l'expression, écrite avec des  ;;; alternatives, équivalente à l'expression «(cond c1 c2 ... cn)»,   ;;; «c1», «c2»... «cn» étant les éléments de la liste «clauses».

 

 
Nous n'étudierons pas l'implantation de cette fonction car vous l'avez vue en TD.
 
Implantation de la fonction sequence-eval  

289

;;; sequence-eval: LISTE[Expression] * Environnement -> Valeur  ;;; (sequence-eval exps env) rend la valeur, dans l'environnement «env», de   ;;; l'expression «(begin e1 ... en)», «e1»... «en» étant les éléments de la liste  ;;; «exps».  ;;; (Il faut évaluer tour à tour les expressions et rendre la valeur de la  ;;; dernière d'entre elles.)

 

 
Tout d'abord notons qu'une séquence peut être vide (i.e. l'expression (begin) est correcte). La norme ne précise pas ce que l'on doit rendre dans ce cas; nous avons choisi de rendre #f.
 
Rappelons que pour évaluer (begin e1 e2 ... en), il faut évaluer tour à tour les expressions e1, e2... en et rendre la valeur de cette dernière. Ainsi la dernière expression doit être traitée de façon différente. Pour ce faire, pour l'efficacité, nous avons déjà vu sur d'autres exemples qu'il fallait définir une fonction interne, de même spécification que la fonction principale, mais dont la donnée est une liste non vide (et nous en profitons pour globaliser la varaible env):  

295

(define (sequence-eval exps env)   ;; sequence-eval+ : LISTE[Expression]/non vide/ -> Valeur    ;; même fonction, sachant que la liste "exps" n'est pas vide et en globalisant la variable "env".    (define (sequence-eval+ exps)     ... à faire     ... à faire     ... à faire     ... à faire                                    )   ;; expression de (sequence-eval exps env) :    (if (pair? exps)       (sequence-eval+ exps)       #f ) )

 

 
Pour implanter la fonction sequence-eval+, deux cas selon qu'il n'y a qu'une expression (c'est alors la dernière) ou plusieurs:  

295

(define (sequence-eval exps env)   ;; sequence-eval+ : LISTE[Expression]/non vide/ -> Valeur    ;; même fonction, sachant que la liste "exps" n'est pas vide et en globalisant la variable "env".    (define (sequence-eval+ exps)     (if (pair? (cdr exps))       ... à faire       ... à faire       ... à faire                                    )   ;; expression de (sequence-eval exps env) :    (if (pair? exps)       (sequence-eval+ exps)       #f ) )

 

 
s'il n'y en a qu'une, il suffit de l'évaluer (et de rendre sa valeur):  

295

(define (sequence-eval exps env)   ;; sequence-eval+ : LISTE[Expression]/non vide/ -> Valeur    ;; même fonction, sachant que la liste "exps" n'est pas vide et en globalisant la variable "env".    (define (sequence-eval+ exps)     (if (pair? (cdr exps))       ... à faire       ... à faire         (evaluation (car exps) env)))   ;; expression de (sequence-eval exps env) :    (if (pair? exps)       (sequence-eval+ exps)       #f ) )

 

 
s'il y en a plusieurs, on évalue la première sans se soucier de sa valeur puis on évalue la séquence des expressions qui restent (le tout à l'aide d'une séquence):  

295

(define (sequence-eval exps env)   ;; sequence-eval+ : LISTE[Expression]/non vide/ -> Valeur    ;; même fonction, sachant que la liste "exps" n'est pas vide et en globalisant la variable "env".    (define (sequence-eval+ exps)     (if (pair? (cdr exps))         (begin (evaluation (car exps) env)                (sequence-eval+ (cdr exps)) )         (evaluation (car exps) env)))   ;; expression de (sequence-eval exps env) :    (if (pair? exps)       (sequence-eval+ exps)       #f ) )

 

 
Implantation de la fonction application-eval  

309	;;; application-eval: Expression * LISTE[Expression] * Environnement -> Valeur  ;;; (application-eval exp-fn arguments env) rend la valeur de l'invocation de   ;;; l'expression «exp-fn» aux arguments «arguments» dans l'environnement «env».

 

 
Notons que exp-fn est une expression dont la valeur doit être fonctionnelle et que arguments est une liste d'expressions. Ainsi, on doit:

• évaluer la valeur de la fonction,
• évaluer les valeurs des arguments; ceux-ci sont représentés par une liste, on pense donc à un map (rappelons que nous avons nommé deug-map cette fonction), mais ce n'est pas aussi simple car la fonction evaluation a deux arguments, l'expression mais aussi l'environnement: comme nous l'avons déjà fait dans ce cas, nous définirons une fonction interne,
• appliquer (on parlera ici d'invocation) la valeur de la fonction aux valeurs des arguments.

 
De plus, nous voudrions vérifier que la valeur de l'expression exp-fn est bien une valeur fonctionnelle.
 
D'où la définition:  

312

(define (application-eval exp-fn arguments env)   ;; eval-env : Expression -> Valeur    ;; (eval-env exp) rend la valeur de «exp» dans l'environnement «env»    (define (eval-env exp)      (evaluation exp env))   ;; expression de (application-eval exp-fn arguments env) :    (let ((f (evaluation exp-fn env)))     (if (invocable? f)         (invocation f (deug-map eval-env arguments))         (deug-erreur 'application-eval                       "pas une fonction" f ) ) ) )

 

 
Les fonctions invocable? et invocation doivent faire partie de la barrière d'interprétation:
 
 

• (invocable? val) rendant vrai si, et seulement si, val est une fonction (primitive ou définie par le programmeur),
• (invocation f vals) rendant la valeur de l'application de f aux éléments de vals.

 
 
Implantation de la fonction bloc-eval  

324	;;; bloc-eval: LISTE[Liaison] * Corps * Environnement -> Valeur  ;;; (bloc-eval liaisons corps env) rend la valeur, dans l'environnement «env»,  ;;; de l'expression «(let liaisons corps)».

 

 
Rappelons la sémantique du let: nous devons évaluer le corps dans un environnement obtenu en ajoutant les liaisons à l'environnement courant. D'où la définition:
 

327	(define (bloc-eval liaisons corps env)   (corps-eval corps (env-add-liaisons liaisons env)) )

 

 
la fonction env-add-liaisons devant être une fonction de la barrière des environnements:  
 

 
(env-add-liaisons liaisons env) rendant l'environnement obtenu en ajoutant, à l'environnement env, les liaisons liaisons.
 
Implantation de la fonction corps-eval  

330	;;; corps-eval: Corps * Environnement -> Valeur  ;;; (corps-eval corps env) rend la valeur de «corps» dans l'environnement «env»

 

 
Tout d'abord des rappels:

• un corps est une suite de définitions et d'expressions,
  • les définitions sont toutes écrites avant les expressions,
  • il peut ne pas y avoir de définitions,
  • il y a obligatoirement une expression,
  • en fait les expressions constituent une séquence (implicite);
   
  
• pour évaluer un corps, on évalue la séquence du corps dans l'environnement obtenu en enrichissant l'environnement courant avec les définitions du corps.

 
D'où la définition:  

332	(define (corps-eval corps env)   (let ((def-exp (corps-separation-defs-exps corps)))     (let ((defs (car def-exp))           (exp (cadr def-exp)))       (evaluation exp (env-enrichissement env defs)) ) ) )

 

 
la fonction corps-separation-defs-exps permettant de séparer les définitions et les expressions présentes dans le corps. Plus précisément:  

338	;;; corps-separation-defs-exps: Corps -> (LISTE[Definition] * LISTE[Expression])  ;;; (corps-separation-defs-exps corps) rend une liste dont le premier élément est  ;;; la liste des definitions du corps «corps» et les autres éléments sont les   ;;; expressions de ce corps.

 

 
et la fonction env-enrichissement devant être une fonction de la barrière des environnements:  
Dans barrière des environnements:
 
 

 
(env-enrichissement env defs) rendant l'environnement env étendu avec un bloc d'activation pour les définitions fonctionnelles defs.
 
Implantation de la fonction corps-separation-defs-exps
 

338	;;; corps-separation-defs-exps: Corps -> (LISTE[Definition] * LISTE[Expression])  ;;; (corps-separation-defs-exps corps) rend une liste dont le premier élément est  ;;; la liste des definitions du corps «corps» et les autres éléments sont les   ;;; expressions de ce corps.

 

 
Noter bien le type du résultat de cette fonction: c'est une liste (hétérogène), le premier élément étant une liste de définitions et les autres éléments étant des expressions (les expressions du corps).
 
L'idée de la définition est simple:

• si le premier élément du corps est une définition, nous devons la rajouter dans la liste des définitions du corps privé de cette définition (d'où un appel récursif),
• si le premier élément n'est pas une définition, la liste des définitions est vide, liste vide que nous devons mettre devant la liste des expressions:

 
 

342	(define (corps-separation-defs-exps corps)   (if (definition? (car corps))       (let ((def-exp-cdr                (corps-separation-defs-exps (cdr corps))))         (cons (cons (car corps)                     (car def-exp-cdr))               (cdr def-exp-cdr)))       (cons '() corps) ) )

 

 
Et nous avons fini d'écrire l'évaluateur, il ne nous reste plus qu'à implanter la barrière d'interprétation et la barrière des environnements.