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.

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.)

(bacquotify '((lambda ((unquote (caar args))) (splice-unquote body)) (unquote (cadar args))))

(list (list* 'lambda (list (caar args)) body) (cadar args))