Normal Order (Lazy) Evaluation
十九课
Applicative Order & Normal Order
之前，我们已经了解了一个 Scheme 解释器的重要组件以及组件之间的关系。当我们已经熟悉的 Scheme evaluator 接受到一个 application expression时，它会首先 evaluate application 中的 sub-expression，再把各个 sub-expression 的结果传入 application 表达式的 procedure，进而执行这个 procedure 得到最终结果，这种 evaluation 的方式被称为 Applicative Order。但实际上至少还有另一种 evaluation 的方式，就是推迟 sub-expression 的 evaluation 过程，先把 sub-expression 代入到 application expression，直到某个阶段必须要获取 sub-expression 的值时才去 evaluate sub-expression。总结如下：
Applicative Order: 在 evaluate expression 前先 evaluate sub-expression
Normal Order: 只在需要的时候 evaluate sub-expression
举例
> ; applicative order
> (define (foo x)
(write-line "inside foo")
(+ x x))
> (foo (begin (write-line "eval arg") 222))
eval arg
inside foo
=> 444
> ; normal order
> (define (foo x)
(write-line "inside foo")
(+ x x))
> (foo (begin (write-line "eval arg") 222))
; => (begin (write-line "inside foo")
; (+ (begin (write-line "eval arg") 222)
; (begin (write-line "eval arg") 222)))
inside foo
eval arg
eval arg
=> 444可以看见，如果用 Normal Order，sub-expression 在最后要执行 <procedure +> 的时候才被 evaluate，因此 "inside foo" 比 "eval arg" 更早被打印出来。但由于 sub-expression 被延迟 evaluate，它被执行了两次，显然这对 Normal Order 的 evaluation 方式来说是劣势。自然的，有两个疑问需要解决：
Normal Order 的好处是什么？
怎么解决 Normal Order 带来的多次 evaluation？
如何改变我们的 Scheme 解释器去实现 Normal Order Evaluation ？（接下来先解决）
Normal Order Scheme Interpreter
为了让 Scheme 解释器执行 Normal Order Evaluation，我们需要做出以下几个改动：
改变 apply 逻辑
记录 env: 因为 arguments (sub-expressions) 的 evaluation 被推迟，那么它们的 evaluation environment 就需要被记录
记录 delayed arguments 的数据结构
支持 actual value 和 delayed value
if 表达式
改变 apply 逻辑
主要有三处变化：
env: 上文提过，为了推迟 evaluation ，需要记录相应的环境
list-of-arg-values: 当执行 primitive-procedure 的时候，强制 evaluate 所有 delayed arguments
list-of-delayed-args: 将 arguments 和 env 打包起来，在之后随时可以强制 evaluate
首先我们看一下 list-of-arg-values 和 list-of-delayed-args 的实现
thunk - promise to do an evaluation
以下几个词都与 thunk 同义：
delayed value
promise to do an evaluation
promise to return a value when needed, i.e. forced
延用 data driven programming 的风格，我们可以利用 tagged list 来表示 thunk:
If expression
一些特殊表达式也需要修改，如 if 的 condition 必须要有 actual-value 才可以判断下一步是 consequence 还是 alternative:
以上，我们完成了对 Scheme 解释器的 evaluator 改造，现在它已经从 Applicative Order 变成了 Normal Order。
Memo-izing evaluation
在 Applicative Order & Normal Order 一节中，我们观察到，Normal Order 由于推迟 sub-expression 的 evaluation，而把 sub-expression 替换到 application expression 的相应位置，同时带来了重复计算 (re-evaluation) 的情况，本节我们介绍如何利用 Memo-izing Thunks 来避免重复计算。
Memo-izing Thunk 的原理再简单不过，计算一次以后就把结果记下来，下次用到的时候再拿出来即可。
具体示意图如下：
需要注意的是，为了使用 thunk 的所有地方都能立即看到 thunk 被 evaluate 过，这里使用 mutation 把 thunk 编程 evaluated-thunk:
Normal Order And Language Design (pros and cons)
Language Design Choice 和人生中的每一个选择一样，都是 trade-off，选择 Normal Order 的 trade-off 如下：
pros：只在必要的时候计算
cons:
可能造成重复计算
不确定计算发生的时间
Memo-izing evaluation 似乎可以解决 cons1，但有时候我们希望 expression 每次都被重新计算。因此解决 Normal Order 的 cons 的本质在于让程序员来决定什么时候 evaluate expression，举例如下：
a、c: applicative order
b: 每次需要的时候都重新计算
d: 只计算一次就记住结果
现在我们的 Scheme Evaluator 已经支持自由定义参数的计算方式：actual value、lazy 以及 lazy-memo。
Streams
有了 Normal Order Scheme Evaluator，我们就可以从另一个角度来看待系统。以前，我们有这些方法来理解系统：
把系统看作是一个 procedure，main procedure 里面可以分成 init、start、finish procedures，而这些 procedures 还可以继续被细化。这时候系统就是一个在规定时间执行规定命令的个体。
把系统看作是一个容器，容器内部有不同种类、不同数量的对象，这些对象互相交流、改变状态，所有对象的状态集合就是系统的状态，系统的使用者可以从中获取自己想要的信息。
还有另外一种理解：
把系统看作是时间轴上的一组状态，系统中的每个对象按时间顺序连续地输出自己的状态，从而系统能够随时知道自己的整体状况。
这里 “按时间顺序连续地输出自己的状态” 就是 Streams。
Stream Abstraction
stream 由两个部分组成，当前的值，和未来值的 promise，也可以理解成一个特殊的 pair，示意图如下：
有了它，我们可以只计算需要的部分。假设我们需要 1 - 100000000 之间的第 100 个素数，通常会这么做：
以上代码首先会遍历 1 - 100000000 之间的所有整数，找到所有素数，再从中取第 100 个素数。显然在这里我们做了很多额外的计算。我们也可以按需去获取 1 - 100000000 之间的整数，一旦找到第 100 个素数立即停止：
既然我们只计算自己想要的数据，那么就可能存在无限大小的数据结构
例1： ones
定义 ones 为每个元素都为 1 的无限序列
ones 的结构如下：
如果没有 normal order：
因为在 procedure body 中执行 (cons 1 ones) 时 ones 尚未被定义，因此抛错；而在 normal order 的情况下，(cons-stream 1 ones) 被执行时，ones 是 lazy 的，因此不会抛错。
例2：add-stream
也可以把两个无限序列相加：
例3：revisit primes
还有一种找素数的方法，就是从 2 开始，找到下一个整数，就忽略所有能被该整数整除的整数：
例4：integration
参考
Last updated