11.1 垃圾
垃圾（garbage）指的是已分配但是不再需要的内存。典型的编程语言的运行时系统采用两种不同的内存分配方式。一种是分配给环境；这种分配方式要和静态作用域保持一致，所以它只需要支持推入（push）和弹出（pop）操作。函数调用返回时，为其环境分配的空间也被返回，供后续函数使用，看似没有成本。【注释】与之相对，在贮存中分配的内存必须伴随某个值的一生，可能要超过其创建位置的作用域——事实上，它可能一直存活下去。因此，我们需要不同的策略来回收在贮存中分配空间所产生的垃圾。
并非没有成本。硬件必须执行“弹出”指令。这不见得就一定比其他内存管理策略更高效。
空间回收的方法有很多，大体可以分到两个阵营中：人工和自动。人工的方式依赖于开发者能够了解内存的使用，并正确的释放不需要的内存。一般认为，人并不擅长做这种事（虽然在某些情况下，人类拥有机器所无法获取的知识）。因此，几十年来，自动化的方法越来越普及。
11.2 什么样的垃圾回收是“正确的”？
垃圾回收既不应该太早地收回空间（可靠性，soundness）也不能太晚（完备性，completeness）。虽然两者都可以被视为缺陷，但是它们的影响并不是对称的：可以说，过早收回糟糕得多。这是因为，如果过早回收了某个贮存地址，计算将继续，并可能将其他数据写入该地址，从而访问到无意义的数据。往好了说，这会导致程序不正确，极端情况下后果更严重，比如可能会导致安全问题。反之，过迟收回会导致性能损失，并且可能最终导致程序终止，尽管此时理论上存在理论上可用的内存。这种性能损失以及程序过早终止很令人讨厌，在某些关键任务系统中可能会导致重大问题，不过，至少程序不会进行无意义的运算。
理想情况下，我们希望拥有所有的这三项：自动化（automation），可靠性和完备性。然而，这里我们面对的是不可兼得的情形，最多只能选择两项。理想的人类能够做到可靠性和完备性，但实践中实现其中一个都很少见。【注释】计算机可以实现自动化，同时可以提供可靠性和完备性中的一个，但可计算性论证表明，自动化的计算过程不能同时达成这两者。实践中，自动化技术一般选择实现可靠性，出于以下原因：（a）它造成的损害最小；（b）它相对更容易实现；（c）在添加一些人工帮助的情况下，可以接近完备性。
你当然是完美的，但是你的程序员同行呢？顺便说一下，经济学理论在等你验证呢。
11.3 人工回收
人工的最彻底的方式是将所有内存回收交由人操作。例如，在C语言中提供了两个基本指令：malloc用于分配内存，free用于释放内存。malloc的输入是（内存的）大小，返回是对贮存的引用；free的输入是这种引用，释放其占用的内存。
“在当代欧美语言，"Moloch"摩洛这个词有特定的引申义，指代需要极大牺牲的人物或者事业。”——维基百科，摩洛词条
“我不认为这个名字听起来像malloc是巧合。”——Ian Barland
11.3.1 完全人工回收的代价
先来考虑一下这些操作的复杂度。首先我们假设malloc有个指向贮存的关联寄存器（比如new-loc），每次分配的时候直接获取下一个可用地址。这个模型非常简单——可惜只是看上去简单而已。问题出在当你需要用free释放内存时。如果调用free针对的是最后一次malloc分配的内存，那么没有问题；但是贮存中数据一般不遵堆栈的规律。如果释放的不是最新分配的内存，将会在贮存中留下空洞。空洞会导致碎片化（fragmentation），最坏的情况下，即使贮存中有足够的空间，也无法分配任何对象——许多分割的碎片，没有一个足够大。
练习
原则上，我们可以通过使所有空余空间相邻来解决碎片化的问题。怎么达成这一点？仔细考虑所有的后果，然后描述一下如何手工进行这项工作。
在大多数手动内存管理方案中，碎片化仍然是个不可克服的问题，不过在这个看上去很简单的方案里还有其他东西值得考虑。释放某个值之后会发生什么？运行时系统需要用某种方式记录这块内存可被分配。它是通过维护空闲表——空闲空间的链表——来达成这点的。稍作思考就会想到问题，空闲表存在哪，它的内存又由谁来管理呢？答案是空闲表存放在空闲的内存单元格中，这就意味着内存分配时存在最小分配单元。
那么，原则上，每次malloc现在必须遍历空闲表以找到合适的位置。说“合适”是因为分配者必须做出复杂的决定。遇到第一个匹配的空间就分配呢还是继续找找？而且“匹配”又是怎么定义的呢？应该选取那些大小刚好的空间，还是将大些的空间拆分成小块（从而增加创建不可用的小空间的可能性）？还有其它诸多问题。
程序员希望内存分配高效。【注释1】因此，实践中，分配系统倾向于只使用一组固定的尺寸，通常是2的幂。这样我们就可以不是只维护一个空闲表，而是为每个尺寸（都是2的幂）维护一个空闲表。然后再维护一个指向这些表的数组，位操作可以减小数组索引的代价。当然，这样会浪费一些空间，因为当需要那些不是2的幂尺寸的内存时，最终分配给其的内存尾部将会有空余。（这是计算机科学中经典的取舍(trade-off)：空间换时间）。free需要将释放的内存放到合适的链表中，有时候还需要将较大块的内存分割成小块以为将来的分配做准备。这个模型中的任何部分都不像看上去的那样高效。【注释2】
如果内存分配不够高效，开发者会尝试各种奇技赢巧来重用程序中的值，这会降低代码的清晰性，很有可能会导致错误。
特别地，free并不免费（译注：双关）。
当然，所有这些都基于程序员可以写出可靠（忽略完备）程序的基础上。但是他们做不到。
11.3.2 引用计数
由于完全手工内存回收给程序员带来极大的负担，一些半自动化技术被广为使用，最为人知的便是引用计数（reference counting）。
使用引用计数的方式，每个值都关联一个计数，记录对其引用的个数。程序员负责负责递增和递减这些计数。当计数降为0时，该值的空间可以安全的回收供未来使用。
请注意，上面简单的定义中隐藏了两个重要假设：
- 程序员可以记录每一次引用。回忆一下，别名也是引用。因此，当写出下面的代码时，
(let ([x <some value>])
(let ([y x])
注：本文内容来自互联网，旨在为开发者提供分享、交流的平台。如有涉及文章版权等事宜，请你联系站长进行处理。