惰性求值

简介

惰性求值（Lazy evaluation）是在需要时才进行求值的计算方式。惰性求值自然地在数据结构中包含递归，可以以简单的方式表示无限的概念，这种方式有利于程序的模块化。

你可以从《Why Functional Programming Matters》中知晓惰性计算可以带来哪些好处。

Haskell语言以采用惰性求值而广为人熟知。Scheme也部分采用了惰性求值。

用于惰性求值的函数

下面这些用于处理惰性求值的函数是在R5RS中定义的。中间状态被称为延时对象（promise），它表示求值方法已经定义好了，但求值还未执行。最终的值通过对延时对象（promise）调用force被计算出来。

(delay proc)

以proc创建一个延时对象（promise）。

(promise? obj)

如果obj是一个延时对象就返回 #t。

(force promise)

对延时对象求值，执行求值操作。

惰性求值的简单例子

[例1]展示一个惰性求值的简单例子。在这个例子中，延时对象（promise）通过对(1 + 2)调用delay产生，然后通过函数force对延时对象求值。

[例1]

  1. (define laz (delay (+ 1 2)))
  2. ;Value: laz
  4. laz
  5. ;Value 11: #[promise 11]
  7. (promise? laz)
  8. ;Value: #t
  10. (force laz)
  11. ;Value: 3
  13. (* 10 (force laz))
  14. ;Value: 30

注意延时对象并没有被force消费掉，这意味着函数force没有副作用。因此，你可以重复使用延时对象。

使用惰性求值表示无限序列

现在，让我们使用惰性求值创建无限序列。首先，我将定义一些用于处理无限序列的基本函数。然后，我会使用这些函数创建无限序列，并将无限序列用于数值计算。

无限序列可以用如表达式（1）的cons单元（cons cell）的嵌套结构表示。cons单元的car和cdr分别是最终值和延时对象（promise）。另一个表达式（1）结构的cons单元通过强制求值cdr部分产生，你可以无限重复这个过程，就像图 1。这个和cons单元的嵌套结构和普通表类似，只是使用延时对象作为cdr部分使其可以表示无限序列。

  1.     (<val> . <promise>)    (1)

infiity sequence

图 1. 无限序列的实现，使用了car和cdr分别为最终值和延时对象的cons单元。

无限序列的基本函数和宏

[代码 1]展示了无限序列的基本函数和宏。其中最重要的是lazy-map，被用于操作无限序列。

由于lazy-map包含一个特殊delay构造用于延迟求值，所以它需要被定义为宏。

[代码 1]

  1. 01:     ;;;;; basic functions and a macro
  2. 02:     
  3. 03:     ;;; car for lazy evaluation
  4. 04:     (define lazy-car car)
  5. 05:     
  6. 06:     ;;; cdr for lazy evaluation
  7. 07:     (define (lazy-cdr ls)
  8. 08:       (force (cdr ls)))
  9. 09:     
  10. 10:     ;;; lazy cons
  11. 11:     (define-syntax lazy-cons
  12. 12:        (syntax-rules ()
  13. 13:           ((_ a b) (cons a (delay b)))))
  14. 14:     
  15. 15:     ;;; lazy map
  16. 16:     (define (lazy-map fn . lss)
  17. 17:       (if (memq '() lss)
  18. 18:           '()
  19. 19:         (lazy-cons (apply fn (map lazy-car lss))
  20. 20:                    (apply lazy-map fn (map lazy-cdr lss)))))
  21. 21:     
  22. 22:     ;;; lazy filter
  23. 23:     (define (lazy-filter pred ls)
  24. 24:       (if (null? ls)
  25. 25:           '()
  26. 26:         (let ((obj (lazy-car ls)))
  27. 27:           (if (pred obj)
  28. 28:               (lazy-cons obj  (lazy-filter pred (lazy-cdr ls)))
  29. 29:             (lazy-filter pred (lazy-cdr ls))))))
  30. 30:     
  31. 31:     ;;; returns n-th item of the lazy list
  32. 32:     (define (lazy-ref ls n)
  33. 33:       (if (= n 0)
  34. 34:           (lazy-car ls)
  35. 35:         (lazy-ref (lazy-cdr ls) (- n 1))))
  36. 36:     
  37. 37:     ;;; returns first n items of the ls
  38. 38:     (define (head ls n)
  39. 39:       (if (= n 0)
  40. 40:           '()
  41. 41:          (cons (lazy-car ls) (head (lazy-cdr ls) (- n 1)))))

(lazy-car ls)

和(car ls)一样，因为car部分是最终值。

(lazy-cdr ls)

计算ls的cdr部分（延时对象）的‘最终’值。

(lazy-cons a b)

这是一个扩展了(cons a (delay b))的宏。如果这个操作被定义为一个函数，b将立刻求值，这样delay就没有任何意义了。

(lazy-map fn . lss)

这是一个惰性求值的map函数，是在[代码 1]中最重要的函数。注意它返回一个包含最终值（car部分）和延时对象（cdr部分）的cons单元。

(lazy-filter pred ls)

这是一个惰性求值的filter函数。它过滤ls并返回一个由包含满足pred条件的元素组成的‘无限序列’。

(lazy-ref ls n)

返回‘无限序列’ls的第n个元素。

(head ls n)

返回ls（惰性求值表）的前n个元素。

无限序列

无限序列可以简洁地用lazy-cons和lazy-map表示。我会展示两个例子：

  • 下一项由前一项定义的序列，如等差数列和等比数列。
  • 菲波那契数列。

下一个项由前一项定义的序列

下一个项由前一项定义的序列可以有如下形式的函数（f）定义：

\[{a}_{i+1} = f({a}_i) \]

可以表示为[代码2]里的(inf-seq a0 f)，a0和f分别是初始项和用于计算随后项的函数。

(inf-seq a0 f)是递归定义的，它的定义清晰表明初始项是a0，第二项是(f a0)，(n+1)项由(f an)表示。

等差和等比数列分别被定义为(ari a0 d)和(geo a0 r)，其中a0，d和r分别是初始值，公差，公比。这些函数使用函数inf-seq定义。

[代码2]

  1. 01:     ;;;;  sequences
  2. 02:     
  3. 03:     ;;; infinite sequences represented by a_(n+1) = f(a_n)
  4. 04:     (define (inf-seq a0 f)
  5. 05:       (lazy-cons a0 (inf-seq (f a0) f)))
  6. 06:     
  7. 07:     ;;; arithmetic sequence
  8. 08:     (define (ari a0 d)
  9. 09:       (inf-seq a0 (lambda (x) (+ x d))))
  10. 10:     
  11. 11:     ;;; geometric sequence
  12. 12:     (define (geo a0 r)
  13. 13:       (inf-seq a0 (lambda (x) (* x r))))

让我们检查一下inf-seq所产生的无限序列（例2）。创建两个等比数列：

  1. g1，初始值1，公比为2。
  2. g2，初始值1，公比为1/2。

然后使用head求值前10项。你将看到正确产生了两个等比数列。

接下来，使用lazy-map计算g1和g2的乘积，并使用head求值前10项。你将看到一个全是1的序列，这表明计算被正确地执行了。

现在，让我们用等差数列和lazy-filter娱乐一番。首先，用(ari 1 1)创建一个等比数列ar1。(head ar1 10)的结果显示等比数列 (1 2 3 ....) 是由 (ari 1 1) 产生的。然后使用lazy-filter取出ar1里的偶数，并使用head求值前10项。你将看到(2 4 6 8 10 12 14 16 18 20)，这表明lazy-filter正常工作。

[例2]

  1. (define g1 (geo 1 2))
  2. ;Value: g1
  4. (define g2 (geo 1 (/ 1 2)))
  5. ;Value: g2
  7. (head g1 10)
  8. ;Value 12: (1 2 4 8 16 32 64 128 256 512)
  10. (head g2 10)
  11. ;Value 13: (1 1/2 1/4 1/8 1/16 1/32 1/64 1/128 1/256 1/512)
  13. (head (lazy-map * g1 g2) 10)
  14. ;Value 14: (1 1 1 1 1 1 1 1 1 1)
  16. (define ar1 (ari 1 1))
  17. ;;Value: ar1
  19. (head ar1 10)
  20. ;;Value 15: (1 2 3 4 5 6 7 8 9 10)
  22. (head (lazy-filter even? ar1) 10)
  23. ;;Value 16: (2 4 6 8 10 12 14 16 18 20)

菲波那切数列

菲波那切数列定义如下：

  1. fib(1) = 1
  2. fib(2) = 1
  3. fib(n+1) = fib(n) + fib(n-1)

代码3展示了Scheme实现的菲波那切数列，用到了lazy-cons和lazy-map。如代码所示，Scheme里的定义和数学上的定义很相似。此外，各个项的计算的复杂度为O(n)。

[例3]中，值被立刻计算出来了。

[代码 3]

  1. 01:     (define fib
  2. 02:       (lazy-cons 1
  3. 03:                  (lazy-cons 1
  4. 04:                             (lazy-map + fib (lazy-cdr fib)))))

[例 3]

  1. (head fib 20)
  2. ;Value 12: (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)
  4. (lazy-ref fib 100)
  5. ;Value: 573147844013817084101

将惰性求值用于数值计算

下面是《Why Functional Programming Matters》里相关代码的Schme版本。也可以查看SICP 3.5. Stream惰性计算在数值计算中的应用。

牛顿-拉夫逊法求平方根

牛顿-拉夫逊法可以使用初始值a0和等式（2）计算N的平方根。

  1.      a(n+1) =  (a(n) + N/a(n)) / 2                   (2)

如果等式（2）收敛到最终值 a，

  1.       a =  (a +  N/a) / 2
  2. ⇒
  3.       2a = a +  N/a
  4.       a =  N/a
  5.       a*a = N
  6.       a =  √N

，这表明最终值a是N的平方根。序列的下一项是前一项的函数（如等式（2）所示），这些序列可用inf-seq表示。

代码4展示了一个计算平方根的程序。在代码4中，初始值被定为1，由于序列收敛很快，所以这没问题。

[代码4]

  1. 01:     ;;; Newton-Raphson method
  2. 02:     (define (newton-raphson n)
  3. 03:       (inf-seq 1 (lambda (x) (/ (+ x (/ n x)) 2))))
  4. 04:     
  5. 05:     ;;; returning a reasonable answer.
  6. 06:     ;;; If the ratio of successive terms is in (1 - eps) and (1 + eps),
  7. 07:     ;;; or the following term is zero,
  8. 08:     ;;; the function returns it.
  9. 09:     (define (lazylist->answer ls eps)
  10. 10:       (let ((e1 (- 1.0 eps))
  11. 11:             (e2 (+ 1.0 eps)))
  12. 12:         (let loop ((val (lazy-car ls))
  13. 13:                    (ls1 (lazy-cdr ls)))
  14. 14:           (let ((val2 (lazy-car ls1)))
  15. 15:             (if  (or (zero? val2) (< e1 (/ val val2) e2))
  16. 16:                 (exact->inexact val2)
  17. 17:               (loop val2 (lazy-cdr ls1)))))))
  18. 18:     
  19. 19:     ;;;
  20. 20:     (define (my-sqrt n eps)
  21. 21:       (lazylist->answer (newton-raphson n) eps))

(newton-raphson n)

一个函数，创建平方根近似值的表。

(lazylist->answer ls eps)

检查收敛是否满足条件了。如果是的，返回数值计算的结果。

如果(1 - eps) < t2/t1 < (1 + eps) 或者 t2 = 0，函数返回 ls 的后续项（即 t1 和 t2）的第二项。

(my-sqrt n eps)

在相对误差eps下，计算n的平方根。

  1. (my-sqrt 9 0.0000001)
  2. ;Value: 3.

数值微分

[代码5]中的easydiff是一种计算数字积分的简单方式，其中f，x，和h分别是被积分的函数，x值，和Δx。理论上，如果h越趋于0，获得的近似值越好。但在实践中，由于数值在计算机里的精度是有限的，微小的h值会导致错误。

为了解决这个问题，我们用lazylist-diff创建h的惰性表。这个惰性表是初始值为h0，公比为0.5的等比数列。然后我们创建一个对应于h的惰性表的近似值的惰性表。

可以通过如下代码加快收敛速度，更快得到答案：

  1. (lazylist->answer (lazylist-diff h0 f x) eps)

函数super是收敛加速函数。可以查看《Why Functional Programming Matters》的关于加速技术部分。如果你使用了传统编程语言，加速计算会相当复杂。相反，使用惰性求值可以以简单的方式实现。此外，因为高度的模块化，你可以在其他问题中复用代码，例如数值积分（4.3.3节）。代码6复用了代码5中的加速函数。

[代码5]

  1. 01:     ;;; differentiation
  2. 02:     
  3. 03:     ;;; primitive function for differentiation
  4. 04:     (define (easydiff f x h)
  5. 05:       (/ (- (f (+ x h)) (f x)) h))
  6. 06:     
  7. 07:     ;;; create a lazy list of approximation for differentiation
  8. 08:     (define (lazylist-diff h0 f x)
  9. 09:       (lazy-map (lambda (h) (easydiff f x h)) (geo h0 0.5)))
  10. 10:     
  11. 11:     ;;; eliminate error from the approximation
  12. 12:     (define (elimerror n ls)
  13. 13:       (let ((a (lazy-car ls))
  14. 14:             (b (lazy-second ls))
  15. 15:             (c (fix:lsh 1 n)))   ; (expt 2 n)
  16. 16:         (lazy-cons
  17. 17:          (/ (- (* b c) a) (- c 1))
  18. 18:          (elimerror n (lazy-cdr ls)))))
  19. 19:     
  20. 20:     ;;; estimate `n' in elimerror
  21. 21:     (define (order ls)
  22. 22:       (let* ((a (lazy-car ls))
  23. 23:              (b (lazy-second ls))
  24. 24:              (c (lazy-ref ls 2))
  25. 25:              (d (- (/ (- a c) (- b c)) 1.0)))
  26. 26:         (cond
  27. 27:          ((< d 2) 1)
  28. 28:          ((<= 2 d 16) (inexact->exact (round (log2 d))))
  29. 29:          (else 4))))
  30. 30:     
  31. 31:     ;;;
  32. 32:     (define (log2 x)
  33. 33:       (/ (log x) (log 2)))
  34. 34:     
  35. 35:     ;;; improve convergence of the lazy list of the approximation
  36. 36:     (define (improve ls)
  37. 37:       (elimerror (order ls) ls))
  38. 38:     
  39. 39:     ;;; return the second value of the lazy list
  40. 40:     (define (lazy-second ls)
  41. 41:       (lazy-car (lazy-cdr ls)))
  42. 42:     
  43. 43:     ;;; further improve the convergence of the list
  44. 44:     (define (super ls)
  45. 45:       (lazy-map lazy-second (inf-seq ls improve)))
  46. 46:                 
  47. 47:     
  48. 48:     ;;; calculate the differentiation of function `f' at x within error eps
  49. 49:     ;;; h0 is initial window width
  50. 50:     (define (diff f x h0 eps)
  51. 51:       (lazylist->answer (super (lazylist-diff h0 f x)) eps))
  1. (diff sin 0.0 0.1 0.0000001)
  2. ;Value: .9999999999999516
  4. (diff exp 0.0 0.1 0.000001)
  5. ;Value: .9999999991733471

数值积分

收敛加速函数无需任何修改即可被用于数值积分。最开始，我们使用easyintegrate创建一个粗略的近似。函数lazylist-integrate使用惰性表，通过递归地调用easyintegrate在中间点切分区间，来改进近似值。函数可以用lazy-map以简单的方式定义。最终，收敛被加速，收敛值由函数integrate返回。

[代码6]

  1. 01:     ;;; integration
  2. 02:     
  3. 03:     ;;; primitive integration
  4. 04:     (define (easyintegrate f a b)
  5. 05:       (* (/ (+ (f a) (f b)) 2) (- b a)))
  6. 06:     
  7. 07:     ;;; create the lazy list of approximation for integration
  8. 08:     (define (lazylist-integrate f a b)
  9. 09:       (let ((mid (/ (+ a b) 2)))
  10. 10:         (lazy-cons (easyintegrate f a b)
  11. 11:                    (lazy-map + (lazylist-integrate f a mid)
  12. 12:                                (lazylist-integrate f mid b)))))
  13. 13:     
  14. 14:     ;;; integrate function `f' in a range of `a' and `b' within error `eps'
  15. 15:     (define (integrate f a b eps)
  16. 16:       (lazylist->answer (super (lazylist-integrate f a b)) eps))
  1. (define pi (* 4 (atan 1)))
  2. ;Value: pi
  4. (integrate sin 0 pi 0.0000001)
  5. ;Value: 2.000000002272428
  7. (integrate exp 0 1 0.0000001)
  8. ;Value: 1.7182818277724858
  10. (- (exp 1) 1)
  11. ;Value: 1.718281828459045

小结

惰性求值允许我们以简洁的方式将重复包含在数据结构中。这个功能有利于程序的模块化，可使代码更为紧凑。

查看网页Haskell可以了解更多关于惰性求值的内容。

你可以在这儿下载本页中出现代码。