gr8vyguy@Blogjava

常青樹LISP語言

介紹

Lisp是歷史最悠久的編程語言之一，接近五十年。Lisp以一種簡潔的方式有效地實現(xiàn)了多種高級語言設(shè)計的目的。LISP全名叫LISt Processor，List是LISP的主要數(shù)據(jù)結(jié)構(gòu)。LISP是由John McCarthy1958年左右在MIT創(chuàng)造的一種基于λ演算的函數(shù)式編程語言，最初的目的是用于人工智能(Artificial Intelligence)和符號運算(Symbolic Computation)。

John McCarthy, 一位編程語言設(shè)計和人工智能大師，Lisp之父，參與設(shè)計Algol，提出Time sharing的概念, 提倡使用邏輯學(xué)和數(shù)學(xué)的方法理解編程語言和系統(tǒng)。獲得過眾多獎項，包括1971的圖靈獎

Lisp成功的三個要素

1. 明確的應(yīng)用領(lǐng)域
   編程語言設(shè)計中最難的問題之一是，對一些優(yōu)秀的結(jié)構(gòu)和概念說不。明確的應(yīng)用領(lǐng)域幫助語言設(shè)計者做出一致地決定和取舍。
   1. Lisp -- 符號計算，邏輯，推理，實驗性編程
   2. C     --  Unix操作系統(tǒng)
   3. Simula -- 模擬
   4. PL/1 -- 嘗試解決所有的問題，所以沒有成功，也沒什么影響
2. 抽象機器
   用于執(zhí)行程序的機器，可以是具體的某一特定的機器比如I386，或者是一抽象的機器。在編程語言設(shè)計的過程中，目標(biāo)機器指定的過于具體，或者過于抽象，都會影響語言的成功。
   1. Fortran -- 線性存儲，沒有Stack，Recursion
   2. Algol     -- Stack, Heap
   3. Smalltalk -- Objects, communicating by messages
3. 理論基礎(chǔ)
   Lisp是Turing完全的，指Lisp程序可以解決所有可計算函數(shù)，也就是Partial recursive 函數(shù)。Lisp中的函數(shù)表達式和回歸記號直接來自λ演算。

Lisp一門極其簡單和非常靈活的語言，這也是Lisp長久不衰的原因。使用Lisp編寫的著名軟件有emacs，gtk等等。

Lisp入門

如果你只接觸過C/C++、Pascal, Java這些命令式(Imperative)語言的話，Lisp可能會讓你覺得十分不同尋常，首先吸引你眼球（或者說讓你覺得混亂的）一定是Lisp程序中異常多的括號。為了簡化Parsing，Lisp采用最簡單的語法，它甚至沒有保留字，它只有兩種基本的數(shù)據(jù)，僅有一種基本的語法結(jié)構(gòu)就是表達式，而這些表達式同時也就是程序結(jié)構(gòu)，但是正如規(guī)則最簡單的圍棋卻有著最為復(fù)雜的變化一樣，Lisp可以完成其它語言難于實現(xiàn)的、最復(fù)雜的功能。Lisp的表達是使用單一的前綴結(jié)構(gòu)，即操作符寫在操作數(shù)的前面。下面是Lisp的前綴表達式的幾個例子，以及等效的普通表達式，

Lisp 前綴表達式	普通表達式
(+ 1 2 3 4 5)	(1 + 2+ 3 + 4 + 5)
(* (+ 2 3) (+ 4 5))	((2 + 3) * (4 + 5))
(f x y)	f(x, y)

Lisp的最基本元素是Atom，Atom是不可分。Lisp中有3種Atom，即整型，浮點數(shù)和符號Atom(Symbolic Atom).

下面的Backus Normal Form(BNF)文法定義了整型Atom和符號Atom。

<atom> ::= <smbl> | <num>
<smbl> ::= <char> | <smbl> <char> | <smbl> <digit>
<num> ::= <digit> | <num> <digit>

nil 是一個特殊的Atom，類似于Java中的null。

Dotted Pairs是Lisp中最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，回歸的Dotted Pair組成Lisp的符號表達式，傳統(tǒng)上稱為S表達式

<sexp> := <atom> | (<sexp> . <sexp>)

Lisp中的基本函數(shù)有針對Atom和Pair的cons，car，cdr，eq，atom，以及cond，lambda，define，quote和eval編程函數(shù)。數(shù)值計算函數(shù)+,-,*,/等等，到此為此，所有介紹的結(jié)構(gòu)構(gòu)成了所謂的Pure Lisp。Pure Lisp是沒有Side Effect的。沒有Side Effect是指計算一個表達式時，只是產(chǎn)生了一個值，而非改變機器的狀態(tài)。Impure Lisp還包括以下幾個有Side Effect的函數(shù)，rplaca, rplacd, set, setq.

Lisp解釋器運行Lisp程序的基本結(jié)構(gòu)是read-eval-print循環(huán)。

(define find (lambda (x y) 
      (cond ((equal y nil) nil)
                ((equal x (car y)) x) 
                (true (find x (cdr y))) )))

定義了一個find函數(shù)，如果List y中有x，返回x，否則返回nil。應(yīng)用find函數(shù)

(find 'apple '(pear peach apple fig banana))

返回符號Atom apple。

歷史上，Lisp是一種dynamically scoped language，也稱為call by name。表達式里的變量在不同的Context下，可能引用不同的值。1978年出現(xiàn)Lisp的一種方言Scheme采用的是statical scoped。現(xiàn)代的大不多Lisp實現(xiàn)都采用staticall scoped。Lisp的方言(Dialect)還包括1980年代Guy L. Steele編寫了Common Lisp，Common Lisp試圖對Lisp標(biāo)準(zhǔn)化，這個標(biāo)準(zhǔn)也被大多數(shù)解釋器和編譯器所接受。其他的方言還有Maclisp，Autolisp，Emacs Lisp。 

Lisp的貢獻

1. expression oriented，Pure Lisp沒有Side Effect。在Lisp中以條件表達式代替條件Statements

Lisp的條件表達式
    (cond (p₁ e₁) ... (p_n e_n)) 的意義是
     if p₁ then e₁
     else if p₂ then e₂
         ...
    else if p_n then e_n
    else no_value

(cond (p₁ e₁) …(p_n e_n)沒有返回值，如果

1.   p₁,...,p_n 都是nil
2.   p₁,...,p_i false 并且 p_i+1 undefined
3.   p₁,...,p_i false, p_i+1 true, e_i+1 undefined

cond表達式的幾個例子

(cond ((< 2 1) 2) ((< 1 2) 1)   返回1
(cond ((< 2 1) 2) ((< 3 2) 1)   沒有值
(cond ((diverge 1) (true 0)   沒有值
(cond (true 0) (diverge 1)    返回0

2. Lisp的Abstract Machine由四部分組成

1. 一個Lisp表達式
2. A continuation函數(shù)，表示為計算的剩余部分
3. An Association List， 變量表
4. A Heap, 保存著Atom，Pair和List，Association List中的變量指向Heap中的元素

Heap的基本單位是一個Cons Cell，也就是dotted pair，一個Cons Cell有car和cdr兩部分組成。

Atom在Heap中的表示方法, car為特定的Bit模式，不能是一個指針模式

(cons x y)的執(zhí)行過程

1. 分配一個新的Cell c
2. Cell c的car指向x
3. Cell c的cdr指向y
4. 返回c

表達式(cons (cons 'A 'B) (cons 'A 'B))生成如下的結(jié)構(gòu)

這里有兩個A，B的Cell，因為每個cons函數(shù)的新建一個Cell。另外我們也可以共用一個Cell，生成如下的結(jié)構(gòu)

使用表達式，((lambda (x) (cons x x)) (cons 'A 'B)).

Cons Cell能夠表達List, Tree等各種數(shù)據(jù)結(jié)構(gòu)。

3. 程序也是數(shù)據(jù)(Progams as Data)

Lisp的程序和數(shù)據(jù)使用同樣的句法，內(nèi)部的實現(xiàn)也是一樣的。所以Lisp的程序可以很容易的作為另一個程序的數(shù)據(jù)輸入。比如在后來的函數(shù)式和動態(tài)語言中普遍使用的eval函數(shù)，最早可以追溯到Lisp。

(define substitute (lambda (exp1 var exp2)
    (cond ((atom exp2) (cond ((eq exp2 var) exp1) (true exp2)))
          (true (cons (substitute exp1 var (car exp2))
               (substitute exp1 var (cdr exp2)))))))
(define substitute-and-eval (lambda (x y z) (eval (substitute x y z))))

substitute函數(shù)有3個參數(shù)x，y，z，將z里面所有的y用x替換。在Lisp中程序也是一個List。

4. 函數(shù)表達式

(lambda ( 〈parameters〉 ) 〈function_body〉)

lambda表達式定義一個函數(shù)。Lisp中的lambda表達式是從20世紀(jì)30年代Alonzo Church等人開發(fā)的λ演算過來的。

比如在λ演算，函數(shù)f(x) = x2+y寫成λx.(x² + y)， 在Lisp為(lambda (x) (+ (square x) y))。在傳統(tǒng)數(shù)學(xué)經(jīng)常不區(qū)分函數(shù)本身和函數(shù)值，比如x^2+y既有表達函數(shù)x^2+y的，也有表達函數(shù)x^2+y在(x,y)點的值的。λ演算對這兩種情況做了明顯的區(qū)別。

5. 回歸(Recursion)

回歸函數(shù)是指一個函數(shù)直接或者間接的調(diào)用自身。

(define f (lambda (x) (cond ((eq x 0) 0) (true (+ x (f (- x 1)))))))

定義了函數(shù)f(x) = 1 + 2 + ... x

在λ演算中定義的函數(shù)都是匿名的，既然沒有名字，如何在調(diào)用自身呢？McCarthy'在他1960年的論文里說，λ演算的記法是不能夠表達回歸函數(shù)。這是錯的，λ演算的記法是能夠表達回歸函數(shù)的。

6. Higher-Order 函數(shù)

Higher-Order 函數(shù)是指以函數(shù)作為參數(shù)或者返回值的函數(shù)。比如數(shù)學(xué)上的Composition操作fog,在Lisp中可以這樣定義 (define compose (lambda (f g) (lambda (x) (f (g x)))))

應(yīng)用compose函數(shù)

(compose (lambda (x) (+ x x)) (lambda (x) (* x x)))

定義了x*x + x*x

maplist函數(shù)一個函數(shù)和list為參數(shù)，應(yīng)用參數(shù)函數(shù)到每個參數(shù)list中的元素。

(define maplist (lambda (f x)
      (cond ((eq x nil) nil)
                 (true (cons (f (car x)) (maplist f (cdr x)))))))

應(yīng)用maplist的一個例子
(maplist square ('1 2 3  4)) => (1 4 9 16)

7 垃圾回收(Garbage Collection)

在計算世界里，垃圾是指程序永不再訪問的數(shù)據(jù)，換句話說，改變垃圾的值，對程序的結(jié)果沒有任何影。Lisp的數(shù)據(jù)和變量都保存在Heap的Cons Cell中。垃圾回收就是指在Heap中找到所有的垃圾，然后釋放。Java中以及其他語言中的自動垃圾回收機制可以回溯到Lisp。

執(zhí)行(car (cons e1 e2))后，任何在e2中分配的cons cells都成了垃圾。

人們已經(jīng)發(fā)展了多種垃圾回收的算法。最簡單的一種是Mark-and-Sweep。

1. Mark Continuation里直接引用的位置
2. Mark任何由已Mark的位置可以達到的位置
3. 直到不能再Mark新的位置，所有沒有Mark的位置都是垃圾

posted on 2007-05-05 19:04 gr8vyguy 閱讀(4832) 評論(3)  編輯  收藏 所屬分類: 計算機科學(xué)基礎(chǔ)