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

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

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

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

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

(setq bouquet '(rose violet buttercup))

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

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

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

如果符号指向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

(eq (cdr (cdr bouquet)) flowers)

到现在为止，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]
        |                     |
        +---------------------+
        |/                   \|