跨越边界: Lisp 之美 lispschemejava设计模式函数式编程
简介： Lisp 长久以来一直被视为伟大的编程语言之一。其漫长的发展过程（接近五十年）中引发的追随狂潮表明：这是一门非同凡响的语言。在 MIT，Lisp 在所有程序员的课程中占了举足轻重的地位。像 Paul Graham 那样的企业家们将 Lisp 卓越的生产力用作他们事业成功起步的推动力。但令其追随者懊恼万分的是，Lisp 从未成为主流编程语言。作为一名 Java™ 程序员，如果您花一点时间研究 Lisp 这座被人遗忘的黄金之城，就会发现许多能够改进编码方式的技术。
我最近第一次完成了马拉松赛跑，我发现跑步比我预想的更有价值。我跑了 26.2 英里，通过该步骤，我开始认为这是对身体非常有益的简单活动。一些语言给了我类似的感觉，如 Smalltalk 和 Lisp。对 Smalltalk 来说，引发类似感觉的是对象；Smalltalk 中的一切内容都是在处理对象和消息传递。对于 Lisp 来说，这个至为重要的步骤更为简单。这门语言完全由列表组成。但不要被这个简单的假相所欺骗。这门有着 48 年历史的语言具有难以置信的强大功能和灵活性，这是 Java 语言所不能企及的。
第一次和 Lisp 打交道时，我还是在校大学生，但这次不是很顺利。因为我拼命地想把 Lisp 编入到熟悉的过程化范例中，而不是在 Lisp 的函数结构下工作。尽管 Lisp 并不是一门严格的函数语言（因为一些特性，它不符合最严格的术语定义），但 Lisp 的许多习语和特性有着很强的函数风格。从那以后，我学会了利用列表和函数式编程。
本期的跨越边界 将重拾这份遗失的财富。我会带您简单地领略一下 Lisp 的基本构造，然后快速的扩展开来。您将学到 Lambda 表达式、递归和宏。这份简单的向导会让您对 Lisp 的高效性和灵活性有所理解。
本文使用 GNU 的 GCL，它针对许多操作系统都有免费下载。但稍作修改，就能使用任何版本的 Common Lisp。请参见 参考资料 获取可用 Lisp 版本的详细说明。
和学习大多数其他语言一样，学习 Lisp 最好的方法就是实践。打开您的解释程序，和我一起编码。Lisp 基本上是一门编译好的语言，通过直接键入命令，就可以轻松地用它进行编程。
基本上，Lisp 是一门关于列表的语言。Lisp 中的一切内容（从数据到组成应用程序的代码）都是列表。每个列表都由一些原子 和列表组成。数字就是原子。键入一个数字仅仅会返回该数字作为结果：
清单 1. 简单原子
>1 1 >a Error: The variable A is unbound. |
如果键入一个字母，解释程序会报错，如清单 1 所示。字母是变量，所以使用之前必须先为其赋值。如果想要引用一个字母或词语而不是变量，请使用引号将其括起来。在变量前加单引号告诉 Lisp 延迟对后续列表或原子进行求值，如清单 2 所示：
清单 2. 延迟求值和引用
>"a" "a" >'a A |
请注意 Lisp 把 a 大写为 A。lisp 假设您希望使用 A 作为符号，因为它没有加括号。后面会讨论赋值，但先要让列表来完成这一任务。简单地讲，Lisp 列表是加了括号并使用空格隔开的原子序列。尝试如清单 3 所示键入一个列表。这个列表是无效的，除非在列表前面加上 '。
清单 3. 键入一个简单列表
>(1 2 3) Error: 1 is invalid as a function. >'(1 2 3) (1 2 3) |
除非在列表前加上 '，否则 Lisp 会像对函数求值那样对每个列表求值。第一个原子是运算符，列表中其余的原子是参数。Lisp 有数目众多的原语函数，正如您预料的那样，其中包括许多数学函数，例如，+、* 和 sqrt。(+ 1 2 3) 返回 6，(* 1 2 3 4) 返回 24。
操纵列表的有两类函数：构造函数 和选择函数。构造函数构建列表，选择函数分解列表。first 和 rest 是核心选择函数。first 选择函数返回列表的第一个原子，rest 选择函数返回除第一个原子外的整个列表。清单 4 显示了这两个选择函数：
清单 4. 基本 Lisp 函数
> (first '(lions tigers bears)) LIONS > (rest '(lions tigers bears)) (TIGERS BEARS) |
这两个选择函数都获取整个列表，返回列表的主要片断。稍后，您将了解递归如何利用这些选择函数。
如果希望构建列表而不是将其分开，就需要构造函数。与在 Java 语言中一样，构造函数构建新元素：在 Java 语言中为对象，在 Lisp 中即为列表。cons、list 和 append 是构造函数示例。核心构造函数 cons 带有两个参数：一个原子和一个列表。cons 将该原子作为第一个元素添加到该列表。如果对 nil 调用 cons，Lisp 将 nil 作为空列表对待，并构建一个含一个元素的列表。append 连接两个列表。list 包含一个由所有参数组成的列表。清单 5 显示了这些构造函数的实际应用：
清单 5. 使用构造函数
> (cons 'lions '(tigers bears)) (LIONS TIGERS BEARS) > (list 'lions 'tigers 'bears) (LIONS TIGERS BEARS) > (append '(lions) '(tigers bears)) (LIONS TIGERS BEARS) |
将 cons 与 first、rest 一起用时可以构建任何列表。list 和 append 运算符只是为了方便，但经常会用到它们。事实上，可以使用cons、first 和 rest 来构建任何列表，或返回任何列表片段。例如，要获取列表的第二或第三个元素，应该获取 rest 中的 first，或 rest 中的 rest 中的 first，如清单 6 所示。或者，若要构建包含两个或三个元素的列表，可以将 cons 和 first、rest 一起使用，来模拟 list 和 append。
清单 6. 构建第二个元素、第三个元素，然后模拟 list 和 append
>(first (rest '(1 2 3))) 2 >(first (rest (rest '(1 2 3)))) 3 >(cons '1 (cons '2 nil)) (1 2) >(cons '1 (cons '2 (cons '3 nil))) (1 2 3) >(cons (first '(1)) '(2 3)) (1 2 3) |
这些示例也许无法引起您的兴趣，但在如此简单的原语之上构建一门简洁优美的语言，其中的原理让一些程序员激动不已。这些由列表构建的简单指令构成了递归、高阶函数，甚至是闭包和 continuation 之类高级抽象的基础。因此下面将研究高级抽象。
可以猜到，Lisp 函数声明为列表。清单 7 构建了一个返回列表第二个元素的函数，展示了函数声明的形式：
清单 7. 构建第二个函数
(defun my_second (lst) (first (rest lst)) ) |
defun 是用于定义自定义函数的函数。第一个参数是函数名，第二个参数是参数列表，第三个参数是希望执行的代码。可以看出，所有 Lisp 代码都表述为列表。借助这项灵活和强大的功能，就可以像操纵其他任何数据一样操纵应用程序。稍后将看到一些示例使代码和数据之间的区别变得模糊。
Lisp 也处理条件结构，如 if 语句。格式为 (if condition_statement then_statement else_statement)。清单 8 是一个简单的my_max 函数，用于计算两个输入变量中的最大值：
清单 8. 计算两个整数中的最大值
(defun my_max (x y) (if (> x y) x y) ) MY_MAX (my_max 2 5) 5 (my_max 6 1) 6 |
下面回顾一下到目前为止看到的内容：
- Lisp 使用列表和原子来表示数据和程序。
- 对列表求值时将第一个元素看作列表函数，将其他元素看作函数参数。
- Lisp 条件语句将 true/false 表达式和代码一起使用。
Lisp 提供用于迭代的编码结构，但递归是更受欢迎的列表遍历方式。使用 first 和 rest 组合实现递归效果很好。清单 9 中的 total函数显示了其运行原理：
清单 9. 使用递归计算列表的总和
>(defun total (x)
(if (null x)
0
(+ (first x) (total (rest x)))
)
)
TOTAL
>(total '(1 5 1))
7
|
清单 9 中的 total 函数将列表当作单个的参数。第一个 if 语句在列表为空的情况下中断递归，返回零值。否则，该函数将第一个元素添加到列表其余部分的总和。现在应该明白如此构建 first 和 rest 的原因。first 能够去除列表的第一个元素，rest 简化了将尾部递归 （清单 9 中的递归类型）应用于列表其余部分的过程。
由于性能的原因，Java 语言中的递归是有限的。Lisp 提供一项称作尾部递归优化 的性能优化技术。Lisp 编译器或解释器能够将特定形式的递归翻译为迭代，从而允许以一种更为简单明快的方式来使用递归数据结构（如树结构）。
如果模糊了数据和代码之间的区别，Lisp 会更有意思。在本系列的前两篇文章中，介绍了 JavaScript 中的高阶函数 和 Ruby 中的闭包。这两项功能都将函数作为参数进行传递。在 Lisp 中，由于函数和列表没有任何区别，高阶函数也就非常简单。
高阶函数的最常见用法或许是 lambda 表达式，这是闭包的 Lisp 版。lambda 函数是用于将高阶函数传入 Lisp 函数的函数定义。例如，清单 10 中的 lambda 表达式计算了两个整数的和：
清单 10. Lambda 表达式
>(setf total '(lambda (a b) (+ a b))) (LAMBDA (A B) (+ A B)) >total (LAMBDA (A B) (+ A B)) >(apply total '(101 102)) 203 |
如果使用过高阶函数或闭包，那么可能更容易理解清单 10 中的代码。第一行代码定义了一个 lambda 表达式并将其和 total 符号绑定到一起。第二行代码仅显示了这个和 total 绑定到一起的 lambda 表达式。最终，最后一个表达式对包含 (101 102) 的列表应用这个 lambda 表达式。
高阶函数提供比面向对象概念更高层次的抽象。可以用它们来更简洁清晰地表达想法。编程的至高境界就是在不牺牲可读性或性能的前提下，用更少的代码提供更强大更灵活的功能。高阶函数能实现所有这些要求。
Lisp 还有两种类型的高阶函数。其中功能最强大的可能是宏。宏为后面的执行定义 Lisp 对象。可以将宏看作代码模板。请参考清单 11 中的示例：
清单 11. 宏
>(defmacro times_two (x) (* 2 x)) TIMES_TWO >(setf a 4) 4 >(times_two a) 8 |
这个示例应该分为两个阶段进行阅读。第一次赋值定义了宏 times_two。在第二个阶段（称为宏扩展）中，在对 a 求值之前，将 a 扩展为 (* 2 a)。该模板中这项延迟求值方式使宏的功能非常强大。Lisp 语言本身的许多功能都是基于宏的。
从年份上讲，Lisp 也许很陈旧，甚至语法也很陈旧。但如果稍作研究，就会发现该语言有着难以置信的强大功能，它的高阶抽象一如既往地有效，并且生产力很高。许多更为现代的语言从 Lisp 中得到借鉴，但是其中大多数语言的功能无法与 Lisp 媲美。如果 Lisp 拥有 Java 或 .NET 的一部分市场，并且大学中具备 lisp 知识的人也占有一定的比例，我们可能就会立即用它进行编码。