不走尋常路的常識邏輯學家 - Lisp之父約翰·麥卡錫

如果希望計算機具有一般的智能，那么其外在結構就必須基于一般的常識和推理——約翰·麥卡錫

        一個 5 歲的小女孩在玩一輛塑料玩具卡車，把它推來推去，嘴里模仿著喇叭聲。她知道不能在餐桌上玩它，也不能用它去打弟弟的頭。去學校之前，她會把卡車放到弟弟夠不著的地方。放學回家后，她也知道在原來的地方可以找到自己的玩具車。

        引導她的行為和期望的推理非常簡單，任何一個同齡的小孩都能理解。但是大多數計算機卻不能。計算機的問題一部分在于它缺少一般 5 歲小孩能從父母那里學到的日常社會知識，例如不能損壞家具，不能傷到自己的弟弟；另一部分在于計算機沒有我們的日常推理能力。人類使用的是一種基于經驗的 常識推測體系，它與常規邏輯不同，因此也與一般計算機程序員的思維不同。常規邏輯使用的是一種被稱為“演繹”（deduction）的推理形式。演繹讓我 們能從“所有失業演員都當了服務生”和“托米是個失業演員”這兩個陳述中推斷出“托米是個服務生”這一新的陳述。其優點在于它的可靠性——如果前提成立， 那么結論一定成立。同時演繹推理也是 “單調的”（monotonic，數學術語，其基本含義為“不變的”）。如果你發現了新的事實，但并不與前提相矛 盾，那么結論仍然成立。

        然而，盡管我們大多數人都在學校學過演繹推理，卻很少在實際生活中用到。5歲的小女孩相信自己的卡車還在原來的位置，是因為她把它放在了弟弟夠 不著的地方。但如果某天她在出門時看到弟弟學會了爬凳子，可能就不會這么有把握了。5歲小孩掌握的常識推理主要依靠基于經驗的推測，而這可能會由于新事實 的出現而不得不作出非單調的修改。而且并不是只有 5 歲小孩會如此。

        就算是公認的演繹推理大師歇洛克·福爾摩斯，也并不經常用到演繹推理。在關于一匹受傷賽馬的冒險故事《銀色馬》中，福爾摩斯運用其天賦的洞察力 得出結論，看門狗沒有叫是因為它認識罪犯。我們的偵探確實才智超群，而且推論看來合情合理，最后在故事中也證明是正確的，但他用的卻不是演繹推理——狗可 能是被麻醉了、戴了口套，或者當時正在野地里追兔子。

        程序員知道如何讓計算機進行演繹推理，因為計算機能夠理解其中涉及的數學。但如果想讓計算機進行人類賴以生存的這種推測性的（而又常常是正確的）常識推理，就得發明一種全新的數理邏輯。而這正是約翰·麥卡錫為自己設立的目標之一。

        麥卡錫的成名還有其他原因。他發明了人工智能領域的首要語言 Lisp（list processing，表處理），而且自其誕生之日起，就為編程語言設計提供了豐饒的思想源泉。同時，作為一名教師和難題設計師，他 在密碼學和平面性檢驗等亞學科領域激發了眾多計算機科學家的靈感。我們將在拉賓和陶爾揚的章節中再行描述。

        約翰·麥卡錫 1927 年出生于波士頓一個共產黨積極分子家庭，童年在四處奔波中度過。他的父親是一名愛爾蘭天主教徒，先后做過木匠、漁民和工會組織者，全家一直馬不停蹄地奔 波，從波士頓搬到紐約，然后又搬到洛杉磯。他的母親是立陶宛猶太人，最初在聯邦通訊社當新聞記者，后來就職于一家共產主義報刊，最后成為了一名社會工作 者。麥卡錫早年對科學的興趣與家庭的政治信仰密不可分。

        當時普遍相信技術對人類必將有利無害。我記得還是小孩的時候，曾讀過一本書叫做《十萬個為什么》，是前蘇聯作家米·伊林在 20 世紀 30 年代早期寫的一套通俗科普書。在美國好像沒有這樣的書。有趣的是，十幾年前我在報上看到過報道一個特別早熟的中國孩子，而他也讀過《十萬個為什么》。

        麥卡錫認為自己的青少年時期平淡無奇，但事實證明并非如此。在上高三時，他得到了一份加州理工學院的課程目錄，上面列出了該校一年級和二年級的微積分課本。他買了這些書，完成了所有的練習題目。這使得他最終在 1944 年進入加州理工后得以免修頭兩年的數學課程。

        1948年，麥卡錫開始攻讀數學系的碩士學位。同年 9 月他參加了加州理工主辦的希克森腦行為機制研討會，大數學家、計算機設計大師約翰·馮·諾依曼在會上演講了一篇關于自復制自動機（self- replicating automata）的論文，這是一種可以對自身進行復制的機器。盡管當時的與會人員并沒有明確地將機器智能與人類智能聯系起來， 但馮·諾依曼的講話卻激發了麥卡錫的好奇心。

        1949年在普林斯頓大學數學系作博士論文時，麥卡錫首次開始嘗試在機器上模擬人類智能。

        我把有智能的東西看做是一個有限自動機，與同樣是有限自動機的環境相連。我和約翰·馮·諾依曼見了面，他對此非常贊成，敦促我一定要把這篇論文寫出來。但最后我并沒有寫出來，因為我認為它還不夠成熟。

        “自動機”模擬的是隨著時間從一個狀態轉入另一個狀態的機器。比如說，普通的手動變速箱汽車在駕駛員點火啟動之后會從“熄火”狀態轉入“空擋但 啟動”狀態。如果駕駛員掛擋前進則轉入“啟動且掛一擋”狀態。而“交互式自動機”（interacting automaton）則是根據其自身的狀態以 及它所觀察到的其他自動機的狀態決定從某個狀態轉入另一狀態。有些自動機是智能的（可看做是自帶駕駛員），但并不是必須智能。交互式自動機試圖在這兩種類 型之間建立一種連續性的統一體。

        麥卡錫放棄了自己對利用自動機模擬人類智能的首次嘗試。但在十幾年之后，當他從事情境演算（situational calculus）方面的工作時，關于狀態和狀態轉換的思想將重新浮出水面。

        在這段時間中，麥卡錫始終沒有放棄制造一臺像人類那樣智能的機器這一想法。1952年夏，普林斯頓大學的一個研究生杰里·雷納 （Jerry Rayna）向麥卡錫建議，可以找一些對機器智能感興趣的人去收集一些該領域的文章。麥卡錫找的第一批人就有克勞德·香農，“信息論”亦即 通信數學理論的發明者。香農的理論最初用于遠程通信，后被廣泛用于語言學、數學以及計算機科學等領域。

        香農不喜歡華而不實的術語堆砌。他整理的卷宗為《自動機研究》（Automata Studies）。而其中收集到的文章讓我很失望，里面有關 智能的內容并不多。所以在 1955 年開始籌備達特茅斯計劃時，我希望開門見山，使用了“人工智能”這一術語，目的是讓參與者們弄清楚我們是在干什么。

        1956年在達特茅斯學院舉辦的夏季人工智能研討會是計算機科學史上的一座里程碑。這項涉及 10 人、耗時 2 個月的雄心勃勃的研究計劃，其目標是“基于‘我們能夠精確、全面地描述人類智能中的學習等特征，并制造出機器模擬之’這一構想，繼續闊步前進”（引自其提 案）。

        研討會的四位組織者——麥卡錫、馬文·明斯基（當時還在哈佛大學）、納撒尼爾·羅切斯特（IBM 的杰出計算機設計師）和香農——向洛克菲勒基金會申請了一筆資金支持，金額在今天看來幾乎少得可憐：主要組織者每人 1200 美元，再加上“外地與會人員的火車票”，總共 7500 美元。

        麥卡錫在提案中寫到，他將研究語言和智能二者間的關系，希望通過程序使計算機能“進行棋類游戲并完成其他任務”。時隔 40 年后回憶起這次研討會時，麥卡錫以他特有的直率形容了自己當時的愿景和期望。

        我為這次會議設定的目標完全不切實際，以為經過一個夏天的討論就能搞定整個項目。我之前從未參與過這種模式的會議，只是略有耳聞。實際上，它和 那種以研究國防為名義的軍事夏令營沒什么區別。創造一臺真正智能的機器是一個極為困難的過程。盡管這次會議在實質上并未解決任何具體問題，但它確立了一些 目標和技術方法，使人工智能獲得了計算機科學界的承認，成為一個獨立的而且最終充滿著活力的新興科研領域。雖然大多數與會者在會后并未繼續從事該領域的研 究，但另外那少數人中卻產生了一批在該領域影響深遠的成就。

        來自卡內基梅隆大學的艾倫·紐厄爾、赫伯特·西蒙和J. C.肖（J. C. Shaw）描述了他們的第二代信息處理語言 （Information Processing Language，IPL 2）。這三位科學家致力于構建一種名為“邏輯理論機”的程序，用于驗證基本 邏輯和博弈論中的定理。而為了做到這一點，他們設計出 IPL 2這種程序語言以便于操作對象符號，例如象棋的棋子或者邏輯變量里的真值。由于這種操作與針對數字的算術運算非常不同，他們提議使用一種所謂的 “表結構”。

        讓我們冒昧地借用《愛麗絲夢游仙境》來說明如何利用表來進行符號處理。假設柴郡貓告訴愛麗絲“不是我瘋了，就是帽匠瘋了”。我們用C、H、A代 表三種觀點，分別是柴郡貓瘋了、帽匠瘋了和愛麗絲瘋了。貓之前的那句聲明可以用表的形式表示為(or C H)。然后貓又告訴愛麗絲“不是你瘋了，就是帽 匠瘋了”。聰明的愛麗絲會把這個聲明和之前的那個一起表示為(and (or C H) (or A H))。最后貓又說“我們三個中只有一個瘋了”。也 就是說，至少有兩個沒有瘋。愛麗絲可以將其表示為 (and (or C H) (or A H) (or (and (not A) (not C)) (and (not A) (not H)) (and (not C) (not H))))。

        把這些聲明表示成表的形式之后，我們就可以定義一些表操作的規則。

        例如(and (or X Y) (or Z Y)) = (or (and X Z) Y)。也就是說，如果不是X成立就是Y成立，而且不是 Z成立就是Y成立，那么不是X和Z都成立，就是Y成立。應用這樣一些規則，我們就能得出結論(and H (not C) (not A))。那么，根據 柴郡貓的說法，只有帽匠瘋了。

        通過表來進行邏輯推理的優點在于，在推理的過程中表可以擴展、收縮和重組。此外，我們可以用同一種形式表示規則和數據。在研討會大多數與會者們 看來，表操作無疑是這次的贏家。達特茅斯會議的另一項成就是馬文·明斯基關于構建幾何定理證明機的提案。明斯基在紙上試驗了幾個例子，認為證明幾何定理可 能是對紐厄爾和西蒙提出的基于規則的方法的一種很好的應用。IBM 公司的赫伯特·格林特（Herbert Gelernter）和納撒尼爾·羅切斯特決定去實現這個程序。格林特日后又開發了一種幫助有機化學家合成新化合 物的工具，他的兒子大衛·格林特（David Gelernter）是并行程序設計和醫學人工智能領域著名的研究者及設計者。麥卡錫身為這個定理證明項目 的顧問，有機會為智能行為編寫程序。

        格林特和他的助手卡爾·格貝里希（Carl Gerberich）采納了我的建議，以 Fortran 為藍本設計了 FLPL——Fortran 表處理語言（Fortran List Processing Language）。其中也加入了一些他們自己的想法。

        1956年，約翰·巴科斯和他在 IBM 的團隊發布了首個高級編程語言 Fortran，將從事數字運算的程序員從為每一臺計算機寫匯編語言中解放出來。直到今天，Fortran 仍然是科學和工程計算中的通用語言。FLPL 首次嘗試了擴展 Fortran 的符號操作能力。1958年夏天在 IBM 工作時，麥卡錫試圖用 FLPL 為自己在高中時常用的代數微分應用寫一個表程序，但很快發現需要用到遞歸條件表達式，而 Fortran 卻不支持遞歸。如果 Fortran 支持遞歸，我就能用 FLPL 做下去。我甚至也考慮了如何往 Fortran 中加入遞歸的問題，但是那樣做過于復雜。

        事實證明，IBM 很快就失去了對人工智能的興趣。一些客戶認為智能機器可能會威脅到他們的工作崗位，因此 20 世紀 60 年代初期的 IBM 市場營銷都把計算機說成是非智能的快速運算設備，百依百順、只按要求行事。

        麥卡錫不再糾纏于修補 Fortran，而是轉頭發明了 Lisp。紐厄爾、肖和西蒙后來把 IPL 形容為一種越變越復雜的語言，而麥卡錫則把他的 Lisp 形容為一種越變越簡單的語言。

        “Lisp”是“list processing language”（表處理語言）的縮寫。確如其名，Lisp 中所有的數據都用表來表示。這些表都被包含在圓括號中。比如說，（Robert taught Dennis）可能就是表示“羅伯特教丹尼斯”這個句子的 一個表。在這種情況下，順序是很重要的，因為它指明了是誰在教誰。

        而（apple tomato milk）則可能表示一個購物清單。在這種情況下，順序就不重要了，因為這三種商品可以按任意順序購買。上述這 兩個例子中，表都包含了“原子”（atom）作為元素。原子和表不同，是 Lisp 中最小的符號單位，不包含其他任何組成部分。而表還能夠包含（而且一般都會包含）其他表作為組成部分。比如說， （Robert taught（Carol and Dennis））反映了句子的語法結構，其中的圓括號指明卡羅爾和丹尼斯都是動詞“教”的對象。再比 如，（times 6（plus x y））表示6 ×（x + y）。這里的順序也很重要，而且圓括號表明x和y是一起的。

        通過這種方式，表不僅能夠表示構成科學和工程的標準數學結構，還能表示構成語言的語句結構。

        從一開始，麥卡錫就擁有一個熱情高漲的合作者團隊。

        當我在 1958 年秋天回到麻省理工的時候，我和明斯基有了一個大工作室、一臺鍵控打孔機，此外還配備了一名秘書、兩個程序員和六個數學專業的研究生。我們是在春天時向杰里·威斯納（Jerry Wiesner）申請的這些，理由是為我們的人工智能項目做準備。

        我們連書面提案都沒準備，申請就得到了批準。很幸運，當時麻省理工的電子研究實驗室剛剛與美國軍方簽署了一份無固定目標的雙向合作協議，而相應 的資源還沒有到位。我想這種靈活的資源調配正是美國的人工智能研究起步領先于其他國家的原因之一。紐厄爾-西蒙的研究之所以能進行，也是由于美國空軍在當 時向蘭德公司提供了彈性的支持。

        隨著工作的深入，麥卡錫希望改進這種語言的表達能力。1959年，為了展示 Lisp 可以明確地表達任何可計算函數，他加入了一個叫做“求值”（eval）的功能。“求值”允許程序定義新的函數或者過程（procedure），然后將其作 為程序的一部分執行。而大多數語言在執行新函數之前都會強制程序中止運行，并且“重新編譯”。由于求值函數可以帶動并執行任何函數，它扮演了一種“通用圖 靈機”的角色，是其他計算機的通用模擬器。

        求值概念具有非常實際的意義。比如說，由于國際金融市場時刻都在變化，股票交易所必須每周 7 天、每天 24 小時不停地提供計算服務。如果有人寫了一個程序，可以用新的方法分析路透社的股票數據，股票經紀人很可能希望馬上就使用它，但又絕不想中斷自己機器的使 用。求值讓這一切成為可能。

        Lisp 中蘊含的思想吸引了負責設計 Algol 語言（巴科斯和諾爾為其發明了巴科斯-諾爾范式）的國際委員會。1960年，在該委員會于巴黎召開的會議上，麥卡錫正式提出了遞歸和條件表達式這兩個概 念。在標記方法上，委員會有了些爭論，但最終仍然接受了他的思想。

        Algol 是第一個采用 Lisp 創新的語言，但絕對不是最后一個。Algol 的后繼語言如 Pascal、C、Ada 以及其他大多數現代編程語言都支持遞歸和條件表達式。但直到最近，主流語言都不支持求值，主要原因在于語言設計者們擔心程序員往運行中的程序里添加新功能 可能會很危險。不過如今的很多程序都必須每周 7 天、每天 24 小時地連續運行，人們對求值這種特性的需求越來越迫切，因此大多數實驗性語言都包含了求值或類似求值的功能。

        近 50 年來，Lisp 一直是人工智能領域的標準語言。麥卡錫并未預料到它會有如此長的壽命，甚至曾建議將其修改成類似 Algol 那樣。然而該領域的編程人員仍然喜歡 Lisp 最初的語法。麥卡錫和在他之前的巴科斯、之后的艾倫·C. 凱一樣，最終已無法控制自己發明的語言的發展方向。

        本文節選自《奇思妙想：15位計算機天才及其重大發現》，薩莎 (Shasha,D.E.) ， (美) 拉瑟 (Lazere,C.A.) 著,向怡寧譯，由人民郵電出版社發行。

來自: www.programmer.com.cn