gr8vyguy@Blogjava

常青樹LISP語言

介紹

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

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

Lisp成功的三個要素

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

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

Lisp入門

如果你只接觸過C/C++、Pascal, Java這些命令式(Imperative)語言的話，Lisp可能會讓你覺得十分不同尋常，首先吸引你眼球（或者說讓你覺得混亂的）一定是Lisp程序中異常多的括號。為了簡化Parsing，Lisp采用最簡單的語法，它甚至沒有保留字，它只有兩種基本的數據，僅有一種基本的語法結構就是表達式，而這些表達式同時也就是程序結構，但是正如規則最簡單的圍棋卻有著最為復雜的變化一樣，Lisp可以完成其它語言難于實現的、最復雜的功能。Lisp的表達是使用單一的前綴結構，即操作符寫在操作數的前面。下面是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，即整型，浮點數和符號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中最基礎的數據結構，回歸的Dotted Pair組成Lisp的符號表達式，傳統上稱為S表達式

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

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

Lisp解釋器運行Lisp程序的基本結構是read-eval-print循環。

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

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

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

返回符號Atom apple。

歷史上，Lisp是一種dynamically scoped language，也稱為call by name。表達式里的變量在不同的Context下，可能引用不同的值。1978年出現Lisp的一種方言Scheme采用的是statical scoped。現代的大不多Lisp實現都采用staticall scoped。Lisp的方言(Dialect)還包括1980年代Guy L. Steele編寫了Common Lisp，Common Lisp試圖對Lisp標準化，這個標準也被大多數解釋器和編譯器所接受。其他的方言還有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函數，表示為計算的剩余部分
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)的執行過程

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

表達式(cons (cons 'A 'B) (cons 'A 'B))生成如下的結構

這里有兩個A，B的Cell，因為每個cons函數的新建一個Cell。另外我們也可以共用一個Cell，生成如下的結構

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

Cons Cell能夠表達List, Tree等各種數據結構。

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

Lisp的程序和數據使用同樣的句法，內部的實現也是一樣的。所以Lisp的程序可以很容易的作為另一個程序的數據輸入。比如在后來的函數式和動態語言中普遍使用的eval函數，最早可以追溯到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函數有3個參數x，y，z，將z里面所有的y用x替換。在Lisp中程序也是一個List。

4. 函數表達式

(lambda ( 〈parameters〉 ) 〈function_body〉)

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

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

5. 回歸(Recursion)

回歸函數是指一個函數直接或者間接的調用自身。

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

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

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

6. Higher-Order 函數

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

應用compose函數

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

定義了x*x + x*x

maplist函數一個函數和list為參數，應用參數函數到每個參數list中的元素。

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

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

7 垃圾回收(Garbage Collection)

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

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

人們已經發展了多種垃圾回收的算法。最簡單的一種是Mark-and-Sweep。

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

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