Lisp 语言入门


Lisp 语言入门 Lisp 是一门历史悠久的语言,全名叫 LISt Processor,也就是“表处理语言”,它是由 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 () (abc xyz) (a b (c) d) 最后一个表是由四个元素构成的,其中第三个元素本身也是一个表。 正如算数表达式 1+1 有值 2 一样,Lisp 中的表达式也有值,如果表达式 e 得出值 v,我们说 e 返回 v。如 果一个表达式是一个表,那么我们把表中的第一个元素叫做操作符,其余的元素叫做自变量。 正如欧几里德的几何世界中有五个公理一样,我们在这里给出 Lisp 世界中的 7 个公理(基本操作符): (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 下一章,我们将讲解与表相关的操作符和条件操作符,以及 Lisp 程序的基本元素——函数。 一集我们讲了 Lisp 世界七个公理的前三个,这一集我们接着讲剩下的四个。 首先是三个表操作 (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) 看到这里大家可能会问,为什么没有取表中除开头外其它某个位置上的元素的操作符,别急,等我们讲到地 球人都知道的函数和递归你就知道该怎么办了,也许你现在已经想得差不多了? 接下来要介绍给大家的是构成程序逻辑的一个基本功能……条件分支,在 Lisp 中,它是由 cond 操作符完成 的,cond 是七个公理中最后一个也是形式最复杂的一个(欧几里德的最后一个公理也如是): (cond (p1 e1) (p2 e2)...(pn en)) 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 (p1 p2 ... pn) e) 其中,pi 为原子,在函数中称之为参数,e 是表达式,也就是函数体。 调用一个函数的方式如下: ((lambda (p1 p2 ... pn) e) a1 a2 ... an) 其中 ai 为表达式,按照我们的惯例,称之为实参。 整个函数的调用过程如下:每一个表达式 ai(实参)先求值,然后再将这些实参代入 e 中求值,最后的结果 即为整个表达式的返回值。 如果一个表达式的第一个元素是一个原子,但不是基本操作符(也就是我们先前提到的那 7 个),如: (f a1 a2 ... an) 并且 f 的值是一个函数(lambda (p1 p2 ... pn) e),则上述表达式等价于 ((lambda (p1 p2 ... pn) e) a1 a2 ... an) 看了这一段,可能大家都有点晕,到窗口去做几个深呼吸,然后回来做下面这个练习,看看这个表达式的结 果是什么? ((lambda (f) (f '(b c))) '(lambda (x) (cons 'a x))) 如果你得出了结果,那么继续往下看,否则再把前面几段话多读几遍,把上面的练习输入到一个能自动匹配 括号的文本编辑器里继续研究。 在这里我打算插几句题外话,可能有很多人已经见识过这个 lambda 了,不过不太可能是在 Lisp 里(要是 这样的话你就应该不用来看这片“入门”了,不是吗?),而多半是在 Python 里,Python 手册中对这个 lambda 仅仅是一笔带过,他大概是这么说的:“使用 lambda 这个词是因为它类似于 Lisp 语言里同名的 一个语法结构。”好了,我们现在就来看看 lambda 这个典故的真正起源。 lambda 这个词来源于 lambda 演算理论。lambda 是什么?对于现在的人来说,这个概念不过就是“函 数”而已,但是对于 lambda 演算理论的出现的那个年代来说,它可是一种革命性的创新。lambda 演算 理论过于复杂,而且作为一篇 Lisp 的简介,讨论它已经完全偏离了主题,但是它所提出的另一个概念—— 高阶函数(High Order Function)——却在 Lisp 语言中占有重要的地位,甚至可以说是 Lisp 如此与 众不同的主要原因。 正如“高阶导数”就是“导数的导数”一样,所谓高阶函数,其实就是“函数的函数”(高数老师,原谅我 吧)。即把一个函数本身当作另一个函数的自变量(在现代的 C++中提出的“functor”这个概念其实就 是高阶函数在 C++中的一种实现)。高阶函数的出现,将“函数”在编程语言中的地位提升到一个“一等 公民”的地位,你可以像操作任何基本数据类型一样操作一个函数,对它进行变换、传递,随你怎么折腾。 下面我们回到正题,继续讨论 Lisp 中的函数,我们可以看到,至今为止,我们的函数都还没有名字,函数 可以没有名字,也就是匿名函数正是 Lisp 的另一大特色,Lisp 可以让程序员把数据和名字剥离开,这对于 许多其它的编程语言来说是直到现在也无法享受到的一种奢侈。 函数没有名字会带来一个问题,那就是你无法在函数中调用自身(好啦,我知道还有 Y 组合,不过这是一篇 入门文章),所以 Lisp 提供了一种形式可以让你用一个标识符来引用函数: (label f (lambda (p1 p2 ... pn) e)) 这个表达式和前面的简单 lambda 表达式等价,但是在 e 中出现的所有 f 都会被替换为整个 lambda 表达 式,也就是递归。 同时,Lisp 为它提供了一种简写形式: (defun f (p1 p2 ... pn) e) 你可以开始写你的第一个有用的 Lisp 程序了,你打算写什么?(无论什么,只要不是 Hello world 就好) 下一集,我们将给出一些常用的函数。 Lisp 的语法元素在前几集中已经基本讨论完毕,相比 C#或 Java 数百页的 Specification,它可能简单的 让你有些惊讶,不过,伟大的东西总是简单的,不是吗?现在让我们来回顾一下上一集中提到的内容,首先 提几个问题: 既然 cond 在概念上相当于过程式语言中的 if 语句,那么与 if 相对的 else 分支在 cond 表达式中应该如何 描述? 在(我们已经学过的)Lisp 中如何表达“重复”这个语义?或者你能写一个 foreach 循环函数? (注:不要问输入输出函数或算术逻辑运算在哪儿之类的问题,它们都是微不足道的事……) 这一集中,我们将描述几个常用的函数,并给出它们的简单实现 首先解答在第一集中提出的问题:如何取一个表中的第二个、第三个或第 n 个元素? 可能有些读者已经想到了,取第二个元素可以采用如下形式: (car (cdr x)) 同理,取第三个元素是这样的: (car (cdr (cdr x))) 事实上,这种组合在 Lisp 中经常要用到,为了方便,Lisp 提供了一个通用模式——cxr,其中 x 为 a 或 d 的序列,来简记 car 和 cdr 的组合,例如: > (cadr '((a b) (c d) e)) (c d) > (caddr '((a b) (c d) e)) e > (cdar '((a b) (c d) e)) (b) 另外,使用(list e1 e2 ... en)来表示 (cons e1 (cons e2 (... (cons en '())...))) > (cons 'a (cons 'b (cons 'c '()))) (a b c) > (list 'a 'b 'c) (a b c) 现在我们定义一些新的常用函数,我建议你先自己想一想,不要急着看我给出的实现。 (注:某些函数在 Common Lisp 中已经存在,所以如果你想试验一下,给它们换个名字) (null x),测试 x 是否为空表。例如: > (null 'a) () > (null '()) t (and x y),逻辑与,当且仅当 x 和 y 都不是空表时返回't,否则返回空表。 > (and 'a 'b) t > (and (atom 'a) (eq 'b 'c)) () (not x),逻辑非,当 x 是空表时返回't,否则返回空表。(有人问我 or 在哪儿?)例如: > (not 'a) () > (not (eq 'a 'b)) t (append x y),连接两个表 x 和 y,注意它与 cons 和 list 之间的不同之处。例如: > (append '(a b) '(c d)) (a b c d) > (append '() '(x y)) (x y) (pair x y),这里 x 和 y 是两个长度相同的表,pair 生成一个表,其中每个元素是 x 和 y 中相应位置上的元 素组成的一个元素对,这个函数的返回值类似于其它语言中的 map 或 dictionary 的概念。例如: > (pair '(a b c) '(x y z)) ((a x) (b y) (c z)) (assoc x y),其中 x 是一个原子,y 是一个形如 pair 所返回的表,assoc 在 y 中查找第一个左元素为 x 的 元素对并返回。例如: > (assoc 'a '((a x) (b y))) x > (assoc 'a '((a (foo bar)) (b y) (c z))) (foo bar) (subst x y z),在表 z 中将任意层次上出现的原子 y 都替换为表达式 x。例如: > (subst '(x y) 'b '(a b (a b c) d)) (a (x y) (a (x y) c) d) 下面我们给出这些常用函数的简单实现: (defun null (x) (eq x '())) (defun and (x y) (cond (x (cond (y 't) ('t '()))) ('t '()))) (defun not (x) (cond (x '()) ('t 't))) (defun append (x y) (cond ((null x) y) ('t (cons (car x) (append (cdr 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)))))) (defun assoc (x y) (cond ((eq (caar y) x) (cadar y)) ('t (assoc x (cdr y))))) (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)))))) 如果看到这里你还没有晕菜,说明你的神经的确很坚强。注意在这些例子中是如何表达“重复”这个概念的, 在 Lisp 中,最常用的重复其实并不是真正意义上的重复,而是递归,这也是绝大多数函数式语言的一个共 同特征——函数的嵌套和递归,构成了整个程序逻辑。 这一部分内容可以让你真正感受到 Lisp 的特色,与编写过程式语言的程序相比,编写 Lisp 程序需要一种完 全不同的思维方式,也许这正是 Lisp 语言几十年来长盛不衰的真正原因吧。 理解了这一部分,下一集中我们将领教一下 Lisp 的威力,我们将用 Lisp 编写一个 Lisp 解释器。如果你以 前没有见过这个程序,我保证它一定会让你吃惊。 上一集我们已经见到了一个 Lisp 程序的大致外貌,在文末,我提到这一集中我们将会用 Lisp 写一个 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))))) (注:可能有的读者已经发现,Lisp 并不要求你一定要在使用函数前先定义它) 整个程序包含三个函数,主函数我们遵从 Lisp(和 Python、Perl)的惯例,叫它 eval,它是整个程序的 骨架。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 (p1 p2 ... pn) e) a1 a2 ... an)的表达式求值,先调用 evlis 来求得自变量(a1 a2 ... an)对应的值(v1 v2 ... vn),把(p1 v1) (p2 v2) ... (pn vn)添加到上下文里,然后对 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)。 讲了这么一大篇,如果你看懂了,说明你已经理解 Lisp 甚至 FP 的基本编程方式和思路,那么我们写了一个 如此之长的程序究竟能干什么呢? 我们在这里得到了一个非常优美的计算模型,eval 函数实际上实现了整个语言,用它我们可以定义所需的任 何其它函数。换句话说,我们现在有了一个自己的 Lisp。 (注:由此可见,递归下降的语法分析是多么美好啊,因为它意味着你可以用几十、最多不过一两百行程序 搞定一个复杂的分析器,对比 LALR 你将更有体会) 下面我们该去哪儿?这个问题,请读者自己去寻找答案。 这个系列终于写完,很是费了我不少力气,因为我从小语文就一直不太好,有时很难表达清楚自己的意思。 这次算是自己撵着自己这只鸭子上架吧。 Lisp 的历史十分悠久,据说仅次于 Fortran,算得上是第二古老的语言。对于 Fortran,语言学家给予的 负面评价远比正面评价多,甚至在很多场合被作为程序设计语言的反面教材;但是 Lisp 则刚好相反,它一 直被人们作为一个优秀作品的例子被大加赞扬,这些人中包括著名的计算机科学家,Smalltalk 的发明人— —Alan Kay。 有一个传言,据说 McCarthy 当时想把这门语言的语法设计往后拖一拖,等到他把一些有趣的事做完之后, 再回过头来给这门基于 Lambda 演算理论的语言加上一些数学家们熟悉的语法,可是他的一个学生发现, 在一个还没有定义正式语法的抽象语法中写程序,感觉非常好,于是 McCarthy 干脆就决定不定义 Lisp 的 语法。直到如今,Lisp 的“语法”定义中值得一提的规则似乎只有一条“括号要配对”,其它的都是“语 义”上的规范。 这样做当然不是没有代价的,很快 Lisp 就出现了第一个分支 Scheme。这个语言由 Guy Steele, Jr.和他 的老师 Gerald Sussman 设计。这两位最开始的工作是改进 Lisp,他们共同把 Lisp 由 Dynamic scope 变成了 Lexical scope。今天几乎大家熟悉的所有语言都是 Lexical scope。后来他们共同把 Continuation 这个概念引入了 Lisp,于是一门新语言就这样诞生。 随后,Sussman 把 Lexical scope 和 Scheme 中的一些其它概念都引入了 Lisp,并由此确立了 Common Lisp 的标准,Sussman 本人也一直是 Common Lisp 的主力。 作为一门最早出现的 FP 语言,Lisp 当然有它的缺点,其中最为人诟病的恐怕就是括号了,所以随后出现的 许多 FP 语言都试图使用另外的语法来清晰的描述程序,这其中最著名的当属 Haskell(也许还有 Caml?),Haskell 是一门“纯正”的 FP 语言,在 Haskell 中,变量不能赋值,没有循环,甚至没有程 序流程,一切都是函数。 (注:我个人认为,想要领会 FP 的精髓,用 Haskell 入门似乎更合适) 近年来,随着 FP 的进一步流行,许多命令式语言当中也逐步加入了 FP 的成分,典型如 C++中的 “functor”,如果你用过 STL 或者 Boost,你会发现利用 functor 可以完成很多不可思议的功能。就我 个人的经验,functor 最密集的应用是在 Boost.Spirit 库中,它可以让你用一大堆 Parse/Match Functor 构造一个复杂的语法分析器。 熟悉一门函数式语言,用心体会它的妙用。在你转变思维方式后,你会发现即便是原来你熟悉的命令式语言 也能发挥出更大的威力。
还剩13页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 2 人已下载

下载pdf

pdf贡献者

benjac

贡献于2012-06-16

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf