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

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

(感谢 @文艺复兴记(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的定义完全是逻辑的体现,不包含任何非本质的控制部分。

另外需要强调的是,上面讲的“控制是非本质复杂性”并不是说控制不重要,控制往往直接决定了程序的性能,当我们因为性能等原因必须采用某种控制的时候,实际上被固化的控制策略也是一种逻辑。比如,当你的需求是“从进程虚拟地址ptr1拷贝1024个字节到地址ptr2“,那么它就是问题的定义,它就是逻辑,这时,提供进程虚拟地址直接访问语义的底层语言就与之完全匹配,反而是更高层次的语言对这个需求无能为力。

介绍了逻辑和控制的关系,可能很多朋友已经开始意识到了上面二进制文件解析实现的问题在哪里,其实这也是 绝大多数程序不够简洁优雅的根本原因:逻辑与控制耦合。上面那个消息定义表格就是不包含控制的纯逻辑,我相信即使不是程序员也能读懂它;而相应的代码把逻辑和控制搅在一起之后就不那么容易读懂了。

熟悉OOP和GoF设计模式的朋友可能会把“逻辑与控制解耦”与经常听说的“接口和实现解耦”联系在一起,他们是不是一回事呢?其实,把这里所说的逻辑和OOP中的接口划等号是似是而非的, 而GoF设计模式最大的问题就在于有意无意地让人们以为“what就是interface, interface就是what”,很多朋友一想到要表达what,要抽象,马上写个接口出来,这就是潜移默化的惯性思维,自己根本意识不到问题在哪里。其实,接口和前面提到的组件复用技术一样,同样受限于特定的抽象维度,它不是表达逻辑的通用方法,比如,我们无法把二进制文件格式特征用接口来表示。

另外,我们熟悉的许多GoF模式以“逻辑与控制解耦”的观点来看,都不是最优的。比如,很多时候Observer模式都是典型的以控制代逻辑,来看一个例子:

对于某网页的超链接,要求其颜色随着状态不同而变化,点击之前的颜色是#FF0000,点击后颜色变成#00FF00。

基于Observer模式的实现是这样的:

[javascript]
$(a).css(‘color’, ‘#FF0000’);

$(a).click(function() {
$(this).css(‘color’, ‘#00FF00’);
});
[/javascript]

而基于纯CSS的实现是这样的:

a:link {color: #FF0000}
a:visited {color: #00FF00}

通过对比,您看出二者的差别了吗?显然,Observer模式包含了非本质的控制,而CSS是只包含逻辑。理论上讲,CSS能做的事情,JavaScript都能通过控制做到,那么为什么浏览器的设计者要引入CSS呢,这对我们有何启发呢?

元语言抽象

好的,我们继续思考下面这个问题:

逻辑决定了程序的本质复杂性,但接口不是表达逻辑的通用方式,那么是否存在表达逻辑的通用方式呢?

答案是:有!这就是元(Meta),包括元语言(Meta Language)和元数据(Meta Data)两个方面。元并不神秘,我们通常所说的配置就是元,元语言就是配置的语法和语义,元数据就是具体的配置,它们之间的关系就是C语言和C程序之间的关系;但是,同时元又非常神奇,因为元既是数据也是代码,在表达逻辑和语义方面具有无与伦比的灵活性。至此,我们终于找到了让代码变得简洁、优雅、易理解、易维护的终极方法,这就是: 通过元语言抽象让逻辑和控制彻底解耦

比如,对于二进制消息解析,经典的做法是类似Google的Protocol Buffers,把消息结构特征抽象出来,定义消息描述元语言,再通过元数据描述消息结构。下面是Protocol Buffers元数据的例子,这个元数据是纯逻辑的表达,它的复杂度体现的是消息结构的本质复杂度,而如何序列化和解析这些控制相关的部分被Protocol Buffers编译器隐藏起来了。

message Person {
  required int32 id = 1;
  required string name = 2;
  optional string email = 3;
}

元语言解决了逻辑表达问题,但是最终要与控制相结合成为具体实现,这就是元语言到目标语言的映射问题。通常有这两种方法:

1) 元编程(Meta Programming),开发从元语言到目标语言的编译器,将元数据编译为目标程序代码;

2) 元驱动编程(Meta Driven Programming),直接在目标语言中实现元语言的解释器。

这两种方法各有优势,元编程由于有静态编译阶段,一般产生的目标程序代码性能更好,但是这种方式混合了两个层次的代码,增加了代码配置管理的难度,一般还需要同时配备Build脚本把整个代码生成自动集成到Build过程中,此外,和IDE的集成也是问题;元驱动编程则相反,没有静态编译过程,元语言代码是动态解析的,所以性能上有损失,但是更加灵活,开发和代码配置管理的难度也更小。除非是性能要求非常高的场合,我推荐的是元驱动编程,因为它更轻量,更易于与目标语言结合。

下面是用元驱动编程解决二进制消息解析问题的例子,meta_message_x是元数据,parse_message是解释器:

[javascript]
var meta_message_x = {
id: ‘x’,
fields: [
{ name: ‘message_type’, type: int8, value: 0x01 },
{ name: ‘payload_size’, type: int16 },
{ name: ‘payload’, type: bytes, size: ‘$payload_size’ },
{ name: ‘crc’, type: crc32, source: [‘message_type’, ‘payload_size’, ‘payload’] }
]
}

var message_x = parse_message(meta_message_x, data, size);
[/javascript]

这段代码我用的是JavaScript语法,因为对于支持Literal的类似JSON对象表示的语言中,实现元驱动编程最为简单。如果是Java或C++语言,语法上稍微繁琐一点,不过本质上是一样的,或者引入JSON配置文件,然后解析配置,或者定义MessageConfig类,直接把这个类对象作为配置信息。

二进制文件解析问题是一个经典问题,有Protocol Buffers、Android AIDL等大量的实例,所以很多人能想到引入消息定义元语言,但是如果我们把问题稍微变换,能想到采用这种方法的人就不多了。来看下面这个问题:

某网站有新用户注册、用户信息更新,和个性设置等Web表单。出于性能和用户体验的考虑,在用户点击提交表单时,会先进行浏览器端的验证,比如:name字段至少3个字符,password字段至少8个字符,并且和repeat password要一致,email要符合邮箱格式;通过浏览器端验证以后才通过HTTP请求提交到服务器。

普通的实现是这个样子的:

[javascript]
function check_form_x() {
var name = $(‘#name’).val();
if (null == name || name.length <= 3) {
return { status : 1, message: ‘Invalid name’ };
}

var password = $(‘#password’).val();
if (null == password || password.length <= 8) {
return { status : 2, message: ‘Invalid password’ };
}

var repeat_password = $(‘#repeat_password’).val();
if (repeat_password != password.length) {
return { status : 3, message: ‘Password and repeat password mismatch’ };
}

var email = $(‘#email’).val();
if (check_email_format(email)) {
return { status : 4, message: ‘Invalid email’ };
}

return { status : 0, message: ‘OK’ };

}
[/javascript]

上面的实现就是按照组建复用的思想封装了一下检测email格式之类的通用函数,这和刚才的二进制消息解析非常相似,没法在不同的表单之间进行大规模复用,很多细节都必须被重复编写。下面是用元语言抽象改进后的做法:

[javascript]
var meta_create_user = {
form_id : ‘create_user’,
fields : [
{ id : ‘name’, type : ‘text’, min_length : 3 },
{ id : ‘password’, type : ‘password’, min_length : 8 },
{ id : ‘repeat-password’, type : ‘password’, min_length : 8 },
{ id : ’email’, type : ’email’ }
]
};

var r = check_form(meta_create_user);
[/javascript]

通过定义表单属性元语言,整个逻辑顿时清晰了,细节的处理只需要在check_form中编写一次,完全实现了“简短、优雅、易理解、以维护”的目标。其实,不仅Web表单验证可以通过元语言描述,整个Web页面从布局到功能全部都可以通过一个元对象描述,完全将逻辑和控制解耦。此外,我编写的用于解析命令行参数的lineparser.js库也是基于元语言的,有兴趣的朋友可以参考并对比它和其他命令行解析库的设计差异。

最后,我们再来从代码长度的角度来分析一下元驱动编程和普通方法之间的差异。假设一个功能在系统中出现了n次,对于普通方法来讲,由于逻辑和控制的耦合,它的代码量是n * (L + C),而元驱动编程只需要实现一次控制,代码长度是C + n * L,其中L表示逻辑相关的代码量,C表示控制相关的代码量。通常情况下L部分都是一些配置,不容易引入bug,复杂的主要是C的部分,普通方法中C被重复了n次,引入bug的可能性大大增加,同时修改一个bug也可能要改n个地方。所以,对于重复出现的功能,元驱动编程大大减少了代码量,减小了引入bug的可能,并且提高了可维护性。

总结

《人月神话》的作者Fred Brooks曾在80年代阐述了它对于软件复杂性的看法,即著名的No Silver Bullet。他认为不存在一种技术能使得软件开发在生产力、可靠性、简洁性方面提高一个数量级。我不清楚Brooks这一论断详细的背景,但是就个人的开发经验而言,元驱动编程和普通编程方法相比在生产力、可靠性和简洁性方面的确是数量级的提升,在我看来它就是软件开发的银弹!

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

好烂啊有点差凑合看看还不错很精彩 (38 人打了分,平均分: 4.13 )
Loading...

程序的本质复杂性和元语言抽象》的相关评论

  1. 最后那个表单的元语言解法对repeat_password的校验有误,至少还需要一个参量来实现这种不同于其他的逻辑实现
    而且分离逻辑和控制终归是有利有弊的,在控制的重复性不高时,分离的行为本身也是很大的负担

  2. 元编程的思想是不错,但是也是增加思维的抽象度而已.
    具体的说,只要我们把问题中共性的部分抽象出来,加以实现,重复利用,就是提高了抽象度,达到了元编程的能力.其实这就是架构.
    问题是,架构不是一般程序员随便可以实现的,这需要大量经验的积累和case的验证.protobuf等不就是证明吗?

  3. lex&yacc就能干这堆事儿吧?
    人月神话貌似楼主并没有看过? 没有银弹,不仅仅是指技术层面的,它还包含了人脑对于逻辑问题的理解极限,包括团队协作。

  4. 不怎么有道理,程序做的事情一样,2种写法哪种更好,以此文的意思是它所推崇的那种更好,理由是什么?是莫须有的更优雅?
    能量化的唯有谁更快,更多的抽象层次只可能让程序跑的更慢。

  5. 能否把 parse_message(meta_message_x, data, size) 和 check_form(meta_create_user) 的实现写完后发出来看看?
    我不认为你把两个实现都写完后看上去会比原来的更简洁

  6. 文章挺長,學習了!謝謝!感覺自己的代碼寫得太少了,很多地方也沒看懂。

  7. 理想是美好的,现实是骨感的。比如网页的那个例子,仍然存在问题,比如:学习成本:你可以一次写好很多校验方式,但是以后需要再用到的时候(包括看和写,不一定是你自己用到),也要付出一定的代价;“元语言”表达的配置被解析代码绑定了,这也是一种耦合——比如说某天需要修改解析代码的某个情况(特别是发现有BUG的情况),那么所有相关的配置都会受到影响。

  8. 一直在思考“复杂性”相关的问题,但是没有这方面资料。
    这篇文章获益匪浅,特别是“算法=逻辑+控制”这个细分,很有启发。

  9. 作者模糊地使用了”控制”的概念, 片面地把程序 等同于 控制 + 逻辑, 后面又混淆了DSL和元编程、声明式语言和命令式语言的概念,有些不妥. 可以看出作者尝试推出结论的思路, 不过还是有点粗糙,需要继续完善.

  10. 博主最后一段言过了,没有银弹就是说问题存在内在的复杂度无法简化,所以生产率没有办法数量级的提高。
    这种模式匹配固然很好,但是对这个问题也无能为力。

    另外,例子中的匹配也是用了下层库来实现了我们代码中的合法性检查,没有手写而已。
    所以问题又变成了谁的库多,谁封装的好。把逻辑代码尽量放在千锤百炼的库里,减少自己犯错误的机会。

  11. 这里的逻辑应该改为需求,或者问题的定义, 问题的定义也包括实体定义、实体关系。
    控制其实也是逻辑的一部分。
    如果想把问题定义和程序实现部分分开,使用程序 = 逻辑 + 控制的说法是不够完善的。

    按照作者的思路, 把所有的“定义”部分描述出来, 其余使用元数据编程辅助,这其实本身和“重用”并没有关系。
    把解析器封装,用参数匹配不同表单起来也是可以重用的。。。这个例子并没有说服力
    如果说元数据编程为了适应不同和或者可变的数据结构,也仍然会带来很多其他问题。。。

  12. @Tim
    我们有一套系统,400种不同的报表,这些报表的元数据都是在MySQL数据库里的,前端JS就是一个解释器而以,整个逻辑全部在MySQL里面。

  13. 恩,逻辑+控制的概念挺支持的。但后面说的元编程,感觉和《unix编程艺术》中的微软数据编程差不多,其实所谓的简洁、美观只是强调看到的某个层次,但是往往牺牲了其他层次(所谓的“被隐藏”的部分)。就像C一样,编译器的实现和优化比C本身的使用更有难度吧。当然,如果已经存在极限优化的“被隐藏”层,那我们大家倒是可以都用。感觉很多上层的开发语言就是如此,但即使他们也依然存在各种缺陷吧。

  14. 个人不太赞同此篇的观点。 前一半说的比较认同,后一半关于元数据编程,感觉说白了还是代码配置化,逻辑通用化,但其实这个思想大家编程时一直在用,只是不是所有的东西都适合配置化。
    这个观点一点都不新奇,现实中这么实践的例子也比比皆是,比如wpf用xaml来定义ui,这里的xaml就是ui生成器的配置,ui生成器就是解释器
    按这个观点归纳下去,c就是c compiler的配置, 各种解释语言就是其对应的解释器的配置。这种归纳非常有道理,但是,太空泛了,更不是万能的,比如QT就没这种抽象,依然不妨碍它的优秀。
    它还是无法上升到一种编程范式的高度,而上升不到编程范式的高度,也就是一种编程技巧,有适用的地方而已,不能说同种程序设计范式下,用这种思路编程就一定比其他的高明。把这个说是银弹实在是勇气不小……

  15. 前几天做一个C/S模式的东西,开始使用protobuf,后来就觉得太麻烦了,因为很多协议,设计协议,然后解析处理啥的,后来就采用JSON格式,因为方便修改扩展使用boost.property_tree来解析,看了这篇文章以后豁然开朗,property_tree 的处理方式就是属于元驱动方式,的确使用起来比protobuf方便很多。

  16. 前一部分总结的不错,后一部分感觉作者完全是搞混了 Data Driven Programming 和 Meta Driven Programming呀…

    Meta Programming 重点在于可以用Meta Language 进行 Programming,仅仅一个 parse 的例子恐不能作为 Programming 的 佐证

  17. 抽象,谁都喜欢,但是抽象后的代码 如果 没有 预见到需求的变化,以至于无法 符合 变化后需求,修改起来就更痛苦。
    配置化、脚本化也好,元编程也好,前提都是在能容纳需求变化的范围内,才显得高明,
    否则可能只算是 过度设计 的一种了?

  18. 仅仅算是个探讨,对实战的指导意义不大,这种元的抽象不是所有语言都能轻松实现的,至少目前这些系统级语言(C/C++/JAVA)要支持这些东西估计还要有第三方库支持了。

  19. 写得非常好!我从中看到了一点Lisp思想的影子(只能说一点啊,因为Lisp我也只了解一点)。用Lisp的数据与代码同形使得它天生就是元编程语言。大概这就是所谓“即使从来不用lisp编程,它也让我写出更好的代码”

  20. 原理看不懂 但编码实践告诉我 这方法很实用 有点像 模式中的 命令与接口模式

  21. 不,最后一句你错了,软件开发领域,永远没有银弹。

    因为,软件开发最大的问题不是别的东西,不是什么抽象封装、逻辑数据都不是,软件开发最大的问题永远只有一个:细节。

    哪怕是由再叼的理论支撑、再叼的技术构造而成的系统,都会被大量的细节所困扰,不知道什么时候,就可能会被一个小细节问题击垮整个系统。听上去很荒诞吗?你可以参考一下由现代高科技打造的飞机,高度的技术含量,每个零件都是精致昂贵的,然而在飞行中却能被一只鸟击垮。

    软件,想要做的好就必须花费很多的精力,天下没有免费的午餐,如果你只是想做个简单的记事本,随随便便就能做出,任何银弹都不需要。而如果是想做Office,那么你只能花费大量的精力去设计、去编写,不管是用什么叼炸天的方法。想要多好的软件,就必须付出同等的精力。

    因为,你必须要考虑到细节问题,哪怕现在的语言多么吹嘘什么面向对象,细节依然是最大的麻烦,永远的麻烦。而处理细节问题,没有银弹。

  22. 下面非技术性讨论。

    我认为“元驱动编程”这个新造的术语不合适。其他都是“驱动编程”,元或者是英语里的meta,其实是个前缀,起到修饰的作用,不是个名词。例如元编程指是对编程的编程,元数据是指关于数据的数据,而这里的“元驱动”居然不是关于驱动的驱动。

    正如上一篇《数据即代码:元驱动编程》中,作者提出“元驱动编程”其实是“主要业务逻辑都放到配置中,再通过程序解释执行配置的设计方法”,也提到了“配置本质上是一种元数据也是一种DSL”。我举得DSL驱动编程、配置驱动编程都比元驱动要好,甚至元数据驱动都比元驱动更准确。

  23. 很喜欢那个css的例子。顺便说下,在RubyOnRails里面,定义DataModel的时候,用的是和这个文章一样的方法来放constraint,同时因为Ruby的关系,实现起来更容易一些。

  24. 请教一下 @Todd 文中提到的 “元驱动编程” 跟 “声明式编程” 有什么本质的区别?印象中,声明式编程的代码风格也是 一种将 what跟how解耦的方式.

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注