プログラミング再入門

プログラミングをもう一度ちゃんと勉強する読書ノート

SICP 3.5 Streams

LISP Scheme

SICPは計算機科学の最初に習うコースとの事ですが、最初から遅延評価を習う事に驚き。

ノート

状態をモデリングするもう一つの方法としてのストリーム。ストリームの方が複雑さをやや緩和出来る。
時々刻々と変化する実世界の状態を、状態変数とその値を変化させる代入で表現していた。
時間とともに値が変化する変数の代わりに、全ての時間を通した値を持つシーケンスを用いる。

3.5.1 Streams Are Delayed Lists

ストリームは遅延リスト。
ループを回すよりもリストの処理の方が簡潔に書けるが、リストの要素が全て揃っている必要があり大きなデータの場合にはリソースの問題が生じる。
ストリームではリスト処理をリソースを消費しない様に実現させる。
ストリームはあたかも最初から全ての要素が揃っているかの様に見せかけて、実は必要になった部分の要素のみを生成する。
delayでプロミスを作るのはschemeの標準仕様。

The stream implementation in action
(car (cdr (filter prime?
                  (enumerate-interval 10000 1000000))))

をリストではなくストリーム版に直すと

(stream-car
 (stream-cdr
  (stream-filter prime?
                 (stream-enumerate-interval 10000 1000000))))

stream-enumerate-intervalを呼ぶと返って来るオブジェクトは

(cons 10000
      (delay (stream-enumerate-interval 10001 1000000)))

car部分は10000で確定しているが、cdr部分はdelayで作られたプロミスである。

stream-filterはstream-carが素数か調べて、素数ではないのでstream-cdrを呼んでstream-filterを再帰呼び出しする。
stream-cdrは

(cons 10001
      (delay (stream-enumerate-interval 10002 1000000)))

を作り出す。
stream-carが10007になって初めて

(cons-stream (stream-car stream)
             (stream-filter pred (stream-cdr stream)))

が呼ばれて、結果のストリームが作られ始める。stream-enumerate-intervalが10009を生成した所で結果のストリームに要素が二つ出来るので、

(car (cdr (list 10007 10009 ...)))

が実行されて、10009を得る事になる。

プログラムはあたかも全てのデータが最初からリストとして揃っているかの様に書いて、そのデータが生成される過程から分離されている。

Implementing delay and force

delayは手続きとして定義は出来ないがスペシャルフォームとしてかなり簡単に定義出来る。delayの引数をlambdaの本体に入れれば良い。lambdaが評価されるまでdelayの引数は評価されない。
forceはそのlambdaを呼び出す。

ストリームが再帰呼び出しと同時に使われた時の効率を考えて（本当は参照透明性がある状況が前提だけど）delayでプロミスを作る時にメモ化する。最初だけ本当に呼び出して、２回目以降はメモされた結果を返す。

（ここでの）ストリームは確定している値を先頭に、２番目には値を生成する手続きを持つ。ストリームを先頭から何度も辿るケースを想定すると、２番目以降にある手続きはその都度評価される事になる。そこでこのリストを構成する手続きを状態変数を持った手続きにするのがmemo-proc。memo-procはストリームを構成するとき（cons-streamが展開されconsで繋げられる時）に評価され、その時点でローカル変数already-run?とresultを生成、lambdaで引数の手続き（手続きp）を呼び出す手続き（手続きmとしておく）を作って返す。この最後の手続きmがリストの要素となる。こうしておくとリストを最初に辿る時に手続きmが評価されて、そこでは引数の手続きpが呼ばれるが、２回目以降の手続きmの評価ではresultの値を返す事になる。ここで手続きpの結果は何らかの値と次の値を生成する手続きを含んだペアであり、この手続きがまたmemo-procでメモ化されている事になる。従って、一度評価されたからと言ってリストの先頭からconsペアが繋がる訳ではないが、一度評価されるとmemo-procが作るローカル変数resultを介してstream-consが作ったペアが（裏で）連結される事になり、二度目以降の評価の時にはこの裏のリンクを辿って実際の手続きを呼ばずにstream-cdrを評価して行ける事になる。

Exercse 3.50

複数のリストを引数に取るmapは

  1. それぞれの先頭要素からなるリストを作り
  2. そのリストを引数として手続きを適用して
  3. その結果をリストに纏める

なので、

  1. 各ストリームのcarにprocを適用した結果と、
  2. 各ストリームのcdrを引数にstream-mapを適用し直した結果を繋ぎ合わせる。

ストリームのcdr

(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
              (cons proc (map stream-cdr argstreams))))))

真ん中のcons-streamは第２引数を評価しないので結果は直ぐに戻される。そこでcdrにアクセスされた時に次のstream-mapが動く事になる。
動作確認のためRacketのstreamを利用して動かしてみる。stream-mapは既に定義されているのでstream-map2に、cons-streamはスペシャルフォームなので単にdefineでは置き換えられずstream-consに直す。

#lang racket
(require racket/stream)

(define stream-null? stream-empty?)
(define stream-car stream-first)
(define stream-cdr stream-rest)
(define the-empty-stream empty-stream)

(define (stream-map2 proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (stream-cons
       (apply proc (map stream-car argstreams))
       (apply stream-map2
              (cons proc (map stream-cdr argstreams))))))

(define (make-stream-sequence x y)
  (if (> x y)
      the-empty-stream
      (stream-cons x (make-stream-sequence (+ x 1) y))))
(define a (make-stream-sequence 2 6))
(define b (make-stream-sequence 5 9))
(stream->list (stream-map2 + a b))

実行結果

'(7 9 11 13 15)
>
Exercise 3.51
  1. stream-mapは最初の要素はstream-carで取り出してprocを適用するので、(define x (stream-map show (stream-enumerate-interval 0 10)))の段階で0が表示される。
  2. (stream-ref x 5)は0始まりで5番目の要素を取り出すので、stream-mapの結果として1〜5までが表示されて、stream-refの結果として5が表示される。
  3. (stream-ref x 7)は7番目の要素を取り出すので、stream-mapの結果として6,7が表示されて、stream-refの結果として7が表示される。

実際に動かして確認したい所だが、どうもRakcetのstreamパッケージとは挙動が違う様なので仕方なく自前で定義してみる。

#lang racket
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
     (cons a (delay b)))))

;(define (force delayed-object)
;  (delayed-object))

(define (display-line x)
  (display x)
  (newline))

cons-streamは引数をその場で評価してはいけないのでマクロとして定義。定義の内容はテキストの通り。
forceはdelayと同様に標準で定義されている事と、この定義では(delayed-object)を評価する時にエラーとなってしまうので標準のforceを使用する。
テキストのdisplay-lineは最初に改行する様になっているが、出力がおかしくなるのでxを表示してから改行する様に変更。
実行結果

> (define x (stream-map show (stream-enumerate-interval 0 10)))
0
> (stream-ref x 5)
1
2
3
4
5
5
> (stream-ref x 7)
6
7
7
>

重複している5と7はstream-mapでshowが表示したものと、stream-refが返した値をREPLが表示したものが重なった結果。予想通り。
ちなみに、Racketのstreamパッケージを使うと

#lang racket
(require racket/stream)

(define (stream-enumerate-interval low high)
  (if (> low high)
      empty-stream
      (stream-cons
       low
       (stream-enumerate-interval (+ low 1) high))))

(define (display-line x)
  (display x)
  (newline))

(define (show x)
  (display-line x)
  x)

このプログラムで出力は

> (define x (stream-map show (stream-enumerate-interval 0 10)))
> (stream-ref x 5)
5
5
> (stream-ref x 7)
7
7
>

余計なオブジェクトは一切作らない。

Exercise 3.52

本来対象となる数列は以下の通り。ただしstreamなので必要な分までしか生成されない。
stream-enumerate-intervalが生成する数列は(1 2 3 ... 18 19 20)。
seqは(1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210)。
yはそのうちの偶数のもの(6 10 28 36 66 78 120 136 190 210)。
zはそのうち５で割り切れるもの(10 15 45 55 105 120 190 210)。

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

stream-mapは最初の要素に付いては直ぐに評価してしまうので
sum = 1
seq = (1)

  • (define y (stream-filter even? seq))

stream-filterは最初の要素に付いては評価する。ここでは既にseq=(1)なので、1が評価される。
even?ではないのでstream-filterが再帰呼び出しされる。そこでseqの第２要素の3が生成される。この時点でsum=3。
これもeven?ではないのでstream-filterが再帰呼び出しされる。そこでseqの第３要素の6が生成される。
sum = 6
seq = (1 3 6)
y = (6)

  • (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq))

同様にstream-filterが最初の要素を出力するまで評価が進む。
sum = 10
seq = (1 3 6 10)
y = (6) … yについてはそれ以上評価は進まないので、seqの要素は増えているがy自身は変化しない。
z = (10)

  • (stream-ref y 7)

yの8番目の要素136が出現するまで評価が進む。
sum = 136
seq = (1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136)
y = (6 10 28 36 66 78 120 136)
z = (10)
stream-refの結果は136。

  • (display-stream z)

stream-for-eachは入力が空になるまでstream-carを呼び続けてしまうので全てを評価する。
sum = 210
seq = (1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210)
y = (6 10 28 36 66 78 120 136)
z = (10 15 45 55 105 120 190 210)
display-streamはzの要素を全て表示する。

> (define sum 0)
> (define (accum x)
    (set! sum (+ x sum))
    sum)
> (define seq (stream-map accum (stream-enumerate-interval 1 20)))
> sum
1
> (define y (stream-filter even? seq))
> sum
6
> y
'(6 . #<promise:...ICP/SICP Ex 3.52.rkt:5:13>)
> (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                           seq))
> sum
10
> y
'(6 . #<promise:...ICP/SICP Ex 3.52.rkt:5:13>)
> z
'(10 . #<promise:...ICP/SICP Ex 3.52.rkt:5:13>)
> (stream-ref y 7)
136
> sum
136
> y
'(6
  .
  #<promise!(10
             .
             #<promise!(28
                        .
                        #<promise!(36
                                   .
                                   #<promise!(66
                                              .
                                              #<promise!(78 . #<promise!(120 . #<promise!(136 . #<promise:...ICP/SICP Ex 3.52.rkt:5:13>)>)>)>)>)>)>)>)
> z
'(10 . #<promise:...ICP/SICP Ex 3.52.rkt:5:13>)
> (display-stream z)
10
15
45
55
105
120
190
210
'done
> sum
210
> y
'(6
  .
  #<promise!(10
             .
             #<promise!(28
                        .
                        #<promise!(36
                                   .
                                   #<promise!(66
                                              .
                                              #<promise!(78 . #<promise!(120 . #<promise!(136 . #<promise:...ICP/SICP Ex 3.52.rkt:5:13>)>)>)>)>)>)>)>)
> z
'(10
  .
  #<promise!(15
             .
             #<promise!(45 . #<promise!(55 . #<promise!(105 . #<promise!(120 . #<promise!(190 . #<promise!(210 . #<promise!()>)>)>)>)>)>)>)>)
>

delayの代わりにlambdaを使いメモ化を使わない場合、stream-cdrでseqを辿る時に毎回accumを呼んでしまう。つまり(define y ...)を評価する時にseqの先頭の1から辿って(accum 2)、(accum 3)と呼び出した所で評価は止まるが、(define zの時に再びseqの先頭の1から辿り始め(accum 2)、(accum 3)、(accum 4)を呼び出してしまう。そうするとその分sumには重複して数が足されてyのstream-mapとzのstream-mapが返す数列が変わってしまう結果となる。

  • seqを定義して(accum 1)が実行される。ここでsum=1。seq = (1 (lambda () (stream-map accum (2 3 4 ...))))（本当は2 3 4の部分もstream-enumerate-intevalによって順次生成されて行く）
  • yを定義。(accum 2)、(accum 3)まで実行される。ここでsum=6。y = (6 (stream-filter even? (stream-cdr (stream-map accum (4 5 6 ...)))))。
  • zを定義。また(accum2)が実行される。ここでsum=8。更に(assum 3)が実行されてsum=11。更に(accum 4)が実行されてsum=15。z = (15 (stream-filter (lambda () ...) (stream-map accum (5 6 7 ...))))。
  • (stream-ref y 7)はy = (6 (stream-filter even? (stream-cdr (stream-map accum (4 5 6 ...)))))から出発するので、(accum 4)から順次評価されて行く。
accum sum y
15 (6)
(accum 4) 19 (6)
(accum 5) 24 (6 24)
(accum 6) 30 6 24 30)
(accum 7) 37 (6 24 30)
(accum 8) 45 (6 24 30)
(accum 9) 54 (6 24 30 54)
(accum 10) 64 (6 24 30 54 64)
(accum 11) 75 (6 24 30 54 64)
(accum 12) 87 (6 24 30 54 64)
(accum 13) 100 (6 24 30 54 64 100)
(accum 14) 114 (6 24 30 54 64 100 114)
(accum 15) 129 (6 24 30 54 64 100 114)
(accum 16) 145 (6 24 30 54 64 100 114)
(accum 17) 162 (6 24 30 54 64 100 114 162)
  • (display-stream z)はz = (15 (stream-filter (lambda () ...) (stream-map accum (5 6 7 ...))))から出発
accum sum z
162 (15)
(accum 5) 167 (15)
(accum 6) 173 (15)
(accum 7) 180 (15 180)
(accum 8) 188 (15 180)
(accum 9) 197 (15 180)
(accum 10) 207 (15 180)
(accum 11) 218 (15 180)
(accum 12) 230 (15 180 230)
(accum 13) 243 (15 180 230)
(accum 14) 257 (15 180 230)
(accum 15) 272 (15 180 230)
(accum 16) 288 (15 180 230)
(accum 17) 305 (15 180 230 305)
(accum 18) 323 (15 180 230 305)
(accum 19) 342 (15 180 230 305)
(accum 20) 362 (15 180 230 305)

メモ化を使わない実装。

#lang racket
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
     (cons a (lambda () b)))))

(define (force delayed-object)
  (delayed-object))

…以下同文
||
実際に動かしてみる。
>|scheme|
> (define sum 0)
> (define (accum x)
    (set! sum (+ x sum))
    sum)
> (define seq (stream-map accum (stream-enumerate-interval 1 20)))
> sum
1
> (define y (stream-filter even? seq))
> sum
6
> y
'(6 . #<procedure:... Ex 3.52-opt.rkt:5:13>)
> (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                           seq))
> sum
15
> y
'(6 . #<procedure:... Ex 3.52-opt.rkt:5:13>)
> z
'(15 . #<procedure:... Ex 3.52-opt.rkt:5:13>)
> (stream-ref y 7)
162
> sum
162
> y
'(6 . #<procedure:... Ex 3.52-opt.rkt:5:13>)
> z
'(15 . #<procedure:... Ex 3.52-opt.rkt:5:13>)
> (display-stream z)
15
180
230
305
'done
> sum
362
> y
'(6 . #<procedure:... Ex 3.52-opt.rkt:5:13>)
> z
'(15 . #<procedure:... Ex 3.52-opt.rkt:5:13>)
> seq
'(1 . #<procedure:... Ex 3.52-opt.rkt:5:13>)
>

Scheme標準のdelayではなくテキストのmemo-procを実行していなかったので、実装して動かしてみる。

#lang racket
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
     (cons a (memo-proc (lambda () b))))))

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

(define (force delayed-object)
  (delayed-object))

…以下同文

実行結果

> (define sum 0)
> (define (accum x)
    (set! sum (+ x sum))
    sum)
> (define seq (stream-map accum (stream-enumerate-interval 1 20)))
> sum
1
> (define y (stream-filter even? seq))
> sum
6
> (define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                           seq))
> sum
10
> (stream-ref y 7)
136
> (display-stream z)
10
15
45
55
105
120
190
210
'done
>

ちゃんと期待通り動いている。