cons()的意外输出

Question

我来自一个迫切的背景,但这些天我在LISP(普通LISP)上尝试

我读到这里大约cons是

(cons x L):

给定LISP对象x和列表L,求值(cons x L)创建一个包含x的列表,后跟L中的元素.

当我故意不使用列表作为第二个参数时,即我使用时

(cons 'a 'a)我期待一个错误,但哇!我有(A . A).

我错过了什么,是 (A . A)什么？

Answer 1

Cons构建"利弊细胞".这与列表最初没有任何关系.cons单元格是一对两个值.cons单元以书面形式由"点对"表示,例如(A . B),其保持两个值'A和'B.

cons单元格中的两个位置称为"car"和"cdr".您可以将这样的cons单元可视化为一个二分块:

  car   cdr
+-----+-----+
|  A  |  B  |
+-----+-----+

在Lisp中,值也可以是对其他内容的引用,例如,另一个cons单元格:

+-----+-----+       +-----+-----+
|  A  |   --------> |  B  |  C  |
+-----+-----+       +-----+-----+

这将以"点对"形式表示为(A . (B . C)).你可以这样继续:

+-----+-----+       +-----+-----+       +-----+-----+
|  A  |   --------> |  B  |   --------> |  C  |  D  |
+-----+-----+       +-----+-----+       +-----+-----+

这是(A . (B . (C . D))).正如您所看到的,在这样的结构中,值始终位于carcons单元格中,并且cdr指向结构的其余部分.最后一个值是最后一个值cdr.但是我们不需要这个例外:NILLisp中有一个特殊值,表示"无".通过放入NIL最后一个cdr,你有一个方便的哨兵值,你的所有值都在cars:

+-----+-----+       +-----+-----+       +-----+-----+       +-----+-----+
|  A  |   --------> |  B  |   --------> |  C  |   --------> |  D  | NIL |
+-----+-----+       +-----+-----+       +-----+-----+       +-----+-----+

这是在Lisp中构建列表的方式.由于(A . (B . (C . (D . NIL))))有点笨拙,它也可以简单地表示为(A B C D). NIL也称为空列表(); 这些是同一事物的可更换符号.

现在您可以看到为什么(cons x list)返回另一个列表. Cons简单地构建另一个缺点与细胞x在car与参考到list在cdr:

+-----+-----+
|  X  |   --------> list
+-----+-----+

如果list是(A B),它的工作原理如下:

+-----+-----+       +-----+-----+       +-----+-----+
|  X  |   --------> |  A  |   --------> |  B  | NIL |
+-----+-----+       +-----+-----+       +-----+-----+

所以,(cons x '(a b))评估为(x a b).

列表只是cons细胞的一种常见用法.您也可以从cons单元格,圆形列表或任何有向图形构造任意树.