TD de LISP numéro 3 et 4

1. Paramètres optionnels et APPLY


• Définir les fonctions de recherche dans une liste telles que member, assoc, etc. avec un argument optionnel pour la fonction de comparaison à utiliser (mot-clé :test).
• Lire la description de ces fonctions dans le manuel en ligne et implémenter aussi les mot-clés :key et :from-the-end.
• Montrez comment éviter l'usage de :key en se servant de :test.
  
• Comment assurer un minimum d'efficacité à ces fonctions ?
  



---

2. fonctions d'arité variable et APPLY
• Définir les fonctions n-aires de manipulation de listes comme append, par une unique fonction récursive en utilisant apply.
• définir ces fonctions sans utiliser apply, à l'aide d'une fonction récursive locale définie par labels.
• idem pour la fonction list* telle que (list* 1 2 3 '(4 5 6)) retourne (1 2 3 4 5 6).
  
  

---

3. Fonctions destructives sur les listes

Définir les différentes fonctions sur les listes en mode destructif (ou modification physique) et non pas en mode copie comme on l'a vu jusqu'ici.

Fonctions concernées :

• nconc version destructive de append.
• delete version destructive de remove.
• nreverse version destructrice de reverse.
• nsubst version destructive de subst.
  
  

---

4. Fonctions de partage sur les listes

Entre la copie et la destruction, il y a le partage, qui consiste à ne rien détruire mais à ne recopier que le minimum.
Définir les fonctions subst et remove en mode partage, de telle sorte que la fonction retourne son argument dans le cas où aucune substitution n'est faite.
NB. la fonction ne doit effectuer qu'un unique parcours de l'arbre, comme pour les autres versions.

Une présentation élégante des 3 versions (copie, partage, destruction) de ces fonctions consiste à utiliser un schéma unique dans lequel on ne fait varier que la fonction de construction de liste : typiquement, dans les versions partage et destruction, on remplace l'usage de cons par celui d'une autre fonction, locale.



---

5. 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 généralisera ensuite à des opérateurs d'arité quelconque.
On commencera en ne traitant que des opérateurs binaires et
• 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.
  
  

---

6. Les macros
• reprendre l'exercice 1 de la feuille de TD 1 & 2 et tranformer les expressions lambda en let ou let* ;
  
• définir les macros let et let*  avec un nombre quelconque de variables ;
• définir les macros and et or ;
• définir les macros cond et case ;
Dans tous les cas, attention aux récursions, aux doubles évaluations et à la capture de variable.
On utilisera macroexpand pour vérifier la correction des expansions.



---

7. Tester backquote

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



---

8. 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
1. dans un premier temps, on définit backquotify pour qu'il transforme l'expression `(e1 e2 .. en) en (list 'e1 ... 'en) ;
2. 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 ;
3. on généralise alors à un arbre : la récursion ne se fait pas seulement sur le cdr mais aussi sur le car ;
4. 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) ;
5. 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.



---

9. Récursions terminales et continuations

Une continuation est une fermeture, c'est-à-dire une lambda-expression capturant l'environnement courant, passée en argument à une autre fonction qui appelle la continuation pour se continuer.
L'un des usages des continuations est de permettre la transformation de n'importe quelle récursion enveloppée en récursion terminale.
• Ecrire la fonction length en récursion terminale avec une continuation.
• appliquer le même principe pour d'autres fonctions : fact, copylist, etc.
• idem pour la fonction size qui est doublement récursive.

---