問題3-50〜52 - TAKUYA’s CODE RECORDER

｢3.5 ストリーム｣の節に入り、｢遅延評価｣という概念が登場してきました。｢遅延評価｣という言葉そのものは、様々なブログで紹介されていて興味を持っていましたが、それが一体何なのかということは全く知りませんでした。まだ冒頭の数ページしか読んでいませんが、なるほど、非常に興味深い概念だということを感じています。
問題に進む前に、delayやforce、cons-streamなどを自前で定義しなければなりませんので、ここを参考にしました。以下のような定義を使って、問題を解いていきたいと思っています。

(define-macro (delay x) `(lambda () ,x))
(define (force x) (x))

(define-macro (cons-stream a b) `(cons ,a (delay ,b)))
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

(define the-empty-stream '())
(define stream-null? null?)

;; memo-procを使う場合は、delayを以下のように置き換える

(define-macro (delay x) `(memo-proc (lambda () ,x)))

(define (memo-proc proc)
  (let ((already-run? #f) (result #f))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? #t)
                 result)
          result))))

問題3-50。一般化したstream-mapの実装です。

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

問題3-51。上記stream-mapなどを使って、遅延評価がどのように動くのかを観察します。

(define (show x)
  (display-line x)
  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)
;==>1
;==>2
;==>3
;==>4
;==>5
;==>6
;==>7
;=>7

xを定義した時点で、stream-mapが評価され、showに(stream-car (stream-enumerate-interval 0 10))が渡されて、0が印字されます。そのため、(stream-ref x 5)の時点では、以下のようになっています。

(stream-ref (cons-stream 0 
                         (stream-map show (stream-enumerate-interval 1 10)))
            5)

stream-refは、第二引数が0でなければ再帰処理に入りますが、その時に、第一引数にstream-cdrを適用したもの渡します。stream-cdrが(stream-map show (stream-enumerate-interval 1 10))に適用されると、これにforceが適用されて、mapが一つ進み、1が印字されます。これが5回繰り返されるという流れになっているようです。ちなみに、delayのメモ版を利用すると、(stream-ref x 7)の印字は、6と7のみとなります。1〜5は既に実行されている遅延オブジェクトであるため、show手続き内にあるdisplay-lineは実行されず、結果のxが返るのみとなります。
問題3-52。この問題には、かなり手こずってしまいましたが、何度もトレースして、紙に実行過程を記しているうちに、何とか理解することができました。自分が見落としていたポイントは、accum手続きがsumを返すという点で、stream-enumerate-intervalの先頭要素がfilterに引っかからなければ、accumが実行され、sumが返され、次にfilterにかけられるのが、このsumであるということに気づきました。sumがfilterに引っかかるまで、なんどもaccumが実行され、思っていたよりも大きな値が返ってきていたようです。delayのメモ版は試していませんが、一度実行したaccumはsumがset!されないため、メモ版を使わない時と異なる値が返ってくるのではと推測することができます。
この問題を解きながら、遅延評価は難しいなと感じてしまいましたが、注釈59に良いことが書いてあったので、それを引用しておきます。

遅延評価を印字と---もっと悪ければ代入と、混ぜ合わせると混乱する。計算機言語の科目の教師は、この節にあるような試験問題で伝統的に学生を苦しめてきた。こういう曖昧さに依存するプログラムを書くのがよくないプログラムスタイルであることはいうまでもない。ストリーム処理の能力の一部は、プログラムの中で事象が実際に起きる順を無視させることである。不幸にもこれは、時と変化に関心を持たせるべき代入のあるところでは、やってはいけないことである。

だから、

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

のような式に感動することは良いことだが、使うべき場合を考えなければならないということなのでしょう。このような視点も持ちながら、今後の内容に取り組んでいきたいと思っています。