SICP对指针的描述

Question

这句话来自 SICP，我认为它在谈论编程语言中的 pointers/references。

As we have seen, pairs provide a primitive “glue” that we can use to construct compound data objects. Figure 2.2 shows a standard way to visualize a pair—in this case, the pair formed by (cons 1 2). In this representation, which is called box-and-pointer notation, each object is shown as a pointer to a box. The box for a primitive object contains a representation of the object. For example, the box for a number contains a numeral. The box for a pair is actually a double box, the left part containing (a pointer to) the car of the pair and the right part containing the cdr.

在这种情况下，本书讨论的是对 (E.G. (cons 1 2)) 以及它们的表示方式。然而，我们也可以使用对来构建这样的列表：

(缺点 1 (缺点 2 '()))

虽然box-and-pointer-notation只是一种表示法，没什么用，但我觉得这看起来很像链表。据我了解，链表是一种数据结构，包含一个值和一个指向另一个链表的指针。话虽如此，我认为 cons 可以像链表一样构造。我很困惑：

The box for a pair is actually a double box, the left part containing (a pointer to) the car of the pair and the right part containing the cdr.

我原本认为指针应该在 cdr 上，因为如果我们通过成对构建列表，那将是下一个列表。

我认为这可能是一种完全不同的指针。在这种情况下，指针究竟意味着什么？我知道的唯一指针是 c 中使用的指针。 SICP 甚至提到任何有关 c 指针的内容吗？

Answer 1

是的，你说得对，cons 单元格用于在 Lisp 中构建链表。

左边部分包含缺点的值。它是一个指针，因为它的值可能是一个数字、一个对象、另一个缺点（例如在树的情况下）或其他任何东西。

你也是正确的，右边的部分 cdr 包含指向列表中下一个 cons 的指针。

所以列表 (54 "foobar" 3) 看起来像这样：

            (car cdr)
             /     \
            54      (car cdr)
                     /     \
                  "foobar"  (car nil)
                             / 
                            3

Answer 2

I originally thought the pointer should be on cdr because that would be the next list if we were constructing a list through pairs.

一个cons cell有两个值，一个car值和一个cdr值。您放入其中的内容不受限制。你可以把任何东西放进去。

您可以使用 cons 单元构建不同的数据结构。单向链表只是其中之一。它可以是二叉树、通过键和值提供访问的cons单元的关联列表、循环数据结构等等。

如果我们这样做

(cons
      (cons :foo 10)
      (cons :bar 5))

... 那么从 cons 单元格到它的 car 值的引用是如何完成的，这对程序员来说基本上是隐藏的。大多数实现将在下面具有某种数据结构，其中包含从 cons 单元指向其 car 和 cdr 组件的指针。通常会对字符和小整数等小对象进行优化 (fixnums) - 这些也可以直接存储在 car 和 cdr，而不是使用指向字符对象的指针。

总结:

A cons 单元格有两个值：car 和 cdr。两者都完全不受约束：您可以引用任何其他 object/value.

大部分实现都是隐藏的。在 Lisp 中，您得到的只是以下具有基本功能的接口：

(consp thing) : 谓词 returns T 如果 thing 是缺点单元格。
(car cons-cell) : cons cell的汽车价值
(cdr cons-cell) : cons cell的cdr值
(cons thing-0 thing-1) : 创建一个 cons cell，thing-0 和 thing-1 可以是任何东西。

列表是由 cons 单元格组成的。但是还有其他数据结构可以由 cons 单元构成。

SICP对指针的描述

SICP's description of pointers

c

pointers

linked-list

lisp

sicp