Lisp之根

The Root of List

约翰麦卡锡于1960年发表了一篇非凡的论文,他在这篇论文中对编程的贡献有如 欧几里德对几何的贡献.1 他向我们展示了,在只给定几个简单的操作符和一个 表示函数的记号的基础上, 如何构造出一个完整的编程语言. 麦卡锡称这种语 言为Lisp, 意为List Processing, 因为他的主要思想之一是用一种简单的数据 结构表(list)来代表代码和数据.

值得注意的是,麦卡锡所作的发现,不仅是计算机史上划时代的大事, 而且是一种 在我们这个时代编程越来越趋向的模式.我认为目前为止只有两种真正干净利落, 始终如一的编程模式:C语言模式和Lisp语言模式.此二者就象两座高地, 在它们 中间是尤如沼泽的低地.随着计算机变得越来越强大,新开发的语言一直在坚定地 趋向于Lisp模式. 二十年来,开发新编程语言的一个流行的秘决是,取C语言的计 算模式,逐渐地往上加Lisp模式的特性,例如运行时类型和无用单元收集.

在这篇文章中我尽可能用最简单的术语来解释约翰麦卡锡所做的发现. 关键是我 们不仅要学习某个人四十年前得出的有趣理论结果, 而且展示编程语言的发展方 向. Lisp的不同寻常之处–也就是它优质的定义–是它能够自己来编写自己. 为了理解约翰麦卡锡所表述的这个特点,我们将追溯他的步伐,并将他的数学标记 转换成能够运行的Common Lisp代码.

七个原始操作符

开始我们先定义表达式.表达式或是一个原子(atom),它是一个字母序列(如 foo),或是一个由零个或多个表达式组成的表(list), 表达式之间用空格分开, 放入一对括号中. 以下是一些表达式:

1
2
3
4
5

foo
()
(foo)
(foo bar)
(a b (c) d)

最后一个表达式是由四个元素组成的表, 第三个元素本身是由一个元素组成的表.
在算术中表达式 1 + 1 得出值2. 正确的Lisp表达式也有值. 如果表达式e得出 值v,我们说e返回v. 下一步我们将定义几种表达式以及它们的返回值.

如果一个表达式是表,我们称第一个元素为操作符,其余的元素为自变量.我们将 定义七个原始(从公理的意义上说)操作符: quote,atom,eq,car,cdr,cons,和 cond.

(quote x) 返回x.为了可读性我们把(quote x)简记 为’x.

1
2
3
4
5
6

> (quote a)
a
> 'a
a
> (quote (a b c))
(a b c)

(atom x)返回原子t如果x的值是一个原子或是空表,否则返回(). 在Lisp中我们 按惯例用原子t表示真, 而用空表表示假.

1
2
3
4
5
6

> (atom 'a)
t
> (atom '(a b c))
()
> (atom '())
t

既然有了一个自变量需要求值的操作符, 我们可以看一下quote的作用. 通过引 用(quote)一个表,我们避免它被求值. 一个未被引用的表作为自变量传给象 atom这样的操作符将被视为代码:

1
2

> (atom (atom 'a))
t

反之一个被引用的表仅被视为表, 在此例中就是有两个元素的表:

1
2

> (atom '(atom 'a))
()

这与我们在英语中使用引号的方式一致. Cambridge(剑桥)是一个位于麻萨诸塞 州有90000人口的城镇. 而Cambridge’’是一个由9个字母组成的单词.

引用看上去可能有点奇怪因为极少有其它语言有类似的概念. 它和Lisp最与众 不同的特征紧密联系:代码和数据由相同的数据结构构成, 而我们用quote操作符 来区分它们.

(eq x y)返回t如果x和y的值是同一个原子或都是空表, 否则返回().

1
2
3
4
5
6

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

(car x)期望x的值是一个表并且返回x的第一个元素.

1
2

> (car '(a b c))
a

(cdr x)期望x的值是一个表并且返回x的第一个元素之后的所有元素.

1
2

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

(cons x y)期望y的值是一个表并且返回一个新表,它的第一个元素是x的值, 后 面跟着y的值的各个元素.

1
2
3
4
5
6
7
8

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

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

1
2
3

> (cond ((eq 'a 'b) 'first)
        ((atom 'a)  'second))
second

当表达式以七个原始操作符中的五个开头时,它的自变量总是要求值的.2 我们称这样 的操作符为函数.

函数的表示

接着我们定义一个记号来描述函数.函数表示为(lambda ($p_{1}$…$p_{n}$) e),其中 $p_{1}$…$p_{n}$是原子(叫做参数),e是表达式. 如果表达式的第一个元素形式如 上

1

((lambda ($p_{1}$...$p_{n}$) e) $a_{1}$...$a_{n}$)

则称为函数调用.它的值计算如下.每一个表达式$a_{i}$先求值,然后e再求值.在e的 求值过程中,每个出现在e中的$p_{i}$的值是相应的$a_{i}$在最近一 次的函数调用中的值.

1
2
3
4
5
6

> ((lambda (x) (cons x '(b))) 'a)
(a b)
> ((lambda (x y) (cons x (cdr y)))
   'z
   '(a b c))
(z b c)

如果一个表达式的第一个元素f是原子且f不是原始操作符

1

(f $a_{1}$...$a_{n}$)

并且f的值是一个函数(lambda ($p_{1}$…$p_{n}$)),则以上表达式的值就是

1

((lambda ($p_{1}$...$p_{n}$) e) $a_{1}$...$a_{n}$)

的值. 换句话说,参数在表达式中不但可以作为自变量也可以作为操作符使用:

1
2
3

> ((lambda (f) (f '(b c)))
   '(lambda (x) (cons 'a x)))
(a b c)

有另外一个函数记号使得函数能提及它本身,这样我们就能方便地定义递归函 数.3 记号

1

(label f (lambda ($p_{1}$...$p_{n}$) e))

表示一个象(lambda ($p_{1}$…$p_{n}$) e)那样的函数,加上这样的特性: 任何出现在e中的f将求值为此label表达式, 就好象f是此函数的参数.

假设我们要定义函数(subst x y z), 它取表达式x,原子y和表z做参数,返回一个 象z那样的表, 不过z中出现的y(在任何嵌套层次上)被x代替.

1
2

> (subst 'm 'b '(a b (a b c) d))
(a m (a m c) d)

我们可以这样表示此函数

1
2
3
4
5
6

(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 ($p_{1}$…$p_{n}$) e))为

1

(defun f ($p_{1}$...$p_{n}$) e)

于是

1
2
3
4
5
6

(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的子句总 是会成功的. 于是

1

(cond (x y) ('t z))

等同于我们在某些语言中写的

1

if x then y else z

####

1
2
3

```
#### 
```lisp

####