学習ログ#4 delay と force

4個目の記事なので初投稿です。

programming languages part A を終えて、part B でracket 書いてます。

遅延評価の話が出てきたので、それのメモです。

遅延評価とは値が必要になるまで、計算しないという計算方法です。

重い計算があるときに、必要ないときは計算しないようにしたり。メモ化して、一度計算したら計算結果を返すようにしたり。計算のコストを減らせます。

例えば以下のようなの関数で、掛け算をすると

； 掛け算. 第二引数が引数なしの関数
(define (my-multi x y-thunk)
 (cond [(= x 0) 0]
       [(= x 1) (y-thunk)]
       [else (+ (y-thunk) (my-multi (- x 1) y-thunk))]))

; 3 秒かかる 足し算。
(define (slow-add x y)
 (begin (sleep 3)
        (+ x y)))

; #1 0 * 7の掛け算
(my-multi 0 (lambda () (slow-add 3 4)))
; #2 3 * 7 の掛け算
(my-multi 3 (lambda () (slow-add 3 4))) 

#1の場合は slow-addが呼ばれないので、すぐに0 が帰ってきます。
遅延評価のおかげで、(y-thunk)に処理がいくまで、関数が展開されないためです。
#2の場合はslow-addが3回呼ばれるので、9秒かかってしまいます。

#2の問題はpromiseによって解決できます。

; promise
(define (my-delay th)
 (mcons #f th))

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

このdelayとforceを組み合わせると、1回目のみ計算して、2回目からは保存した計算結果を返すことが出来ます。メモ化といっしょです。

my-multiの例であれば、

; 200 * 7 の掛け算
(my-multi 200
         (let ([p (my-delay (lambda () (slow-add 3 4)))])
           (lambda () (my-force p))))

以前の方法であれば、200*3= 600秒かかる処理ですが、計算結果を保持して再計算をしないので、3秒の処理になります。また、x=0のときは、遅延評価のおかげで計算がよばれないので、すぐに結果を得られます。

このように、遅延評価やdelay forceを使うと不用な計算や再計算をしないで済むので高速になります。

以上です。また気がむいたら書きます。