编程语言的王道：Lisp之美

如果希望构建列表而不是将其分开，就需要构造函数。与在 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 编译器或解释器能够将特定形式的递归翻译为迭代，从而允许以一种更为简单明快的方式来使用递归数据结构（如树结构）。