分析执行分离
介绍分析式求值器：把表达式的语法分析与执行分开，语法只分析一次，从而大幅提升解释器效率。
分析式求值器
要动手实践本节内容，请先获取分析式元循环求值器（analyzing metacircular evaluator）：
cp ~cs61as/lib/analyze.scm .第 12 课中的元循环求值器实现虽然简单，但效率很低。问题出在表达式的语法分析与执行交错在一起：程序每执行一次，它的语法就要被重新分析一遍。下面看一个例子。
假设我们定义了下面这个 factorial 函数：
(define (fact num)
(if (= num 0)
1
(* num (fact (- num 1)))))那么计算 (fact 3) 时会发生什么呢？
eval (fact 3)
self-evaluating? ==> #f
variable? ==> #f
quoted? ==> #f
assignment? definition?
if? ==> #f
lambda? ==> #f
begin? ==> #f
cond? ==> #f
application? ==> #t
eval fact
self-evaluating? ==> #f
variable? ==> #t
lookup-variable-value ==> <procedure fact>
list-of-values (3)
eval3 ==> 3
apply <procedure fact> (3)
eval (if (= num 0) ...)
self-evaluating? ==> #f
variable? ==> #f
quoted? ==> #f
assignment? ==> #f
definition? ==> #f
if? ==> #t
eval-if (if (= num 0) ...)
if-predicate ==> (= num 0)
eval (= num 0)
self-evaluating? ==> #f
...
if-alternative ==> (* num (fact (- num 1)))
eval (* num (fact (- num 1)))
self-evaluating? ==> #f
...
list-of-values (num (fact (- num 1)))
...
eval (fact (- num 1))
...
apply <procedure fact> (2)
eval (if (= num 0) ...)求值器不得不先后四次检查过程体：判断它是个 if 表达式，抽出各个组成部分，再对它们求值（而每个部分的求值，又要先判断它属于哪种表达式）。
这正是解释型语言远比编译型语言慢的原因之一：解释器一遍又一遍地对程序做语法分析；而编译器只分析一次，编译后的程序直接执行那些依赖变量实际取值的计算即可。本节我们要学习的分析式求值器（analyzing evaluator），目的就是避免对程序语法的重复分析。
分离的思路
eval 接受两个参数：一个表达式和一个环境（environment）。其中表达式参数在我们重新遇到同一个表达式时是不变的，而环境每次都会不同。举个例子：计算 (fact 3) 时，我们在一个 num 等于 3 的环境中求值 fact 的过程体；这个过程体里又包含递归调用 (fact 2)，此时求值的是同一个过程体，但环境变成了 num 绑定为 2 的环境。
我们的方案是：梳理整个求值过程，找出那些只依赖 exp 而不依赖 env 的部分，并且只做一次。承担这项工作的过程叫做 analyze（分析）。
analyze 的返回结果是什么呢？它必须能与某个环境结合，最终产出一个值。解决办法是：让 analyze 返回一个只接受 env 参数的过程，由它完成剩下的求值工作。
也就是说，原来的形式
(eval exp env) ==> value变成了两步：
1. (analyze exp) ==> exp-procedure
2. (exp-procedure env) ==> value检验理解
analyze 返回的过程接受什么类型的参数？
以后再次求值同一个表达式时，只需要重复第 2 步。这有点像记忆化（memoization）：我们记住某个计算的结果，避免重复计算。区别在于，这里记住的只是整个问题解法的一部分，而不是完整的答案。
只要稍作改写，就能复刻原来 eval 的效果：
(define (eval exp env)
((analyze exp) env))analyze
analyze 的结构与原来的 eval 十分相似：
(define (analyze exp)
(cond
((self-evaluating? exp)
(analyze-self-eval exp))
((variable? exp)
(analyze-var exp))
...
((foo? exp) (analyze-foo exp))
...))区别在于：原来像 eval-if 那样同时接受表达式和环境两个参数的过程，被换成了像 analyze-if 这样只接受表达式一个参数的过程。这些分析过程是怎么工作的呢？作为理解的中间步骤，先看一个完全照搬 eval-if 结构、一点时间也不省的 analyze-if 版本：
eval-if：
(define (eval-if exp env)
(if (true? (eval (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env)))analyze-if：
(define (analyze-if exp)
(lambda (env)
(if (true? (eval (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env))))这个版本的 analyze-if 返回一个以 env 为参数的过程，过程体与原来的 eval-if 完全一致。因此，如果我们执行
((analyze-if some-if-expression) some-environment)结果与在原来的元循环求值器中写
(eval-if some-if-expression some-environment)完全相同。
但我们还想改进这个初版 analyze-if，因为它实际上并没有省掉任何工作。每次调用 analyze-if 返回的过程时，它都会把原来 eval-if 的全部工作重做一遍。
初版 analyze-if 里有三处对 eval 的调用。每一处调用都是先对表达式做分析，再在给定环境中算出值。我们要做的，是把每处 eval 调用拆成两个独立的阶段，第一阶段只做一次，不必每次都做：
(define (analyze-if exp)
(let ((pproc (analyze (if-predicate exp)))
(cproc (analyze (if-consequent exp)))
(aproc (analyze (if-alternative exp))))
(lambda (env)
(if (true? (pproc env))
(cproc env)
(aproc env)))))在这个最终版本里，analyze-if 返回的过程已经不含任何分析步骤了。所有组成部分在调用它之前就分析完毕，不需要再做任何分析。
效率提升最大的地方在于 lambda 表达式的处理方式。在原来的元循环求值器中（为清晰起见，这里省略了一些数据抽象），代码是这样的：
(define (eval-lambda exp env) (list 'procedure exp env))除了记住过程的文本和创建它时所处的环境，求值器对 lambda 表达式几乎什么都不做。但在分析式求值器中，我们会用 analyze-sequence 过程去分析过程体；此时作为过程表示形式存储的内容不再包含它的文本！取而代之，求值器在元循环 Scheme 中把一个过程表示成底层 Scheme 的一个过程，外加形式参数和定义环境。
（务必阅读 SICP 4.1.7 节，看看所有语法分析过程具体是怎么实现的。）
层次混淆
分析式求值器会把下面这样的表达式
(if A B C)转变成一个过程
(lambda (env)
(if (A-execution-procedure env)
(B-execution-procedure env)
(C-execution-procedure env)))这看起来像是倒退：我们本想实现 if，结果得到的却是一个做 if 的过程。这不是无限倒退吗？
并不是。执行过程里的那个 if 是由底层 Scheme 处理的，而不是由元循环 Scheme 处理的。因此不存在倒退——我们不会为那个 if 再去调用 analyze-if。况且底层 Scheme 的 if，比在元 Scheme 里给那个 if 做语法分析要快得多。
那又如何？
表达式语法分析是编译器工作的大头。从某种意义上说，这个分析式求值器就是一台编译器！它把 Scheme 编译成 Scheme，所以算不上实用的编译器。不过，把它改成编译成别的东西——比如某台计算机的机器语言——也并不会难多少。
结构与之类似的编译器叫做递归下降（recursive descent）编译器。如今在实践中，大多数编译器采用另一种技术（称为栈机器，stack machine），因为这种方式可以自动生成语法分析器。（我之前在讲数据导向程序设计时提到过它。）但如果是手写语法分析器，递归下降是最容易的选择。
（继续往下之前，务必先读 SICP 4.1.7 节。）
一个例子
下面用分析式求值器求值 factorial，是个很好的例子。先看这段 Scheme 代码：
(define factorial
(lambda (n)
(if (= n 1)
1
(* (factorial (- n 1)) n))))
(factorial 2) ;; 参数取小一点，例子才不会太长这里有两条语句：一条定义，一条应用。
我们先从定义开始，这里把它记为 d（即 '(define (factorial n) ...)'）：
(eval d env)
((analyze d) env)
((analyze-definition d) env)analyze-definition 会先分析 definition-value，然后创建一个执行过程；该过程被执行时，会把变量名 define 到分析后的 definition-value 上。
这一点很关键：我们赋给 factorial 的不是普通的 lambda，而是一个已分析的 lambda。这会在日后带来可观的性能收益。
那么，为了算出 factorial 的值，我们自然要用 analyze-lambda（经由 analyze 中的分发）来分析这个 lambda。
analyze-lambda 的收益，关键在于过程体只分析一次：它把分析后的过程体（一个 Scheme 过程）装进过程抽象数据类型，而不是像旧 eval 那样存一串简单的指令。
要点在于：以后每次调用我们的 lambda，都不必再做语法分析。语法分析只在创建 lambda 时做一次。
下面看它如何运作。
（注意：我会用 := 表示存储：
var := value这并不是真正的 Scheme 语法，但我觉得比写一堆 let 语句更清楚。）
(analyze-lambda '(lambda (n) ...)')现在我们需要 analyze 过程体，然后把它存起来，这样以后就不必重复分析：
analyzed-body := (analyze (lambda-body '(lambda (n) (if ...))'))
(analyze-if '(if (= n 1)
1
(* (factorial (- n 1)) n))')analyze-if 会分析传给它的全部内容，存好结果，然后用这些存好的值创建一个新的执行过程。
if-pred := (analyze '(= n 1)')
; 这就是执行过程：(lambda (env)
; (execute-application (analyzed/= env)
; ...))
if-true := (analyze '1')
; 这就是执行过程：(lambda (env) 1)
if-false := (analyze '(* (factorial (- n 1)) n)')
; 这个太长了，写不出来，不过和 if-pred 差不多
;; 这是我们返回的执行过程：
;; 把这个执行过程叫做 'analyzed-fact-if'
(lambda (env)
(if (true? (if-pred env))
(if-true env)
(if-false env)))知道了这个结果，我们再回到 analyze-lambda：
analyzed-body := analyzed-fact-if
(analyze-lambda '(lambda (n) ...)')
=> (lambda (env) (make-procedure '(n) analyzed-body env'))我们把最后一个表达式存进 factorial 变量，factorial 的定义就完成了。注意，过程体只分析一次——就在分析阶段。求值阶段从来不 analyze！这意味着求值时每次调用这个 factorial 函数，我们都知道它的过程体里有一个 if 语句，知道这个 if 判断 n 是否等于 0（以及判断为真和为假时各自该做什么）。
接下来正式求值 factorial，你会看到之前那些费解的分析工作如何带来回报。
(eval '(factorial 2) env') ; env 里有 factorial 的定义
((analyze '(factorial 2)') env)
((analyze-application '(factorial 2)') env)
((lambda (env) (execute-application ...)) env)
((procedure-body {内部的 factorial 值})
(extend-environment ...)) ; extend-environment 和旧 eval 里一样
;; 把这个扩展后的环境叫做 env2
(analyzed-body env2) ; analyzed-body 来自上面的定义
((lambda (env)
(if (true? (if-pred env))
(if-true env)
(if-false env)))
env2)
(if (true? (if-pred env2)) ; (= n 0)
(if-true env2) ; 1
(if-false env2)) ; (* (factorial (- n 1)) n)这里 n = 2 != 0，所以我们会去执行 (if-false env2)。if-false 会把 * 应用到 (factorial (- n 1)) 和 n 上，但这些参数早就 analyze 过了（在我们做 analyze-lambda 的时候）。于是我们对分析后的 (factorial (- n 1)) 求值，也就是：
(analyzed-factorial {调用 analyzed (- n 1) 的结果})
(analyzed-body env3)
;env3 := env2 扩展 n := (- {上一个 n} 1) = (- 2 1) = 1
(if (true? (if-pred env3)) ; (= n 0)
(if-true env3) ; 1
(if-false env3)) ; (* (factorial (- n 1)) n)我们用同样的方式继续递归：
(if (true? (if-pred env4)) ; (= n 0)
(if-true env4) ; 1
(if-false env4)) ; (* (factorial (- n 1)) n)这一次 n 真的等于 0，于是我们调用 (if-true env4)。if-true 不理睬 env4，直接返回数字 1。然后我们回到前面那些 execute-application 的原始应用，把所有东西乘起来。
结果是……2。
大功告成。
请注意：整个求值阶段中，我们从未检查过任何语句的语法。语法早已看过并 analyze 过了，我们只是照着这些 analyzed 语句的指示行事。想想看，计算 (factorial 100) 这类东西时，这样的效率提升有多可观。