Scheme - ストリームは遅延リスト(delay、遅延評価とメモ化手続きによる最適化)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の3(標準部品化力, オブジェクトおよび状態)、3.5(ストリーム)、3.5.1(ストリームは遅延リスト)、ストリームの実装の働き、delayとforceの実装、問題 3.52を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 3.52

各式が評価し終わったときのsumの値。

(define sum 0)
;; 0

(define (accum x)
  (set! (+ x sum))
  sum)
;; 0

(define seq (stream-map accum (stream-enumerate-interval 1 20)))
;; (accum 1)
;; 1

(define y (strem-filter even? seq))
;; 1 (accum 2):3 (accum 3):6
;; 6

(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
;; 1 3 6 (accum 4): 10
;; 10

(stream-ref y 7)
;; stream 1 3 6(0) 10(1) 15 21 28(2) 36(3) 45 55 66(4) 78(5) 91 105 120(6) 136(7)
;; ということで、評価に応じて印字される応答は136
;; sumの値は136   
(display-stream z)
;; 上記のstreamの続き 153 171 190 210
;; 印字される応答
10
15
45
55
105
120
190
210
done ;; 返される値
;; sumの値は 210

(delay <exp>)を単に(lambda () <exp>)で実装し、memo-procの用意するメモ化による最適化を使わなかった時。

(define sum 0)
;; sum 0

(define (accum x)
  (set! (+ x sum))
  sum)
;; sum 0

(define seq (strem-map accum (strem-enumerate-interval 1 20)))
;; sum 1
;; seq (stream-cons 1 (strem-map accum (strem-enumerate-interval 2 20)))
;; seq (cons 1 (delay (stream-map accum (strem-enumerate-iterval 2 20))))

(define y (strem-filter even? seq))
;; 1 (accum 2):3 (accum 3):6
;; sum 6
;; y (stream-cons 6 (strem-filter even? (stream-enumerate-interval 4 20)))
;; y (cons 6 (delay (stream-filter even? (stream-enumerate-interval 4 20))))

(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
;; 1 (accum 2):8 (accum 3): 11 (accum 4): 15
;; sum 15
;; z (stream-cons 15 (stream-filter (lambda (x) (= (remainder x 5) 0))
;;                                  (stream-map accum (stream-enumerate-interval 5 20))))

(stream-red y 7)
;; 0番目: 6
;; (accum 4): 19
;; (accum 5): 24
;; 1番目: 24
;; (accum 6): 30
;; 2番目: 30
;; (accum 7): 37
;; (accum 8): 45
;; (accum 9): 54
;; 3番目: 54
;; (accum 10): 64
;; 4番目: 64
;; (accum 11): 75
;; (accum 12): 87
;; (accum 13): 100
;; 5番目: 100
;; (accum 14): 114
;; 6番目: 114
;; (accum 15): 129
;; (accum 16): 145
;; (accum 17): 162
;; 7番目: 162
;; よって、評価に応じて印字される応答は162
;; sumの値は162

(display-stream z)
;; (accum 5): 167
;; (accum 6): 173
;; (accum 7): 180
;; (accum 8): 188
;; (accum 9): 197
;; (accum 10): 207
;; (accum 11): 218
;; (accum 12): 230
;; (accum 13): 243
;; (accum 14): 257
;; (accum 15): 272
;; (accum 16): 288
;; (accum 17): 305
;; (accum 18): 323
;; (accum 19): 342
;; (accum 20): 362
;; よって印字される応答は以下のようになる
15
180
230
305
done ;; 返される値
;; sumの値は362

memo-procの用意するメモ化による最適化を使わなかった場合、この例だと(accum 2)、(accum 3)、(accum 4)が2回以上走ることに、すなわち上記の最適化を使った場合に比べて手続きaccumによるsumへの代入する回数、数値が多くなり、その分sumの値や評価に応じて印字される応答が違ってくる。