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