原创转载：LISP的历史

 2011-5-8 21:30  2817 8 8 分类: 软件与OS

转载摘自：http://www.cnblogs.com/alonecat06/archive/2008/09/11/1285869.html，在此向原作者致谢意。

作者：读来du往de猫的世界斌伯

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，否则返回空表()

> (eq 'a 'a)
t
> (eq 'a 'b)
()
> (eq '() '())
t

(car x)要求x是一个表，它返回x中的第一个元素，例如：

> (car '(a b))
a

(cdr x)同样要求x是一个表，它返回x中除第一个元素之外的所有元素组成的表，例如：

> (cdr '(a b c))
(b c)

(cons x y)要求y是一个表，它返回一个表，这个表的第一个元素是x，其后是y中的所有元素，例如：

> (cons 'a '(b c))
(a b c)

> (cons 'a (cons 'b (cons 'c ())))
(a b c)

(cond (...) ...(...)) 的求值规则如下. p表达式依次求值直到有一个返回t. 如果能找到这样的p表达式,相应的e表达式的值作为整个cond表达式的返回值.

> (cond ((eq 'a 'b) 'first)
((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是麦卡锡的设计,不如说是他的发现. 它不是生来就是一门用于人工智能, 快速原型开发或同等层次任务的语言. 它是你试图公理化计算的结果(之一).