程序的本质复杂性和元语言抽象

程序的本质复杂性和元语言抽象

(感谢 @文艺复兴记(todd) 投递此文)

组件复用技术的局限性

常听到有人讲“我写代码很讲究,一直严格遵循DRY原则,把重复使用的功能都封装成可复用的组件,使得代码简短优雅,同时也易于理解和维护”。显然,DRY原则和组件复用技术是最常见的改善代码质量的方法,不过,在我看来以这类方法为指导,能帮助我们写出“不错的程序”,但还不足以帮助我们写出简短、优雅、易理解、易维护的“好程序”。对于熟悉Martin Fowler《重构》和GoF《设计模式》的程序员,我常常提出这样一个问题帮助他们进一步加深对程序的理解:

如果目标是代码“简短、优雅、易理解、易维护”,组件复用技术是最好的方法吗?这种方法有没有根本性的局限?

虽然基于函数、类等形式的组件复用技术从一定程度上消除了冗余,提升了代码的抽象层次,但是这种技术却有着本质的局限性,其根源在于 每种组件形式都代表了特定的抽象维度,组件复用只能在其维度上进行抽象层次的提升。比如,我们可以把常用的HashMap等功能封装为类库,但是不管怎么封装复用类永远是类,封装虽然提升了代码的抽象层次,但是它永远不会变成Lambda,而实际问题所代表的抽象维度往往与之并不匹配。

以常见的二进制消息的解析为例,组件复用技术所能做到的只是把读取字节,检查约束,计算CRC等功能封装成函数,这是远远不够的。比如,下面的表格定义了二进制消息X的格式:

Message X:
--------------------------------------------------------
| ID |  Name           | Type    | Size | Constraints  |
--------------------------------------------------------
| 1  | message type    | int     | 1    | = 0x01       |
--------------------------------------------------------
| 2  | payload size    | int     | 2    | > 0          |
--------------------------------------------------------
| 3  | payload         | bytes   | <2>  |              |
--------------------------------------------------------
| 4  | CRC             | int     | 4    |              |
--------------------------------------------------------

它的解析函数大概是这个样子:

bool parse_message_x(char* data, int32 size, MessageX& x) {
    char *ptr = data;
    if (ptr + sizeof(int8) <= data + size) {
        x.message_type = read_int8(ptr);
        if (0x01 != x.message_type) return false;
        ptr += sizeof(int8);
    } else {
        return false;
    }
    if (ptr + sizeof(int16) <= data + size) {
        x.payload_size = read_int16(ptr);
        ptr += sizeof(int16);
    } else {
        return false;
    }
    if (ptr + x.payload_size <= data + size) {
        x.payload = new int8[x.payload_size];
        read(ptr, x.payload, x.payload_size);
        ptr += x.payload_size;
    } else {
        return false;
    }
    if (ptr + sizeof(int32) <= data + size) {
        x.crc = read_int32(ptr);
        ptr += sizeof(int32);
    } else {
        delete x.payload;
        return false;
    }
    if (crc(data, sizeof(int8) + sizeof(int16) + x.payload_size) != x.crc) {
        delete x.payload;
        return false;
    }
    return true;
}

很明显,虽然消息X的定义非常简单,但是它的解析函数却显得很繁琐,需要小心翼翼地处理很多细节。在处理其他消息Y时,虽然虽然Y和X很相似,但是却不得不再次在解析过程中处理这些细节,就是组件复用方法的局限性,它只能帮我们按照函数或者类的语义把功能封装成可复用的组件,但是消息的结构特征既不是函数也不是类,这就是抽象维度的失配。

程序的本质复杂性

上面分析了组件复用技术有着根本性的局限性,现在我们要进一步思考:

如果目标还是代码“简短、优雅、易理解、易维护”,那么代码优化是否有一个理论极限?这个极限是由什么决定的?普通代码比起最优代码多出来的“冗余部分”到底干了些什么事情?

回答这个问题要从程序的本质说起。Pascal语言之父Niklaus Wirth在70年代提出:Program = Data Structure + Algorithm,随后逻辑学家和计算机科学家R Kowalski进一步提出:Algorithm = Logic + Control。谁更深刻更有启发性?当然是后者!而且我认为数据结构和算法都属于控制策略,综合二位的观点,加上我自己的理解,程序的本质是:Program = Logic + Control。换句话说,程序包含了逻辑和控制两个维度。

逻辑就是问题的定义,比如,对于排序问题来讲,逻辑就是“什么叫做有序,什么叫大于,什么叫小于,什么叫相等”?控制就是如何合理地安排时间和空间资源去实现逻辑。逻辑是程序的灵魂,它定义了程序的本质;控制是为逻辑服务的,是非本质的,可以变化的,如同排序有几十种不同的方法,时间空间效率各不相同,可以根据需要采用不同的实现。

程序的复杂性包含了本质复杂性和非本质复杂性两个方面。套用这里的术语, 程序的本质复杂性就是逻辑,非本质复杂性就是控制。逻辑决定了代码复杂性的下限,也就是说不管怎么做代码优化,Office程序永远比Notepad程序复杂,这是因为前者的逻辑就更为复杂。如果要代码简洁优雅,任何语言和技术所能做的只是尽量接近这个本质复杂性,而不可能超越这个理论下限。

理解”程序的本质复杂性是由逻辑决定的”从理论上为我们指明了代码优化的方向:让逻辑和控制这两个维度保持正交关系。来看Java的Collections.sort方法的例子:

interface Comparator<T> {
    int compare(T o1, T o2);
}
public static <T> void sort(List<T> list, Comparator<? super T> comparator)

使用者只关心逻辑部份,即提供一个Comparator对象表明序在类型T上的定义;控制的部分完全交给方法实现者,可以有多种不同的实现,这就是逻辑和控制解耦。同时,我们也可以断定,这个设计已经达到了代码优化的理论极限,不会有本质上比它更简洁的设计(忽略相同语义的语法差异),为什么?因为逻辑决定了它的本质复杂度,Comparator和Collections.sort的定义完全是逻辑的体现,不包含任何非本质的控制部分。

另外需要强调的是,上面讲的“控制是非本质复杂性”并不是说控制不重要,控制往往直接决定了程序的性能,当我们因为性能等原因必须采用某种控制的时候,实际上被固化的控制策略也是一种逻辑。比如,当你的需求是“从进程�