通过 Lisp 语言理解编程算法：Lisp 速成课程

阅读完本章节后，你将会对 Lisp 写出的代码是什么样的有一个直观的认识。为什么 Lisp 代码如此短呢？就是因为 Lisp 使用 “自下而上” 的编程方法。你不是在基础语言上开发，而是在基础语言上构件一种你自己的语言，然后再用后者开发。你要是不能想象 Lisp 语言的代码是什么样，可以试着想象 XML，想象 XML 中的每个节点都是函数和自变量，而且可以执行。（Lisp 的代码都是嵌套和递归的，编译后就是一颗解析树。没有数据和代码之分，而且是动态类型语言。） Lisp 在所有语言里，具有最高的抽象层次，编程能力最强。（这里的抽象指编程语言本身的抽象，不是对待编程物的抽象。）Lisp 最突出的特点是“代码即数据，数据即代码”。Lisp 构建计算单元的方式尊崇由具体微小入手，像搭积木一般逐步构建规模，这点非常契合人类思维，并且让代码的呈现方式也契合这种方式，便于阅读，赏心悦目。

我预计本书将有两个读者群：

• 希望在算法和编写高效程序方面取得进步的读者——这正是本书的主要读者群。

• 使用 Lisp 的读者，无论他们是熟练的还是有抱负的，他们碰巧也对算法深感兴趣。

本章节主要针对第一个读者群。读完这个章节之后，你应该能够理解本书中其余部分的 Lisp 代码了。此外，如果你愿意的话，你还可以了解运行 Lisp 的基本知识并对其进行实验。

对于 Lisp 用户来说，你可能有兴趣阅读这一章节，不过，这么做只是为了熟悉我在本书中使用这种语言的风格。另外，你还会发现我对评论中多次提到的问题的立场：使用某些第三方扩展是否合理，以及在多大程度上，作者应该谨慎地只坚持使用标准提供的工具。

Lisp 的核心

东西：它们是预先定义的、始终存在的、不可变的。这些都是构件块，在其上构建所有其他操作符，包括顺序块操作符 block、条件表达式 if 和无条件跳转 go 等。如果 oper 是一个特殊操作符的名称，则执行此运算符的底层代码，该代码以自己独特的方式处理参数。

• 还有普通函数的求值：如果 oper 是函数名，首先，使用相同的求值规则计算所有参数，然后用得到的值调用函数。

• 最后就是宏（macro）求值。宏提供了一种更改特定表单求值规则的方法。如果 oper 为宏命名，则用它的代码代替表达式，然后进行求值。宏是 Lisp 中的主要内容，它们用于构建语言的大部分，并为用户提供了一种可访问的方式来扩展 Lisp 语言。但是，它们与本书的主题相互独立、完全不同的，因此，本书不再详细讨论。但你可以在 On Lisp 、 Let Over Lambda 这样的书籍中深入研究 Lisp 的宏。

需要注意的是，在 Lisp 中，语句和表达式之间并没有区别，没有特殊的关键字，没有操作符优先规则，以及在其他语言中可能会遇到的其他类似的任意东西。一切都是统一的：从某种意义上说，一切都是表达式，它将被求值并返回一些值。

代码示例

综上所述，让我们考虑一个 Lisp 表达的求值示例。下面的示例代码实现了著名的二分搜索算法（binary search algorithm）（我们将在下一章中详细讨论）：

(when (> (length vec) 0)(let ((beg 0)(end (length vec)))(do ()((= beg end))(let ((mid (floor (+ beg end) 2)))(if (> (? vec mid) val)(:= beg (1+ mid))(:= end mid))))(values beg(? vec beg)(= (? vec beg) val))))

它是一种复合表单。其中，所谓的顶级表单是 when，它是一个宏，用于一个单子句条件表达式：一个只有 trye- 分支的 if。首先，它对表达式 (> (length vec) 0) 进行求值，这是一个应用于两个参数的逻辑操作符 > 的普通函数：得到的结果是变量 vec 的内容长度和一个常数 0。如果求值返回 true，那就说明 vec 的长度大于 0，则表单的其余部分将以相同的方式进行求值。如果没有异常发生，则求值结果要么为 false（在 Lisp 中为 nil），要么为从最后一个表单返回的 3 个值 (values…)。而 ? 是通用访问操作符，它通过不同的方式抽象来按键查询数据结构。在本例中，它从第二个参数的索引处 vec 中检索项。下面我们将讨论这里提到的其他操作符。

但首先我要谈一谈 RUTILS。它是一个第三方库，为标准 Lisp 语法及其基本操作符提供了许多扩展。它存在的原因是 Lisp 标准永远不会改变，而且，正如这个世界上的任何事物一样，它也有它的缺陷。此外，我们对优雅高效的代码的理解也随着时间的推移而不断发展。然而，Lisp 标准的最大优势在于，作者从最基本的语法开始，几乎在所有级别上都采用了多种方法来修改和发展语言，从而抵消了 Lisp 不可变性的问题。这样一来解决了我们的最终需求，毕竟：我们对改变标准远不如对改变语言那样感兴趣。因此，RUTILS 是 Lisp 的进化方式之一，其目的是在不损害语言原则的前提下，使 Lisp 的编程更易于理解。因此在本书中，我将使用 RUTILS 中的一些基本扩展，并将根据需要解释它们。当然，使用第三方库是个人偏好和品味的问题，可能不会被某些旧版本的 Lisp 所认可，但不必担心，在你的代码中，你完全可以轻松将它们替换为你喜欢的替代库。

REPL

Lisp 程序不仅应该以简单脚本的一次性方式运行，而且还应该作为实时系统运行，这些实时系统不仅需要长时间运行，还要经历数据的更改、代码的更改。这种与程序交互的一般方式称为“读取 - 求值 - 输出”循环（Read-Eval-Print-Loop，REPL），字面意思是 Lisp 编译器 read 一个表单，用上述规则对其进行 eval，将结果 print 回给用户，然后 loop。

REPL 是与 Lisp 程序交互的默认方式，它与 Unix shell 非常相似。当你运行 Lisp 时（例如，通过在 shell 中输入 sbcl），你将会进入 REPL。在本书中，我将在所有基于 REPL 的代码交互之前使用 REPL 提示（CL-USER> 或类似的提示）。下面是一个例子：

CL-USER> (print "Hello world")"Hello world" "Hello world"

好奇的读者可能会问，"hello world" 为什么打印两次？这证明了在 Lisp 中，一切都是表达式。与大多数其他语言不同，print 语句不仅将其参数打印到控制台（或其他输出流），但也会按原样返回。这在调试时非常方便，因为你可以在不更改程序流程的情况下，将几乎任何表单封装到一个 print 中。

显然，如果不需要交互的话，那么只需“读取 - 求值”部分即可。但是，更重要的是，Lisp 提供了一种方法来自定义流程的每个阶段：

• 在 read 阶段，可以通过称为读取宏（reader macro）机制引入特殊语法（“syntax sugar”）。

• 普通宏是自定义 eval 阶段的一种方法。

• 从概念上来讲，print 阶段是最简单的阶段，并且还有一种通过公共 Lisp 对象系统（Common Lisp Object System，CLOS）的 print-object 函数定制对象输出的标准方法。

• 并且，loop 阶段可以被所需的任何程序逻辑所取代。

译注：syntax sugar，语法糖，由英国计算机科学家 Peter John Landin 发明的一个术语，指计算机语言中添加的某种语法，这种语法对语言的功能并没有影响，但是更方便进程员使用。通常来说使用语法糖能够增加进程的可读性，从而减少进程代码出错的机会。

基本表达式

结构化编程范式指出，所有程序都可以用 3 种基本结构表示：顺序执行、分支和循环。让我们看看这些操作符在 Lisp 中是如何表示的。

顺序执行

顺序执行是最简单的程序流程。在所有命令式语言中，如果将多个表单放在一行中并对生成的代码块进行求值，则会出现这种情况。像这样：

CL-USER> (print "hello") (+ 2 2)"hello"4

最后一个表达式返回的值将整个序列的值“变暗”。

这里，REPL- 交互表单形成了隐式顺序代码单元。然而，在许多情况下，我们需要明确界定这些单元这可以通过 block 操作符来完成：

CL-USER> (block test(print "hello")(+ 2 2))"hello"4

这样的块有一个名称（本例中为 test）。这允许通过使用操作符 return-from 提前结束执行：

CL-USER> (block test(return-from test 0)(print "hello")(+ 2 2))0

一个简短的 reture 用于从名称为 nil 的块中退出（在我们将进一步讨论的大多数循环结构中都是隐式的）：

CL-USER> (block nil(return 0)(print "hello")(+ 2 2))0

最后，如果我们甚至不打算过早地从一个块返回，可以使用不需要名称的 progn 操作符：

CL-USER> (progn(print "hello")(+ 2 2))"hello"4

分支

条件表达式计算它们的第一个表单的值，并根据它执行几个可选代码路径之一。基本条件表达式是 if：

CL-USER> (if nil(print "hello")(print "world"))"world"

正如我们所见，nil 在 Lisp 中用来表示逻辑的 “false”。所有其他值在逻辑上都被认为是 “true”，包括符号 T 或 t ，它直接就代表了 “true” 的含义。

当我们需要一次做几件事时，在其中一个条件分支中，这是我们需要使用 progn 或 block 的情况之一：

CL-USER> (if (+ 2 2)(progn(print "hello")4)(print "world"))"hello"4

然而，我们通常不需要表达式的两个分支，也就是说，我们并不在乎条件不成立（或成立）时会发生什么。这是一种非常常见的情况，在 Lisp 中有它的特殊表达式： when 和 unless：

CL-USER> (when (+ 2 2)(print "hello")4)"world"4CL-USER> (unless (+ 2 2)(print "hello")4)NIL

正如你所看到的，它也很方便，因为你不必显式地将顺序表单封装在 progn 中。

另一个标准条件表达式是 cond，当我们想要连续求值几个条件时就使用它：

CL-USER> (cond((typep 4 'string)(print "hello"))((> 4 2)(print "world")nil)(t(print "can't get here")))"world"NIL

如果前面的条件都不起作用（因为它的条件总是 “true” 的话）那么 t 情况就是一个全面控制（catch-all），将被触发。上面的代码相当于下面的代码：

(if (typep 4 'string)(print "hello")(if (> 4 2)(progn(print "world")nil)(print "can't get here")))

在 Lisp 中还有更多的条件表达式，用宏来定义自己的条件表达式非常容易（实际上，是关于使用 when、unless、cond 来如何定义的问题），当需要使用特殊表达式时，我们将讨论它的实现。

循环

与分支一样，Lisp 也具有丰富的循环结构，并且在必要时也很容易定义新的结构。这种方法不同于主流语言，主流语言通常只有少量这样的语句，有时还通过多态性提供扩展机制。它甚至被认为是一种“美德”，因为它对初学者而言，不那么令人困惑。这在一定程度上还是有意义的。不过，在 Lisp 中，通用方法和自定义方法都可以共存并相互补充。然而，定义自定义控件结构的传统非常强大。为什么呢？其中一个理由就是与人类语言相似：实际上，when 和 unless，以及 dotimes 和 loop 都是直接来自人类语言中的单词，或者是来自自然语言表达。我们的母语并没有那么原始和枯燥。另一个原因就是因为你可以。也就是说，在 Lisp 中定义自定义语法扩展要比其他语言中容易得多，有时简直让人无法抗拒。在许多用例中，它们使代码变得更加简单明了。

无论如何，对于一个完全的初学者来说，实际上，你必须知道与任何其他语言差不多的迭代结构。最简单的是 dotimes，它将计数器变量迭代给定次数（从 0 到 (- times 1))，并在每次迭代中执行主体。它类似于 C 语言中的 for (int i = 0; i < times; i++) 循环。

CL-USER> (dotimes (i 3)(print i))012NIL

尽管返回值可以在循环头部中指定，但默认情况下，返回值为 nil。

另一方面，最通用（和底层）的循环结构是 do：

CL-USER> (do ((i 0 (1+ i))(prompt (read-line) (read-line)))((> i 1) i)(print (pair i prompt))(terpri))foo(0 "foo")bar(1 "bar")2

do 迭代在第一部分（本例中是 i 和 prompt）中定义的多个变量（零或更多），直到满足第二部分的终止条件（本例中是 (> i 1)），与 dotimes（以及其他 do-style 宏）一样，执行它的主体——其余的表单（本例中是 print 和 terpri，是打印换行符的简写）。read-line 从标准输入读取，直到遇到换行符，并且 1+ 返回 i 的当前值增加 1。

所有 do-style 宏（有很多这样的宏，既有内置的，也有外部库提供的：dolist、dotree、do-register-groups、dolines 等）都有一个可选的返回值。在 do 中，它遵循终止条件，在本例中，只返回 i 的最终值。

除了 do-style 的迭代外，CL 生态系统中还有一个大不相同的“猛兽”：臭名昭著的 loop 宏。它用途非常广泛，尽管在语法方面有点不顺畅，并且有一些令人惊讶的行为。但是详细阐述它已经超出了本书的范畴，特别是因为在 Peter Seibel 的《 LOOP for Black Belts 》中关于 loop 有一个很不错的介绍。

许多语言提供了一个通用循环结构，它能够迭代任意序列、生成器和其他类似的行为，通常是 foreach 的一些变体。在更详细地讨论序列之后，我们将回到这种结构。

此外还有另一种迭代射血：函数式迭代，基于高阶函数（map、reduce 和类似的函数）——我们也将在接下来的章节中对其进行更为详细的介绍。

过程和变量

我们已经讨论了结构化变成的三大支柱，但其中一个重要的，实际上也是最重要的结构仍然是变量和过程。

如果我告诉你，你可以多次执行相同的计算，但是要改变一些参数的话……好吧，好吧，这个差劲的玩笑。因此，过程是重用计算的最简单方法，并且过程接受参数，允许将值传递到他们的主体中。在 Lisp 中，过程称为 lambda。可以这样定义一个： (lambda (x y) (+ x y))。当使用时，这样的过程——通常也被称为函数，尽管它与我们所认为的数学函数大不相同，并且在这种情况下，它被称为匿名函数，因为它没有任何名称，将产生期输入的总和：

CL-USER> ((lambda (x y) (+ x y)) 2 2)4

通过完整的代码签名来引用过程是相当麻烦的，显而易见的解决方案是为它们指定名称。在 Lisp 中，一个常见的方法是通过 defun 宏：

CL-USER> (defun add2 (x y) (+ x y))ADD2CL-USER> (add2 2 2)4

过程的参数是变量的例子。变量用于命名存储单元（memory cells），这些单元的内容被多次使用，并且可能在过程中被更改。他们有不同的用途：

• 将数据传递给程序

• 作为代码块中某些变化数据的临时占位符（如循环计数器）

• 作为存储计算结果以便进一步重用的一种方法

• 定义程序配置参数（如 OS 环境变量，也可以将其视为程序主函数的参数）

• 引用应该可以从程序中的任何地方访问的全局对象（如 *standard-output* 流）

• 还有更多

我们可以没有变量吗？从理论上来说，也许可以。至少，编程中有一种所谓的“无点”风格（point-free style），就强烈反对使用变量。但是，就像他们所说，不要在工作中尝试这个（至少在你完全明白你在做什么之前）。我们是否可以用常量或者单赋值变量来替换变量，即不能随时间变化的变量？这种方法是由所谓的纯函数语言所提倡的。在某种程度上来说，是这样。但是，从算法开发的角度来看，它使许多优化变得复杂了，即使没有完全超越它们，也会令开发者头疼。

那么，如何在 Lisp 中定义变量呢？你已经看到了一些变体：过程参数和 let-bindings。用 Lisp 的话说，这样的变量叫做局部变量或词法变量（lexical variable）。这是因为在整个代码块的执行过程中，它们只能在本地访问，在代码中定义它们。let 是引入此类局部变量的一般方法，它是伪装的 lambda（“在它上面有一层薄薄的语法糖”）：

CL-USER> (let ((x 2))(+ x x))4CL-USER> ((lambda (x) (+ x x))2)4

使用 lambda，你可以在一个地方创建一个过程，可能的话，也许可以将它分配一个一个变量（本质上就是 defun 所做的），然后在不同的地方多次应用，让你定义一个过程并立即调用它，这样就没有办法存储它并在以后再次重新应用。这甚至比匿名函数更加匿名！而且，它还不需要编译器的额外开销。但机制是相同的。

通过 let 创建变量称为绑定（binding），因为他们会立即被赋值（绑定）。可以一次绑定多个变量：

CL-USER> (let ((x 2)(y 2))(+ x y))4

但是，我们通常需要使用前一个变量的值来定义一行变量和下一个变量。使用 let 很麻烦，因为需要嵌套（因为过程参数是独立分配的）：

(let ((len (length list)))(let ((mid (floor len 2)))(let ((left-part (subseq list 0 mid))(right-part (subseq list mid)))...)))

为了简化这个用例，我们用 let 来演示：

(let* ((len (length list))(mid (floor len 2))(left-part (subseq list 0 mid))(right-part (subseq list mid)))...)

然而，还有许多其他方法可以定义变量：一次绑定多个值；当数据结构（通常是列表）的内容被分配给多个变量时，执行所谓的“析构（destructuring）绑定”，第一个元素分配给第一个变量，第二个元素分配给第二个变量，以此类推；访问某个结构的槽（slots）等。对于这样的用例，有来自 RUTILS 的 with 绑定，其工作方式类似于 let，具有额外的功能。这里有一个非常简单的例子：

(with ((len (length list))(mid rem (floor len 2));; this group produces a list of 2 sublists;; that are bound to left-part and right-part;; and ; character starts a comment in lisp((left-part right-part) (group mid list)))...

在本书的代码中，你将只看到这两种绑定结构：let 用于普定绑定和并行绑定，以及 with 用于其余所有绑定。

正如我们所说的，变量不仅可以被定义，或者它们可以被称为“常量“，而且还可以被修改。要改变变量的值，我们将使用来自 RUTILS 的 :=（它是标准 psetf 宏的缩写）：

CL-USER> (let ((x 2))(print (+ x x))(:= x 4)(+ x x))48

一般来说，修改是一种危险的够早，因为它可能会产生意想不到的“超距作用”效果，当在代码的某个位置更改变量的值时，会影响使用相同变量的不同部分的执行。然而，这不可能发生在词法变量上：每个 let 都创建自己的作用域，以保护前面的值不被修改（就像将参数传递给过程调用，并在调用中修改它们不会改变调用代码中那些值一样）：

CL-USER> (let ((x 2))(print (+ x x))(let ((x 4))(print (+ x x)))(print (+ x x)))484

显然，当两个 let 在不同的地方使用同一个变量名时，它们不会相互影响，这两个变量实际上是完全不同的。

然而，有时在一个地方修改变量，然后在另一个地方查看效果还是有用的。具有这种行为的变量称为全局变量或动态变量（在 Lisp 术语中也称为特殊变量）。它们有几个重要的目的。其中之一是定义需要在任何地方都可访问的重要配置参数。另一个是引用通用单例对象，如标准流或随机数生成器的状态。还有一个是指向某些上下文，这些上下文可以根据特定过程的需要在某些地方进行更高（，*package* 全局变量确定我们在哪个包中操作——前面所有的示例中的 CL-USER）。全局变量也有更高级的用法。定义全局变量的常用方法是使用 defparameter，它指定全局变量的初始值：

(defparameter *connection* nil"A default connection object."); this is a docstring describing the variable

在 Lisp 中，全局变量通常在其名称周围有所谓的“耳罩”，以提醒用户他们正在处理的是什么内容。由于它们的超距作用效果，它并不是最安全的编程语言特性，甚至还有一句“全局变量被认为是有害的”咒语。但是，Lisp 并不是那种“娇气”的语言，它发现了许多特殊变量的用途。顺便说一句，它们之所以被称为是“特殊的”，是因为它们有一个特殊的功能，极大地拓宽了它们正常使用的可能性：如果将它们绑定在 let 中，则它们将充当词法变量，也就是说，即前一个值在离开 let 主体时被保留和恢复：

CL-USER> (defparameter *temp* 1)*TEMP*CL-USER> (print *temp*)1CL-USER> (progn(let ((*temp* 2))(print *temp*)(:= *temp* 4)(print *temp*))*temp*)241

Lisp 中的过程是一类对象。这意味着你可以将其分配给变量，以及在运行时检查和重新定义，因此可以使用它来做许多其他有用的操作。RUTILS 函数 call 将调用作为参数传递给它的过程：

CL-USER> (call 'add2 2 2)4CL-USER> (let ((add2 (lambda (x y) (+ x y))))(call add2 2 2))4

注：call 是标准 funcall 的 RUTILS 缩写。在 20 世纪 60 年代，从变量中调用函数肯定很有趣，但现在它变得如此普遍，以至于不需要前缀了。

实际上，使用 defun 定义函数也会创建一个全局变量，尽管是在函数名称空间中。函数、类型、类——所有这些对下你给通常都定义为全局对象。不过，对于函数，有一种方法可以用 flet 在本地定义它们：

CL-USER> (foo 1);; ERROR: The function COMMON-LISP-USER::FOO is undefined.CL-USER> (flet ((foo (x) (1+ x)))(foo 1))2CL-USER> (foo 1);; ERROR: The function COMMON-LISP-USER::FOO is undefined.

注释

最后，还有一个语法我们需要只到：如何在代码中添加注释。只有失败者才不会注释他们的代码，在本书中，注释将会被广泛使用，贯穿本书，来解释代码示例的某些部分。Lisp 中，注释以 ; 字符开头，以行位结束。因此，下面的代码段是一个注释： ; this is a comment。还有一种常见的注释风格，即当前代码行之后的简短注释以单个 ; 开头，如果某个代码块前面有较长的注释，占据整行或多行，并以 ;; 开头。包含多个 LISP 顶级表单（全局定义）的代码部分的注释以 ;;; 开头，也占用整行。此外，每个全局定义都可以有一个特殊的类似注释的字符串，称为“文档字符串”（docstring），用于描述其用途和用法，并且可以通过编程查询。综上所述，不同的注释可能是这样子的：

;;; Some code section(defun this ()"This has a curious docstring."...)(defun that ()...;; this is an interesting block don't you find?(block interesting(print "hello"))); it prints hello

入门指南

我强烈建议你尝试使用本书后面章节中的代码。并试着改进这些代码，找出问题，并相处解决方案，测量和跟踪一切。这不仅能够帮助你掌握一些 Lisp 技能，而且还能更深入理解所讨论的算法和数据结构的描述、他们的缺陷以及极端情况。事实上，做到这一点相当容易。你需要做的就是安装一些 Lisp（最好是 SBCL 或 CCL），添加 Quicklisp，并在其帮助下添加 RUTILS。

正如我上面所说，使用 Lisp 的通常方法是与其 REPL 进行交互。运行 REPL 相当简单，在我的 Mint Linux 上，运行以下命令：

$ apt-get install sbcl rlwrap...$ rlwrap sbcl...* (print "hello world")"hello world" "hello world"*

* 是 Lisp 的原始提示符。它基本上和你在 SLIME 中看到的 CL-USER> 提示符是一样的。你还可以运行 Lisp 脚本文件： sbcl --script hello.lisp。如果它只包含一行 (print "hello world")，我们将会看到“hello world”短语被打印到控制台上。

这是一个有效的设置，但并不是最方便的设置。一个更高级的环境是在 Emacs 内部运行的 SLIME （类似于 vim 的项目，称为 SLIMV）。还有许多其他解决方案：一些 Lisp 实现提供了集成开发环境（IDE），某些 IDE 和编辑器也提供了集成。

进入 REPL 后，你必须发出以下命令：

* (ql:quickload :rutilsx)* (use-package :rutilsx)* (named-readtables:in-readtable rutilsx-readtable)

好了，以上就是你需要知道的 Lisp 知识，已经足以开始了。我们将熟悉其他 Lisp 概念，因为它们将在本书下一章中用到。但是，你现在就可以准备好读写 Lisp 程序了。一开始，它们可能看起来很陌生的感觉，但当你克服了最初的障碍并习惯它们的古怪的前缀表层语法，我保证，你将能够看懂并欣赏它们的清晰和简洁。

所以，就像他们在 Lisp 岛上说的那样，快乐去探险吧！

作者介绍：

Vsevolod Dyomkin，Lisp 程序员，居住在乌克兰基辅。精通乌克兰语、俄语和英语。目前正在撰写关于 Lisp 的书籍 Programming Algorithms in Lisp，该书将使用 CC BY-NC-ND 许可（创作公用许可协议），供公众免费阅读。

原文链接：

LISP, THE UNIVERSE AND EVERYTHING