原子，列表和求值

在 Lisp 中，所有的以空格或是括号分隔的，都是一种叫做原子(atom)的元素(element)，当然，原子也是可被分类的，确切的说，原子可被分为符号和值，这两种东西在 Lisp 的解释器里是不同的。符号是一个词法上的概念，可以类比设想一门自然语言中的名词。而值则是确切存在的自然客属物。一个符号可以指代值，值也就被符号指代，这些我们将会在稍后详细讲解。

我们现在尝试着将原子进行组合，可以得到什么呢？设想我们已经学到过的组合，比如数组，哈希……同样的的，在 Lisp 中，原子的组合叫做列表，一个列表被一对闭合的大括号所包围。我们来写出一些列表：

(1 2 3)
(a 1 Kyoto_Animation)
((lisp is so) amazing)
(defun fac (x) (if (eql x 0) 1 (* x (fac (- x 1)))))
((())())

如你所见，空也是一个元素，空列表也是列表，列表嵌套列表也是合法的。和我们之前所讲过的基本 λ 计算一样，这给了我们强有力的求值工具。

那么列表有什么具体的作用呢？简单地说（在这里，我们忽略了少部分的特殊情况），列表是用于求值(evaluation)的。更严格的说，Lisp中的列表是一个 Program。我们来考虑计算语义上的辖域。辖域主要分为三个部分（一个计算系统）：定义式域，命令式域以及表达式域，我们可以说，大部分列表是属于表达式域的，最初的 Lisp 是一个纯表达式域的语言，并且是严格依照代数语义学的理论建构的。当然，现在的 Lisp 经过许多的演化，成为了一个语族。Lisp 拥有众多的方言，Scheme、Racket等等，我们学习的是 Common Lisp，是之后的 Lisp 社区综合了早期的各种 Lisp 方言而尝试制定的一个统一标准。

还有一个值得注意的问题是，我们发现，对于列表的嵌套深度，Lisp 是没有限度的，这带给了阅读程序的人很大的混淆，比如以下的表达式:

(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))

实际上，在一般的Lisp编写时，遵循一种叫做美观打印的原则，即把多个运算对象垂直对齐的写法，因此，符合规范的写法应该是这样的

(+ (* 3
      (+ (* 2 4)
         (+ 3 5)))
   (+ (- 10 7)
      6))

我们继续来讲回求值的概念，现在给出一个列表，我们按照什么样的规则来得出它的值呢，这和我们接下来要介绍的代换模型有关。

如果按照一般的想法，我们计算 1 + 2 的时候，大脑里思考的是：辨识出这是一个加法运算，然后创造值1，创造值2，运算1与2的加法运算。还有一种思考方式是：创造一个值1，对1应用加法（动词），（宾语）是2，得出结果。

实际上在一般的语义学分析中采取的都是第一种做法，即关系指代型的语义关系，谓词是第一公民。比如 Bob loves Alice 应写成 Love(Bob,Alice)。

代换模型采用的是第一种做法，即我们将1和2应用于加法过程。我们定义：一个列表的第一个原子是运算符，其余所有的都是运算对象。代换模型所做的事情是：对运算符求值，得出一个过程，然后分别对运算对象求值，将其应用到运算符过程的形式参数位（回想一下β-规约）。同时，我们也知道， Lisp 出于效率的考虑，采用了急切求值的做法。

代换模型要求我们不得不采用一种叫做前缀表示法的记法来表示运算，如 (+ 1 2)，这和我们经常使用的中缀表示法是不同的。实际上，我们可以把前缀表示法抽象成一颗表达式树，来看看它在计算机中有什么优势。

特殊的列表，词法作用域

但是事情并不总是尽如人意的，我们会发现，拥有一些列表，它们即无法被代换模型合理的解释，也无法被认为是固化的求值顺序，这个时候，我们就会说代换模型失效了。

我们可以稍稍前进一些，发掘到 Lisp 中少数命令式的风格语句。第一个便是setq和let了。考虑以下的语法规则：

(setq a 47)
(setq a 50)
(defun dec (x)
    (let ((num 40))
         (setq num (- num
                      x))))
(dec 10)
(dec 10)

以上的代码会输出什么值呢？如果我们使用单纯的代换模型来解释以上的代码，我们可以说，setq是一个求值过程，他接受了 a 和47，返回了47，接受了 a 和50，返回了50，我们就会有理由的相信，setq 是一个接受两个参数并返回第二个参数的过程，但是我们在前两条语句后，如果调用 a 会发现什么呢？

我们会发现，a 的值被改变了。我们之前说过，函数式编程的核心是使用不变量来计算，一旦引入了setq和let这样特殊的列表，变量也就被引入了Lisp语言之中，这个时候，我们就要用一个更加通用的环境模型来解释列表的求值过程了。

当然现在也无需立刻介绍这个模型，只需要确知，拥有一个叫做setq的过程，它能够改变变量的值，至于let它仅仅是创建了更深的一层变量作用域而已。

实际说来，let只是lambda的一个语法糖而已，至于匿名函数，我们也会在稍后讲到。

另外两个特殊的列表是条件选择和反引号函数，分别叫做cond和quote。反引号的作用，实际上就是将意指转为符号。我们本来的 Lisp 语言，是将语法对象确定为一个指代，是有语法学之后的语义学含义的。而quote则可以将语法学对象仅仅限制在符号的范畴里，举例说，一旦(setq a (quote b))被求值，那么b的含义被仅仅被限制在了符号层面上，以后我们求值 a，就会仅仅是 b 这个符号。

至于条件选择的特殊之处，同样也在与它不会将列表里的每一个元素都求值，这样的选择性求值也和原本我们所说的代换模型的求值规则相悖。大家有兴趣的话，可以试着去写一个自己的条件选择函数，来看看能不能运行。

接下来让我们来讲讲作用域的事情。所谓的作用域，其实就是一个变量约束所能生效的范围。一般而言，第一个找到的定义了变量的过程是作用域的边界，我们来看下面的例子：

(defun fun (x)
    (let ((var 5))
         (let ((var 4))
              (+ x var))))

这一个过程会输出什么呢？实际上，我们可以说外层的var和内层的有着截然不同的词法含义。尽管他们的符号相同，但他们是被互相隔离的。或者说，内层的变量在参与运算的时候遮蔽了外层变量。这便是所谓的词法作用域，设想一个盒子里套另一个盒子的模型，你就很理解为什么这两个var会能够共存在一个过程中（实际上并不是一个）。我们作为住在最里面盒子的小人，一旦盒子里有了我们所需要的东西，自然也就不需要打破下一层障壁了。

符号，取值与匿名函数

Lisp 是一门符号语言，或者说，它是为了解决符号运算而被设计出来的。一个很著名的符号运算例子便是多项式求导，在之后，我们会试着制作出一个完备的多项式求导系统。

一个符号，是一个语义上的概念。所谓的符号都只是解释器所能够接受的名称。而一个值，则是确实地存储在内存中的地址上的二进制串。我们把一个符号指向一个值的过程，实际上就相当于创建了一个指向内存区域的指针。以后解释器碰到求值这个符号的时候，就会去调取指向的内存。

为了避免语义的二义性，一个符号往往在一个作用域内只能有一个值，同时，Lisp 还有与众不同的两个特点：其一是并不对符号的大小写加以区分，其二则是一个符号虽然不能同时具有两个值，但确实是能同时拥有一个值和一个过程名称的，这一点将会给我们更深的思考：到底 Lisp 中的过程是以怎样的形式存储和被使用的？

值得注意的是，Lisp 并不会持久化的存储值的内存，除非是一个全局的赋值，否则 Lisp 会在每次需要的时候重新分配内存来存储变量和值。这一点也往往被人诟病为非常低效，但实际上，一旦我们深入到解释器的细节层面，我们就可以做许多优化来避免运行过慢的局面。

有了之前的基础后，这边的介绍就简单的多了。事实上我们首先要明确的一点是，所有的过程都是没有名字的，或者说匿名的，我们使用以下的语法规则来创建它们：

(lambda (argument_list)
        (function_body))
(lambda (x y)
        (+ x y))
((lambda (a b c)
         (* a (+ b c))) 5 6 7)

一个匿名函数只有在能被求值，或者说，拥有实际参数的时候才合法，所以说，如果我们单单地对一个 lambda 表达式求值是错误的，因为这实际上只是一个指代，而没有被实例化。

当然，如之前所述，我们也可以给过程指定一个符号的名称，使用defun就可以完成这样的过程。

宏与多值函数

什么是宏？这需要我们进一步的去推广列表求值的概念，既然 Lisp 中一切都是符号，那一个列表当然也可以表示为一个符号，一个列表也有它本身的值。所以从这个层面上，我们可以先简单地将宏（Marco）和函数以这样的定义区分开来：

宏是一种语法结构，它接受参数，返回一个将参数绑定到形参的表。

我们可以来参看几个例子

(defmarco reverse (a b)
    `(cons ,b ,a))
(defmarco filter-remainder (list x)
    `(filter ,(lambda (p) (= (remainder p x) 0)) ,list))
(defmarco setq-literal (symbol literal)
    `(setq ,symbol ',literal))

这里首先出现了一种新的语法结构，即反引号（backquote）。反引号和引号一样，会抑制之后元素的求值过程，但是与引号不同的是，一旦遇到一个逗号，我们就可以要求解释器去求值逗号之后的一个元素。

简要说明上面三个例子的意思，reverse **宏接受了两个参数，并把它们按照第二个，第一个的方式组合成了序对，而filter-remainder接受了一个列表和一个除数，用于筛选出列表中能够整除除数的部分。而setq-literal则将一个符号的值绑定为另一个符号，我们可以看到由于引号的存在，第二个参数不会被setq求值。

Lisp 的宏是一个极为强大的语法结构，它给了我们扩展语言表达的能力，或者说，正是有了宏的概念，Lisp 所谓的求值与应用（Evaluation ＆ Application）循环才真正圆满。有了宏，我们可以轻松地用它来制作 Parser，模式匹配和其它语言的解释器，甚至，可以编写 Lisp 自己的解释器（这一点确实难以置信，但我会在之后说明）。

然后再介绍一个 Lisp 内置的函数marcoexpand，它接受一个宏（需要被引号抑制求值），可以将要用于求值的宏返回的列表打印出来，在你不知道一个宏究竟有什么效果的时候，这个功能非常有用。

多值是什么？多值即是一个非确定性的计算过程，形式化一点讲，多值就是一个一到多的映射。正常的说，Lisp 中的映射都是一个单射，由于 Curry 化的存在，Lisp 的函数都可以被转化为一个链式的高阶过程链，但是，这里存在着几个特殊的表结构，它们会返回多值。

其中有一个较为常用的是values过程，它返回所有参数求值后的结果，例如：

(values (+ 1 3) (/ 6 2))
-> 3
-> 4

你也可以通过宏来书写自己的多值函数。