正规序与应用序

惰性求值器

首先，获取我们版本的惰性求值器（lazy evaluator）：

cp ~cs61as/lib/lazy.scm .

既然求值器本身可以用 Lisp 程序写出来，我们就可以通过修改求值器，试验语言设计中的各种不同选择。事实上，新语言往往就是这么做出来的：先写一个求值器，把新语言嵌入到已有的高级语言里。

比方说，我们想和 Lisp 社区的其他人讨论对 Lisp 的某项修改，就可以给出一个体现该修改的求值器。对方可以用这个新求值器做实验，再把意见以进一步修改的形式反馈回来。在高级语言基础上实现，不仅便于测试和调试求值器，嵌入的方式还让设计者可以直接”挪用”底层语言的特性和控制结构——我们的嵌入式 Lisp 求值器就使用了底层 Lisp 的原始过程和控制结构。要到很久以后（也可能永远不需要），设计者才需要劳神用低级语言或硬件去做一个完整的实现。

本节和下一节，我们来探讨 Scheme 的几种变体，它们能带来可观的额外表达能力。

正规序与应用序回顾

在第 1 课开始讨论求值模型时我们就说过，Scheme 是一门应用序（applicative-order）语言：调用过程时，所有参数都会先求值。与之相对，正规序（normal-order）语言会把过程参数的求值推迟到真正需要参数值的时候。把过程参数的求值拖到最后一刻（比如拖到某个原始操作非它不可时）才进行，这种做法就叫惰性求值（lazy evaluation）。

来看下面这个过程：

(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 之前，两个分支的值都会被求值。惰性求值的一大好处是：有些过程（比如 unless）即使某些参数求值会出错或根本停不下来，也能做有用的计算。

检验理解

看下面的例子：

> (define (double x) (+ x x))
double
> (double (+ 2 1))
6

在应用序下，+ 会被调用几次？

在正规序下，+ 会被调用几次？

严格与非严格

如果进入过程体时某个参数还没有求值，我们就说这个过程在该参数上是非严格（non-strict）的；如果参数在进入过程体之前就已求值，我们就说这个过程在该参数上是严格（strict）的。在纯粹的应用序语言中，所有过程对每个参数都是严格的。在纯粹的正规序语言中，所有复合过程对每个参数都是非严格的，而原始过程可以是严格的，也可以是非严格的。也有些语言（见 SICP 习题 4.31）允许程序员精细控制自己定义的过程的严格性。

cons 是个很适合做成非严格的典型例子（推广开来，几乎任何数据结构构造器都是）。即使不知道元素的值，我们也照样能做有用的计算：把元素组合成数据结构，再对这些数据结构做运算。比如说，不知道列表里各个元素的值，也完全能算出表的长度。本课后面讲第 11 课的流（stream）时，我们就会用到这个思路：用非严格的 cons 对来实现流。