lisp入门

lisp入门（一）lisp是一门历史悠久的语言，全名叫listprocessor，也就是“表处理语言”，它是由johnmccarthy于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'()'())tlisp入门（二）上一集我们讲了lisp世界七个公理的前三个，这一集我们接着讲剩下的四个。首先是三个表操作(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中的函数定义我们已经在上节给出（快速抢答：谁还记得请举手），在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入门（四）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是否为空表。例如：(null'a)()(null'())t(andxy)，逻辑与，当且仅当x和y都不是空表时返回't，否则返回空表。(and'a'b)t(and(atom'a)(eq'b'c))()(notx)，逻辑非，当x是空表时返回't，否则返回空表。（有人问我or在哪儿？）例如：(not'a)()(not(eq'a'b))t(appendxy)，连接两个表x和y，注意它与cons和list之间的不同之处。例如：(append'(ab)'(cd))(abcd)(append'()'(xy))(xy)(pairxy)，这里x和y是两个长度相同的表，pair生成一个表，其中每个元素是x和y中相应位置上的元素组成的一个元素对，这个函数的返回值类似于其它语言中的map或dictionary的概念。例如：(pair'(abc)'(xyz))((ax)(by)(cz))(assocxy)，其中x是一个原子，y是一个形如pair所返回的表，assoc在y中查找第一个左元素为x的元素对并返回。例如：(assoc'a'((ax)(by)))x(assoc'a'((a(foobar))(by)(cz)))(foobar)(substxyz)，在表z中将任意层次上出现的原子y都替换为表达式x。例如：(subst'(xy)'b'(ab(abc)d))(a(xy)(a(xy)c)d)下面我们给出这些常用函数的简单实现：(defunnull(x)(eqx'()))(defunand(xy)(cond(x(cond(y't)('t'())))('t'())))(defunnot(x)(cond(x'())