Langage, Evaluation et Compilation
partiel janvier 2000
Corrigé partie 1 & 2
Question 1
1. Le comportement des 2 évaluateurs va différer dans 2 cas :
- en cas d'effet de bord dans l'évaluation des arguments : l'ordre de ces effets de bord n'est plus garanti ;
- en cas de non terminaison dans l'évaluation gloutonne d'un argument qui ne serait pas évalué par l'évaluateur paresseux. Le comportement est identique en cas de programmation purement fonctionnelle
qui termine.
NB il était question de "comportement", pas de complexité.
2. Les 2 évaluateurs correspondent à 2 stratégies différentes de réduction. Dans les "bons" cas de figure, ces 2 stratégies sont équivalentes.
Question 2
1. On peut spécifier ces environnements paresseux de plusieurs façons. La plus simple et la plus efficace me paraît celle-ci : une liste de liste (variable expression . environnement) pour les variables non évaluées ou (variable valeur . T) pour les variables déjà évaluées.
NB "enlever" l'environnement ne suffit pas, car il peut être NIL.
2. La fonction make-lazy-env ne pose pas de problèmes :
- on peut chercher à traiter à part le cas des constantes (mais ce n'est pas obligatoire, leur évaluation s'en chargera) : dans ce cas, il faut éviter de faire un test avec ATOM !!!
- on pourrait aussi chercher à traiter à part le cas des arguments réduits à une variable, pour faire des économies d'environnement...
- la fonction make-env du cours avait un argument d'environnement, celui que l'on construit : il en faut donc un second pour make-lazy-env, l'environnement dans lequel il faudra évaluer les paramètres.
3. La spécification de lazy-meval-symbol est claire : si le paramètre n'a pas encore été évalué, il faut l'évaluer (par lazy-meval) et modifier l'environnement en conséquence.
Question 3
Les modifications de meval sont les suivantes :
1- faire appel à lazy-meval partout, et non à meval ;
2- ne pas évaluer les arguments pour les lambda-expr et les fonctions "mdéfinies" (mais continuer à le faire dans les autres cas) ;
3- faire appel à lazy-meval-symbol pour les symboles ;
4- que faire pour SETF sur les variables ? on peut évaluer l'expression à affecter, dans ce cas pas de problème, ou repousser paresseusement l'évaluation : dans ce cas, danger en cas de circularité par exemple pour (setf x (1+ x)), si x n'est pas encore évalué. Le plus sage est donc de construire un nouvel environnement…
Question 4
L'automate reconnaissant le langage : (ab)*ba(a+b)* est :
((:voc a b) (:init 0) (:finals 3) (:trans (0 a 1 b 2) (1 b 0) (2 a 3) (3 a 3 b 3)))
Le code généré est donc :
0 LOA N1 1000
1 INC N1
2 BRA 3
3 DEC N1
4 LOA C1 N1
5 BEQ C1 A 8
6 BEQ C1 B 13
7 BEQ C1 NULL 25
8 DEC N1
9 LOA C1 N1
10 BEQ C1 A 25
11 BEQ C1 B 3
12 BEQ C1 NULL 25
13 DEC N1
14 LOA C1 N1
15 BEQ C1 A 18
16 BEQ C1 B 25
17 BEQ C1 NULL 25
18 DEC N1
19 LOA C1 N1
20 BEQ C1 A 18
21 BEQ C1 B 18
22 BEQ C1 NULL 23
23 LOA N1 1
24 BEA 26
25 LOA N1 0
26 STP
Question 5
Question 6
Question 7
Le code généré est bien long et il y a toujours une instruction par caractère pour chaque état et ceux indépendemment des transitions. Un saut inconditionnel équivalent au "else" serait le bienvenu.
On aurait pu faciliter la génération de code et le calcul des adresses en regroupant l'épilogue et le prologue. Comme par exemple :
0 LOA N1 1000
1 INC N1
2 BRA @ETAT-INIT
4 LOA N1 1
5 BEA 16
6 LOA N1 0
7 STP
…
Mathieu LAFOURCADE LIRMM - 161, rue Ada — 34392 Montpellier Cedex 5 - Bureau : 2.114 - Téléphone : 67 41 85 71 - Fax : 67 41 85 00. mathieu.lafourcade@lirmm.fr