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 阅读(4814) 评论(3)  编辑  收藏 所属分类: 计算机科学基础