從Jao的Programming
Musing 看到的:Babar Kazar 整理了一
堆經(jīng)典論文。Jao強烈建議每個嚴(yán)肅
的程序員讀每篇論文,說它們都或多或少有意思。粗粗掃了一下,很多論文都沒讀過。挑了些俺多少知道一點的介紹。
· An axiomatic basis for
computer programming C. A. R. Hoare
Tony Hoare名下的公理化語義(Axiomatic Semantics)。著名的Hoare
Triples, P{C}Q, 就是從這里來的。論文不長,雙列6頁。前輩們就是這樣
的,6頁紙就能開宗立派。不像俺,6頁紙連介紹部分都寫不周全。哪位老大想知道怎么證明程序正確。前置條件,不變條件,后置條件的妙用,可
以用這篇論文開牙。
· Communicating Sequential Processes (CSP)
C. A. R. Hoare
Hoare, 又見Hoare。其實也正
常。牛人之牛,就在于成就深廣。鏈接的文檔應(yīng)該不算論文,而算專著。260頁。從1985年推出到現(xiàn)在20多年過去,這本書的引用率在CS歷史上排名第三,可見其影響之深。對并發(fā)編程有強烈興趣的
老大可以去鉆研一把。我沒讀過。
· Towards a theory of type structure
John C. Reynolds
號稱經(jīng)典中的經(jīng)典。不過也沒讀過。類型系統(tǒng)一直是編程語言研發(fā)的熱點,也是
非常有趣的方向――類型系統(tǒng)的編程好比讓機器證明一系列定理。Reynolds在論文
里討論了什么才是正確的類型結(jié)構(gòu),和句法正確必須獨立于任何具體的類型表達形式,并且給出了帶類型的lambda算子的一種
擴展,允許他描述用戶自定義類型和多態(tài)函數(shù)。滿篇公式,有勇氣去讀的老大要有心理準(zhǔn)備。
· Structured Programming with go to
Statements Donald E. Knuth
這篇論文詳細結(jié)構(gòu)化編程時討論了什么時候用goto,什么時候不用goto。高爺爺精細
務(wù)實的態(tài)度非常值得學(xué)習(xí)。高老太爺用了一輩子goto(MIX和MMIX程序里沒了Goto怎么玩兒得轉(zhuǎn)囁?),豈能輕易被Dijkstra對goto的批評嚇退?他仔細探討了幾種不同的程序,考察goto用在那些程序里
的利弊。最后得出結(jié)論,goto在某些程序里仍然高效實用。雖然論文是30年前的,但里面的分析手法和利用goto的優(yōu)化技術(shù)至
今可用。
· An APL Machine 1970
Philip S. Abrams
只知道APL是門有歷史意義的語言。順便說一句,APL這個名字太土
了。A Programming Language ==APL。象什么話嘛。
· A Mathematical Theory of Communication
Claude Shannon
Bell實驗室當(dāng)年輝煌一時。出了名的叫人做A,結(jié)果發(fā)明了B。香農(nóng)老大就是其中
杰出代表。香農(nóng)進了Bell實驗室后,居然沒人吩咐他干嘛。香農(nóng)老大轉(zhuǎn)念一想,自己喜歡數(shù)學(xué),Bell的生意盡在通
訊,干嘛不看看把數(shù)學(xué)應(yīng)用到通訊上有什么結(jié)果呢?于是1948年這篇論文問世樂。搞通訊的人崩潰樂。現(xiàn)代信息理論就誕生樂。
· Bayesian Networks without Tears
貝葉斯理論熱了好幾年了。估計還會繼續(xù)熱下去。現(xiàn)在信息越來越多,我們已經(jīng)
審美疲勞。大家渴望的不是信息,而是知識。靠個人的力量把信息提煉成知識太慢,我們需要機器的幫忙。機器學(xué)習(xí)不熱都難,而貝葉斯理論在機器學(xué)習(xí)里有很好的
應(yīng)用。這篇文章行為淺顯,可以輕松讀完。對了,那個人人喝罵的微軟回形針的智能引擎就是用貝葉斯網(wǎng)絡(luò)實現(xiàn)的。
· A Relational Model of Data for Large
Shared Data Banks 1970 Edgar F. Codd
沒有關(guān)系代數(shù),人類將會怎樣?Codd劃時代的論文奠
定了現(xiàn)代數(shù)據(jù)庫的基礎(chǔ)。嘿嘿,其實俺也沒有讀過這篇論文。順便說一句,現(xiàn)在的ORM試圖把data
schema和對象系統(tǒng)映射起來。問題是,data schema只
是對關(guān)系的一種表達方式而已,還和具體的系統(tǒng)實現(xiàn)有關(guān)。也許把對象間的結(jié)構(gòu)和關(guān)系映射起來才是正道。
· Worse Is Better Richard P. Gabriel
網(wǎng)上膾炙人口的文章。很有教育意義。簡單說,worse is better包括下面幾點:
-- 簡單:設(shè)計要簡單。但如果接口和實現(xiàn)不能兩全,追求實現(xiàn)的簡單。文章
里給出的Unix vs Multics的例子非常有意思。
-- 正確:程序必須在所有可見的方面
正確。其它地方,如果簡單和正確不能兩全,追求簡單。
-- 一致性:程序不能太不一致。但為了簡單,可以在少數(shù)地方不一致。
-- 完備性:程序應(yīng)該盡可能照顧到重要的地方,但是不能犧牲簡潔。
強烈推薦。
· Why Functional Programming Matters
John Hughes
為普通程序員準(zhǔn)備的大餐,所以寫得通俗。沒有公式,也沒有拗口的術(shù)語。著重
展示了Fold和Map的強大抽象能力。不由想到我在大學(xué)里修的一門課,編程語言。課是好課,老師是一流老師。課上我們學(xué)習(xí)
了淺顯的程序語言理論,重點學(xué)習(xí)了函數(shù)編程(用Common Lisp)和邏輯編程(用Prolog)。這門課徹底改變我對編程的理解,明白了imperative programming和OO
programming外還有精彩世界。至今想來都覺得幸運。那門課的作業(yè)
也很有意思,實現(xiàn)一個駐留內(nèi)存的數(shù)據(jù)庫,支持關(guān)系代數(shù)里的常見操作。
· The Early History Of Smalltalk
Alan Kay
還有什么好說的呢?Alan Kay這個名
字說明一切。30年前Alan Kay就做出來Smalltalk,現(xiàn)在想來仍然讓人驚嘆。引一段文章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的風(fēng)范啊。高
太爺在文章里解釋了問什么他的書取名為《編程的藝術(shù)》。明顯他對人們談到編程時把科學(xué)置于藝術(shù)之上很不了然。高爺爺追溯“藝術(shù)”的詞源,說藝術(shù)的本意就是
技能,也是技術(shù)和技巧兩次的起源。從這里開始,他開始討論藝術(shù)和科學(xué)的關(guān)聯(lián),討論藝術(shù)在編程里的表現(xiàn)形式和意義。用他的話說,他作為教育者和作者的畢生目
標(biāo)就是叫人寫美妙的程序。讀起來讓人心潮彭湃的說。
· The next 700 programming languages
Peter J. Landin
42年前的論文,影響深遠。Peter在論文里描述
的函數(shù)語言ISWIM(If You See
What I Mean)現(xiàn)在沒有幾個人知道了。但他對lambda算子的推
崇和對函數(shù)語言的論述影響了后來的函數(shù)語言設(shè)計。
· Growing a Language
Guy Lewis Steele Jr.
好文!G老大在OOPSLA 98上的
主題演講。G老大主張應(yīng)該采取漸進的方式設(shè)計一門可以被自由擴展的語言(LISP圈子里的牛人們
多半都持這種觀點吧?)。這篇演講稿針對該觀點做了精練地論述。說起進化的觀點,可以參看另外一篇好文章,SICP作者之一,Jay
Sussman的近作。
· The Complexity of Theorem Proving
Procedures Stephen A. Cook
仙風(fēng)道骨的庫克爺爺?shù)某擅鳌_@篇文章一出,好比有人在加州荒漠里發(fā)現(xiàn)第一
塊狗頭金,立刻掀起開發(fā)加州的狂潮。計算復(fù)雜性理論迅速遍地開花。相比這篇論文開創(chuàng)性的貢獻,庫克因此得到圖靈獎不過小小點綴。NP-Complete在
這篇論文里被嚴(yán)格定義。更重要的是,庫克證明了第一個NP-Complete的問題,SAT(Boolean
Satisfiability Problem)。有了SAT,再加上折磨了
無數(shù)學(xué)生的Polynomial Reducibility,無數(shù)的NPC問題就出現(xiàn)
樂。。。別看俺在這里唾沫橫飛,當(dāng)年做有關(guān)計算理論的證明題還是相當(dāng)吃力的,沒有少熬夜。奇怪的是,某一天我給同學(xué)講解我的解法,NPC的相關(guān)定義突然
變得清晰起來。當(dāng)初讓我絞盡腦汁的證明竟然變得相當(dāng)機械。后來知道,給人講解(包括寫作)是非常有效地學(xué)習(xí)方法。懷著備課的目標(biāo)讀文章,假設(shè)自己給別人講
解正在讀的文章,有助快速理解所讀內(nèi)容。SAT的證明相當(dāng)復(fù)雜,我反正沒有耐心讀完。
· The Original 'Lambda Papers' Guy
Steele and Gerald Sussman
一系列講解lambda算子和scheme設(shè)計的經(jīng)典
論文。學(xué)scheme時讀過,對理解scheme的設(shè)計理念很有幫助。
·
The UNIX Time-Sharing System
Dennis Ritchie and Ken Thompson
作者不用介紹了吧?這篇文章里介紹的Unix特性早為人熟
知。不過第八部分(VIII Perspective)討論了作者的設(shè)計理念,仍然值得一讀。