【整理】LISP简介
LISP的歷史
LISP（全名LIST Processor，即鏈表處理語言），由約翰·麥卡錫在1960年左右創造的一種基于λ演算的函數式編程語言。
Lisp 代表 LISt Processing，即表處理，這種編程語言用來處理由括號（即“(”和“)”）構成的列表。約翰麥卡錫于1960年發表了一篇非凡的論文,他在這篇論文中對編程的貢獻有如歐幾里德對幾何的貢獻.[1] 他向我們展示了,在只給定幾個簡單的操作符和一個表示函數的記號的基礎上, 如何構造出一個完整的編程語言. 麥卡錫稱這種語言為Lisp, 意為List Processing, 因為他的主要思想之一是用一種簡單的數據結構表(list)來代表代碼和數據.
值得注意的是,麥卡錫所作的發現,不僅是計算機史上劃時代的大事, 而且是一種在我們這個時代編程越來越趨向的模式。可以說到目前為止只有兩種真正干凈利落, 始終如一的編程模式:C語言模式和Lisp語言模式。此二者就象兩座高地, 在它們中間是尤如沼澤的低地.隨著計算機變得越來越強大,新開發的語言一直在堅定地趨向于Lisp模式。二十年來,開發新編程語言的一個流行的秘訣是,取C語言的計算模式,逐漸地往上加Lisp模式的特性,例如運行時類型和無用單元收集。
LISP有很多種方言，各個實現中的語言不完全一樣。1980年代Guy L. Steele編寫了Common Lisp試圖進行標準化，這個標準被大多數解釋器和編譯器所接受。在Unix/Linux系統中，還有一種和Emacs一起的Emacs Lisp（而Emacs正是用Lisp編寫的）非常流行，并建立了自己的標準。
LISP的祖先是1950年代Carnegie-Mellon大學的Newell、Shaw、Simon開發的IPL語言。
LISP語言的主要現代版本包括Common Lisp和Scheme。
?
LISP有9大創新
直到現在，越流行語言吸收的LISP元素越多，如python,ruby。LISP直到現在仍然被眾多牛人推崇。當年LISP有9大創新，50年后，深刻影響了編程語言的進程。可見一個完善的理論被適當地應用，可以變得多么強大，煥發多么奪目的生機：
1. 條件語句。當初的語言是沒有if else的，goto統治世界。
2. 函數類型。函數成了語言里的類型，可以被變量指代，可以被當成參數傳來傳去（的一類公民的必要條件，參考SICP第一章）。這一條可以極大簡化編程，讓我們寫出非常漂亮的程序。所以現在的流行語言紛紛加入了這個特性（可惜Java沒有)。
3. 遞歸。這個不用說了吧。
4. 動態類型。smalltalk, python, ruby。。。連C#也有一個類似的var了。
5. 垃圾收集。不要以為GC是Smalltalk的發明哈，更不是Java的。
6. 基于表達式的編程。任何表達式都可以成為另一個表達式的一部分。不像很多語言，把表達和陳述分開。
7. 符號類型。這個在python和ruby里被采用，廣受歡迎。
8. 代碼即解析樹。這個讓LISP能方便地定義新的句法，操作程序本身，編寫元程序，生成真正意義上的宏。
9. 語言無時不在。代碼運行/解析可以在任何時候發生。這點和8.配合可以讓語言的擴展和交流變得非常容易。
?
基本介紹
Lisp的表達式是一個原子(atom)或表(list)，原子(atom)是一個字母序列，如abc；表是由零個或多個表達式組成的序列，表達式之間用空格分隔開，放入一對括號中，如：
abc
()
(abc xyz)
(a b (c) d)
最后一個表是由四個元素構成的，其中第三個元素本身也是一個表。
正如算數表達式1+1有值2一樣，Lisp中的表達式也有值，如果表達式e得出值v，我們說e返回v。如果一個表達式是一個表，那么我們把表中的第一個元素叫做操作符，其余的元素叫做自變量。
下面是一個在標準輸出設備上輸出Hello World的簡單Common Lisp程序，這種程序通常作為開始學習編程語言時的第一個程序：(format t "Hello, world!~%")
Lisp的7個公理（基本操作符）：quote,atom,eq,car,cdr,cons,和 cond.
?
- (quote x)返回x，我們簡記為'x
- (atom x)當x是一個原子或者空表時返回原子t，否則返回空表()。在Lisp中我們習慣用原子t表示真，而用空表()表示假。
> (atom 'a)
t
> (atom '(a b c))
()
> (atom '())
t
現在我們有了第一個需要求出自變量值的操作符，讓我們來看看quote操作符的作用——通過引用(quote)一個表，我們避免它被求值。一個未被引用的表達式作為自變量，atom將其視為代碼，例如：
> (atom (atom 'a))
t
反之一個被引用的表僅僅被視為表
> (atom '(atom 'a))
()
引用看上去有些奇怪，因為你很難在其它語言中找到類似的概念，但正是這一特征構成了Lisp最為與眾不同的特點——代碼和數據使用相同的結構來表示，而我們用quote來區分它們。
- (eq x y)當x和y的值相同或者同為空表時返回t，否則返回空表()
t
> (eq 'a 'b)
()
> (eq '() '())
t
- (car x)要求x是一個表，它返回x中的第一個元素，例如：
a
- (cdr x)同樣要求x是一個表，它返回x中除第一個元素之外的所有元素組成的表，例如：
(b c)
- (cons x y)要求y是一個表，它返回一個表，這個表的第一個元素是x，其后是y中的所有元素，例如：
(a b c)
> (cons 'a (cons 'b (cons 'c ())))
(a b c)
- (cond (...) ...(...)) 的求值規則如下. p表達式依次求值直到有一個返回t. 如果能找到這樣的p表達式,相應的e表達式的值作為整個cond表達式的返回值.
((atom 'a) 'second))
second
函數的表示
當表達式以七個原始操作符中的五個開頭時,它的自變量總是要求值的。 我們稱這樣的操作符為函數。接著我們定義一個記號來描述函數。函數表示為(lambda (...) e),其中 ...是原子(叫做參數),e是表達式。如果表達式的第一個元素形式如上
((lambda (...) e) ...) 則稱為函數調用。它的值計算如下，每一個表達式先求值，然后e再求值。在e的求值過程中,每個出現在e中的的值是相應的在最近一次的函數調用中的值。
> ((lambda (x) (cons x '(b))) 'a)
(a b)
> ((lambda (x y) (cons x (cdr y)))
'z
'(a b c))
(z b c)
如果一個表達式的第一個元素f是原子且f不是原始操作符 (f ...) 并且f的值是一個函數(lambda (...))，則以上表達式的值就是 ((lambda (...) e) ...) 的值。換句話說，參數在表達式中不但可以作為自變量也可以作為操作符使用:
> ((lambda (f) (f '(b c)))
'(lambda (x) (cons 'a x)))
(a b c)
有另外一個函數記號使得函數能提及它本身,這樣我們就能方便地定義遞歸函數。記號 (label f (lambda (...) e)) 表示一個象(lambda (...) e)那樣的函數，加上這樣的特性: 任何出現在e中的f將求值為此label表達式， 就好象f是此函數的參數。
假設我們要定義函數(subst x y z)，它取表達式x，原子y和表z做參數,返回一個象z那樣的表，不過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)))))))
我們簡記f=(label f (lambda (...) e))為
(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))))))
偶然地我們在這兒看到如何寫cond表達式的缺省子句. 第一個元素是't的子句總是會成功的. 于是
(cond (x y) ('t z))
等同于我們在某些語言中寫的
if x then y else z
一些函數
既然我們有了表示函數的方法,我們根據七個原始操作符來定義一些新的函數. 為了方便我們引進一些常見模式的簡記法. 我們用cxr,其中x是a或d的序列,來簡記相應的car和cdr的組合. 比如(cadr e)是(car (cdr e))的簡記,它返回e的第二個元素.
> (cadr '((a b) (c d) e))
(c d)
> (caddr '((a b) (c d) e))
e
> (cdar '((a b) (c d) e))
(b)
我們還用(list ...)表示(cons ...(cons '()) ...).
> (cons 'a (cons 'b (cons 'c '())))
(a b c)
> (list 'a 'b 'c)
(a b c)
現在我們定義一些新函數. 我在函數名后面加了點,以區別函數和定義它們的原始函數,也避免與現存的common Lisp的函數沖突.
(null. x)測試它的自變量是否是空表.
(defun null. (x)
(eq x '()))
> (null. 'a)
()
> (null. '())
t
(and. x y)返回t如果它的兩個自變量都是t, 否則返回().
(defun and. (x y)
(cond (x (cond (y 't) ('t '())))
('t '())))
> (and. (atom 'a) (eq 'a 'a))
t
> (and. (atom 'a) (eq 'a 'b))
()
(not. x)返回t如果它的自變量返回(),返回()如果它的自變量返回t.
(defun not. (x)
(cond (x '())
('t 't)))
> (not. (eq 'a 'a))
()
> (not. (eq 'a 'b))
t
(append. x y)取兩個表并返回它們的連結.
(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)
(pair. x y)取兩個相同長度的表,返回一個由雙元素表構成的表,雙元素表是相應位置的x,y的元素對.
(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))
(assoc. x y)取原子x和形如pair.函數所返回的表y,返回y中第一個符合如下條件的表的第二個元素:它的第一個元素是x.
(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
一個驚喜
因此我們能夠定義函數來連接表,替換表達式等等.也許算是一個優美的表示法, 那下一步呢? 現在驚喜來了. 我們可以寫一個函數作為我們語言的解釋器:此函數取任意Lisp表達式作自變量并返回它的值. 如下所示:
(defun eval. (e a)
(cond
((atom e) (assoc. e a))
((atom (car e))
(cond
((eq (car e) 'quote) (cadr e))
((eq (car e) 'atom) (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.的定義比我們以前看到的都要長. 讓我們考慮它的每一部分是如何工作的.
eval.有兩個自變量: e是要求值的表達式, a是由一些賦給原子的值構成的表,這些值有點象函數調用中的參數. 這個形如pair.的返回值的表叫做環境. 正是為了構造和搜索這種表我們才寫了pair.和assoc..
eval.的骨架是一個有四個子句的cond表達式. 如何對表達式求值取決于它的類型. 第一個子句處理原子. 如果e是原子, 我們在環境中尋找它的值:
> (eval. 'x '((x a) (y b)))
a
第二個子句是另一個cond, 它處理形如(a ...)的表達式, 其中a是原子. 這包括所有的原始操作符, 每個對應一條子句.
> (eval. '(eq 'a 'a) '())
t
> (eval. '(cons x '(b c))
'((x a) (y b)))
(a b c)
這幾個子句(除了quote)都調用eval.來尋找自變量的值.
最后兩個子句更復雜些. 為了求cond表達式的值我們調用了一個叫 evcon.的輔助函數. 它遞歸地對cond子句進行求值,尋找第一個元素返回t的子句. 如果找到了這樣的子句, 它返回此子句的第二個元素.
> (eval. '(cond ((atom x) 'atom)
('t 'list))
'((x '(a b))))
list
第二個子句的最后部分處理函數調用. 它把原子替換為它的值(應該是lambda 或label表達式)然后對所得結果表達式求值. 于是
(eval. '(f '(b c))
'((f (lambda (x) (cons 'a x)))))
變為
(eval. '((lambda (x) (cons 'a x)) '(b c))
'((f (lambda (x) (cons 'a x)))))
它返回(a b c).
eval.的最后cond兩個子句處理第一個元素是lambda或label的函數調用.為了對label 表達式求值, 先把函數名和函數本身壓入環境, 然后調用eval.對一個內部有 lambda的表達式求值. 即:
(eval. '((label firstatom (lambda (x)
(cond ((atom x) x)
('t (firstatom (car x))))))
y)
'((y ((a b) (c d)))))
變為
(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 (...) e) ...)的表達式求值,先調用evlis.來求得自變量(...)對應的值(...),把()...()添加到環境里, 然后對e求值. 于是
(eval. '((lambda (x y) (cons x (cdr y)))
'a
'(b c d))
'())
變為
(eval. '(cons x (cdr y))
'((x a) (y (b c d))))
最終返回(a c d).
后果
既然理解了eval是如何工作的, 讓我們回過頭考慮一下這意味著什么. 我們在這兒得到了一個非常優美的計算模型. 僅用quote,atom,eq,car,cdr,cons,和cond, 我們定義了函數eval.,它事實上實現了我們的語言,用它可以定義任何我們想要的額外的函數.
當然早已有了各種計算模型--最著名的是圖靈機. 但是圖靈機程序難以讀懂. 如果你要一種描述算法的語言, 你可能需要更抽象的, 而這就是約翰麥卡錫定義 Lisp的目標之一.
約翰麥卡錫于1960年定義的語言還缺不少東西. 它沒有副作用, 沒有連續執行 (它得和副作用在一起才有用), 沒有實際可用的數,沒有動態可視域. 但這些限制可以令人驚訝地用極少的額外代碼來補救. Steele和Sussman在一篇叫做“解釋器的藝術”的著名論文中描述了如何做到這點。
如果你理解了約翰麥卡錫的eval, 那你就不僅僅是理解了程序語言歷史中的一個階段. 這些思想至今仍是Lisp的語義核心. 所以從某種意義上, 學習約翰麥卡錫的原著向我們展示了Lisp究竟是什么. 與其說Lisp是麥卡錫的設計,不如說是他的發現. 它不是生來就是一門用于人工智能, 快速原型開發或同等層次任務的語言. 它是你試圖公理化計算的結果(之一).
隨著時間的推移, 中級語言, 即被中間層程序員使用的語言, 正一致地向Lisp靠近. 因此通過理解eval你正在明白將來的主流計算模式會是什么樣.
?
?
?
后記：細看LISP的代碼，就可以看到，正如Woodpecker.org.cn上的一個網頁（http://wiki.woodpecker.org.cn/moin/Lisp，該網頁有相當多的Lisp資源）所說，LISP語法解析樹的前綴表達。可能是我看慣C風格的程序，一時半會還不習慣，甚至覺得這個LISP比起ObjectARX難多了。不過在這短短的數小時內，通過數個網頁增進了對LISP的了解，雖然還未能消化得了，但今后還有更多深入研究的時間，希望能夠把LISP的威力發揮出來。
?
?
轉載于:https://www.cnblogs.com/alonecat06/archive/2008/09/11/1285869.html
總結
以上是生活随笔為你收集整理的【整理】LISP简介的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： たんやわんやですよ
- 下一篇： 探求数据仓库关键环节ETL的本质