ANSI Common Lisp 中文版

这本书面向的读者

ANSI Common Lisp 这本书适合学生或者是专业的程序员去读。本书假设读者阅读前没有 Lisp 的相关知识。有别的程序语言的编程经验也许对读本书有帮助，但也不是必须的。本书从解释 Lisp 中最基本的概念开始，并对于 Lisp 最容易迷惑初学者的地方进行特别的强调。

本书也可以作为教授 Lisp 编程的课本，也可以作为人工智能课程和其他编程语言课程中，有关 Lisp 部分的参考书。想要学习 Lisp 的专业程序员肯定会很喜欢本书所采用的直截了当、注重实践的方法。那些已经在使用 Lisp 编程的人士将会在本书中发现许多有用的实例，此外，本书也是一本方便的 ANSI Common Lisp 参考书。

如何使用这本书

学习 Lisp 最好的办法就是拿它来编程。况且在学习的同时用你学到的技术进行编程，也是非常有趣的一件事。编写本书的目的就是让读者尽快的入门，在对 Lisp 进行简短的介绍之后， 第 2 章开始用 21 页的内容，介绍了着手编写 Lisp 程序时可能会用到的所有知识。 3-9 章讲解了 Lisp 里面一些重要的知识点。这些章节特别强调了一些重要的概念，比如指针在 Lisp 中扮演的角色，如何使用递归来解决问题，以及第一级函数的重要性等等。

针对那些想要更深入了解 Lisp 的读者： 10-14 章包含了宏、CLOS、列表操作、程序优化，以及一些更高级的课题，比如包和读取宏。

15-17 章通过 3 个 Common Lisp 的实际应用，总结了之前章节所讲解的知识：一个是进行逻辑推理的程序，另一个是 HTML 生成器，最后一个是针对面向对象编程的嵌入式语言。

本书的最后一部分包含了 4 个附录，这些附录应该对所有的读者都有用： 附录 A-D 包括了一个如何调试程序的指南， 58 个 Common Lisp 操作符的源程序，一个关于 ANSI Common Lisp 和以前的 Lisp 语言区别的总结，以及一个包括所有 ANSI Common Lisp 的参考手册。

本书还包括一节备注。这些备注包括一些说明，一些参考条目，一些额外的代码，以及一些对偶然出现的不正确表述的纠正。备注在文中用一个小圆圈来表示，像这样：○

λ

代码

虽然本书介绍的是 ANSI Common Lisp ，但是本书中的代码可以在任何版本的 Common Lisp 中运行。那些依赖 Lisp 语言新特性的例子的旁边，会有注释告诉你如何把它们运行于旧版本的 Lisp 中。

本书中所有的代码都可以在互联网上下载到。你可以在网络上找到这些代码，它们还附带着一个免费软件的链接，一些过去的论文，以及 Lisp 的 FAQ 。还有很多有关 Lisp 的资源可以在此找到： http://www.eecs.harvard.edu/onlisp/ 源代码可以在此 FTP 服务器上下载： ftp://ftp.eecs.harvard.edu:/pub/onlisp/ 读者的问题和意见可以发送到 pg@eecs.harvard.edu 。

On Lisp

在整本 On Lisp 书中，我一直试着指出一些 Lisp 独一无二的特性，这些特性使得 Lisp 更像 “Lisp” 。并展示一些 Lisp 能让你完成的新事情。比如说宏： Lisp 程序员能够并且经常编写一些能够写程序的程序。对于程序生成程序这种特性，因为 Lisp 是主流语言中唯一一个提供了相关抽象使得你能够方便地实现这种特性的编程语言，所以 Lisp 是主流语言中唯一一个广泛运用这个特性的语言。我非常乐意邀请那些想要更进一步了解宏和其他高级 Lisp 技术的读者，读一下本书的姐妹篇： On Lisp 。

鸣谢

在所有帮助我完成这本的朋友当中，我想特别的感谢一下 Robert Morris 。他的重要影响反应在整本书中。他的良好影响使这本书更加优秀。本书中好一些实例程序都源自他手。这些程序包括 138 页的 Henley 和 249 页的模式匹配器。

我很高兴能有一个高水平的技术审稿小组：Skona Brittain, John Foderaro, Nick Levine, Peter Norvig 和 Dave Touretzky。本书中几乎所有部分都得益于它们的意见。 John Foderaro 甚至重写了本书 5.7 节中一些代码。

另外一些人通篇阅读了本书的手稿，它们是：Ken Anderson, Tom Cheatham, Richard Fateman, Steve Hain, Barry Margolin, Waldo Pacheco, Wheeler Ruml 和 Stuart Russell。特别要提一下，Ken Anderson 和 Wheeler Ruml 给予了很多有用的意见。

我非常感谢 Cheatham 教授，更广泛的说，哈佛，提供我编写这本书的一些必要条件。另外也要感谢 Aiken 实验室的人员：Tony Hartman, Dave Mazieres, Janusz Juda, Harry Bochner 和 Joanne Klys。

我非常高兴能再一次有机会和 Alan Apt 合作。还有这些在 Prentice Hall 工作的人士： Alan, Mona, Pompili Shirley McGuire 和 Shirley Michaels, 能与你们共事我很高兴。

本书用 Leslie Lamport 写的 LaTeX 进行排版。LaTeX 是在 Donald Knuth 编写的 TeX 的基础上，又加了 L.A.Carr, Van Jacobson 和 Guy Steele 所编写的宏完成。书中的图表是由 John Vlissides 和 Scott Stanton 编写的 Idraw 完成的。整本书的预览是由 Tim Theisen 写的 Ghostview 完成的。 Ghostview 是根据 L. Peter Deutsch 的 Ghostscript 创建的。

我还需要感谢其他的许多人，包括：Henry Baker, Kim Barrett, Ingrid Bassett, Trevor Blackwell, Paul Becker, Gary Bisbee, Frank Deutschmann, Frances Dickey, Rich 和 Scott Draves, Bill Dubuque, Dan Friedman, Jenny Graham, Alice Hartley, David Hendler, Mike Hewett, Glenn Holloway, Brad Karp, Sonya Keene, Ross Knights, Mutsumi Komuro, Steffi Kutzia, David Kuznick, Madi Lord, Julie Mallozzi, Paul McNamee, Dave Moon, Howard Mullings, Mark Nitzberg, Nancy Parmet 和其家人, Robert Penny, Mike Plusch, Cheryl Sacks, Hazem Sayed, Shannon Spires, Lou Steinberg, Paul Stoddard, John Stone, Guy Steele, Steve Strassmann, Jim Veitch, Dave Watkins, Idelle and Julian Weber, the Weickers, Dave Yost 和 Alan Yuille。

另外，着重感谢我的父母和 Jackie。

高德纳给他的经典丛书起名为《计算机程序设计艺术》。在他的图灵奖获奖感言中，他解释说这本书的书名源自于内心深处的潜意识 ── 潜意识告诉他，编程其实就是追求编写最优美的程序。

就像建筑设计一样，编程既是一门工程技艺也是一门艺术。一个程序要遵循数学原理也要符合物理定律。但是建筑师的目的不仅仅是建一个不会倒塌的建筑。更重要的是，他们要建一个优美的建筑。

像高德纳一样，很多程序员认为编程的真正目的，不仅仅是编写出正确的程序，更重要的是写出优美的代码。几乎所有的 Lisp 黑客也是这么想的。 Lisp 黑客精神可以用两句话来概括：编程应该是有趣的。程序应该是优美的。这就是我在这本书中想要传达的精神。

保罗•格雷厄姆 (Paul Graham)

1.1 新的工具 (New Tools)

为什么要学 Lisp？因为它让你能做一些其它语言做不到的事情。如果你只想写一个函数来返回小于 n 的数字总和，那么用 Lisp 和 C 是差不多的：

; Lisp                   /* C */
(defun sum (n)           int sum(int n){
  (let ((s 0))             int i, s = 0;
    (dotimes (i n s)       for(i = 0; i < n; i++)
      (incf s i))))          s += i;
                            return(s);
                          }

如果你只想做这种简单的事情，那用什么语言都不重要。假设你想写一个函数，输入一个数 n ，返回把 n 与传入参数 (argument)相加的函数。

; Lisp
(defun addn (n)
  #'(lambda (x)
      (+ x n)))

在 C 语言中 addn 怎么实现？你根本写不出来。

你可能会想，谁会想做这样的事情？程序语言教你不要做它们没有提供的事情。你得针对每个程序语言，用其特定的思维来写程序，而且想得到你所不能描述的东西是很困难的。当我刚开始编程时 ── 用 Baisc ── 我不知道什么是递归，因为我根本不知道有这个东西。我是用 Basic 在思考。我只能用迭代的概念表达算法，所以我怎么会知道递归呢？

如果你没听过词法闭包 「Lexical Closure」 (上述 addn 的范例)，相信我， Lisp 程序员一直在使用它。很难找到任何长度的 Common Lisp 程序，没有用到闭包的好处。在 112 页前，你自己会持续使用它。

闭包仅是其中一个我们在别的语言找不到的抽象概念之一。另一个更有价值的 Lisp 特点是， Lisp 程序是用 Lisp 的数据结构来表示。这表示你可以写出会写程序的程序。人们真的需要这个吗？没错 ── 它们叫做宏，有经验的程序员也一直在使用它。学到 173 页你就可以自己写出自己的宏了。

有了宏、闭包以及运行期类型，Lisp 凌驾在面向对象程序设计之上。如果你了解上面那句话，也许你不应该阅读此书。你得充分了解 Lisp 才能明白为什么此言不虚。但这不是空泛之言。这是一个重要的论点，并且在 17 章用程序相当明确的证明了这点。

第二章到第十三章会循序渐进地介绍所有你需要理解第 17 章程序的概念。你的努力会有所回报：你会感到在 C++ 编程是窒碍难行的，就像有经验的 C++ 程序员用 Basic 编程会感到窒息一样。更加鼓舞人心的是，如果我们思考为什么会有这种感觉。 编写 Basic 对于平常用 C++ 编程是令人感到窒息的，是因为有经验的 C++ 程序员知道一些用 Basic 不可能表达出来的技术。同样地，学习 Lisp 不仅教你学会一门新的语言 ── 它教你崭新的并且更强大的程序思考方法。

1.2 新的技术 (New Techniques)

如上一节所提到的， Lisp 赋予你别的语言所没有的工具。不仅仅如此，就 Lisp 带来的新特性来说 ── 自动内存管理 (automatic memory management)，显式类型 (manifest typing)，闭包 (closures)等 ── 每一项都使得编程变得如此简单。结合起来，它们组成了一个关键的部分，使得一种新的编程方式是有可能的。

Lisp 被设计成可扩展的：让你定义自己的操作符。这是可能的，因为 Lisp 是由和你程序一样的函数与宏所构成的。所以扩展 Lisp 就和写一个 Lisp 程序一样简单。事实上，它是如此的容易（和有用），以至于扩展语言自身成了标准实践。当你在用 Lisp 语言編程时，你也在创造一个适合你的程序的语言。你由下而上地，也由上而下地工作。

几乎所有的程序，都可以从订作适合自己所需的语言中受益。然而越复杂的程序，由下而上的程序设计就显得越有价值。一个由下而上所设计出来的程序，可写成一系列的层，每层担任上一层的程序语言。 TeX 是最早使用这种方法所写的程序之一。你可以用任何语言由下而上地设计程序，但 Lisp 是本质上最适合这种方法的工具。

由下而上的编程方法，自然发展出可扩展的软件。如果你把由下而上的程序设计的原则，想成你程序的最上层，那这层就成为使用者的程序语言。正因可扩展的思想深植于 Lisp 当中，使得 Lisp 成为实现可扩展软件的理想语言。三个 1980 年代最成功的程序提供 Lisp 作为扩展自身的语言: GNU Emacs ， Autocad ，和 Interleaf 。

由下而上的编程方法，也是得到可重用软件的最好方法。写可重用软件的本质是把共同的地方从细节中分离出来，而由下而上的编程方法本质地创造这种分离。与其努力撰写一个庞大的应用，不如努力创造一个语言，用相对小的努力在这语言上撰写你的应用。和应用相关的特性集中在最上层，以下的层可以组成一个适合这种应用的语言 ── 还有什么比程序语言更具可重用性的呢？

Lisp 让你不仅编写出更复杂的程序，而且写的更快。 Lisp 程序通常很简短 ── Lisp 给了你更高的抽象化，所以你不用写太多代码。就像 Frederick Brooks 所指出的，编程所花的时间主要取决于程序的长度。因此仅仅根据这个单独的事实，就可以推断出用 Lisp 编程所花的时间较少。这种效果被 Lisp 的动态特点放大了：在 Lisp 中，编辑-编译-测试循环短到使编程像是即时的。

更高的抽象化与互动的环境，能改变各个机构开发软件的方式。术语快速建型描述了一种始于 Lisp 的编程方法：在 Lisp 里，你可以用比写规格说明更短的时间，写一个原型出来，而这种原型是高度抽象化的，可作为一个比用英语所写的更好的规格说明。而且 Lisp 让你可以轻易的从原型转成产品软件。当写一个考虑到速度的 Common Lisp 程序时，通过现代编译器的编译，Lisp 与其他的高阶语言所写的程序运行得一样快。

除非你相当熟悉 Lisp ，这个简介像是无意义的言论和冠冕堂皇的声明。Lisp 凌驾面向对象程序设计？ 你创造适合你程序的语言？ Lisp 编程是即时的？ 这些说法是什么意思？现在这些说法就像是枯竭的湖泊。随着你学到更多实际的 Lisp 特色，见过更多可运行的程序，这些说法就会被实际经验之水所充满，而有了明确的形状。

1.3 新的方法 (New Approach)

本书的目标之一是不仅是教授 Lisp 语言，而是教授一种新的编程方法，这种方法因为有了 Lisp 而有可能实现。这是一种你在未来会见得更多的方法。随着开发环境变得更强大，程序语言变得更抽象， Lisp 的编程风格正逐渐取代旧的规划-然后-实现 (plan-and-implement)的模式。

在旧的模式中，错误永远不应该出现。事前辛苦订出缜密的规格说明，确保程序完美的运行。理论上听起来不错。不幸地，规格说明是人写的，也是人来实现的。实际上结果是， 规划-然后-实现 模型不太有效。

身为 OS/360 的项目经理， Frederick Brooks 非常熟悉这种传统的模式。他也非常熟悉它的后果：

任何 OS/360 的用户很快的意识到它应该做得更好...再者，产品推迟，用了更多的内存，成本是估计的好几倍，效能一直不好，直到第一版后的好几个版本更新，效能才算还可以。

而这却描述了那个时代最成功系统之一。

旧模式的问题是它忽略了人的局限性。在旧模式中，你打赌规格说明不会有严重的缺失，实现它们不过是把规格转成代码的简单事情。经验显示这实在是非常坏的赌注。打赌规格说明是误导的，程序到处都是臭虫 (bug) 会更保险一点。

这其实就是新的编程模式所假设的。设法尽量降低错误的成本，而不是希望人们不犯错。错误的成本是修补它所花费的时间。使用强大的语言跟好的开发环境，这种成本会大幅地降低。编程风格可以更多地依靠探索，较少地依靠事前规划。

规划是一种必要之恶。它是评估风险的指标：越是危险，预先规划就显得更重要。强大的工具降低了风险，也降低了规划的需求。程序的设计可以从最有用的信息来源中受益：过去实作程序的经验。

Lisp 风格从 1960 年代一直朝着这个方向演进。你在 Lisp 中可以如此快速地写出原型，以致于你已历经好几个设计和实现的循环，而在旧的模式当中，你可能才刚写完规格说明。你不必担心设计的缺失，因为你将更快地发现它们。你也不用担心有那么多臭虫。当你用函数式风格来编程，你的臭虫只有局部的影响。当你使用一种很抽象的语言，某些臭虫(如迷途指针)不再可能发生，而剩下的臭虫很容易找出，因为你的程序更短了。当你有一个互动的开发环境，你可以即时修补臭虫，不必经历 编辑，编译，测试的漫长过程。

Lisp 风格会这么演进是因为它产生的结果。听起来很奇怪，少的规划意味著更好的设计。技术史上相似的例子不胜枚举。一个相似的变革发生在十五世纪的绘画圈里。在油画流行前，画家使用一种叫做蛋彩的材料来作画。蛋彩不能被混和或涂掉。犯错的代价非常高，也使得画家变得保守。后来随着油画颜料的出现，作画风格有了大幅地改变。油画“允许你再来一次”这对困难主题的处理，像是画人体，提供了决定性的有利条件。

新的材料不仅使画家更容易作画了。它使新的更大胆的作画方式成为可能。 Janson 写道：

如果没有油画颜料，弗拉芒大师们的征服可见的现实的口号就会大打折扣。于是，从技术的角度来说，也是如此，但他们当之无愧地称得上是“现代绘画之父”，油画颜料从此以后成为画家的基本颜料。

做为一种介质，蛋彩与油画颜料一样美丽。但油画颜料的弹性给想像力更大的发挥空间 ── 这是决定性的因素。

程序设计正经历着相同的改变。新的介质像是“动态的面向对象语言” ── 即 Lisp 。这不是说我们所有的软件在几年内都要用 Lisp 来写。从蛋彩到油画的转变也不是一夜完成的；油彩一开始只在领先的艺术中心流行，而且经常混合着蛋彩来使用。我们现在似乎正处于这个阶段。 Lisp 被大学，研究室和某些顶尖的公司所使用。同时，从 Lisp 借鉴的思想越来越多地出现在主流语言中：交互式编程环境 (interactive programming environment)、垃圾回收(garbage collection)、运行期类型 (run-time typing)，仅举其中几个。

强大的工具正降低探索的风险。这对程序员来说是好消息，因为意味者我们可以从事更有野心的项目。油画的确有这个效果。采用油画后的时期正是绘画的黄金时期。类似的迹象正在程序设计的领域中发生。

2.1 形式 (Form)

人可以通过实践来学习一件事，这对于 Lisp 来说特别有效，因为 Lisp 是一门交互式的语言。任何 Lisp 系统都含有一个交互式的前端，叫做顶层(toplevel)。你在顶层输入 Lisp 表达式，而系统会显示它们的值。

Lisp 通常会打印一个提示符告诉你，它正在等待你的输入。许多 Common Lisp 的实现用 > 作为顶层提示符。本书也沿用这个符号。

一个最简单的 Lisp 表达式是整数。如果我们在提示符后面输入 1 ，

> 1
1
>

系统会打印出它的值，接着打印出另一个提示符，告诉你它在等待更多的输入。

在这个情况里，打印的值与输入的值相同。数字 1 称之为对自身求值。当我们输入需要做某些计算来求值的表达式时，生活变得更加有趣了。举例来说，如果我们想把两个数相加，我们输入像是：

> (+ 2 3)
5

在表达式 (+ 2 3) 里， + 称为操作符，而数字 2 跟 3 称为实参。

在日常生活中，我们会把表达式写作 2 + 3 ，但在 Lisp 里，我们把 + 操作符写在前面，接著写实参，再把整个表达式用一对括号包起来： (+ 2 3) 。这称为前序表达式。一开始可能觉得这样写表达式有点怪，但事实上这种表示法是 Lisp 最美妙的东西之一。

举例来说，我们想把三个数加起来，用日常生活的表示法，要写两次 + 号，

2 + 3 + 4

而在 Lisp 里，只需要增加一个实参：

(+ 2 3 4)

日常生活中用 + 时，它必须有两个实参，一个在左，一个在右。前序表示法的灵活性代表著，在 Lisp 里， + 可以接受任意数量的实参，包含了没有实参：

> (+)
0
> (+ 2)
2
> (+ 2 3)
5
> (+ 2 3 4)
9
> (+ 2 3 4 5)
14

由于操作符可接受不定数量的实参，我们需要用括号来标明表达式的开始与结束。

表达式可以嵌套。即表达式里的实参，可以是另一个复杂的表达式：

> (/ (- 7 1) (- 4 2))
3

上面的表达式用中文来说是， (七减一) 除以 (四减二) 。

Lisp 表示法另一个美丽的地方是：它就是如此简单。所有的 Lisp 表达式，要么是 1 这样的数原子，要么是包在括号里，由零个或多个表达式所构成的列表。以下是合法的 Lisp 表达式：

2 (+ 2 3) (+ 2 3 4) (/ (- 7 1) (- 4 2))

稍后我们将理解到，所有的 Lisp 程序都采用这种形式。而像是 C 这种语言，有着更复杂的语法：算术表达式采用中序表示法；函数调用采用某种前序表示法，实参用逗号隔开；表达式用分号隔开；而一段程序用大括号隔开。

在 Lisp 里，我们用单一的表示法，来表达所有的概念。

2.2 求值 (Evaluation)

上一小节中，我们在顶层输入表达式，然后 Lisp 显示它们的值。在这节里我们深入理解一下表达式是如何被求值的。

在 Lisp 里， + 是函数，然而如 (+ 2 3) 的表达式，是函数调用。

当 Lisp 对函数调用求值时，它做下列两个步骤：

1. 首先从左至右对实参求值。在这个例子当中，实参对自身求值，所以实参的值分别是 2 跟 3 。
2. 实参的值传入以操作符命名的函数。在这个例子当中，将 2 跟 3 传给 + 函数，返回 5 。

如果实参本身是函数调用的话，上述规则同样适用。以下是当 (/ (- 7 1) (- 4 2)) 表达式被求值时的情形：

1. Lisp 对 (- 7 1) 求值: 7 求值为 7 ， 1 求值为 1 ，它们被传给函数 - ，返回 6 。
2. Lisp 对 (- 4 2) 求值: 4 求值为 4 ， 2 求值为 2 ，它们被传给函数 - ，返回 2 。
3. 数值 6 与 2 被传入函数 / ，返回 3 。

但不是所有的 Common Lisp 操作符都是函数，不过大部分是。函数调用都是这么求值。由左至右对实参求值，将它们的数值传入函数，来返回整个表达式的值。这称为 Common Lisp 的求值规则。

> (/ 1 0)
Error: Division by zero
      Options: :abort, :backtrace
>> :abort
>

一个不遵守 Common Lisp 求值规则的操作符是 quote 。 quote 是一个特殊的操作符，意味着它自己有一套特别的求值规则。这个规则就是：什么也不做。 quote 操作符接受一个实参，并完封不动地返回它。

> (quote (+ 3 5))
(+ 3 5)

为了方便起见，Common Lisp 定义 ' 作为 quote 的缩写。你可以在任何的表达式前，贴上一个 ' ，与调用 quote 是同样的效果：

> '(+ 3 5)
(+ 3 5)

使用缩写 ' 比使用整个 quote 表达式更常见。

Lisp 提供 quote 作为一种保护表达式不被求值的方式。下一节将解释为什么这种保护很有用。

2.3 数据 (Data)¶

Lisp 提供了所有在其他语言找的到的，以及其他语言所找不到的数据类型。一个我们已经使用过的类型是整数（integer），整数用一系列的数字来表示，比如： 256 。另一个 Common Lisp 与多数语言有关，并很常见的数据类型是字符串（string），字符串用一系列被双引号包住的字符串表示，比如： "ora et labora" [3] 。整数与字符串一样，都是对自身求值的。

有两个通常在别的语言所找不到的 Lisp 数据类型是符号（symbol）与列表（lists），符号是英语的单词 (words)。无论你怎么输入，通常会被转换为大写：

> 'Artichoke
ARTICHOKE

符号（通常）不对自身求值，所以要是想引用符号，应该像上例那样用 ' 引用它。

列表是由被括号包住的零个或多个元素来表示。元素可以是任何类型，包含列表本身。使用列表必须要引用，不然 Lisp 会以为这是个函数调用：

> '(my 3 "Sons")
(MY 3 "Sons")
> '(the list (a b c) has 3 elements)
(THE LIST (A B C) HAS 3 ELEMENTS)

注意引号保护了整个表达式（包含内部的子表达式）被求值。

你可以调用 list 来创建列表。由于 list 是函数，所以它的实参会被求值。这里我们看一个在函数 list 调用里面，调用 + 函数的例子：

> (list 'my (+ 2 1) "Sons")
(MY 3 "Sons")

我们现在来到领悟 Lisp 最卓越特性的地方之一。Lisp的程序是用列表来表示的。如果实参的优雅与弹性不能说服你 Lisp 表示法是无价的工具，这里应该能使你信服。这代表着 Lisp 程序可以写出 Lisp 代码。 Lisp 程序员可以（并且经常）写出能为自己写程序的程序。

不过得到第 10 章，我们才来考虑这种程序，但现在了解到列表和表达式的关系是非常重要的，而不是被它们搞混。这也就是为什么我们需要 quote 。如果一个列表被引用了，则求值规则对列表自身来求值；如果没有被引用，则列表被视为是代码，依求值规则对列表求值后，返回它的值。

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

这里第一个实参被引用了，所以产生一个列表。第二个实参没有被引用，视为函数调用，经求值后得到一个数字。

在 Common Lisp 里有两种方法来表示空列表。你可以用一对不包括任何东西的括号来表示，或用符号 nil 来表示空表。你用哪种表示法来表示空表都没关系，但它们都会被显示为 nil ：

> ()
NIL
> nil
NIL

你不需要引用 nil （但引用也无妨），因为 nil 是对自身求值的。

2.4 列表操作 (List Operations)¶

用函数 cons 来构造列表。如果传入的第二个实参是列表，则返回由两个实参所构成的新列表，新列表为第一个实参加上第二个实参：

> (cons 'a '(b c d))
(A B C D)

可以通过把新元素建立在空表之上，来构造一个新列表。上一节所看到的函数 list ，不过就是一个把几个元素加到 nil 上的快捷方式：

> (cons 'a (cons 'b nil))
(A B)
> (list 'a 'b)
(A B)

取出列表元素的基本函数是 car 和 cdr 。对列表取 car 返回第一个元素，而对列表取 cdr 返回第一个元素之后的所有元素：

> (car '(a b c))
A
> (cdr '(a b c))
(B C)

你可以把 car 与 cdr 混合使用来取得列表中的任何元素。如果我们想要取得第三个元素，我们可以：

> (car (cdr (cdr '(a b c d))))
C

不过，你可以用更简单的 third 来做到同样的事情：

> (third '(a b c d))
C

2.5 真与假 (Truth)¶

在 Common Lisp 里，符号 t 是表示逻辑 真 的缺省值。与 nil 相同， t 也是对自身求值的。如果实参是一个列表，则函数 listp 返回 真 ：

> (listp '(a b c))
T

函数的返回值将会被解释成逻辑 真 或逻辑 假 时，则称此函数为谓词（predicate）。在 Common Lisp 里，谓词的名字通常以 p 结尾。

逻辑 假 在 Common Lisp 里，用 nil ，即空表来表示。如果我们传给 listp 的实参不是列表，则返回 nil 。

> (listp 27)
NIL

由于 nil 在 Common Lisp 里扮演两个角色，如果实参是一个空表，则函数 null 返回 真 。

> (null nil)
T

而如果实参是逻辑 假 ，则函数 not 返回 真 ：

> (not nil)
T

null 与 not 做的是一样的事情。

在 Common Lisp 里，最简单的条件式是 if 。通常接受三个实参：一个 test 表达式，一个 then 表达式和一个 else 表达式。若 test 表达式求值为逻辑 真 ，则对 then 表达式求值，并返回这个值。若 test 表达式求值为逻辑 假 ，则对 else 表达式求值，并返回这个值：

> (if (listp '(a b c))
      (+ 1 2)
      (+ 5 6))
3
> (if (listp 27)
      (+ 1 2)
      (+ 5 6))
11

与 quote 相同， if 是特殊的操作符。不能用函数来实现，因为实参在函数调用时永远会被求值，而 if 的特点是，只有最后两个实参的其中一个会被求值。 if 的最后一个实参是选择性的。如果忽略它的话，缺省值是 nil ：

> (if (listp 27)
     (+ 1 2))
NIL

虽然 t 是逻辑 真 的缺省表示法，任何非 nil 的东西，在逻辑的上下文里通通被视为 真 。

> (if 27 1 2)
1

逻辑操作符 and 和 or 与条件式类似。两者都接受任意数量的实参，但仅对能影响返回值的几个实参求值。如果所有的实参都为 真 （即非 nil ），那么 and 会返回最后一个实参的值：

> (and t (+ 1 2))
3

如果其中一个实参为 假 ，那之后的所有实参都不会被求值。 or 也是如此，只要碰到一个为 真 的实参，就停止对之后所有的实参求值。

以上这两个操作符称为宏。宏和特殊的操作符一样，可以绕过一般的求值规则。第十章解释了如何编写你自己的宏。

2.6 函数 (Functions)¶

你可以用 defun 来定义新函数。通常接受三个以上的实参：一个名字，一组用列表表示的实参，以及一个或多个组成函数体的表达式。我们可能会这样定义 third ：

> (defun our-third (x)
   (car (cdr (cdr x))))
OUR-THIRD

第一个实参说明此函数的名称将是 our-third 。第二个实参，一个列表 (x) ，说明这个函数会接受一个形参： x 。这样使用的占位符符号叫做变量。当变量代表了传入函数的实参时，如这里的 x ，又被叫做形参。

定义的剩余部分， (car (cdr (cdr x))) ，即所谓的函数主体。它告诉 Lisp 该怎么计算此函数的返回值。所以调用一个 our-third 函数，对于我们作为实参传入的任何 x ，会返回 (car (cdr (cdr x))) ：

> (our-third '(a b c d))
C

既然我们已经讨论过了变量，理解符号是什么就更简单了。符号是变量的名字，符号本身就是以对象的方式存在。这也是为什么符号，必须像列表一样被引用。列表必须被引用，不然会被视为代码。符号必须要被引用，不然会被当作变量。

你可以把函数定义想成广义版的 Lisp 表达式。下面的表达式测试 1 和 4 的和是否大于 3 ：

> (> (+ 1 4) 3)
T

通过将这些数字替换为变量，我们可以写个函数，测试任两数之和是否大于第三个数：

> (defun sum-greater (x y z)
   (> (+ x y) z))
SUM-GREATER
> (sum-greater 1 4 3)
T

Lisp 不对程序、过程以及函数作区别。函数做了所有的事情（事实上，函数是语言的主要部分）。如果你想要把你的函数之一作为主函数（main function），可以这么做，但平常你就能在顶层中调用任何函数。这表示当你编程时，你可以把程序拆分成一小块一小块地来做调试。

2.7 递归 (Recursion)¶

上一节我们所定义的函数，调用了别的函数来帮它们做事。比如 sum-greater 调用了 + 和 > 。函数可以调用任何函数，包括自己。自己调用自己的函数是递归的。 Common Lisp 函数 member ，测试某个东西是否为列表的成员。下面是定义成递归函数的简化版：

> (defun our-member (obj lst)
   (if (null lst)
       nil
   (if (eql (car lst) obj)
       lst
       (our-member obj (cdr lst)))))
OUR-MEMBER

谓词 eql 测试它的两个实参是否相等；此外，这个定义的所有东西我们之前都学过了。下面是运行的情形：

> (our-member 'b '(a b c))
(B C)
> (our-member 'z '(a b c))
NIL

下面是 our-member 的定义对应到英语的描述。为了知道一个对象 obj 是否为列表 lst 的成员，我们

1. 首先检查 lst 列表是否为空列表。如果是空列表，那 obj 一定不是它的成员，结束。
2. 否则，若 obj 是列表的第一个元素时，则它是列表的成员。
3. 不然只有当 obj 是列表其余部分的元素时，它才是列表的成员。

当你想要了解递归函数是怎么工作时，把它翻成这样的叙述有助于你理解。

起初，许多人觉得递归函数很难理解。大部分的理解难处，来自于对函数使用了错误的比喻。人们倾向于把函数理解为某种机器。原物料像实参一样抵达；某些工作委派给其它函数；最后组装起来的成品，被作为返回值运送出去。如果我们用这种比喻来理解函数，那递归就自相矛盾了。机器怎可以把工作委派给自己？它已经在忙碌中了。

较好的比喻是，把函数想成一个处理的过程。在过程里，递归是在自然不过的事情了。日常生活中我们经常看到递归的过程。举例来说，假设一个历史学家，对欧洲历史上的人口变化感兴趣。研究文献的过程很可能是：

1. 取得一个文献的复本
2. 寻找关于人口变化的资讯
3. 如果这份文献提到其它可能有用的文献，研究它们。

过程是很容易理解的，而且它是递归的，因为第三个步骤可能带出一个或多个同样的过程。

所以，别把 our-member 想成是一种测试某个东西是否为列表成员的机器。而是把它想成是，决定某个东西是否为列表成员的规则。如果我们从这个角度来考虑函数，那么递归的矛盾就不复存在了。

2.8 阅读 Lisp (Reading Lisp)¶

上一节我们所定义的 our-member 以五个括号结尾。更复杂的函数定义更可能以七、八个括号结尾。刚学 Lisp 的人看到这么多括号会感到气馁。这叫人怎么读这样的程序，更不用说编了？怎么知道哪个括号该跟哪个匹配？

答案是，你不需要这么做。 Lisp 程序员用缩排来阅读及编写程序，而不是括号。当他们在写程序时，他们让文字编辑器显示哪个括号该与哪个匹配。任何好的文字编辑器，特别是 Lisp 系统自带的，都应该能做到括号匹配（paren-matching）。在这种编辑器中，当你输入一个括号时，编辑器指出与其匹配的那一个。如果你的编辑器不能匹配括号，别用了，想想如何让它做到，因为没有这个功能，你根本不可能编 Lisp 程序 [1] 。

有了好的编辑器之后，括号匹配不再会是问题。而且由于 Lisp 缩排有通用的惯例，阅读程序也不是个问题。因为所有人都使用一样的习惯，你可以忽略那些括号，通过缩排来阅读程序。

任何有经验的 Lisp 黑客，会发现如果是这样的 our-member 的定义很难阅读：

(defun our-member (obj lst) (if (null lst) nil (if
(eql (car lst) obj) lst (our-member obj (cdr lst)))))

但如果程序适当地缩排时，他就没有问题了。可以忽略大部分的括号而仍能读懂它：

defun our-member (obj lst)
 if null lst
    nil
    if eql (car lst) obj
       lst
       our-member obj (cdr lst)

事实上，这是你在纸上写 Lisp 程序的实用方法。等输入程序至计算机的时候，可以利用编辑器匹配括号的功能。

2.9 输入输出 (Input and Output)¶

到目前为止，我们已经利用顶层偷偷使用了 I/O 。对实际的交互程序来说，这似乎还是不太够。在这一节，我们来看几个输入输出的函数。

最普遍的 Common Lisp 输出函数是 format 。接受两个或两个以上的实参，第一个实参决定输出要打印到哪里，第二个实参是字符串模版，而剩余的实参，通常是要插入到字符串模版，用打印表示法（printed representation）所表示的对象。下面是一个典型的例子：

> (format t "~A plus ~A equals ~A. ~%" 2 3 (+ 2 3))
2 plus 3 equals 5.
NIL

注意到有两个东西被打印出来。第一行是 format 印出来的。第二行是调用 format 函数的返回值，就像平常顶层会打印出来的一样。通常像 format 这种函数不会直接在顶层调用，而是在程序内部里使用，所以返回值不会被看到。

format 的第一个实参 t ，表示输出被送到缺省的地方去。通常是顶层。第二个实参是一个用作输出模版的字符串。在这字符串里，每一个 ~A 表示了被填入的位置，而 ~% 表示一个换行。这些被填入的位置依序由后面的实参填入。

标准的输入函数是 read 。当没有实参时，会读取缺省的位置，通常是顶层。下面这个函数，提示使用者输入，并返回任何输入的东西：

(defun askem (string)
 (format t "~A" string)
 (read))

它的行为如下：

> (askem "How old are you?")
How old are you?29

29

记住 read 会一直永远等在这里，直到你输入了某些东西，并且（通常要）按下回车。因此，不打印明确的提示信息是很不明智的，程序会给人已经死机的印象，但其实它是在等待输入。

第二件关于 read 所需要知道的事是，它很强大： read 是一个完整的 Lisp 解析器（parser）。不仅是可以读入字符，然后当作字符串返回它们。它解析它所读入的东西，并返回产生出来的 Lisp 对象。在上述的例子，它返回一个数字。

askem 的定义虽然很短，但体现出一些我们在之前的函数没看过的东西。函数主体可以有不只一个表达式。函数主体可以有任意数量的表达式。当函数被调用时，会依序求值，函数会返回最后一个的值。

在之前的每一节中，我们坚持所谓“纯粹的” Lisp ── 即没有副作用的 Lisp 。副作用是指，表达式被求值后，对外部世界的状态做了某些改变。当我们对一个如 (+ 1 2) 这样纯粹的 Lisp 表达式求值时，没有产生副作用。它只返回一个值。但当我们调用 format 时，它不仅返回值，还印出了某些东西。这就是一种副作用。

当我们想要写没有副作用的程序时，则定义多个表达式的函数主体就没有意义了。最后一个表达式的值，会被当成函数的返回值，而之前表达式的值都被舍弃了。如果这些表达式没有副作用，你没有任何理由告诉 Lisp ，为什么要去对它们求值。

2.10 变量 (Variables)¶

let 是一个最常用的 Common Lisp 的操作符之一，它让你引入新的局部变量（local variable）：

> (let ((x 1) (y 2))
     (+ x y))
3

一个 let 表达式有两个部分。第一个部分是一组创建新变量的指令，指令的形式为 (variable expression) 。每一个变量会被赋予相对应表达式的值。上述的例子中，我们创造了两个变量， x 和 y ，分别被赋予初始值 1 和 2 。这些变量只在 let 的函数体内有效。

一组变量与数值之后，是一个有表达式的函数体，表达式依序被求值。但这个例子里，只有一个表达式，调用 + 函数。最后一个表达式的求值结果作为 let 的返回值。以下是一个用 let 所写的，更有选择性的 askem 函数：

(defun ask-number ()
 (format t "Please enter a number. ")
 (let ((val (read)))
   (if (numberp val)
       val
       (ask-number))))

这个函数创建了变量 val 来储存 read 所返回的对象。因为它知道该如何处理这个对象，函数可以先观察你的输入，再决定是否返回它。你可能猜到了， numberp 是一个谓词，测试它的实参是否为数字。

如果使用者不是输入一个数字， ask-number 会持续调用自己。最后得到一个只接受数字的函数：

> (ask-number)
Please enter a number. a
Please enter a number. (ho hum)
Please enter a number. 52
52

我们已经看过的这些变量都叫做局部变量。它们只在特定的上下文里有效。另外还有一种变量叫做全局变量（global variable），是在任何地方都是可视的。 [2]

你可以给 defparameter 传入符号和值，来创建一个全局变量：

> (defparameter *glob* 99)
*GLOB*

全局变量在任何地方都可以存取，除了在定义了相同名字的区域变量的表达式里。为了避免这种情形发生，通常我们在给全局变量命名时，以星号作开始与结束。刚才我们创造的变量可以念作 “星-glob-星” (star-glob-star)。

你也可以用 defconstant 来定义一个全局的常量：

(defconstant limit (+ *glob* 1))

我们不需要给常量一个独一无二的名字，因为如果有相同名字存在，就会有错误产生 (error)。如果你想要检查某些符号，是否为一个全局变量或常量，使用 boundp 函数：

> (boundp '*glob*)
T

2.11 赋值 (Assignment)¶

在 Common Lisp 里，最普遍的赋值操作符（assignment operator）是 setf 。可以用来给全局或局部变量赋值：

> (setf *glob* 98)
98
> (let ((n 10))
   (setf n 2)
   n)
2

如果 setf 的第一个实参是符号（symbol），且符号不是某个局部变量的名字，则 setf 把这个符号设为全局变量：

> (setf x (list 'a 'b 'c))
(A B C)

也就是说，通过赋值，你可以隐式地创建全局变量。 不过，一般来说，还是使用 defparameter 明确地创建全局变量比较好。

你不仅可以给变量赋值。传入 setf 的第一个实参，还可以是表达式或变量名。在这种情况下，第二个实参的值被插入至第一个实参所引用的位置：

> (setf (car x) 'n)
N
> x
(N B C)

setf 的第一个实参几乎可以是任何引用到特定位置的表达式。所有这样的操作符在附录 D 中被标注为 “可设置的”（“settable”）。你可以给 setf 传入（偶数）个实参。一个这样的表达式

(setf a 'b
      c 'd
      e 'f)

等同于依序调用三个单独的 setf 函数：

(setf a 'b)
(setf c 'd)
(setf e 'f)

2.12 函数式编程 (Functional Programming)¶

函数式编程意味着撰写利用返回值而工作的程序，而不是修改东西。它是 Lisp 的主流范式。大部分 Lisp 的内置函数被调用是为了取得返回值，而不是副作用。

举例来说，函数 remove 接受一个对象和一个列表，返回不含这个对象的新列表：

> (setf lst '(c a r a t))
(C A R A T)
> (remove 'a lst)
(C R T)

为什么不干脆说 remove 从列表里移除一个对象？因为它不是这么做的。原来的表没有被改变：

> lst
(C A R A T)

若你真的想从列表里移除某些东西怎么办？在 Lisp 通常你这么做，把这个列表当作实参，传入某个函数，并使用 setf 来处理返回值。要移除所有在列表 x 的 a ，我们可以说：

(setf x (remove 'a x))

函数式编程本质上意味着避免使用如 setf 的函数。起初可能觉得这根本不可能，更遑论去做了。怎么可以只凭返回值来建立程序？

完全不用到副作用是很不方便的。然而，随着你进一步阅读，会惊讶地发现需要用到副作用的地方很少。副作用用得越少，你就更上一层楼。

函数式编程最重要的优点之一是，它允许交互式测试（interactive testing）。在纯函数式的程序里，你可以测试每个你写的函数。如果它返回你预期的值，你可以有信心它是对的。这额外的信心，集结起来，会产生巨大的差别。当你改动了程序里的任何一个地方，会得到即时的改变。而这种即时的改变，使我们有一种新的编程风格。类比于电话与信件，让我们有一种新的通讯方式。

2.13 迭代 (Iteration)¶

当我们想重复做一些事情时，迭代比递归来得更自然。典型的例子是用迭代来产生某种表格。这个函数

(defun show-squares (start end)
  (do ((i start (+ i 1)))
      ((> i end) 'done)
    (format t "~A ~A~%" i (* i i))))

列印从 start 到 end 之间的整数的平方：

> (show-squares 2 5)
2 4
3 9
4 16
5 25
DONE

do 宏是 Common Lisp 里最基本的迭代操作符。和 let 类似， do 可以创建变量，而第一个实参是一组变量的规格说明列表。每个元素可以是以下的形式

(variable initial update)

其中 variable 是一个符号， initial 和 update 是表达式。最初每个变量会被赋予 initial 表达式的值；每一次迭代时，会被赋予 update 表达式的值。在 show-squares 函数里， do 只创建了一个变量 i 。第一次迭代时， i 被赋与 start 的值，在接下来的迭代里， i 的值每次增加 1 。

第二个传给 do 的实参可包含一个或多个表达式。第一个表达式用来测试迭代是否结束。在上面的例子中，测试表达式是 (> i end) 。接下来在列表中的表达式会依序被求值，直到迭代结束。而最后一个值会被当作 do 的返回值来返回。所以 show-squares 总是返回 done 。

do 的剩余参数组成了循环的函数体。在每次迭代时，函数体会依序被求值。在每次迭代过程里，变量被更新，检查终止测试条件，接著（若测试失败）求值函数体。

作为对比，以下是递归版本的 show-squares ：

(defun show-squares (i end)
   (if (> i end)
     'done
     (progn
       (format t "~A ~A~%" i (* i i))
       (show-squares (+ i 1) end))))

唯一的新东西是 progn 。 progn 接受任意数量的表达式，依序求值，并返回最后一个表达式的值。

为了处理某些特殊情况， Common Lisp 有更简单的迭代操作符。举例来说，要遍历列表的元素，你可能会使用 dolist 。以下函数返回列表的长度：

(defun our-length (lst)
  (let ((len 0))
    (dolist (obj lst)
      (setf len (+ len 1)))
    len))

这里 dolist 接受这样形式的实参(variable expression)，跟着一个具有表达式的函数主体。函数主体会被求值，而变量相继与表达式所返回的列表元素绑定。因此上面的循环说，对于列表 lst 里的每一个 obj ，递增 len 。很显然这个函数的递归版本是：

(defun our-length (lst)
 (if (null lst)
     0
     (+ (our-length (cdr lst)) 1)))

也就是说，如果列表是空表，则长度为 0 ；否则长度就是对列表取 cdr 的长度加一。递归版本的 our-length 比较易懂，但由于它不是尾递归（tail-recursive）的形式 (见 13.2 节)，效率不是那么高。

2.14 函数作为对象 (Functions as Objects)¶

函数在 Lisp 里，和符号、字符串或列表一样，是稀松平常的对象。如果我们把函数的名字传给 function ，它会返回相关联的对象。和 quote 类似， function 是一个特殊操作符，所以我们无需引用（quote）它的实参：

> (function +)
#<Compiled-Function + 17BA4E>

这看起来很奇怪的返回值，是在典型的 Common Lisp 实现里，函数可能的打印表示法。

到目前为止，我们仅讨论过，不管是 Lisp 打印它们，还是我们输入它们，看起来都是一样的对象。但这个惯例对函数不适用。一个像是 + 的内置函数 ，在内部可能是一段机器语言代码（machine language code）。每个 Common Lisp 实现，可以选择任何它喜欢的外部表示法（external representation）。

如同我们可以用 ' 作为 quote 的缩写，也可以用 #' 作为 function 的缩写：

> #'+
#<Compiled-Function + 17BA4E>

这个缩写称之为升引号（sharp-quote）。

和别种对象类似，可以把函数当作实参传入。有个接受函数作为实参的函数是 apply 。apply 接受一个函数和实参列表，并返回把传入函数应用在实参列表的结果：

> (apply #'+ '(1 2 3))
6
> (+ 1 2 3)
6

apply 可以接受任意数量的实参，只要最后一个实参是列表即可：

> (apply #'+ 1 2 '(3 4 5))
15

函数 funcall 做的是一样的事情，但不需要把实参包装成列表。

> (funcall #'+ 1 2 3)
6

defun 宏，创建一个函数并给函数命名。但函数不需要有名字，而且我们不需要 defun 来定义他们。和大多数的 Lisp 对象一样，我们可以直接引用函数。

要直接引用整数，我们使用一系列的数字；要直接引用一个函数，我们使用所谓的lambda 表达式。一个 lambda 表达式是一个列表，列表包含符号 lambda ，接著是形参列表，以及由零个或多个表达式所组成的函数体。

下面的 lambda 表达式，表示一个接受两个数字并返回两者之和的函数：

(lambda (x y)
 (+ x y))

列表 (x y) 是形参列表，跟在它后面的是函数主体。

一个 lambda 表达式可以作为函数名。和普通的函数名称一样， lambda 表达式也可以是函数调用的第一个元素，

> ((lambda (x) (+ x 100)) 1)
101

而通过在 lambda 表达式前面贴上 #' ，我们得到对应的函数，

> (funcall #'(lambda (x) (+ x 100))
          1)

lambda 表示法除上述用途以外，还允许我们使用匿名函数。

2.15 类型 (Types)¶

Lisp 处理类型的方法非常灵活。在很多语言里，变量是有类型的，得声明变量的类型才能使用它。在 Common Lisp 里，数值才有类型，而变量没有。你可以想像每个对象，都贴有一个标明其类型的标签。这种方法叫做显式类型（manifest typing）。你不需要声明变量的类型，因为变量可以存放任何类型的对象。

虽然从来不需要声明类型，但出于效率的考量，你可能会想要声明变量的类型。类型声明在第 13.3 节时讨论。

Common Lisp 的内置类型，组成了一个类别的层级。对象总是不止属于一个类型。举例来说，数字 27 的类型，依普遍性的增加排序，依序是 fixnum 、 integer 、 rational 、 real 、 number 、 atom 和 t 类型。（数值类型将在第 9 章讨论。）类型 t 是所有类型的基类（supertype）。所以每个对象都属于 t 类型。

函数 typep 接受一个对象和一个类型，然后判定对象是否为该类型，是的话就返回真：

> (typep 27 'integer)
T

我们会在遇到各式内置类型时来讨论它们。

2.16 展望 (Looking Forward)¶

本章仅谈到 Lisp 的表面。然而，一种非比寻常的语言形象开始出现了。首先，这个语言用单一的语法，来表达所有的程序结构。语法基于列表，列表是一种 Lisp 对象。函数本身也是 Lisp 对象，函数能用列表来表示。而 Lisp 本身就是 Lisp 程序。几乎所有你定义的函数，与内置的 Lisp 函数没有任何区别。

如果你对这些概念还不太了解，不用担心。 Lisp 介绍了这么多新颖的概念，在你能驾驭它们之前，得花时间去熟悉它们。不过至少要了解一件事：在这些概念当中，有着优雅到令人吃惊的概念。

Richard Gabriel 曾经半开玩笑的说， C 是拿来写 Unix 的语言。我们也可以说， Lisp 是拿来写 Lisp 的语言。但这是两种不同的论述。一个可以用自己编写的语言和一种适合编写某些特定类型应用的语言，是有着本质上的不同。这开创了新的编程方法：你不但在语言之中编程，还把语言改善成适合程序的语言。如果你想了解 Lisp 编程的本质，理解这个概念是个好的开始。

Chapter 2 总结 (Summary)¶

1. Lisp 是一种交互式语言。如果你在顶层输入一个表达式， Lisp 会显示它的值。
2. Lisp 程序由表达式组成。表达式可以是原子，或一个由操作符跟着零个或多个实参的列表。前序表示法代表操作符可以有任意数量的实参。
3. Common Lisp 函数调用的求值规则： 依序对实参从左至右求值，接著把它们的值传入由操作符表示的函数。 quote 操作符有自己的求值规则，它完封不动地返回实参。
4. 除了一般的数据类型， Lisp 还有符号跟列表。由于 Lisp 程序是用列表来表示的，很轻松就能写出能编程的程序。
5. 三个基本的列表函数是 cons ，它创建一个列表； car ，它返回列表的第一个元素；以及 cdr ，它返回第一个元素之后的所有东西。
6. 在 Common Lisp 里， t 表示逻辑 真 ，而 nil 表示逻辑 假 。在逻辑的上下文里，任何非 nil 的东西都视为 真 。基本的条件式是 if 。 and 与 or 是相似的条件式。
7. Lisp 主要由函数所组成。可以用 defun 来定义新的函数。
8. 自己调用自己的函数是递归的。一个递归函数应该要被想成是过程，而不是机器。
9. 括号不是问题，因为程序员通过缩排来阅读与编写 Lisp 程序。
10. 基本的 I/O 函数是 read ，它包含了一个完整的 Lisp 语法分析器，以及 format ，它通过字符串模板来产生输出。
11. 你可以用 let 来创造新的局部变量，用 defparameter 来创造全局变量。
12. 赋值操作符是 setf 。它的第一个实参可以是一个表达式。
13. 函数式编程代表避免产生副作用，也是 Lisp 的主导思维。
14. 基本的迭代操作符是 do 。
15. 函数是 Lisp 的对象。可以被当成实参传入，并且可以用 lambda 表达式来表示。
16. 在 Lisp 里，是数值才有类型，而不是变量。

Chapter 2 习题 (Exercises)¶

1. 描述下列表达式求值之后的结果：

(a) (+ (- 5 1) (+ 3 7))

(b) (list 1 (+ 2 3))

(c) (if (listp 1) (+ 1 2) (+ 3 4))

(d) (list (and (listp 3) t) (+ 1 2))

2. 给出 3 种不同表示 (a b c) 的 cons 表达式 。
3. 使用 car 与 cdr 来定义一个函数，返回一个列表的第四个元素。
4. 定义一个函数，接受两个实参，返回两者当中较大的那个。
5. 这些函数做了什么？

(a) (defun enigma (x)
      (and (not (null x))
           (or (null (car x))
               (enigma (cdr x)))))

(b) (defun mystery (x y)
      (if (null y)
          nil
          (if (eql (car y) x)
              0
              (let ((z (mystery x (cdr y))))
                (and z (+ z 1))))))

6. 下列表达式， x 该是什么，才会得到相同的结果？

(a) > (car (x (cdr '(a (b c) d))))
    B
(b) > (x 13 (/ 1 0))
    13
(c) > (x #'list 1 nil)
    (1)

7. 只使用本章所介绍的操作符，定义一个函数，它接受一个列表作为实参，如果有一个元素是列表时，就返回真。
8. 给出函数的迭代与递归版本：

1. 接受一个正整数，并打印出数字数量的点。
2. 接受一个列表，并返回 a 在列表里所出现的次数。

9. 一位朋友想写一个函数，返回列表里所有非 nil 元素的和。他写了此函数的两个版本，但两个都不能工作。请解释每一个的错误在哪里，并给出正确的版本。

(a) (defun summit (lst)
      (remove nil lst)
      (apply #'+ lst))

(b) (defun summit (lst)
      (let ((x (car lst)))
        (if (null x)
            (summit (cdr lst))
            (+ x (summit (cdr lst))))))

脚注

3.1 构造 (Conses)¶

在 2.4 节我们介绍了 cons , car , 以及 cdr ，基本的 List 操作函数。 cons 真正所做的事情是，把两个对象结合成一个有两部分的对象，称之为 Cons 对象。概念上来说，一个 Cons 是一对指针；第一个是 car ，第二个是 cdr 。

Cons 对象提供了一个方便的表示法，来表示任何类型的对象。一个 Cons 对象里的一对指针，可以指向任何类型的对象，包括 Cons 对象本身。它利用到我们之后可以用 cons 来构造列表的可能性。

我们往往不会把列表想成是成对的，但它们可以这样被定义。任何非空的列表，都可以被视为一对由列表第一个元素及列表其余元素所组成的列表。 Lisp 列表体现了这个概念。我们使用 Cons 的一半来指向列表的第一个元素，然后用另一半指向列表其余的元素(可能是别的 Cons 或 nil )。 Lisp 的惯例是使用 car 代表列表的第一个元素，而用 cdr 代表列表的其余的元素。所以现在 car 是列表的第一个元素的同义词，而 cdr 是列表的其余的元素的同义词。列表不是不同的对象，而是像 Cons 这样的方式连结起来。

当我们想在 nil 上面建立东西时，

> (setf x (cons 'a nil))
(A)

图 3.1 一个元素的列表

产生的列表由一个 Cons 所组成，见图 3.1。这种表达 Cons 的方式叫做箱子表示法 (box notation)，因为每一个 Cons 是用一个箱子表示，内含一个 car 和 cdr 的指针。当我们调用 car 与 cdr 时，我们得到指针指向的地方：

> (car x)
A
> (cdr x)
NIL

当我们构造一个多元素的列表时，我们得到一串 Cons (a chain of conses):

> (setf y (list 'a 'b 'c))
(A B C)

产生的结构见图 3.2。现在当我们想得到列表的 cdr 时，它是一个两个元素的列表。

图 3.2 三个元素的列表

> (cdr y)
(B C)

在一个有多个元素的列表中， car 指针让你取得元素，而 cdr 让你取得列表内其余的东西。

一个列表可以有任何类型的对象作为元素，包括另一个列表：

> (setf z (list 'a (list 'b 'c) 'd))
(A (B C) D)

当这种情况发生时，它的结构如图 3.3 所示；第二个 Cons 的 car 指针也指向一个列表：

> (car (cdr z))
(B C)

图 3.3 嵌套列表

前两个我们构造的列表都有三个元素；只不过 z 列表的第二个元素也刚好是一个列表。像这样的列表称为嵌套列表，而像 y 这样的列表称之为平坦列表 (flatlist)。

如果参数是一个 Cons 对象，函数 consp 返回真。所以我们可以这样定义 listp :

(defun our-listp (x)
  (or (null x) (consp x)))

因为所有不是 Cons 对象的东西，就是一个原子 (atom)，判断式 atom 可以这样定义：

(defun our-atom (x) (not (consp x)))

注意， nil 既是一个原子，也是一个列表。

3.2 等式 (Equality)¶

每一次你调用 cons 时， Lisp 会配置一块新的内存给两个指针。所以如果我们用同样的参数调用 cons 两次，我们得到两个数值看起来一样，但实际上是两个不同的对象：

> (eql (cons 'a nil) (cons 'a nil))
NIL

如果我们也可以询问两个列表是否有相同元素，那就很方便了。 Common Lisp 提供了这种目的另一个判断式： equal 。而另一方面 eql 只有在它的参数是相同对象时才返回真，

> (setf x (cons 'a nil))
(A)
> (eql x x)
T

本质上 equal 若它的参数打印出的值相同时，返回真：

> (equal x (cons 'a nil))
T

这个判断式对非列表结构的别种对象也有效，但一种仅对列表有效的版本可以这样定义：

> (defun our-equal (x y)
    (or (eql x y)
        (and (consp x)
             (consp y)
             (our-equal (car x) (car y))
             (our-equal (cdr x) (cdr y)))))

这个定义意味着，如果某个 x 和 y 相等( eql )，那么他们也相等( equal )。

勘误: 这个版本的 our-equal 可以用在符号的列表 (list of symbols)，而不是列表 (list)。

3.3 为什么 Lisp 没有指针 (Why Lisp Has No Pointers)¶

一个理解 Lisp 的秘密之一是意识到变量是有值的，就像列表有元素一样。如同 Cons 对象有指针指向他们的元素，变量有指针指向他们的值。

你可能在别的语言中使用过显式指针 (explicitly pointer)。在 Lisp，你永远不用这么做，因为语言帮你处理好指针了。我们已经在列表看过这是怎么实现的。同样的事情发生在变量身上。举例来说，假设我们想要把两个变量设成同样的列表：

 > (setf x '(a b c))
(A B C)
> (setf y x)
(A B C)

图 3.4 两个变量设为相同的列表

当我们把 x 的值赋给 y 时，究竟发生什么事呢？内存中与 x 有关的位置并没有包含这个列表，而是一个指针指向它。当我们给 y 赋一个相同的值时， Lisp 复制的是指针，而不是列表。（图 3.4 显式赋值 x 给 y 后的结果）无论何时，你将某个变量的值赋给另个变量时，两个变量的值将会是 eql 的：

> (eql x y)
T

Lisp 没有指针的原因是因为每一个值，其实概念上来说都是一个指针。当你赋一个值给变量或将这个值存在数据结构中，其实被储存的是指向这个值的指针。当你要取得变量的值，或是存在数据结构中的内容时， Lisp 返回指向这个值的指针。但这都在台面下发生。你可以不加思索地把值放在结构里，或放“在”变量里。

为了效率的原因， Lisp 有时会选择一个折衷的表示法，而不是指针。举例来说，因为一个小整数所需的内存空间，少于一个指针所需的空间，一个 Lisp 实现可能会直接处理这个小整数，而不是用指针来处理。但基本要点是，程序员预设可以把任何东西放在任何地方。除非你声明你不愿这么做，不然你能够在任何的数据结构，存放任何类型的对象，包括结构本身。

3.4 建立列表 (Building Lists)¶

图 3.5 复制的结果

函数 copy-list 接受一个列表，然后返回此列表的复本。新的列表会有同样的元素，但是装在新的 Cons 对象里：

> (setf x '(a b c)
        y (copy-list x))
(A B C)

图 3.5 展示出结果的结构; 返回值像是有着相同乘客的新公交。我们可以把 copy-list 想成是这么定义的：

(defun our-copy-list (lst)
 (if (atom lst)
     lst
     (cons (car lst) (our-copy-list (cdr lst)))))

这个定义暗示着 x 与 (copy-list x) 会永远 equal ，并永远不 eql ，除非 x 是 NIL 。

最后，函数 append 返回任何数目的列表串接 (concatenation)：

> (append '(a b) '(c d) 'e)
(A B C D . E)

通过这么做，它复制所有的参数，除了最后一个

3.5 示例：压缩 (Example: Compression)¶

作为一个例子，这节将演示如何实现简单形式的列表压缩。这个算法有一个令人印象深刻的名字，游程编码(run-length encoding)。

(defun compress (x)
  (if (consp x)
      (compr (car x) 1 (cdr x))
      x))

(defun compr (elt n lst)
  (if (null lst)
      (list (n-elts elt n))
      (let ((next (car lst)))
        (if (eql next elt)
            (compr elt (+ n 1) (cdr lst))
            (cons (n-elts elt n)
                  (compr next 1 (cdr lst)))))))

(defun n-elts (elt n)
  (if (> n 1)
      (list n elt)
      elt))

图 3.6 游程编码 (Run-length encoding)：压缩

在餐厅的情境下，这个算法的工作方式如下。一个女服务生走向有四个客人的桌子。“你们要什么？” 她问。“我要特餐，” 第一个客人说。 “我也是，” 第二个客人说。“听起来不错，” 第三个客人说。每个人看着第四个客人。 “我要一个 cilantro soufflé，” 他小声地说。 (译注：蛋奶酥上面洒香菜跟酱料）

瞬息之间，女服务生就转身踩着高跟鞋走回柜台去了。 “三个特餐，” 她大声对厨师说，“还有一个香菜蛋奶酥。”

图 3.6 展示了如何实现这个压缩列表演算法。函数 compress 接受一个由原子组成的列表，然后返回一个压缩的列表：

> (compress '(1 1 1 0 1 0 0 0 0 1))
((3 1) 0 1 (4 0) 1)

当相同的元素连续出现好几次，这个连续出现的序列 (sequence)被一个列表取代，列表指明出现的次数及出现的元素。

主要的工作是由递归函数 compr 所完成。这个函数接受三个参数： elt ， 上一个我们看过的元素； n ，连续出现的次数；以及 lst ，我们还没检查过的部分列表。如果没有东西需要检查了，我们调用 n-elts 来取得 n elts 的表示法。如果 lst 的第一个元素还是 elt ，我们增加出现的次数 n 并继续下去。否则我们得到，到目前为止的一个压缩的列表，然后 cons 这个列表在 compr 处理完剩下的列表所返回的东西之上。

要复原一个压缩的列表，我们调用 uncompress (图 3.7)

> (uncompress '((3 1) 0 1 (4 0) 1))
(1 1 1 0 1 0 0 0 0 1)

(defun uncompress (lst)
  (if (null lst)
      nil
      (let ((elt (car lst))
            (rest (uncompress (cdr lst))))
        (if (consp elt)
            (append (apply #'list-of elt)
                    rest)
            (cons elt rest)))))

(defun list-of (n elt)
  (if (zerop n)
      nil
      (cons elt (list-of (- n 1) elt))))

图 3.7 游程编码 (Run-length encoding)：解压缩

这个函数递归地遍历这个压缩列表，逐字复制原子并调用 list-of ，展开成列表。

> (list-of 3 'ho)
(HO HO HO)

我们其实不需要自己写 list-of 。内置的 make-list 可以办到一样的事情 ── 但它使用了我们还没介绍到的关键字参数 (keyword argument)。

图 3.6 跟 3.7 这种写法不是一个有经验的Lisp 程序员用的写法。它的效率很差，它没有尽可能的压缩，而且它只对由原子组成的列表有效。在几个章节内，我们会学到解决这些问题的技巧。

载入程序

在这节的程序是我们第一个实质的程序。
当我们想要写超过数行的函数时，
通常我们会把程序写在一个文件，
然后使用 load 让 Lisp 读取函数的定义。
如果我们把图 3.6 跟 3.7 的程序，
存在一个文件叫做，“compress.lisp”然后输入

(load "compress.lisp")

到顶层，或多或少的，
我们会像在直接输入顶层一样得到同样的效果。

注意：在某些实现中，Lisp 文件的扩展名会是“.lsp”而不是“.lisp”。

3.6 存取 (Access)¶

Common Lisp 有额外的存取函数，它们是用 car 跟 cdr 所定义的。要找到列表特定位置的元素，我们可以调用 nth ，

> (nth 0 '(a b c))
A

而要找到第 n 个 cdr ，我们调用 nthcdr ：

> (nthcdr 2 '(a b c))
(C)

nth 与 nthcdr 都是零索引的 (zero-indexed); 即元素从 0 开始编号，而不是从 1 开始。在 Common Lisp 里，无论何时你使用一个数字来参照一个数据结构中的元素时，都是从 0 开始编号的。

两个函数几乎做一样的事; nth 等同于取 nthcdr 的 car 。没有检查错误的情况下， nthcdr 可以这么定义：

(defun our-nthcdr (n lst)
  (if (zerop n)
      lst
      (our-nthcdr (- n 1) (cdr lst))))

函数 zerop 仅在参数为零时，才返回真。

函数 last 返回列表的最后一个 Cons 对象：

> (last '(a b c))
(C)

这跟取得最后一个元素不一样。要取得列表的最后一个元素，你要取得 last 的 car 。

Common Lisp 定义了函数 first 直到 tenth 可以取得列表对应的元素。这些函数不是 零索引的 (zero-indexed)：

(second x) 等同于 (nth 1 x) 。

此外， Common Lisp 定义了像是 caddr 这样的函数，它是 cdr 的 cdr 的 car 的缩写 ( car of cdr of cdr )。所有这样形式的函数 cxr ，其中 x 是一个字符串，最多四个 a 或 d ，在 Common Lisp 里都被定义好了。使用 cadr 可能会有异常 (exception)产生，在所有人都可能会读的代码里使用这样的函数，可能不是个好主意。

3.7 映射函数 (Mapping Functions)¶

Common Lisp 提供了数个函数来对一个列表的元素做函数调用。最常使用的是 mapcar ，接受一个函数以及一个或多个列表，并返回把函数应用至每个列表的元素的结果，直到有的列表没有元素为止：

> (mapcar #'(lambda (x) (+ x 10))
          '(1 2 3))
(11 12 13)

> (mapcar #'list
          '(a b c)
          '(1 2 3 4))
((A 1) (B 2) (C 3))

相关的 maplist 接受同样的参数，将列表的渐进的下一个 cdr 传入函数。

> (maplist #'(lambda (x) x)
           '(a b c))
((A B C) (B C) (C))

其它的映射函数，包括 mapc 我们在 89 页讨论（译注：5.4 节最后），以及 mapcan 在 202 页（译注：12.4 节最后）讨论。

3.8 树 (Trees)¶

Cons 对象可以想成是二叉树， car 代表左子树，而 cdr 代表右子树。举例来说，列表

(a (b c) d) 也是一棵由图 3.8 所代表的树。 （如果你逆时针旋转 45 度，你会发现跟图 3.3 一模一样）

图 3.8 二叉树 (Binary Tree)

Common Lisp 有几个内置的操作树的函数。举例来说， copy-tree 接受一个树，并返回一份副本。它可以这么定义：

(defun our-copy-tree (tr)
  (if (atom tr)
       tr
       (cons (our-copy-tree (car tr))
             (our-copy-tree (cdr tr)))))

把这跟 36 页的 copy-list 比较一下； copy-tree 复制每一个 Cons 对象的 car 与 cdr ，而 copy-list 仅复制 cdr 。

没有内部节点的二叉树没有太大的用处。 Common Lisp 包含了操作树的函数，不只是因为我们需要树这个结构，而是因为我们需要一种方法，来操作列表及所有内部的列表。举例来说，假设我们有一个这样的列表：

(and (integerp x) (zerop (mod x 2)))

而我们想要把各处的 x 都换成 y 。调用 substitute 是不行的，它只能替换序列 (sequence)中的元素：

> (substitute 'y 'x '(and (integerp x) (zerop (mod x 2))))
(AND (INTEGERP X) (ZEROP (MOD X 2)))

这个调用是无效的，因为列表有三个元素，没有一个元素是 x 。我们在这所需要的是 subst ，它替换树之中的元素。

> (subst 'y 'x '(and (integerp x) (zerop (mod x 2))))
(AND (INTEGERP Y) (ZEROP (MOD Y 2)))

如果我们定义一个 subst 的版本，它看起来跟 copy-tree 很相似：

> (defun our-subst (new old tree)
    (if (eql tree old)
        new
        (if (atom tree)
            tree
            (cons (our-subst new old (car tree))
                  (our-subst new old (cdr tree))))))

操作树的函数通常有这种形式， car 与 cdr 同时做递归。这种函数被称之为是 双重递归 (doubly recursive)。

3.9 理解递归 (Understanding Recursion)¶

学生在学习递归时，有时候是被鼓励在纸上追踪 (trace)递归程序调用 (invocation)的过程。 (288页「译注：附录 A 追踪与回溯」可以看到一个递归函数的追踪过程。)但这种练习可能会误导你：一个程序员在定义一个递归函数时，通常不会特别地去想函数的调用顺序所导致的结果。

如果一个人总是需要这样子思考程序，递归会是艰难的、没有帮助的。递归的优点是它精确地让我们更抽象地来设计算法。你不需要考虑真正函数时所有的调用过程，就可以判断一个递归函数是否是正确的。

要知道一个递归函数是否做它该做的事，你只需要问，它包含了所有的情况吗？举例来说，下面是一个寻找列表长度的递归函数：

> (defun len (lst)
    (if (null lst)
        0
        (+ (len (cdr lst)) 1)))

我们可以借由检查两件事情，来确信这个函数是正确的：

1. 对长度为 0 的列表是有效的。
2. 给定它对于长度为 n 的列表是有效的，它对长度是 n+1 的列表也是有效的。

如果这两点是成立的，我们知道这个函数对于所有可能的列表都是正确的。

我们的定义显然地满足第一点：如果列表( lst ) 是空的( nil )，函数直接返回 0 。现在假定我们的函数对长度为 n 的列表是有效的。我们给它一个 n+1 长度的列表。这个定义说明了，函数会返回列表的 cdr 的长度再加上 1 。 cdr 是一个长度为 n 的列表。我们经由假定可知它的长度是 n 。所以整个列表的长度是 n+1 。

我们需要知道的就是这些。理解递归的秘密就像是处理括号一样。你怎么知道哪个括号对上哪个？你不需要这么做。你怎么想像那些调用过程？你不需要这么做。

更复杂的递归函数，可能会有更多的情况需要讨论，但是流程是一样的。举例来说， 41 页的 our-copy-tree ，我们需要讨论三个情况： 原子，单一的 Cons 对象， n+1 的 Cons 树。

第一个情况（长度零的列表）称之为基本用例( base case )。当一个递归函数不像你想的那样工作时，通常是处理基本用例就错了。下面这个不正确的 member 定义，是一个常见的错误，整个忽略了基本用例：

(defun our-member (obj lst)
  (if (eql (car lst) obj)
      lst
      (our-member obj (cdr lst))))

我们需要初始一个 null 测试，确保在到达列表底部时，没有找到目标时要停止递归。如果我们要找的对象没有在列表里，这个版本的 member 会陷入无穷循环。附录 A 更详细地讨论了这种问题。

能够判断一个递归函数是否正确只不过是理解递归的上半场，下半场是能够写出一个做你想做的事情的递归函数。 6.9 节讨论了这个问题。

3.10 集合 (Sets)¶

列表是表示小集合的好方法。列表中的每个元素都代表了一个集合的成员：

> (member 'b '(a b c))
(B C)

当 member 要返回“真”时，与其仅仅返回 t ，它返回由寻找对象所开始的那部分。逻辑上来说，一个 Cons 扮演的角色和 t 一样，而经由这么做，函数返回了更多资讯。

一般情况下， member 使用 eql 来比较对象。你可以使用一种叫做关键字参数的东西来重写缺省的比较方法。多数的 Common Lisp 函数接受一个或多个关键字参数。这些关键字参数不同的地方是，他们不是把对应的参数放在特定的位置作匹配，而是在函数调用中用特殊标签，称为关键字，来作匹配。一个关键字是一个前面有冒号的符号。

一个 member 函数所接受的关键字参数是 :test 参数。

如果你在调用 member 时，传入某个函数作为 :test 参数，那么那个函数就会被用来比较是否相等，而不是用 eql 。所以如果我们想找到一个给定的对象与列表中的成员是否相等( equal )，我们可以：

> (member '(a) '((a) (z)) :test #'equal)
((A) (Z))

关键字参数总是选择性添加的。如果你在一个调用中包含了任何的关键字参数，他们要摆在最后; 如果使用了超过一个的关键字参数，摆放的顺序无关紧要。

另一个 member 接受的关键字参数是 :key 参数。借由提供这个参数，你可以在作比较之前，指定一个函数运用在每一个元素：

> (member 'a '((a b) (c d)) :key #'car)
((A B) (C D))

在这个例子里，我们询问是否有一个元素的 car 是 a 。

如果我们想要使用两个关键字参数，我们可以使用其中一个顺序。下面这两个调用是等价的：

> (member 2 '((1) (2)) :key #'car :test #'equal)
((2))
> (member 2 '((1) (2)) :test #'equal :key #'car)
((2))

两者都询问是否有一个元素的 car 等于( equal ) 2。

如果我们想要找到一个元素满足任意的判断式像是── oddp ，奇数返回真──我们可以使用相关的 member-if ：

> (member-if #'oddp '(2 3 4))
(3 4)

我们可以想像一个限制性的版本 member-if 是这样写成的：

(defun our-member-if (fn lst)
  (and (consp lst)
       (if (funcall fn (car lst))
           lst
           (our-member-if fn (cdr lst)))))

函数 adjoin 像是条件式的 cons 。它接受一个对象及一个列表，如果对象还不是列表的成员，才构造对象至列表上。

> (adjoin 'b '(a b c))
(A B C)
> (adjoin 'z '(a b c))
(Z A B C)

通常的情况下它接受与 member 函数同样的关键字参数。

集合论中的并集 (union)、交集 (intersection)以及补集 (complement)的实现，是由函数 union 、 intersection 以及 set-difference 。

这些函数期望两个（正好 2 个）列表（一样接受与 member 函数同样的关键字参数）。

> (union '(a b c) '(c b s))
(A C B S)
> (intersection '(a b c) '(b b c))
(B C)
> (set-difference '(a b c d e) '(b e))
(A C D)

因为集合中没有顺序的概念，这些函数不需要保留原本元素在列表被找到的顺序。举例来说，调用 set-difference 也有可能返回 (d c a) 。

3.11 序列 (Sequences)¶

另一种考虑一个列表的方式是想成一系列有特定顺序的对象。在 Common Lisp 里，序列( sequences )包括了列表与向量 (vectors)。本节介绍了一些可以运用在列表上的序列函数。更深入的序列操作在 4.4 节讨论。

函数 length 返回序列中元素的数目。

> (length '(a b c))
3

我们在 24 页 (译注：2.13节 our-length )写过这种函数的一个版本（仅可用于列表）。

要复制序列的一部分，我们使用 subseq 。第二个（需要的）参数是第一个开始引用进来的元素位置，第三个（选择性）参数是第一个不引用进来的元素位置。

> (subseq '(a b c d) 1 2)
(B)
>(subseq '(a b c d) 1)
(B C D)

如果省略了第三个参数，子序列会从第二个参数给定的位置引用到序列尾端。

函数 reverse 返回与其参数相同元素的一个序列，但顺序颠倒。

> (reverse '(a b c))
(C B A)

一个回文 (palindrome) 是一个正读反读都一样的序列 —— 举例来说， (abba) 。如果一个回文有偶数个元素，那么后半段会是前半段的镜射 (mirror)。使用 length 、 subseq 以及 reverse ，我们可以定义一个函数

(defun mirror? (s)
  (let ((len (length s)))
    (and (evenp len)
         (let ((mid (/ len 2)))
           (equal (subseq s 0 mid)
                  (reverse (subseq s mid)))))))

来检测是否是回文：

> (mirror? '(a b b a))
T

Common Lisp 有一个内置的排序函数叫做 sort 。它接受一个序列及一个比较两个参数的函数，返回一个有同样元素的序列，根据比较函数来排序：

> (sort '(0 2 1 3 8) #'>)
(8 3 2 1 0)

你要小心使用 sort ，因为它是破坏性的(destructive)。考虑到效率的因素， sort 被允许修改传入的序列。所以如果你不想你本来的序列被改动，传入一个副本。

使用 sort 及 nth ，我们可以写一个函数，接受一个整数 n ，返回列表中第 n 大的元素：

(defun nthmost (n lst)
  (nth (- n 1)
       (sort (copy-list lst) #'>)))

我们把整数减一因为 nth 是零索引的，但如果 nthmost 是这样的话，会变得很不直观。

(nthmost 2 '(0 2 1 3 8))

多努力一点，我们可以写出这个函数的一个更有效率的版本。

函数 every 和 some 接受一个判断式及一个或多个序列。当我们仅输入一个序列时，它们测试序列元素是否满足判断式：

> (every #'oddp '(1 3 5))
T
> (some #'evenp '(1 2 3))
T

如果它们输入多于一个序列时，判断式必须接受与序列一样多的元素作为参数，而参数从所有序列中一次提取一个：

> (every #'> '(1 3 5) '(0 2 4))
T

如果序列有不同的长度，最短的那个序列，决定需要测试的次数。

3.12 栈 (Stacks)¶

用 Cons 对象来表示的列表，很自然地我们可以拿来实现下推栈 (pushdown stack)。这太常见了，以致于 Common Lisp 提供了两个宏给堆使用： (push x y) 把 x 放入列表 y 的前端。而 (pop x) 则是将列表 x 的第一个元素移除，并返回这个元素。

两个函数都是由 setf 定义的。如果参数是常数或变量，很简单就可以翻译出对应的函数调用。

表达式

(push obj lst)

等同于

(setf lst (cons obj lst))

而表达式

(pop lst)

等同于

(let ((x (car lst)))
  (setf lst (cdr lst))
  x)

所以，举例来说：

> (setf x '(b))
(B)
> (push 'a x)
(A B)
> x
(A B)
> (setf y x)
(A B)
> (pop x)
(A)
> x
(B)
> y
(A B)

以上，全都遵循上述由 setf 所给出的相等式。图 3.9 展示了这些表达式被求值后的结构。

图 3.9 push 及 pop 的效果

你可以使用 push 来定义一个给列表使用的互动版 reverse 。

(defun our-reverse (lst)
  (let ((acc nil))
    (dolist (elt lst)
      (push elt acc))
    acc))

在这个版本，我们从一个空列表开始，然后把 lst 的每一个元素放入空表里。等我们完成时，lst 最后一个元素会在最前端。

pushnew 宏是 push 的变种，使用了 adjoin 而不是 cons ：

 > (let ((x '(a b)))
     (pushnew 'c x)
     (pushnew 'a x)
     x)
(C A B)

在这里， c 被放入列表，但是 a 没有，因为它已经是列表的一个成员了。

3.13 点状列表 (Dotted Lists)¶

调用 list 所构造的列表，这种列表精确地说称之为正规列表(properlist )。一个正规列表可以是 NIL 或是 cdr 是正规列表的 Cons 对象。也就是说，我们可以定义一个只对正规列表返回真的判断式： [3]

(defun proper-list? (x)
  (or (null x)
      (and (consp x)
           (proper-list? (cdr x)))))

至目前为止，我们构造的列表都是正规列表。

然而， cons 不仅是构造列表。无论何时你需要一个具有两个字段 (field)的列表，你可以使用一个 Cons 对象。你能够使用 car 来参照第一个字段，用 cdr 来参照第二个字段。

> (setf pair (cons 'a 'b))
(A . B)

因为这个 Cons 对象不是一个正规列表，它用点状表示法来显示。在点状表示法，每个 Cons 对象的 car 与 cdr 由一个句点隔开来表示。这个 Cons 对象的结构展示在图 3.10 。

图3.10 一个成对的 Cons 对象 (A cons used as a pair)

一个非正规列表的 Cons 对象称之为点状列表 (dotted list)。这不是个好名字，因为非正规列表的 Cons 对象通常不是用来表示列表： (a . b) 只是一个有两部分的数据结构。

你也可以用点状表示法表示正规列表，但当 Lisp 显示一个正规列表时，它会使用普通的列表表示法：

> '(a . (b . (c . nil)))
(A B C)

顺道一提，注意列表由点状表示法与图 3.2 箱子表示法的关联性。

还有一个过渡形式 (intermediate form)的表示法，介于列表表示法及纯点状表示法之间，对于 cdr 是点状列表的 Cons 对象：

> (cons 'a (cons 'b (cons 'c 'd)))
(A B C . D)

图 3.11 一个点状列表 (A dotted list)

这样的 Cons 对象看起来像正规列表，除了最后一个 cdr 前面有一个句点。这个列表的结构展示在图 3.11 ; 注意它跟图3.2 是多么的相似。

所以实际上你可以这么表示列表 (a b) ，

(a . (b . nil))
(a . (b))
(a b . nil)
(a b)

虽然 Lisp 总是使用后面的形式，来显示这个列表。

3.14 关联列表 (Assoc-lists)¶

用 Cons 对象来表示映射 (mapping)也是很自然的。一个由 Cons 对象组成的列表称之为关联列表(assoc-listor alist)。这样的列表可以表示一个翻译的集合，举例来说：

> (setf trans '((+ . "add") (- . "subtract")))
((+ . "add") (- . "subtract"))

关联列表很慢，但是在初期的程序中很方便。 Common Lisp 有一个内置的函数 assoc ，用来取出在关联列表中，与给定的键值有关联的 Cons 对：

> (assoc '+ trans)
(+ . "add")
> (assoc '* trans)
NIL

如果 assoc 没有找到要找的东西时，返回 nil 。

我们可以定义一个受限版本的 assoc ：

(defun our-assoc (key alist)
  (and (consp alist)
       (let ((pair (car alist)))
        (if (eql key (car pair))
            pair
            (our-assoc key (cdr alist))))))

和 member 一样，实际上的 assoc 接受关键字参数，包括 :test 和 :key 。 Common Lisp 也定义了一个 assoc-if 之于 assoc ，如同 member-if 之于 member 一样。

3.15 示例：最短路径 (Example: Shortest Path)¶

图 3.12 包含一个搜索网络中最短路径的程序。函数 shortest-path 接受一个起始节点，目的节点以及一个网络，并返回最短路径，如果有的话。

在这个范例中，节点用符号表示，而网络用含以下元素形式的关联列表来表示：

(node . neighbors)

所以由图 3.13 展示的最小网络 (minimal network)可以这样来表示：

(setf min '((a b c) (b c) (c d)))

(defun shortest-path (start end net)
  (bfs end (list (list start)) net))

(defun bfs (end queue net)
  (if (null queue)
      nil
      (let ((path (car queue)))
        (let ((node (car path)))
          (if (eql node end)
              (reverse path)
              (bfs end
                   (append (cdr queue)
                           (new-paths path node net))
                   net))))))

(defun new-paths (path node net)
  (mapcar #'(lambda (n)
              (cons n path))
          (cdr (assoc node net))))

图 3.12 广度优先搜索(breadth-first search)

图 3.13 最小网络

要找到从节点 a 可以到达的节点，我们可以：

> (cdr (assoc 'a min))
(B C)

图 3.12 程序使用广度优先的方式搜索网络。要使用广度优先搜索，你需要维护一个含有未探索节点的队列。每一次你到达一个节点，检查这个节点是否是你要的。如果不是，你把这个节点的子节点加入队列的尾端，并从队列起始选一个节点，从这继续搜索。借由总是把较深的节点放在队列尾端，我们确保网络一次被搜索一层。

图 3.12 中的代码较不复杂地表示这个概念。我们不仅想要找到节点，还想保有我们怎么到那的纪录。所以与其维护一个具有节点的队列 (queue)，我们维护一个已知路径的队列，每个已知路径都是一列节点。当我们从队列取出一个元素继续搜索时，它是一个含有队列前端节点的列表，而不只是一个节点而已。

函数 bfs 负责搜索。起初队列只有一个元素，一个表示从起点开始的路径。所以 shortest-path 调用 bfs ，并传入 (list (list start)) 作为初始队列。

bfs 函数第一件要考虑的事是，是否还有节点需要探索。如果队列为空， bfs 返回 nil 指出没有找到路径。如果还有节点需要搜索， bfs 检查队列前端的节点。如果节点的 car 部分是我们要找的节点，我们返回这个找到的路径，并且为了可读性的原因我们反转它。如果我们没有找到我们要找的节点，它有可能在现在节点之后，所以我们把它的子节点（或是每一个子路径）加入队列尾端。然后我们递回地调用 bfs 来继续搜寻剩下的队列。

因为 bfs 广度优先地搜索，第一个找到的路径会是最短的，或是最短之一：

> (shortest-path 'a 'd min)
(A C D)

这是队列在我们连续调用 bfs 看起来的样子：

((A))
((B A) (C A))
((C A) (C B A))
((C B A) (D C A))
((D C A) (D C B A))

在队列中的第二个元素变成下一个队列的第一个元素。队列的第一个元素变成下一个队列尾端元素的 cdr 部分。

在图 3.12 的代码不是搜索一个网络最快的方法，但它给出了列表具有多功能的概念。在这个简单的程序中，我们用三种不同的方式使用了列表：我们使用一个符号的列表来表示路径，一个路径的列表来表示在广度优先搜索中的队列 [4] ，以及一个关联列表来表示网络本身。

3.16 垃圾 (Garbages)¶

有很多原因可以使列表变慢。列表提供了顺序存取而不是随机存取，所以列表取出一个指定的元素比数组慢，同样的原因，录音带取出某些东西比在光盘上慢。电脑内部里， Cons 对象倾向于用指针表示，所以走访一个列表意味着走访一系列的指针，而不是简单地像数组一样增加索引值。但这两个所花的代价与配置及回收 Cons 核 (cons cells)比起来小多了。

自动内存管理(Automatic memory management)是 Lisp 最有价值的特色之一。 Lisp 系统维护着一段內存称之为堆(Heap)。系统持续追踪堆当中没有使用的内存，把这些内存发放给新产生的对象。举例来说，函数 cons ，返回一个新配置的 Cons 对象。从堆中配置内存有时候通称为 consing 。

如果内存永远没有释放， Lisp 会因为创建新对象把内存用完，而必须要关闭。所以系统必须周期性地通过搜索堆 (heap)，寻找不需要再使用的内存。不需要再使用的内存称之为垃圾 (garbage)，而清除垃圾的动作称为垃圾回收 (garbage collection或 GC)。

垃圾是从哪来的？让我们来创造一些垃圾：

> (setf lst (list 'a 'b 'c))
(A B C)
> (setf lst nil)
NIL

一开始我们调用 list ， list 调用 cons ，在堆上配置了一个新的 Cons 对象。在这个情况我们创出三个 Cons 对象。之后当我们把 lst 设为 nil ，我们没有任何方法可以再存取 lst ，列表 (a b c) 。 [5]

因为我们没有任何方法再存取列表，它也有可能是不存在的。我们不再有任何方式可以存取的对象叫做垃圾。系统可以安全地重新使用这三个 Cons 核。

这种管理內存的方法，给程序員带来极大的便利性。你不用显式地配置 (allocate)或释放 (dellocate)內存。这也表示了你不需要处理因为这么做而可能产生的臭虫。內存泄漏 (Memory leaks)以及迷途指针 (dangling pointer)在 Lisp 中根本不可能发生。

但是像任何的科技进步，如果你不小心的话，自动內存管理也有可能对你不利。使用及回收堆所带来的代价有时可以看做 cons 的代价。这是有理的，除非一个程序从来不丢弃任何东西，不然所有的 Cons 对象终究要变成垃圾。 Consing 的问题是，配置空间与清除內存，与程序的常规运作比起来花费昂贵。近期的研究提出了大幅改善內存回收的演算法，但是 consing 总是需要代价的，在某些现有的 Lisp 系统中，代价是昂贵的。

除非你很小心，不然很容易写出过度显式创建 cons 对象的程序。举例来说， remove 需要复制所有的 cons 核，直到最后一个元素从列表中移除。你可以借由使用破坏性的函数避免某些 consing，它试着去重用列表的结构作为参数传给它们。破坏性函数会在 12.4 节讨论。

当写出 cons 很多的程序是如此简单时，我们还是可以写出不使用 cons 的程序。典型的方法是写出一个纯函数风格，使用很多列表的第一版程序。当程序进化时，你可以在代码的关键部分使用破坏性函数以及/或别种数据结构。但这很难给出通用的建议，因为有些 Lisp 实现，內存管理处理得相当好，以致于使用 cons 有时比不使用 cons 还快。这整个议题在 13.4 做更进一步的细部讨论。

无论如何 consing 在原型跟实验时是好的。而且如果你利用了列表给你带来的灵活性，你有较高的可能写出后期可存活下来的程序。

Chapter 3 总结 (Summary)¶

1. 一个 Cons 是一个含两部分的数据结构。列表用链结在一起的 Cons 组成。
2. 判断式 equal 比 eql 来得不严谨。基本上，如果传入参数印出来的值一样时，返回真。
3. 所有 Lisp 对象表现得像指针。你永远不需要显式操作指针。
4. 你可以使用 copy-list 复制列表，并使用 append 来连接它们的元素。
5. 游程编码是一个餐厅中使用的简单压缩演算法。
6. Common Lisp 有由 car 与 cdr 定义的多种存取函数。
7. 映射函数将函数应用至逐项的元素，或逐项的列表尾端。
8. 嵌套列表的操作有时被考虑为树的操作。
9. 要判断一个递归函数是否正确，你只需要考虑是否包含了所有情况。
10. 列表可以用来表示集合。数个内置函数把列表当作集合。
11. 关键字参数是选择性的，并不是由位置所识别，是用符号前面的特殊标签来识别。
12. 列表是序列的子类型。 Common Lisp 有大量的序列函数。
13. 一个不是正规列表的 Cons 称之为点状列表。
14. 用 cons 对象作为元素的列表，可以拿来表示对应关系。这样的列表称为关联列表(assoc-lists)。
15. 自动内存管理拯救你处理内存配置的烦恼，但制造过多的垃圾会使程序变慢。

Chapter 3 习题 (Exercises)¶

1. 用箱子表示法表示以下列表：

(a) (a b (c d))
(b) (a (b (c (d))))
(c) (((a b) c) d)
(d) (a (b . c) d)

2. 写一个保留原本列表中元素顺序的 union 版本：

> (new-union '(a b c) '(b a d))
(A B C D)

3. 定义一个函数，接受一个列表并返回一个列表，指出相等元素出现的次数，并由最常见至最少见的排序：

> (occurrences '(a b a d a c d c a))
((A . 4) (C . 2) (D . 2) (B . 1))

4. 为什么 (member '(a) '((a) (b))) 返回 nil？
5. 假设函数 pos+ 接受一个列表并返回把每个元素加上自己的位置的列表：

> (pos+ '(7 5 1 4))
(7 6 3 7)

使用 (a) 递归 (b) 迭代 (c) mapcar 来定义这个函数。

6. 经过好几年的审议，政府委员会决定列表应该由 cdr 指向第一个元素，而 car 指向剩下的列表。定义符合政府版本的以下函数：

(a) cons
(b) list
(c) length (for lists)
(d) member (for lists; no keywords)

勘误: 要解决 3.6 (b)，你需要使用到 6.3 节的参数 &rest 。

7. 修改图 3.6 的程序，使它使用更少 cons 核。 （提示：使用点状列表）
8. 定义一个函数，接受一个列表并用点状表示法印出：

> (showdots '(a b c))
(A . (B . (C . NIL)))
NIL

9. 写一个程序来找到 3.15 节里表示的网络中，最长有限的路径 (不重复)。网络可能包含循环。

脚注

4.1 数组 (Array)¶

在 Common Lisp 里，你可以调用 make-array 来构造一个数组，第一个实参为一个指定数组维度的列表。要构造一个 2 x 3 的数组，我们可以：

> (setf arr (make-array '(2 3) :initial-element nil))
#<Simple-Array T (2 3) BFC4FE>

Common Lisp 的数组至少可以达到七个维度，每个维度至少可以容纳 1023 个元素。

:initial-element 实参是选择性的。如果有提供这个实参，整个数组会用这个值作为初始值。若试著取出未初始化的数组内的元素，其结果为未定义（undefined）。

用 aref 取出数组内的元素。与 Common Lisp 的存取函数一样， aref 是零索引的（zero-indexed）：

> (aref arr 0 0)
NIL

要替换数组的某个元素，我们使用 setf 与 aref ：

> (setf (aref arr 0 0) 'b)
B
> (aref arr 0 0)
B

要表示字面常量的数组（literal array），使用 #na 语法，其中 n 是数组的维度。举例来说，我们可以这样表示 arr 这个数组：

#2a((b nil nil) (nil nil nil))

如果全局变量 *print-array* 为真，则数组会用以下形式来显示：

> (setf *print-array* t)
T
> arr
#2A((B NIL NIL) (NIL NIL NIL))

如果我们只想要一维的数组，你可以给 make-array 第一个实参传一个整数，而不是一个列表：

> (setf vec (make-array 4 :initial-element nil))
#(NIL NIL NIL NIL)

一维数组又称为向量（vector）。你可以通过调用 vector 来一步骤构造及填满向量，向量的元素可以是任何类型：

> (vector "a" 'b 3)
#("a" b 3)

字面常量的数组可以表示成 #na ，字面常量的向量也可以用这种语法表达。

可以用 aref 来存取向量，但有一个更快的函数叫做 svref ，专门用来存取向量。

> (svref vec 0)
NIL

在 svref 内的 “sv” 代表“简单向量”（“simple vector”），所有的向量缺省是简单向量。 [1]

4.2 示例：二叉搜索 (Example: Binary Search)¶

作为一个示例，这小节演示如何写一个在排序好的向量里搜索对象的函数。如果我们知道一个向量是排序好的，我们可以比（65页） find 做的更好， find 必须依序检查每一个元素。我们可以直接跳到向量中间开始找。如果中间的元素是我们要找的对象，搜索完毕。要不然我们持续往左半部或往右半部搜索，取决于对象是小于或大于中间的元素。

图 4.1 包含了一个这么工作的函数。其实这两个函数： bin-search 设置初始范围及发送控制信号给 finder ， finder 寻找向量 vec 内 obj 是否介于 start 及 end 之间。

(defun bin-search (obj vec)
  (let ((len (length vec)))
    (and (not (zerop len))
         (finder obj vec 0 (- len 1)))))

(defun finder (obj vec start end)
  (let ((range (- end start)))
    (if (zerop range)
        (if (eql obj (aref vec start))
            obj
            nil)
        (let ((mid (+ start (round (/ range 2)))))
          (let ((obj2 (aref vec mid)))
            (if (< obj obj2)
                (finder obj vec start (- mid 1))
                (if (> obj obj2)
                    (finder obj vec (+ mid 1) end)
                    obj)))))))

图 4.1: 搜索一个排序好的向量

如果要找的 range 缩小至一个元素，而如果这个元素是 obj 的话，则 finder 直接返回这个元素，反之返回 nil 。如果 range 大于 1 ，我们設置 middle ( round 返回离实参最近的整数) 為 obj2 。如果 obj 小于 obj2 ，则递归地往向量的左半部寻找。如果 obj 大于 obj2 ，则递归地往向量的右半部寻找。剩下的一个选择是 obj=obj2 ，在这个情况我们找到要找的元素，直接返回这个元素。

如果我们插入下面这行至 finder 的起始处：

(format t "~A~%" (subseq vec start (+ end 1)))

我们可以观察被搜索的元素的数量，是每一步往左减半的：

> (bin-search 3 #(0 1 2 3 4 5 6 7 8 9))
#(0 1 2 3 4 5 6 7 8 9)
#(0 1 2 3)
#(3)
3

4.3 字符与字符串 (Strings and Characters)¶

字符串是字符组成的向量。我们用一系列由双引号包住的字符，来表示一个字符串常量，而字符 c 用 #\c 表示。

每个字符都有一个相关的整数 ── 通常是 ASCII 码，但不一定是。在多数的 Lisp 实现里，函数 char-code 返回与字符相关的数字，而 code-char 返回与数字相关的字符。

字符比较函数 char< （小于）， char<= （小于等于)， char= （等于)， char>= （大于等于) ， char> （大于)，以及 char/= （不同)。他们的工作方式和 146 页（译注 9.3 节)比较数字用的操作符一样。

> (sort "elbow" #'char<)
"below"

由于字符串是字符向量，序列与数组的函数都可以用在字符串。你可以用 aref 来取出元素，举例来说，

> (aref "abc" 1)
#\b

但针对字符串可以使用更快的 char 函数：

> (char "abc" 1)
#\b

可以使用 setf 搭配 char （或 aref ）来替换字符串的元素：

> (let ((str (copy-seq "Merlin")))
   (setf (char str 3) #\k)
   str)

如果你想要比较两个字符串，你可以使用通用的 equal 函数，但还有一个比较函数，是忽略字母大小写的 string-equal ：

> (equal "fred" "fred")
T
> (equal "fred" "Fred")
NIL
>(string-equal "fred" "Fred")
T

Common Lisp 提供大量的操控、比较字符串的函数。收录在附录 D，从 364 页开始。

有许多方式可以创建字符串。最普遍的方式是使用 format 。将第一个参数设为 nil 来调用 format ，使它返回一个原本会印出来的字符串：

> (format nil "~A or ~A" "truth" "dare")
"truth or dare"

但若你只想把数个字符串连结起来，你可以使用 concatenate ，它接受一个特定类型的符号，加上一个或多个序列：

> (concatenate 'string "not " "to worry")
"not to worry"

4.4 序列 (Sequences)¶

在 Common Lisp 里，序列类型包含了列表与向量（因此也包含了字符串）。有些用在列表的函数，实际上是序列函数，包括 remove 、 length 、 subseq 、 reverse 、 sort 、 every 以及 some 。所以 46 页（译注 3.11 小节的 mirror? 函数）我们所写的函数，也可以用在其他种类的序列上：

> (mirror? "abba")
T

我们已经看过四种用来取出序列元素的函数： 给列表使用的 nth ， 给向量使用的 aref 及 svref ，以及给字符串使用的 char 。 Common Lisp 也提供了通用的 elt ，对任何种类的序列都有效：

> (elt '(a b c) 1)
B

针对特定类型的序列，特定的存取函数会比较快，所以使用 elt 是没有意义的，除非在代码当中，有需要支持通用序列的地方。

使用 elt ，我们可以写一个针对向量来说更有效率的 mirror? 版本：

(defun mirror? (s)
  (let ((len (length s)))
    (and (evenp len)
         (do ((forward 0 (+ forward 1))
              (back (- len 1) (- back 1)))
             ((or (> forward back)
                  (not (eql (elt s forward)
                            (elt s back))))
              (> forward back))))))

这个版本也可用在列表，但这个实现更适合给向量使用。频繁的对列表调用 elt 的代价是昂贵的，因为列表仅允许顺序存取。而向量允许随机存取，从任何元素来存取每一个元素都是廉价的。

许多序列函数接受一个或多个，由下表所列的标准关键字参数：

一个接受所有关键字参数的函数是 position ，返回序列中一个元素的位置，未找到元素时则返回 nil 。我们使用 position 来演示关键字参数所扮演的角色。

> (position #\a "fantasia")
1
> (position #\a "fantasia" :start 3 :end 5)
4

第二个例子我们要找在第四个与第六个字符间，第一个 a 所出现的位置。 :start 关键字参数是第一个被考虑的元素位置，缺省是序列的第一个元素。 :end 关键字参数，如果有给的话，是第一个不被考虑的元素位置。

如果我们给入 :from-end 关键字参数，

> (position #\a "fantasia" :from-end t)
7

我们得到最靠近结尾的 a 的位置。但位置是像平常那样计算；而不是从尾端算回来的距离。

:key 关键字参数是序列中每个元素在被考虑之前，应用至元素上的函数。如果我们说，

> (position 'a '((c d) (a b)) :key #'car)
1

那么我们要找的是，元素的 car 部分是符号 a 的第一个元素。

:test 关键字参数接受需要两个实参的函数，并定义了怎样是一个成功的匹配。缺省函数为 eql 。如果你想要匹配一个列表，你也许想使用 equal 来取代：

> (position '(a b) '((a b) (c d)))
NIL
> (position '(a b) '((a b) (c d)) :test #'equal)
0

:test 关键字参数可以是任何接受两个实参的函数。举例来说，给定 < ，我们可以询问第一个使第一个参数比它小的元素位置：

> (position 3 '(1 0 7 5) :test #'<)
2

使用 subseq 与 position ，我们可以写出分开序列的函数。举例来说，这个函数

(defun second-word (str)
  (let ((p1 (+ (position #\  str) 1)))
    (subseq str p1 (position #\  str :start p1))))

返回字符串中第一个单字空格后的第二个单字：

> (second-word "Form follows function")
"follows"

要找到满足谓词的元素，其中谓词接受一个实参，我们使用 position-if 。它接受一个函数与序列，并返回第一个满足此函数的元素：

> (position-if #'oddp '(2 3 4 5))
1

position-if 接受除了 :test 之外的所有关键字参数。

有许多相似的函数，如给序列使用的 member 与 member-if 。分别是， find （接受全部关键字参数）与 find-if （接受除了 :test 之外的所有关键字参数）：

> (find #\a "cat")
#\a

> (find-if #'characterp "ham")
#\h

不同于 member 与 member-if ，它们仅返回要寻找的对象。

通常一个 find-if 的调用，如果解读为 find 搭配一个 :key 关键字参数的话，会显得更清楚。举例来说，表达式

(find-if #'(lambda (x)
             (eql (car x) 'complete))
         lst)

可以更好的解读为

(find 'complete lst :key #'car)

函数 remove （22 页）以及 remove-if 通常都可以用在序列。它们跟 find 与 find-if 是一样的关系。另一个相关的函数是 remove-duplicates ，仅保留序列中每个元素的最后一次出现。

> (remove-duplicates "abracadabra")
"cdbra"

这个函数接受前表所列的所有关键字参数。

函数 reduce 用来把序列压缩成一个值。它至少接受两个参数，一个函数与序列。函数必须是接受两个实参的函数。在最简单的情况下，一开始函数用序列前两个元素作为实参来调用，之后接续的元素作为下次调用的第二个实参，而上次返回的值作为下次调用的第一个实参。最后调用最终返回的值作为 reduce 整个函数的返回值。也就是说像是这样的表达式：

(reduce #'fn '(a b c d))

等同于

(fn (fn (fn 'a 'b) 'c) 'd)

我们可以使用 reduce 来扩充只接受两个参数的函数。举例来说，要得到三个或多个列表的交集(intersection)，我们可以：

> (reduce #'intersection '((b r a d 's) (b a d) (c a t)))
(A)

4.5 示例：解析日期 (Example: Parsing Dates)¶

作为序列操作的示例，本节演示了如何写程序来解析日期。我们将编写一个程序，可以接受像是 “16 Aug 1980” 的字符串，然后返回一个表示日、月、年的整数列表。

(defun tokens (str test start)
  (let ((p1 (position-if test str :start start)))
    (if p1
        (let ((p2 (position-if #'(lambda (c)
                                   (not (funcall test c)))
                               str :start p1)))
          (cons (subseq str p1 p2)
                (if p2
                    (tokens str test p2)
                    nil)))
        nil)))

(defun constituent (c)
  (and (graphic-char-p c)
       (not (char= c #\ ))))

图 4.2 辨别符号 (token)

图 4.2 里包含了某些在这个应用里所需的通用解析函数。第一个函数 tokens ，用来从字符串中取出语元 （token）。给定一个字符串及测试函数，满足测试函数的字符组成子字符串，子字符串再组成列表返回。举例来说，如果测试函数是对字母返回真的 alpha-char-p 函数，我们得到：

> (tokens "ab12 3cde.f" #'alpha-char-p 0)
("ab" "cde" "f")

所有不满足此函数的字符被视为空白 ── 他们是语元的分隔符，但永远不是语元的一部分。

函数 constituent 被定义成用来作为 tokens 的实参。

在 Common Lisp 里，图形字符是我们可见的字符，加上空白字符。所以如果我们用 constituent 作为测试函数时，

> (tokens "ab12 3cde.f gh" #'constituent 0)
("ab12" "3cde.f" "gh")

则语元将会由空白区分出来。

图 4.3 包含了特别为解析日期打造的函数。函数 parse-date 接受一个特别形式组成的日期，并返回代表这个日期的整数列表：

> (parse-date "16 Aug 1980")
(16 8 1980)

(defun parse-date (str)
  (let ((toks (tokens str #'constituent 0)))
    (list (parse-integer (first toks))
          (parse-month (second toks))
          (parse-integer (third toks)))))

(defconstant month-names
  #("jan" "feb" "mar" "apr" "may" "jun"
    "jul" "aug" "sep" "oct" "nov" "dec"))

(defun parse-month (str)
  (let ((p (position str month-names
                         :test #'string-equal)))
    (if p
        (+ p 1)
        nil)))

图 4.3 解析日期的函数

parse-date 使用 tokens 来解析日期字符串，接著调用 parse-month 及 parse-integer 来转译年、月、日。要找到月份，调用 parse-month ，由于使用的是 string-equal 来匹配月份的名字，所以输入可以不分大小写。要找到年和日，调用内置的 parse-integer ， parse-integer 接受一个字符串并返回对应的整数。

如果需要自己写程序来解析整数，也许可以这么写：

(defun read-integer (str)
  (if (every #'digit-char-p str)
      (let ((accum 0))
        (dotimes (pos (length str))
          (setf accum (+ (* accum 10)
                         (digit-char-p (char str pos)))))
        accum)
    nil))

这个定义演示了在 Common Lisp 中，字符是如何转成数字的 ── 函数 digit-char-p 不仅测试字符是否为数字，同时返回了对应的整数。

4.6 结构 (Structures)¶

结构可以想成是豪华版的向量。假设你要写一个程序来追踪长方体。你可能会想用三个向量元素来表示长方体：高度、宽度及深度。与其使用原本的 svref ，不如定义像是下面这样的抽象，程序会变得更容易阅读，

(defun block-height (b) (svref b 0))

而结构可以想成是，这些函数通通都替你定义好了的向量。

要想定义结构，使用 defstruct 。在最简单的情况下，只要给出结构及字段的名字便可以了：

(defstruct point
  x
  y)

这里定义了一个 point 结构，具有两个字段 x 与 y 。同时隐式地定义了 make-point 、 point-p 、 copy-point 、 point-x 及 point-y 函数。

2.3 节提过， Lisp 程序可以写出 Lisp 程序。这是目前所见的明显例子之一。当你调用 defstruct 时，它自动生成了其它几个函数的定义。有了宏以后，你将可以自己来办到同样的事情（如果需要的话，你甚至可以自己写出 defstruct ）。

每一个 make-point 的调用，会返回一个新的 point 。可以通过给予对应的关键字参数，来指定单一字段的值：

(setf p (make-point :x 0 :y 0))
#S(POINT X 0 Y 0)

存取 point 字段的函数不仅被定义成可取出数值，也可以搭配 setf 一起使用。

> (point-x p)
0
> (setf (point-y p) 2)
2
> p
#S(POINT X 0 Y 2)

定义结构也定义了以结构为名的类型。每个点的类型层级会是，类型 point ，接著是类型 structure ，再来是类型 atom ，最后是 t 类型。所以使用 point-p 来测试某个东西是不是一个点时，也可以使用通用性的函数，像是 typep 来测试。

> (point-p p)
T
> (typep p 'point)
T

我们可以在本来的定义中，附上一个列表，含有字段名及缺省表达式，来指定结构字段的缺省值。

(defstruct polemic
  (type (progn
          (format t "What kind of polemic was it? ")
          (read)))
  (effect nil))

如果 make-polemic 调用没有给字段指定初始值，则字段会被设成缺省表达式的值：

> (make-polemic)
What kind of polemic was it? scathing
#S(POLEMIC :TYPE SCATHING :EFFECT NIL)

结构显示的方式也可以控制，以及结构自动产生的存取函数的字首。以下是做了前述两件事的 point 定义：

(defstruct (point (:conc-name p)
                  (:print-function print-point))
  (x 0)
  (y 0))

(defun print-point (p stream depth)
  (format stream "#<~A, ~A>" (px p) (py p)))

:conc-name 关键字参数指定了要放在字段前面的名字，并用这个名字来生成存取函数。预设是 point- ；现在变成只有 p 。不使用缺省的方式使代码的可读性些微降低了，只有在需要常常用到这些存取函数时，你才会想取个短点的名字。

:print-function 是在需要显示结构出来看时，指定用来打印结构的函数 ── 需要显示的情况比如，要在顶层显示时。这个函数需要接受三个实参：要被印出的结构，在哪里被印出，第三个参数通常可以忽略。 [2] 我们会在 7.1 节讨论流（stream）。现在来说，只要知道流可以作为参数传给 format 就好了。

函数 print-point 会用缩写的形式来显示点：

> (make-point)
#<0,0>

4.7 示例：二叉搜索树 (Example: Binary Search Tree)¶

由于 sort 本身系统就有了，极少需要在 Common Lisp 里编写排序程序。本节将演示如何解决一个与此相关的问题，这个问题尚未有现成的解决方案：维护一个已排序的对象集合。本节的代码会把对象存在二叉搜索树里（ binary search tree ）或称作 BST。当二叉搜索树平衡时，允许我们可以在与时间成 log n 比例的时间内，来寻找、添加或是删除元素，其中 n 是集合的大小。

图 4.4: 二叉搜索树

二叉搜索树是一种二叉树，给定某个排序函数，比如 < ，每个元素的左子树都 < 该元素，而该元素 < 其右子树。图 4.4 展示了根据 < 排序的二叉树。

图 4.5 包含了二叉搜索树的插入与寻找的函数。基本的数据结构会是 node （节点），节点有三个部分：一个字段表示存在该节点的对象，以及各一个字段表示节点的左子树及右子树。可以把节点想成是有一个 car 和两个 cdr 的一个 cons 核（cons cell）。

(defstruct (node (:print-function
                  (lambda (n s d)
                    (format s "#<~A>" (node-elt n)))))
  elt (l nil) (r nil))

(defun bst-insert (obj bst <)
  (if (null bst)
      (make-node :elt obj)
      (let ((elt (node-elt bst)))
        (if (eql obj elt)
            bst
            (if (funcall < obj elt)
                (make-node
                   :elt elt
                   :l (bst-insert obj (node-l bst) <)
                   :r (node-r bst))
                (make-node
                   :elt elt
                   :r (bst-insert obj (node-r bst) <)
                   :l (node-l bst)))))))

(defun bst-find (obj bst <)
  (if (null bst)
      nil
      (let ((elt (node-elt bst)))
        (if (eql obj elt)
            bst
            (if (funcall < obj elt)
                (bst-find obj (node-l bst) <)
                (bst-find obj (node-r bst) <))))))

(defun bst-min (bst)
  (and bst
       (or (bst-min (node-l bst)) bst)))

(defun bst-max (bst)
  (and bst
       (or (bst-max (node-r bst)) bst)))

图 4.5 二叉搜索树：查询与插入

一棵二叉搜索树可以是 nil 或是一个左子、右子树都是二叉搜索树的节点。如同列表可由连续调用 cons 来构造，二叉搜索树将可以通过连续调用 bst-insert 来构造。这个函数接受一个对象，一棵二叉搜索树及一个排序函数，并返回将对象插入的二叉搜索树。和 cons 函数一样， bst-insert 不改动做为第二个实参所传入的二叉搜索树。以下是如何使用这个函数来构造一棵叉搜索树：

> (setf nums nil)
NIL
> (dolist (x '(5 8 4 2 1 9 6 7 3))
    (setf nums (bst-insert x nums #'<)))
NIL

图 4.4 显示了此时 nums 的结构所对应的树。

我们可以使用 bst-find 来找到二叉搜索树中的对象，它与 bst-insert 接受同样的参数。先前叙述所提到的 node 结构，它像是一个具有两个 cdr 的 cons 核。如果我们把 16 页的 our-member 拿来与 bst-find 比较的话，这样的类比更加明确。