3.16 垃圾 (Garbages)

有很多原因可以使列表变慢。列表提供了顺序存取而不是随机存取，所以列表取出一个指定的元素比数组慢，同样的原因，录音带取出某些东西比在光盘上慢。电脑内部里， Cons 对象倾向于用指针表示，所以走访一个列表意味着走访一系列的指针，而不是简单地像数组一样增加索引值。但这两个所花的代价与配置及回收 Cons 核 (cons cells)比起来小多了。

自动内存管理(Automatic memory management)是 Lisp 最有价值的特色之一。 Lisp 系统维护着一段內存称之为堆(Heap)。系统持续追踪堆当中没有使用的内存，把这些内存发放给新产生的对象。举例来说，函数 cons ，返回一个新配置的 Cons 对象。从堆中配置内存有时候通称为 consing 。

如果内存永远没有释放， Lisp 会因为创建新对象把内存用完，而必须要关闭。所以系统必须周期性地通过搜索堆 (heap)，寻找不需要再使用的内存。不需要再使用的内存称之为垃圾 (garbage)，而清除垃圾的动作称为垃圾回收 (garbage collection或 GC)。

垃圾是从哪来的？让我们来创造一些垃圾：

> (setf lst (list 'a 'b 'c))
(A B C)
> (setf lst nil)
NIL

一开始我们调用 list ， list 调用 cons ，在堆上配置了一个新的 Cons 对象。在这个情况我们创出三个 Cons 对象。之后当我们把 lst 设为 nil ，我们没有任何方法可以再存取 lst ，列表 (a b c) 。 [5]

因为我们没有任何方法再存取列表，它也有可能是不存在的。我们不再有任何方式可以存取的对象叫做垃圾。系统可以安全地重新使用这三个 Cons 核。

这种管理內存的方法，给程序员带来极大的便利性。你不用显式地配置 (allocate)或释放 (dellocate)內存。这也表示了你不需要处理因为这么做而可能产生的臭虫。內存泄漏 (Memory leaks)以及迷途指针 (dangling pointer)在 Lisp 中根本不可能发生。

但是像任何的科技进步，如果你不小心的话，自动內存管理也有可能对你不利。使用及回收堆所带来的代价有时可以看做 cons 的代价。这是有理的，除非一个程序从来不丢弃任何东西，不然所有的 Cons 对象终究要变成垃圾。 Consing 的问题是，配置空间与清除內存，与程序的常规运作比起来花费昂贵。近期的研究提出了大幅改善內存回收的演算法，但是 consing 总是需要代价的，在某些现有的 Lisp 系统中，代价是昂贵的。

除非你很小心，不然很容易写出过度显式创建 cons 对象的程序。举例来说， remove 需要复制所有的 cons 核，直到最后一个元素从列表中移除。你可以借由使用破坏性的函数避免某些 consing，它试着去重用列表的结构作为参数传给它们。破坏性函数会在 12.4 节讨论。

当写出 cons 很多的程序是如此简单时，我们还是可以写出不使用 cons 的程序。典型的方法是写出一个纯函数风格，使用很多列表的第一版程序。当程序进化时，你可以在代码的关键部分使用破坏性函数以及/或别种数据结构。但这很难给出通用的建议，因为有些 Lisp 实现，內存管理处理得相当好，以致于使用 cons 有时比不使用 cons 还快。这整个议题在 13.4 做更进一步的细部讨论。

无论如何 consing 在原型跟实验时是好的。而且如果你利用了列表给你带来的灵活性，你有较高的可能写出后期可存活下来的程序。