列表示意图

例如,列表 (rose violet buttercup) 有三个元素,‘rose’、‘violet’ 和 ‘buttercup’。在计算机中,‘rose’ 的电子地址记录在称为 cons cell(因为它实际上是函数 cons 创建的东西)的计算机内存段中。该 cons cell 还保存了指向第二个 cons cell 的地址,其 CAR 是原子 ‘violet’;而该地址(指示如何找到 ‘violet’ 的地址)与保存原子 ‘buttercup’ 的地址一起保存在第三个 cons cell 的地址中。

这听起来比实际上更复杂,但在图表中更容易理解:

    ___ ___      ___ ___      ___ ___
   |___|___|--> |___|___|--> |___|___|--> nil
     |            |            |
     |            |            |
      --> rose     --> violet   --> buttercup


在图表中,每个框表示计算机内存中的一个字,通常以内存地址的形式保存一个Lisp对象。框,即地址,是成对出现的。每个箭头指向地址所指的内容,要么是一个原子,要么是另一对地址。第一个框是 ‘rose’ 的电子地址,箭头指向 ‘rose’;第二个框是下一对框的地址,其第一部分是 ‘violet’ 的地址,第二部分是下一对的地址。最后一个框指向符号 nil,表示列表的结束。

当变量使用诸如 setq 这样的操作设置为列表时,它将存储在变量中的第一个框的地址。因此,表达式的求值

(setq bouquet '(rose violet buttercup))

会创建这样的情况:

bouquet
     |
     |     ___ ___      ___ ___      ___ ___
      --> |___|___|--> |___|___|--> |___|___|--> nil
            |            |            |
            |            |            |
             --> rose     --> violet   --> buttercup


在此示例中,符号 bouquet 持有第一对框的地址。

相同的列表可以用不同类型的框符号表示,如下所示:

bouquet
 |
 |    --------------       ---------------       ----------------
 |   | car   | cdr  |     | car    | cdr  |     | car     | cdr  |
  -->| rose  |   o------->| violet |   o------->| butter- |  nil |
     |       |      |     |        |      |     | cup     |      |
      --------------       ---------------       ----------------


(符号由不仅仅是地址对组成,但符号的结构由地址组成。实际上,符号 bouquet 由一组地址框组成,其中一个是打印字 ‘bouquet’ 的地址,第二个是附加到符号的函数定义的地址(如果有的话),第三个是列表 (rose violet buttercup) 的地址的第一对地址框,依此类推。这里我们显示符号的第三个地址框指向列表的第一对地址框。)

如果将符号设置为列表的 CDR,列表本身不会改变;符号只是具有列表中更远地址的地址。 (在行话中,CARCDR 是“非破坏性的”)因此,对以下表达式的求值

(setq flowers (cdr bouquet))

会产生:


bouquet        flowers
  |              |
  |     ___ ___  |     ___ ___      ___ ___
   --> |   |   |  --> |   |   |    |   |   |
       |___|___|----> |___|___|--> |___|___|--> nil
         |              |            |
         |              |            |
          --> rose       --> violet   --> buttercup



变量 flowers 的值是 (violet buttercup),也就是说,符号 flowers 持有地址的对应的框,其中第一个框持有 violet 的地址,第二个框持有 buttercup 的地址。

一对地址框称为 cons cell点对。有关 cons cell 和点对的更多信息,请参见 See Cons Cell and List Types in The GNU Emacs Lisp Reference Manual, 以及 Dotted Pair Notation in The GNU Emacs Lisp Reference Manual.

函数 cons 将一个新的地址对添加到上面所示的地址系列的前面。例如,对以下表达式的求值

(setq bouquet (cons 'lily bouquet))

产生:


bouquet                       flowers
  |                             |
  |     ___ ___        ___ ___  |     ___ ___       ___ ___
   --> |   |   |      |   |   |  --> |   |   |     |   |   |
       |___|___|----> |___|___|----> |___|___|---->|___|___|--> nil
         |              |              |             |
         |              |              |             |
          --> lily      --> rose       --> violet    --> buttercup



然而,这并不会改变符号 flowers 的值,可以通过求值以下表达式来查看:

(eq (cdr (cdr bouquet)) flowers)

这会返回 t,表示为真。

在被重新设置之前,flowers 仍然具有值 (violet buttercup);也就是说,它持有第一个框的地址,该框的第一个地址是 violet

总而言之,在Lisp中,要获得列表的 CDR,只需获取系列中下一个 cons cell 的地址;要获取列表的 CAR,只需获取列表的第一个元素的地址;要在列表前面添加新元素,只需在列表的前面添加一个新的 cons cell。就是这样!Lisp的底层结构非常简单!

而在一系列 cons 单元中,最后一个地址指向什么呢?它指向空列表,即 nil 的地址。

总之,当一个 Lisp 变量被设置为某个值时,它会被赋予指向该变量所引用的列表的地址。