c - SICP对指针的描述

Question

此引述自SICP我认为是在谈论编程语言中的指针/引用。

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 上，因为如果我们通过 pair 构造列表，那将是下一个列表。

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

Answer 1

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 单元格有两个值，一个car 值和一个cdr 值。您放入其中的内容不受限制。你可以把任何东西放进去。

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

如果我们这样做

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

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

总结:

cons 单元格有两个值:car 和 cdr。两者都是完全不受约束的:您可以引用任何其他对象/值。

大部分实现都是隐藏的。在 Lisp 中，您所获得的只是以下具有基本功能的接口(interface):

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

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