lisp语言的函数
当表达式以七个原始操作符中的五个开头时，它的自变量总是要求值的.[2] 我们称这样 的操作符为函数. 接
((lambda (...) e) ...)
则称为函数调用.它的值计算如下.每一个表达式先求值，然后e再求值.在e的求值过程中，每个出现在e中的的值是相应的在最近一次的函数调用中的值.
(f ...)
并且f的值是一个函数（lambda (...）），则以上表达式的值就是
((lambda (...) e) ...)
(a b c)
有另外一个函数记号使得函数能提及它本身，这样我们就能方便地定义递归函数.[3] 记号
(label f (lambda (...) e))
表示定义函数名为 f 的函数为（lambda (...) e）。特别的，次定义语句本身e之中可以出现 f ，且任何出现在e中的f将求值为此label表达式，就好象f是此函数已知的参数。如此形成了自指嵌套。 假设我们要定义函数（subst x y z），它取表达式x，原子y和表z做参数，返回一个象z那样的表，不过z中出现的y（在任何嵌套层次上）被x代替.
> (subst 'm 'b '(a b (a b c) d))
(a m (a m c) d)
我们可以这样表示此函数
我们简记f=(label f (lambda (...) e））为
(
偶然地我们在这儿看到如何写cond表达式的缺省子句. 第一个元素是't的子句总是会成功的. 于是
(cond (x y) ('t z))
等同于我们在某些语言中写的
if x then y else z
一些函数
既然我们有了表示函数的方法，我们根据七个原始操作符来定义一些新的函数. 为了方便我们引进一些常见模式的简记法. 我们用cxr，其中x是a或d的序列，来简记相应的car和cdr的组合. 比如（cadr e)是（car (cdr e））的简记，它返回e的第二个元素.
> (cadr '((a b) (c d) e))
(c d)
> (caddr '((a b) (c d) e))
e
> (cdar '((a b) (c d) e))
(b)
我们还用（list ...）表示（cons ...(cons '()) ...).
> (cons 'a (cons 'b (cons 'c '())))
(a b c)
> (list 'a 'b 'c)
(a b c)
现在我们定义一些新函数. 我在函数名后面加了点,以区别函数和定义它们的原始函数，也避免与现存的common Lisp的函数冲突.
(null. x）测试它的自变量是否是空表.
(defun null. (x)
(eq x '()))
> (null. 'a)
()
> (null. '())
t
(and. x y)返回t如果它的两个自变量都是t，否则返回（）.
(defun and. (x y)
(cond (x (cond (y 't) ('t '())))
('t '())))
> (and. (atom 'a) (eq 'a 'a))
t
(c d)
(pair. x y）取两个相同长度的表，返回一个由双元素表构成的表，双元素表是相应位置的x,y的元素对.
(defun pair. (x y)
(cond ((and. (null. x) (null. y)) '())
((and. (not. (atom x)) (not. (atom y)))
(cons (list (car x) (car y))
(pair. (cdrx) (cdr y))))))
> (pair. '(x y z) '(a b c))
((x a) (y b) (z c))
(assoc. x y)取原子x和形如pair.函数所返回的表y，返回y中第一个符合如下条件的表的第二个元素：它的第一个元素是x.
(defun assoc. (x y)
(cond ((eq (caar y) x) (cdar y))
('t (assoc. x (cdr y)))))
> (assoc. 'x '((x a) (y b)))
a
> (assoc. 'x '((x new) (x a) (y b)))
new
一个惊喜
因此我们能够定义函数来连接表，替换表达式等等.也许算是一个优美的表示法，那下一步呢? 现在惊喜来了. 我们可以写一个函数作为我们语言的解释器：此函数取任意Lisp表达式作自变量并返回它的值. 如下所示：
(defun eval. (e a)
(cond
((atom e) (assoc. e a))
((atom (car 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)))))
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 (...) e) ...）的表达式求值，先调用evlis.来求得自变量（...）对应的值（...），把（）...（）添加到环境里，然后对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).
后果
既然理解了eval是如何工作的，让我们回过头考虑一下这意味着什么. 我们在这儿得到了一个非常优美的计算模型. 仅用quote,atom,eq,car,cdr,cons，和cond，我们定义了函数eval.，它事实上实现了我们的语言，用它可以定义任何我们想要的额外的函数.
