Programming in Emacs Lisp笔记（九）List的实现

List的实现

Lisp中list使用了连续的指针对来保存数据，指针对的第一个指针指向一个原子或者另一个list，指针对的第二个指针指向另一个指针对，或者指向nil，以表明list的结束。

List图示

举例来说，list(rose violet buttercup)有3个元素，rose，violet和buttercup。在计算机中，rose的地址被保存在计算机内存中，通过这个地址可以知道 原子violet被分配在了哪个位置；通过这个地址又可以知道原子buttercup的地址。

听起来比较复杂，看图就简单多了：

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

这个图中，每个方框代表一个保存了Lisp对象的内存块，这通常是一个内存地址。在方框中的地址是成对的。每个箭头指向了这个地址的内容，它可能是一个原 子也可能是另一个地址对。第一个方框是rose的地址；第二个方框保存了下一个方框对的地址，这个地址的第一个部分指向violet第二个部分指向下一个 方框对。最后一个方框指向符号nil，标明list的结束。

当执行一个设置函数时比如setq，它将第一个方框的地址保存到变量中。比如：

(setq bouquet '(rose violet buttercup))

产生的情况如下：

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

在这个例子中符号bouquet保存了第一个方框对的地址。

同样，list也可以被成有序的方框：

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

（符号是由地址组成的。实际上bouquet包含了一组地址，一个地址指向可打印的单词bouquet，第二个是地址绑定到该符号上的函数定 义（如果存在），第三个地址是list(rose violet buttercup)的第一个地址对的地址，等等。这里只显示了第三个地址的情况。）

如果符号指向list的CDR部分，这个list本身不会改变；符号将拥有从那个位置开始的list。（CAR和CDR是'non-destructive'的）因此执行下面的语句：

(setq flowers (cdr bouquet))

将产生下面的结果：

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

flowers的值是(violet buttercup)，这就是说符号flowers拥有了一个地址对的地址。

这种地址对被称为cons cell或者dotted pair。

函数cons添加一个新的地址对到一连串地址对的前面。例如，执行下面的语句：

(setq bouquet (cons 'lily bouquet))

产生的效果如下：

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

而这并不会改变flowers的值，你可以看到：

(eq (cdr (cdr bouquet)) flowers)

将返回t。

到现在为止，flowers的值仍是(violet buttercup)；它拥有violet的cons cell地址。这也不会改变任何之前的cons cells；他们仍然在那里。

就这样，在Lisp里获取list的CDR，将获取到连续的cons cell串中的第二个；获取list的CAR，将得到第一个。将cons将一个新元素连接到list上，你将会把新元素的cons cell添加到list的前面。

cons cell串的最后一个指向什么？它指向空list，nil。

把符号看作抽屉柜

前面章节曾提示过把符号（symbol）想像成抽屉柜。函数定义放到一个抽屉里，变量放到了另一个，等等。

实际上放在各个抽屉里的是值或函数定义的地址。

（另外，符号有一个抽屉存放属性列表（property list），它用于记录其它信息。）

            Chest of Drawers            Contents of Drawers

            __   o0O0o   __
          /                 \
         ---------------------
        |    directions to    |            [map to]
        |     symbol name     |             bouquet
        |                     |
        +---------------------+
        |    directions to    |
        |  symbol definition  |             [none]
        |                     |
        +---------------------+
        |    directions to    |            [map to]
        |    variable value   |             (rose violet buttercup)
        |                     |
        +---------------------+
        |    directions to    |
        |    property list    |             [not described here]
        |                     |
        +---------------------+
        |/                   \|