lisp - cons cell 和 2-vector 有什么区别？

Question

在有向量的 Lisp 中，为什么 cons 单元仍然是必要的？据我了解，cons cell 是:

• 恰好包含 2 个元素的结构
• 已订购
• 访问是 O(1)

不过，所有这些也适用于二维向量。那么有什么区别呢？ cons 细胞只是 Lisps 有载体之前的遗迹吗？还是有其他我不知道的差异？

Answer 1

虽然在物理上，cones 类似于任何其他双元素聚合结构，但它们不仅仅是 2 向量的过时形式。

首先，Lisp 中的所有类型被划分为cons。和 atom .只有 cons 的类型是 cons ;其他一切都是原子。矢量是一个原子!

Conses 构成嵌套列表的表示基础，当然是用来编写代码的。它们有一个特殊的打印符号，例如 (cons 1 (cons 2 nil)) 生成的对象方便地打印为 (1 2)和 (cons 1 (cons 2 3)) 产生的对象打印为 (1 2 . 3) .

cons与 atom区分在语法中很重要，因为满足 consp 的表达式test 被视为复合形式。而不是关键字符号的原子，t或 nil self 评估。

要获取列表本身而不是复合形式的值，我们使用 quote ，我们有一个很好的速记。

有一个向量类型是很有用的，它不会以这种方式纠缠在求值语义中:它的实例只是自求值原子。

Cons 细胞不是 Lisp 有载体之前的遗迹。首先，几乎没有这样的时间。 1960 年的 Lisp 1 手册已经描述了数组。其次，后来的新方言还是有缺点的。

具有相似表示的对象并不是简单地相互冗余。类型区分很重要。例如，我们不会仅仅因为它们都具有三个插槽就认为以下两个是相互冗余的:

(defstruct name first initial last)

(defstruct bank-transaction account type amount)

在 TXR Lisp 方言中，我曾经有过这样的语法糖 a..b表示为 (cons a b)对于范围。但这意味着范围是 consp ，由于对列表的歧义，这很愚蠢。我最终改变了它 a..b表示 (rcons a b) : 构造范围对象的形式，打印为 #R(x y) . (并且可以将这种方式指定为文字)。这产生了一个有用的细微差别，因为我们可以区分函数参数是一个范围(rangep)还是一个列表(consp)。就像我们关心某个对象是否是 bank-transaction或 name . Range 对象的表示方式与 conses 完全相同，并从相同的堆中分配；只是它们有不同的类型，使它们成为原子。如果以形式进行评估，它们将对自己进行评估。

基本上，我们必须将类型视为一个额外的插槽。双元素向量实际上具有(至少)三个属性，而不仅仅是两个:它具有第一个元素、第二个元素和类型。矢量#(1 1)不同于 cons 单元格 (1 . 1)因为它们都有第三个方面，类型，这是不一样的。

一个对象与所有其他同类对象共享的不可变属性仍然可以被视为“插槽”。实际上，所有对象都有一个“类型槽”。所以 conses 实际上是具有 car 的三属性对象, cdr和 type :

(car '(a . b)) -> A
(cdr '(a . b)) -> B
(type-of '(a . b)) -> CONS

她是第四个“槽”:

(class-of '(a . b)) -> #<BUILT-IN-CLASS CONS>

我们不能仅根据在堆上分配的每个实例存储向量来查看对象。

---

顺便说一句，1960 年代的 MacLisp 方言将 cons 的概念扩展到具有更多命名字段(除了 car 和 cdr 之外)的固定大小聚合对象: cxr -s。这些对象被称为“帅哥”并且是documented in Kent Pitman's MacLisp manual .帅哥不满足谓词consp ，但是hunkp ;即它们被认为是原子。但是，它们用多个点扩展了 cons 符号。