学习箱形图和指针图的资源
Resources for Learning Box and Pointer Diagrams
我目前正在学习 Berkely's summer 2011 CS3L course 并且正在努力理解方框图和指针图。如何构建它们以及如何解释它们。
提供的说明是here。
然而，我还不是"getting it."
我知道列表是成对的组合，一对的 cdr 可能指向另一对。我也明白 cdr 指向的那对可能是另一个列表。我只是不明白如何在图表中将其全部画出来。
作为参考，这是我遇到的一个问题示例：
(define cal
(list (append (list (cons (list 1 2) (cons 3 '())))
(list (cons 4 (cons 5 '()))))
6
7))
给出像上面这样的代码，我想画出方框和指针图，然后能够说出需要什么样的 car 和 cdr 组合才能获得列表中的任何给定数字。
同样，作为参考，下面是我应该能够想出的图表：
重申一下，我要找的是可以更清楚地解释盒形图和指针图的构建的视频或文章。
提前感谢任何愿意为我指明正确方向的人。
尝试从内到外开始，就像口译员一样。画图，比如说，(cons 3 '()) - 很简单，对吧？现在，应该有什么指向它吗？没错，就是(cons (list 1 2) (cons 3 '()))的cdr。所以，当你为那个更大的表达式画图时，确保它的 cdr 指向你画的第一个子图。要完成这个更大的表达式的绘制，您还需要为 (list 1 2) 绘制图表 - 就像您开始时一样简单。
从那里开始工作 - append 操作是最棘手的部分，但您链接的说明解释了 append 的工作原理。
忘记列表。没有列表。只有一对。
(define cal
(list (append (list (cons (list 1 2) (cons 3 '())))
(list (cons 4 (cons 5 '()))))
6
7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL))) ; (list 1 2)
(define B (cons 3 NIL)) ; (cons 3 '())
(define C (cons 5 NIL)) ; (cons 5 '())
(define cal
(list (append (list (cons A B))
(list (cons 4 C)))
6
7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL)))
(define B (cons 3 NIL))
(define C (cons 5 NIL))
(define D (cons A B))
(define E (cons 4 C))
(define cal
(list (append (list D)
(list E))
6
7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL)))
(define B (cons 3 NIL))
(define C (cons 5 NIL))
(define D (cons A B))
(define E (cons 4 C))
(define F (list D E)) ; (append (list D) (list E))
(define cal
(list F
6
7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL)))
(define B (cons 3 NIL))
(define C (cons 5 NIL))
(define D (cons A B))
(define E (cons 4 C))
(define F (cons D (cons E NIL))) ; (list D E)
(define cal
(cons F
(cons 6
(cons 7 NIL))))
每个cons是一个盒子。每个名字都是一个指针。
仅此而已。
这个答案使用 Common Lisp 作为示例，但在 Scheme 中并没有根本的不同。另请注意，如果您想了解打印图表的实际实现方式，您可以使用 Common Lisp 中的 sdraw.lisp（例如使用 CCL 或 SBCL 程序）。
你首先要清楚你要打印的结果，当源包含cons/list/append操作时，这可能会很困难。此外，由于源代码也是一棵cons-cells树，您必须注意不要将源代码与评估后获得的值混在一起。
所以这一切都从正确评估表格开始。
评价cal
让我们首先评估表达式。下面，我还提到直接从输入表达式绘制框，但 IMO 有助于详细说明中间步骤。
在递归计算所有表达式后，Scheme 和 Common Lisp 的结果是一样的：
((((1 2) 3) (4 5)) 6 7)
这里是你如何要求系统跟踪计算，在Common Lisp中。首先，要知道您无法跟踪 list 等标准函数。所以让我们用简单的包装器将它们隐藏在自定义包中：
(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))
然后，在 REPL 中，转到那个包：
CL-USER> (in-package :so)
#<PACKAGE "SO">
要求跟踪那些函数：
SO> (trace list append cons) ;; the shadowing ones
(LIST CONS APPEND)
现在，您可以直接输入cal的值，但这次使用的符号是我们要求跟踪的符号。
SO> (list (append (list (cons (list 1 2) (cons 3 '())))
(list (cons 4 (cons 5 '()))))
6
7)
环境然后评估表单并打印每个函数的调用方式和结果 returns。
0: (SO::LIST 1 2)
0: LIST returned (1 2)
0: (SO::CONS 3 NIL)
0: CONS returned (3)
0: (SO::CONS (1 2) (3))
0: CONS returned ((1 2) 3)
0: (SO::LIST ((1 2) 3))
0: LIST returned (((1 2) 3))
0: (SO::CONS 5 NIL)
0: CONS returned (5)
0: (SO::CONS 4 (5))
0: CONS returned (4 5)
0: (SO::LIST (4 5))
0: LIST returned ((4 5))
0: (SO::APPEND (((1 2) 3)) ((4 5)))
0: APPEND returned (((1 2) 3) (4 5))
0: (SO::LIST (((1 2) 3) (4 5)) 6 7)
0: LIST returned ((((1 2) 3) (4 5)) 6 7)
((((1 2) 3) (4 5)) 6 7)
可视化为缺点细胞
将列表视为 Cons-cell 链可能会有所帮助，即将 (a b c) 变为 (a . (b . (c . nil)))。让我们定义一个辅助函数：
(defun consprint (x)
(if (consp x)
(format nil
"(~a . ~a)"
(consprint (car x))
(consprint (cdr x)))
(prin1-to-string x)))
结果如下：
SO> (consprint '((((1 2) 3) (4 5)) 6 7))
"((((1 . (2 . NIL)) . (3 . NIL)) . ((4 . (5 . NIL)) . NIL)) . (6 . (7 . NIL)))"
绘制：一种术语重写方法
使用递归、自下而上的方法绘制它。
定义。：这里我定义了一个leaf作为cons-cell，它的CAR和CDR槽都有原子：例如(0 . NIL) 和 (X . Y) 都是叶子，但 ((0 . 1) . 2) 不是。请注意，这包括不正确的列表，当我用符号替换子项时，我依靠它来解释绘图方法。
((((1 . (2 . NIL)) . (3 . NIL)) . ((4 . (5 . NIL)) . NIL)) . (6 . (7 . NIL)))
^^^^^^^^^ ^^^^^^^^^ ^^^^^^^^^ ^^^^^^^^^
上面我在所有叶子上都画了下划线：你可以很容易地画出这些方框，并用符号（A、B、...）标记它们。
在下面，我将原始单元格替换为相关框的名称，并再次在新叶子下划线：
((((1 . A) . B) . ((4 . C) . NIL)) . (6 . D))
^^^^^^^ ^^^^^^^ ^^^^^^^
然后，当有代表一个方框的符号时，画一个指向那个方框的箭头。例如，您定义了一个名为 E 的框对应于 (1 . A)，因此您绘制 [1/x] 并将 x 连接到框 A.
您获得：
(((E . B) . (F . NIL)) . G)
现在，考虑(E . B)：它的车是一个符号，所以你需要绘制的方框没有值，而是一个从CAR槽向外的箭头指向E单元格（就像它的 CDR 指向 B）。
你重复这个过程直到终止。其余部分是视觉布局，其中通常只是 linked 原子列表的框是水平放置的。
直接从表达式中绘制
大概原来的练习是要你直接从原来的表达式中画出方框。可以像上面那样做，从叶表达式向上工作并用表示现有框的符号替换它们的值。
- 缺点直接映射到盒子。
- 列表只是cons的重复应用，元素有多少，画多少框就可以很快。
- append 实际上会复制参数中除最后一个列表之外的所有内容，但在绘制时您可以 "mutate" 现有框。对于每个现有框，继续跟踪 CDR，直到到达 cdr 中没有箭头的框，然后 link 该框到参数中的下一个框，从而将不同的框链接在一起。
绘制 append 的实际纯功能版本以了解结构共享和垃圾收集如何工作可能会很有趣。
[请注意，这个答案并不鼓励你作弊：如果你正在学习一门要求你能够绘制方框图和指针图的课程，那么你应该能够做到这一点，而不是让程序来做为你。但该程序可以帮助您学习。]
学习方框图和指针图工作原理的一个好方法是能够与知道如何绘制它们的程序对话。在很久以前的 Lisp 黄金时代，我们的 Lisp 机器上有很棒的对话界面，可以让图形和文本混合在一起，还有漂亮的图形绘制程序，可以从中轻松构建工具来做到这一点。使用这些工具，你可以根据conses构建各种结构，并让程序为你绘制图表，从而你可以很好地掌握结构的工作原理。
嗯……事实证明，现在是 Lisp 的黄金时代。如果您使用 Racket (and you can use Racket if you are not already using it) then there is a very wonderful package called sdraw 来执行此操作。它没有与 Racket 发行版捆绑在一起，但要安装它，您可以使用 DrRacket 的包管理器或直接执行
raco pkg install --auto sdraw
这将安装它。现在你可以（在 DrRacket window 中，这在终端会话中不起作用）只需与 Racket REPL 对话并让它为你绘制缺点树：
通过简单地与语言交互并让它为您绘制内容，您就可以很好地了解各种结构是如何组合在一起的。
从代码开始，您可以从顶层向下工作。鉴于：
(define cal
(list (append (list (cons (list 1 2) (cons 3 '())))
(list (cons 4 (cons 5 '()))))
6
7))
你可以看到第一层是一个包含三个元素的列表：一个复杂的对象，一个6和一个7。这可以用三个cons单元格来表示：
现在你只需要弄清楚第一个 cons 单元格的 car 指向什么。回顾代码，this 指向一个由两个列表组成的列表，附加在一起。如果您查看括号，您会发现对 list 的第一次调用仅采用一个参数，因此这将创建一个包含一个元素的列表。
当附加两个列表时，关闭第一个列表的 nil 将替换为指向第二个列表前面的指针，因此：
要附加的两个列表中的第一个列表由以下代码创建：
(list (cons (list 1 2) (cons 3 '())))
这里，列表(1 2)被放在列表(3)的前面，创建一个新的列表。这是一个包含两个元素的列表，其中列表的 car 指向列表 (1 2)，列表的 cdr 指向 (3)。我们可以继续为这一层绘制方框：
由于最后一层的car正好指向列表(1 2)，我们可以将其填入：
现在，append函数的第二个参数是也是一个只包含一个元素的列表，所以：
那个单个元素是 (cons 4 (cons 5 '())) 的结果，它只是列表 (4 5)，所以我们最终可以通过从 car 指向这个列表来完成我们的框图最后一个缺点单元格：
我目前正在学习 Berkely's summer 2011 CS3L course 并且正在努力理解方框图和指针图。如何构建它们以及如何解释它们。
提供的说明是here。 然而，我还不是"getting it."
我知道列表是成对的组合，一对的 cdr 可能指向另一对。我也明白 cdr 指向的那对可能是另一个列表。我只是不明白如何在图表中将其全部画出来。
作为参考，这是我遇到的一个问题示例：
(define cal
(list (append (list (cons (list 1 2) (cons 3 '())))
(list (cons 4 (cons 5 '()))))
6
7))
给出像上面这样的代码，我想画出方框和指针图，然后能够说出需要什么样的 car 和 cdr 组合才能获得列表中的任何给定数字。
同样，作为参考，下面是我应该能够想出的图表：
重申一下，我要找的是可以更清楚地解释盒形图和指针图的构建的视频或文章。
提前感谢任何愿意为我指明正确方向的人。
尝试从内到外开始，就像口译员一样。画图，比如说，(cons 3 '()) - 很简单，对吧？现在，应该有什么指向它吗？没错，就是(cons (list 1 2) (cons 3 '()))的cdr。所以，当你为那个更大的表达式画图时，确保它的 cdr 指向你画的第一个子图。要完成这个更大的表达式的绘制，您还需要为 (list 1 2) 绘制图表 - 就像您开始时一样简单。
从那里开始工作 - append 操作是最棘手的部分，但您链接的说明解释了 append 的工作原理。
忘记列表。没有列表。只有一对。
(define cal
(list (append (list (cons (list 1 2) (cons 3 '())))
(list (cons 4 (cons 5 '()))))
6
7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL))) ; (list 1 2)
(define B (cons 3 NIL)) ; (cons 3 '())
(define C (cons 5 NIL)) ; (cons 5 '())
(define cal
(list (append (list (cons A B))
(list (cons 4 C)))
6
7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL)))
(define B (cons 3 NIL))
(define C (cons 5 NIL))
(define D (cons A B))
(define E (cons 4 C))
(define cal
(list (append (list D)
(list E))
6
7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL)))
(define B (cons 3 NIL))
(define C (cons 5 NIL))
(define D (cons A B))
(define E (cons 4 C))
(define F (list D E)) ; (append (list D) (list E))
(define cal
(list F
6
7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL)))
(define B (cons 3 NIL))
(define C (cons 5 NIL))
(define D (cons A B))
(define E (cons 4 C))
(define F (cons D (cons E NIL))) ; (list D E)
(define cal
(cons F
(cons 6
(cons 7 NIL))))
每个cons是一个盒子。每个名字都是一个指针。
仅此而已。
这个答案使用 Common Lisp 作为示例，但在 Scheme 中并没有根本的不同。另请注意，如果您想了解打印图表的实际实现方式，您可以使用 Common Lisp 中的 sdraw.lisp（例如使用 CCL 或 SBCL 程序）。
你首先要清楚你要打印的结果，当源包含cons/list/append操作时，这可能会很困难。此外，由于源代码也是一棵cons-cells树，您必须注意不要将源代码与评估后获得的值混在一起。 所以这一切都从正确评估表格开始。
评价cal
让我们首先评估表达式。下面，我还提到直接从输入表达式绘制框，但 IMO 有助于详细说明中间步骤。 在递归计算所有表达式后，Scheme 和 Common Lisp 的结果是一样的：
((((1 2) 3) (4 5)) 6 7)
这里是你如何要求系统跟踪计算，在Common Lisp中。首先，要知道您无法跟踪 list 等标准函数。所以让我们用简单的包装器将它们隐藏在自定义包中：
(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))
然后，在 REPL 中，转到那个包：
CL-USER> (in-package :so)
#<PACKAGE "SO">
要求跟踪那些函数：
SO> (trace list append cons) ;; the shadowing ones
(LIST CONS APPEND)
现在，您可以直接输入cal的值，但这次使用的符号是我们要求跟踪的符号。
SO> (list (append (list (cons (list 1 2) (cons 3 '())))
(list (cons 4 (cons 5 '()))))
6
7)
环境然后评估表单并打印每个函数的调用方式和结果 returns。
0: (SO::LIST 1 2)
0: LIST returned (1 2)
0: (SO::CONS 3 NIL)
0: CONS returned (3)
0: (SO::CONS (1 2) (3))
0: CONS returned ((1 2) 3)
0: (SO::LIST ((1 2) 3))
0: LIST returned (((1 2) 3))
0: (SO::CONS 5 NIL)
0: CONS returned (5)
0: (SO::CONS 4 (5))
0: CONS returned (4 5)
0: (SO::LIST (4 5))
0: LIST returned ((4 5))
0: (SO::APPEND (((1 2) 3)) ((4 5)))
0: APPEND returned (((1 2) 3) (4 5))
0: (SO::LIST (((1 2) 3) (4 5)) 6 7)
0: LIST returned ((((1 2) 3) (4 5)) 6 7)
((((1 2) 3) (4 5)) 6 7)
可视化为缺点细胞
将列表视为 Cons-cell 链可能会有所帮助，即将 (a b c) 变为 (a . (b . (c . nil)))。让我们定义一个辅助函数：
(defun consprint (x)
(if (consp x)
(format nil
"(~a . ~a)"
(consprint (car x))
(consprint (cdr x)))
(prin1-to-string x)))
结果如下：
SO> (consprint '((((1 2) 3) (4 5)) 6 7))
"((((1 . (2 . NIL)) . (3 . NIL)) . ((4 . (5 . NIL)) . NIL)) . (6 . (7 . NIL)))"
绘制：一种术语重写方法
使用递归、自下而上的方法绘制它。
定义。：这里我定义了一个leaf作为cons-cell，它的CAR和CDR槽都有原子：例如(0 . NIL) 和 (X . Y) 都是叶子，但 ((0 . 1) . 2) 不是。请注意，这包括不正确的列表，当我用符号替换子项时，我依靠它来解释绘图方法。
((((1 . (2 . NIL)) . (3 . NIL)) . ((4 . (5 . NIL)) . NIL)) . (6 . (7 . NIL)))
^^^^^^^^^ ^^^^^^^^^ ^^^^^^^^^ ^^^^^^^^^
上面我在所有叶子上都画了下划线：你可以很容易地画出这些方框，并用符号（A、B、...）标记它们。
在下面，我将原始单元格替换为相关框的名称，并再次在新叶子下划线：
((((1 . A) . B) . ((4 . C) . NIL)) . (6 . D))
^^^^^^^ ^^^^^^^ ^^^^^^^
然后，当有代表一个方框的符号时，画一个指向那个方框的箭头。例如，您定义了一个名为 E 的框对应于 (1 . A)，因此您绘制 [1/x] 并将 x 连接到框 A.
您获得：
(((E . B) . (F . NIL)) . G)
现在，考虑(E . B)：它的车是一个符号，所以你需要绘制的方框没有值，而是一个从CAR槽向外的箭头指向E单元格（就像它的 CDR 指向 B）。
你重复这个过程直到终止。其余部分是视觉布局，其中通常只是 linked 原子列表的框是水平放置的。
直接从表达式中绘制
大概原来的练习是要你直接从原来的表达式中画出方框。可以像上面那样做，从叶表达式向上工作并用表示现有框的符号替换它们的值。
- 缺点直接映射到盒子。
- 列表只是cons的重复应用，元素有多少，画多少框就可以很快。
- append 实际上会复制参数中除最后一个列表之外的所有内容，但在绘制时您可以 "mutate" 现有框。对于每个现有框，继续跟踪 CDR，直到到达 cdr 中没有箭头的框，然后 link 该框到参数中的下一个框，从而将不同的框链接在一起。
绘制 append 的实际纯功能版本以了解结构共享和垃圾收集如何工作可能会很有趣。
[请注意，这个答案并不鼓励你作弊：如果你正在学习一门要求你能够绘制方框图和指针图的课程，那么你应该能够做到这一点，而不是让程序来做为你。但该程序可以帮助您学习。]
学习方框图和指针图工作原理的一个好方法是能够与知道如何绘制它们的程序对话。在很久以前的 Lisp 黄金时代，我们的 Lisp 机器上有很棒的对话界面，可以让图形和文本混合在一起，还有漂亮的图形绘制程序，可以从中轻松构建工具来做到这一点。使用这些工具，你可以根据conses构建各种结构，并让程序为你绘制图表，从而你可以很好地掌握结构的工作原理。
嗯……事实证明，现在是 Lisp 的黄金时代。如果您使用 Racket (and you can use Racket if you are not already using it) then there is a very wonderful package called sdraw 来执行此操作。它没有与 Racket 发行版捆绑在一起，但要安装它，您可以使用 DrRacket 的包管理器或直接执行
raco pkg install --auto sdraw
这将安装它。现在你可以（在 DrRacket window 中，这在终端会话中不起作用）只需与 Racket REPL 对话并让它为你绘制缺点树：
通过简单地与语言交互并让它为您绘制内容，您就可以很好地了解各种结构是如何组合在一起的。
从代码开始，您可以从顶层向下工作。鉴于：
(define cal
(list (append (list (cons (list 1 2) (cons 3 '())))
(list (cons 4 (cons 5 '()))))
6
7))
你可以看到第一层是一个包含三个元素的列表：一个复杂的对象，一个6和一个7。这可以用三个cons单元格来表示：
现在你只需要弄清楚第一个 cons 单元格的 car 指向什么。回顾代码，this 指向一个由两个列表组成的列表，附加在一起。如果您查看括号，您会发现对 list 的第一次调用仅采用一个参数，因此这将创建一个包含一个元素的列表。
当附加两个列表时，关闭第一个列表的 nil 将替换为指向第二个列表前面的指针，因此：
要附加的两个列表中的第一个列表由以下代码创建：
(list (cons (list 1 2) (cons 3 '())))
这里，列表(1 2)被放在列表(3)的前面，创建一个新的列表。这是一个包含两个元素的列表，其中列表的 car 指向列表 (1 2)，列表的 cdr 指向 (3)。我们可以继续为这一层绘制方框：
由于最后一层的car正好指向列表(1 2)，我们可以将其填入：
现在，append函数的第二个参数是也是一个只包含一个元素的列表，所以：
那个单个元素是 (cons 4 (cons 5 '())) 的结果，它只是列表 (4 5)，所以我们最终可以通过从 car 指向这个列表来完成我们的框图最后一个缺点单元格：