从Jao的Programming Musing 看到的:Babar Kazar 整理了一堆经典论文。Jao强烈建议每个严肃的程序员读每篇论文,说它们都或多或少有意思。粗粗扫了一下,很多论文都没读过。挑了些俺多少知道一点的介绍。
· An axiomatic basis for computer programming C. A. R. Hoare
Tony Hoare名下的公理化语义(Axiomatic Semantics)。著名的Hoare Triples, P{C}Q, 就是从这里来的。论文不长,双列6页。前辈们就是这样的,6页纸就能开宗立派。不像俺,6页纸连介绍部分都写不周全。哪位老大想知道怎么证明程序正确。前置条件,不变条件,后置条件的妙用,可以用这篇论文开牙。 · Towards a theory of type structure John C. Reynolds
号称经典中的经典。不过也没读过。类型系统一直是编程语言研发的热点,也是非常有趣的方向――类型系统的编程好比让机器证明一系列定理。Reynolds在论文里讨论了什么才是正确的类型结构,和句法正确必须独立于任何具体的类型表达形式,并且给出了带类型的lambda算子的一种扩展,允许他描述用户自定义类型和多态函数。满篇公式,有勇气去读的老大要有心理准备。 · Structured Programming with go to Statements Donald E. Knuth
这篇论文详细结构化编程时讨论了什么时候用goto,什么时候不用goto。高爷爷精细务实的态度非常值得学习。高老太爷用了一辈子goto(MIX和MMIX程序里没了Goto怎么玩儿得转嗫?),岂能轻易被Dijkstra对goto的批评吓退?他仔细探讨了几种不同的程序,考察goto用在那些程序里的利弊。最后得出结论,goto在某些程序里仍然高效实用。虽然论文是30年前的,但里面的分析手法和利用goto的优化技术至今可用。 · An APL Machine 1970 Philip S. Abrams
只知道APL是门有历史意义的语言。顺便说一句,APL这个名字太土了。A Programming Language ==APL。象什么话嘛。
· A Mathematical Theory of Communication Claude Shannon
Bell实验室当年辉煌一时。出了名的叫人做A,结果发明了B。香农老大就是其中杰出代表。香农进了Bell实验室后,居然没人吩咐他干嘛。香农老大转念一想,自己喜欢数学,Bell的生意尽在通讯,干嘛不看看把数学应用到通讯上有什么结果呢?于是1948年这篇论文问世乐。搞通讯的人崩溃乐。现代信息理论就诞生乐。 · Bayesian Networks without Tears
贝叶斯理论热了好几年了。估计还会继续热下去。现在信息越来越多,我们已经审美疲劳。大家渴望的不是信息,而是知识。靠个人的力量把信息提炼成知识太慢,我们需要机器的帮忙。机器学习不热都难,而贝叶斯理论在机器学习里有很好的应用。这篇文章行为浅显,可以轻松读完。对了,那个人人喝骂的微软回形针的智能引擎就是用贝叶斯网络实现的。 · Worse Is Better Richard P. Gabriel
网上脍炙人口的文章。很有教育意义。简单说,worse is better包括下面几点:
-- 简单:设计要简单。但如果接口和实现不能两全,追求实现的简单。文章里给出的Unix vs Multics的例子非常有意思。
-- 正确:程序必须在所有可见的方面正确。其它地方,如果简单和正确不能两全,追求简单。
-- 一致性:程序不能太不一致。但为了简单,可以在少数地方不一致。
-- 完备性:程序应该尽可能照顾到重要的地方,但是不能牺牲简洁。
强烈推荐。 · Why Functional Programming Matters John Hughes
为普通程序员准备的大餐,所以写得通俗。没有公式,也没有拗口的术语。着重展示了Fold和Map的强大抽象能力。不由想到我在大学里修的一门课,编程语言。课是好课,老师是一流老师。课上我们学习了浅显的程序语言理论,重点学习了函数编程(用Common Lisp)和逻辑编程(用Prolog)。这门课彻底改变我对编程的理解,明白了imperative programming和OO programming外还有精彩世界。至今想来都觉得幸运。那门课的作业也很有意思,实现一个驻留内存的数据库,支持关系代数里的常见操作。 · The Early History Of Smalltalk Alan Kay
还有什么好说的呢?Alan Kay这个名字说明一切。30年前Alan Kay就做出来Smalltalk,现在想来仍然让人惊叹。引一段文章Alan Kay评述Smalltalk的话:In computer terms, Smalltalk is a recursion on the notion of computer itself. Instead of dividing "computer stuff" into things each less strong than the whole--like data structures, procedures, and functions which are the usual paraphernalia of programming languages--each Smalltalk object is a recursion on the entire possibilities of the computer. Thus its semantics are a bit like having thousands and thousands of computer all hooked together by a very fast network. Questions of concrete representation can thus be postponed almost indefinitely because we are mainly concerned that the computers behave appropriately, and are interested in particular strategies only if the results are off or come back too slowly. · Computer Programming as an Art Donald E. Knuth
高老太爷在1974年图灵奖仪式上的致词。真是顶尖geek的风范啊。高太爷在文章里解释了问什么他的书取名为《编程的艺术》。明显他对人们谈到编程时把科学置于艺术之上很不了然。高爷爷追溯“艺术”的词源,说艺术的本意就是技能,也是技术和技巧两次的起源。从这里开始,他开始讨论艺术和科学的关联,讨论艺术在编程里的表现形式和意义。用他的话说,他作为教育者和作者的毕生目标就是叫人写美妙的程序。读起来让人心潮彭湃的说。 · Growing a Language Guy Lewis Steele Jr.
好文!G老大在OOPSLA 98上的主题演讲。G老大主张应该采取渐进的方式设计一门可以被自由扩展的语言(LISP圈子里的牛人们多半都持这种观点吧?)。这篇演讲稿针对该观点做了精练地论述。说起进化的观点,可以参看另外一篇好文章,SICP作者之一,Jay Sussman的近作。 · The Complexity of Theorem Proving Procedures Stephen A. Cook
仙风道骨的库克爷爷的成名作。这篇文章一出,好比有人在加州荒漠里发现第一块狗头金,立刻掀起开发加州的狂潮。计算复杂性理论迅速遍地开花。相比这篇论文开创性的贡献,库克因此得到图灵奖不过小小点缀。NP-Complete在这篇论文里被严格定义。更重要的是,库克证明了第一个NP-Complete的问题,SAT(Boolean Satisfiability Problem)。有了SAT,再加上折磨了无数学生的Polynomial Reducibility,无数的NPC问题就出现乐。。。别看俺在这里唾沫横飞,当年做有关计算理论的证明题还是相当吃力的,没有少熬夜。奇怪的是,某一天我给同学讲解我的解法,NPC的相关定义突然变得清晰起来。当初让我绞尽脑汁的证明竟然变得相当机械。后来知道,给人讲解(包括写作)是非常有效地学习方法。怀着备课的目标读文章,假设自己给别人讲解正在读的文章,有助快速理解所读内容。SAT的证明相当复杂,我反正没有耐心读完。