论坛首页 综合技术论坛

Programming in Emacs Lisp笔记(九)List的实现

浏览 2598 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2007-07-03  

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]
| |
+---------------------+
|/ \|

论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics