LISP编程举例

Lisp是一门历史悠久的语言，全名叫LIStProcessor，也就是“表处理语言”，它是由John

McCarthy于1958年就开始设计的一门语言。和Lisp同时期甚至更晚出现的许多语言如Algo

等如今大多已经消亡，又或者仅仅在一些特定的场合有一些微不足道的用途，到现在还广为

人知的恐怕只剩下了Fortran和COBOL。但唯独Lisp，不但没有随着时间而衰退，反倒是

一次又一次的焕发出了青春，从Lisp分支出来的Scheme、ML等语言在很多场合的火爆程

度甚至超过了许多老牌明星。那么这颗常青树永葆青春的奥秘究竟在哪里呢？

如果你只接触过C/C++、Pascal这些“过程式语言”的话，Lisp可能会让你觉得十分不同寻

常，首先吸引你眼球（或者说让你觉得混乱的）一定是Lisp程序中异常多的括号，当然从

现在的角度来讲，这种设计的确对程序员不大友好，不过考虑到五六十年代的计算机处理能

力，简化语言本身的设计在那时算得上是当务之急了。

Lisp的基本语法很简单，它甚至没有保留字（有些语言学家可能对这一点有异议，别怕，我

听你们的），它只有两种基本的数据，仅有一种基本的语法结构就是表达式，而这些表达式

同时也就是程序结构，但是正如规则最简单的围棋却有着最为复杂的变化一样，Lisp使用最

基本的语言结构定义却可以完成其它语言难于实现的、最复杂的功能。

废话少说，现在我们就来看看Lisp语言中的基本元素。

Lisp的表达式是一个原子(atom)或表(list)，原子(atom)是一个字母序列，如abc；表是由零个

或多个表达式组成的序列，表达式之间用空格分隔开，放入一对括号中，如：

abc

()

(abcxyz)

(ab(c)d)

最后一个表是由四个元素构成的，其中第三个元素本身也是一个表。

正如算数表达式1+1有值2一样，Lisp中的表达式也有值，如果表达式e得出值v，我们说e返回v。如果一个表达式是一个表，那么我们把表中的第一个元素叫做操作符，其余的元

素叫做自变量。

正如欧几里德的几何世界中有五个公理一样，我们在这里给出Lisp世界中的7个公理（基

本操作符）：

(quotex)返回x，我们简记为'x

(atomx)当x是一个原子或者空表时返回原子t，否则返回空表()。在Lisp中我们习惯用原子

t表示真，而用空表()表示假。

>(atom'a)

t

>(atom'(abc))

()

>(atom'())t

现在我们有了第一个需要求出自变量值的操作符，让我们来看看quote操作符的作用——通

过引用(quote)一个表，我们避免它被求值。一个未被引用的表达式作为自变量，atom将其

视为代码，例如：>(atom(atom'a))

t

反之一个被引用的表仅仅被视为表>(atom'(atom'a))

()

引用看上去有些奇怪，因为你很难在其它语言中找到类似的概念，但正是这一特征构成了Lisp最为与众不同的特点——代码和数据使用相同的结构来表示，而我们用quote来区分它

们。(eqxy)当x和y的值相同或者同为空表时返回t，否则返回空表()

>(eq'a'a)

t

>(eq'a'b)

()

>(eq'()'())

t

首先是三个表操作

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

>(car'(ab))

a

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

>(cdr'(abc))

(bc)

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

素，例如：>(cons'a'(bc))

(abc)

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

(abc)

看到这里大家可能会问，为什么没有取表中除开头外其它某个位置上的元素的操作符，别急，

等我们讲到地球人都知道的函数和递归你就知道该怎么办了，也许你现在已经想得差不多

了？

接下来要介绍给大家的是构成程序逻辑的一个基本功能……条件分支，在Lisp中，它是由cond操作符完成的，cond是七个公理中最后一个也是形式最复杂的一个（欧几里德的最后

一个公理也如是）：

(cond(p1e1)(p2e2)...(pnen))

p1到pn为条件，e1到en为结果，cond操作符依次对p1到pn求值，直到找到第一个值为原子t（还记得吗？）的p，此时把对应的e作为整个表达式的值返回，例如：

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

((atom'a)'second))

second

好了，至此我们已经有了Lisp世界的所有基本公理，我们可以开始构建整个世界的规则了。

在这七个操作符中，除quote和cond之外，以其他的五个操作符开头的表达式总是要对它

的所有自变量求值，然后产生结果，我们把这样的表达式叫做函数。

上一集我们讲到了“函数”，其实这个概念早在初中数学里就已经学过了，一个函数无非就

是将自变量映射到值的对应关系，在Lisp里也一样。

Lisp中的函数定义我们已经在上节给出（快速抢答：谁还记得请举手），在Lisp中采用如下

形式描述一个函数：

(lambda(p1p2...pn)e)

其中，pi为原子，在函数中称之为参数，e是表达式，也就是函数体。

调用一个函数的方式如下：

((lambda(p1p2...pn)e)a1a2...an)

其中ai为表达式，按照我们的惯例，称之为实参。

整个函数的调用过程如下：每一个表达式ai（实参）先求值，然后再将这些实参代入e中求

值，最后的结果即为整个表达式的返回值。

如果一个表达式的第一个元素是一个原子，但不是基本操作符（也就是我们先前提到的那7

个），如：

(fa1a2...an)

并且f的值是一个函数(lambda(p1p2...pn)e)，则上述表达式等价于

((lambda(p1p2...pn)e)a1a2...an)

看了这一段，可能大家都有点晕，到窗口去做几个深呼吸，然后回来做下面这个练习，看看

这个表达式的结果是什么？

((lambda(f)(f'(bc)))'(lambda(x)(cons'ax)))如果你得出了结果，那么继续往下看，否则再把前面几段话多读几遍，把上面的练习输入到

一个能自动匹配括号的文本编辑器里继续研究。

在这里我打算插几句题外话，可能有很多人已经见识过这个lambda了，不过不太可能是在Lisp里（要是这样的话你就应该不用来看这片“入门”了，不是吗？），而多半是在Python

里，Python手册中对这个lambda仅仅是一笔带过，他大概是这么说的：“使用lambda这个

词是因为它类似于Lisp语言里同名的一个语法结构。”好了，我们现在就来看看lambda这

个典故的真正起源。

lambda这个词来源于lambda演算理论。lambda是什么？对于现在的人来说，这个概念不过

就是“函数”而已，但是对于lambda演算理论的出现的那个年代来说，它可是一种革命性

的创新。lambda演算理论过于复杂，而且作为一篇Lisp的简介，讨论它已经完全偏离了主

题，但是它所提出的另一个概念——高阶函数（HighOrderFunction）——却在Lisp语言中

占有重要的地位，甚至可以说是Lisp如此与众不同的主要原因。

正如“高阶导数”就是“导数的导数”一样，所谓高阶函数，其实就是“函数的函数”（高

数老师，原谅我吧）。即把一个函数本身当作另一个函数的自变量（在现代的C++中提出的

“functor”这个概念其实就是高阶函数在C++中的一种实现）。高阶函数的出现，将“函数”

在编程语言中的地位提升到一个“一等公民”的地位，你可以像操作任何基本数据类型一样

操作一个函数，对它进行变换、传递，随你怎么折腾。

下面我们回到正题，继续讨论Lisp中的函数，我们可以看到，至今为止，我们的函数都还

没有名字，函数可以没有名字，也就是匿名函数正是Lisp的另一大特色，Lisp可以让程序

员把数据和名字剥离开，这对于许多其它的编程语言来说是直到现在也无法享受到的一种奢

侈。

函数没有名字会带来一个问题，那就是你无法在函数中调用自身（好啦，我知道还有Y组

合，不过这是一篇入门文章），所以Lisp提供了一种形式可以让你用一个标识符来引用函数：

(labelf(lambda(p1p2...pn)e))

这个表达式和前面的简单lambda表达式等价，但是在e中出现的所有f都会被替换为整个lambda表达式，也就是递归。

同时，Lisp为它提供了一种简写形式：

(defunf(p1p2...pn)e)

你可以开始写你的第一个有用的Lisp程序了，你打算写什么？（无论什么，只要不是Helloworld就好）

下一集，我们将给出一些常用的函数。

Lisp的语法元素在前几集中已经基本讨论完毕，相比C#或Java数百页的Specification，它可能简单的让你有些惊讶，不过，伟大的东西总是简单的，不是吗？现在让我们来回顾一下

上一集中提到的内容，首先提几个问题：

既然cond在概念上相当于过程式语言中的if语句，那么与if相对的else分支在cond表达

式中应该如何描述？

在（我们已经学过的）Lisp中如何表达“重复”这个语义？或者你能写一个foreach循环函

数？

（注：不要问输入输出函数或算术逻辑运算在哪儿之类的问题，它们都是微不足道的事……）

这一集中，我们将描述几个常用的函数，并给出它们的简单实现

首先解答在第一集中提出的问题：如何取一个表中的第二个、第三个或第n个元素？

可能有些读者已经想到了，取第二个元素可以采用如下形式：

(car(cdrx))

同理，取第三个元素是这样的：

(car(cdr(cdrx)))

事实上，这种组合在Lisp中经常要用到，为了方便，Lisp提供了一个通用模式——cxr，其

中x为a或d的序列，来简记car和cdr的组合，例如：

>(cadr'((ab)(cd)e))

(cd)

>(caddr'((ab)(cd)e))

e

>(cdar'((ab)(cd)e))

(b)

另外，使用(liste1e2...en)来表示(conse1(conse2(...(consen'())...)))

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

(abc)

>(list'a'b'c)

(abc)

现在我们定义一些新的常用函数，我建议你先自己想一想，不要急着看我给出的实现。

（注：某些函数在CommonLisp中已经存在，所以如果你想试验一下，给它们换个名字）

(nullx)，测试x是否为空表。例如：