运行求值器

运行求值器

我们来看看 Scheme 是如何运行求值器的。到目前为止，我们了解了 Scheme 表达式如何通过 mc-eval 和 mc-apply 求值。那么，求值器这个程序本身又是怎么运行起来的呢？

我们的求值器程序所做的工作，是把所有表达式都归约为原语过程的应用。因此，要运行求值器，我们只需创建一个机制，借用底层 Scheme 系统来完成原语过程的应用。

每个原语过程的名字都必须有绑定，这样当 mc-eval 求值一个原语应用的运算符时，才能找到要传给 mc-apply 的对象。因此我们建立一个全局环境，把一些独特的对象与待求值表达式中可能出现的原语过程名关联起来（例如，把 + 绑定到底层 Scheme 中同名的过程）。全局环境还包含符号 true 和 false 的绑定，这样它们就能在待求值的表达式中作为变量使用。

(define (setup-environment)
  (let ((initial-env
         (extend-environment (primitive-procedure-names)
                             (primitive-procedure-objects)
                             the-empty-environment)))
    (define-variable! 'true true initial-env)
    (define-variable! 'false false initial-env)
    initial-env))

(define the-global-environment (setup-environment))

为了方便运行元循环求值器，我们提供一个驱动循环（driver loop），模拟底层 Scheme 系统的读取-求值-打印循环（read-eval-print loop，即 REPL）。它先打印一个提示符（prompt），读取一个输入表达式，在全局环境中对该表达式求值，然后打印结果。为了让表达式的值与其他可能的输出区分开，我们在每个打印结果前加上一个输出提示符（output prompt）。

(define input-prompt ";;; M-Eval input:")
(define output-prompt ";;; M-Eval value:")

(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read)))
    (let ((output (mc-eval input the-global-environment)))
      (announce-output output-prompt)
      (user-print output)))
  (driver-loop))

(define (prompt-for-input string)
  (newline) (newline) (display string) (newline))

(define (announce-output string)
  (newline) (display string) (newline))

我们用一个特殊的打印过程 user-print，避免打印复合过程的环境部分——它可能是一张很长的表，甚至可能包含环。

(define (user-print object)
  (if (compound-procedure? object)
      (display (list 'compound-procedure
                     (procedure-parameters object)
                     (procedure-body object)
                     '(procedure-env>)))
      (display object)))

现在，运行求值器只需初始化全局环境并启动驱动循环。下面是一次示例交互：

(define the-global-environment (setup-environment))

(driver-loop)

;;; M-Eval input:
(define (append x y)
  (if (null? x)
      y
      (cons (car x)
            (append (cdr x) y))))

;;; M-Eval value:
ok

;;; M-Eval input:
(append '(a b c) '(d e f))

;;; M-Eval value:
(a b c d e f)

等等，我还是不明白。怎么可能用一个用 Scheme 写的求值器来求值 Scheme 代码呢？

这是因为 Scheme 足够强大，可以把程序当作数据来处理，还能让我们构造出既有层次结构、又可以带环的数据结构。下一节我给你打个比方。

数据即程序

要理解「用 Scheme 写的解释器去解释 Scheme 表达式」，可以把程序看作一台抽象机器的描述。例如，计算阶乘的程序：

(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))

可以看作这样一台机器的描述：它包含做减法、做乘法和相等性检验的部件，还有一个两位开关，以及另一台阶乘机器。（阶乘机器是无穷的，因为它内部还包含一台阶乘机器——这就是递归！）这台机器大致如下：

和 factorial 一样，求值器也是一台非常特殊的机器：它把其他机器的描述作为输入，然后重新配置自身去模拟给定的机器。例如，我们给求值器 factorial 的定义，求值器就会模拟它，从而能计算阶乘。

所以，我们的求值器就是一台能模拟所有其他机器的万能机器！

如果你想更深入地了解这些机器，请关注第 5 单元。

要点

在本小节中，你了解了求值器是如何工作的。

接下来？

去做作业吧！你还应该开始动手做项目 4，在那里你将学习 Python 编程语言。