保羅格雷厄姆
約翰麥卡錫于1960年發(fā)表了一篇非凡的論文,他在這篇論文中對編程的貢獻有如歐幾里德對幾何的貢獻.1 他向我們展示了,在只給定幾個(gè)簡(jiǎn)單的操作符和一個(gè)表示函數的記號的基礎上, 如何構造出一個(gè)完整的編程語(yǔ)言. 麥卡錫稱(chēng)這種語(yǔ)言為L(cháng)isp, 意為L(cháng)ist Processing, 因為他的主要思想之一是用一種簡(jiǎn)單的數據結構表(list)來(lái)代表代碼和數據.
值得注意的是,麥卡錫所作的發(fā)現,不僅是計算機史上劃時(shí)代的大事, 而且是一種在我們這個(gè)時(shí)代編程越來(lái)越趨向的模式.我認為目前為止只有兩種真正干凈利落, 始終如一的編程模式:C語(yǔ)言模式和Lisp語(yǔ)言模式.此二者就象兩座高地, 在它們中間是尤如沼澤的低地.隨著(zhù)計算機變得越來(lái)越強大,新開(kāi)發(fā)的語(yǔ)言一直在堅定地趨向于Lisp模式. 二十年來(lái),開(kāi)發(fā)新編程語(yǔ)言的一個(gè)流行的秘決是,取C語(yǔ)言的計算模式,逐漸地往上加Lisp模式的特性,例如運行時(shí)類(lèi)型和無(wú)用單元收集.
在這篇文章中我盡可能用最簡(jiǎn)單的術(shù)語(yǔ)來(lái)解釋約翰麥卡錫所做的發(fā)現. 關(guān)鍵是我們不僅要學(xué)習某個(gè)人四十年前得出的有趣理論結果, 而且展示編程語(yǔ)言的發(fā)展方向. Lisp的不同尋常之處--也就是它優(yōu)質(zhì)的定義--是它能夠自己來(lái)編寫(xiě)自己. 為了理解約翰麥卡錫所表述的這個(gè)特點(diǎn),我們將追溯他的步伐,并將他的數學(xué)標記轉換成能夠運行的Common Lisp代碼.
開(kāi)始我們先定義表達式.表達式或是一個(gè)原子(atom),它是一個(gè)字母序列(如 foo),或是一個(gè)由零個(gè)或多個(gè)表達式組成的表(list), 表達式之間用空格分開(kāi), 放入一對括號中. 以下是一些表達式:
foo () (foo) (foo bar) (a b (c) d)最后一個(gè)表達式是由四個(gè)元素組成的表, 第三個(gè)元素本身是由一個(gè)元素組成的表.
在算術(shù)中表達式 1 + 1 得出值2. 正確的Lisp表達式也有值. 如果表達式e得出值v,我們說(shuō)e返回v. 下一步我們將定義幾種表達式以及它們的返回值.
如果一個(gè)表達式是表,我們稱(chēng)第一個(gè)元素為操作符,其余的元素為自變量.我們將定義七個(gè)原始(從公理的意義上說(shuō))操作符: quote,atom,eq,car,cdr,cons,和 cond.
> (quote a) a > ‘a(chǎn) a > (quote (a b c)) (a b c)
> (atom ‘a(chǎn)) t > (atom ‘(a b c)) () > (atom ‘()) t
既然有了一個(gè)自變量需要求值的操作符, 我們可以看一下quote的作用. 通過(guò)引用(quote)一個(gè)表,我們避免它被求值. 一個(gè)未被引用的表作為自變量傳給象 atom這樣的操作符將被視為代碼:
> (atom (atom ‘a(chǎn))) t
反之一個(gè)被引用的表僅被視為表, 在此例中就是有兩個(gè)元素的表:
> (atom ‘(atom ‘a(chǎn))) ()
這與我們在英語(yǔ)中使用引號的方式一致. Cambridge(劍橋)是一個(gè)位于麻薩諸塞州有90000人口的城鎮. 而``Cambridge‘‘是一個(gè)由9個(gè)字母組成的單詞.
引用看上去可能有點(diǎn)奇怪因為極少有其它語(yǔ)言有類(lèi)似的概念. 它和Lisp最與眾不同的特征緊密聯(lián)系:代碼和數據由相同的數據結構構成, 而我們用quote操作符來(lái)區分它們.
> (eq ‘a(chǎn) ‘a(chǎn)) t > (eq ‘a(chǎn) ‘b) () > (eq ‘() ‘()) t
> (car ‘(a b c)) a
> (cdr ‘(a b c)) (b c)
> (cons ‘a(chǎn) ‘(b c)) (a b c) > (cons ‘a(chǎn) (cons ‘b (cons ‘c ‘()))) (a b c) > (car (cons ‘a(chǎn) ‘(b c))) a > (cdr (cons ‘a(chǎn) ‘(b c))) (b c)
> (cond ((eq ‘a(chǎn) ‘b) ‘first)
((atom ‘a(chǎn)) ‘second))
second
當表達式以七個(gè)原始操作符中的五個(gè)開(kāi)頭時(shí),它的自變量總是要求值的.2 我們稱(chēng)這樣 的操作符為函數.
((lambda (...) e) ...)
則稱(chēng)為函數調用.它的值計算如下.每一個(gè)表達式
> ((lambda (x) (cons x ‘(b))) ‘a(chǎn)) (a b) > ((lambda (x y) (cons x (cdr y))) ‘z ‘(a b c)) (z b c)如果一個(gè)表達式的第一個(gè)元素f是原子且f不是原始操作符
(f ...)
并且f的值是一個(gè)函數(lambda (
((lambda (...) e) ...)
的值. 換句話(huà)說(shuō),參數在表達式中不但可以作為自變量也可以作為操作符使用:
> ((lambda (f) (f ‘(b c))) ‘(lambda (x) (cons ‘a(chǎn) x))) (a b c)
有另外一個(gè)函數記號使得函數能提及它本身,這樣我們就能方便地定義遞歸函數.3 記號
(label f (lambda (...) e))
表示一個(gè)象(lambda (
假設我們要定義函數(subst x y z), 它取表達式x,原子y和表z做參數,返回一個(gè)象z那樣的表, 不過(guò)z中出現的y(在任何嵌套層次上)被x代替.
> (subst ‘m ‘b ‘(a b (a b c) d)) (a m (a m c) d)我們可以這樣表示此函數
(label subst (lambda (x y z)
(cond ((atom z)
(cond ((eq z y) x)
(‘t z)))
(‘t (cons (subst x y (car z))
(subst x y (cdr z)))))))
我們簡(jiǎn)記f=(label f (lambda ((defun f (...) e)
于是
(defun subst (x y z)
(cond ((atom z)
(cond ((eq z y) x)
(‘t z)))
(‘t (cons (subst x y (car z))
(subst x y (cdr z))))))
偶然地我們在這兒看到如何寫(xiě)cond表達式的缺省子句. 第一個(gè)元素是‘t的子句總是會(huì )成功的. 于是
(cond (x y) (‘t z))
等同于我們在某些語(yǔ)言中寫(xiě)的
if x then y else z
> (cadr ‘((a b) (c d) e)) (c d) > (caddr ‘((a b) (c d) e)) e > (cdar ‘((a b) (c d) e)) (b)我們還用(list
> (cons ‘a(chǎn) (cons ‘b (cons ‘c ‘()))) (a b c) > (list ‘a(chǎn) ‘b ‘c) (a b c)
現在我們定義一些新函數. 我在函數名后面加了點(diǎn),以區別函數和定義它們的原始函數,也避免與現存的common Lisp的函數沖突.
(defun null. (x) (eq x ‘())) > (null. ‘a(chǎn)) () > (null. ‘()) t
(defun and. (x y)
(cond (x (cond (y ‘t) (‘t ‘())))
(‘t ‘())))
> (and. (atom ‘a(chǎn)) (eq ‘a(chǎn) ‘a(chǎn)))
t
> (and. (atom ‘a(chǎn)) (eq ‘a(chǎn) ‘b))
()
(defun not. (x)
(cond (x ‘())
(‘t ‘t)))
> (not. (eq ‘a(chǎn) ‘a(chǎn)))
()
> (not. (eq ‘a(chǎn) ‘b))
t
(defun append. (x y)
(cond ((null. x) y)
(‘t (cons (car x) (append. (cdr x) y)))))
> (append. ‘(a b) ‘(c d))
(a b c d)
> (append. ‘() ‘(c d))
(c d)
(defun pair. (x y)
(cond ((and. (null. x) (null. y)) ‘())
((and. (not. (atom x)) (not. (atom y)))
(cons (list (car x) (car y))
(pair. (cdr) (cdr y))))))
> (pair. ‘(x y z) ‘(a b c))
((x a) (y b) (z c))
(defun assoc. (x y)
(cond ((eq (caar y) x) (cadar y))
(‘t (assoc. x (cdr y)))))
> (assoc. ‘x ‘((x a) (y b)))
a
> (assoc. ‘x ‘((x new) (x a) (y b)))
new
(defun eval. (e a)
(cond
((atom e) (assoc. e a))
((atom (car e))
(cond
((eq (car e) ‘quote) (cadr e))
((eq (car e) ‘a(chǎn)tom) (atom (eval. (cadr e) a)))
((eq (car e) ‘eq) (eq (eval. (cadr e) a)
(eval. (caddr e) a)))
((eq (car e) ‘car) (car (eval. (cadr e) a)))
((eq (car e) ‘cdr) (cdr (eval. (cadr e) a)))
((eq (car e) ‘cons) (cons (eval. (cadr e) a)
(eval. (caddr e) a)))
((eq (car e) ‘cond) (evcon. (cdr e) a))
(‘t (eval. (cons (assoc. (car e) a)
(cdr e))
a))))
((eq (caar e) ‘label)
(eval. (cons (caddar e) (cdr e))
(cons (list (cadar e) (car e)) a)))
((eq (caar e) ‘lambda)
(eval. (caddar e)
(append. (pair. (cadar e) (evlis. (cdr e) a))
a)))))
(defun evcon. (c a)
(cond ((eval. (caar c) a)
(eval. (cadar c) a))
(‘t (evcon. (cdr c) a))))
(defun evlis. (m a)
(cond ((null. m) ‘())
(‘t (cons (eval. (car m) a)
(evlis. (cdr m) a)))))
eval.的定義比我們以前看到的都要長(cháng). 讓我們考慮它的每一部分是如何工作的.
eval.有兩個(gè)自變量: e是要求值的表達式, a是由一些賦給原子的值構成的表,這些值有點(diǎn)象函數調用中的參數. 這個(gè)形如pair.的返回值的表叫做環(huán)境. 正是為了構造和搜索這種表我們才寫(xiě)了pair.和assoc..
eval.的骨架是一個(gè)有四個(gè)子句的cond表達式. 如何對表達式求值取決于它的類(lèi)型. 第一個(gè)子句處理原子. 如果e是原子, 我們在環(huán)境中尋找它的值:
> (eval. ‘x ‘((x a) (y b))) a
第二個(gè)子句是另一個(gè)cond, 它處理形如(a ...)的表達式, 其中a是原子. 這包括所有的原始操作符, 每個(gè)對應一條子句.
> (eval. ‘(eq ‘a(chǎn) ‘a(chǎn)) ‘())
t
> (eval. ‘(cons x ‘(b c))
‘((x a) (y b)))
(a b c)
這幾個(gè)子句(除了quote)都調用eval.來(lái)尋找自變量的值.
最后兩個(gè)子句更復雜些. 為了求cond表達式的值我們調用了一個(gè)叫 evcon.的輔助函數. 它遞歸地對cond子句進(jìn)行求值,尋找第一個(gè)元素返回t的子句. 如果找到了這樣的子句, 它返回此子句的第二個(gè)元素.
> (eval. ‘(cond ((atom x) ‘a(chǎn)tom)
(‘t ‘list))
‘((x ‘(a b))))
list
第二個(gè)子句的最后部分處理函數調用. 它把原子替換為它的值(應該是lambda 或label表達式)然后對所得結果表達式求值. 于是
(eval. ‘(f ‘(b c))
‘((f (lambda (x) (cons ‘a(chǎn) x)))))
變?yōu)?(eval. ‘((lambda (x) (cons ‘a(chǎn) x)) ‘(b c))
‘((f (lambda (x) (cons ‘a(chǎn) x)))))
它返回(a b c).
eval.的最后cond兩個(gè)子句處理第一個(gè)元素是lambda或label的函數調用.為了對label 表達式求值, 先把函數名和函數本身壓入環(huán)境, 然后調用eval.對一個(gè)內部有 lambda的表達式求值. 即:
(eval. ‘((label firstatom (lambda (x)
(cond ((atom x) x)
(‘t (firstatom (car x))))))
y)
‘((y ((a b) (c d)))))
變?yōu)?(eval. ‘((lambda (x)
(cond ((atom x) x)
(‘t (firstatom (car x)))))
y)
‘((firstatom
(label firstatom (lambda (x)
(cond ((atom x) x)
(‘t (firstatom (car x)))))))
(y ((a b) (c d)))))
最終返回a.
最后,對形如((lambda (
(eval. ‘((lambda (x y) (cons x (cdr y)))
‘a(chǎn)
‘(b c d))
‘())
變?yōu)?(eval. ‘(cons x (cdr y))
‘((x a) (y (b c d))))
最終返回(a c d).
既然理解了eval是如何工作的, 讓我們回過(guò)頭考慮一下這意味著(zhù)什么. 我們在這兒得到了一個(gè)非常優(yōu)美的計算模型. 僅用quote,atom,eq,car,cdr,cons,和cond, 我們定義了函數eval.,它事實(shí)上實(shí)現了我們的語(yǔ)言,用它可以定義任何我們想要的額外的函數.
當然早已有了各種計算模型--最著(zhù)名的是圖靈機. 但是圖靈機程序難以讀懂. 如果你要一種描述算法的語(yǔ)言, 你可能需要更抽象的, 而這就是約翰麥卡錫定義 Lisp的目標之一.
約翰麥卡錫于1960年定義的語(yǔ)言還缺不少東西. 它沒(méi)有副作用, 沒(méi)有連續執行 (它得和副作用在一起才有用), 沒(méi)有實(shí)際可用的數,4 沒(méi)有動(dòng)態(tài)可視域. 但這些限制可以令人驚訝地用極少的額外代碼來(lái)補救. Steele和Sussman在一篇叫做``解釋器的藝術(shù)‘‘的著(zhù)名論文中描述了如何做到這點(diǎn).5
如果你理解了約翰麥卡錫的eval, 那你就不僅僅是理解了程序語(yǔ)言歷史中的一個(gè)階段. 這些思想至今仍是Lisp的語(yǔ)義核心. 所以從某種意義上, 學(xué)習約翰麥卡錫的原著(zhù)向我們展示了Lisp究竟是什么. 與其說(shuō)Lisp是麥卡錫的設計,不如說(shuō)是他的發(fā)現. 它不是生來(lái)就是一門(mén)用于人工智能, 快速原型開(kāi)發(fā)或同等層次任務(wù)的語(yǔ)言. 它是你試圖公理化計算的結果(之一).
隨著(zhù)時(shí)間的推移, 中級語(yǔ)言, 即被中間層程序員使用的語(yǔ)言, 正一致地向Lisp靠近. 因此通過(guò)理解eval你正在明白將來(lái)的主流計算模式會(huì )是什么樣.
在約翰麥卡錫的論文中,假用f來(lái)表示, 而不是空表. 我用空表表示假以使例子能在Common Lisp中運行. (fixme)
我略過(guò)了構造dotted pairs, 因為你不需要它來(lái)理解eval. 我也沒(méi)有提apply, 雖然是apply(它的早期形式, 主要作用是引用自變量), 被約翰麥卡錫在1960年稱(chēng)為普遍函數, eval只是不過(guò)是被apply調用的子程序來(lái)完成所有的工作.
我定義了list和cxr等作為簡(jiǎn)記法因為麥卡錫就是這么做的. 實(shí)際上 cxr等可以被定義為普通的函數. List也可以這樣, 如果我們修改eval, 這很容易做到, 讓函數可以接受任意數目的自變量.
麥卡錫的論文中只有五個(gè)原始操作符. 他使用了cond和quote,但可能把它們作為他的元語(yǔ)言的一部分. 同樣他也沒(méi)有定義邏輯操作符and和not, 這不是個(gè)問(wèn)題, 因為它們可以被定義成合適的函數.
在eval.的定義中我們調用了其它函數如pair.和assoc.,但任何我們用原始操作符定義的函數調用都可以用eval.來(lái)代替. 即
(assoc. (car e) a)能寫(xiě)成
(eval. ‘((label assoc.
(lambda (x y)
(cond ((eq (caar y) x) (cadar y))
(‘t (assoc. x (cdr y))))))
(car e)
a)
(cons (list ‘e e) (cons (list ‘a(chǎn) a) a)))
麥卡錫的eval有一個(gè)錯誤. 第16行是(相當于)(evlis. (cdr e) a)而不是(cdr e), 這使得自變量在一個(gè)有名函數的調用中被求值兩次. 這顯示當論文發(fā)表的時(shí)候, eval的這種描述還沒(méi)有用IBM 704機器語(yǔ)言實(shí)現. 它還證明了如果不去運行程序, 要保證不管多短的程序的正確性是多么困難.
我還在麥卡錫的論文中碰到一個(gè)問(wèn)題. 在定義了eval之后, 他繼續給出了一些更高級的函數--接受其它函數作為自變量的函數. 他定義了maplist:
(label maplist
(lambda (x f)
(cond ((null x) ‘())
(‘t (cons (f x) (maplist (cdr x) f))))))
然后用它寫(xiě)了一個(gè)做微分的簡(jiǎn)單函數diff. 但是diff傳給maplist一個(gè)用x做參數的函數, 對它的引用被maplist中的參數x所捕獲.6
這是關(guān)于動(dòng)態(tài)可視域危險性的雄辯證據, 即使是最早的更高級函數的例子也因為它而出錯. 可能麥卡錫在1960年還沒(méi)有充分意識到動(dòng)態(tài)可視域的含意. 動(dòng)態(tài)可視域令人驚異地在Lisp實(shí)現中存在了相當長(cháng)的時(shí)間--直到Sussman和Steele于 1975年開(kāi)發(fā)了Scheme. 詞法可視域沒(méi)使eval的定義復雜多少, 卻使編譯器更難寫(xiě)了.
This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)
Copyright ? 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright ? 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split=0 roots_of_lisp.tex
The translation was initiated by Dai Yuwen on 2003-10-24
聯(lián)系客服
