第十七章 惰性求值

簡(jiǎn)介

惰性求值（Lazy evaluation）是在需要時(shí)才進(jìn)行求值的計(jì)算方式。惰性求值自然地在數(shù)據(jù)結(jié)構(gòu)中包含遞歸，可以以簡(jiǎn)單的方式表示無(wú)限的概念，這種方式有利于程序的模塊化。

你可以從《Why Functional Programming Matters》中知曉惰性計(jì)算可以帶來(lái)哪些好處。

Haskell語(yǔ)言以采用惰性求值而廣為人熟知。Scheme也部分采用了惰性求值。

用于惰性求值的函數(shù)

下面這些用于處理惰性求值的函數(shù)是在R5RS中定義的。中間狀態(tài)被稱(chēng)為延時(shí)對(duì)象（promise），它表示求值方法已經(jīng)定義好了，但求值還未執(zhí)行。最終的值通過(guò)對(duì)延時(shí)對(duì)象（promise）調(diào)用force被計(jì)算出來(lái)。

(delay proc)

以proc創(chuàng)建一個(gè)延時(shí)對(duì)象（promise）。

(promise? obj)

如果obj是一個(gè)延時(shí)對(duì)象就返回 #t。

(force promise)

對(duì)延時(shí)對(duì)象求值，執(zhí)行求值操作。

惰性求值的簡(jiǎn)單例子

[例1]展示一個(gè)惰性求值的簡(jiǎn)單例子。在這個(gè)例子中，延時(shí)對(duì)象（promise）通過(guò)對(duì)(1 + 2)調(diào)用delay產(chǎn)生，然后通過(guò)函數(shù)force對(duì)延時(shí)對(duì)象求值。

[例1]

(define laz (delay (+ 1 2)))
;Value: laz

laz
;Value 11: #[promise 11]

(promise? laz)
;Value: #t

(force laz)
;Value: 3

(* 10 (force laz))
;Value: 30

注意延時(shí)對(duì)象并沒(méi)有被force消費(fèi)掉，這意味著函數(shù)force沒(méi)有副作用。因此，你可以重復(fù)使用延時(shí)對(duì)象。

使用惰性求值表示無(wú)限序列

現(xiàn)在，讓我們使用惰性求值創(chuàng)建無(wú)限序列。首先，我將定義一些用于處理無(wú)限序列的基本函數(shù)。然后，我會(huì)使用這些函數(shù)創(chuàng)建無(wú)限序列，并將無(wú)限序列用于數(shù)值計(jì)算。

無(wú)限序列可以用如表達(dá)式（1）的cons單元（cons cell）的嵌套結(jié)構(gòu)表示。cons單元的car和cdr分別是最終值和延時(shí)對(duì)象（promise）。另一個(gè)表達(dá)式（1）結(jié)構(gòu)的cons單元通過(guò)強(qiáng)制求值cdr部分產(chǎn)生，你可以無(wú)限重復(fù)這個(gè)過(guò)程，就像圖 1。這個(gè)和cons單元的嵌套結(jié)構(gòu)和普通表類(lèi)似，只是使用延時(shí)對(duì)象作為cdr部分使其可以表示無(wú)限序列。

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

圖 1. 無(wú)限序列的實(shí)現(xiàn)，使用了car和cdr分別為最終值和延時(shí)對(duì)象的cons單元。

無(wú)限序列的基本函數(shù)和宏

[代碼 1]展示了無(wú)限序列的基本函數(shù)和宏。其中最重要的是lazy-map，被用于操作無(wú)限序列。

由于lazy-map包含一個(gè)特殊delay構(gòu)造用于延遲求值，所以它需要被定義為宏。

[代碼 1]

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

(lazy-car ls)

和(car ls)一樣，因?yàn)閏ar部分是最終值。

(lazy-cdr ls)

計(jì)算ls的cdr部分（延時(shí)對(duì)象）的‘最終’值。

(lazy-cons a b)

這是一個(gè)擴(kuò)展了(cons a (delay b))的宏。如果這個(gè)操作被定義為一個(gè)函數(shù)，b將立刻求值，這樣delay就沒(méi)有任何意義了。

(lazy-map fn . lss)

這是一個(gè)惰性求值的map函數(shù)，是在[代碼 1]中最重要的函數(shù)。注意它返回一個(gè)包含最終值（car部分）和延時(shí)對(duì)象（cdr部分）的cons單元。

(lazy-filter pred ls)

這是一個(gè)惰性求值的filter函數(shù)。它過(guò)濾ls并返回一個(gè)由包含滿(mǎn)足pred條件的元素組成的‘無(wú)限序列’。

(lazy-ref ls n)

返回‘無(wú)限序列’ls的第n個(gè)元素。

(head ls n)

返回ls（惰性求值表）的前n個(gè)元素。

無(wú)限序列

無(wú)限序列可以簡(jiǎn)潔地用lazy-cons和lazy-map表示。我會(huì)展示兩個(gè)例子：

• 下一項(xiàng)由前一項(xiàng)定義的序列，如等差數(shù)列和等比數(shù)列。
• 菲波那契數(shù)列。

下一個(gè)項(xiàng)由前一項(xiàng)定義的序列

下一個(gè)項(xiàng)由前一項(xiàng)定義的序列可以有如下形式的函數(shù)（f）定義：

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

可以表示為[代碼2]里的(inf-seq a0 f)，a0和f分別是初始項(xiàng)和用于計(jì)算隨后項(xiàng)的函數(shù)。

(inf-seq a0 f)是遞歸定義的，它的定義清晰表明初始項(xiàng)是a0，第二項(xiàng)是(f a0)，(n+1)項(xiàng)由(f an)表示。

等差和等比數(shù)列分別被定義為(ari a0 d)和(geo a0 r)，其中a0，d和r分別是初始值，公差，公比。這些函數(shù)使用函數(shù)inf-seq定義。

[代碼2]

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

讓我們檢查一下inf-seq所產(chǎn)生的無(wú)限序列（例2）。創(chuàng)建兩個(gè)等比數(shù)列：

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

然后使用head求值前10項(xiàng)。你將看到正確產(chǎn)生了兩個(gè)等比數(shù)列。

接下來(lái)，使用lazy-map計(jì)算g1和g2的乘積，并使用head求值前10項(xiàng)。你將看到一個(gè)全是1的序列，這表明計(jì)算被正確地執(zhí)行了。

現(xiàn)在，讓我們用等差數(shù)列和lazy-filter娛樂(lè)一番。首先，用(ari 1 1)創(chuàng)建一個(gè)等比數(shù)列ar1。(head ar1 10)的結(jié)果顯示等比數(shù)列 (1 2 3 ....) 是由 (ari 1 1) 產(chǎn)生的。然后使用lazy-filter取出ar1里的偶數(shù)，并使用head求值前10項(xiàng)。你將看到(2 4 6 8 10 12 14 16 18 20)，這表明lazy-filter正常工作。

[例2]

(define g1 (geo 1 2))
;Value: g1

(define g2 (geo 1 (/ 1 2)))
;Value: g2

(head g1 10)
;Value 12: (1 2 4 8 16 32 64 128 256 512)

(head g2 10)
;Value 13: (1 1/2 1/4 1/8 1/16 1/32 1/64 1/128 1/256 1/512)

(head (lazy-map * g1 g2) 10)
;Value 14: (1 1 1 1 1 1 1 1 1 1)

(define ar1 (ari 1 1))
;;Value: ar1

(head ar1 10)
;;Value 15: (1 2 3 4 5 6 7 8 9 10)

(head (lazy-filter even? ar1) 10)
;;Value 16: (2 4 6 8 10 12 14 16 18 20)

菲波那切數(shù)列

菲波那切數(shù)列定義如下：

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

代碼3展示了Scheme實(shí)現(xiàn)的菲波那切數(shù)列，用到了lazy-cons和lazy-map。如代碼所示，Scheme里的定義和數(shù)學(xué)上的定義很相似。此外，各個(gè)項(xiàng)的計(jì)算的復(fù)雜度為O(n)。

[例3]中，值被立刻計(jì)算出來(lái)了。

[代碼 3]

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

[例 3]

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

(lazy-ref fib 100)
;Value: 573147844013817084101

將惰性求值用于數(shù)值計(jì)算

下面是《Why Functional Programming Matters》里相關(guān)代碼的Schme版本。

牛頓-拉夫遜法求平方根

牛頓-拉夫遜法可以使用初始值a0和等式（2）計(jì)算N的平方根。

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

如果等式（2）收斂到最終值 a，

      a =  (a +  N/a) / 2
?
      2a = a +  N/a
      a =  N/a
      a*a = N
      a =  √N(yùn)

，這表明最終值a是N的平方根。序列的下一項(xiàng)是前一項(xiàng)的函數(shù)（如等式（2）所示），這些序列可用inf-seq表示。

代碼4展示了一個(gè)計(jì)算平方根的程序。在代碼4中，初始值被定為1，由于序列收斂很快，所以這沒(méi)問(wèn)題。

[代碼4]

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

(newton-raphson n)

一個(gè)函數(shù)，創(chuàng)建平方根近似值的表。

(lazylist->answer ls eps)

檢查收斂是否滿(mǎn)足條件了。如果是的，返回?cái)?shù)值計(jì)算的結(jié)果。

如果(1 - eps) < t2/t1 < (1 + eps) 或者 t2 = 0，函數(shù)返回 ls 的后續(xù)項(xiàng)（即 t1 和 t2）的第二項(xiàng)。

(my-sqrt n eps)

在相對(duì)誤差eps下，計(jì)算n的平方根。

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

數(shù)值微分

[代碼5]中的easydiff是一種計(jì)算數(shù)字積分的簡(jiǎn)單方式，其中f，x，和h分別是被積分的函數(shù)，x值，和Δx。理論上，如果h越趨于0，獲得的近似值越好。但在實(shí)踐中，由于數(shù)值在計(jì)算機(jī)里的精度是有限的，微小的h值會(huì)導(dǎo)致錯(cuò)誤。

為了解決這個(gè)問(wèn)題，我們用lazylist-diff創(chuàng)建h的惰性表。這個(gè)惰性表是初始值為h0，公比為0.5的等比數(shù)列。然后我們創(chuàng)建一個(gè)對(duì)應(yīng)于h的惰性表的近似值的惰性表。

可以通過(guò)如下代碼加快收斂速度，更快得到答案：

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

函數(shù)super是收斂加速函數(shù)?？梢圆榭础禬hy Functional Programming Matters》的關(guān)于加速技術(shù)部分。如果你使用了傳統(tǒng)編程語(yǔ)言，加速計(jì)算會(huì)相當(dāng)復(fù)雜。相反，使用惰性求值可以以簡(jiǎn)單的方式實(shí)現(xiàn)。此外，因?yàn)楦叨鹊哪K化，你可以在其他問(wèn)題中復(fù)用代碼，例如數(shù)值積分（4.3.3節(jié)）。代碼6復(fù)用了代碼5中的加速函數(shù)。

[代碼5]

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

(diff sin 0.0 0.1 0.0000001)
;Value: .9999999999999516

(diff exp 0.0 0.1 0.000001)
;Value: .9999999991733471

數(shù)值積分

收斂加速函數(shù)無(wú)需任何修改即可被用于數(shù)值積分。最開(kāi)始，我們使用easyintegrate創(chuàng)建一個(gè)粗略的近似。函數(shù)lazylist-integrate使用惰性表，通過(guò)遞歸地調(diào)用easyintegrate在中間點(diǎn)切分區(qū)間，來(lái)改進(jìn)近似值。函數(shù)可以用lazy-map以簡(jiǎn)單的方式定義。最終，收斂被加速，收斂值由函數(shù)integrate返回。

[代碼6]

     ;;; integration
     
     ;;; primitive integration
     (define (easyintegrate f a b)
       (* (/ (+ (f a) (f b)) 2) (- b a)))
     
     ;;; create the lazy list of approximation for integration
     (define (lazylist-integrate f a b)
       (let ((mid (/ (+ a b) 2)))
         (lazy-cons (easyintegrate f a b)
                    (lazy-map + (lazylist-integrate f a mid)
                                (lazylist-integrate f mid b)))))
     
     ;;; integrate function `f' in a range of `a' and `b' within error `eps'
     (define (integrate f a b eps)
       (lazylist->answer (super (lazylist-integrate f a b)) eps))

(define pi (* 4 (atan 1)))
;Value: pi

(integrate sin 0 pi 0.0000001)
;Value: 2.000000002272428

(integrate exp 0 1 0.0000001)
;Value: 1.7182818277724858

(- (exp 1) 1)
;Value: 1.718281828459045

小結(jié)

惰性求值允許我們以簡(jiǎn)潔的方式將重復(fù)包含在數(shù)據(jù)結(jié)構(gòu)中。這個(gè)功能有利于程序的模塊化，可使代碼更為緊湊。