高德纳(Donald Ervin Knuth):这位所有程序员心中的大神今天80岁了


来自:图灵教育(微信号:turingbooks)

80th 高德纳(Donald Ervin Knuth)

高德纳1938年1月10日出生于美国威斯康辛州,1956年以超高分数高中毕业进入凯斯理工学院。当时高德纳比较纠结是学物理还是音乐,因为高德纳的老爹在教会弹奏管风琴,对他影响比较大,他从小就喜欢弹奏乐器。 最终高德纳选了物理专业,不过,1959年,又改修数学了。毕业的时候,因为过于优秀,学校顺带把硕士学位一起颁给他了。1960年,高德纳去加州理工学院伯克利分校攻读数学专业博士。


是呢,高德纳本身不是学习计算机专业的,他接触的第一台计算机是IBM 650。那时候他大学一年级,此后才开始自学捯饬计算机和写程序,慢慢变成了编程高手。


1962年1月,Addison-Wesley(目前是培生的子品牌)找到当时读博的高德纳,邀请他为编译器这一新生领域写本书,同年夏他启动了这项计划。不过高德纳跟出版社那边一直没打招呼,约稿后过了四年,高德纳都没动静,编辑不淡定了,跑来催稿......高德纳说刚刚写了3000页的草稿呢,编辑非常之崩溃:说好的一本几百页的书呢?出版社本来打算将高德纳的草稿压缩为一本书出版,专家审读认为草稿的任何一页都是干货,无法再压缩了......于是,计算机史上最疯狂的出版计划诞生了。TAOCP系列原计划出版7卷,已经出版《计算机程序设计艺术 卷1:基本算法》《计算机程序设计艺术 卷2:半数值算法》《计算机程序设计艺术 卷3:排序与查找》《计算机程序设计艺术,卷4A:组合算法》《计算机程序设计艺术:MMIX的增补》。


1974年,美国计算机协会将国际计算机界的至高荣誉“图灵奖”授予了高德纳——此时的高德纳36岁,目前他仍然是最年轻的图灵奖得主。高德纳是当代最著名的计算机科学家,排版软件TeX和字体设计系统Metafont发明人。文学编程概念发明人,WEB与CWEB软件发明人。


1968年,《计算机程序设计艺术 卷1:基本算法》第1版面世,2018 年是卷1出版 50 周年。而今天(美国时间1月10日),是一个很特别的日子,高德纳 80 周岁生日——虽然大神一直在我们心中,但是我们还是想借今天这个机会发一篇文章向大神致敬。


同时,感谢中文版所有译者,翻译这样一本书需要付出的艰辛难以想象: 卷1译者(李伯民、范明、蒋爱军),卷2译者(巫斌、范明),卷3译者(贾洪峰),卷4A译者(李伯民)。感谢各位跟高德纳一起为国内读者谱写计算机巨著的艺术篇章。


从斯坦福大学高德纳的个人主页了解到,1月8日—10日,高德纳跟亲朋挚友在瑞典 Piteå 举行高德纳80周岁生日研讨会  Knuth80: Algorithms, Combinatorics, and Information,研讨会上顶级风琴演奏师Jan Overduin 会演奏高德纳创作 50 多年的乐曲:Fantasia Apocalyptica(音乐是高德纳割舍不下的爱好)。今天的题图来自80岁生日研讨会现场参与者的分享。


另外还有一个好消息,4B英文版预计会在2018年年中出版。


之前图灵教育公众号已经发布几篇高德纳和TAOCP的文章,列出供大家参考:


今天这篇文章跟之前文章的内容不同,整理自《编程人生》,就程序员广为关注的问题,我们来看看高德纳是怎么看的。


另外,今天副图文分享的是一篇高德纳的长访谈,内容非常赞,翻译水准也是相当高,推荐大家收藏和阅读。




崇拜从事大型软件项目的人


在写作《计算机程序设计艺术》期间,因为对当时的排版软件非常不满意,高德纳中断了10年时间,转而编写排版系统TeX。


“通过实际编程,我学到了很多很多。我明白了编程到底会占用我多大一部分精力。事实证明,编程比我想象的要困难得多。我可以兼顾教课和写书两项全职工作,但却无法兼顾教课和编程。编程需要太多精力去关注细节,那会占据我大脑的绝大部分空间,让我无暇顾及其他事情。所以我现在特崇拜那些从事大型软件项目的人——若非亲身实践过,我决不会这么想。


编程和宗教很像


“我觉得编程和宗教很像,每个人心中都有自己的信仰。有些人喜欢强加信仰于他人。有些人不会强加,而是可能会说:虽然我无法证明这东西是最棒的,但我觉得它确实好用,所以我想让别人也尝试一下,并且在试过之后也觉得它不错。不过我不喜欢那种在外面四处转悠、告诉别人应该信仰什么的方式。试图改变别人的信仰是件挺别扭的事。


如果不能自己写库

那编程还有什么乐趣可言呢?


人们会有这样一种奇怪的思想:他们想写自成一体的程序,别人只需设置几个参数,程序就会做他们想要的工作。所以,会有一小部分程序员编写程序库,也会有人给库写用户手册,还有人使用这些库。问题是,如果只是在调用库里的东西,如果不能自己写库,那编程还有什么乐趣可言呢?如果编程这项工作就是找到正确的参数组合,而且找它们又没什么技术含量,那又有谁愿意把编程作为自己的职业呢?


可复用软件过于强调了这句话:“决不能打开盒子去看看里面有什么。”程序里有黑盒是好的,但通常来说,如果能看到盒子里的东西,弄清楚那东西到底是什么,那我们就可以改进它,让它运行得更出色。但现在的世道是,什么都被严格封装起来,仅仅让程序员看到一个封闭的单元,而不让程序员去剖析研究它。程序员唯一能做的,就是把各部分组装起来。所以你的脑子里全都是:调用这个子程序时,参数是x0、 y0、x1、 y1,但调用那个子程序时,参数变成了x0、x1、 y0、 y1。你要把它们一一填写正确,这就是你的工作。


也许2%的程序员热衷文学编程


文学编程基于这样的想法:最合理的表达方法,是以相互关联的形式化与非形式化两种方式来描述同一事物。实际上,文学编程只不过提供了一种能在自然语言和形式化语言之间自由切换,并能把它们结合在一起的天然框架,比方说,在英语和C或Lisp之间。所以对我来说,用这种方式写文档显然更有优势。另一方面,在写程序时,我可以用读者最容易理解,而不是编译器最想要的形式表达出来。


有些人自底向上编写程序,他们不断构造子程序,让程序规模越来越大,而他们的自信也随之逐渐建立起来。还有些人自顶向下编写程序,他们一开始就在考虑:“嗯,这是我要去解决的问题。想解决它的话,我必须先完成这个,再完成那个。”


在编写文学程序时,我可以根据自己的喜好,两者任选其一。我最终写出来的程序几乎总是和我实际思考问题的顺序相一致。我可以在开始的时候先这么想:“这是我要解决的问题,所以我得先解决它,再解决它。”


随后,我还可以换一种思路:“现在,让我们自底向上地构建一些工具。”我们心中时刻牢记着最终达到的目标,但我们可以时而自底向上地构建几个工具,时而自顶向下地解决几个问题。实际上,我们编写文学程序的顺序是:先去解决当前必须解决的问题,再在后续章节里解决下一步要解决的问题。


我开始处理当前最让我头疼但已经下决心要解决的事情。如果我下定决心去做一件事,就会干净利落地把它完成,而不是拖延下去直到火烧眉毛。然而,这种顺序既不同于自顶向下,也不同于自底向上,它是一种心理上的顺序:“接下来完成这件事最让我感到心满意足,可我是否已经做好准备、下定决心去完成它了呢?”对于这种顺序,我们有着比较清楚的了解与认识,因此,能够自由地按照人类易于理解的顺序组织程序,这点对我而言十分重要。


既然这方法这么棒,那为什么到现在还没风靡全球呢?为什么不是每个人都用它来编程?有人曾一针见血地指出这一问题的关键所在,我记不清是谁了,好像是Jon Bentley,大意是这样的:世上只有百分之二的人天生就是程序员,也只有百分之二的人天生就是作家,而Knuth呢,他希望所有人又是天才程序员,又是天才作家。


如何克服烦躁和痛苦

将测试纳入思维框架


程序员们通常倾向于保护自己的劳动结晶,所以大部分人不会尽其所能地去测试——测试让人感到既烦躁又痛苦,高德纳承认编写 TeX 的时候也有这种感觉。但是他是如何做到把测试严格纳入自己的思维框架的呢?必须忘掉自己是程序的作者,就可以充分享受寻找错误带来的乐趣。“我试着想象别的什么人是作者。除了乐趣之外,这样做还很容易让我进入批评别人的模式。我也不知道这是为什么。我的性格特点就是热衷于抨击和挑错。我喜欢跟别人对着干,那种感觉对我来说好像一针强心剂。我不会就那么坐着,附和着说:‘ 啊,是这么回事。那它为什么好使呢?’ 


阅读源代码很让人头疼

怎么办?


很让人头疼,不过为了培养这种能力,头疼也值了。我是怎么做的呢?以前有台计算机,名叫Bunker Ramo 300,别人告诉我,它用的Fortran 编译器速度出奇地快,可谁都不明白其中的原因。我弄到一份这编译器的源代码副本。我连这台计算机的手册都没有,所以,我甚至无法确定它用的机器语言是什么。但是,我把它看成是一个有趣的挑战。我能琢磨出BEGIN在哪儿,有了BEGIN,就可以开始破译。有些操作码的助记符是两字母的,所以我渐渐明白:“这里可能是个装载(load)指令,那里可能是个分支(branch)。”而且我知道,它是个Fortran编译器,所以它有时会查看卡片的第七列,来分辨该行是不是注释。


三个小时过去后,我有点明白这台计算机了。我还发现了一些庞大的分支表。所以说,这编译器就像个谜题,我不断地画着简单的图表,就好像我在国家安全局上班,正在辛辛苦苦地破译密码。但我知道它的速度的确很快,我还知道,它是个Fortran编译器。从有意隐藏信息的角度来说,它没有加密,只不过我手头没有这台计算机的手册,所以它用机器码写出来就如同密码一样。


最后,我终于明白这个编译器为什么如此之快了。不幸的是,这并非因为它的算法出类拔萃,而是因为它用的是非结构化编程,并且代码被人工优化到了极致。


这就是你解决这一类未知谜题的基本方法——先画出表格和示意图,然后通过图表获得一些信息,再做出一个假设。一般来说,在我阅读技术文献时,必然会迎接这种挑战。我试着模仿作者的思路,试着理解文中概念的意义。你阅读别人的材料越多,未来开拓创新的能力就越强,至少在我看来是这样。



高德纳作品中文版

作者:高德纳

译者:李伯民 范明 蒋爱军


《卷1:基本算法(第3版)》讲解基本算法,其中包含了其他各卷都需用到的基本内容。本卷从基本概念开始,然后讲述信息结构,并辅以大量的习题及答案。


作者:高德纳

译者:巫斌 范明

《卷2:半数值算法(第3版)》全面讲解了半数值算法,分“随机数”和“算术”两章。书中总结了主要算法范例及这些算法的基本理论,广泛剖析了计算机程序设计与数值分析间的相互联系。


作者:高德纳

译者:贾洪峰

卷3:排序与查找(第2版)》扩展了卷1中信息结构的内容,主要讲排序和查找。书中对排序和查找算法进行了详细的介绍并对各种算法的效率做了大量的分析。          



《美国科学家》(American Scientist)杂志曾将《计算机程序设计艺术》与爱因斯坦的《相对论》、狄拉克的《量子力学》等书并列为20世纪最重要的12本科学类专著。


比尔·盖茨曾经花几个月研读《计算机程序设计艺术》,并这样对广大程序员说:如果你自以为是一个很好的程序员,请去读读高德纳的《计算机程序设计艺术》吧……要是你真把它读下来了,就毫无疑问可以给我递简历了。


根据著名Common Lisp专家Peter Seibel的访谈笔录成书的《编程人生》,记录了15 位软件先驱的编程生涯。Seibel特别有意思,在访谈每个大牛的时候基本都会问到一个问题:

你觉得《计算机程序设计艺术》这套书怎么样?我在访谈中问过一些人,他们中有些真的从头读到了尾,有些把它放在书架上,在需要时作为参考书查阅,还有些就只是摆在书架上,连碰都不去碰它。


以下大牛都认真研读过高德纳的《计算机程序设计艺术》:

  • 参与创建Common Lisp和Scheme的Guy Steele

  • Smalltalk之母Dan Ingalls

  • 调试大师Bernie Cosell

  • JavaScript宗师Douglas Crockford

  • JavaScript之父Brendan Eich

  • Java大神Joshua Bloch

  • Haskell先驱Simon Peyton Jones

  • 人工智能专家、谷歌研发总监Peter Norvig


关于TAOCP,他们说


➤ Brendan Eich

Knuth 写的《计算机程序设计艺术》,卷1到卷3,我很喜欢,特别是半数值算法那部分,还有双重散列之类的,关于黄金比例的证明则被留做练习题,很有意思。


➤ Joshua Bloch

Knuth的《计算机程序设计艺术》,事实上,我从来没有读完这一套书,没有从头到尾看过。但当我研究某个具体算法的时候,我就去看他会怎么说。往往可以得到我想要的东西,这套书太全面了。


➤ Douglas Crockford

在上大学时,有那么几个月我连房租都没交,就是为了买他的书。我读过这些书,从中得到了不少乐趣,比如在第一卷的索引有个关于拖车的笑话就很好玩。我到现在为止还没能把书上的内容全部搞懂。Knuth对某些地方的研究要比我深入得多,但我还是喜欢这些书并把它们当做参考资料。


➤ Simon Peyton Jones

Don Knuth的《计算机程序设计艺术》系列不是能够一口气读下去的,不是那种书。在某个阶段我多次推荐过这套书。


 Peter Norvig

有段时间我拿它当我的显示器底座,因为它是我最大部头的成套书之一,而且高度恰好合适。我感觉这样很舒服,因为它总在那儿陪着我,而且因为它就在我面前,所以我找参考书的时候就更容易去顺手翻翻它。

Seibel:但你每次想查阅它,还得先把显示器抬起来吗?

Norvig:不用,我那套书是盒装的,你只要使劲抽书就行,也可以只抽其中一本。


 

推荐↓↓↓
算法与数据结构
上一篇:从婚介所到约会软件,爱情算法靠谱吗