延迟求值与 Thunks

Delayed Evaluation & Thunks.

A key semantic issue for a language construct is when are its subexpressions evaluated. 在 Racket (与包括 ML 的绝大多数语言) 中，对于一个函数调用 (e1 e2 ... en)，我们先对参数 e2, … en 进行求值再执行函数体中的内容。见下例：

1	(define (my-if-bad x y z) (if x y z))

与直觉相反，my-if-bad 并不能完全替换 if：这是因为作为函数的 my-if-bad 与作为 special-form atom 的 if 有着完全不同的 rules for evaluating subexpressions.

(my-if-bad e1 e2 e3)，作为函数，当被调用时，需要对所有参数 e1,e2,e3 进行求值。
(if x y z)，作为括号序列，if 的规则是先对 e1 求值，如果结果为 true，则对 e2 求值。反之对 e3 求值。也就是说，与函数不同，我们无需同时对 e2 与 e3 进行求值。

(define (factorial-wrong x)
  (my-if-bad (= x 0)
             1
             (* x (factorial-wrong (- x 1)))))

我们使用 my-if-bad 来替换经典阶乘算法中的 if：这个程序会因为无限递归而无法终止。原因是因为由于 my-if-bad 是函数，无论 x 是否等于 0，程序都会继续对函数体中的 (factorial-wrong (-x 1)) 进行求值。

可以看出问题的关键在于推迟对参数的求值；我们可以利用 function bodies are not evaluated until the function gets called 这一特性来实现一个可行的 my-if：

(define (my-if x y z) (if x (y) (z)))

(define (factorial x)
  (my-if (= x 0)
         (lambda () 1)
         (lambda () (* x (factorial (- x 1)))))

将所有 (if e1 e2 e3) 替换成 (my-if e1 (lambda () e2) (lambda () e3))。这样，使用 my-if 函数定义的阶乘算法不会产生无限递归的错误。

可以发现，由于我们用 lambda 创建无参匿名函数将 e2 和 e3 包了起来，在调用 my-if 时并不会对 e2 和 e3 进行求值。直到执行 my-if 的函数体并对 either y or z 进行调用时，我们才需要对 e2 或 e3 其中之一进行求值。这一逻辑与 if 本质是相同的。

1
2
3

e                            ; e will be evaluated immediately
(define x (lambda () e))     ; wrap e in a thunk
(x)                          ; e won't be evaluated until x is called

利用 function bodies are not evaluated until the function gets called 的特性，将表达式 e 封装在一个无参函数中推迟其求值的做法称为 delayed evaluation。这个无参函数被称为 thunk。

thunk.

noun. the zero-argument function wrapping e.
verb. we use “thunk the argument” to mean “use lambda () e instead of e“ to delay the evaluation of e.

使用 thunk 进行表达式的延时求值是一个常见且强大的 functional programming idiom。这并不是 Racket 特有的 —— 实际上这一部分完全可以在学习 ML 的时候进行介绍。