4.2  Scheme 的变形——惰性求值

现在我们有了一个用 Lisp 程序表达的求值器，只需修改求值器就可以试验语言设计中的替代选择。实际上，新语言通常是通过首先编写一个将新语言嵌入到现有高级语言中的求值器来发明的。例如，如果我们希望与 Lisp 社区的另一个成员讨论对 Lisp 的提议修改的某个方面，我们可以提供一个体现该变化的求值器。接收者随后可以试验新求值器，并发送进一步的修改意见。高级语言的实现基础不仅使测试和调试求值器更容易；此外，嵌入还使设计者能够从底层语言中³¹攫取特性，就像我们嵌入的 Lisp 求值器使用底层 Lisp 的基本过程和控制结构一样。只有到后来（如果有的话），设计者才需要费心在低级语言或硬件中构建完整的实现。在本节和下一节中，我们探索 Scheme 的一些变体，它们提供了显著的额外表达能力。

4.2.1  正则序和应用序

在第 1.1 节开始讨论求值模型时，我们注意到 Scheme 是一种应用序语言，即 Scheme 过程的所有参数都在过程应用时被求值。相比之下，正则序语言将过程参数的求值延迟到实际需要参数值时。将过程参数的求值延迟到最后一刻（例如，直到它们被基本操作需要时）称为惰性求值。³²考虑以下过程：

(define (try a b)
  (if (= a 0) 1 b))

在 Scheme 中对 (try 0 (/ 1 0)) 求值会产生错误。而在惰性求值下，则不会出错。对该表达式求值将返回 1，因为参数 (/ 1 0) 永远不会被求值。

一个利用惰性求值的例子是定义过程 unless

(define (unless condition usual-value exceptional-value)
  (if condition exceptional-value usual-value))

它可以用于诸如以下的表达式：

(unless (= b 0)
        (/ a b)
        (begin (display "exception: returning 0")
               0))

这在一个应用序语言中行不通，因为在调用 unless 之前，常规值和异常值都会被求值（对比练习 1.6）。惰性求值的一个优点是，某些过程（如 unless）即使其某些参数的求值会产生错误或不终止，也能进行有用的计算。

如果在参数被求值之前就进入过程体，我们说该过程对该参数是非严格的。如果参数在进入过程体之前被求值，我们说该过程对该参数是严格的。³³在纯应用序语言中，所有过程对每个参数都是严格的。在纯正则序语言中，所有复合过程对每个参数都是非严格的，而基本过程可以是严格的也可以是非严格的。还有一些语言（见练习 4.31）允许程序员对他们定义的过程的严格性进行精细控制。

一个可以有用地被设为非严格的过程的突出例子是 cons（或者一般来说，几乎任何数据结构的构造子）。我们可以进行有用的计算，将元素组合成数据结构并操作结果数据结构，即使元素的值未知。例如，计算一个列表的长度而不需要知道列表中各个元素的值，这是完全合理的。我们将利用这一思想，在第 4.2.3 节中将第 3 章的流实现为由非严格的 cons 序对形成的列表。

练习 4.25.  假设（在普通的应用序 Scheme 中）我们如上定义 unless，然后用 unless 定义 factorial：

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

如果我们尝试求值 (factorial 5) 会发生什么？这些定义在正则序语言中能工作吗？

练习 4.26.  Ben Bitdiddle 和 Alyssa P. Hacker 对于惰性求值在实现诸如 unless 之类的东西时的重要性有分歧。Ben 指出，在应用序中可以将 unless 实现为一种特殊形式。Alyssa 反驳说，如果那样做，unless 就仅仅是语法，而不是一个能与高阶过程结合使用的过程了。请补充双方论点的细节。展示如何将 unless 实现为派生表达式（如 cond 或 let），并给出一个将 unless 作为过程（而不是特殊形式）可能有用的例子。

4.2.2  带惰性求值的解释器

在本节中，我们将实现一个正则序语言，它与 Scheme 相同，只是复合过程对每个参数都是非严格的。基本过程将仍然是严格的。修改第 4.1.1 节的求值器并不困难，使其解释的语言表现出这种行为。几乎所有需要的修改都围绕过程应用展开。

基本思想是，当应用一个过程时，解释器必须确定哪些参数需要求值，哪些需要延迟。被延迟的参数不会被求值；相反，它们会被转换成称为 thunk 的对象。³⁴thunk 必须包含在需要时产生参数值所需的信息，就像在应用时已经求值过一样。因此，thunk 必须包含参数表达式以及过程应用被求值时的环境。

对 thunk 中的表达式求值的过程称为强制求值。³⁵通常，thunk 只在其值被需要时才会被强制求值：当它被传递给将使用 thunk 值的基本过程时；当它作为条件谓词的值时；以及当它作为即将被应用为过程的运算符的值时。我们面临的一个设计选择是是否对 thunk 进行记忆化，就像我们在第 3.5.1 节中对延迟对象所做的那样。使用记忆化，thunk 在第一次被强制求值时，会存储计算得到的值。后续的强制求值只需返回存储的值，而无需重复计算。我们将让我们的求值器进行记忆化，因为这对许多应用来说更高效。然而，这里有一些棘手的考虑。³⁶

修改求值器

惰性求值器与第 4.1 节中的求值器之间的主要区别在于 eval 和 apply 中对过程应用的处理方式。

eval 的 application? 子句变为

((application? exp)
 (apply (actual-value (operator exp) env)
        (operands exp)
        env))

这与第 4.1.1 节中 eval 的 application? 子句几乎相同。然而，对于惰性求值，我们调用 apply 时传入的是运算对象表达式，而不是对它们求值后产生的参数。由于如果参数需要被延迟，我们将需要环境来构造 thunk，所以我们也必须传递环境。我们仍然对运算符求值，因为 apply 需要实际要应用的过程，以便根据其类型（基本还是复合）进行分派并应用它。

每当我们需要表达式的实际值时，我们使用

(define (actual-value exp env)
  (force-it (eval exp env)))

而不是仅仅使用 eval，这样如果表达式的值是一个 thunk，它将被强制求值。

我们新版本的 apply 也与第 4.1.1 节中的版本几乎相同。不同之处在于 eval 传入的是未求值的运算对象表达式：对于基本过程（它们是严格的），我们在应用基本过程之前对所有参数求值；对于复合过程（它们是非严格的），我们在应用过程之前延迟所有参数。

(define (apply procedure arguments env)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure
          procedure
          (list-of-arg-values arguments env)))  ; changed
        ((compound-procedure? procedure)
         (eval-sequence
          (procedure-body procedure)
          (extend-environment
           (procedure-parameters procedure)
           (list-of-delayed-args arguments env) ; changed
           (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type -- APPLY" procedure))))

处理参数的过程与第 4.1.1 节中的 list-of-values 类似，只是 list-of-delayed-args 延迟参数而不是求值它们，而 list-of-arg-values 使用 actual-value 而不是 eval：

(define (list-of-arg-values exps env)
  (if (no-operands? exps)
      '()
      (cons (actual-value (first-operand exps) env)
            (list-of-arg-values (rest-operands exps)
                                env))))
(define (list-of-delayed-args exps env)
  (if (no-operands? exps)
      '()
      (cons (delay-it (first-operand exps) env)
            (list-of-delayed-args (rest-operands exps)
                                  env))))

我们必须修改求值器的另一个地方是 if 的处理，在测试谓词表达式是真还是假之前，我们必须使用 actual-value 而不是 eval 来获取其值：

(define (eval-if exp env)
  (if (true? (actual-value (if-predicate exp) env))
      (eval (if-consequent exp) env)
      (eval (if-alternative exp) env)))

最后，我们必须修改 driver-loop 过程（第 4.1.4 节），使用 actual-value 而不是 eval，这样如果延迟的值被传播回读取-求值-打印循环，它将在被打印之前被强制求值。我们还更改提示符以指示这是惰性求值器：

(define input-prompt ";;; L-Eval input:")
(define output-prompt ";;; L-Eval value:")
(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read)))
    (let ((output
           (actual-value input the-global-environment)))
      (announce-output output-prompt)
      (user-print output)))
  (driver-loop))

完成这些修改后，我们可以启动求值器并进行测试。在第 4.2.1 节中讨论的 try 表达式的成功求值表明解释器正在执行惰性求值：

(define the-global-environment (setup-environment))
(driver-loop)
;;; L-Eval input:
(define (try a b)
  (if (= a 0) 1 b))
;;; L-Eval value:
ok
;;; L-Eval input:
(try 0 (/ 1 0))
;;; L-Eval value:
1

thunk 的表示

我们的求值器必须安排在将过程应用于参数时创建 thunk，并在之后强制求值这些 thunk。thunk 必须将表达式与环境打包在一起，以便之后能够产生参数的值。要强制求值 thunk，我们只需从 thunk 中提取表达式和环境，并在该环境中对表达式求值。我们使用 actual-value 而不是 eval，以防表达式的值本身是一个 thunk，我们将强制求值它，依此类推，直到遇到不是 thunk 的东西：

(define (force-it obj)
  (if (thunk? obj)
      (actual-value (thunk-exp obj) (thunk-env obj))
      obj))

将表达式与环境打包的一种简单方法是创建一个包含表达式和环境的列表。因此，我们如下创建 thunk：

(define (delay-it exp env)
  (list 'thunk exp env))

(define (thunk? obj)
  (tagged-list? obj 'thunk))

(define (thunk-exp thunk) (cadr thunk))

(define (thunk-env thunk) (caddr thunk))

实际上，我们的解释器想要的并不完全是这个，而是经过记忆化的 thunk。当一个 thunk 被强制求值时，我们将其转换为一个已求值的 thunk，方法是用其值替换存储的表达式，并更改 thunk 标签，使其能被识别为已求值。³⁷

(define (evaluated-thunk? obj)
  (tagged-list? obj 'evaluated-thunk))

(define (thunk-value evaluated-thunk) (cadr evaluated-thunk))
(define (force-it obj)
  (cond ((thunk? obj)
         (let ((result (actual-value
                        (thunk-exp obj)
                        (thunk-env obj))))
           (set-car! obj 'evaluated-thunk)
           (set-car! (cdr obj) result)  ; replace exp with its value
           (set-cdr! (cdr obj) '())     ; forget unneeded env
           result))
        ((evaluated-thunk? obj)
         (thunk-value obj))
        (else obj)))

注意，同一个 delay-it 过程在有和没有记忆化的情况下都能工作。

练习 4.27.  假设我们在惰性求值器中输入以下定义：

(define count 0)
(define (id x)
  (set! count (+ count 1))
  x)

给出以下交互序列中缺失的值，并解释你的答案。³⁸

(define w (id (id 10)))
;;; L-Eval input:
count
;;; L-Eval value:
<response>
;;; L-Eval input:
w
;;; L-Eval value:
<response>
;;; L-Eval input:
count
;;; L-Eval value:
<response>

练习 4.28.  Eval 使用 actual-value 而不是 eval 在将运算符传递给 apply 之前对其求值，以便强制求值运算符的值。给出一个例子，演示这种强制求值的必要性。

练习 4.29.  展示一个程序，你预期它在没有记忆化的情况下会比有记忆化时运行得慢得多。同时，考虑以下交互，其中 id 过程的定义如练习 4.27 所示，且 count 从 0 开始：

(define (square x)
  (* x x))
;;; L-Eval input:
(square (id 10))
;;; L-Eval value:
<response>
;;; L-Eval input:
count
;;; L-Eval value:
<response>

分别给出求值器有记忆化和没有记忆化时的响应。

练习 4.30.  Cy D. Fect，一位改过自新的 C 程序员，担心某些副作用可能永远不会发生，因为惰性求值器不会强制求值序列中的表达式。由于序列中除最后一个之外的表达式的值不会被使用（表达式在那里只是为了其效果，例如给变量赋值或打印），之后不会有任何对该值的使用（例如，作为基本过程的参数）而导致它被强制求值。因此 Cy 认为在求值序列时，我们必须强制求值序列中除最后一个之外的所有表达式。他提议修改第 4.1.1 节中的 eval-sequence，使用 actual-value 而不是 eval：

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (actual-value (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

a. Ben Bitdiddle 认为 Cy 错了。他向 Cy 展示了练习 2.23 中描述的 for-each 过程，这是带有副作用的序列的一个重要例子：

(define (for-each proc items)
  (if (null? items)
      'done
      (begin (proc (car items))
             (for-each proc (cdr items)))))

他声称课本中的求值器（使用原始的 eval-sequence）能正确处理这个问题：

;;; L-Eval input:
(for-each (lambda (x) (newline) (display x))
          (list 57 321 88))
57
321
88
;;; L-Eval value:
done

解释为什么 Ben 关于 for-each 行为的看法是正确的。

b. Cy 同意 Ben 关于 for-each 例子的看法是正确的，但他说那不是他提议修改 eval-sequence 时所考虑的那类程序。他在惰性求值器中定义了以下两个过程：

(define (p1 x)
  (set! x (cons x '(2)))
  x)

(define (p2 x)
  (define (p e)
    e
    x)
  (p (set! x (cons x '(2)))))

使用原始的 eval-sequence 时，(p1 1) 和 (p2 1) 的值是什么？使用 Cy 提议的 eval-sequence 修改后，值会是什么？

c. Cy 还指出，按照他的提议修改 eval-sequence 不会影响部分 a 中示例的行为。解释为什么这是正确的。

d. 你认为在惰性求值器中应该如何处理序列？你喜欢 Cy 的方法、课本中的方法，还是其他方法？

练习 4.31.  本节采用的方法有些令人不快，因为它对 Scheme 做出了不兼容的更改。将惰性求值实现为一种向上兼容的扩展可能会更好，也就是说，这样普通的 Scheme 程序将像以前一样工作。我们可以通过扩展过程声明的语法来实现这一点，让用户控制参数是否应该被延迟。同时，我们还可以给用户选择带记忆化或不带记忆化的延迟。例如，定义

(define (f a (b lazy) c (d lazy-memo))
  ...)

将定义 f 为具有四个参数的过程，其中第一个和第三个参数在过程被调用时求值，第二个参数被延迟，第四个参数既被延迟又被记忆化。因此，普通的过程定义将产生与普通 Scheme 相同的行为，而给每个复合过程的每个参数添加 lazy-memo 声明将产生本节定义的惰性求值器的行为。设计并实现产生这种 Scheme 扩展所需的更改。你将需要实现新的语法过程来处理 define 的新语法。你还必须安排 eval 或 apply 确定何时参数应该被延迟，并相应地强制求值或延迟参数，而且你必须安排强制求值时根据情况是否进行记忆化。

4.2.3  流作为惰性列表

在第 3.5.1 节中，我们展示了如何将流实现为延迟列表。我们引入了特殊形式 delay 和 cons-stream，它们允许我们构造一个计算流 cdr 的"承诺"，而直到之后才实际履行该承诺。我们可以使用这种通用技术，在需要对求值过程进行更多控制时引入特殊形式，但这很笨拙。一方面，特殊形式不像过程那样是一等对象，所以我们不能将其与高阶过程一起使用。³⁹ 此外，我们被迫将流创建为一种与列表相似但不相同的新型数据对象，这要求我们为流重新实现许多普通的列表操作（map、append 等）。

有了惰性求值，流和列表可以完全相同，因此不需要特殊形式或单独的列表和流操作。我们所要做的就是安排 cons 是非严格的。实现这一点的一种方法是扩展惰性求值器以允许非严格的基本过程，并将 cons 实现为其中之一。更简单的方法是回想一下（第 2.1.3 节），根本没有必要将 cons 实现为基本过程。相反，我们可以将序对表示为过程：⁴⁰

(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))
(define (cdr z)
  (z (lambda (p q) q)))

基于这些基本操作，列表操作的标准定义既可以处理无限列表（流），也可以处理有限列表，而流操作可以实现为列表操作。以下是一些例子：

(define (list-ref items n)
  (if (= n 0)
      (car items)
      (list-ref (cdr items) (- n 1))))
(define (map proc items)
  (if (null? items)
      '()
      (cons (proc (car items))
            (map proc (cdr items)))))
(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))
(define (add-lists list1 list2)
  (cond ((null? list1) list2)
        ((null? list2) list1)
        (else (cons (+ (car list1) (car list2))
                    (add-lists (cdr list1) (cdr list2))))))
(define ones (cons 1 ones))
(define integers (cons 1 (add-lists ones integers)))
;;; L-Eval input:
(list-ref integers 17)
;;; L-Eval value:
18

注意，这些惰性列表甚至比第 3 章的流更懒惰：列表的 car 以及 cdr 都是被延迟的。⁴¹实际上，即使访问惰性序对的 car 或 cdr 也不需要强制求值列表元素的值。该值只会在真正需要时才会被强制求值——例如，用作基本过程的参数，或作为答案被打印。

惰性序对还有助于解决第 3.5.4 节中流出现的问题，我们发现构建带循环的系统的流模型可能需要我们在程序中散布显式的 delay 操作，超出了 cons-stream 提供的那些。有了惰性求值，过程的所有参数都被统一延迟。例如，我们可以按照第 3.5.4 节最初的意图实现积分列表和求解微分方程的过程：

(define (integral integrand initial-value dt)
  (define int
    (cons initial-value
          (add-lists (scale-list integrand dt)
                    int)))
  int)
(define (solve f y0 dt)
  (define y (integral dy y0 dt))
  (define dy (map f y))
  y)
;;; L-Eval input:
(list-ref (solve (lambda (x) x) 1 0.001) 1000)
;;; L-Eval value:
2.716924

练习 4.32.  给出一些例子，说明第 3 章的流与本节描述的"更懒惰的"惰性列表之间的区别。你如何利用这种额外的惰性？

练习 4.33.  Ben Bitdiddle 通过求值以下表达式来测试上面给出的惰性列表实现：

(car '(a b c))

令他惊讶的是，这产生了一个错误。经过一番思考，他意识到通过读取引号表达式得到的"列表"与 cons、car 和 cdr 的新定义所操作的列表是不同的。修改求值器对引号表达式的处理，使得在驱动循环中键入的引号列表能产生真正的惰性列表。

练习 4.34.  修改求值器的驱动循环，使得惰性序对和列表能以某种合理的方式打印。（对于无限列表，你将如何处理？）你可能还需要修改惰性序对的表示，以便求值器能够识别它们以便打印。