惰性求值

Lazy Evaluation.

在实际使用 thunk 的过程中，我们常常会遇到重复计算的情况：

1
2
3
4

(define my-mult x y-thunk
  (cond [(= x 0) 0]
        [(= x 1) (y-thunk)]
        [#t (+ (y-thunk) (my-mult (- x 1) y-thunk))]))

在这个递归实现的乘法函数中，每递归一层都需要调用一次 y-thunk。一种可行的解决方案是，在调用函数时我们使用 let 定义本地变量对调用 y-thunk 的结果进行储存。

1
2
3

(my-mult x (lambda () (+ 3 4)))                  ; ordinary call
(my-mult x (let ([z (+ 3 4)]) (lambda () z)))    ; store the result in z
(my-mult x (lambda () (let ([z (+ 3 4)]) z)))    ; wrong: the same as ordinary call

注意第三种写法是错误的；它本质上与第一种相同，因为在 let 中计算的过程仍然被包含在 thunk 中。

这种优化方式操作性不强。在这里我们介绍一个更普适的优化方案：lazy-evaluation/call-by-need/promises. 惰性求值的基本思路是利用 mutation 来对 thunk 进行记忆化，仅在需要时才对表达式进行求值。

惰性求值 (lazy evaluation) 包含两个操作：delay 与 force：

1
2
3
4
5
6
7
8
9

(define (my-delay f)
  (mcons #f f))

(define (my-force th)
  (if (mcar th)
      (mcdr th)
      (begin (set-mcar! th #t)
             (set-mcdr! th ((mcdr th)))
             (mcdr th))))

• delay: 对于 thunk f，delay 返回一个 pair。这个 pair 被称为 promise。注意，在创建 promise 的过程中 thunk 并没有被调用，所以表达式不会被计算。
  • first field 用来标记我们是否对 thunk f 进行过求值。
  • second field 初始存储 thunk f 本身。
• force: 替换朴素的 (thunk) 操作。查看 promise 的 first field，判断我们是否对 thunk f 进行过求值。
  • 若为假，对 thunk f 进行求值并将 second field mutate 为求值的结果；再将 first field 设为真。
  • 若为真，直接返回 second field 中储存的值。

接下来我们利用惰性求值对上例进行优化：

1
2
3
4
5
6

(define (my-mult x y-promise)
  (cond [(= x 0) 0]
        [(= x 1) (my-force y-promise)]
        [#t (+ (my-force y-promise) (my-mult (- x 1) my-promise))]))

(my-mult e1 (my-delay (lambda () e2)))    ; calling

在一些编程语言例如 Haskell 中，惰性求值被运用到所有的函数调用中：也就是说，对于所有的函数参数，我们要么从不对其进行求值，要么仅仅对其进行一次求值。这样的机制又被称为 call-by-need。而传统的在函数体被执行之前保证对所有的函数参数进行求值的机制被称为 call-by-value。