Introduction  
L'évaluation convertit un texte en une valeur. Ainsi, le coeur d'un interprète Scheme, celui de DrScheme par exemple, est:  
 

 
La fonction display permet d'imprimer une valeur quelconque:  
 

 
La fonction eval convertit une S-expression Scheme --- représentant un programme --- en sa valeur:  
 

 
La fonction read permet de lire une S-expression quelconque (symbole, nombre, liste, vecteur...). Elle convertit un flux de caractères (provenant d'un clavier, d'un fichier) en une S-expression Scheme:  
 

 
Insistons sur le rôle de cette fonction : il ne faut pas confondre le programme qui est une idée dans la tête du programmeur et ses diverses représentations. Pour un éditeur de texte, c'est une suite de caractères, pour le système d'exploitation un fichier, pour Scheme la valeur produite par read c'est-à-dire une S-expression, pour un débogueur des octets liés par des pointeurs. En conclusion, un programme est la description d'un calcul qui peut revêtir différentes représentations suivant les outils dont on dispose et, pour nous écrivain d'un interprète, c'est une S-expression qui nous est fournie par la fonction read.
 
Spécification de la fonction deug-eval  
Dans cette partie, nous voudrions (ré)écire la fonction eval de l'interprète sous la forme d'une fonction deug-eval qui a comme donnée une S-expression --- représentant un programme --- et qui retourne la valeur de cette S-expression. Ainsi:  
(deug-eval '(+ 2 3)) -> 5  

 
et la fonction deug-eval a comme spécification:  
 

 
Le langage Scheme que nous analyserons ne sera pas un Scheme complet, ceci pour quatre raisons:

• notre objectif est de voir (tous) les mécanismes fondamentaux et cela ne servirait à rien de traiter un certain nombre de constructions Scheme car elles se traitent comme d'autres constructions que nous avons traitées;
• nous avons vu en cours et en TD que des constructions de Scheme, très pratiques, ne sont pas indispensables car on peut les remplacer par d'autres (il en est ainsi du and, du or, du cond...). Lorsque l'on écrit un évaluateur, plus le langage est petit, moins on a de choses à faire.
• c'est ainsi que cela se passe dans la réalité: on commence par ne traiter qu'une partie du langage et, ensuite, on complète l'interpréteur ;
• et enfin, pour une raison technique: un programme Scheme -- tel qu'il est défini par la carte de référence -- est une suite de définitions et d'expressions, une définition ou une expression étant représentée par une S-expression. Ainsi un programme Scheme est constitué par un certain nombre de S-expressions et la fonction qui évalue un programme Scheme devrait avoir un nombre quelconque d'arguments. Comme nous ne savons pas faire, nous décidons que nos programmes seront réduit à une S-expression.

 
Cas des programmes « complets »  
La restriction précédente n'est pas une restriction fondamentale: si nous avons un programme P entier -- i.e. qui contient des définitions et des expressions --- à évaluer, il suffit de l'envelopper dans une forme (let () P) avant de le soumettre à la fonction deug-eval. Par exemple, si nous voulons faire évaluer le programme suivant (qui comporte une définition et une expression):  
 
 

 
nous écrirons:  
 
 

 
Auto-évaluation  
De plus en plus fort! deug-eval étant écrit en Scheme et évaluant un programme Scheme, on peut le faire évaluer par lui-même. Par exemple, le source de deug-eval étant dans la fenêtre de définition et étant compilé, la fenêtre d'interaction peut contenir:  

... ;;; deug-eval: Deug-Programme -> Valeur  ;;; (deug-eval p) rend la valeur du programme  ;;; (de Deug-Scheme) "p".  (define (deug-eval p) ...

le source de deug-eval

 
 
 

 
Le deug-eval de la première ligne est la fonction définie dans la fenêtre de définition (et est donc évalué par DrScheme) alors que le deug-eval de la dernière ligne est la fonction définie dans le source de deug-eval. Le second deug-eval est donc évalué par la définition interne de deug-eval qui est elle-même évaluée par le premier deug-eval. On parle d'auto-évaluation.
 
Remarque très importante: nous avons dit que nous ne traiterions pas toutes les constructions de Scheme. Mais, si l'on veut pouvoir faire de l'auto-évaluation, il faut que le langage utilisé pour écrire deug-eval soit inclus dans le langage que deug-eval évalue (en pratique, on s'est arrangé pour que ces deux langages soient égaux).
 
Remarque non moins importante: dans toute cette partie, nous utiliserons deux langages Scheme: celui de la carte de référence et le langage pour lequel nous écrivons un interprète. Systématiquement (ou tout du moins nous essaierons!), nous nommerons Scheme le langage de la carte de référence et DEUG-Scheme celui qu'évalue deug-eval. Lors de l'auto-évaluation, nous avons même trois langages Scheme:

• celui de DrScheme qui évalue le premier deug-eval,
• celui -- c'est un Deug-Scheme -- qui est évalué par le premier deug-eval (dans l'exemple précédent, tout ce qui est dans la boîte encadrée appartient à ce langage),
• et enfin -- c'est aussi un Deug-Scheme, mais pas le même que le précédent puisqu'il n'est pas évalué par la même fonction -- celui qui est évalué par le second deug-eval (dans l'exemple précédent, '(+ 2 3) appartient à ce langage).

 
et encore, rien ne nous interdit de faire de l'auto-auto-évaluation: on aurait alors quatre niveaux de langages.
 
Aussi nous parlerons de Scheme sous-jacent: le Scheme sous-jacent du Deug-Scheme évalué par le premier deug-eval est le Scheme de DrScheme et le Scheme sous-jacent du Deug-Scheme évalué par le second deug-eval est le Deug-Scheme évalué par le premier deug-eval.
 
Dernière remarque: l'auto-évaluation peut vous sembler un exercice de style. Il n'en est rien! ne serait-ce parce qu'elle est excellente pour tester l'évaluateur. En effet, son écriture utilisant toutes les constructions du langage, il les teste toutes, alors qu'il faudrait de nombreux tests « classiques » pour tout tester.
 
Grammaire de DEUG-Scheme  
Un programme est écrit dans un langage de programmation qui fixe les règles grammaticales que tous les programmes écrits dans ce langage doivent respecter. La syntaxe de bas niveau de Scheme est rudimentaire (des blancs, des parenthèses et des mots sans oublier quelques règles d'abréviations concernant l'apostrophe). La grammaire de Scheme comporte des formes spéciales, des applications fonctionnelles, des variables et des citations. Ce faisant on plaque une interprétation sur les S-expressions qui sont lues.
 
La grammaire du sous-ensemble de Scheme utilisé dans ce cours est indiqué en tête du listing donné en annexe (page ??).

• Comme déjà indiqué, un programme DEUG-Scheme est simplement une expression DEUG-Scheme (il n'y en a qu'une et il n'y a pas de définition au top-level).
• Il n'y a pas de and, de or et de let*, ces constructions n'étant pas essentielles.
• En revanche, nous avons conservé le cond, qui n'est pas essentiel non plus, mais qui est tellement pratique pour écrire les sources de deug-eval (et nous l'avons donc mis dans le langage en vue de l'auto-évaluation).

 
 
Structure générale du listing  
Tout d'abord, comme nous l'avons déjà dit, le listing contient (bien sûr sous forme de commentaires) la grammaire du langage utilisé:  

5	;;;; {{{ Grammaire du langage
32	;;;; }}} Grammaire du langage

 

 
On trouve ensuite le source proprement dit. Dans un premier temps, nous définissons des fonctions de service utiles pour écrire le programme:  

34	;;;; {{{ Utilitaires généraux
100	;;;; }}} Utilitaires généraux

 

 
Pour le programme proprement dit, comme pour les expressions booléennes que nous avons vues dans les cours précédents, nous écrirons une barrière syntaxique, une barrière d'interprétation et une barrière d'abstraction des environnements:
 
 

 
Il est facile de déterminer la barrière syntaxique (il suffit de regarder la grammaire), et nous le ferons tout de suite.
 
En revanche, pour la barrière d'évaluation et la barrière d'abstraction des environnements, il n'est pas aisé de trouver a priori les fonctions nécessaires, aussi nous reporterons cette étude plus tard.
 
Ainsi, nous donnerons d'abord la barrière syntaxique:  

102	;;;; {{{ Barrière-syntaxique
224	;;;; }}} Barrière-syntaxique

 

 
qui nous permettra d'écrire l'évaluateur (la fonction deug-eval):  

226	;;;; {{{ Evaluateur
350	;;;; }}} Evaluateur

 

 
au dessus d'une barrière d'interprétation:  

352	;;;; {{{ Barrière-interpretation
475	;;;; }}} Barrière-interpretation

 

 
et d'une barrière d'abstraction des environnements:  

477	;;;; {{{ Environnements-H (barrière de haut niveau)
677	;;;; }}} Environnements-H (barrière de haut niveau)

 

 
Enfin, nous avons écrit, bien sûr sous forme de commentaires, le mode d'emploi de notre logiciel:  

679	;;;; {{{ Mode d'emploi
697	;;;; }}} Mode d'emploi