Lisp入门

超、凢脫俗 2022-07-16 06:11 513阅读 0赞

基于 GNU Common Lisp 编译环境

LISP 是 LISt Processor 的缩写，是“列表处理语言”意思。

Lisp语言最初是由美国的 John McCarthy 在 1958 年提出来的，是最早的计算机语言之一。

然而，半个多世纪后的今天，Lisp 语言仍然在使用，并且还会继续被使用，这和它独特的结构是分不开的。Lisp的基本框架可以容下任何修订或扩充。

《黑客与画家》的作者 Paul Graham 就对 Lisp 语言赞誉有加，认为大部分的现代语言都在向 Lisp 靠近。

## 关于LISP ##

LISP 是 LISt Processor 的缩写，是“列表处理语言”意思。

Lisp语言最初是由美国的John McCarthy在1960年提出来的，是最早的计算机语言之一。因为 LISP 语言在符号处理方面的优势，LISP 最初使用于[人工智能][Link 1]处理。（早期有部分人工智能的研究者认为：“符号演算系统可以衍生出智能。”）[\[1\]][1]

然而，四十多年后的今天，Lisp语言仍然在使用，并且还会继续被使用，这和它独特的结构是分不开的。Lisp的基本框架可以容下任何修订或扩充。

## 第一次运行 ##

Windows 用户安装完了之后，您只需从开始菜单中找到它并单击以运行就可以了。

Linux 用户安装完之后，在终端运行 `gcl` 即可启动LISP编译环境。

## 尝试 ##

运行后，您会看到如下类似的信息：

GCL (GNU Common Lisp)  2.6.6 CLtL1    Feb 10 2005 08:19:54
    Source License: LGPL(gcl,gmp), GPL(unexec,bfd)
    Binary License:  GPL due to GPL'ed components: (UNEXEC)
    Modifications of this banner must retain notice of a compatible license
    Dedicated to the memory of W. Schelter
    
    Use (help) to get some basic information on how to use GCL.
    
    >

其中的 `>` 号表示你可以在其后输入指令。比如我们可以输入第一个指令 `(help)` 。看看会发生什么。

## 第一章 函数 ##

我们会讲解一下 lisp 的基本概念。在讲解基本概念之前，我们先要学会使用 Lisp 的解释器。解释器基本上是这个样子的：你给解释器一个表达式（也就是你在键盘上打字），而解释器显示这个表达式的值（就是给你一个答案）。

现在，往解释器里输入 42 这个数字，并且按回车键，看看解释器会给你什么反馈。

解释器会返回同一个数：

### 数学表达式 ###

LISP 可以算数学题，不过，你要先学会 LISP 的表达方式才行。 比如

1+2

这个数学式子，在 LISP 中会表示为：

(+ 1 2)

也就是说，在 LISP 中，数学表达式要用括号括起来，并且运算符要放在第一个，运算数放在后面，中间用必要的空格隔开。上面表达式中的运算符，即第一个符号，称之为 **操作符**，而其他的符号，称为 **操作域**。这种把操作符放在第一个位置的表达方式，称之为 **前缀表示法**，也被叫做 **波兰表示法**。

你把上面的式子输入到 LISP 解释器中，按下回车键看看会出现什么现象。

数字 3 会出现 。

在 Common Lisp中，我们输入一个式子，而Lisp的解译器告诉我们结果。 这样，我们就拥有了一个计算器，那么，我们可以把玩一下这个计算器。比如，依次输入下列算式，看看结果是什么。

(- 3 2)
    (* 6 7)
    (/ 8 6)

第一行的结果是 1，第二行的结果是 42。 第三行的结果竟然是 4/3。看来，LISP 还是很智能的，知道用分数来表示结果。

而且，即使再复杂点的数学表达式，LISP 也能计算。

(+ 1 2 3 4)
    (* (+ 2 4) 7)

### 函数的表达方式 ###

Lisp语言的是一种函数式语言。所谓函数是说，它的语句就像数学中的函数表达式的作用是一样的。 虽然概念一样，然而在表达上还是有些出入的。

在数学中，我们会这样表示一个函数

\{\\displaystyle f(x)\}![\{\\displaystyle f(x)\}][displaystyle f_x]

同样的函数，在Lisp中我们会这样表示：

(f x)

在数学中，函数是一个函数名，后面跟着一个括号，括号里面装着参数。但在 LISP 中，整个函数表达式用括号括起来，第一个元素是函数的名称，后面跟着函数的参数。

如果是有两个参数（在一些立体几何的函数中就会有这样的例子），比如

\{\\displaystyle z=f(x,y)\}![\{\\displaystyle z=f(x,y)\}][displaystyle z_f_x_y]

聪明的你们应该可以猜出来是这样写的：

(f x y)

因为加法符号的可以看成是一个二元函数，所以，我们可以这样写：

+(1,1)

那么，写成 LISP 的形式，就是

(+ 1 1)

现在，你知道为什么数学表达式中运算符要放在最前面了吧。

复合函数如：

f(g(x))

在 LISP 中会写成

(f (g x))

在Lisp中，表达式是很重要的概念。你每次输入的表达式，都会被求值。

我们可以尝试一下 LISP 中自带的函数

(sqrt 9)

sqrt 表示开方的意思，这句话的意思就是对9开方，返回的结果自然是3了。

(log 16 2)

这句话表示求以2为底16的对数。

### 逻辑运算 ###

逻辑运算，就是关于真假的运算，我们应该先习惯 LISP 的语法，那么 3<4 该如何写呢？

(< 3 4)

上面这个式子的结果是

在 LISP 中，T 代表逻辑真，而 NIL 代表逻辑假。暂且不用太追究名称的由来，后面我会告诉你的。

接下来，尝试一个逻辑与表达式：

(and T T)

就是真且真为真。

或的英语翻译是OR。

(OR T NIL)

顺带告诉大家，在Lisp中大小写不重要。

最后来个最复杂的

(or (> 3 4) (> 4 2))

## 第二章 表、CAR、CDR ##

### 表和原子 ###

Lisp的全名叫“表处理语言”，LISt Procesor 。可见表在Lisp中的重要性。

简单说来，用小括号括起来的表达式式就叫表。

比如：

(+ 1 2)

就是一个表。

而表里面的东西，就是原子。比如上面的这个表里，+ 是原子，1 是原子，2 也是原子。

原子就是不包含空格的符号，可以是字符，也可以是数字。比如，下面的这个表里，有两个原子。

'(hello world)

这两个原子分别是 hello 和 world。

其实，上面的那个式子，也是 LISP 语言中的 hello world 程序。很简单，对吧。不过别忘记括号前面的单引号，否则会报错。

表里不仅可以包含原子，也可以包含另一个表。举个例子：

(or (> 3 4) (> 4 2))

在上表中，or是原子，而 (> 3 4) 、(> 4 2) 都是表，不是原子。当然了，这两个小表里，包含的东西都是元素。

也就是说：表是可以嵌套的。

表的大小并没有限制，最小的表就是空表：

()

### 程序和数据 ###

编程这项工作，是在写一个程序，而写程序的目的是为了处理数据。程序与数据是编程中的两大要素，而在 Lisp 中，这两者都用 **表** 来表示。

如果你在解译器中输入一个表，那么Lisp会对这个表求值。所以在解释器中输入

(+ 1 2)

会打印3。

说明这个表的值是3。

我们再看一个例子：

(1 2 3)

如果你在解释器中输入上面的表达式，会得到一个错误：Error: 1 is invalid as a function. 意思是1不是一个可用函数。

在所有的表中，第一个原子总是函数，代表操作、指令、命令。而之后原子（或表）是参数，意即对操作的说明。所以 (+ 1 2) 表示 1 + 2，而 (- 4 3) 表示 4 -3。

例外是这个

()

这是一个空表，会返回

NIL

NIL是一个原子，表示逻辑假，但它同时也是空表。它是LISP语言中唯一一个既是表又是原子的东西。

程序是表，那数据该如何表示？ 数据也是用表来表示。

Lisp会对所有的表求值，但如果我们想使用表本身（作为数据），这反而会成为一件麻烦事。只要用一个简单的操作符就可以防止求值，那就是 ' 操作符（单引号）。

'(+ 1 2)

这次解译器不对这个表其求值了，结果不再是3这个原子，而是一个表，原封未动的表。

(+ 1 2)

还记得我们的 hello world 程序吗?

'(Hello world!)

会返回

(HELLO WORLD!)

各种程序语言的入门书籍都喜欢一个hello, world程序。在此郑重告诉大家， Lisp 也有自己的 Hello，world！

上面我们输入的是小写的字母，输出的却是大写的字母。这是因为在 Lisp 中大小写无所谓。

不过 ' 这个东西其实只是一个语法糖（为了让程序员少打几个字符而创造的语法）。它其实是一种简写，全称是quote操作，意思是引用。上面的hello world 程序如果写全了，就是：

(quote (Hello world!))

### CAR 操作符 ###

CAR操作符的作用是取出表的第一个元素。

(car '(1 2 3 4 5))

上表会返回 1。

CAR操作符的作用是取出表的第一个元素，注意，我说的是元素不是原子，所以car的返回值也可能是个表。

让我们来试试

(car '((1 2) 3))

返回的值就是一个表。CAR 的作用就是取出第一个元素，至于第一个元素是表还是原子，它并不关心。

不过，CAR 这个名称真的是很古老了，我们可以用 first 操作符来替代它。实际上，first 是 CAR 的别名。

注意到，我们上面的代码在参数表是由一个单引号（引用操作）引导的。这是非常重要的。如果我们去掉单引号。

(car (1 2 3 4 5))

系统将会报错： error: 1不是可用的函数

如果大家还记得我们之前的报错，就会知道，这是因为系统试图执行内表中的代码。是的，在 LISP 中，表就是程序。 如果没有特殊说明系统会对一切看得到的表求值。所以，我们要加上单引号，表示想要以数据的形式使用这个表。

还有一个事情是值得注意的，CAR 操作只对表管用，不可以把它用在原子上。比如：

(car 1)

系统会返回错误： error: 1不是“表”类型

### CDR 操作符 ###

CDR 操作符和 CAR 的作用是相反的，它的作用是去除表的第一个元素。

(cdr '(1 2 3 4 5))

上面表达式的返回值是

(2 3 4 5)

CDR 总是返回一个表。它的意义，就是取出表中除了第一个元素之外的所有元素，然后返回这些元素组成的表。

CDR 的别名是 rest，这也是非常形象的名字，意思是其余，即除了第一个以外的其余。

我们可以用CDR操作符取出函数的参数，比如

(cdr '(+ 1 2 3))

这行代码可以取出(+ 1 2 3)的参数(1 2 3)。

如果表中只有一个元素，那么对这个表进行 CDR 操作，将会发生什么事情呢？让我们来试验一下：

(cdr '(1))

将会返回 NIL。不要忘记，NIL 也代表一个空表。所以，上面的表达式返回的其实是一个空表。

通过了解 CAR 和 CDR操作符，你会有种感觉，第一个元素竟然和其他所有元素平等。是的，这确实是 LISP 的世界观，至于为什么，你读下去就会知道。

### CXR 组合操作符 ###

问你一个问题，**如何取出第二个元素？**

先不要急着往下看，好好想想。

我们至今只接触了两个运算符，一个是CAR，可以取出第一个，另一个是CDR，可以取出其余的。那么如何用这两个运算符取出第二个元素呢？

答案在下面：

(car (cdr '(1 2 3)))

第二个元素就是去掉第一个元素之后的第一个元素。我们先用CDR取出除第一个元素外的其他元素（本质上就是去掉了第一个元素），然后就可以在这个新表中取出第一个元素了，这样，我们得到的就是原表的第二个元素。

哇，聪明如你，是不是悟到了一种方法，可以取任何第几个元素。

那思考一下如何取第三个元素吧，写出来，在解译器上试验一下吧

恭喜你，你的第一个原创Lisp代码实现了。如果还没实现，那么恭喜你，下面是代码：

(car (cdr (cdr '(1 2 3))))

实际上，LISP 中由专门的操作符来表示这些操作，比如 CADR

试试下面的代码：

(cadr '(1 2 3))

你也可以自己寻找更多类似的操作符。

## 第三章 构造表 ##

### CONS 操作符 ###

我们刚刚学习了如何拆分一个表，现在学习如何合并一个表。 CONS 操作符就是做这件事情的。

假设有一个列表 (1 2 3) ，我们做一下 CAR 操作：

(car '(1 2 3))

返回 1 。

我们再做一下 CDR 操作：

(cdr '(1 2 3))

返回 (2 3) 。

CONS 操作符的作用就是将拆开的表连起来。

(cons 1 '(2 3))

返回的将是原来的列表 (1 2 3) 。

### S 表达式 ###

cons 操作符的第二个参数要是一个列表，才能返回一个列表。否则：

(cons 2 3)

(2 . 3)

这次中间有一个点。为什么呢？

因为，表实际上是一个树（二叉树）。我们上面所用到的带括号的式子被称为 S表达式。而在S表达式中， 二叉树在表示为 (Left . Right) 。

如果左支是一个表，则就会成为如下形式。

((List) . Right)

如果右支是一个表，当然也可以表示为 (Left . (List)) ，但是此时我们一般把点省略掉，写成

(Left List)

你现在可能有些晕，用一段表达式表示就很清晰了，如下

'(3 . (2 3))

(3 2 3)

CONS操作符的作用是将两棵树连接成一棵树。

那么现在你能回答为什么CDR操作符会取出除第一个外的所有元素了吗，因为它的实质是取二叉树的右支。

总之CONS操作符的作用是连接一个元素与一个表（顺序不可颠倒）。

(cons 2 '(2 3))

(2 2 3)

如果要连接三个或以上的元素，要这样

(cons 1 (cons 2 '(3)))

(1 2 3)

真正有点实质性的是这个式子

(cons 1 (cons 2 (cons 3 nil))) ;;; (1 2 3)
    
    (cons 3 nil) ;;; (3)

如果二叉树的右支是NIL，那么连NIL都省略掉。如

'(3 . Nil) ;;; (3)

一件有趣的事情是这样

(cdr '(3)) ;;; NIL

### append 函数\[[编辑][Link 2]\] ###

append函数的作用是连接两个表。

>(append '(3 3) '(4 4))
    
    (3 3 4 4)

形象点说，它会把最外一层括号去掉，然后连接。比如

>(append '((3)) '(4 4))
    
    ((3) 4 4)

### LIST 函数 ###

LIST 函数的意义是将所有的参数放入一个表中并返回之。

>(list 1 1 1 1)
    
    (1 1 1 1)
    
    >(list '(2 3) '(2) 1 2)
    
    ((2 3) (2) 1 2)

## 第四章 原子和值 ##

### 再讲原子 ###

这次，我们愿意详细讲解原子

原子可以是任何数，分数，小数，自然数，负数等等。

原子可以是一个字母排列，当然其中可以夹杂数字和符号。

空表就是原子NIL。

在 LISP 解释器中输入引用符（单引号）紧接着输入一个原子，可以返回这个原子本身，就像对列表的操作一样。比如：

'sdf

会返回 SDF。

SDF 是一个普通的原子。像

*  sd2f
 *  SDF+
 *  SDF\*
 *  SDF.

都是普通的原子。

但原子中还是不能包含一些特殊字符的，比如逗号：*sdf,* 。这个会返回错误 Error: A comma has appered out of a backquote. 含义是，逗号出现在了单引号之外。

### ATOM运算符 ###

判断一个字符序列是不是原子，或者甚至一个元素是不是原子，我们用ATOM运算符。

(atom 'a)
    (atom '(3))

上面的第一个表达式返回 T，因为 a 是一个原子。而第二个表达式则返回 NIL，因为 *(3)* 是一个列表。 换言之， ATOM运算符在参数为原子时返回真，在参数为一个表时或参数构不成原子时返回假。

### SETQ运算符 ###

首先来看一下

>1
    
    1
    
    >a
    
    Error: The variable A is unbound

很好，我们说过，解译器的功能就是对一个输入的表达式求值而已。1的值自然是1，然而a的值呢，错误说变量A的值还未经绑定。绑定的意思就是类c语言中的赋值。

如何绑定一个变量呢，如下

>(setq a 5)
    
    5

然后，我们再次输入a，情形就不同了。

>a
    
    5

不过，你肯定对输入(setq a 5)之后有一个5出现迷惑不解，setq运算符的意义就是赋值并且将此值返回。就是说，表达式(setq a 5)的值是5 。

我们可以接着

>(setq a 6)
    
    6
    
    >a
    
    6

再然后，我们可以

>(cons a '(3))
    
    (6 3)

现在这样也是可以的：

>(setq a 'b)
    
    B
    
    >(cons a '(3))
    
    (B 3)
    
    >(setq a '(1 2 3))
    
    (1 2 3)
    
    >(cdr a)
    
    (2 3)

##     ##

## 第五章 断言函数 ##

### ATOM 函数 ###

前面已经讲过了，用来判断一个表达式是不是原子

>(atom (+ 1 1))
    
    T
    
    >(atom '(3))
    
    NIL

因为2是原子，而（3）是个表。

### NULL 函数 ###

NULL函数用来判断表达式的值是不是NIL。

>(null nil)
    
    T
    
    >(null (car '(3)))
    
    NIL

### EQUAL 函数 ###

用来判断两个表达式的值是否完全相等

>(equal 's 's)
    
    T
    
    >(equal '(s) '(s))
    
    T

## 第六章 自己定义函数 ##

### DEFUN 操作符 ###

DEFUN操作符用来自定义函数，形式如下

(defun 函数名原子 参数名列表 执行列表)

比如

(defun 2nd (x)
      (car (cdr x))
    )

这样，我们就定义了一个函数，就像我们之前接触的很多操作符一样。这个函数的名称是 2nd，而它的作用就是 返回一个列表的第二个元素。

这个函数的名称后面是一个列表 (x) ，表示这个函数只接受一个x作为参数。紧接着是另一个列表 (car (cdr x))，表示这个函数作用于 x 身上就如同这个表达式的作用一样，返回值也是这个表达式作用于 x 之后的值。

让我们应用一下这个元素。

(2nd '(1 2 3))

会返回 2

函数的定义式中，有个x，是函数的参数，上面的这个函数的执行过程就相当于

(car (cdr '(1 2 3)))

### 参数 ###

参数就是我们第一个定义中的x，参数的个数是没有限制的。比如

(defun lianjie (x y)
      (append x y)
    )

这个函数的作用是连接两个表，因为它执行的是append函数。

### 系统自带的函数 ###

系统自带了很多函数，比如下面这两个函数：

#### First函数 ####

(first '(1 2 3))

返回参数列表的第一个所组成的值。

#### Last函数 ####

(last '(1 2 3))

（3）

没错，last函数的作用就是返回参数列表的最后一个所组成的表。注意，返回的是一个列表而不是一个原子。

### 第一个自定义函数 ###

我们将要定义一个函数 ends，它的作用是返回参数列表的头尾两个元素组成的列表。

如何实现呢，我们首先取出参数列表的第一个元素，然后取出最后一个元素，再将两者连在一起就行了。这要用到我们之前提到的 first 函数和 last 函数。

(defun ends (x) 
      (cons (first x) (last x))
    )

这样，我们就定义完成了这个函数。分析一下定义体中的 (cons (first x) (last x)) 这是要连接两个元素，第一个元素是 x 的第一个元素，第二个元素是 last 函数所取出的表。其结果自然就是x的头和尾两个元素所组成的列表。

我们来试验一下：

(ends '(1 2 3))

(1 3)

上面的这个例子中，关键的一步相当于 *(cons 1 '(3))* 。

## 第七章 条件操作符 ##

Cond 操作符

Cond操作符有些复杂。 它的形式为

(cond 分支列表1 分支列表2 分支列表3 ... 分支列表N)

而其中分支列表的构成为 (条件p 值e)

Cond 操作符将对每一个“条件p”求值，如果为NIL，就接着求下一个，如果为真，就返回相应的“值e”，如果没有一个真值，cond操作符返回nil。Cond操作符的参数可以不止两个。

(cond (nil 1) (nil 2) (t 3))

(cond (t 1) (nil 2) (t 3))

有了cond操作符，我们就相当于拥有了类c语言中的if语句。

现在我们将编一个函数，返回两个数种的最大值。

在编写之前，我们要知道，系统已经给我们提供了一个函数，那就是max 。所以我们的函数名字就叫max2。

(defun max2 (a b) (cond ((> a b) a) (t b)))
    
    (max2 2 3)

有了cond操作符，我们就相当于拥有了类c语言中的if语句。当然，cond语句比c中的if语句更强大，同时也更难用。在common Lisp中，已经有一个函数if了，它的形式如下 (if 判断表达式 真值时的返回值 假值时的返回值)

### 两个例子 ###

现在我们将编一个函数，返回两个数中的最大值。

在编写之前，我们要知道，系统已经给我们提供了一个函数，那就是max 。所以我们的函数名字就叫max2，以示区别。

我们依次输入以下代码：

>(defun max2 (a b) (cond ((> a b) a) (t b)))
    
    MAX2
    
    >(max2 2 3)
    
    3

Max2的行为分析：当参数a大于参数b时，返回a，如果不满足此条件，那么就一定要返回b。

所以，我们的条件是a和b的大小比较，如果为真，则返回a，否则，一定返回b。

当然，这个函数，我们也可以用if函数构造。构造如下：

(defun max2 (a b)
      (if (> a b) a b)
    )

我们还可以定义一个求绝对值的函数。

当然，这个函数系统本身也提供。这个函数的行为如下：

>(abs -3)
    
    3

该如何构造呢，显然，当参数大于0是返回本身，当参数小于0时返回它的相反数。

>(defun abs2 (x) (cond ((> x 0) x) (t (- 0 x))))
    
    ABS2
    
    >(abs2 -3)
    
    3

其中，(- 0 x)表示的意思是 0-x，也就是x的相反数。

## 第八章 递归函数 ##

一个小递归函数

大家还记得数学上的递归定义么？

我们所知的最简单的定义就是等差数列。

an=an-1\+d

我们有一个最简单的数列

0 2 4 6 8 10 ...

怎么表示呢，应该这样

an=an-1\+2，其中a1=0

那么其定义就是 (defun dseq (n) (+ (dseq (- n 1)) 2))。注意，不要立刻输进去，因为这是一个错误的式子，先看懂它再说。

它的错误在哪里呢？如果dseq函数要求(dseq 3)，它就会先去求(dseq 2)，然后会再去求(dseq 1)，再是(dseq 0)，再是(dseq -1)，以至无穷。它的错误就在于它不会停止。

这样的话，我们需要用到条件句。

完整的定义如下：

>(defun dseq (x) (cond ((= x 1) 0) (t (+ (dseq (- x 1)) 2))))
    
    DSEQ
    >(dseq 1)
    
    0
    >(dseq 2)
    
    2
    >(dseq 4)
    
    6
    >(dseq 999)
    
    1996

后面的验证也说明它是正确的。

### trace函数 ###

下面一个函数len用来计算一个表x的长（即元素个数）度。

>(defun len (x) (cond ((null x) 0) (t (+ (len (cdr x)) 1))))

递归式是(len (cdr x)) ，终结条件是(null x)为真。

我们输入

>(len '(a b c d))
    
    4

Trace函数用来跟踪函数调用的情况

>(trace len)
    (LEN)
    >(len '(a b c d))

看看吧，会有很形象的东西出现

# 第九章 七大公理 #

Lisp有7个基本操作符（实际上或许可以再精简）。这7个基本操作符就像几何中的公理一样，任何其他函数都可以由这七大公理定义。也就是说，7个基本操作符包含了Lisp的所有语义。

这7个基本操作符是：

1.  Quote
2.  Atom
3.  Eq
4.  Car
5.  Cdr
6.  Cons
7.  Cond

在下一章中，我们会定义几个小例子，讲解如何用这7个函数构建一些其他的基本函数。

# 第十章 小例子 #

从一到八章，我们讲解了许多函数，有好多不是公理，我们来一一实现它们（以及一些新的函数）。

这些函数系统都有提供，我们重新发明一遍轮子。这些轮子的简单程度可以说是令人发指。

### NULL函数 ###

NULL函数用于检测表是否为空，或者元素是否为nil。

(defun null2 (x) (cond ((equal x nil) t) (t nil)))

解释：如果参数与nil相等，就返回t，否则返回nil。这和逻辑学上的not函数是一致的（但null函数的应用范围更广，因为它可以应用于表）。

### And函数 ###

>(defun and2 (x y) (cond ((equal x nil) nil) ((not (equal y nil)) t) (t nil)))

### Or函数 ###

>(defun or2 (x y) (cond ((equal x t) t) ((equal y t) t)))

### Last 函数的表示 ###

>(defun last2 (x) (cond ((equal (cdr x) nil) x) (t (last2 (cdr x)))))

### Length函数的表示 ###

下面讲如何计算一个表x的长（即元素个数）度。

>(defun len (x) (cond ((null x) 0) (t (+ (len (cdr x)) 1))))

递归式是(len (cdr x)) ，终结条件是(null x)为真。

### Append函数的表示 ###

设参数形式是x和y。很容易分析出来，递归式是(cons (car x) (append2 (cdr x) y))，终结条件是当x为NIL时，返回y。

>(defun append2 (x y) (cond ((eq x nil) y) (t (cons (car x) (append2 (cdr x) y)))))

### Equal函数的表示 ###

设参数形式是x和y。很容易分析出来，递归式是(equal (cdr x) (cdr y))，递归条件是(equal (car x) (car y))，终止条件是(equal (cdr x) nil)或者(equal (cdr y) nil)或者((atom x) (equal x y))

(defun equal2 (x y) 
      (cond 
        ((null x) (not y))
        ((null y) (not x))
        ((atom x) (eq x y))
        ((atom y) (eq x y))
        ((not (equal2  (car x) (car y))) nil)
        (t (equal2 (cdr x) (cdr y)))
      )
    )

代码解释：

((null x) (not y))

首先，如果x为空，说明遇到了x列表的末尾，这时检测y列表是否也到了，如果到了（此时我们知道之前的元素都相等），那么返回真，否则返回假。

((null y) (not x))

如果y到了末尾，一样处理。

((atom x) (eq x y))

如果x是一个原子，说明函数是从(equal2 (car x) (car y))字句进入的，且(car x)的结果为原子。这时函数就可以结束了，返回x=y的结果。

((atom y) (eq x y))

如果y是一个原子，说明函数是从(equal2 (car x) (car y))字句进入的，且(car y)的结果为原子。这时函数就可以结束了，返回x=y的结果。

(t (equal2 (cdr x) (cdr y)))

否则的情况，我们就递归。

总结，大家可以发现，其实这个函数的递归路径有两个。

### If函数的表示 ###

用cond可以实现if函数。实际上，在类c语言中，if语句强调的是程序的走向，但在Lisp中，程序的走向可以忽略（从某种意义上），而强调的是返回值。

>(defun if2 (p e1 e2)
     (cond (p e1) (t e2))
     )
    
    IF2

\--需要一个while实现的例子。

[Link 1]: https://zh.wikibooks.org/w/index.php?title=%E4%BA%BA%E5%B7%A5%E6%99%BA%E8%83%BD&action=edit&redlink=1
[1]: https://zh.wikibooks.org/wiki/Lisp_%E5%85%A5%E9%96%80/%E5%BA%8F%E7%AB%A0_%E5%A6%82%E4%BD%95%E5%BC%80%E5%A7%8B#cite_note-aiid-1
[displaystyle f_x]: https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074
[displaystyle z_f_x_y]: https://wikimedia.org/api/rest_v1/media/math/render/svg/1eefb2840000f404c8c0f3f5d6d72f2624854591
[Link 2]: https://zh.wikibooks.org/w/index.php?title=Lisp_%E5%85%A5%E9%96%80/%E7%AC%AC%E4%B8%89%E7%AB%A0_%E6%A7%8B%E9%80%A0%E8%A1%A8&action=edit&section=4