不能在 Clojure 的库级别有效地实现 cons 单元吗？

Question

Clojure 有自己的集合，不需要传统的 lispy cons 单元。但我觉得这个概念很有趣，它被用在一些教材中（例如 SICP）。我一直想知道是否有任何理由表明这个 cons 原语需要是一个原语。我们不能只在库中实现它（以及操作它的传统函数）吗？我搜索了一下，没有找到这样的库。

Answer 1

你可以自己实现。这是一个尝试：

(defprotocol cons-cell
  (car [this])
  (cdr [this]) 
  (rplaca [this v])
  (rplacd [this v]))

(deftype Cons [^:volatile-mutable car
               ^:volatile-mutable cdr]
  cons-cell
  (car [this] (.car this))
  (cdr [this] (.cdr this))
  (rplaca [this value] (set! car value))
  (rplacd [this value] (set! cdr value)))

(defn cons [car cdr]
  (Cons. car cdr))

循环列表：

(let [head (cons 0 nil)]
  (rplacd head head) 
  head)

Answer 2

Cons 单元格是 Lisp 中用于 s 表达式的重要构建块。例如，请参阅 McCarthy 从 1958 年开始关于 Lisp 和符号表达式的各种出版物（例如 Recursive Functions of Symbolic Expressions）。 Lisp 中的每个列表都是由 cons 单元组成的。

用 cons 单元作为库来实现链表（和树，...）绝对是可能的。但对于 Lisp 来说，它们是如此重要，以至于它需要尽早使用它们并实现非常有效的实现。

在 Lisp 系统中，通常有许多 cons cells 并且分配新 cons cells 的比率很高（称为 consing）。因此，Lisp 的实现者可能希望优化他们的 Lisp 实现：

小型cons cells -> 不超过两个机器字，一个字用于car，一个字用于cdr
快速分配新的劣势细胞
cons 单元的高效垃圾收集（非常快速地找到不再使用的 cons 单元）
直接在 cons 单元中存储原始数据（数字、字符等）-> 没有指针开销
优化 Lisp 数据的局部性，例如 cons 单元结构（列表、关联列表、树等），例如通过使用 generational/copying 垃圾收集器 and/or cons 单元的内存区域

因此 Lisp 系统使用各种技巧来实现这一点。例如，如果指针指向一个 cons 单元，则它们可以进行编码——因此 cons 单元本身不需要类型标签。 Fixnums 的标签位很少，适合 cons 单元格的 CAR 或 CDR。在 MIT Lisp Machine 上，当 cons cell 是线性列表的一部分时，系统还具有省略 CDR 部分的功能。

为了实现所有这些优化目标，通常需要在汇编程序 and/or C 中手动调整 Lisp 运行时的实现。Lisp 处理器或 Lisp VM 通常会提供 CAR、CDR、CONS、CONSP、 ...作为机器指令。

正如 TFB 所说：类似地，可以在库中实现浮点数，但与 CPU 支持的原生浮点数和运算相比，效率不高。 Lisp 实现在非常非常低的水平上提供缺点单元。

但在这样的 Lisp 实现之外，显然可以将 cons 单元实现为一个库——但 space 和时间效率稍差。

旁注

Maclisp 的缺点单元有两个以上的插槽，称为 Hunks

Answer 3

当然，除了 lambda（在 Clojure 中称为 fn）之外，您无需任何工具即可实现 cons 单元。

(defn cons' [a d]
  (fn [f] (f a d)))

(defn car' [c]
  (c (fn [a d] a)))

(defn cdr' [c]
  (c (fn [a d] d)))

user> (car' (cdr' (cons' 1 (cons' 2 nil))))
2

这与您在 Clojure 中可以得到的一样 space-efficient（关闭两个绑定的 lambda 只是一个具有两个字段的对象）。 car 和 cdr 显然可以 time-efficient 如果您使用记录或其他东西代替；我要说的是，是的，你当然可以制作 cons 单元，即使你几乎没有可用的工具。

为什么还没有完成呢？我们已经有了更好的工具。 Clojure 的序列抽象比 cons 单元做的更好，而向量是一个完美的元组。对cons细胞的需求并不大。再加上想要它们的任何人都会发现重新实施非常容易，并且没有客户需要预期的图书馆解决方案。

不能在 Clojure 的库级别有效地实现 cons 单元吗？

Can't cons cells be implemented efficiently at the library level in Clojure?

lisp

clojure

cons

data-structures