所以 lambda calculus 其实可以产生出几乎所有程序语言的功能。中国的古话“三生万物”，也许就是这个意思。
求值顺序，call-by-name, call-by-value
当解释一个程序的时候，我们可以有好几种不同的“求值顺
序”(evaluation order)。这有点像遍历二叉树有好几种不同的顺序一样（中序，前序，后序）。只不过这里的顺序更加复杂一些。比如下面的程序：
((lambda (x) (* x x)) (+ 1 2)) 我们可以先执行最外层的调用，把 (+ 1 2) 传递进入函数，得到 (* (+ 1 2) (+ 1 2))。所以求值顺序是：
((lambda (x) (* x x)) (+ 1 2)) => (* (+ 1 2) (+ 1 2)) => (* 3 (+ 1 2)) => (* 3 3) => 9 但是我们也可以先算出 (+ 1 2) 的结果，然后再把它传进这个函数。所以求值顺序是：
((lambda (x) (* x x)) (+ 1 2)) => ((lambda (x) (* x x)) 3) => (* 3 3) => 9 我们把第一种方式叫做 call-by-name (CBN)，因为它把参数的“名字”（也就是表达式自己）传进函数。我们把第二种方式叫做 call-by-value (CBV)，因为它先把参数的名字进行解释，得到它们的“值”之后，才把它们传进函数。
这两种解释方式的效率是不一样的。从上面的例子，你可以看出 CBN 比 CBV 多出了一步。为什么呢？因为函数 (lambda (x) (* x x)) 里面有两个 x，所以 (+ 1 2) 被传进函数的时候被复制了一份。之后我们需要对它的每一拷贝都进行一次解释，所以 (+ 1 2) 被计算了两次！ 鉴于这个原因，几乎所有的程序语言都采用 CBV，而不是 CBN。CBV 常常被叫做“strict”或者“applicative order”。虽然 CBN 效率低下，与它等价的一种顺序 call-by-need 却没有这个问题。call-by-need 的基本原理是对 CBN 中被拷贝的表达式进行“共享”和“记忆”。当一个表达式的一个拷贝被计算过了之后，其它的拷贝自动得到它的值，从而避免重复求值。call-by-need 也叫“lazy evaluation”，它是 Haskell 语言所用的语义。
求值顺序不只停留于 call-by-name, call-by-value, call-by-need。人们还设计了很多种其它的求值顺序，虽然它们大部分都不能像 call-by-value 和 call-by-need 这么实用。
完整的 lambda calculus 解释器
下面是我们今天要完成的解释器，它只有39行（不包括空行和注释）。你可以先留意一下各个部分的注释，它们标注各个部件的名称，并且有少许讲解。这个解释器实现的是 CBV 顺序的 lambda calculus，外加基本的算术。加入基本算术的原因是为了可以让初学者写出比较有趣一点的程序，不至于一开头就被迫去学 Church encoding。
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; 以下三个定义 env0, ent-env, lookup 是对环境（environment）的基本操作： ;; 空环境 (define env0 '()) ;; 扩展。对环境 env 进行扩展，把 x 映射到 v，得到一个新的环境 (define ext-env (lambda (x v env) (cons `(,x . ,v) env))) ;; 查找。在环境中 env 中查找 x 的值 (define lookup (lambda (x env) (let ([p (assq x env)]) (cond [(not p) x] [else (cdr p)])))) ;; 闭包的数据结构定义，包含一个函数定义 f 和它定义时所在的环境 (struct Closure (f env)) ;; 解释器的递归定义（接受两个参数，表达式 exp 和环境 env） ;; 共 5 种情况（变量，函数，调用，数字，算术表达式） (define interp1 (lambda (exp env) (match exp ; 模式匹配 exp 的以下情况（分支） [(? symbol? x) (lookup x env)] ; 变量 [(? number? x) x] ; 数字 [`(lambda (,x) ,e) ; 函数 (Closure exp env)] [`(,e1 ,e2) ; 调用 (let ([v1 (interp1 e1 env)] [v2 (interp1 e2 env)]) (match v1 [(Closure `(lambda (,x) ,e) env1) (interp1 e (ext-env x v2 env1))]))] [`(,op ,e1 ,e2) ; 算术表达式 (let ([v1 (interp1 e1 env)] [v2 (interp1 e2 env)]) (match op ['+ (+ v1 v2)] ['- (- v1 v2)] ['* (* v1 v2)] ['/ (/ v1 v2)]))]))) ;; 解释器的“用户界面”函数。它把 interp1 包装起来，掩盖第二个参数，初始值为 env0 (define interp (lambda (exp) (interp1 exp env0))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 测试例子
这里有一些测试的例子。你最好先玩一下再继续往下看，或者自己写一些新的例子。学习程序的最好办法就是玩弄这个程序，给它一些输入，观察它的行为。有时候这比任何语言的描述都要直观和清晰。
(interp '(+ 1 2)) ;; => 3 (interp '(* 2 3)) ;; => 6 (interp '(* 2 (+ 3 4))) ;; => 14 (interp '(* (+ 1 2) (+ 3 4))) ;; => 21 (interp '(((lambda (x) (lambda (y) (* x y))) 2) 3)) ;; => 6 (interp '((lambda (x) (* 2 x)) 3)) ;; => 6 (interp '((lambda (y) (((lambda (y) (lambda (x) (* y 2))) 3) 0)) 4)) ;; => 6 ;; (interp '(1 2)) ;; => match: no matching clause for 1 在接下来的几节，我们来看看这个解释器里主要的分支（match）表达式的各种情况。
对基本算术操作的解释
算术操作在解释器里是最简单也是最“基础”的东西，因为它们不能再被细分为更小的元素了。所以在接触函数，调用等复杂的结构之前，我们来看一看对算术操作的处理。以下就是这个解释器里处理基本算术的部分，它是 interp1 的最后一个分支。
(match exp ... ... [`(,op ,e1 ,e2) (let ([v1 (interp1 e1 env)] ; 递归调用 interp1 自己，得到 e1 的值 [v2 (interp1 e2 env)]) ; 递归调用 interp1 自己，得到 e2 的值 (match op ; 分支：处理操作符 op 的 4 种情况 ['+ (+ v1 v2)] ; 如果是加号，输出结果为 (+ v1 v2) ['- (- v1 v2)] ; 如果是减号，乘号，除号，相似的处理 ['* (* v1 v2)] ['/ (/ v1 v2)]))])