编程语言是怎么构造的（四 将语法分析和执行分离）

导航：
编程语言是怎么构造的（一 四则混合运算的实现）
编程语言是怎么构造的（二 变量的定义和调用）
编程语言是怎么构造的（三 函数的定义和调用）
编程语言是怎么构造的（四 将语法分析和执行分离）

---

前面的解释器虽然实现了的功能，但也非常低效，因为有关表达式的语法分析和执行交织在一起。如果一个程序要执行多次，那么对于它的语法分析也就需要做许多次。如果是一个递归那么这个分析是代价高安的，反复执行是一个浪费。我们可以对这个求值器做一个些变换，使它的效率大大提高，也就是将分析和执行分开。对一个表达式就只需要调用一次分析，然后执行过程就可以被调用多次了。分开后，eval现在变成这样：
分析和执行分开

(define (eval exp env)
  ((analyze exp) env))
;上面这段代码表示说一个过程可以分成两个过程来调用，当然实际使用中不会一次就执行了。可以现吧分析的结果放到一个过程，在后续继续执行。，如下：
(define analyzed-proc (analyze exp)) ;这儿exp是要传入的表达式
(analyzed-proc env1) ;这儿的env1 表示环境1，里面存放变量
(analyzed-proc env2) ;这儿的env2 表示环境2，里面存放变量

完整的分析函数

(define (analyze exp)
  (cond [(number? exp) (lambda (env) exp)] ;number 是自求值的表达式,例如'1 这样,这儿只是为了满足接受env作为参数的形式,其实在内部并没有使用env
        [(variable? exp) (lambda (env) (lookup-variable-value exp env))] ;查找变量的值仍然需要在执行过程种做，因为这个值依赖所用的环境，也就是说在运行时可能外部环境改变了变量的值。
        [(operator? exp) (let [(optor (syb->pro exp))] (lambda (env) optor))] ;如果是操作符,就可以在分析的时候要找到这个操作符对应的操作过程，而不需要每次执行的时候做，使这个工作只需做一次,可以提高一点效率。
        [(operation? exp) (lambda (env) ((m-eval (car exp) env) (list-of-values (cdr exp) env)))];如果是一个四则表达式,仍然要在执行过程做了。因为表达式里面可能存在变量。
        [(definition? exp) (analyze-definition exp)];如果是define表达式,就在分析阶段获取变量部分和获取值部分的工作, 然后求值部分放到执行阶段。
        [(begin? exp) (analyze-sequence (begin-actions exp))];如果是begin开头的的表达式序列,可以先做分析操作的表达式序列。
        [(if? exp) (analyze-if exp)]; if分析，这一步可以现分析条件，和真假部分。
        [(lambda? exp) (analyze-lambda exp)] ;如果是lambda 开头的就表示要创建一个复合过程
        [(procedure? exp) (lambda (env) exp)] ;如果是过程,就直接返回过程本生。
        [(start-with-pair? exp) (lambda (env) (eval-start-with-pair exp env))] ;是否是返回的函数表达式例如 ((rtf 2) 3),这个只有在执行弄了
        [(application? exp) (lambda (env) (eval-application exp env))] ;不属于上述各种情况的简单过程,执行的时候弄。
        [else (error  "unknown expression type -- m-eval" exp)]
     ))

延迟执行

这儿需要用到延迟执行的技术，比如说有的对于number类型，在分析的时候是没有用处的，还是要放到执行阶段，但是为了吧这个弄成分析和执行两个步骤，就需要用到延迟执行，这个其实非常简单:

(+ 1 2) ;如果直接写这个表达式就求值了。
(lambda () (+ 1 2)) ;表达式放到一个lambda里面就不会立即求值了，当需要的时候再调用这个lambda。

对define 语句的递归分析

最复杂的就是这个地方，define的value部分又可能是另外的一个表达式，那么又需要对value进行分析。

(define (analyze-definition exp)
  (lambda (env)
    (define-variable! (definition-variable exp) ((analyze (definition-value exp)) env) env)
    'ok
   );这儿：((analyze (definition-value exp)) env) 这个就是相当于原来的 (m-eval (definition-value exp) env)
 )

对if 语句的分析

这儿就是先吧if的条件部分，满足条件执行部分，和不满足条件执行部分 的分析的过程保存下来，再根据情况执行。

(define (analyze-if exp)
  (let [(ifproc (analyze (if-predicate exp))) (cproc (analyze(if-consequent exp))) (aproc (analyze(if-alternative exp)))]
    (lambda (env)
      (if (true? (ifproc env))
      (cproc env)
      (aproc env)
      ))))

对表达式序列的分析

对于表达式序列的分析，序列中的每一个表达式都将被分析，产生出一个执行过程。这些执行过程被组合起来形成一个执行过程。该执行过程以一个环境为参数。它以这个环境为参数，顺序调用各独立的执行过程。

;--这个地方要仔细看才看的明白
(define (analyze-sequence exps)
  (define (sequentially proc1 proc2)
    (lambda (env) (proc1 env) (proc2 env)))
  (define (loop first-proc rest-procs)
    (if (null? rest-procs)
        first-proc
        (loop (sequentially first-proc (car rest-procs))
              (cdr rest-procs))))
  (let ((procs (map analyze exps)))
    (if (null? procs)
        (error "Empty sequence -- ANALYZE"))
    (loop (car procs) (cdr procs)))
  )

最后我们来调用看看

;将这个复杂的一段程序，分析后的过程存放到analyzed-proc
(define analyzed-proc
  (analyze '(begin (define q 4)
         (define t (+ 2 q))
         (define z1 z)
         (define sqr (lambda (z)
                       (define k 3)
                       (define doub (lambda (r)
                                      (* 2 z r)))
                       (* z z (doub k))
                       )
           )

         (define (cube x) (* x x x))
         (define (dof2 f x) (f (f x)))

         (define (rtf1 x) (lambda (y) (+ 1 x y)) )
         (define (rtf2 x) (lambda (y) (+ 2 x y)) )
         (define (select-func a)
           (if (< a 2) rtf1 rtf2 ))

         (define (ssm n)
           (if (< n 2) 1 (+ n (ssm (- n 1)))))

         (define (factorial n)
           (if (< n 2) 1 (* n (factorial (- n 1)))))
         
         (+ ( - 16 (cube 3))
            (+ 2 t)
            (dof2 cube q)
            (((select-func 3) 1) 3)
            (sqr 3)
            (* y x)
            (ssm 6)
            (factorial z1)
            )
     )
   )
  )
;分别在不同的环境里面调用两次
(analyzed-proc (extend-environment '(x y z) '(1 2 3) the-empty-environment))
(analyzed-proc (extend-environment '(x y z) '(4 5 6) the-empty-environment))

得到的结果如下

262338
263070

总结

分析和执行其实不难，就是吧一个过程的执行分成两个部分。分析函数对一个表达式进行分析，然后返回一个带环境作为参数的lambda，在lambda的内容就是执行分析结果。这个也就是函数式编程里面的柯里化的应用。
这一部分的代码请到此下载