第 2 章 函数
最后更新于：2022-04-01 02:44:59
## 第 2 章 函数
函数不仅是 Lisp 程序的根基，它同时也是 Lisp 语言的基石。在多数语言里，'+' (加法) 操作符都和用户自定义的函数多少有些不一样。但 Lisp 采用了函数应用作为其统一模型，来描述程序能完成的所有计算。
在Lisp 里，'+' 和你自己定义的函数一样，也是个函数。
事实上，除了少数称为*特殊形式*（special form）的操作符之外， Lisp 的核心就是一个函数的集合。有什么可以阻止你给这个集合添砖加瓦呢？答案是:
> 没有
如果你觉得某件事 Lisp 应该能做，那你完全可以把它写出来，然后你的新函数可以享有和内置函数同等的待遇。
这对程序员产生了深远的影响。它意味着，或可以把任何一个新加入的函数都看作是对Lisp 语言的扩充，也可以把它当成特定应用的一部分。典型情况是，有经验的Lisp 程序员两边都写一些，并不断调整语言和应用之间的界限，直到它们彼此完美地配合在一起。本书要讲述的正是如何在语言和应用之间达到最佳的结合点。由于我们向这一最终目标迈进的每一步都依赖于函数，所以自然应该先从函数开始。
### 2.1 作为数据的函数
有两点让 Lisp 函数与众不同。一是前面提到的:
> Lisp 本身就是函数的集合。
这意味着我们可以自己给 Lisp 增加新的操作符。另一个关于函数的重要问题，是要了解：
> 函数也是 Lisp 的对象。
Lisp 提供了其他语言拥有的大多数数据类型。我们有整数和浮点数、字符串、数组、结构体等等。但 Lisp 还支持一种乍看之下让人奇怪的数据类型：函数。几乎所有编程语言都提供某种形式的函数或过程。那么，说 "Lisp 把函数作为一种数据类型提供出来" 又是什么意思呢？这意味着在 Lisp 里我们可以像对待其他熟悉的数据类型那样来对待函数，就像整数那样：在运行期创建一个新函数，把函数保存在变量和结构体里面，把它作为参数传给其他函数，还有把它作为函数的返回值。
这种在运行期创建和返回函数的能力特别有用。这个优点可能初看起来还让人心存疑虑，就好像那些可以在某些计算机上运行的可以修改自身的机器语言程序一样。但对于 Lisp 来说，在运行期创建新函数的技术简直就是家常便饭。
### 2.2 定义函数
多数人的学习会从 "用 defun 创建函数" 开始。下面的表达式定义了一个叫 double 的函数，其返回值是传入参数的两倍。
~~~
> (defun double (x) (* x 2))
DOUBLE
~~~
如果把上述定义送入 Lisp ，我们就可以在其他函数里调用 double ，或者从最顶层(toplevel) 调用：
~~~
> (double 1)
2
~~~
Lisp 的源代码文件通常主要由类似这样的函数定义组成，这有几分类似 C 或者 Pascal 这些语言中的过程定义。但接下来就大不一样了。这些 defun 并不只是过程定义，它们还是 Lisp 调用。在我们了解了 defun 背后的运作机制后，这种区别会更明显。
同时，函数本身也是对象。defun 实际所做的就是构造这样的对象，然后把它保存在第一个参数名下。因此我们既可以调用 double ，也可以持有这个名字对应的函数对象。要得到这个对象，通常的做法是使用 #' (井号 + 单引号) 操作符。这个操作符的作用可以理解成：它能将名字映射到实际的函数对象。把它放到double 的前面：
~~~
> #'double
#<Interpreted-Function C66ACE>
~~~
我们就有了上面定义所创建的实际对象。尽管它的输出形式在不同的Lisp 实现中各不相同，但 Common Lisp 的函数是第一类(first-class) 对象，它和整数和字符串这些更熟悉的对象享有完全相同的权利。所以，我们既可以把这个函数作为参数传递，也可以把它作为返回值返回，还能把它存在数据结构里，等等：
~~~
> (eq #'double (car (list #'double)))
T
~~~
甚至可以不用 defun 来定义函数。和大多数 Lisp 对象一样，我们也可以通过其文字表达的形式来引用它。
就像当我们提到一个整数时，只要使用这个数字本身那样。而表示字符串时，用括在两个双引号之间的一
系列字符。如果要表达的是一个函数，我们可以使用一种称为–表达式(lambda-expression) 的东西。–表达式是一个由三个部分组成的列表：lambda 符号、参数列表，以及包含零个以上表达式的主体。下面这个–表达式相当于一个和double 等价的函数：
~~~
(lambda (x) (* x 2))
~~~
它描述了一个函数，函数的参数是 ，并且返回 。–表达式也可以看作是函数的名字。如果说double 是个正规的名字，就像 "米开朗琪罗"，那么 (lambda (x) (* x 2)) 就相当于具体的描述，比如 "完成西斯庭大教堂穹顶壁画的人" 。通过把一个井号和引号 "#" 放在表达式的前面，我们就得到了相应的函数：
~~~
> #'(lambda (x) (* x 2))
#<Interpreted-Function C674CE>
~~~
这个函数和 double 的表现相同，但它们是两个不同的对象。
在函数调用中，函数名出现在前面，接下来是参数：
~~~
> (double 3)
6
~~~
由于–表达式同时也是函数的名字，因而它也可以出现在函数调用的最前面：
~~~
> ((lambda (x) (* x 2)) 3)
6
~~~
在 Common Lisp 里，我们可以同时拥有名为double 的函数和变量。
~~~
> (setq double 2)
2
> (double double)
4
~~~
当名字出现在函数调用的首位，或者前置 #' 的时候，它被认为是函数。其他场合下它被当成变量名。
因此我们说 Common Lisp 拥有独立的函数和变量名字空间 (name-space)。我们可以同时有一个叫 foo 的变量以及一个叫 foo 的函数，而且它们不必相同。这种情形可能会让人不解，并且可能在一定程度上影响代码的可读性，但这是 Common Lisp 程序员必须面对的问题。
Common Lisp 还提供了两个函数用于将符号映射到它所代表的函数或者变量，以备不时之需。symbol-value 函数以一个符号为参数，返回对应变量的值：
译者注：拥有分开的变量和函数命名空间的 Lisp 称为 Lisp-2，在另一类 Lisp-1 下，变量和函数定义在同一命名空间里，最著名的
这种 Lisp 方言是 Scheme。关于 Lisp-1 vs. Lisp-2 在网上有很多讨论，一般观点认为 Lisp-1 对于编译器来说更难实现。
~~~
> (symbol-value 'double)
2
~~~
而 symbol-function 则用来得到一个全局定义的函数：
~~~
> (symbol-function 'double)
#<Interpreted-Function C66ACE>
~~~
注意到，由于函数也是普通的对象，所以变量也可以把函数作为它的值：
~~~
> (setq x #'append)
#<Compiled-Function 46B4BE>
> (eq (symbol-value 'x) (symbol-function 'append))
T
~~~
深入分析的话，defun 实际上是把它第一个参数的 symbol-function 设置成了用它其余部分构造的函数。
下面两个表达式完成的功能基本相同：
~~~
(defun double (x) (* x 2))
(setf (symbol-function 'double)
#'(lambda (x) (* x 2)))
~~~
所以，defun 和其它语言的过程定义的效果相同， 把一个名字和一段代码关联起来。但是内部机制完全不一样。我们可以不用defun 来创建函数，函数也不一定要保存在某个符号的值里面。和任何语言里定义过程的方法一样，defun 的内部实现使用的也是一种更通用的机制：构造一个函数，然后把它和某个名字关联起来，这两步其实是两个独立的操作。当我们不需要利用Lisp 中所谓函数所有的通用性时，用 defun 来生成函数就和在其他限制更多的语言里定义函数一样的简单。
### 2.3 函数型参数
函数同为数据对象，就意味着我们可以像对待其他对象那样把它传递给其他函数。这种性质对于Lisp 这种自底向上程序设计至关重要。
如果一门语言把函数作为数据对象，那么它必然也会提供某种方式让我们能调用它们。在Lisp 里，这个函数就是apply。一般而言，我们用两个参数来调用apply ：函数和它的参数列表。下列四个表达式的效果是一样的：
~~~
(+ 1 2)
(apply #'+ '(1 2))
(apply (symbol-function '+) '(1 2))
(apply #'(lambda (x y) (+ x y)) '(1 2))
~~~
在Common Lisp 里，apply 可以带任意数量的参数。其中，最前面给出的函数将被应用到一个列表，该列表由其余参数cons 到最后一个参数产生，而最后的参数也是个列表。所以表达式
~~~
(apply #'+ 1 '(2))
~~~
和前面四个表达式等价。如果不方便以列表的形式提供参数，可以使用funcall ，它和apply 唯一的区别也在于此。表达式
~~~
(funcall #'+ 1 2)
~~~
和上面的那些表达式效果相同。
很多内置的Common Lisp 函数都可以把函数作为参数。这些内置函数中，最常用的是映射类的函数。例如 mapcar 带有两个以上参数 一个函数加上一个以上的列表(每个列表都分别是函数的参数)，然后它可以将参数里的函数依次作用在每个列表的元素上：
~~~
> (mapcar #'(lambda (x) (+ x 10))
'(1 2 3))
(11 12 13)
> (mapcar #'+
'(1 2 3)
'(10 100 1000))
(11 102 1003)
~~~
Lisp 程序经常需要对列表中的每一项都做一些操作，然后再把结果同样以列表的形式返回。上面的第一个例子介绍的步骤，就是用来完成这个工作的常用办法：生成一个你所需功能的函数，然后用 mapcar 把它映射到列表上。
我们已经了解到，"把函数当作数据来使用" 的能力给编程带来了极大的便利。在许多语言里，即便我们可以像 mapcar 那样把函数作为参数传递进去，那也只能是事先在代码中定义好的函数。如果只有一小段代码需要把列表中的每项都加上10，我们就只得专门定义一个叫plus_ten 或者类似名字的函数，而这个函数只是在这段代码中才会用到。有了–表达式，就可以直接表达函数了。
Common Lisp 和它以前方言之间一个最大的区别就是它拥有大量使用函数型参数的内置函数。其中，除了随处可见的mapcar ，还有两个最常用的函数就是sort 和 remove-if 。前者是通用的排序函数。它接受一个列表和一个谓词，然后使用这个谓词，对原列表中的元素两两进行比较，并返回所得排序后的列表。
~~~
> (sort '(1 4 2 5 6 7 3) #'<)
(1 2 3 4 5 6 7)
~~~
有种办法可以帮助记忆sort 函数工作方式，如果你用 排序一个没有重复元素的列表，那么当你把 应用到结果列表的时候，它将会返回真。
假使Common Lisp 里没有remove-if 函数的话，那它就应该是你写的第一个工具。它接受一个函数和列表，并且返回这个列表中所有调用那个函数返回假的元素。
~~~
> (remove-if #'evenp '(1 2 3 4 5 6 7))
(1 3 5 7)
~~~
作为把函数作为参数的函数示例，这里给出一个remove-if 的受限版本：
~~~
(defun our-remove-if (fn lst)
(if (null lst)
nil
(if (funcall fn (car lst))
(our-remove-if fn (cdr lst))
(cons (car lst) (our-remove-if fn (cdr lst))))))
~~~
注意到在这个定义里fn 并没有前缀#' 。因为函数就是数据对象，变量可以将一个函数作为它的正规值。
这就是事情的来龙去脉。#' 仅用来引用那些以符号命名的函数 通常是用defun 全局定义的。
正如第4 章将要展示的那样，编写那种接受函数作为参数的新工具是自下而上程序设计的重要环节。
Common Lisp 自带了大量的工具函数，很多你想要的可能已经有了。但无论是使用内置的工具，比如sort ， 还是编写你的实用工具，基本原则是一样的：与其把功能写死，不如传进去一个函数参数。
### 2.4 作为属性的函数
函数作为Lisp 对象这一事实也创造了条件，让我们能够编写出那种可以随时扩展以满足新需求的程序。
假设我们需要写一个以动物种类作为参数并产生相应行为的函数。在大多数语言中，会使用case 语句达到这个目的，Lisp 里也可以用同样的办法：
~~~
(defun behave (animal)
(case animal
~~~
译者注：即 (apply #'< '(1 2 3 4 5 6 7)) T 。
~~~
(dog (wag-tail)
(bark))
(rat (scurry)
(squeak))
(cat (rub-legs)
(scratch-carpet))))
~~~
如果要增加一种新动物该怎么办呢？如果计划增加新的动物，那么把behave 定义成下面的样子可能会更好一些：
~~~
(defun behave (animal)
(funcall (get animal 'behavior)))
~~~
同时把每种个体动物的行为以单独的函数形式保存，例如，存放在以它们名字命名的属性列表里：
~~~
(setf (get 'dog 'behavior)
#'(lambda ()
(wag-tail)
(bark)))
~~~
用这种方式处理的话，要增加一种新动物，所有你需要做的事情就是定义一个新的属性。一个函数都不用重写。
上述第二种方法尽管更灵活，但看上去要慢些。实际上也是如此。如果速度很关键，我们可以把属性表换成结构体，而且特别要用编译过的函数代替解释性的函数。(第2.9 节解释了怎样做到这些。) 使用了结构体和编译函数，上面的代码就会灵活，而且其速度可以达到甚至超过那些使用case 语句的实现。
这样使用函数相当于面向对象编程中的方法概念。总的来说，方法是作为对象属性的一种函数，这也正是
我们手里有的。如果把继承引入这个模型，你就得到了面向对象编程的全部要素。第25 章将用少得惊人的代码来说明这一点。
面向对象编程的一大亮点是它能让程序可扩展。这一点在Lisp 界激起的反响要小很多，因为在这里，人们早已把可扩展性当成理所当然的事情了。如果我们要的可扩展性不是很依赖继承，那么纯Lisp 可能就已经足够应付了。
### 2.5 作用域
Common Lisp 是一种词法作用域(lexically scope) 的Lisp。Scheme 是最早的有词法作用域的方言；在它之前，动态作用域(dynamicscope) 被视为Lisp 的本质属性之一。
词法作用域和动态作用域的区别在于语言处理自由变量的方式不同。当一个符号被用来表达变量时，我们称这个符号在表达式中是被绑定的(bound)，这里的变量可以是参数，也可以是来自像let 和do 这样的变量绑定操作符。如果符号不受到约束，就认为它是自由的。下面的例子具体说明了作用域：
~~~
(let ((y 7))
(defun scope-test (x)
(list x y)))
~~~
在函数表达式里，x 是受约束的，而y 是自由的。自由变量有意思的地方就在于，这种变量应有的值并不那么显而易见。一个约束变量的值是确信无疑的 当调用scope-test 时，x 的值就是通过参数传给它的值。但y 的值应该是什么呢？这要看具体方言的作用域规则。
在动态作用域的Lisp 里，要想找出当scope-test 执行时自由变量的值，我们要往回逐个检查函数的调用链。当发现y 被绑定时，这个被绑定的值即被用在scope-test 中。如果没有发现，那就取y 的全局值。这样，在用动态作用域的Lisp 里，在调用的时候y 将会产生这样的值：
~~~
> (let ((y 5))
(scope-test 3))
(3 5)
~~~
如果是动态作用域，那么在定义 scope-test 时，把y 绑定到7 就没有任何意义了。调用 scope-test 时，y 只有一个值，就是 5。
在词法作用域的 Lisp 里，我们不再往回逐个检查函数的调用链，而是逐层检查定义这个函数时，它所处的各层外部环境。在一个词法作用域Lisp 里，我们的示例将捕捉到定义scope-test 时，变量y 的绑定。所以可以在 Common Lisp 里观察到下面的现象：
~~~
> (let ((y 5))
(scope-test 3))
(3 7)
~~~
这里将y 绑定到5。这样做对函数调用的返回值不会有丝毫影响。
尽管你仍然可以通过将变量声明为special 来得到动态作用域，但是词法作用域是Common Lisp 的默认行为。总的来说，Lisp 社区对昨日黄花的动态作用域几乎没什么留恋。因为它经常会导致痛苦而又难以捉摸的bug。而词法作用域不仅仅是一种避免错误的手段。在下一章我们会看到，它同时也带来了一些崭新的编程技术。
### 2.6 闭包
由于Common Lisp 是词法作用域的，所以如果定义含有自由变量的函数，系统就必须在函数定义时保存那些变量的绑定。这种函数和一组变量绑定的组合称为闭包。我们发现，闭包在各种场合都能大显身手。
闭包在 Common Lisp 程序中如此无所不在，以至于你可能已经用了它却浑然不知。每当你传给 mapcar 一
个包含自由变量的前缀#' 的–表达式时，你就在使用闭包。例如，假设我们想写一个函数，它接受一个数列并且给每个数加上相同的数字。这个list+ 函数
~~~
(defun list+ (lst n)
(mapcar #'(lambda (x) (+ x n))
lst))
~~~
将做到我们想要的：
~~~
> (list+ '(1 2 3) 10)
(11 12 13)
~~~
如果仔细观察list+ 里传给mapcar 的那个函数，就可以发现它实际上是个闭包。那个n 是自由的，其绑定来自周围的环境。在词法作用域下，每一次这样使用映射函数都将导致一个闭包的创建。
闭包在 Abelson 和 Sussman 的经典教材《计算机程序的构造和解释》一书中扮演了更加重要的角色。闭包是带有局部状态的函数。使用这种状态最简单的方式是如下的情况：
~~~
(let ((counter 0))
(defun new-id () (incf counter))
(defun reset-id () (setq counter 0)))
~~~
这两个函数共享一个计数器变量。前者返回计数器的下一个值，后者把计数器重置到0。这种方式避免了对计数器变量非预期的引用，尽管同样的功能也可以用一个全局的计数器变量完成。
如果返回的函数能带有局部状态，那么也会很有帮助。例如这个make-adder 函数
~~~
(defun make-adder (n)
#'(lambda (x) (+ x n)))
~~~
接受一个数值参数，然后返回一个闭包，当调用后者时，能够把之前那个数加到它的参数上。我们可以根据需要生成任意数量的这种加法器：
在动态作用域(作为默认作用域) 的情况下，这种表达方式也会一样工作，虽然其原理不同 前提是mapcar 没有一个参数的名字是 "n" 。
~~~
> (setq add2 (make-adder 2)
add10 (make-adder 10))
#<Interpreted-Function BF162E>
> (funcall add2 5)
7
> (funcall add10 3)
13
~~~
在 make-adder 返回的那些闭包里，内部状态都是固定的，但其实也可以生成那种能应要求改变自己状态的闭包。
~~~
(defun make-adderb (n)
#'(lambda (x &optional change)
(if change
(setq n x)
(+ x n))))
~~~
这个新版本的 make-adder 函数返回一个闭包，如果调用它时只传入一个参数，那么其行为和旧版本是一样的。
~~~
> (setq addx (make-adderb 1))
#<Interpreted-Function BF1C66>
> (funcall addx 3)
4
~~~
但是，如果这个新加法器的第二个参数不为空的话，在它内部，n 的拷贝将被设置成第一个参数的值：
~~~
> (funcall addx 100 t)
100
> (funcall addx 3)
103
~~~
甚至有可能返回共享同一数据对象的一组闭包。图2.1 中的函数被用来创建原始数据库。它接受一个关联表(db)，并相应返回一个由查询、追加和删除这三个闭包所组成的列表。
~~~
(defun make-dbms (db)
(list
#'(lambda (key)
(cdr (assoc key db)))
#'(lambda (key val)
(push (cons key val) db)
key)
#'(lambda (key)
(setf db (delete key db :key #'car))
key)))
~~~
图2.1： 一个列表里的三个闭包
每次调用make-dbms 都会创建新的数据库 这个新数据库就是一组新函数，它们把自己的共享拷贝封存在一张关联表(assoc-list) 里面。
~~~
> (setq cities (make-dbms '((boston . us) (paris .france))))
(#<Interpreted-Function 8022E7>
#<Interpreted-Function 802317>
#<Interpreted-Function 802347>)
~~~
数据库里实际的关联表是对外界不可见的，我们甚至不知道它是个关联表 但是可以通过构成 cities 的那些函数访问到它：
~~~
> (funcall (car cities) 'boston)
US
> (funcall (second cities) 'london 'england)
LONDON
> (funcall (car cities) 'london)
ENGLAND
~~~
调用列表的 car 多少有些难看。实际的程序中，函数访问的入口可能隐藏在结构体里。当然也可以设法更简洁地使用它们 数据库可以通过这样的函数间接访问：
~~~
(defun lookup (key db)
(funcall (car db) key))
~~~
无论怎样，这种改进都不会影响到闭包的基本行为。
实际程序中的闭包和数据结构往往比我们在make-adder 和make-dbms 里看到的更加精巧。这里用到的单个共享变量也可以发展成任意数量的变量，每个都可以约束到任意的数据结构上。
闭包是 Lisp 的众多独特和实实在在的优势之一。如果下些工夫的话，还可能把有的 Lisp 程序翻译成能力稍弱的语言，但只要试着去翻译上面那些使用了闭包的程序，你就会明白这种抽象帮我们省去了多少工作。
后续章节将进一步探讨闭包的更多细节。第5 章展示了如何用它们构造复合函数，接着在第6 章里会继续介绍如何用它们替代传统的数据结构。
### 2.7 局部函数
在用–表达式定义函数时，我们就会面对一个使用 defun 时所没有的限制：使用–表达式定义的函数由于它没有名字，因此也就没有办法引用自己。这意味着在 Common Lisp 里，不能用 lambda 定义递归函数。
如果我们想要应用某些函数到一个列表的所有元素上，可以使用最熟悉的Lisp 语句：
~~~
> (mapcar #'(lambda (x) (+ 2 x))
'(2 5 7 3))
(4 7 9 5)
~~~
要是想把递归函数作为第一个参数送给mapcar 呢？如果函数已经用defun 定义了，我们就可以通过名字简单地引用它：
~~~
> (mapcar #'copy-tree '((a b) (c d e)))
((A B) (C D E))
~~~
但现在假设这个函数必须是一个闭包，它从mapcar 所处的环境获得绑定。在我们的list+ 例子里，
~~~
(defun list+ (lst n)
(mapcar #'(lambda (x) (+ x n))
lst))
~~~
mapcar 的第一个参数是 #'(lambda (x) (+ x n)) ，它必须要在list+ 里定义，原因是它需要捕捉n 的绑定。到目前为止都还一切正常，但如果要给mapcar 传递一个函数，而这个函数在需要局部绑定的同时也是递归的呢？我们不能使用一个在其他地方通过defun 定义的函数，因为这需要局部环境的绑定。并且我们也不能使用lambda 来定义一个递归函数，因为这个函数将无法引用其自身。
Common Lisp 提供了labels 帮助我们跳出这个两难的困境。除了在一个重要方面有所保留外，labels 基本可以看作是let 的函数版本。labels 表达式里的每个绑定规范都必须符合如下形式：
~~~
(<name> <parameters> . <body>)
~~~
在labels 表达式里，⟨name⟩ 将指向与下面表达式等价的函数：
~~~
#'(lambda <parameters> . <body>)
~~~
例如，
~~~
> (labels ((inc (x) (1+ x)))
(inc 3))
> 4
~~~
尽管如此，在let 与labels 之间有一个重要的区别。在let 表达式里，变量的值不能依赖于同一个let 里生成的另一个变量 就是说，你不能说
~~~
(let ((x 10) (y x))
y)
~~~
然后认为这个新的 能反映出那个新 的值。相反，在labels 里定义的函数 的函数体里就可以引用那里定义的其他函数，包括 本身，这就使定义递归函数成为可能。
使用labels ，我们就可以写出类似list+ 这样的函数了，但这里 mapcar 的第一个参数是递归函数：
~~~
(defun count-instances (obj lsts)
(labels ((instances-in (lst)
(if (consp lst)
(+ (if (eq (car lst) obj) 1 0)
(instances-in (cdr lst)))
0)))
(mapcar #'instances-in lsts)))
~~~
该函数接受一个对象和一个列表，然后分别统计出该对象在列表的每个元素(作为列表) 中出现的次数，把这些次数组成列表，并返回它：
~~~
> (count-instances 'a '((a b c) (d a r p a) (d a r) (a a)))
(1 2 1 2)
~~~
### 2.8 尾递归
递归函数自己调用自己。如果函数调用自己之后不做其他工作，这种调用就称为尾递归(tail-recursive)。
下面这个函数不是尾递归的
~~~
(defun our-length (lst)
(if (null lst)
0
(1+ (out-length (cdr lst)))))
~~~
因为在从递归调用返回之后，我们又把结果传给了1+。而下面这个函数就是尾递归的⁴
~~~
(defun our-find-if (fn lst)
(if (funcall fn (car lst))
(car lst)
(our-find-if fn (cdr lst))))
~~~
因为通过递归调用得到的值被立即返回了。
尾递归是一种令人青睐的特性，因为许多Common Lisp 编译器都可以把尾递归转化成循环。若使用这种编译器，你就可以在源代码里书写优雅的递归，而不必担心函数调用在运行期产生的系统开销。
如果一个函数不是尾递归的话，常常可以把一个使用累积器(accumulator) 的局部函数嵌入到其中，用这种方法把它转换成尾递归的形式。在这里，累积器指的是一个参数，它代表着到目前为止计算得到的值。例如our-length 可以转换成
~~~
(defun our-length (lst)
(labels ((rec (lst acc)
(if (null lst)
~~~
⁴原书勘误：如果没有找到期望的元素，our-find-if 函数将无限递归下去。
~~~
acc
(rec (cdr lst) (1+ acc)))))
(rec lst 0)))
~~~
上面定义的函数里，到现在为止，所有见到的列表元素的总数都被放在了另一个参数acc 里。当递归运行到达列表的结尾，acc 的值就是总的长度，只要直接返回它就可以了。通过在调用树从上往下走的过程中累计这个值，而不是从下往上地在返回的时候再计算它，我们就可以将rec 尾递归化。
许多 Common Lisp 编译器都能做尾递归优化，但这并不是所有编译器的默认行为。所以在编写尾递归函数时，你应该把
~~~
(proclaim '(optimize speed))
~~~
写在文件的最前面，确保编译器不会辜负你的苦心，进行期望的优化。⁵
如果提供尾递归和类型声明，现有的Common Lisp 编译器就能生成运行速度能与C 程序相媲美，甚至超过◦ 它的代码。RichardGabriel 以下面的函数作为例证，它从1 累加到n ：
~~~
(defun triangle (n)
(labels ((tri (c n)
(declare (type fixnum n c))
(if (zerop n)
c
(tri (the fixnum (+ n c))
(the fixnum (- n 1))))))
(tri 0 n)))
~~~
这就是快速的Common Lisp 代码的典范。一开始就用这样写程序可能会觉得不太自然。可能更好的办法
是先用自己最习惯的方式编写函数，然后在必要时把它转化成尾递归的等价形式。
### 2.9 编译
Lisp 函数可以单独编译或者按文件编译。如果你只是在toplevel 下输入一个defun 表达式，
~~~
> (defun foo (x) (1+ x))
FOO
~~~
多数实现会创建相应的解释函数(interpretedfunction)。你可以使用compiled-function-p 来检查函数是
否被编译过：
~~~
> (compiled-function-p #'foo)
NIL
~~~
我们可以把函数名传给compile ，用这种办法来编译foo
~~~
> (compile 'foo)
FOO
~~~
这样可以编译foo 的定义，并把之前的解释版本换成编译版本。
~~~
> (compiled-function-p #'foo)
T
~~~
编译和解释函数都是Lisp 对象，两者的行为表现是相同的，只是对 compiled-function-p 的反应不一样。
直接给出的函数也可以编译：compile 希望它的第一个参数是个名字，但如果你给它的是nil ，它就会编译第二个参数给出的–表达式。
~~~
> (compile nil '(lambda (x) (+ x 2)))
#<Compiled-Function BF55BE>
~~~
⁵(optimize speed) 的声明应该是(optimize (speed 3)) 的简写。但是有一种 Common Lisp 实现，若使用前一种声明，则会进行尾递归优化，而后一种声明则不会产生这种优化。
如果你同时给出名字和函数参数，compile 的效果就相当于编译一个defun ：
~~~
> (progn (compile 'bar '(lambda (x) (* x 3)))
(compiled-function-p #'bar))
T
~~~
把compile 集成进语言里意味着程序可以随时构造和编译新函数。不过，显式调用compile 和调用eval 一样，都属于非常规的手段，同样要多加小心。⁶ 当第2.1 节里说在运行时创建新函数属常用编程技术时， 它指的是从类似 make-adder 那样的函数中生成的闭包，并非指从原始列表里调用compile 得到的新函数。调用 compile 并不属于常用的编程技术，相反，它极少会用到。所以要注意，若非必要，尽量避免使用它。除非你在Lisp 之上实现另一种语言，但即使如此，用宏也有可能达到同样的目的。
有两类函数不能被作为参数送给compile。根据 2(667 页)，你不能编译"在非空词法环境中解释性地定义出的" 函数。那就是说，在 toplevel 下，如果你定义一个带有let 的foo
~~~
> (let ((y 2))
(defun foo (x) (+ x y)))
~~~
那么，(compile 'foo) 是不能保证正常工作的。你也不能对已经编译过的函数调用compile ，CLTL2 隐晦地暗示 "结果 ...是不确定的"。
通常编译Lisp 代码的方法，不是用compile 逐个地编译函数，而是用compile-file 编译整个文件。该函数接受一个文件名，然后创建源代码的编译版本 一般情况下，编译出的文件和源文件有相同的基本文件名，但扩展名不一样。编译过的文件被加载后，compiled-function-p 对文件里定义的所有函数，返回值都是真。
后面的章节还有赖编译带来的另一种效果：如果当某个函数出现在另一函数中，并且外面的函数已经编译的话，那么里面的函数也会随之被编译。 2 里并没有明确这一行为，但所有正规的实现都支持它。
对于那些返回函数的函数来说，内层函数的编译行为是很清楚的。当make-adder (第12 页) 被编译时，它将返回一个编译过的函数：
~~~
> (compile 'make-adder)
MAKE-ADDER
> (compiled-function-p (make-adder 2))
T
~~~
后面的章节将说明，这一事实对于实现嵌入式语言来说尤为重要。如果一种新语言是通过转换实现的，而
且转换出来的代码是编译过的，那么它也会产生编译后的输出 这个转换过程也就成为了新语言事实上的编译器。(在第53 页有一个简单的例子。)
要是有特别小的函数，就可能会有内联编译它的需要。否则调用这个函数的开销可能会超出执行函数本身的开销。如果我们定义了一个函数：
~~~
(defun 50th (lst) (nth 49 lst))
~~~
并且声明：
~~~
(proclaim '(inline 50th))
~~~
所以只要函数一编译过，它在引用50th 的时候就无需进行真正的函数调用了。如果我们定义并且编译一个调用了 50th 的函数，
~~~
(defun foo (lst)
(+ (50th lst) 1))
~~~
那么编译foo 的同时，50th 的代码应该被编译进它里面。就好像我们原来写的就是
⁶第190页解释了显式调用eval 有害的理由。 ⁷把这段代码写在文件里然后再编译是没问题的。这一限制是由于具体实现的原因，被强加在了解释型函数上，而绝不是因为在清楚明白的词法环境中定义函数有什么不对。
~~~
(defun foo (lst)
(+ (nth 49 lst) 1))
~~~
一样。缺点是，如果我们改动了50th 的定义的话，那么就必须重新编译foo ，否则它用的还是原来的定义。
内联函数的限制基本上和宏差不多(见第7.9 节)。
### 2.10 来自列表的函数
一些早期的 Lisp 方言用列表来表示函数。这赋予了程序员非同一般的编写和执行其Lisp 程序的能力。
在Common Lisp 中，函数不再由列表构词 优良的实现把它们编译成本地代码。但你仍然可以写出那种编写程序的程序，因为列表是编译器的输入。
再怎么强调 "Lisp 程序可以编写 Lisp 程序" 都不为过，尤其是当这一事实经常被忽视时。即使有经验的 Lisp 程序员也很少意识到他们因这种语言特性而得到的种种好处。例如，正是这个特性使得Lisp 宏如此强大。
本书里描述的大部分技术都依赖于这个能力，即编写处理 Lisp 表达式的程序的能力。