高级编程语言的发展
高級編程語言的發(fā)展歷程（一）創(chuàng)始紀(jì)
高級編程語言的發(fā)展歷程（二）虛擬機(jī)的前世今生
高級編程語言的發(fā)展歷程（三）FORTRAN 語言是怎么來的
高級編程語言的發(fā)展歷程（四）LISP 和 AI 的青梅竹馬 A
高級編程語言的發(fā)展歷程（五）LISP 和 AI 的青梅竹馬 B
高級編程語言的發(fā)展歷程（六）SCHEME 語言是怎么來的
高級編程語言的發(fā)展歷程（七） LISP 語言前傳
原文標(biāo)題：高級語言是怎么來的
高級編程語言的發(fā)展歷程（一）?創(chuàng)始紀(jì)
2009-5-13 原文鏈接
終于放暑假了，有心情來八卦了。我主要想八卦一下高級語言的設(shè)計(jì)思想和各種范式的來龍去脈，也就是回答這個(gè)問題：編程語言為什么會發(fā)生成現(xiàn)在這個(gè)樣子哩?這里面的奧妙又在哪里哩? 我嘗試著把這個(gè)系列的八卦寫下去，包括虛擬機(jī)的設(shè)計(jì)、線程的設(shè)計(jì)、棧和寄存器兩大流派的來龍去脈等等。
高級編程語言的創(chuàng)始紀(jì)上寫道：“初，世間無語言，僅電路與連線。及大牛出，天地開，始有 FORTRAN, LISP。ALGOL 隨之，乃有萬種語?！?我們都知道，LISP 是基于遞歸函數(shù)的，FORTRAN 是做科學(xué)計(jì)算的?，F(xiàn)在的 C 等等，都比較像 FORTRAN 而不像 LISP?？墒呛苌儆腥酥?#xff0c;最初，FORTRAN 是不支持函數(shù)遞歸調(diào)用的，而LISP是一生下來就支持的，所有高級語言里面的遞歸調(diào)用，都是逐漸從 LISP 那里學(xué)來的。這段塵封的歷史非常有趣，值得八卦一番。
一般人學(xué)編程，除了寫 Hello World 之外，人生寫的第二個(gè)程序，不是階乘就是菲波拉契數(shù)列，要不就是漢洛塔。而這幾個(gè)程序，基本上都是因?yàn)楹瘮?shù)的遞歸調(diào)用才顯得簡單漂亮。沒有遞歸的日子里， 人民非常想念您。可是，第一版的 FORTRAN 就居然不支持遞歸。 細(xì)心的讀者要問了，不支持遞歸的語言能圖靈完全么？當(dāng)然可以，圖靈機(jī)就是沒遞歸的典型的例子。但是沒遞歸調(diào)用的程序會很難寫，尤其像漢諾塔這種。那 么，FORTRAN 他怎么就悍然不支持遞歸呢，讓我們回到 1960 年。
話說當(dāng)年，IBM 是計(jì)算機(jī)行業(yè)的領(lǐng)軍者。那時(shí)候的計(jì)算機(jī)，都是比柜子還大的大家伙，至于計(jì)算能力嘛，卻比你的手機(jī)還弱。那時(shí)候計(jì)算機(jī)所做的最多的事情，不是發(fā)郵件打游戲， 而是作計(jì)算。作計(jì)算嘛，自然需要一種和數(shù)學(xué)語言比較接近的編程語言。于是，1960年，IBM 就搗鼓出了 FORTRAN，用行話說，就是公式翻譯系統(tǒng)。這 個(gè)公式翻譯系統(tǒng)，就成了世界上第一個(gè)編程語言。這個(gè)編程語言能做數(shù)學(xué)計(jì)算，能作條件判斷，能 GOTO。用現(xiàn)在的眼光看，這個(gè)語言能夠模擬圖靈機(jī)上的一切操作，所以是圖靈完全的。學(xué)過數(shù)值計(jì)算的同學(xué)都知道，科學(xué)計(jì)算無非就是一大堆數(shù)學(xué)計(jì)算按照步驟進(jìn)行而已。所以，一些控制判斷語句，數(shù)學(xué)公式加上一個(gè)數(shù)組，基本上就能完成所有的科學(xué)計(jì)算了。IBM 覺得這個(gè)語言夠用了，就發(fā)布了 FORTRAN 語言規(guī)范，并且在自家的大型機(jī)上實(shí)現(xiàn)了這個(gè)語言。
在實(shí)現(xiàn)這個(gè)語言的時(shí)候，IBM 的工程師要寫一個(gè) FORTRAN 編譯器 （請注意那時(shí)候的大型機(jī)沒有操作系統(tǒng)）。那時(shí)候的編譯器都是用機(jī)器語言或者很低級的匯編語言寫成的，所以編譯器要越簡單越好。這些工程師覺得，弄一個(gè)讓用戶運(yùn)行時(shí)動態(tài)開辟內(nèi)存的機(jī)制太麻煩了，所以干脆，強(qiáng)迫用戶在寫程序的時(shí)候，就要定好數(shù)組的大小，變量的類型和數(shù)目。這個(gè)要求并不過分，因?yàn)樵诳茖W(xué)計(jì)算中， 數(shù)組的維度，用到的變量等，在計(jì)算之前，就是可以知道大小的。用現(xiàn)在的話說，就是不能動態(tài)開辟內(nèi)存空間，也就相當(dāng)于沒有 malloc 的 C，或者沒有 new 的 C++。這樣的好處是，一個(gè)程序要多少內(nèi)存，編譯的時(shí)候就知道的一清二楚了。這個(gè)主意看上去很聰明，不過 IBM 的工程師比你想得更加聰明，他們想，既然一個(gè)程序或者子程序要多少內(nèi)存在編譯的時(shí)候都知道了，我們干脆就靜態(tài)的把每個(gè)子程序在內(nèi)存中的位置，子程序中參數(shù)，返回值和局部變量放的位置，大小都定好，不久更加整齊高效么。是的，我們都知道，在沒有操作系統(tǒng)管理的情況下，程序的內(nèi)存策略越簡單越好，如果內(nèi)存放的整整齊齊的，計(jì)算機(jī)的管理員就能夠很好的管理機(jī)器的內(nèi)存，這樣也是一件非常好的事情。（再次強(qiáng)調(diào)，當(dāng)年還沒有操作系統(tǒng)呢，操作系統(tǒng)要等到1964年發(fā)布 的 IBM 360 才有，具體開發(fā)一個(gè)操作系統(tǒng)之難度可參考《人月神話》）。
可是，聰明的讀者一下子就看出來了，這樣靜態(tài)的搞內(nèi)存分配，就遞不成歸不了。為啥呢？試想，我有個(gè) Fib 函數(shù)，用來計(jì)算第 N 個(gè)菲波拉契數(shù)。這個(gè)函數(shù)輸入一個(gè)整數(shù)，返回一個(gè)整數(shù)，FORTRAN 編譯器幫我把這個(gè)函數(shù)給靜態(tài)分配了。好，我運(yùn)行 Fib(5) 起來，FORTRAN 幫我把 5 存在某個(gè)專門給輸入?yún)?shù)的位置。我在 Fib(5) 里面遞歸的調(diào)用了Fib(4)，FORTRAN 一看，哈，不還是 Fib 么，參數(shù)是 4，我存。這一存，新的參數(shù)4，就把原來的 5 給覆蓋掉了，新的返回值，也把原來的返回值給覆蓋掉了。大事不好了，這么一搞，新的調(diào)用的狀態(tài)居然覆蓋了老的調(diào)用，這下，就沒法返回原來的 Fib(5) 了，這樣一搞，怎么遞歸啊？
IBM 這些寫編譯器的老前輩們，不是不知道這個(gè)問題，而是壓根就鄙視提出這個(gè)問題的人：你丫科學(xué)計(jì)算遞歸什么呀，通通給我展開成循環(huán)，展不開是你數(shù)學(xué)沒學(xué)好，想用遞歸，你就不要用 FORTRAN 了。那時(shí)候 IBM 乃是老大，只有他們家才生產(chǎn)大型機(jī)，老大發(fā)話，下面的消費(fèi)者只能聽他的。
既然軟件不支持，硬件也就可以偷工減料嘛，所以，硬件上，就壓根沒有任何棧支持。我們都知道，計(jì)算機(jī)發(fā)展史上，軟件和硬件是相互作用的。我們現(xiàn)在也很難猜測，是 IBM 的軟件工程師因?yàn)?IBM 的硬件工程師沒有在硬件上設(shè)計(jì)出堆棧，所以沒有能在 FORTRAN 里面設(shè)計(jì)出遞歸調(diào)用呢，還是 IBM 的硬件工程師覺得既然軟件沒要求，我就不設(shè)計(jì)了呢？不管怎么樣，我們看到的是，1960 年前，所有的機(jī)器的硬件都沒有直接支持棧的機(jī)制。熟悉 CPU 的都知道，現(xiàn)代 CPU 里面，都有兩個(gè)至關(guān)重要的地址寄存器，一個(gè)叫做 PC(Program Counter)， 用來標(biāo)記下一條要執(zhí)行的指令的位置，還有一個(gè)就是棧頂指針 SP(Stack Pointer)。如果沒有后者，程序之間的調(diào)用就會非常麻煩，因?yàn)樾枰绦騿T手工維護(hù)一個(gè)棧，才能保證程序之間調(diào)用最后還能正確的返回。而當(dāng)年，因?yàn)?FORTRAN 壓根就不支持遞歸，所以支持 FORTRAN 的硬件，就省去了棧指針了。如果一個(gè)程序員想要遞歸調(diào)用，唯一的實(shí)現(xiàn)方法，就是讓程序員借用一個(gè)通用寄存器作為棧指針，自己硬寫一個(gè)棧，而且不能用 FORTRAN。
因?yàn)?FORTRAN 不支持遞歸調(diào)用，按照自然規(guī)律，自然會有支持遞歸的語言在同時(shí)代出現(xiàn)。于是，很快的，LISP 和 ALGOL 這兩個(gè)新語言就出道了。我們只說 LISP，它的創(chuàng)始人 John McCarchy 是 MIT 教授，也是人工智能之父，是學(xué)院派人物。他喜歡阿隆佐·邱奇(Alonzo Church)的那一套 Lambda 演算，而非圖靈的機(jī)械構(gòu)造。所以，LISP 從一開始，就支持遞歸的調(diào)用，因?yàn)檫f歸就是 lambda 演算的靈魂. 但是有兩大問題擺在 McCarchy 面前。一是他的 LISP 理論模型找不到一個(gè)可以跑的機(jī)器，二是他的 LISP 模型中有一個(gè)叫做 eval 的指令，可以把一個(gè)字符串當(dāng)成指令在運(yùn)行時(shí)求值，而這個(gè)，當(dāng)時(shí)還沒有人解決過。按照 Paul Graham 大叔在他的《黑客與畫家》 里面的說法，McCarchy 甚至壓根就不想實(shí)現(xiàn)這個(gè) eval 指令，因?yàn)楫?dāng) IBM 的一個(gè)叫 Steve Russell 的工程師宣稱要實(shí)現(xiàn) eval 的時(shí)候，McCarthy 還連連搖手說理論是理論，實(shí)際是實(shí)際，我不指望這個(gè)能被實(shí)現(xiàn)?？墒?#xff0c;Russell 居然就把這兩個(gè)問題一并給解決了（這哥們也是電子游戲創(chuàng)始人，史上第一個(gè)電子游戲就是他寫的，叫 Space War）。他的方法，說來也簡單，就是寫了一個(gè)解釋器，讓 LISP 在這個(gè)解釋器里面跑。這個(gè)創(chuàng)舉，讓傳統(tǒng)上編譯 -> 運(yùn)行 的高級語言流程，變成了編寫 -> 解釋執(zhí)行的流程，也就是著名的 REPL(read–eval–print loop) 流程。他做的事情，相當(dāng)于在IBM 的機(jī)器上用機(jī)器碼寫了一個(gè)通用圖靈機(jī)，用來解釋所有的 LISP 指令。這個(gè)創(chuàng)舉，就讓 LISP 從理論走到了實(shí)踐。
因?yàn)橛辛诉\(yùn)行時(shí)的概念，LISP 想怎么遞歸，就可以怎么遞歸，只要運(yùn)行時(shí)支持一個(gè)軟件實(shí)現(xiàn)的棧就可以了。上面我也說了，也就是寫解釋器的人麻煩一點(diǎn)而已，寫 LISP 程序的人完全就可以不管下層怎么管理?xiàng)５牧?。同時(shí)，有了解釋器，也解放了原來動態(tài)分配空間的麻煩，因?yàn)楝F(xiàn)在所有的空間分配都可以由解釋器管理了，所以，運(yùn)行時(shí)環(huán)境允許你動態(tài)的分配空間。對空間分配的動態(tài)支持，隨之就帶來了一項(xiàng)新技術(shù)：垃圾收集器。這個(gè)技術(shù)出現(xiàn)在 LISP 里面不是偶然的，是解釋器的自然要求和歸宿。在 FORTRAN 上本來被繞過的問題，就在 LISP 里面用全新的方法被解決了。LISP 的劃時(shí)代意義和解釋器技術(shù)，使得伴隨的很多技術(shù)，比如抽象語法樹，動態(tài)數(shù)據(jù)結(jié)構(gòu)，垃圾收集，字節(jié)碼等等，都很早的出現(xiàn)在了 LISP 中，加上 LISP 本身規(guī)則很少，使用起來非常靈活。所以，每當(dāng)有一項(xiàng)新技術(shù)出現(xiàn)，特別是和解釋器和運(yùn)行時(shí)相關(guān)的一項(xiàng)新技術(shù)出現(xiàn)，我們就會聽到有人說， “這玩意兒 LISP 里早就有了”，這話，是有一定道理的。
除了上面的軟件模擬之外，MIT 還有一派在作硬件模擬，這一派，以后發(fā)展成了燦爛一時(shí)的 LISP machine，為日后所有虛擬機(jī)理論鋪開了一條新路。這一派在70、80年代迅速崛起，然后隨著 PC 的興起又迅速的隕落，讓人唏噓不已.
最后附送一個(gè)八卦：1960 年的時(shí)候，高級語言編程領(lǐng)域也發(fā)生了一件大事，即 ALGOL 60 的提出。ALGOL 是劃時(shí)代的標(biāo)準(zhǔn)，我們今天用的 C/Java 全是 ALGOL 家族的。ALGOL 注意到了 FORTRAN 不支持遞歸的問題，于是從一開始，就訂立標(biāo)準(zhǔn)支持遞歸。但是，處理遞歸需要很小心的安排每個(gè)函數(shù)每次調(diào)用的地址和所謂的活動窗口(Active Frame)，而并不是每個(gè)編譯器都是牛人寫的，所以在處理遞歸這樣一個(gè)新事物上，難免會出點(diǎn)小問題和小 BUG。這時(shí)候，搞笑的高爺爺(Knuth)出場了，他提出了一個(gè)測試，叫做“是男人就得負(fù)67”。(The man or boy test). 恕我功底不深，不能給各位讀者把這個(gè)男人測試的關(guān)竅講清楚，但是，我知道，這個(gè)測試，乃是看 ALGOL 60 編譯器有沒有正確的實(shí)現(xiàn)遞歸和外部引用的。照高爺爺?shù)恼f法，真的男人要能得到正確答案，不是男人的就得不到正確答案。當(dāng)然，高爺爺當(dāng)時(shí)自己也沒有男人編譯器，所以自己猜了一個(gè)-121，后來，真的男人編譯器出來了，正確答案是-67?？梢?#xff0c;高爺爺?shù)娜四X編譯器，也不是男人編譯器。（各位欲知詳情的，猛點(diǎn)這個(gè)）
高級編程語言的發(fā)展歷程（二）虛擬機(jī)的前世今生
2009-6-13?原文鏈接
上節(jié)我們提到了 LISP 中，因?yàn)?eval 的原因，發(fā)展出了運(yùn)行時(shí)環(huán)境這樣一個(gè)概念。基于這個(gè)概念，日后發(fā)展出了虛擬機(jī)技術(shù)。但這段歷史并不是平鋪直敘的，實(shí)際上，這里面還經(jīng)歷了一個(gè)非常漫長而曲折的過程，說起來也是非常有意思的。本文我們就著重解釋虛擬機(jī)的歷史。
我們21世紀(jì)的程序員，凡要是懂一點(diǎn)編程技術(shù)的，基本上都知道虛擬機(jī)和字節(jié)碼這樣兩個(gè)重要的概念。所謂的字節(jié)碼(bytecode)，是一 種非常類似于機(jī)器碼的指令格式。這種指令格式是以二進(jìn)制字節(jié)為單位定義的（不會有一個(gè)指令只用到一個(gè)字節(jié)的前四位），所以叫做字節(jié)碼。所謂的虛擬機(jī)，就是說不是一臺真的計(jì)算機(jī)，而是一個(gè)環(huán)境，其他程序能在這個(gè)環(huán)境中運(yùn)行，而不是在真的機(jī)器上運(yùn)行?，F(xiàn)在主流高級語言如 Java, Python, PHP, C#，編譯后的代碼都是以字節(jié)碼的形式存在的，這些字節(jié)碼程序，最后都是在虛擬機(jī)上運(yùn)行的。
虛擬機(jī)的安全性和跨平臺性
虛擬機(jī)的好處大家都知道，最容易想到的是安全性和跨平臺性。安全性是因?yàn)楝F(xiàn)在可執(zhí)行程序被放在虛擬機(jī)環(huán)境中運(yùn)行，虛擬機(jī)可以隨時(shí)對程序的危險(xiǎn)行為，比如緩沖區(qū)溢出，數(shù)組訪問過界等等進(jìn)行控制?？缙脚_性是因?yàn)橹灰煌脚_上都裝上了支持同一個(gè)字節(jié)碼標(biāo)準(zhǔn)的虛擬機(jī)，程序就可以在不同的平臺上不加修改而運(yùn)行，因?yàn)樘摂M機(jī)架構(gòu)在各種不同的平臺之上，用虛擬機(jī)把下層平臺間的差異性給抹平了。我們最熟悉的例子就是 Java 了。Java 語言號稱一次編寫，到處運(yùn)行(Write Once, Run Anywhere)，就是因?yàn)楦鱾€(gè)平臺上的 Java 虛擬機(jī)都統(tǒng)一支持 Java 字節(jié)碼，所以用戶感覺不到虛擬機(jī)下層平臺的差異。
虛擬機(jī)是個(gè)好東西，但是它的出現(xiàn)，不是完全由安全性和跨平臺性驅(qū)使的。
跨平臺需求的出現(xiàn)
我們知道，在計(jì)算機(jī)還是鎖在機(jī)房里面的昂貴的龐然大物的時(shí)候，系統(tǒng)軟件都是硬件廠商附送的東西（是比爾·蓋茨這一代人的出現(xiàn)，才有了和硬件產(chǎn)業(yè)分庭抗禮的軟件產(chǎn)業(yè)），一個(gè)系統(tǒng)程序員可能一輩子只和一個(gè)產(chǎn)品線的計(jì)算機(jī)打交道，壓根沒有跨平臺的需求。應(yīng)用程序員更加不要說了，因?yàn)橛?jì)算機(jī)很稀有，寫程序都是為某一臺計(jì)算機(jī)專門寫的，所以一段時(shí)間可能只和一臺龐然大物打交道，更加不要說什么跨平臺了。真的有跨平臺需求，是從微型計(jì)算機(jī)開始真的普及開始的。因?yàn)橹挥杏?jì)算機(jī)普及了，各種平臺都被廣泛采用了，相互又不互相兼容軟件，才會有軟件跨平臺的需求。微機(jī)普及的歷史，比 PC 普及的歷史要早10年，而這段歷史，正好和 UNIX 發(fā)展史是并行重疊的。
熟悉 UNIX 發(fā)展史的讀者都知道， UNIX 真正普及開來，是因?yàn)槠淙慷加?C，一個(gè)當(dāng)時(shí)絕對能夠稱為跨平臺的語言重寫了一次。又因?yàn)槊绹髮W(xué)和科研機(jī)構(gòu)之間的開源共享文化，C 版本的 UNIX 出生沒多久，就迅速從原始的 PDP-11 實(shí)現(xiàn)，移植到了 DEC, Intel 等平臺上，產(chǎn)生了無數(shù)衍生版本。隨著跨平臺的 UNIX 的普及， 微型計(jì)算機(jī)也更多的普及開來，因?yàn)橹恍枰莆栈镜?UNIX 知識，就可以順利操作微型計(jì)算機(jī)了。所以，微機(jī)和 UNIX 這兩樣?xùn)|西都在 1970年 到 1980 年在美國政府、大學(xué)、科研機(jī)構(gòu)、公司、金融機(jī)構(gòu)等各種信息化前沿部門間真正的普及開來了。這些歷史都是人所共知耳熟能詳?shù)摹?/p>
既然 UNIX 是跨平臺的，那么，UNIX 上的語言也應(yīng)當(dāng)是跨平臺的 （注: 本節(jié)所有的故事都和 Windows 無關(guān)，因?yàn)?Windows 本身就不是一個(gè)跨平臺的操作系統(tǒng)）。UNIX 上的主打語言 C 的跨平臺性，一般是以各平臺廠商提供編譯器的方式實(shí)現(xiàn)的，而最終編譯生成的可執(zhí)行程序，其實(shí)不是跨平臺的。所以，跨平臺是源代碼級別的跨平臺，而不是可執(zhí)行程序?qū)用娴?。而除了?biāo)準(zhǔn)了 C 語言外，UNIX 上有一派生機(jī)勃勃的跨平臺語言，就是腳本語言。（注：腳本語言和普通的編程語言相比，在能完成的任務(wù)上并沒有什么的巨大差異。腳本語言往往是針對特定類型的問題提出的，語法更加簡單，功能更加高層，常常幾百行C語言要做的事情，幾行簡單的腳本就能完成）
解釋和執(zhí)行
腳本語言美妙的地方在于，它們的源代碼本身就是可執(zhí)行程序，所以在兩個(gè)層面上都是跨平臺的。不難看出，腳本語言既要能被直接執(zhí)行，又要跨平臺的話，就必然要有一個(gè)“東西”，橫亙在語言源代碼和平臺之間。往上，在源代碼層面，分析源代碼的語法，結(jié)構(gòu)和邏輯，也就是所謂的“解釋”；往下，要隱藏平臺差異，使得源代碼中的邏輯，能在具體的平臺上以正確的方式執(zhí)行，也就是所謂的“執(zhí)行”。
雖說我們知道一定要這么一個(gè)東西，能夠?qū)ι稀敖忉尅?#xff0c;對下“執(zhí)行”，但是 “解釋” 和 “執(zhí)行” 兩個(gè)模塊畢竟是相互獨(dú)立的，因此就很自然的會出現(xiàn)兩個(gè)流派：“把解釋和執(zhí)行設(shè)計(jì)到一起”和“把解釋和執(zhí)行單獨(dú)分開來”這樣兩個(gè)設(shè)計(jì)思路，需要讀者注意的是，現(xiàn)在這兩個(gè)都是跨平臺的、安全的設(shè)計(jì)，而在后者中字節(jié)碼作為了解釋和執(zhí)行之間的溝通橋梁，前者并沒有字節(jié)碼作為橋梁。
解釋和執(zhí)行在一起的方案
我們先說前者，前者的優(yōu)點(diǎn)是設(shè)計(jì)簡單，不需要搞什么字節(jié)碼規(guī)范，所以 UNIX 上早期的腳本語言，都是采用前者的設(shè)計(jì)方法。我們以 UNIX 上大名鼎鼎的 AWK 和 Perl 兩個(gè)腳本語言的解釋器為例說明。AWK 和 Perl 都是 UNIX 上極為常用的、圖靈完全的語言，其中 AWK， 在任何 UNIX 系統(tǒng)中都是作為標(biāo)準(zhǔn)配置的，甚至入選 IEEE POSIX 標(biāo)準(zhǔn)，是入選 IEEE POSIX 盧浮宮的唯一同類語言品牌，其地位絕對不是 UNIX 下其他腳本語言能夠比的。這兩個(gè)語言是怎么實(shí)現(xiàn)解釋和運(yùn)行的呢？我從 AWK 的標(biāo)準(zhǔn)實(shí)現(xiàn)中摘一段代碼您一看就清楚了：
int main(int argc, char *argv[]) {...syminit();compile_time = 1;yyparse();...if (errorflag == 0){compile_time = 0;run(winner);}... }其中，run 的原型是：
run(Node *a) /* execution of parse tree starts here */而 winner 的定義是：
Node *winner ; /* root of parse tree */熟悉 Yacc 的讀者應(yīng)該能夠立即看出，AWK 調(diào)用了 Yacc 解析源代碼，生成了一棵語法樹。按照 winner 的定義，winner 是這棵語法樹的根節(jié)點(diǎn)。 在“解釋”沒有任何錯(cuò)誤之后，AWK 就轉(zhuǎn)入了“執(zhí)行” (compile_time 變成了 0)，將 run 作用到這棵語法樹的根節(jié)點(diǎn)上。不難想像，這個(gè) run 函數(shù)的邏輯是遞歸的（事實(shí)上也是），在語法樹上，從根依次往下，執(zhí)行每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)，然后收集結(jié)果。是的，這就是整個(gè) AWK 的基本邏輯：對于一段源代碼，先用解釋器（這里 awk 用了 Yacc 解釋器），生成一棵語法樹，然后，從樹的根節(jié)點(diǎn)開始，往下用 run 這個(gè)函數(shù)，遇山開山，遇水搭橋，一路遞歸下去，最后把整個(gè)語法樹遍歷完，程序就執(zhí)行完畢了。（這里附送一個(gè)小八卦，抽象語法樹這個(gè)概念是 LISP 先提出的，因?yàn)?LISP 是最早像 AWK 這樣做的，LISP 實(shí)在是屬于開天辟地的作品！）Perl 的源代碼也是類似的邏輯解釋執(zhí)行的，我就不一一舉例了。
三大缺點(diǎn)
現(xiàn)在我們看看這個(gè)方法的優(yōu)缺點(diǎn)。優(yōu)點(diǎn)是顯而易見的，因?yàn)橥ㄟ^抽象語法樹在兩個(gè)模塊之間通信，避免了設(shè)計(jì)復(fù)雜的字節(jié)碼規(guī)范，設(shè)計(jì)簡單。但是缺點(diǎn)也非常明顯。最核心的缺點(diǎn)就是性能差，需要資源多，具體來說，就是如下三個(gè)缺點(diǎn)。
缺點(diǎn)1，因?yàn)榻忉尯瓦\(yùn)行放在了一起，每次運(yùn)行都需要經(jīng)過解釋這個(gè)過程。假如我們有一個(gè)腳本，寫好了就不修改了，只需要重復(fù)的運(yùn)行，那么在一般應(yīng)用下尚可以忍受每次零點(diǎn)幾秒的重復(fù)冗余的解釋過程，在高性能的場合就不能適用了。
缺點(diǎn)2，因?yàn)檫\(yùn)行是采用遞歸的方式的，效率會比較低。我們都知道，因?yàn)檫f歸涉及到棧操作和狀態(tài)保存和恢復(fù)等，代價(jià)通常比較高，所以能不用遞歸就不用遞歸。在高性能的場合使用遞歸去執(zhí)行語法樹，不值得。
缺點(diǎn)3，因?yàn)橐磺谐绦虻钠瘘c(diǎn)都是源代碼，而抽象語法樹不能作為通用的結(jié)構(gòu)在機(jī)器之間互傳，所以不得不在所有的機(jī)器上都布置一個(gè)解釋+運(yùn)行的模塊。在資源充裕的系統(tǒng)上布置一個(gè)這樣的系統(tǒng)沒什么，可在資源受限的系統(tǒng)上就要慎重了，比如嵌入式系統(tǒng)上。鑒于有些語言本身語法結(jié)構(gòu)復(fù)雜，布置一個(gè)解釋模塊的代價(jià)是非常高昂的。本來一個(gè)遞歸執(zhí)行模塊就很吃資源了，再加一個(gè)解釋器，嵌入式系統(tǒng)就沒法做了。所以， 這種設(shè)計(jì)在嵌入式系統(tǒng)上是行不通的。
當(dāng)然，還有一些其他的小缺點(diǎn)，比如有程序員不喜歡開放源代碼，但這種設(shè)計(jì)中，一切都從源代碼開始，要發(fā)布可執(zhí)行程序，就等于發(fā)布源代碼，所以，不愿意公布源代碼的商業(yè)公司很不喜歡這些語言等等。但是上面的三個(gè)缺點(diǎn)，是最致命的，這三個(gè)缺點(diǎn)，決定了有些場合，就是不能用這種設(shè)計(jì)。
分開解釋和執(zhí)行
前面的三個(gè)主要缺點(diǎn)，恰好全部被第二個(gè)設(shè)計(jì)所克服了。在第二種設(shè)計(jì)中，我們可以只解釋一次語法結(jié)構(gòu)，生成一個(gè)結(jié)構(gòu)更加簡單緊湊的字節(jié)碼文件。這樣，以后每次要運(yùn)行腳本的時(shí)候，只需要把字節(jié)碼文件送給一個(gè)簡單的解釋字節(jié)碼的模塊就行了。因?yàn)樽止?jié)碼比源程序要簡單多了，所以解釋字節(jié)碼的模塊比原來解釋源程序的模塊要小很多；同時(shí)，脫離了語法樹，我們完全可以用更加高性能的方式設(shè)計(jì)運(yùn)行時(shí)，避免遞歸遍歷語法樹這種低效的執(zhí)行方式；同時(shí)，在嵌入式系統(tǒng)上，我們可以只部署運(yùn)行時(shí)，不部署編譯器。這三個(gè)解決方案，預(yù)示了在運(yùn)行次數(shù)遠(yuǎn)大于編譯次數(shù)的場合，或在性能要求高的場合，或在嵌入式系統(tǒng)里，想要跨平臺和安全性，就非得用第二種設(shè)計(jì)，也就是字節(jié)碼+虛擬機(jī)的設(shè)計(jì)。
講到了這里，相信對 Java，對 PHP 或者對 Tcl 歷史稍微了解的讀者都會一拍腦袋頓悟了：原來這些牛逼的虛擬機(jī)都不是天才拍腦袋想出來的，而是被需求和現(xiàn)實(shí)給召喚出來的啊！
我們先以 Java 為例，說說在嵌入式場合的應(yīng)用。Java 語言原本叫 Oak 語言，最初不是為桌面和服務(wù)器應(yīng)用開發(fā)的，而是為機(jī)頂盒開發(fā)的。SUN 最初開發(fā) Java 的唯一目的，就是為了參加機(jī)頂盒項(xiàng)目的競標(biāo)。嵌入式系統(tǒng)的資源受限程度不必細(xì)說了，自然不會允許上面放一個(gè)解釋器和一個(gè)運(yùn)行時(shí)。所以，不管 Java 語言如何，Java 虛擬機(jī)設(shè)計(jì)得直白無比，簡單無比，手機(jī)上，智能卡上都能放上一個(gè) Java 運(yùn)行時(shí)（當(dāng)然是精簡版本的）。 這就是字節(jié)碼和虛擬機(jī)的威力了。
SUN 無心插柳，等到互聯(lián)網(wǎng)興起的時(shí)候， Java 正好對繪圖支持非常好，在 Flash 一統(tǒng)江湖之前，憑借跨平臺性能，以 Applet 的名義一舉走紅。然后，又因?yàn)檫@種設(shè)計(jì)先天性的能克服性能問題，在性能上大作文章，憑借 JIT 技術(shù)，充分發(fā)揮上面說到的優(yōu)點(diǎn)2，再加上安全性，一舉拿下了企業(yè)服務(wù)器市場的半壁江山，這都是后話了。
再說 PHP。PHP 的歷史就包含了從第一種設(shè)計(jì)轉(zhuǎn)化到第二種設(shè)計(jì)以用來優(yōu)化運(yùn)行時(shí)性能的歷史。PHP 是一般用來生成服務(wù)器網(wǎng)頁的腳本語言。一個(gè)大站點(diǎn)上的 PHP 腳本，一旦寫好了，每天能訪問千百萬次，所以，如果全靠每次都解釋，每次都遞歸執(zhí)行，性能上是必然要打折扣的。所以，從1999年的 PHP4 開始， Zend 引擎就橫空出世，專門管加速解釋后的 PHP 腳本，而對應(yīng)的 PHP 解釋引擎，就開始將 PHP 解釋成字節(jié)碼，以支持這種一次解釋，多次運(yùn)行的框架。在此之前， PHP 和 Perl，還有 cgi，還算平分秋色的樣子，基本上服務(wù)器上三類網(wǎng)頁的數(shù)量都差不多，三者語法也很類似，但是到了 PHP4 出現(xiàn)之后，其他兩個(gè)基于第一種設(shè)計(jì)方案的頁面就慢慢消逝了，全部讓位給 PHP。WordPress 博客，也是基于 PHP 技術(shù)的，底層也是 Zend 引擎的。著名的 LAMP 里面的那個(gè) P， 原始上也是 PHP，而這個(gè)詞真的火起來，也是99年 PHP4 出現(xiàn)之后的事情。
第二種設(shè)計(jì)的優(yōu)點(diǎn)正好滿足了實(shí)際需求的事情，其實(shí)不勝枚舉。比如說 在 Lua 和 Tcl 等宿主語言上也都表現(xiàn)的淋漓盡致。像這樣的小型語言，本來就是讓運(yùn)行時(shí)為了嵌入其他語言的，所以運(yùn)行時(shí)越小越好，自然的，就走了和嵌入式系統(tǒng)一樣的設(shè)計(jì)道路。
結(jié)語
其實(shí)第二種設(shè)計(jì)也不是鐵板一塊，里面也有很多流派，各派有很多優(yōu)缺點(diǎn)，也有很多細(xì)致的考量，下一節(jié)，如果不出意外，我將介紹我最喜歡的一個(gè)內(nèi)容：下一代虛擬機(jī)：寄存器還是棧。
說了這么多，最后就是一句話，有時(shí)候我們看上去覺得一種設(shè)計(jì)好像是天外飛仙，橫空出世，其實(shí)其后都有現(xiàn)實(shí)、需求等等的諸多考量。虛擬機(jī)技術(shù)就是這樣，在各種需求的引導(dǎo)下，逐漸的演化成了現(xiàn)在的樣子。
高級編程語言的發(fā)展歷程（三）FORTRAN 語言是怎么來的
2009-7-2 原文鏈接
在“高級語言是怎么來的”子系列的第一篇中，我們結(jié)合當(dāng)時(shí)硬件的特點(diǎn)，分析了 FORTRAN 為什么一開始不支持遞歸。但是 FORTRAN 本身是怎么來的這個(gè)問題其實(shí)還是沒有得到正面回答，本節(jié)我們就談?wù)?FORTRAN 語言本身是怎么來的。
其實(shí)，FORTRAN 語言也是現(xiàn)實(shí)驅(qū)動的。所以我們還是回到當(dāng)時(shí)，看看當(dāng)時(shí)程序員的需求和軟硬件條件，看看 FORTRAN 是怎么來的。了解歷史的另一個(gè)好處是，因?yàn)?FORTRAN 的發(fā)展歷史正好和高級語言的發(fā)展歷史高度重合，所以了解 FORTRAN 的背景，對于理解其他高級語言的產(chǎn)生都是大有幫助的。
困難的浮點(diǎn)計(jì)算
我們先從硬件的角度說起。大致從 1946 年第一臺計(jì)算機(jī)誕生，到 1953 年，計(jì)算機(jī)一直都缺少兩件非常重要的功能，一個(gè)叫浮點(diǎn)計(jì)算，一個(gè)叫數(shù)組下標(biāo)尋址，這兩個(gè)功能的缺失直接導(dǎo)致了高級語言的興起。我們依次單個(gè)分析。讀者對浮點(diǎn)計(jì)算應(yīng)該都不陌生，用通俗的話說就是如 0.98×12.6 這樣的實(shí)數(shù)乘法，或者 0.98 + 12.6 這樣的實(shí)數(shù)加法的運(yùn)算。用行話說，就是用計(jì)算機(jī)進(jìn)行大范圍高精度數(shù)的算術(shù)運(yùn)算。
學(xué)過二進(jìn)制的同學(xué)都知道，二進(jìn)制整數(shù)之間的乘法和加法等運(yùn)算都是相對簡單的，和正常的十進(jìn)制運(yùn)算是一樣的，只是把加法和乘法這些基本操作用更加簡單的邏輯或(OR) 和邏輯與 (AND) 實(shí)現(xiàn)而已，在電子電路上也很好實(shí)現(xiàn)。因此，就是世界上最早的電子計(jì)算機(jī)，ENIAC，也是支持整數(shù)的乘法加法等算術(shù)操作的。
可是浮點(diǎn)運(yùn)算就不一樣了。因?yàn)橐粋€(gè)額外的小數(shù)點(diǎn)的引入，在任何時(shí)候都要注意小數(shù)點(diǎn)的對齊。如果用定點(diǎn)計(jì)數(shù)，則計(jì)數(shù)的范圍受到限制，不能表示非常大或者非常小的數(shù)。所以，浮點(diǎn)數(shù)一般都是用科學(xué)記數(shù)法表示的，比如 IEEE 754 標(biāo)準(zhǔn)。（不熟悉 IEEE 754 的讀者也可以想像一下如何設(shè)計(jì)一套高效的存儲和操作浮點(diǎn)數(shù)的規(guī)范和標(biāo)準(zhǔn)，以及浮點(diǎn)算法），科學(xué)記數(shù)法表示的浮點(diǎn)數(shù)的加減法每次都要對齊小數(shù)點(diǎn)，乘除法為了保持精度，在設(shè)計(jì)算法上也有很多技巧，所以說，相比較于整數(shù)的運(yùn)算和邏輯運(yùn)算，浮點(diǎn)運(yùn)算是一件復(fù)雜的事情。落實(shí)到硬件上就是說，在硬件上設(shè)計(jì)一個(gè)浮點(diǎn)運(yùn) 算，需要復(fù)雜的電路和大量的電子元器件。在早期電子管計(jì)算機(jī)中，是很少能做到這么大的集成度的。因此，不支持浮點(diǎn)也是自然的設(shè)計(jì)取舍。在計(jì)算機(jī)上放一個(gè)浮點(diǎn)模塊這個(gè)想法，需要等電子工業(yè)繼續(xù)發(fā)展，使得電子管體積小一點(diǎn)，功耗低一點(diǎn)后，才能進(jìn)入實(shí)踐。
關(guān)于浮點(diǎn)計(jì)算的一些八卦
關(guān)于浮點(diǎn)，這里順帶八卦一點(diǎn)浮點(diǎn)計(jì)算的事情。在計(jì)算機(jī)芯片設(shè)計(jì)中，浮點(diǎn)計(jì)算一直是一個(gè)讓硬件工程師頭疼的事情，即使到了386時(shí)代，386 處理器(CPU)的浮點(diǎn)乘法也是用軟件模擬的，如果想用硬件做浮點(diǎn)乘法，需要額外購買一塊 80387 浮點(diǎn)協(xié)處理器 FPU，否則就在 386 上做軟件的模擬。這樣做的原因在一塊硅片上刻蝕一個(gè) CPU 和一個(gè) FPU 需要的集成度還是太高，當(dāng)時(shí)的工藝根本沒法實(shí)現(xiàn)。真的把 FPU 和 CPU 融在一起刻蝕到一塊硅片上，已經(jīng)是 1989 年的事情了。當(dāng)時(shí)，Intel 把融合了 80386 和 80387 的芯片改了改，起了個(gè)名字叫 80486，推向了市場。帶著浮點(diǎn)的處理器的普及，使得個(gè)人計(jì)算機(jī)能做的事情變多了。極度依賴于浮點(diǎn)計(jì)算的多媒體計(jì)算機(jī)（視頻和聲音等多媒體的壓縮，轉(zhuǎn)換和回放都是要依賴于浮點(diǎn)運(yùn)算的），也正好隨著 80486 的流行，逐漸普及開來。
在處理器上融合浮點(diǎn)運(yùn)算依然是困難的。即使到今天，很多低端的處理器，都不帶有浮點(diǎn)處理器。所以，號稱能夠上天入地的，被移植到很多低端設(shè)備（比如手機(jī)）上的 Linux 內(nèi)核，必然是不能支持浮點(diǎn)運(yùn)算的，因?yàn)檫@樣會破壞內(nèi)核的可移植性。我們都知道，在內(nèi)核模式下，為了保證內(nèi)核操作的原子性，一般在內(nèi)核從事關(guān)鍵任務(wù)的時(shí)候所有中斷是要被屏蔽的，用通俗的話說就是內(nèi)核在做事情的時(shí)候，其他任何人不得打擾。如果內(nèi)核支持浮點(diǎn)運(yùn)算，不管是硬件實(shí)現(xiàn)也好，軟件模擬也罷，如果允許在內(nèi)核中進(jìn)行像浮點(diǎn)計(jì)算這樣復(fù)雜而耗時(shí)的操作，整個(gè)系統(tǒng)的性能和實(shí)時(shí)響應(yīng)能力會急劇下 降。即使是在硬件上實(shí)現(xiàn)的浮點(diǎn)運(yùn)算，也不是件容易的事情，會耗費(fèi) CPU 較多的時(shí)鐘周期，比如 Pentium 上的浮點(diǎn)數(shù)除法，需要耗費(fèi) 39 個(gè)時(shí)鐘周期才行，在流水線設(shè)計(jì)的 CPU 中，這種占用多個(gè)時(shí)鐘周期的浮點(diǎn)運(yùn)算會讓整個(gè)流水線暫停，讓 CPU 的吞吐量下降。在現(xiàn)代 CPU 設(shè)計(jì)中，工程師們發(fā)明了超標(biāo)量，亂序執(zhí)行，SIMD 等多種方式來克服流水線被浮點(diǎn)運(yùn)算這種長周期指令堵塞的問題，這都是后話了。
正因?yàn)閷τ谟?jì)算機(jī)來說，浮點(diǎn)運(yùn)算是一個(gè)挑戰(zhàn)性的操作，但又是做科學(xué)計(jì)算所需要的基本操作，所以浮點(diǎn)計(jì)算能力就成了計(jì)算機(jī)能力的一個(gè)測試標(biāo)準(zhǔn)。我們常常聽說有一個(gè)世界上前 500 臺最快的超級計(jì)算機(jī)列表，這里所謂的“快”的衡量標(biāo)準(zhǔn)，就是以每秒鐘進(jìn)行多少次浮點(diǎn)計(jì)算(FLOPS) 為準(zhǔn)。按照 Top500.org, 即評選世界上前 500 臺超級計(jì)算機(jī)的機(jī)構(gòu)2009年6月的數(shù)據(jù)，世界上最快的計(jì)算機(jī)，部署在美國能源部位于新墨西哥的洛斯阿拉莫斯國家實(shí)驗(yàn)室 (Los Alamos National Laboratory)，當(dāng)年造出第一顆原子彈的實(shí)驗(yàn)室。這臺超級計(jì)算機(jī)，浮點(diǎn)計(jì)算速度的峰值高達(dá) 1456 TFlops，主要用來模擬核試驗(yàn)。因?yàn)槊绹乃泻藦楊^，海軍核動力航母中的反應(yīng)堆以及核試驗(yàn)，都由能源部國家核安全署(NNSA) 管理，所以能源部一直在投資用超級計(jì)算機(jī)進(jìn)行核試驗(yàn)。在1996年美國宣布不再進(jìn)行大規(guī)模的物理核試驗(yàn)后的這么多年，美國能源部一直用超級計(jì)算機(jī)來做核試驗(yàn)，所以在 Top500 列表中，美國能源部擁有最多數(shù)量的超級計(jì)算機(jī)。
數(shù)組下標(biāo)尋址之障
言歸正傳，我們剛才說了在早期計(jì)算機(jī)發(fā)展史上，浮點(diǎn)計(jì)算的困難。除了浮點(diǎn)計(jì)算，還有一件事情特別困難，叫做數(shù)組下標(biāo)尋址。用現(xiàn)代通俗的話 說，就是當(dāng)年的計(jì)算機(jī)，不直接支持 A[3] 這樣的數(shù)組索引操作，即使這個(gè)操作從邏輯上說很簡單：把數(shù)組 A 的地址加上 3，就得到了 A[3] 的地址，然后去訪問這個(gè)地址。
這個(gè)困難在今天的程序員看來是不可思議的。為什么這么簡單的數(shù)組下標(biāo)尋址機(jī)制最一開始的計(jì)算機(jī)沒有支持呢？ 原來，當(dāng)年的計(jì)算機(jī)內(nèi)存很小，只有一千到兩K的存儲空間，所以，描述地址只需要幾位二/十進(jìn)制數(shù)（BCD)。從而，在每條指令后面直接加一個(gè)物理地址是可行且高效的尋址方式。這種尋址方式，叫做直接尋址，當(dāng)時(shí)所有的機(jī)器，都只支持直接尋址，因?yàn)樵跈C(jī)器碼中直接指出操作數(shù)的準(zhǔn)確地址是最簡單直接的方法，計(jì)算機(jī)不需要任何復(fù)雜的地址解碼電路。但壞處是，這個(gè)設(shè)計(jì)太不靈活了，比如說 A[3] 這個(gè)例子，就沒法用直接尋址來表示。
一般情況下，如果知道數(shù)組A， 對于 A[3] 這樣的例子，用直接尋址問題去模擬間接尋址的困難還不是很大，只要程序員事先記住數(shù)組 A 的地址然后手工加上 3 就行了 （A也是程序員分配的，因?yàn)楫?dāng)時(shí)沒有操作系統(tǒng)，所以程序員手工管理內(nèi)存的一切）。可是，也有一些情況這樣直接尋址是不行的。比如說，當(dāng)時(shí)計(jì)算機(jī)已經(jīng)能支持跳轉(zhuǎn)和判斷指令了，也就是說，可以寫循環(huán)語句了。我們可以很容易看到， 以 i 為循環(huán)變量的循環(huán)體內(nèi)，對 A[i] 的訪問是不能寫成一個(gè)靜態(tài)的直接尋址的，因?yàn)?i 一直在變化，所以不可能事先一勞永逸的定好 A[i] 的所在位置，然后靜態(tài)寫在程序中。
這樣，即使寫一個(gè)簡單的 10×10 矩陣的乘法，程序員就不得不死寫10的三次方即1000 行地址訪問，而沒辦法用幾行循環(huán)代替。當(dāng)時(shí)的一些聰明人，也想了一些方法去克服這個(gè)問題，比如說，他們先取出 A 的地址，然后做一次加法，把結(jié)果，也就是當(dāng)時(shí) A[i] 的地址，注射到一個(gè)讀內(nèi)存的 LOAD 指令后面。然后執(zhí)行那條 LOAD 指令。比如我要讀 A[i]，我先看，A的地址是 600，再看看 i 是3， 就加上 i，變成603，然后，把后面的指令改成 LOAD 603， 這樣，就可以讀到 A[i]。這個(gè)小技巧之所以可行，要感謝馮諾依曼爺爺?shù)捏w系設(shè)計(jì)。在馮諾依曼計(jì)算機(jī)中，數(shù)據(jù)和程序是混在一起不加區(qū)分的，所以程序員可以隨時(shí)像修改數(shù)據(jù)一樣修改將要運(yùn)行的下一條程序指令。就這樣，靠著這個(gè)小技巧，好歹程序員再也不要用1000行代碼表示一個(gè)矩陣乘法了。
SpeedCoding 的出現(xiàn)
計(jì)算機(jī)本來就是用來做數(shù)學(xué)計(jì)算的，可是科學(xué)計(jì)算里面最最基本的兩個(gè)要素——浮點(diǎn)計(jì)算和數(shù)組下標(biāo)訪問，在當(dāng)時(shí)的計(jì)算機(jī)上都缺少支持。這種需求和實(shí)際的巨大落差，必然會召喚出一個(gè)中間層來消弭這種落差。其實(shí)計(jì)算機(jī)科學(xué)的一般規(guī)律就是這樣：當(dāng) A 和 C 相差巨大的時(shí)候，我們就引入一個(gè)中間層 B，用 B 來彌合 A 和 C 之間的不兼容。當(dāng)年的這個(gè)中間層，就叫做 SpeedCoding，由 IBM 的工程師 John Backus 開發(fā)。
SpeedCoding，顧名思義，就是讓程序員編程更快。它其實(shí)是一個(gè)簡單，運(yùn)行在 IBM 701 計(jì)算機(jī)上的解釋器。它允許程序員直接寫浮點(diǎn)計(jì)算和下標(biāo)尋址的指令，并且在底層把這些 “偽指令” 翻譯成對應(yīng)的機(jī)器碼，用軟件模擬浮點(diǎn)計(jì)算，自動修改地址等等。這樣，程序員就可以從沒完沒了的手工實(shí)現(xiàn)浮點(diǎn)運(yùn)算和下標(biāo)尋址實(shí)現(xiàn)中解放出來，快速的編程。這 個(gè) SpeedCoding，這可以算得上是 FORTRAN 的種子了。
雖然這個(gè)解釋器超級慢，程序員用這個(gè)解釋器也用得很爽，也不感到它非常慢。這是因?yàn)楫?dāng)年計(jì)算機(jī)浮點(diǎn)計(jì)算都繞不過軟件模擬，即使最好的程序員用機(jī)器碼而不用這個(gè)解釋器，寫出來的程序，也不比這個(gè)解釋器下運(yùn)行快多少。另一個(gè)更加重要 的原因是，這個(gè)解釋器極大的減少了程序員 debug 和 code 的時(shí)間。隨著計(jì)算機(jī)速度的提高，當(dāng)年一個(gè)程序耗費(fèi)的計(jì)算成本和程序員編程耗費(fèi)的人力成本基本上已經(jīng)持平了。所以，相比較于寫更加底層的機(jī)器碼，用了 SpeedCoding 的程序員的程序雖然慢點(diǎn)，但人力成本瞬間降成 0，總體下來，用 SpeedCoding 比起不用來，總體成本還要低不少。
好景不長，因?yàn)榭蛻粢恢钡囊蠛碗娮庸I(yè)的發(fā)展，IBM 在 1954 年，終于發(fā)布了劃時(shí)代的 704 計(jì)算機(jī)，很多經(jīng)典的語言和程序，都首次在 704 上完成了。比如之前我們提到的 Steve Russell 的 LISP 解釋器，就是在 704 上完成的。704 計(jì)算機(jī)一下子支持了浮點(diǎn)計(jì)算和間接下標(biāo)尋址。這下用 SpeedCoding 的人沒優(yōu)勢了，因?yàn)闄C(jī)器碼支持浮點(diǎn)和下標(biāo)尋址之后，寫機(jī)器碼比寫 SpeedCoding 復(fù)雜不了多少，但是速度快了很多倍，因?yàn)?SpeedCoding 解釋器太慢了，以前因?yàn)楦↑c(diǎn)和解釋器一樣慢，所以大家不在意它慢，現(xiàn)在浮點(diǎn)和尋址快了，就剩下解釋器慢，寫機(jī)器碼的反而占了上風(fēng)，程序員也就不用 SpeedCoding 了。
FORTRAN 創(chuàng)世紀(jì)
在 704 出來之前，做 SpeedCoding 的 John Backus 就認(rèn)識到，要想讓大家用他的 SpeedCoding, 或者說，想要從軟件工具上入手，減少程序的開發(fā)成本，只有兩個(gè)方法：
- 程序員可以方便的寫數(shù)學(xué)公式
- 這個(gè)系統(tǒng)最后能夠解析/生成足夠的快的程序
他認(rèn)為，只有達(dá)到了這兩點(diǎn)，程序員才會樂意使用高級的像 SpeedCoding 這樣的工具，而不是隨著硬件的發(fā)展在機(jī)器碼和 SpeedCoding 這樣的工具之間跳來跳去。他本人通過實(shí)現(xiàn) SpeedCoding，也認(rèn)識到如果有一個(gè)比機(jī)器碼高級的語言，生產(chǎn)效率會高很多倍。那么，現(xiàn)在唯一的問題就是實(shí)現(xiàn)它，當(dāng)然，這就不是一個(gè)小項(xiàng)目了，就需要 IBM 來支持他的開發(fā)了。 所以，在1953年，他把他的想法寫成了一個(gè)文檔，送給了 IBM 的經(jīng)理。項(xiàng)目在 1954 年， 704 發(fā)布的當(dāng)年，終于啟動。John Backus 領(lǐng)導(dǎo)的設(shè)計(jì)一個(gè)能達(dá)到上面兩點(diǎn)的編程系統(tǒng)的項(xiàng)目的成果，就是日后的 FORTRAN。
和現(xiàn)在大多數(shù)編程語言不一樣，FORTRAN 語言的設(shè)計(jì)的主要問題不是語法和功能，而是編譯器怎么寫才能高性能。John Backus 日后回憶說，當(dāng)時(shí)誰也沒把精力放在語言細(xì)節(jié)上，語言設(shè)計(jì)很潦草的就完成了（所以其后正式發(fā)布后又經(jīng)過了N多修訂），他們所有的功夫都是花在怎么寫一個(gè)高性能的編譯器上。這個(gè)高性能的編譯器很難寫，到 1957 年才寫好，總共花了 IBM 216 個(gè)人月。等到 FORTRAN 一推出，不到一年的時(shí)間，在 IBM 總共售出的 60 臺 704上，就部署了超過一半?，F(xiàn)在沒啥編程語言能夠這么牛的攻城掠地了 ：）
結(jié)語?
放到歷史的上下文中看，FORTRAN 的出現(xiàn)是很自然的。一方面，復(fù)雜的數(shù)學(xué)運(yùn)算使得一個(gè)能夠表述數(shù)學(xué)計(jì)算的高級語言成為必須，計(jì)算機(jī)的發(fā)展也為這個(gè)需求提供了硬件條件；另一方面，隨著計(jì)算機(jī)的發(fā)展，程序員的時(shí)間成本一直不變，但是計(jì)算的成本一直在降低，用高級語言和用機(jī)器碼在性能上的些許差異變得可以忽略。這樣的歷史現(xiàn)實(shí)，必然會召喚出以少量的增加計(jì)算機(jī)工作量為代價(jià)，但能大幅度降低程序員時(shí)間成本的新的工具和設(shè)計(jì)。這種新的工具，新的設(shè)計(jì)，又對程序設(shè)計(jì)產(chǎn)生革命性的影響。在整個(gè)編程發(fā)展的 歷史上，FORTRAN 和其他高級語言的出現(xiàn)可以說是第一波的革命；而后， UNIX和C語言的興盛，使得系統(tǒng)編程的效率得到革命性提升，可以算是第二波革命；而面向?qū)ο蠓椒?#xff0c;使得復(fù)雜的 GUI 等系統(tǒng)的編程效率得到提升，應(yīng)該算得上是第三波革命。到如今，現(xiàn)在各種各樣的方法論就更加多了，且看以后回看，哪種方法和工具能夠大浪淘沙留下來。
高級編程語言的發(fā)展歷程（四）LISP 和 AI 的青梅竹馬 A
2009-8-31 原文鏈接
LISP 語言的歷史和一些番外的八卦和有趣的逸事，其實(shí)值得花一本書講。我打算用三篇文章扼要的介紹一下 LISP 的早期歷史。講 LISP，躲不過要講 AI （人工智能）的，所以干脆我就先八卦八卦他們的青梅竹馬好了。
翻開任何一本介紹各種編程語言的書，都會毫無驚奇的發(fā)現(xiàn)，每每說到 LISP，通常的話就是“LISP 是適合人工智能（AI）的語言”。我不知道讀者讀到這句話的時(shí)候是怎么理解的，但是我剛上大學(xué)的時(shí)候，自以為懂了一點(diǎn) LISP 和一點(diǎn)人工智能的時(shí)候，猛然看到這句話，打死我也不覺得“適合”。即使后來我看了 SICP 很多遍， 也難以想象為什么它就 “適合” 了， 難道 LISP 真的能做 C 不能做的事情么？難道僅僅是因?yàn)?John McCarthy 這樣的神人既是 AI 之父， 又是 LISP 之父， 所以 AI 和 LISP 兄妹兩個(gè)就一定是很般配？ 計(jì)算機(jī)科學(xué)家又不是上帝，創(chuàng)造個(gè)亞當(dāng)夏娃讓他們沒事很般配干啥？ 既然“本是同根生”這樣的說法是不能讓人信服的，那么到底這句話的依據(jù)在哪里呢？ 我也是后來看 AI 文獻(xiàn)，看當(dāng)年的人工智能的研究情況，再結(jié)合當(dāng)年人工智能研究的指導(dǎo)思想，當(dāng)年的研究者可用的語言等歷史背景，才完全理解“適合” 這兩個(gè)自的。所以，這篇既是八卦，也是我的心得筆記。我們一起穿越到 LISP 和 AI 的童年時(shí)代。雖然他們現(xiàn)在看上去沒什么緊密聯(lián)系， 他們小時(shí)候真的是青梅竹馬的親密玩伴呢！
讓機(jī)器擁有智能，是人長久的夢想，因?yàn)檫@樣機(jī)器就可以聰明的替代人類完成一些任務(wù)。二戰(zhàn)中高速電子計(jì)算機(jī)的出現(xiàn)使得這個(gè)夢想更加近了一步。二戰(zhàn)后，計(jì)算機(jī)也不被完全軍用了，精英科學(xué)家也不要繼續(xù)制造原子彈了，所以，一下子既有資源也有大腦來研究 “智能機(jī)器”這種神奇的東西了。我們可以隨便舉出當(dāng)年研究繁盛的例子：維納在 1948 年發(fā)表了《控制論》，副標(biāo)題叫做 《動物和機(jī)器的控制和通信》，其中講了生物和機(jī)器的反饋，講了腦的行為。創(chuàng)立信息論的大師香農(nóng)在 1949 年提出了可以下棋的機(jī)器，也就是面向特定領(lǐng)域的智能機(jī)器。同時(shí)，1949年，加拿大著名的神經(jīng)科學(xué)家 Donald Hebb 發(fā)表了“行為的組織”，開創(chuàng)了神經(jīng)網(wǎng)絡(luò)的研究；圖靈在 1950 年發(fā)表了著名的題為“計(jì)算的機(jī)器和智能”的文章，提出了著名的圖靈測試。如此多的學(xué)科被創(chuàng)立，如此多的學(xué)科創(chuàng)始人在關(guān)心智能機(jī)器，可見當(dāng)時(shí)的確是這方面研究的黃金時(shí)期。
二戰(zhàn)結(jié)束十年后，也就是 1956 年，研究智能機(jī)器的這些研究者，都隱隱覺得自己研究的東西是一個(gè)新玩意，雖然和數(shù)學(xué)、生物、電子都有關(guān)系，但和傳統(tǒng)的數(shù)學(xué)、生物、電子或者腦科學(xué)都不一樣，因此，另立一個(gè)新招牌成了一個(gè)必然的趨勢。John McCarthy 同學(xué)就趁著 1956 年的這個(gè)暑假，在 Dortmouth 大學(xué)（當(dāng)年也是美國計(jì)算機(jī)科學(xué)發(fā)展的圣地之一，比如說，它是 BASIC 語言發(fā)源地）， 和香農(nóng)、Minsky 等其他人（這幫人當(dāng)年還都是年輕人），一起開了個(gè)會，提出了一個(gè)很酷的詞，叫做 Artificial Intelligence，算是人工智能這個(gè)學(xué)科正式成立。因?yàn)?AI 是研究智能的機(jī)器，學(xué)科一成立，就必然有兩個(gè)重要的問題要回答，一是你怎么表示這個(gè)世界，二是計(jì)算機(jī)怎么能基于這個(gè)世界的知識得出智能。第一點(diǎn)用行話說就 是“知識表示”的模型，第二點(diǎn)用行話說就是“智能的計(jì)算模型”。別看這兩個(gè)問題的不起眼，就因?yàn)楫?dāng)時(shí)的研究者對兩個(gè)看上去很細(xì)微的問題的回答，直接造就了 LISP 和 AI 的一段情緣。
我們各表一支。先說怎么表示知識的問題。AI 研究和普通的編程不一樣的地方在于，AI 的輸入數(shù)據(jù)通常非常多樣化，而且沒有固定格式。比如一道要求解的數(shù)學(xué)題，一段要翻譯成中文的英文，一個(gè)待解的 sodoku 謎題，或者一個(gè)待識別的人臉圖片。所有的這些，都需要先通過一個(gè)叫做“知識表示”的學(xué)科，表達(dá)成計(jì)算機(jī)能夠處理的數(shù)據(jù)格式。自然，計(jì)算機(jī)科學(xué)家想用一種統(tǒng) 一的數(shù)據(jù)格式表示需要處理多種多樣的現(xiàn)實(shí)對象，這樣，就自然的要求設(shè)計(jì)一個(gè)強(qiáng)大的，靈活的數(shù)據(jù)格式。這個(gè)數(shù)據(jù)格式，就是鏈表。
這里我就不自量力的憑我有限的學(xué)識，追尋一下為啥鏈表正好成為理想的數(shù)據(jù)結(jié)構(gòu)的邏輯線。我想，讀過 SICP 的讀者應(yīng)該對鏈表的靈活性深有感觸。為了分析鏈表的長處，我們不妨把他和同時(shí)代的其他數(shù)據(jù)結(jié)構(gòu)來做一比較。如我在前面所說，當(dāng)時(shí)的數(shù)據(jù)結(jié)構(gòu)很有限，所以我們不妨比較一下鏈表和同時(shí)代的另一個(gè)最廣泛使用的數(shù)據(jù)結(jié)構(gòu)——數(shù)組——的優(yōu)劣。我們都知道，數(shù)組和鏈表都是線性數(shù)據(jù)結(jié)構(gòu)，兩者各有千秋，而 FORTRAN 基本上是圍繞數(shù)組建立的，LISP 則是圍繞鏈表實(shí)現(xiàn)的。通過研究下棋，幾何題等 AI 問題的表示，我們的讀者不難發(fā)現(xiàn)， AI 研究關(guān)心于符號和邏輯計(jì)算遠(yuǎn)大于數(shù)值計(jì)算，比如下棋，就很難抽象成一個(gè)基于純數(shù)字的計(jì)算問題。這樣，只能存數(shù)字的數(shù)組就顯得不適合。當(dāng)然我們可以把數(shù)組擴(kuò)展一下，讓這些數(shù)組元素也可以存符號。不過即使這樣，數(shù)組也不能做到存儲不同結(jié)構(gòu)的數(shù)據(jù)。比方說棋類中，車馬炮各有各自的規(guī)則，存儲這些規(guī)則需要的結(jié)構(gòu)和單元大小都不一樣，所以我們需要一個(gè)存儲異構(gòu)數(shù)據(jù)單元的模塊，而不是讓每個(gè)單元格的結(jié)構(gòu)一樣。加上在AI 中，一些數(shù)據(jù)需要隨時(shí)增加和修改的。比如國際象棋里，兵第一步能走兩步，到底部又能變成皇后等等，這就需要兵的規(guī)則能夠隨時(shí)修改、增加、刪除和改變。其他問題也有類似的要求，所有的這些，都需要放開數(shù)組維度大小一樣的約束，允許動態(tài)增加和減少某一維度的大小，或者動態(tài)高效的增加刪除數(shù)組元素。而一旦放開了單元格要同構(gòu)和能隨時(shí)增加和刪除這樣兩個(gè)約束，數(shù)組其實(shí)就不再是數(shù)組了，因?yàn)殡S機(jī)訪問的特性基本上就丟失了，數(shù)組就自然的變成了鏈表，要用鏈表的實(shí)現(xiàn)。
所以，用鏈表而不是數(shù)組來作為人工智能的統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)，固然有天才的靈機(jī)一動，也有現(xiàn)實(shí)需求的影響。當(dāng)然，值得一提的是，在 Common LISP 這樣一個(gè)更加面向?qū)嵺`而不是科學(xué)研究的 LISP 版本中，數(shù)組又作為鏈表的補(bǔ)充，成了基本的數(shù)據(jù)結(jié)構(gòu)，而 Common LISP，也就能做圖像處理等和矩陣打交道的事情。這個(gè)事實(shí)更加說明，用什么樣的數(shù)據(jù)結(jié)構(gòu)作為基本單元，都是由現(xiàn)實(shí)需求推動的。
當(dāng)然，科學(xué)家光證明了列表能表示這些現(xiàn)實(shí)世界的問題還不夠，還要能證明或者驗(yàn)證額外的兩點(diǎn)才行。第一點(diǎn)是列表表示能夠充分的表示所有的人工智能問題，即列表結(jié)構(gòu)的充分性。只有證明了這一點(diǎn)，我們才敢放心大膽的用鏈表，而不會擔(dān)心突然跳出一個(gè)問題鏈表表達(dá)不了；第二是人工智能的確能夠通過對列表的某種處理方法獲得，而不會擔(dān)心突然跳出一個(gè)人工智能問題，用現(xiàn)有的對鏈表的處理方法根本沒法實(shí)現(xiàn)。只有這兩個(gè)問題的回答是肯定的時(shí)候，列表處理才會成為人工智能的一部分。
對于這兩個(gè)問題，其實(shí)都并沒有一個(gè)確定的答案，而只是科學(xué)家的猜想，或者說是一種大家普遍接受的研究范式（paradigm）。 在 1976 年，當(dāng)年構(gòu)想 IPL(Information Processing Language)，也就是 LISP 前身的兩位神人 Alan Newell 和 Herbert Simon，終于以回憶歷史的方式寫了一篇文章。在這篇文章中，他們哲學(xué)般的把當(dāng)時(shí)的這個(gè)范式概括為：一個(gè)物理符號系統(tǒng)對于一般智能行為是既充分又必要的（ A physical symbol system has the necessary and sufficient means for general intelligence action）。用大白話說就是，“智能必須依賴于某種符號演算系統(tǒng)，且基于符號演算系統(tǒng)也能夠衍生出智能”。在實(shí)踐中，如果你承認(rèn)這個(gè)猜想，或者說這個(gè)范式，那你就承認(rèn)了可以用符號演算來實(shí)現(xiàn) AI。于是，這個(gè)猜想就讓當(dāng)時(shí)幾乎所有的研究者，把寶押在了實(shí)現(xiàn)一個(gè)通用的符號演算系統(tǒng)上，因?yàn)榧偃缥覀冎圃斐鲆粋€(gè)通用的基于符號演算的系統(tǒng)，我們就能用這個(gè)系統(tǒng)實(shí)現(xiàn)智能。
上面我們說過，鏈表的強(qiáng)大的表達(dá)能力對于這個(gè)符號演算系統(tǒng)來講是綽綽有余的了，所以我們只要關(guān)心如何實(shí)現(xiàn)符號演算，因?yàn)榧偃缟厦娴牟孪胧菍Φ?#xff0c;且鏈表已經(jīng)能夠表示所有的符號，那么我們的全部問題就變成了如何去構(gòu)建這樣的符號演算系統(tǒng)。后面我們可以看到，LISP 通過函數(shù)式編程來完成了這些演算規(guī)則的構(gòu)建。
這里，需要提請讀者注意的是，LISP 的全稱是 LISt Processing，即列表處理，但實(shí)際上 LISP 是由兩種互相正交的哲學(xué)組合形成的，一個(gè)是列表處理，另一個(gè)是函數(shù)式編程。雖然在下面以后，我們會介紹 S-Expression 這樣美妙的把兩者無縫結(jié)合在一起的形式，但是為了清晰我們的概念，我要強(qiáng)調(diào)一下列表處理和函數(shù)式編程是兩個(gè)正交的部分。實(shí)際上，我們完全可以用其他的不是函數(shù)的方式構(gòu)建一個(gè)列表處理語言。在歷史上，早在 FORTRAN 出現(xiàn)之前，Alan Newell 和 Herbert Simon 就用匯編實(shí)現(xiàn)了一個(gè)叫 IPL 的語言，而這個(gè) IPL 語言就是面向過程的對列表處理的，而后，McCarthy 一開始也是用一系列的 FORTRAN 子程序來做列表處理的。比如 LISP 里面的 CAR 操作，其全稱實(shí)際上是 Content of the Address portion of the Register， 顧名思義，寄存器的地址單元內(nèi)容，也即列表的第一個(gè)元素（和C表達(dá)數(shù)組的方式類似，這里寄存器中存著指向列表第一個(gè)元素的指針）。 函數(shù)式的卻不以列表為基本數(shù)據(jù)單元的語言也很多，比如 Scala ，就是以對象為基本數(shù)據(jù)單元。 因此，函數(shù)式和列表處理是不一定要互相耦合的。 那么，到底是什么原因使得 LISP 選擇函數(shù)式，這樣的選擇又為啥更加適合當(dāng)時(shí) AI 的研究呢，我們下節(jié)將繼續(xù)介紹當(dāng)時(shí) AI 的研究范式，強(qiáng)弱 AI 之間的辯論和函數(shù)式編程在當(dāng)年 AI 研究上的優(yōu)點(diǎn)。
高級編程語言的發(fā)展歷程（五）LISP 和 AI 的青梅竹馬 B
2010-2-10 原文鏈接
上回我們說到 LISP 和 AI 很是青梅竹馬的時(shí)候，浮光掠影地說因?yàn)?LISP 的基本數(shù)據(jù)單元——”鏈表”在知識表示上的比較優(yōu)勢。我們說， AI 要處理的數(shù)據(jù)結(jié)構(gòu)和要刻畫的現(xiàn)實(shí)世界的模型很復(fù)雜，使得數(shù)組等其他簡單數(shù)據(jù)結(jié)構(gòu)不能勝任，所以“鏈表”成了最佳的選擇。如果我們順著這樣的邏輯線往下看， 似乎選擇 LISP 這個(gè)“列表處理的語言”似乎是理所當(dāng)然的。可是，這個(gè)原因并不充分。因?yàn)?LISP 語言可不僅僅是列表處理，還包括函數(shù)式編程等等其他。反過來說，如果僅僅是列表處理對于 AI 至關(guān)重要的話，那么在 FORTRAN 和 ALGOL 這些通用編程語言又非常普及的傳統(tǒng)語言里面寫一些關(guān)于列表處理的函數(shù)豈不是更加直觀和方便？ 歸根結(jié)底，到底 LISP 還有什么其他奧妙呢？
當(dāng)我們追尋函數(shù)式編程這條線索的時(shí)候，就會不可避免的觸及到 AI 的早期歷史。LISP 的特性，其實(shí)都是和當(dāng)時(shí) AI 的范式 (paradigm) 息息相關(guān)的。
AI 范式的演變
早在 McCarthy 這一代人提出 AI 之前，馮諾伊曼等人就開始研究什么是智能以及如何實(shí)現(xiàn)智能的問題了。所不同的是，他們更加偏重于研究大腦的內(nèi)部工作機(jī)理，并且試圖通過在模擬大腦的工作機(jī)理，來實(shí)現(xiàn)智能。這一學(xué)派的哲學(xué)很清晰： 人類大腦是一個(gè)標(biāo)準(zhǔn)的智能體，我們只需要讓計(jì)算機(jī)模擬人的大腦的工作方式，計(jì)算機(jī)就有了和人類大腦一樣的智能了。對于這一派的研究者來說，他們相信大腦的結(jié)構(gòu)和工作機(jī)理決定了智能，至于大腦是用腦細(xì)胞構(gòu)成的，還是用電子電路模擬的，對于智能來說毫不重要。這方面的著名工作就是馮·諾伊曼的《計(jì)算機(jī)和大腦》這篇論文。在這篇不算很學(xué)術(shù)的隨筆里面，他分析了人的大腦有多少個(gè)神經(jīng)元，計(jì)算機(jī)有多少個(gè)晶體管，通過這些定量的比較來解釋計(jì)算機(jī)和人的大腦的差距。當(dāng)時(shí)和馮·諾伊曼齊名的另一個(gè)神童是開創(chuàng)控制論的維納。他和馮·諾伊曼一樣，兼通很多學(xué)科。和馮·諾伊曼一樣，他職業(yè)是數(shù)學(xué)家，但是也精通如神經(jīng)科學(xué)和腦科學(xué)等學(xué)科。 一個(gè)顯然的例子就是在《控制論》這本書里面， 維納對大腦和神經(jīng)的分析比比皆是。這種對大腦和神經(jīng)分析的傳統(tǒng)，從 Cajal （對，就是寫 Advice for a Young Investigator 的那個(gè)大神)）開始，一直延續(xù)到了后來 AI 中的聯(lián)接主義（主要研究神經(jīng)網(wǎng)絡(luò)的一個(gè)人工智能學(xué)派）。
可是，從腦科學(xué)和認(rèn)知科學(xué)的角度去分析智能在當(dāng)時(shí)有一個(gè)非常大的局限: 腦神經(jīng)解剖學(xué)本身不成熟。比方說，現(xiàn)如今腦科學(xué)家在分析腦功能的時(shí)候一般會借助于 fMRI 和其他一些神經(jīng)造影技術(shù)。這些技術(shù)可以做到實(shí)時(shí)觀測到腦中血氧分布，直接確定大腦在執(zhí)行特定任務(wù)時(shí)候的活躍部分。當(dāng)年的科學(xué)家則只能使用有限的幾種醫(yī)學(xué)成 像技術(shù)，或者從血管攝影的角度研究大腦。受限于當(dāng)時(shí)的研究條件，當(dāng)年的研究者很難直接觀測到腦神經(jīng)的實(shí)時(shí)工作狀態(tài)，分析大腦的實(shí)時(shí)工作機(jī)理。因此，對腦的研究就很難做到非常深刻。醫(yī)學(xué)研究條件的限制，加上當(dāng)時(shí)電子學(xué)的發(fā)展和集成度遠(yuǎn)遠(yuǎn)不夠，用電子電路模擬大腦生成智能就顯得非常遙遠(yuǎn)。因此，雖然這一派的思想超前，但是大部分的工作都不在于真正的用電子電路模擬大腦，而是在探索腦科學(xué)和神經(jīng)科學(xué)本身，或者僅僅用電子電路模擬一些簡單的神經(jīng)動力學(xué)行為和小規(guī)模神經(jīng)網(wǎng)絡(luò)。正是因?yàn)檫B接主義在實(shí)現(xiàn)人工智能本身方面進(jìn)展并不大，所以在AI領(lǐng)域中一直不是潮流的研究方向。上個(gè)世紀(jì) 80 年代前成功實(shí)施的一些人工智能系統(tǒng)，極少是來自于連接主義學(xué)派的。直到80年代后隨著 BP 算法的重新發(fā)現(xiàn)，聯(lián)接主義才迎來了第二春。這時(shí)候，LISP 已經(jīng)過完 20 歲生日了。所以，聯(lián)接主義 對 AI 領(lǐng)域使用的編程語言的選擇的影響并不算大。
符號主義
雖然聯(lián)接主義這一學(xué)派在當(dāng)時(shí)不怎么流行，當(dāng)年的 AI 研究可是進(jìn)行的如火如荼。這如火如荼的學(xué)派，采用的是另外一套方法，我們稱之為“符號主義學(xué)派”。符號主義學(xué)派的淵源，可以直接追溯到圖靈。圖靈在人工智能方面做過很多的研究，其中最為大家所知的就是“圖靈測試“了。有句俗話叫做“在網(wǎng)上，沒人知道你是一條狗”， 在這句話里，只要把“狗”換成“計(jì)算機(jī)”，就是簡單版的圖靈測試了。用個(gè)比較“潮”的比方，圖靈測試就是讓一臺計(jì)算機(jī)或者一個(gè)真實(shí)的人（又叫評委）在網(wǎng)上交流，然后讓這個(gè)評委猜測和他交談的究竟是人還是計(jì)算機(jī)。如果這位評委也不能分辨談話的對方到底是人還是計(jì)算機(jī)的話，我們就認(rèn)為這個(gè)計(jì)算機(jī)已經(jīng)足以“以假亂真”，擁有“和人類一樣的智能”了，也就是通過“圖靈測試了”。
在很長一段時(shí)間里，圖靈測試一直是人工智能研究的圣杯(holy grail)。也就是說，通過”圖靈測試“ 成了人工智能研究的終極目標(biāo)。那么，自然的，最最直接的通過圖靈測試的方法不是讓計(jì)算機(jī)和人腦一樣思考，而是只要能夠讓計(jì)算機(jī)處理對話中用到的的單詞、句子和符號，并且在對話中能夠和人一樣的操縱這些單詞和符號，計(jì)算機(jī)就有很大的希望通過圖靈測試。從最極端的情況來看，計(jì)算機(jī)甚至都不需要去“理解”這些句子的含義，都有可能通過圖靈測試。[具體細(xì)節(jié)可以閱讀 Wikipedia 上的“Chinese Room (中文房間)”條目]。有一個(gè)開源的聊天機(jī)器人，叫做 A.L.I.C.E.， 就把上面我們說的“只要能夠處理和操縱符號，就有可能通過圖靈測試”發(fā)揮到了近乎極致。這個(gè)聊天機(jī)器人在圖靈測試比賽中已經(jīng)多次騙過人類評委，到了非常 “智能”幾乎能以假亂真的地步?？墒?#xff0c;就是這樣一個(gè)離通過圖靈測試很近的機(jī)器人，其基本結(jié)構(gòu)卻簡單到了我們都不能想像的地步：A.L.I.C.E. 的數(shù)據(jù)庫里面有一條一條的規(guī)則，這些規(guī)則規(guī)定了她看到你說什么的時(shí)候她說什么。唯一有點(diǎn)“智能”的地方，就是有些規(guī)則不光取決于你這句話，還取決于你的上一句話。[比如日常對話中我們先問“你喜歡看電影么？”，接著再問“什么類型的？”，這時(shí)候就需要前一句話推出這個(gè)問題是“（喜歡）什么類型的（電 影)”]?！爸形姆块g”的例子，和 A.L.I.C.E. 機(jī)器人如此簡單的結(jié)構(gòu)，都出人意料的顯示出，即使計(jì)算機(jī)擁有了對符號的操作能力，通過了圖靈測試，它也未必是“有智能”的。可惜這句話只是我的馬后炮而已，在 AI 發(fā)展的早期，因?yàn)閳D靈測試的拉動，聯(lián)接主義的相對弱勢和符號主義的繁盛，都把全世界的 AI 研究往一個(gè)方向拽，這個(gè)方向，很自然的，就是“符號處理”。
符號處理和 LISP 補(bǔ)充
其實(shí)上一篇我們已經(jīng)提到了，Alan Newell 和 Herbert Simon 認(rèn)為對符號演算系統(tǒng)就可以衍生出智能，所以上面的文字，算是對符號主義這個(gè) paradigm 做一個(gè)歷史的小注解。當(dāng)我們把 LISP 放到這段歷史中，就會自然的想到， 什么語言適合人工智能的問題，就變成了“什么語言能做符號處理”。這個(gè)問題的答案，讀者也都猜到了，就是 LISP。
符號處理在 LISP 里面的長處前文我已經(jīng)介紹過一些了，這里我們可以再補(bǔ)充幾點(diǎn)零碎的。LISP 里有一個(gè)大家都知道的統(tǒng)一表示程序和數(shù)據(jù)的方法，叫做 S-Expression。這個(gè) S，其實(shí)就是 Symbolic 的意思。把程序和數(shù)據(jù)都統(tǒng)一的當(dāng)成符號，用現(xiàn)代編程語言的話說，就是 LISP 支持 meta-programming。LISP 程序可以處理，生成和修改 LISP 程序。這個(gè)特性，加上函數(shù)是一階對象的特性，使得 LISP 遠(yuǎn)遠(yuǎn)比同時(shí)代的任何語言靈活。我本人不是 LISP 的用戶（初級用戶都算不上），因此在這一點(diǎn)上所知有限。但單就我有限的對 LISP 的理解，我認(rèn)為 LISP 的這種靈活，恰好滿足了基于符號處理的 AI 領(lǐng)域?qū)φZ言的“強(qiáng)大的表達(dá)能力”（可以對任何復(fù)雜系統(tǒng)建模）和“高層的抽象能力” 的需求。關(guān)于第一點(diǎn)，有一個(gè)著名的段子，說任何一門編程語言技巧和思想被提出的時(shí)候，總會有一個(gè)高人出來，說，這個(gè)玩意兒在 LISP 里面早就有了，具體的例子包括剛才說的 metaprogramming， object oriented language。這里面蘊(yùn)含的，就是 LISP 的強(qiáng)大的表達(dá)能力，使得很多編程的范式，在 LISP 里面都能實(shí)現(xiàn)，或者找到影子。關(guān)于第二點(diǎn)，SICP 中例子比比皆是，講得都比我深刻許多，就無需廢話了。
在上篇文章中我提到，翻開任何一本編程的書，都會講到“LISP是適合 AI 的編程語言”。那么，如果您和我當(dāng)年一樣，有興趣從事 AI 方面的研究和探索，就不免要疑惑：“為了學(xué)習(xí) AI， 我要不要學(xué)習(xí) LISP” 呢？現(xiàn)在距離我當(dāng)年的這個(gè)疑惑已經(jīng)差不多8年了，我并沒有一個(gè)確定的答案，但是我知道了更多的一些事實(shí)。
如今的 AI 范式
如果你讓任何一個(gè) AI 方向的研究者推薦幾本適合初學(xué)者的書的話，十有八九他會提到 “Artificial Intelligence: A Modern Approach”(人工智能，一種現(xiàn)代方法) 和 “Artificial Intelligence: A New Synthesis” (人工智能，一個(gè)新的綜述)。這兩本書的作者分別是 Peter Norvig 和 Nils Nilsson，都是 AI 領(lǐng)域的元老級人物。如果你是一個(gè)對書名很敏感的人，你肯定會想：奇怪了，這種書又不是暢銷書，難道這兩位大牛寫了書怕賣不出去，非要在書名上加一個(gè) “現(xiàn)代” 或者 “新” 來吸引眼球？ 事實(shí)上，這個(gè)“現(xiàn)代”和這個(gè)“新”都大有來頭。實(shí)際上，這二十年來，AI 研究領(lǐng)域接連發(fā)生了好幾個(gè)非常大的 paradigm shift. 傳統(tǒng)的基于符號的 AI 方法不再是主流，取而代之的，是多種多樣的基于統(tǒng)計(jì)的，基于自動推理的，基于機(jī)器學(xué)習(xí)的，基于群體智慧的，基于大規(guī)模數(shù)據(jù)集的等等各種各樣研究方法的興起。這個(gè) paradigm shift， 對于領(lǐng)域之外的人好像是靜悄悄的，可實(shí)際上 AI 領(lǐng)域早已發(fā)生了翻天覆地的變化。所以才會有 “新” 和 “現(xiàn)代” 這樣的詞出現(xiàn)在書標(biāo)題上。不幸的是，大多寫編程語言書的作者，未必全部知曉這個(gè)變化，因此還沿襲原來的框架，繼續(xù)寫下 “LISP是適合 AI 的編程語言” 這樣一個(gè)早就不能完全反映現(xiàn)狀的斷言。如果我們統(tǒng)計(jì)一個(gè)從事 AI 研究的研究者或者科學(xué)家用什么語言，答案可能是五花八門無所不有： 做 AI Search 的用 C/C++/Java， 做機(jī)器學(xué)習(xí)的如果模型和矩陣關(guān)系密切，可以用 Matlab， 如果統(tǒng)計(jì)計(jì)算較多，也可以用 R。至于做數(shù)據(jù)挖掘等等，語言和庫更加五花八門，根本無法宣稱那一個(gè)語言占上風(fēng)。LISP 是適合 AI 的語言的教科書神話，也早就被無數(shù)的這樣的實(shí)例給打破了。（延伸閱讀：Why is Lisp used for AI?）
高級編程語言的發(fā)展歷程（六）SCHEME 語言是怎么來的
2010-7-12 原文鏈接
導(dǎo)言
Scheme 是 LISP 的一個(gè)方言(dialect)。著名的 SICP 書就是以 Scheme 為教學(xué)語言（實(shí)際上 SICP 的作者就是 Scheme 的作者）。雖然 Scheme 本身只是一個(gè)精簡化的適合教學(xué)的語言，可它首先提出的一些重要的思想，引領(lǐng)了新一代的 LISP 語言的出現(xiàn)。實(shí)際上， LISP 語言發(fā)展的歷史是連續(xù)的，之所以我在這里人為的把 LISP 的發(fā)展史劃分為上一代和現(xiàn)代，是因?yàn)殡S著 Scheme 首次引入并規(guī)范化了一些重要概念， LISP 語言出現(xiàn)了很多以前從來沒有大規(guī)模普及的新特性。以 Common LISP 為代表的 LISP 語言也因?yàn)檫@些新特性，而煥發(fā)了第二春。人所共知的 Paul Graham 大叔，借著這一波 LISP 復(fù)興的浪潮，不光寫出了 On Lisp 這樣的好書；而且還用 Common LISP 寫出了一個(gè)在線電子商務(wù)平臺，在 1998 年的時(shí)候以近 5 千萬美元的價(jià)格賣給了 Yahoo! （憑借這筆買賣, Paul 大叔現(xiàn)在經(jīng)營著 Y Combinator 天使投資，成為硅谷著名的天使）。前段時(shí)間賣給 Google 的 ITA，負(fù)擔(dān)著世界上大部分的航班資訊查詢，核心系統(tǒng)也是 Common LISP。雖然不該把 Common LISP 的很多成就全部歸結(jié)到 Scheme, 但 Scheme 作為一個(gè)重要的歷史分水嶺，探究一下它的歷史來源還是很有趣的。
函數(shù)作為一級對象
我們都知道 LISP 是一個(gè)函數(shù)式的編程語言。在 LISP 中，函數(shù)是一種基本類型。類比的看，C 家族的語言中，整數(shù)是一個(gè)基本的類型，所以，整數(shù)類型的變量既可以作為參數(shù)傳遞給一個(gè)函數(shù)，也可以作為返回值返回。比如，兩個(gè)整數(shù)求和這個(gè)函數(shù)，用 C 家族的語法就是：
int add(int a, int b);因?yàn)樵?LISP 里面，函數(shù)也成了基本類型。如果我們有一個(gè) add 函數(shù)如下：
(define (add x y) (+ x y))顯然，它在 LISP 里就和 C 里的 int 一樣，能夠作為參數(shù)傳遞給其他函數(shù)。
函數(shù)作為參數(shù)在 LISP 里非常普遍。我們知道著名的 APPLY MAP 和 REDUCE 這三個(gè)“高階”函數(shù)（所謂高階的意義就是參數(shù)可以是函數(shù)）。其中 APPLY 的最基本形式可以帶兩個(gè)參數(shù)，第一個(gè)參數(shù)是函數(shù)，第二個(gè)參數(shù)是一個(gè)列表。APPLY 的效果就是把這個(gè)列表作為參數(shù)表，送給第一個(gè)參數(shù)所代表的函數(shù)求值。如果我們在 LISP 里面用 APPLY(add, (1, 2)) 結(jié)果就是3，即把 (1,2) 送給add 作為參數(shù)，結(jié)果自然是 3。這是函數(shù)作為參數(shù)的例子，還有函數(shù)作為返回值的例子就不一一列舉了。
自由變量的幽靈
在 add 這個(gè)函數(shù)的定義中我們可以看到，它的結(jié)果和兩個(gè)輸入值 x, y 有關(guān)。如果我們用 add(1,2) 調(diào)用 add 函數(shù)， 我們至少期望變量 x 會被賦值為 1， 變量 y 被賦值為 2。而結(jié)果 (+ x y) 則相應(yīng)的為 3。在這個(gè)簡單的例子中， 顯然，如果 x 和 y 有一個(gè)值不知道的話， (+ x y) 的計(jì)算就無法完成。我們暫且把這些對函數(shù)求值不可缺少的變量稱之為“必要變量”。顯然，這些必要變量的值是需要確定的，否則函數(shù)無法進(jìn)行求值。在我們 add 函數(shù)的例子里，x, y 這兩個(gè)變量既是全部的必要變量，又是這個(gè)函數(shù)的參數(shù)，所以這個(gè)函數(shù)的結(jié)果就完全由輸入的 x, y 的值確定。可以想象，任何一個(gè)像 add 這樣的所有的必要變量都是來自于輸入?yún)?shù)的函數(shù)，不論在什么地方被調(diào)用，只要輸入的參數(shù)值一樣，輸出的結(jié)果必然一樣。
如果現(xiàn)實(shí)中所有的函數(shù)都有上面的性質(zhì)的話，那就沒有這篇文章了?？上У氖俏覀兒芸彀l(fā)現(xiàn)有好多函數(shù)不符合上面我們說的“輸入的參數(shù)值一樣，輸出的結(jié)果必然一樣”這個(gè)結(jié)論。我們甚至無須用 LISP 里面的例子來說明這一點(diǎn)。用 C 語言的都知道，取系統(tǒng)當(dāng)前時(shí)間的函數(shù) time，以及取隨機(jī)數(shù)的函數(shù) rand, 都是不需要輸入值（0個(gè)輸入?yún)?shù)）。因此任何時(shí)候這兩個(gè)函數(shù)被調(diào)用的時(shí)候，我們都可以認(rèn)為輸入值一樣（為 void 或 null)。但我們在不同的時(shí)間調(diào)用 time 或者多次調(diào)用 rand，很顯然可以知道他們輸出的結(jié)果不可能每次一樣。
函數(shù)式編程里面有更多的類似的例子。這些例子說明了的確有些函數(shù)，對于同樣的輸入值，能夠得到不同的結(jié)果。這就很顯然的表明，這些函數(shù)的必要變量中，有些不是函數(shù)的輸入?yún)?shù)或者內(nèi)部變量。我們把這些變量，叫做自由變量(free variable) [相反的那些被成為受限變量(bounded variable)]。這里的自由和受限，都是相對函數(shù)講的，以變量的取值是不是由函數(shù)本身決定來劃分的。
雖然自由和受限變量是函數(shù)式語言里面的概念，但在命令式語言中也有影子。比方說，C 語言中，函數(shù)中用到的全局變量就是自由變量；在 Java 程序中，匿名內(nèi)部類里面的方法可以用到所在外部類中的成員變量或者所在方法里標(biāo)記為 final 的那些變量。這些可以被內(nèi)部類的方法訪問的，又不在內(nèi)部類方法的參數(shù)表里面的變量都是自由變量。樂意翻看 GNU C Library 的好奇讀者會看到，GNU libc 中的 rand 函數(shù)就用到了一個(gè) random_data 的變量作為自由變量 (glibc/stdlib/random.c)。time 也是一樣，通過一個(gè)系統(tǒng)調(diào)用來設(shè)置時(shí)間，而這在原理上等價(jià)于用到一個(gè)叫做”當(dāng)前時(shí)間”的自由變量 (glibc/stdlib/time/time.c)。
我們知道，在高級語言里面僅僅設(shè)計(jì)或者加入一個(gè)特性不難，難的是讓所有的特性能協(xié)調(diào)一致的工作。比方說 Java 語言假設(shè)一切均為為對象，容器類型也假設(shè)裝著對象，但是 int 類型卻不是對象，讓無數(shù)程序員為裝箱拆箱大汗淋漓。回到 LISP， 當(dāng)函數(shù)允許自由變量，函數(shù)有能夠被作為參數(shù)傳來傳去的時(shí)候，自由變量的幽靈就隨著函數(shù)作為參數(shù)傳遞而在程序各處游蕩。這就帶來了兩個(gè)問題，一個(gè)涉及到自由變量的值的確定機(jī)制，另一個(gè)涉及到這個(gè)機(jī)制的實(shí)現(xiàn)。
兩種作用域
為了說明自由變量的幽靈和作用域，我們還是從一個(gè)例子入手。假設(shè)我們要一個(gè)做加 n 的函數(shù)。為了體現(xiàn)出自由變量，我們把它寫成
(define (addn s) ( lambda x (+ x s)))這個(gè)函數(shù)本身沒什么特別的：輸入一個(gè) s, 輸出一個(gè) 對任意 x 返回 x+s 的函數(shù)。注意到這個(gè)函數(shù)的“返回值”是一個(gè)函數(shù)?；谶@個(gè) addn 函數(shù)，我們可以定義 +1 函數(shù) add1 函數(shù)如下
(define (add1 s) ((addn 1) s))這個(gè)也很好解釋，如果輸入一個(gè) s， (addn 1) 返回了一個(gè)加一函數(shù)，這個(gè)函數(shù)作用在 s 上，即可得到 s+1。一切看上去很順利，直到我們用一個(gè) Scheme 出現(xiàn)前的 LISP 解析器去計(jì)算 (add1 4)。我們期望得到的值是 5， 而它給你的值可能是 8。怎么回事？
為了解釋這個(gè) 8 的來源，我們可以模擬一下一個(gè)基于棧的解釋器的工作過程。(add1 4) 調(diào)用首先將參數(shù) s 賦值為 4 然后，展開 add1 函數(shù)，即將 s=4 壓棧，計(jì)算 (addn 1)。在調(diào)用 addn 時(shí)。s 又作為了 addn 的形式參數(shù)。因此，按照基于棧的解釋器的標(biāo)準(zhǔn)做法，我們在一個(gè)新的活動窗口中將 s =1 壓棧。addn 這個(gè)函數(shù)返回的是一個(gè) “l(fā)ambda x (+ x s)” 的函數(shù)，其中 s 是自由變量。然而一旦 addn 返回，棧中的 s=1 就會被彈出。當(dāng)我們把這個(gè)返回了的 lambda 表達(dá)式作用到 4 上求值時(shí)候，x 是這個(gè) lambda 表達(dá)式傳入的形式參數(shù)，賦值為 4，棧里面的 s 的值 只有 s=4, 因此 (+ x s) 得到的是 8。
這顯然不是我們想要的。總結(jié)這個(gè)結(jié)果錯(cuò)了的原因，是因?yàn)槲覀兊慕忉屍鳑]有限定 lambda x (+ x s) 里面的自由變量 s 為 1。而是在計(jì)算這個(gè) lambda 表達(dá)式的時(shí)候才去查找這個(gè)自由變量的值。自由變量的幽靈在函數(shù)上開了一個(gè)后門，而我們沒有在我們想要的地方堵上它，讓它在函數(shù)真正求值的時(shí)候泄漏出來。
我們不是第一個(gè)發(fā)現(xiàn)這個(gè)問題的人。實(shí)際上， LISP 剛出來沒多久，就有人向 LISP 的發(fā)明人 John McCarthy 報(bào)告了這個(gè) “BUG”。John 也認(rèn)為這是一個(gè)小 BUG，就把球踢給了當(dāng)時(shí)寫 LISP 實(shí)現(xiàn)的 Steve Russell。此人我之前介紹過，乃是一個(gè)水平很高的程序猿(Code Monkey)。他認(rèn)識到，這個(gè)問題的來源，在于返回的 lambda 表達(dá)式失去了不應(yīng)該失去的確定它自由變量值的環(huán)境信息，在求值的時(shí)候，這些環(huán)境信息應(yīng)該跟著這個(gè) lambda 表達(dá)式一起。這樣才能保證沒有這個(gè) BUG。不過 lambda 表達(dá)式在 LISP 語言中已經(jīng)成型了，所以他就引入了一個(gè)新叫做 FUNCTION 的修飾符。作為參數(shù)的 lambda 表達(dá)式或函數(shù)要改寫成 (FUNCTION lambda) 。這樣，這個(gè) lambda 表達(dá)式在被 eval 解析的時(shí)候就會被標(biāo)記成 FUNARG，并且靜態(tài)綁定到解析時(shí)所在環(huán)境。而用 APPLY 對函數(shù)求值時(shí)，有 FUNARG 標(biāo)簽的函數(shù)會在當(dāng)時(shí)綁定的環(huán)境中求值，而不是在當(dāng)前環(huán)境中求值。自由變量沒有到處亂跑，而是被限制在了當(dāng)時(shí)綁定的環(huán)境里面。Russell 的這個(gè)巧妙設(shè)計(jì)，成功關(guān)閉了自由變量在函數(shù)上開的口。這種加上了環(huán)境的函數(shù)就既能夠被四處傳遞，而不需要擔(dān)心自由變量的幽靈到處亂串。這個(gè)東西，后來就被 稱為“閉包”。Russell 用 FUNCTION，以用一種“裝飾”的方式，在 LISP 1.5 中第一次引入和實(shí)現(xiàn)了閉包。
在編程語言的術(shù)語中，上面的讓自由變量自由自在的在運(yùn)行時(shí)賦值的機(jī)制，一般叫做動態(tài)作用域(dynamic scope)，而讓函數(shù)和確定自由變量值在解析時(shí)靜態(tài)綁定的機(jī)制，一般稱之為靜態(tài)作用域(static dynamic scope)。既然是靜態(tài)綁定的環(huán)境是解析的時(shí)候確定的，而解析器是逐行解析程序的，所以，靜態(tài)作用域的環(huán)境是完全由程序代碼的結(jié)構(gòu)確定的。因此有時(shí)候靜態(tài)作用域又被等價(jià)的稱為“文法作用域”(lexical scope)。上面我們的例子里。我們的真正意圖是使用靜態(tài)作用域，卻遇到了一個(gè)使用動態(tài)作用域的 LISP 解析器，因此出現(xiàn)了 (add1 4) 等于 8 的錯(cuò)誤。但這個(gè)問題并不足以說明靜態(tài)作用域一定好。動態(tài)作用域的問題，關(guān)鍵在于違反了 Alpha 變換原則和封裝原則，不過不在此詳細(xì)展開了。
高級編程語言的發(fā)展歷程（七）?LISP 語言前傳
2011-9-27 原文鏈接
Lisp 的主要設(shè)計(jì)者 John McCarthy 曾經(jīng)就 Lisp 的發(fā)展史，專門寫過一篇?History of Lisp?的文章。這里介紹的歷史，基本史實(shí)部分參照了 John McCarthy 的這篇文章，以及同時(shí)期 MIT 的關(guān)于 Lisp 的技術(shù)報(bào)告。
Lisp 的歷史要從 IBM 的神奇機(jī)器 704 說起。此時(shí)是 1954 年，盡管距離 1946 年第一臺計(jì)算機(jī) ENIAC 的出現(xiàn)已經(jīng)八年了，商用計(jì)算機(jī)市場還僅僅起步。很早就進(jìn)入計(jì)算機(jī)市場的 IBM 做出了一個(gè)影響深遠(yuǎn)的決定：發(fā)布一臺可以進(jìn)行浮點(diǎn)計(jì)算的，面向科學(xué)和工程的電子計(jì)算機(jī)。這臺計(jì)算機(jī)，很樸素地跟著 IBM 之前發(fā)布的 701，702 后，被編號成 704（不知為什么 IBM 從來沒公布過 703）。說 704 是神奇機(jī)器，是因?yàn)檫@臺機(jī)器在計(jì)算機(jī)科學(xué)發(fā)展史上意義重大：世界上最早的語音合成程序就是由 Bell 實(shí)驗(yàn)室的科學(xué)家在 IBM 704 上完成的。 Fortran，Lisp 也是最早在 IBM 704 上實(shí)現(xiàn)的。
和當(dāng)年的所有計(jì)算機(jī)一樣，IBM 704 是個(gè)百萬美元級別的大玩具，不是一般人甚至一般大學(xué)能夠買得起的。好在 IBM 和大學(xué)的關(guān)系一向很緊密，在 1957 年的時(shí)候，決定捐一臺 704 給 MIT。當(dāng)時(shí)在 Dartmouth 教書的 John McCarthy 和在 MIT 教書的 Marvin Minsky 關(guān)系很好，因此這臺即將到達(dá)的 704，即將成為 McCarthy 的新玩具。
當(dāng)年部署一臺計(jì)算機(jī)的周期很長，為了不讓自己閑著，McCarthy 決定一邊等機(jī)器部署，一邊研究一下如果有了這臺機(jī)器，可以做點(diǎn)什么。當(dāng)時(shí) Minsky 手里有一個(gè) IBM 的項(xiàng)目，內(nèi)容是使用計(jì)算機(jī)證明平面幾何問題。既然計(jì)算機(jī)沒來不能寫程序，他們就只能從抽象的層面思考問題的解決方法。這個(gè)思考的結(jié)果，是開發(fā)一套支持符號計(jì)算的 FORTRAN?子系統(tǒng)。他們的基本想法是，用一系列的 FORTRAN 子程序，來做邏輯推理和符號演繹。
回頭看，這條路的確繞開了沒有 704 就寫不了程序的路障。因?yàn)槲覀冎恍枰笾铝私?Fortran 能夠做什么，不能做什么，無需實(shí)際 Fortran 編程，就可以假想我們已經(jīng)有了一系列未來可以實(shí)現(xiàn)的子程序，然后只要在數(shù)學(xué)上證明這些通過子程序的組合，加上自動邏輯推理，就可以證明平面幾何定理。這就把一個(gè)計(jì)算機(jī)工程學(xué)問題，抽象成了一個(gè)數(shù)學(xué)問題（日后這個(gè)領(lǐng)域被正式劃歸到人工智能的學(xué)科中，但在當(dāng)時(shí)這還是屬于數(shù)學(xué)問題）
這樣，計(jì)算機(jī)沒來之前，McCarthy 的最終結(jié)果，是一個(gè)用 Fortran 子程序做列表處理的簡單系統(tǒng)。McCarthy 的這條路很現(xiàn)實(shí)的做法——如果不用 Fortran 而是自己寫一個(gè)新的語言的編譯器話，可能需要好幾年的時(shí)間。而 McCarthy 當(dāng)年還不是終身教授，投入到寫作新語言這樣曠日持久且不能保證成果的項(xiàng)目中去，不會對他的職業(yè)生涯有太大的正面作用。
704 送到 MIT 后， McCarthy 帶著兩個(gè)研究生，將之前計(jì)劃的 Fortran 列表處理子程序?qū)崿F(xiàn)了，并命名為 Fortran 列表處理語言 (FLPL) 。然而，因?yàn)?Fortran 語言本身的限制，McCarthy 對 FLPL 并不滿意。他在寫作自動求函數(shù)導(dǎo)數(shù)的程序時(shí)[讀過 SICP 的讀者會發(fā)現(xiàn)這是一道習(xí)題]，發(fā)現(xiàn) FLPL 的弱點(diǎn)集中體現(xiàn)在兩個(gè)地方。
第一個(gè)問題是遞歸。我們在 Fortran 語言怎么來的這一節(jié)已經(jīng)提到，704 上的 Fortran 語言是不支持遞歸的。而 McCarthy 心中所設(shè)想的語言，很重要的一條就是遞歸：沒有遞歸，很多列表處理的函數(shù)只能用循環(huán)來實(shí)現(xiàn)，而循環(huán)本身并不是 McCarthy 設(shè)想的語言的一部分。熟悉函數(shù)求導(dǎo)的鏈?zhǔn)椒▌t的讀者可以想像，沒有遞歸的求導(dǎo)程序是何其難寫，因?yàn)楹瘮?shù)求導(dǎo)過程本身就是遞歸定義的。
第二個(gè)問題是 Fortran 的 IF 語句。IF 家族的分支語句，在計(jì)算機(jī)程序設(shè)計(jì)中可以說必不可少。在 McCarthy 那里 IF 就更重要了，因?yàn)閹缀跛杏羞f歸函數(shù)的地方就有 IF（因?yàn)檫f歸函數(shù)需要 IF 判斷結(jié)束條件）。相信讀者都很熟悉這種 IF 結(jié)構(gòu)
IF 條件 THEN一些語句; ELSE另一些語句; END IF這是從 ALGOL 語言一脈相承下來的，很“自然”的 IF 寫法。而早期的 FORTRAN 的 IF 寫法卻不這么直觀，而是
IF (表達(dá)式) A B C取決于表達(dá)式的值是小于零，等于零還是大于零，分別跳到（等價(jià)于 goto）標(biāo)簽 A， 標(biāo)簽B 或者標(biāo)簽 C。這個(gè) IF 隱含了三個(gè) Goto，可以說和結(jié)構(gòu)化編程的實(shí)踐截然相反，降低了程序的可讀性。 Fortran 首創(chuàng)的這個(gè)三分支跳轉(zhuǎn)的 IF 飽受詬病，Fortran 77 開始支持結(jié)構(gòu)化的 IF，而 Fortran 90 標(biāo)準(zhǔn)進(jìn)一步宣布三分支跳轉(zhuǎn)的用法已經(jīng)“過時(shí)”，不支持使用。
在 McCarthy 那里，Fortran 的三分支跳轉(zhuǎn) IF 也不方便。為此，在 FLPL 中，他試圖用一個(gè)叫 XIF 子程序完成類似于 IF 的分支功能，用法是：
XIF(條件, 表達(dá)式A, 表達(dá)式B)取決于條件的滿足與否，XIF 返回表達(dá)式 A 或者表達(dá)式 B 的值。很快，他發(fā)現(xiàn)，用子程序的方法實(shí)現(xiàn) XIF，在語義上并不正確。我們知道，在 Fortran 和其他高級語言中，函數(shù)參數(shù)的值在進(jìn)入函數(shù)之前必須全部確定。在 XIF 這里，不難看出，不管條件滿足與否，我們都先要計(jì)算表達(dá)式 A 和表達(dá)式 B 的值。而 IF 是個(gè)分支邏輯，從語義上來說，應(yīng)該只計(jì)算滿足條件的分支的值。因此，用函數(shù)來實(shí)現(xiàn) IF 是不正確的 [讀過 SICP 的讀者會發(fā)現(xiàn)這又是一道習(xí)題]。
作為一個(gè)旁注，盡管 John McCarthy 早在50多年前就發(fā)現(xiàn)了函數(shù)實(shí)現(xiàn) IF 是語義錯(cuò)誤的，現(xiàn)代的程序員還常常犯這個(gè)錯(cuò)誤。一個(gè)值得一提的例子是 C++ 邏輯運(yùn)算符重載和短路表達(dá)式的不等價(jià)性。我們都知道，在 C 語言中，邏輯與 (&&) 和邏輯或( || ) 都隸屬于短路表達(dá)式，也就是說，對于 A && B 這樣的表達(dá)式，如果 A 已經(jīng)確定為 false，就無需計(jì)算表達(dá)式 B 的值，即 B 的計(jì)算被”短路”。以 C 為藍(lán)本的 C++ 一方便保留了這些短路表達(dá)式，另一方面在面向?qū)ο蟮奶匦灾?#xff0c;引入了運(yùn)算符重載。具體來說，只要一個(gè)對象定義了 operator&& 成員函數(shù)，就可以進(jìn)行 && 運(yùn)算。乍一看，這是一個(gè)很酷的特性，可以讓程序員用 A&&B 這樣的數(shù)學(xué)表達(dá)式表達(dá)復(fù)雜的邏輯關(guān)系。然而，仔細(xì)想想， ?A.operator&&(B) 在語義上并不等價(jià)于 C 所定義的 A&&B，原因在于 A.operator&&() 是個(gè)函數(shù)，在求值之前需要先計(jì)算 B 的值，而后者是個(gè)短路表達(dá)式，本質(zhì)上相當(dāng)于
IF A:return True ELSE:return B因?yàn)槎搪繁磉_(dá)式不一定會對 B 求值，這兩者從語義上就是不等價(jià)的。如果 B 不是一個(gè)簡單的對象，而是一個(gè)復(fù)雜表達(dá)式的時(shí)候，對 B 求值可能有副作用，而這個(gè)副作用，是寫 A && B 并把它當(dāng)做短路表達(dá)式的程序員所沒有預(yù)見的。按照 C++ Gotcha 的說法，這很容易造成潛在的程序 Bug。實(shí)際上，C++邏輯運(yùn)算符重載是一個(gè)危險(xiǎn)的特性，很多公司的編程標(biāo)準(zhǔn)都禁止使用邏輯運(yùn)算符重載。
遞歸和 IF 兩個(gè)問題，使得 Fortran 從本質(zhì)上就不符合 McCarthy 期望，以 Fortran 為宿主的開發(fā)列表處理語言也不可能達(dá)到 McCarthy 想要的結(jié)果。因此，唯一的解，就是拋開 Fortran，從頭開始，設(shè)計(jì)一個(gè)新的語言。值得注意的是，此時(shí) McCarthy 正好跳槽到了 MIT 做助理教授，MIT 有足夠多的編程強(qiáng)人，可以幫 McCarthy 完成這個(gè)編寫新語言的任務(wù)。這個(gè)強(qiáng)人，就是?Steve Russell；這個(gè)語言，就是 Lisp。
總結(jié)
- 上一篇： dm365启动分析以及RBL、UBL、U
- 下一篇： 浏览器渲染流水线解析与网页动画性能优化