每当我倍感压力以及有很多事情要做的时候，我总是有这样一种反常的反应，那就是希望做一些其他的事情来摆脱这种状况。通常情况下，这些事情都是些我能够编写并实现的独立的小程序。
一天早上，我几乎要被一堆事情给整疯了——我得看一本书、处理一些工作上的事情、还要准备一场Strange
Loop的演讲，然后这时我突然想到：“我该写一个垃圾收集器了”。
是的，我知道那一刻让我看上去有多疯狂。不过我的神经故障却是你实现一段基础的程序语言设计的免费教程！在100行左右毫无新意的c代码中，我设法实现一个基本的标记和扫描模块。
垃圾收集被认为是有更多编程牛人出没的水域之一，但在这里，我会给你一个漂亮的儿童游泳池去玩耍。可能这里面仍然会有一些能手，但至少这会是一个浅水区。
精简、复用、再复用
垃圾收集背后有这样一个基本的观念：编程语言(大多数的)似乎总能访问无限的内存。而开发者可以一直分配、分配再分配——像魔法一样，取之不尽用之不竭。
当然，我们从来都没有无限的内存。所以计算机实现收集的方式就是当机器需要分配一些内存，而内存又不足时，让它收集垃圾。
“垃圾(Garbage)”在这里表示那些事先分配过但后来不再被使用的内存。而基于对无限内存的幻想，我们需要确保“不再被使用”对于编程语言来说是非常安全的。要知道在你的程序试图访问一些随机的对象时它们却刚好正在得到回收，这可不是一件好玩的事情。
为了实现收集，编程语言需要确保程序不再使用那个对象。如果该程序不能得到一个对象的引用，那么显然它也不会再去使用它。所以关于”in use”的定义事实上非常简单：
- 任何被一个变量引用的对象，仍然在作用域内，就属于”in use”状态。
- 任何被另一个对象引用的对象，仍在使用中，就是”in use”状态。
如果对象A被一个变量引用，而它又有一些地方引用了对象B，那么B就是在使用中(“in use”)，因为你能够通过A来访问到它。
这样到最后的结果就是得到一张可访问的对象图——以一个变量为起点并能够遍历到的所有对象。任何不在图中的对象对于程序来说都是死的，而它的内存也是时候被回收了。
标记并清理
有很多不同的方法可以实现关于查找和回收所有未被使用的对象的操作，但是最简单也是第一个被提出的算法就是”标记-清除”算法。它由John
McCarthy——Lisp(列表处理语言)的发明者提出，所以你现在做的事情就像是与一个古老的神在交流，但希望你别用一些洛夫克拉夫特式的方法——最后以你的大脑和视网膜的完全枯萎而结束。
该算法的工作原理几乎与我们对”可访问性(reachability)”的定义完全一样：
- 从根节点开始，依次遍历整个对象图。每当你访问到一个对象，在上面设置一个”标记(mark)”位，置为true。
- 一旦搞定，找出所有标记位为”not”的对象集，然后删除它们。
对，就是这样。我猜你可能已经想到了，对吧？如果是，那你可能就成为了一位被引用了数百次的文章的作者。所以这件事情的教训就是，想要在CS(计算机科学)领域中出名，你不必开始就搞出一个很牛的东西，你只需要第一个整出来即可，哪怕这玩意看上去很搓。
对象对
在我们落实这两个步骤之前，让我们先做些不相关的准备工作。我们不会为一种语言真正实现一个解释器——没有分析器，字节码、或任何这种愚蠢的东西。但我们确实需要一些少量的代码来创建一些垃圾去收集。
让我们假装我们正在为一种简单的语言编写一个解释器。它是动态类型，并且有两种类型的变量：int 和 pair。 下面是用枚举来标示一个对象的类型：
|
1
2
3
4
|
typedef OBJ_INT, OBJ_PAIR} |
其中，pair可以是任何一对东西，两个int、一个int和另一个pair，什么都可以。随你怎么想都行。因为一个对象在虚拟机中可以是这两个当中的任意一种类型，所以在c中实现对象的典型方法是时用一个标记联合体(tagged
union)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
typedefstructsObject ObjectType union{ /* intvalue; /* struct{ structsObject* structsObject* }; };} |
这个Object结构拥有一个type字段表示它是哪种类型的值——要么是int要么是pair。接下来用一个union来持有这个int或是pair的数据。如果你对c语言很生疏，一个union就是一个结构体，它将字段重叠在内存中。由于一个给定的对象只能是int或是pair，我们没有任何理在一个单独的对象中同时为所有这3个字段分配内存。一个union就搞定。帅吧。
小虚拟机
现在我们可以将其包装在一个小的虚拟机结构中了。它(指虚拟机)在这里的角色是用一个栈来存储在当前作用域内的变量。大多数语言虚拟机要么是基于栈(如JVM和CLR)的，要么是基于寄存器(如Lua)的。但是不管哪种情况，实际上仍然存在这样一个栈。它用来存放在一个表达式中间需要用到的临时变量和局部变量。
我们来简洁明了地建立这个模型，如下：
|
1
2
3
4
5
6
|
|