TD Compilation numéro 1
L'objectif de ces exercices est d'appliquer les schémas
d'évaluation et de compilation sur des objectifs simples.
- Calculette
Définir la fonction calcul qui prend une expression
arithmétique
en paramètre et l'évalue.
L'expression ne doit contenir que des nombres et des opérateurs
arithmétiques usuels.
On commencera en ne traitant que des opérateurs binaires.
- faire une version qui prend en compte spécifiquement
chaque
opérateur
;
- faire une version qui traite génériquement
chaque
opérateur
;
- généraliser au cas de l'évaluation de
n'importe
quelle
expression Lisp qui n'utilise que des fonctions globales nommées
et des constantes de n'importe quel type.
- Traiter le cas de quote.
- Généraliser
à
des opérateurs d'arité quelconque.
- en intégrant l'arité quelconque au code de la
fonction ;
- en transformant préalablement la donnée pour
binariser tous les opérateurs d'arité > 2. (transformation source-à-source).
- Interprétation d'automates
- on commencera par définir de façon abstraite
(ADT) une
structure
de données automate et l'interface fonctionnelle
correspondant ;
dans un deuxième temps on définira une
implémentation
particulière (à base de listes pour simplifier), on
définira les fonctions de l'interface, que l'on pourra remplacer
ultérieurement par des macros.
- définir la fonction eval-auto, qui prend en
argument un
automate
et un mot et retourne vrai/faux suivant que l'automate reconnaît
le mot
ou pas.
on fera d'abord une version pour des automates déterministes,
avant d'en faire une pour les automates indéterministes.
- Compilation d'automates
Écrire la fonction compile-auto, qui prend en argument
un
automate et retourne une fonction d'interprétation de mot, qui
prend en
argument un mot et retourne vrai/faux suivant que l'automate
reconnaît
le mot ou pas. L'invariant suivant doit être
vérifié :
(eval-auto auto mot) = (apply (compile-auto auto) mot ())
- on commencera par définir à la main la fonction
d'interprétation correspondant à un automate donné
;
- dans un second temps, on définit la fonction compile-auto
qui
génère la fonction d'interprétation de n'importe
quel
automate ;
Une des façons de faire consiste à faire de chaque
état
de l'automate une fonction locale.
- on peut enfin transformer cette fonction compile-auto
en une macro def-compile-auto.
Voir le poly de compilation pour plus de détails.
- Tester backquote
Voir le poly de LISP pour plus de détails.
Pour comprendre ce que fait backquote, il est
intéressant
d'analyser la valeur de `(toto , titi truc ,@tata tutu) ou de
toute
autre expression backquotée.
Pour cela, on peut regarder '`(toto , titi truc ,@tata tutu) : comme
print
restitue la forme bacquotée d'origine, on analysera la valeur en
en prenant les car et cdr successifs.
Essayez avec macroexpand.
Expliquer.
- Implémenter backquote
L'objectif est de définir le fonctionnement du
caractère backquote
en définissant une fonction backquotify qui transforme
l'expression
backquotée en une expression de construction de liste.
Pour cela, il faut d'abord supposer que ",x" est lu (fonction read)
comme la liste (unquote x), de la même manière que
"'x" est lu (quote x). Idem pour ",@x" qui est lu
(splice-unquote
x).
On procède par étapes
- dans un premier temps, on définit backquotify
pour qu'il
transforme l'expression `(e1 e2 .. en) en (list 'e1 ... 'en)
;
- on traite ensuite le cas où des ei sont de la
forme (unquote
fi) de telle sorte que l'expression produite comporte alors fi
à la place de 'ei ;
- on généralise alors à un arbre : la
récursion
ne se fait pas seulement sur le cdr mais aussi sur le car
;
- on traite ensuite le cas des (splice-unquote x) :
attention, il
faut alors faire une récursion de la cellule "du dessus"
(rare
contre-exemple à la règle consistant à ne tester
dans
une récursion que la cellule courante) ;
- on finit par la définition d'une fonction de
simplification qui
fait l'inverse de l'étape 1 en reconstruisant des constantes et
qui simplifie les appels imbriqués (append, cons
et list*
ou list, etc.)
On peut alors vérifier, que ça marche :
(bacquotify '((lambda ((unquote (caar args))) (splice-unquote
body))
(unquote (cadar args))))
doit retourner quelque-chose comme :
(list (list* 'lambda (list (caar args)) body) (cadar args))
On peut même comparer ce que votre version produit avec le
résultat de la version du système, que la question
précédente permet d'obtenir.