❶ 如何阅读和学习《计算机程序设计艺术（TAOCP）》

哦，上帝！《The Art of Computer Programming》引那位出名的王垠对TAOCP的评论： 本来早就想想写一个对于Knuth的The Art of Computer Programming的看法。 没想到一去Amazon就找到一个同类 关于Knuth的 TAOCP，我想，大部分人声称看了他的书，或者买了他的书，不过是作为一种炫耀的资本或者摆设。我对门的同学几年前就买了一套三本，全新的精装本，花了 200多块钱。可是呢，他从来就没看。我把它借过来，看了几页就放在那里没有看了。我哪有时间看他用那些一个字节6位的机器语言实现简单的链表！有一天一个师弟走进来，看到那套书在我书架上，显示出一种敬畏感：“挖！师兄！你好牛啊！居然看这么高深的书！” 我一愣。嗯，不错嘛，这套书放在书架上可以让人对我刮目相看。这恐怕就是它对很多人的实际作用。还有人可以帮助神化这套书，同时也神化自己，比如他可以这么说：“谁要是看完了Don Knuth的 The Art of Computer Programming 我就雇用他！” 这样可以显得比一般看过书的人还要高一等。据说Bill Gates就是这么做的。我怀疑他自己看完过没有。 我讨厌这套书的一个原因就是Knuth故意用一个叫 MIX 的处理器的机器语言来写这本书。虽然在新版的书里他设计了一种新的处理器 MMIX，但是换汤不换药。他以为一部“永恒”的计算机编程书不应该使用高级语言，因为它们很容易过时。但是他错了，机器语言恰恰是最容易过时的东西，看看现在有多少牌子的更新换代的处理器就知道。而世界上确实存在非常高级的语言从60年代到现在都没有过时。我预言，MMIX会在不久的将来被淘汰。很好笑的是MMIX是在MIX上加了一个“M”，代表Millennium（千禧年）。关于它的专著也起名为 MMIXware---A RISC Computer for the Third Millennium。一千年甚至短短一百年，几十年以后，计算机还是不是二进制的集成电路都说不清楚，况且这个处理器其实就是从别的处理器比如RISC II, Sparc之类的捡了一点东西，没有什么大的创新。他就把这个处理器的模拟程序印在纸上卖，曰：“一个优秀的程序要像一部好的小说一样容易读懂。一个优秀的程序员会在将来拿到普利策奖。” 用机器语言写一点初级的计算机入门部分还可以，但是用来写整整一部书未免容易让读者只见树木不见森林了。看TAOCP最容易出现的一种现象就是，“哇！原来这个程序可以这么写。” 但是你不知道为啥那么写。虽然可以知道一些底层的原因，但是最根本的原理，读者始终不会明白。就像看清楚了一张图片上的每一个像素，却认不出图片上其实是一个熟人。看清楚了棋盘上每一个棋子能走的地方，却不能赢棋。Dijkstra 说计算科学不应该被叫做"computer science"，就像外科手术不应该叫做"knife science"。可是这关Knuth什么事呢，他的书名叫做 The Art of... 再说他的支票吧…… 很多人拿了Knuth的支票就作为一种可以炫耀的东西。以前我就看到一个Cambridge的教授主页上挂着一个Knuth支票的照片。Knuth的支票真的可以作为炫耀的资本吗？告诉你们，我找到的错误都是typo而已，没想到他也给我支票。谁叫他打字不小心，Millennium都能打成 Millenium？嘿！我凑足了一顿饭钱的支票时就想去中国银行兑现，准备换了钱大吃一顿。可是银行的职员告诉我，他们必须把支票寄回美国才能拿到现金，办理这件事的费用大大高于支票本身的价值！所以Knuth相当于给我一些空头支票。Damn！早该想到的，他为什么不往大家的信用卡上面转账，而使用支票这种过时的东西！他明显觉得有他签名的支票，肯定谁也不会拿去兑现，甚至装裱在相框里作为纪念。hmmm... 算你狠~ 好了，啰里啰唆。还是看看这个别人写的书评。White elephant，这确实道出了我对这套书的感觉。 (但是评价者有些观点我不能苟同，比如“O(n)表示法足够了”。) 希望以后对 paper 也有这种公开的 comments！ Dan Friedman 的故事 (4)——C311当我刚从 Cornell 转学到 IU 的时候，Dan Friedman 叫我去上他的研究生程序语言课 B521。我当时以自己在 Cornell 上过程序语言课程为由，想不去上他的课。Friedman 把我叫到他的办公室，让我在他旁边坐下来，和蔼的对我说：“王垠，我知道你在 Cornell 上过这种课。我也知道 Cornell 是比 IU 好很多的学校。可是每个老师的教学方法都是不一样的，你应该来上我的课。我和我的朋友们在这里做教授，不是因为喜欢这个学校，而是因为我们的家人和朋友都在这里。”后来由于跟 Amr Sabry（我现在的导师）的课程 B522 时间重合，他特别安排我坐在本科生的 C311 的课堂上，却拿研究生课程的学分。后来发现，这两门课的内容基本没有区别，只不过研究生的作业要多一些。 在第一堂课上，他说了一句让我记忆至今的话：“《The Little Schemer》和《Essentials of Programming Languages》是这门课的参考教材，但是我上课从来不讲我的书里的内容。”刚一开始，我就发现这门课跟我在 Cornell 学到的东西很不一样。虽然有些概念，比如 closure，CPS，我在 Cornell 都学过，在他的课堂上，我却看到这些概念完全不同的一面，以至于我觉得其实我之前完全不懂这些概念！这是因为在 Cornell 学到这些东西的时候只是用来应付作业，而在 Friedman 的课上，我利用它们来完成有实际意义的目标，所以才真正的体会到这些概念的内涵和价值。 一个例子就是课程进入到没几个星期的时候，我们开始写解释器来执行简单的 Scheme 程序。然后我们把这个解释器进行 CPS 变换，引入全局变量作为"寄存器" (register)，把 CPS 产生的 continuation 转换成数据结构（也就是堆栈）。最后我们得到的是一个抽象机 (abstract machine)，而这在本质上相当于一个真实机器里的中央处理器（CPU）或者虚拟机（比如 JVM）。所以我们其实从无到有，“发明”了 CPU！从这里，我才真正的理解到寄存器，堆栈等的本质，以及我们为什么需要它们。我才真正的明白了，冯诺依曼体系构架为什么要设计成这个样子。后来他让我们去看一篇他的好朋友 Olivier Danvy 的论文，讲述如何从各种不同的解释器经过 CPS 变换得出不同种类的抽象机模型。这是我第一次感觉到程序语言的理论对于现实世界的巨大威力，也让我理解到，机器并不是计算的本质。机器可以用任何可行的技术实现，比如集成电路，激光，量子，分子，基因…… 但是无论用什么作为机器的材料，我们所要表达的语义，也就是计算的本质，却是不变的。 而这些还不是我那届 C311 全部的内容。后半学期，我们开始学习 miniKanren，一种他自己设计的用于教学的逻辑式语言 (logic programming language)。这个语言类似 Prolog，但是它把 Prolog 的很多缺点给去掉了，而且变得更加容易理解。教材是免费送给我们的《The Reasoned Schemer》。在书的最后，两页纸的篇幅，就是整个 miniKanren 语言的实现！我学得比较快，后来就开始捣鼓这个实现，把有些部分重新设计了一下，然后加入了一些我想要的功能。这样的教学，给了我设计逻辑式语言的能力，而不只是停留于一个使用者。这是学习 Prolog 不可能做到的事情，因为 Prolog 实现的复杂性，会让初学者无从下手，只能停留在使用者的阶段。 我很幸运当初听了他的话，去上了这门课，否则我就不会是今天的我。 谁是真正的程序语言专家Knuth 也曾有类似的说法：“要是看不懂 TAOCP，就别当程序员。”他总是被誉为“计算机科学的神”，在他的演讲里大谈文学，艺术，上帝和宗教，给人陡增神秘感。他总是说程序员应该学习机器语言，而不是高级语言，机器才是不变的真理。但是 Knuth 却不是从科学的角度来看这个问题，而只是他个人的偏见。当他看到 Fortran, Lisp, ALGOL, Pascal, C, C++, Java 这些语言的发展仿佛没有尽头的时候，他并没有理解其中不变的原理。在程序语言的设计上，他不是一个强者。他很有可能根本不理解 lambda calculus 和类型理论，否则他不会设计出像 TeX 那样毫无章法的语言。TeX 排版的质量无可厚非，但是到了1978年还仍然采用程序语言专家们早已深恶痛绝的 dynamic scoping，再加上其它一些蹩脚的设计，说明他对程序语言理论缺乏理解。实际上 TeX 含有一个图灵完备的扩展语言，是因为 Knuth 点赞了 Guy Steele（Scheme 的发明者）的建议，然而 Knuth 却没有把它设计好。 Knuth 觉得机器是不变的真理，所以他坚持用机器语言来写作 TAOCP。但是由于机器语言缺乏抽象，程序员没法专注于真正的问题。使用机器语言来描述算法，会把本来很简单的问题都显得高深难懂，仿佛这书永远也看不完。有多少人真正的看过 TAOCP 呢？恐怕大部分人把这套书买回去，只是把它们摆在书架上做面子。只要有人说机器语言太难懂，这些人就会说你自己不够聪明，不配做程序员。而其实呢，他们自己都没看过。 机器不是计算的本质这个事实，很多人包括 Dijkstra，早就看到了。他说：“计算机科学是个错误的名字，因为它不是计算机的科学，这就像外科手术不是刀子的科学。”而这是几乎每一个程序语言专家都明白的道理。在他们的眼里，这不再是道听途说或者个人观点，而是可以用逻辑来证明的事实。真正明白计算本质的人，可以设计出全新的硬件来来满足语义的需要，而不是受控于处理器的设计。他们甚至可以超越集成电路，而使用另外的技术来制造机器。这些都说明，计算其实是独立于机器的。 有不好的想法不要紧，但是如果把不好的想法硬说成是好的，那就会阻碍历史发展了。我并不否认 Knuth 和 Ritchie 对算法，排版和操作系统的重要贡献，但是由于他们以及他们崇拜者经常在有关语言的事情上误导群众，所以觉得有必要指出他们的一些局限性。Linus Torvalds, Guido van Rossum, Eric Raymond, Paul Graham 也经常发表对语言的评论，被很多人奉为圣旨，但其实他们言论里面很少有真知灼见。 其实我要说的不过是，通常程序员们膜拜的偶像，大部分都不是真正的程序语言专家。希望你不要觉得这是危言耸听，实际上这些是大部分世界级的计算机科学家们很多年前就知道的事情。