Lisp入门（五）

上一集我们已经见到了一个Lisp程序的大致外貌，在文末，我提到这一集中我们将会用Lisp写一个Lisp解释器，事实上这个解释器并不太长，虽然它有可能是你至今为止见过的最长的一个。

我已经有点等不及了，让我们先来看一下整个程序，然后再来讲解：

(defun eval (e a)
  (cond
    ((atom e) (assoc e a))
    ((atom (car e))
     (cond
       ((eq (car e) 'quote) (cadr e))
       ((eq (car e) 'atom)  (atom   (eval (cadr e) a)))
       ((eq (car e) 'eq)    (eq     (eval (cadr e) a)
                                    (eval (caddr e) a)))
       ((eq (car e) 'car)   (car    (eval (cadr e) a)))
       ((eq (car e) 'cdr)   (cdr    (eval (cadr e) a)))
       ((eq (car e) 'cons)  (cons   (eval (cadr e) a)
                                    (eval (caddr e) a)))
       ((eq (car e) 'cond)  (evcon (cdr e) a))
       ('t (eval (cons (assoc (car e) a)
                        (cdr e))
                  a))))
    ((eq (caar e) 'label)
     (eval (cons (caddar e) (cdr e))
            (cons (list (cadar e) (car e)) a)))
    ((eq (caar e) 'lambda)
     (eval (caddar e)
            (append (pair (cadar e) (evlis (cdr  e) a))
                     a)))))

(defun evcon (c a)
  (cond ((eval (caar c) a)
         (eval (cadar c) a))
        ('t (evcon (cdr c) a))))

(defun evlis (m a)
  (cond ((null m) '())
        ('t (cons (eval  (car m) a)
                  (evlis (cdr m) a)))))

（注：可能有的读者已经发现，Lisp并不要求你一定要在使用函数前先定义它）

整个程序包含三个函数，主函数我们遵从Lisp（和Python、Perl）的惯例，叫它eval，它是整个程序的骨架。eval的定义比我们以前看到的任何一个函数都要长，让我们考虑它的每一部分是如何工作的。

eval有两个自变量：e是要求值的表达式，a是由一些赋给原子的值构成的表，这些值有点象函数调用中的参数。这个形如pair返回值的表叫做上下文，正是为了构造和搜索这种表我们才在前一章写了pair和assoc。

eval的骨架是一个有四个子句的cond表达式，如何对表达式求值取决于它的类型，第一个分支处理原子，如果e是原子, 我们在上下文中寻找它的值：

> (eval 'x '((x a) (y b))) a

第二个分支是另一个cond，它处理形如(a)的表达式，其中a是原子。这包括所有的基本操作符，每个对应一条分支。

> (eval '(eq 'a 'a) '()) t > (eval '(cons x '(b c)) '((x a) (y b))) (a b c)

这几个分支(除了quote)都调用eval来寻找自变量的值。

最后两个分支更复杂些。为了求cond表达式的值我们调用了一个叫evcon的辅助函数。它递归地对cond分支进行求值，寻找第一个元素返回t的子句，如果找到了这样的子句，它返回此分支的第二个元素。

> (eval '(cond ((atom x) 'atom) ('t 'list)) '((x '(a b)))) list 

第二个分支的最后部分处理函数调用。它把原子替换为它的值（应该是lambda或label表达式）。然后对所得结果表达式求值。于是：

(eval '(f '(b c)) '((f (lambda (x) (cons 'a x)))))

变为：

(eval '((lambda (x) (cons 'a x)) '(b c)) '((f (lambda (x) (cons 'a x)))))

它返回(a b c)

eval的最后两个cond分支处理第一个元素是lambda或label的函数调。用为了对label表达式求值，先把函数名和函数本身压入上下文，然后调用eval对一个内部有lambda的表达式求值，即：

(eval '((label firstatom (lambda (x) (cond ((atom x) x) ('t (firstatom (car x)))))) y) '((y ((a b) (c d)))))

变为

(eval '((lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))) y) '((firstatom (label firstatom (lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))))) (y ((a b) (c d)))))

最终返回a。

最后，对形如((lambda (p₁ p₂ ... p_n) e) a₁ a₂ ... a_n)的表达式求值，先调用evlis来求得自变量(a₁ a₂ ... a_n)对应的值(v₁ v₂ ... v_n)，把(p₁ v₁) (p₂ v₂) ... (p_n v_n)添加到上下文里，然后对e求值。于是：

(eval '((lambda (x y) (cons x (cdr y))) 'a '(b c d)) '())

变为：

(eval '(cons x (cdr y)) '((x a) (y (b c d))))

最终返回(a c d)。

讲了这么一大篇，如果你看懂了，说明你已经理解Lisp甚至FP的基本编程方式和思路，那么我们写了一个如此之长的程序究竟能干什么呢？

我们在这里得到了一个非常优美的计算模型，eval函数实际上实现了整个语言，用它我们可以定义所需的任何其它函数。换句话说，我们现在有了一个自己的Lisp。

（注：由此可见，递归下降的语法分析是多么美好啊，因为它意味着你可以用几十、最多不过一两百行程序搞定一个复杂的分析器，对比LALR你将更有体会）

下面我们该去哪儿？这个问题，请读者自己去寻找答案。