16. Interprétation d’un sous-ensemble de Scheme
1 Exercice 16.14.1
Dans la fonction install-software page 372, je rajoute modulo et ppdiv comme primitives MISS :
(install-def! '($define modulo ($lambda (p q) |
($if ($< p q) p (modulo ($- p q) q))))) |
(install-def! '($define ppdiv |
($lambda (n) |
($letrec ((iter ($lambda (d) |
($if ($> ($* d d) n) ; en l'absence de $cond ! |
n |
($if ($zero? (modulo n d)) |
d |
(iter ($+ d 2))))))) |
($if ($zero? (modulo n 2)) |
2 |
(iter 3)))))) |
> (miss) |
Miss Is (almost) a Subset of Scheme ! Type quit to quit. |
? (ppdiv 2003) |
--> 2003 |
? (ppdiv 2001) |
--> 3 |
? quit |
bye |
> |
2 Exercice 16.14.2 –> 16.14.7
Les solutions sont intégrées au module chap16-sol.rkt.
3 Exercice 16.14.8
Pas de pb, il s’agit d’augmenter la listes des primitives en utilisant celles de Racket.
4 Exercice 16.14.9
En liaison dynamique, il n’y a plus de fermetures a priori. La valeur d’une lambda-expression ne transporte pas le souvenir de son environnement de création. Cette valeur sera par exemple la lambda elle-même.
> ($define a 1) |
> ($define foo |
($let ((a 1000)) |
($lambda (n) ($+ n a)))) |
> foo |
($lambda (n) ($+ n a)) |
> (foo 3) |
4 |
> ($let ((a 10)) |
(foo 3)) |
13 |
Tout se passe essentiellement dans la fonction apply, qui prend maintenant l’environnement d’exécution en argument ! Voici les modifications à apporter au fichier chap16-sol.rkt :
(define (%eval expr env) |
(cond ((%constant? expr) expr) |
((symbol? expr) (%lookup expr env)) |
((%special? expr) (%eval-special expr env)) |
(else (%apply (%eval (car expr) env) |
(%evlis (cdr expr) env) |
env)))) ; <----- liaison dynamique ! |
|
(define (%eval-special expr env) |
(case (car expr) |
(($if) (%eval-if expr env)) |
(($lambda) expr) ; <----- la valeur d'une lambda est cette lambda ! |
(($let) (%eval-let expr env)) |
(($letrec) (%eval-letrec expr env)) |
(($begin) (%eval-begin (cdr expr) env)) |
(($set!) (%eval-set! expr env)) |
(($define) (%eval-define expr env)) |
(else (error "Forme speciale inconnue" (mcar expr))))) |
|
(define (%lambda? expr) ; <----- à la place de $closure? |
(and (pair? expr) (equal? (car expr) '$lambda))) |
|
(define (%apply proc Lvals env) ; env est l'environnement d'execution ! |
(cond ((%primitive? proc) ; si proc est une primitive hard, elle est traitee en interne sans environnement |
(%apply-internal proc Lvals)) |
((%lambda? proc) ; si proc est une lambda dynamique |
(%apply-lambda proc Lvals env)) |
(else (error '%apply "Bug : fonction impossible a appliquer : ~a" proc)))) |
|
(define (%apply-lambda proc Lvals env) |
(let ((Lparams (cadr proc)) ; la liste des paramètres |
(body (cons '$begin (cddr proc)))) ; l'expression formant le corps |
(%eval body (%extend-env Lparams Lvals env)))) ; <---- et on calcule dans l'env. d'exécution ! |
5 Exercice 16.14.10
Le source de l’interprète solution est dans le fichier exo_16_14_10.rkt, ou plutôt les deux car il y en a un en version statique et l’autre en version dynamique. En ce qui concerne la question b), on sait bien (livre exercice 6.8.5) effectuer un produit uniquement avec des additions et des soustractions. Seul problème, il faut une fonction récursive, et notre langage n’a ni define ni letrec. Qu’à cela ne tienne, il suffit que la fonction se connaisse elle-même, comme aurait dit Socrate :
? (with ((mul (function (x y f) (if0 x 0 (+ y (f (- x 1) y f)))))) |
(mul 2010 2020 mul)) |
= 4060200 ; en statique et en dynamique |
Je vous laisse le reste...