Cette réponse utilise Common Lisp pour ses exemples, mais ce n'est pas fondamentalement différent en Scheme. Notez également que vous pouvez jouer avec sdraw.lisp en Common Lisp (par exemple avec des programmes CCL ou SBCL) si vous voulez voir comment l'impression du diagramme peut réellement être implémentée.
Vous devez d'abord être clair sur le résultat que vous voulez imprimer, ce qui peut être difficile lorsque la source contient des opérations de cons/list/append. De plus, étant donné que le code source est également un arbre de cellules cons, vous devez faire attention à ne pas mélanger la source avec la valeur obtenue après son évaluation. Tout commence donc par évaluer correctement la forme.
Évaluer cal
Commençons par évaluer l'expression. Ensuite, je mentionne également comment dessiner directement les boîtes à partir de l'expression d'entrée, mais à mon avis, il est utile de détailler cette étape intermédiaire. Le résultat est le même en Scheme et en Common Lisp, après avoir évalué récursivement toutes les expressions :
((((1 2) 3) (4 5)) 6 7)
Voici comment vous pourriez demander au système de tracer le calcul, en Common Lisp. Tout d'abord, sachez que vous ne pouvez pas tracer les fonctions standard comme list, etc. Alors, masquons-les dans un package personnalisé avec des wrappers simples :
(defpackage :so
(:use :cl)
(:shadow #:list #:cons #:append))
(in-package :so)
(defun list (&rest args) (apply #'cl:list args))
(defun cons (&rest args) (apply #'cl:cons args))
(defun append (&rest args) (apply #'cl:append args))
Ensuite, dans le REPL, allez dans ce package :
CL-USER> (in-package :so)
#
Demandez de tracer ces fonctions :
SO> (trace list append cons) ;; celles qui ont été masquées
(LIST CONS APPEND)
Maintenant, vous pouvez entrer la valeur de cal directement, mais cette fois les symboles utilisés sont ceux que nous avons demandé de tracer.
SO> (list (append (list (cons (list 1 2) (cons 3 '())))
(list (cons 4 (cons 5 '()))))
6
7)
L'environnement évalue ensuite la forme et affiche comment chaque fonction est appelée et quels sont les résultats qu'elle renvoie.
0: (SO::LIST 1 2)
0: LIST a renvoyé (1 2)
0: (SO::CONS 3 NIL)
0: CONS a renvoyé (3)
0: (SO::CONS (1 2) (3))
0: CONS a renvoyé ((1 2) 3)
0: (SO::LIST ((1 2) 3))
0: LIST a renvoyé (((1 2) 3))
0: (SO::CONS 5 NIL)
0: CONS a renvoyé (5)
0: (SO::CONS 4 (5))
0: CONS a renvoyé (4 5)
0: (SO::LIST (4 5))
0: LIST a renvoyé ((4 5))
0: (SO::APPEND (((1 2) 3)) ((4 5)))
0: APPEND a renvoyé (((1 2) 3) (4 5))
0: (SO::LIST (((1 2) 3) (4 5)) 6 7)
0: LIST a renvoyé ((((1 2) 3) (4 5)) 6 7)
((((1 2) 3) (4 5)) 6 7)
Visualiser en tant que cellules cons
Il peut être utile de voir les listes comme des chaînes de cellules cons, c'est-à-dire transformer (a b c) en (a . (b . (c . nil))). Définissons une fonction d'aide :
(defun consprint (x)
(if (consp x)
(format nil
"(~a . ~a)"
(consprint (car x))
(consprint (cdr x)))
(prin1-to-string x)))
Voici le résultat :
SO> (consprint '((((1 2) 3) (4 5)) 6 7))
"((((1 . (2 . NIL)) . (3 . NIL)) . ((4 . (5 . NIL)) . NIL)) . (6 . (7 . NIL)))"
Dessiner : une approche de réécriture de terme
Utilisez une approche récursive ascendante pour le dessiner.
Définition. : Ici je définis une feuille comme une cellule cons qui a des atomes à la fois dans ses slots CAR et CDR : par exemple (0 . NIL) et (X . Y) sont tous deux des feuilles, mais pas ((0 . 1) . 2). Notez que cela inclut les listes incorrectes, quelque chose sur lequel je m'appuie pour expliquer la méthode de dessin lorsque je remplace les sous-termes par des symboles.
((((1 . (2 . NIL)) . (3 . NIL)) . ((4 . (5 . NIL)) . NIL)) . (6 . (7 . NIL)))
^^^^^^^^^ ^^^^^^^^^ ^^^^^^^^^ ^^^^^^^^^
Au-dessus j'ai souligné toutes les feuilles : vous pouvez facilement dessiner ces boîtes, et les étiqueter avec des symboles (A, B, ...).
Ici dessous je remplace les cellules d'origine par les noms de leurs boîtes associées, et je souligne à nouveau les nouvelles feuilles :
((((1 . A) . B) . ((4 . C) . NIL)) . (6 . D))
^^^^^^^ ^^^^^^^ ^^^^^^^
Ensuite, lorsqu'il y a un symbole représentant une boîte, dessinez une flèche vers cette boîte. Par exemple, vous définissez une boîte nommée E qui correspond à (1 . A), donc vous dessinez [1/x] et connectez le x à la boîte A.
Vous obtenez :
(((E . B) . (F . NIL)) . G)
Maintenant, considérez (E . B) : son car est un symbole, donc la boîte que vous devez dessiner n'a pas de valeur, mais une flèche sortante du slot CAR qui pointe vers la cellule E (tout comme son CDR pointe vers B). Répétez ce processus jusqu'à la fin. Le reste est la mise en page visuelle, où typiquement les boîtes qui sont juste des listes liées d'atomes sont disposées horizontalement.
Dessin direct à partir d'expressions
Possiblement l'exercice original vous demande de dessiner des boîtes directement à partir de l'expression d'origine. La même chose peut être faite comme ci-dessus, en remontant à partir des expressions de feuilles et en remplaçant leurs valeurs par des symboles dénotant des boîtes existantes.
- Un cons est directement mappé sur une boîte.
- une liste est simplement une application répétée de cons, et vous pouvez aller rapidement en dessinant autant de boîtes qu'il y a d'éléments.
- append en pratique fait une copie de tout sauf de la dernière liste dans les arguments, mais en dessinant vous pouvez "muter" les boîtes existantes. Pour chaque boîte existante, suivez le CDR jusqu'à ce que vous atteigniez une boîte sans flèche dans cdr, et reliez cette boîte à la suivante des arguments, en chaînant ainsi les différentes boîtes entre elles.
Il peut être intéressant de dessiner également la version réelle et purement fonctionnelle de append pour voir comment le partage de structure et la collecte de déchets fonctionnent.
