Scheme - 標準部品化力、オブジェクトおよび状態(ストリーム(ストリームは遅延リスト(ストリームの実装の働き、delayとforceの実装(メモ化による最適化の影響、注意点))))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: 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
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 3.52.

メモ化による最適化を行った場合。

(define sum 0)
sum: 0

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

(define seq (stream-map accum (stream-enumerate-interval 1 20)))
seq: (1 thunk:(2..))
sum: 1

(define y (stream-filter even? seq))
y: (3 thunk:(3..))
sum: 3
y: (6 thunk:(4..))
sum: 6

(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
z: (10 tunk:(5 ..))
sum: 10

(stream-ref y 7)
y: (6 10 15 21 28 36 45 55 66 78 91 105 120 136 thunk:(17..))
y: (6 10 28 36 66 78 120 136 thunk:(17..))
sum: 136

(display-stream z)
z: (10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210)
10
15
45
55
105
120
190
210)
sum: 210

メモ化による最適化を行わなかった場合。

(define sum 0)
sum: 0

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

(define seq (stream-map accum (stream-enumerate-interval 1 20)))
seq: (1 thunk:(2..))
sum: 1

(define y (stream-filter even? seq))
y: (3 thunk:(3..))
sum: 3
y: (6 thunk:(4..))
sum: 6

(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
seq: (8 thunk: (3..))
sum: 8
seq: (11 thunk:(4..))
sum: 11
seq: (15 thunk:(5..))
sum: 15

(stream-ref y 7)
y: (6 19 24 30 37 45 54 64 75 87 100 114 129 145 162 thunk:(18..))
y: (6 24 30 54 64 100 114 162 thunk:(18..))
sum: 162

(display-stream z)
z: (15 167 173 180 188 197 207 218 230 243 257 272 288 305 323 342 362)
z: (15 180 230 305)
15
180
230
305
sum: 362