zero 的故事 [0] = 它什么也没做

有一个在 Linux 系统中比较容易安装和使用的软件，它叫 zero，寄居于 github 篱下： http://github.com/liyanrui/zero

它之所以叫 zero，是因为它貌似做了一些事，但实质上它什么也没有做。它就像一个讲大道理的人，即使它努力写了一本《道德经》，但是它还是什么也没有做。大道理就是这样的，它看似告诉了你关于一切事物的终极真理，但这种终极真理存在与不存在，对世界的运行可能并没有太大的影响。

这些大道理，其实是作者们讲给自己以及那些像自己的人听的。这样的人，终归是是少数，而且少到了不足以影响世界运行的地步。

zero 讲给自己听的大道理是，程序的文档和程序本身可以放在一起来写。它很单纯的认为，用文本编辑器创建一个文本文件，然后在这份文件中按照某种逻辑顺序，撰写一段程序文档内容，编写一段程序源码，再撰写一段文档内容……这两个过程交替进行，像拧麻花一样，像织毛衣一样，像左右互搏一样，像左脚踩右脚右踩左脚的梯云纵一样，这样就能实现社会和谐，码农安定的美好局面。

按照 zero 的想法，我创建了一份文本文件，名为 km.zero，然后撰写了一段程序文档：

/type{km_init} 函数实现了 $k$ 均值聚类初始化过程，首先从样点集合中随机选取指定数量的样点作为初始种类中心，然后初始化种类树，即对样点集合进行首次分类，其定义如下：

其中， /type{...} 与 $...$ 均为 TeX 排版标记。为程序写文档，总不能用 MS Word 吧？

接下来，编写一段代码：

@ agn_km.c #
<km-init>
static AgnTree *
km_init(AgnList *points, size_t K, AgnArrayEnv *env) {
        size_t n = agn_list_size(points);
        size_t *indices = generate_indices(K, 0, n - 1);
        # 初始化种类中心 -> init_centers @
        # 初始化种类树 -> class_tree @
        agn_array_free(init_centers, NULL);
        free(indices);
        return class_tree;
}
@

其中， @ ... # ， < ... > ， # ... @ 以及 @ 这些奇怪的符号，是 zero 讲给自己听的一些神秘的符号，现在可以不用理睬它们。

接下来，我觉得有必要解释一下 km_init 这个函数的返回值的数据结构，所以继续撰写程序文档：

/type{km_init} 函数的返回结果是种类树，它是 /type{AgnTree} 的一个实例。种类树的结构分为三层，根结点，亦即第一层结点，用于存放样点链表的指针；第二层结点表示种类，存放的数据为种类中心。第三层结点存放分配到相应种类的样点。

如果没有上述文档内容的解释，该怎么理解 km_init 返回的那个 class_tree 是什么东西呢，从它的类型定义能看出来吗？

typedef struct AgnTree {
        struct AgnTree *upper;
        struct AgnTree *next;
        struct AgnTree *lower;
        void *data;
} AgnTree;

从它的类型定义，只能看出来它是一棵树。

从 km_init 函数的全部代码分析吗？此时， km_init 函数还没有完全的写出来，它只是个外壳，它的主体内容目前只是两个占位语句，即：

# 初始化种类中心 -> init_centers @
# 初始化种类树 -> class_tree @

即使 km_init 函数已经完全实现出来了，通过它的源代码能理解 class_tree 表达的事物吗？

static AgnTree *
km_init(AgnList *points, size_t K, AgnArrayEnv *env) {
        size_t n = agn_list_size(points);
        size_t *indices = generate_indices(K, 0, n - 1);
        AgnArray *init_centers = agn_array_alloc(K);
        for (size_t i = 0; i < K; i++) {
                AgnArray *xi = agn_list_index(points, indices[i]);
                init_centers->body[i] = env->copy(xi);
        }
        AgnTree  *class_tree = agn_tree_alloc();
        class_tree->data = points;
        for (size_t i = 0; i < K; i++) {
                agn_tree_prepend(class_tree, init_centers->body[i]);
        }
        assign_points(class_tree, points, env);
        agn_array_free(init_centers, NULL);
        free(indices);
        return class_tree;
}

对我的底细有些了解的人，也许很快就能看出， class_tree 的根结点存储了一个样点链表的指针；第二层结点存储了 K 个随机样点，而且这些样点似乎扮演的是什么什么中心点的角色。那么 class_tree 的结构就是这样了吗，它还有没有第三层结点？这需要看 assign_points 函数的实现方能知道。此时， assign_points 函数我还没有实现……即使它实现了，通过它能理解 class_tree 的结构吗？

static void
assign_points(AgnTree *class_tree, AgnList *points, AgnArrayEnv *env) {
        AgnList *it = points;
        while (it) {
                AgnArray *x = it->data;
                AgnTree *target = class_tree->lower;
                AgnTree *other = class_tree->lower->next;
                for ( ; other != NULL; other = other->next) {
                        if (env->cmp(other->data, target->data, x) >= 0) {
                                target = other;
                        }
                }
                agn_tree_prepend(target, it->data);
                it = it->next;
        }
}

看懂了 assign_points 函数的实现，如果此时还没有忘掉自己原本的意图——弄懂 class_tree 的结构，那么现在应该能够得出结论：

/type{km_init} 函数的返回结果是种类树，它是 /type{AgnTree} 的一个实例。种类树的结构分为三层，根结点，亦即第一层结点，用于存放样点集合；第二层结点表示种类，存放的数据为种类中心。第三层结点存放分配到相应种类的样点。

可是，你所得出的结论，不正是前文中我所撰写的那段程序文档内容吗？

我作为写代码的人，可以在完全实现 km_init 函数以及它的辅助函数 assign_points 之前，就能理解 class_tree 的结构，因为它源于我的设计。但是，作为阅读我所写的代码的人，你需要通读所有代码才能弄明白一件在我看来是再简单也不过的事。

开源，开的是什么？当你煞废心机读懂了一段代码，恍然大悟之后，会有成就感吗？如果你真的觉得这是非常有成就感的事，那么上面的故事就是我向你泼的一碗凉水。

我敢保证，如果你读懂了上述代码，最后得到的充其量是像下面这样的一份代码阅读笔记：

/type{km_init} 函数实现了 $k$ 均值聚类初始化过程，首先从样点集合中随机选取指定
数量的样点作为初始种类中心，然后初始化种类树，即对样点集合进行首次分类，其定义如下：

@ agn_km.c # [C]
<km-init>
static AgnTree *
km_init(AgnList *points, size_t K, AgnArrayEnv *env) {
        size_t n = agn_list_size(points);
        size_t *indices = generate_indices(K, 0, n - 1);
        # 初始化种类中心 -> init_centers @
        # 初始化种类树 -> class_tree @
        agn_array_free(init_centers, NULL);
        free(indices);
        return class_tree;
}
@

/type{km_init} 函数的返回结果是种类树，它是 /type{AgnTree} 的一个实例。种类树的
结构分为三层，根结点，亦即第一层结点，用于存放样点集合；第二层结点表示种类，存放的数
据为种类中心。第三层结点存放分配到相应种类的样点。

/type{assign_points} 函数可从种类树的第二层结点中为之选择相适的结点，并将样点存入
该结点的子结点内，其定义如下：

@ agn_km.c # <km-init> ^+
static void
assign_points(AgnTree *class_tree, AgnList *points, AgnArrayEnv *env) {
        AgnList *it = points;
        while (it) {
                AgnArray *x = it->data;
                AgnTree *target = class_tree->lower;
                AgnTree *other = class_tree->lower->next;
                for ( ; other != NULL; other = other->next) {
                        if (env->cmp(other->data, target->data, x) >= 0) {
                                target = other;
                        }
                }
                agn_tree_prepend(target, it->data);
                it = it->next;
        }
}
@

/noindent 对于两个不同的种类中心，/type{env->cmp} 函数能够比较出它们中哪一个距距
样点更近。基于 /type{env->cmp} 函数便可为当前样点选择距其最近的种类中心，从而将样
点加入相应的种类。

将那些文档内容直接作为代码注释，难道不可以吗？

/* 
 * assign_points 函数可从种类树的第二层结点中为之选择相适的结点，
 * 并将样点存入该结点的子结点内 
 */
static void
assign_points(AgnTree *class_tree, AgnList *points, AgnArrayEnv *env) {
        AgnList *it = points;
        while (it) {
                AgnArray *x = it->data;
                AgnTree *target = class_tree->lower;
                AgnTree *other = class_tree->lower->next;
                for ( ; other != NULL; other = other->next) {
                        if (env->cmp(other->data, target->data, x) >= 0) {
                                target = other;
                        }
                }
                agn_tree_prepend(target, it->data);
                it = it->next;
        }
}

/* 
 * km_init 函数实现了 $k$ 均值聚类初始化过程，首先从样点集合中随机选取指定数量
 * 的样点作为初始种类中心，然后初始化种类树，即对样点集合进行首次分类。函数的返回
 * 结果是种类树，它是 /type{AgnTree} 的一个实例。种类树的结构分为三层，根结点，
 * 亦即第一层结点，用于存放样点集合；第二层结点表示种类，存放的数据为种类中心。第
 * 三层结点存放分配到相应种类的样点。
 */
static AgnTree *
km_init(AgnList *points, size_t K, AgnArrayEnv *env) {
        size_t n = agn_list_size(points);
        size_t *indices = generate_indices(K, 0, n - 1);
        /* 初始化种类中心 */
        AgnArray *init_centers = agn_array_alloc(K);
        for (size_t i = 0; i < K; i++) {
                AgnArray *xi = agn_list_index(points, indices[i]);
                init_centers->body[i] = env->copy(xi);
        }
        /* 初始化种类树 */
        AgnTree  *class_tree = agn_tree_alloc();
        class_tree->data = points;
        for (size_t i = 0; i < K; i++) {
                agn_tree_prepend(class_tree, init_centers->body[i]);
        }
        assign_points(class_tree, points, env);
        agn_array_free(init_centers, NULL);
        free(indices);
        return class_tree;
}

代码中的注释肯定有助于理解代码，然而这些注释之间的却没有什么联系。如果说有联系，也是一种反人类的联系。

我们阅读一份文件，总是习惯自上而下的阅读。这种阅读习惯导致我们先看到了 assign_points 函数的注释及其实现代码，但是我们却被迫的先跳过它，去看下面的 km_init ，在看了 km_init 的注释及代码之后，再回过头来看 assign_points 的实现。之所以如此折腾，是因为函数的摆放位置必须满足编译器的要求——先定义，再调用。于是，为了阅读一份比较长的源代码，我们不得不上下求索去漫漫且修远的函数调用关系，然后顺着这个关系去阅读代码。结果你的得到的依然是类似于上文中的那份代码阅读笔记。

还有一个问题，怎么确定注释的范围？例如：

/* 初始化种类树 */
AgnTree  *class_tree = agn_tree_alloc();
class_tree->data = points;
for (size_t i = 0; i < K; i++) {
        agn_tree_prepend(class_tree, init_centers->body[i]);
}
assign_points(class_tree, points, env);

上述代码中的 assign_points 函数调用语句是否属于 /* 初始化种类树 */ 所注释的代码范围？

zero 用占位语句的方式，可以很自然的确定注释范围。譬如：

@ agn_km.c #
<km-init>
static AgnTree *
km_init(AgnList *points, size_t K, AgnArrayEnv *env) {
        size_t n = agn_list_size(points);
        size_t *indices = generate_indices(K, 0, n - 1);
        # 初始化种类中心 -> init_centers @
        # 初始化种类树 -> class_tree @
        agn_array_free(init_centers, NULL);
        free(indices);
        return class_tree;
}
@

基于随机索引值获取初始种类中心的过程如下：

@ 初始化种类中心 -> init_centers #
AgnArray *init_centers = agn_array_alloc(K);
for (size_t i = 0; i < K; i++) {
        AgnArray *xi = agn_list_index(points, indices[i]);
        init_centers->body[i] = env->copy(xi);
}
@

获取初始种类中心后，便可初始化种类树——将样点集合记录于树的根结点，
将初始种类中心存入树的第二层结点，然后基于初始种类中心，对样点数据
进行分配，存入树的第三层结点：

@ 初始化种类树 -> class_tree #
AgnTree  *class_tree = agn_tree_alloc();
class_tree->data = points;
for (size_t i = 0; i < K; i++) {
        agn_tree_prepend(class_tree, init_centers->body[i]);
}
assign_points(class_tree, points, env);
@

zero 的大道理就是这些。除此之外，它什么也没做。它没有自己的文档标记语言，也没有自己的编程语言。它所讲的道理，也不过是『此两者同出而异名，同谓之玄。玄之又玄，众妙之门』此类虚无缥缈的东西而已。

事实上，zero 本身就构成了一个笑话，它的文档远远落后于它的代码实现。因为我和大部分人一样，觉得写代码要比写文档容易许多。