SICP読書会(Exercise 3.50 – Exercise 3.52)

今回のあらすじ

SICPの3.5 Streamsを最初からバリバリ読んで、Exercise 3.52まで解くことにしましょう。

3.5 Streams

• これまでは局所状態を持つオブジェクトで実世界のオブジェクトをモデル化していた。
• モデルにおける時間の変化はモデルの局所状態への代入という形で実現されていた。
• これだとコンピューターにおける時間とモデル化された世界での時間が同調してしまう。

という訳で、この節では考え方を変えて

• モデルの状態 x は時刻 t によって決まる関数 x(t) だと考える
• 各時刻におけるモデルの状態を並べれば x(t) を近似できる

ということから、このモデルの状態の並びのようなデータのストリームを中心に色々と物事を考えていくようです。

3.5.1 Streams Are Delayed Lists

ここではストリームが何なのかを説明する為に2.2.3節で書いたリスト処理版のコードをストリーム版に置き換えています。

ストリーム版のコードは

• cons を cons-stream に
• car を stream-car に
• cdr を stream-cdr に
• ……

のようにペアを扱うAPIを置き換えただけです。

胆は

• cons-stream は特殊形式で、 (cons-stream a b) の b はすぐには評価されない
• stream-cdr された時点で初めて b が評価される

という点です。
ストリームの後続の要素を辿った時に初めて必要な計算が行われるので、
これでリスト処理のように簡潔なコードを保ちつつも、
リスト処理のように中間結果のリストを作ることが無くなるので効率良く処理ができます。

cons-stream と stream-cdr は特殊なもののように見えますが、

• cons-stream と stream-cdr は delay と force があれば実装できる
• delay は実のところ lambda で実現できる
• force は delay で作った手続きを呼ぶだけに過ぎない

という訳で簡単に実装できます。

ただしテキストだとSchemeでの特殊形式の定義方法は載ってないので、そこは自力で調べる必要はあります。
例えば以下のようにして定義できます:

(define-syntax delay
  (syntax-rules ()
    ((_ <exp>)
     (memo-proc (lambda () <exp>)))))

Exercise 3.50

Complete the following definition, which generalizes stream-map to allow
procedures that take multiple arguments, analogous to map in section 2.2.3,
footnote 12.

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

このテンプレートを正直に埋めると以下のコードになるんですけど:

(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))))))

例えば (stream-map proc a b c) という呼び出しがあった場合、
a の要素数が b や c より少なかった場合は問題ないのですが、
b や c の方が少なかった場合はエラーになってしまいますね。

という訳で、ちゃんと直すと以下のコードになると思います:

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

Exercise 3.51

In order to take a closer look at delayed evaluation, we will use the
following procedure, which simply returns its argument after printing it:

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

What does the interpreter print in response to evaluating each expression in
the following sequence? [59]

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

• (define ...) で 0
• (stream-ref x 5) で 1 2 3 4 5
• (stream-ref x 7) で 6 7

が出力されますね。

• stream-map はストリームの最初の要素については即座に処理するので、まず0が出力される
• stream-ref はストリームの先頭から指定個数の要素を辿るが、 stream-map による元の要素の「変換」結果はメモ化されているので、既に評価済みの要素に対して show が再実行されることはない。

ということから上記のような出力になります。

Exercise 3.52

Consider the sequence of expressions

(define sum 0)
(define (accum x)
  (set! sum (+ x sum))
  sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
(define y (stream-filter even? seq))
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
(stream-ref y 7)
(display-stream z)

これだと分かり辛いので以下のように各式に名前を付けてましょう:

(define sum 0)
(define (accum x)                                                 ; E0
  (set! sum (+ x sum))
  sum)
(print "E0: " sum ";")
(define seq (stream-map accum (stream-enumerate-interval 1 20)))  ; E1
(print "E1: " sum ";")
(define y (stream-filter even? seq))                              ; E2
(print "E2: " sum ";")
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))       ; E3
                         seq))
(print "E3: " sum ";")
(stream-ref y 7)                                                  ; E4
(print "E4: " sum ";")
(display-stream z)                                                ; E5
(print "E5: " sum ";")

また、 base = (stream-enumerate-interval 1 20) とすると、
各シーケンスの内容は以下の通りです:

base = 1  2  3  4  5  6  7  8  9 10 11 12 13  14  15  16  17  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              120             190 210

What is the value of sum after each of the above expressions is evaluated?

• E0では0です。 seq はまだ処理されていないからです。
• E1では1です。 stream-map により seq の最初の要素が即座に処理されるからです。
• E2では6です。 stream-filter は条件に合致する要素が見つかるまで seq を辿るからです。
• E3では10です。E2と同じ理屈です。
• E4では136です。 y の(0から数え始めて)7番目の要素が得られるまで seq が辿られるからです。
• E5では210です。 display-stream により seq が最後まで辿られるからです。

What is the printed response to evaluating the stream-ref and
display-stream expressions?

• stream-ref: 136
• display-stream: 10, 15, 45, 55, 120, 190, 210

になりますね。

Would these responses differ if we had implemented (delay <exp>) simply as
(lambda () <exp>) without using the optimization provided by memo-proc?
Explain.

当然結果は変わりますね。
メモ化されていなければ
seq に対して stream-cdr = 列挙される度に accum が呼ばれることになります。
そして seq はE2-E5で四重に列挙されるからです。

多分、

• E0: 0 (seq は列挙されてない)
• E1: 1 (seq 定義時の stream-map により1が accum される)
• E2: 1 + (2 + 3) = 6 (y 定義時の seq の列挙で base = 2-3 まで列挙される)
• E3: 6 + (2 + 3 + 4) = 15 (z 定義時の seq の列挙で base = 2-4 が列挙される。ただし seq の戻り値は accum の結果なので、E2時点の結果6に2-4の総和を加えたものが z の条件に合う最初の要素になる)
• E4: 15 + (4 + 5 + … + 17) = 162 (y の(0から数え始めて)7番目の要素が得られるまで seq が列挙される。 y の最初の要素の分で既に seq は base = 3 まで列挙済みなので、ここでは base = 4-17 までが列挙される)
• E5: 162 + (5 + 6 + … + 20) = 362 (E4 と同じ理屈で base = 5-20 が列挙される)

ですね。なので

• stream-ref: 162
• display-stream: 15, 180, 230, 305

になります。

次回予告

3.5.2 Infinite Streams
を読んで、その後は片っ端から問題を解いていきましょう。