理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

問題 3-51 (3.5.1 Streams Are Delayed Lists)

これまで,Gauche の util.stream を使ってたんですけど,これどうも SICP に書いてあるのとは違う動作をする.実際 higepon さんも同じことを言ってた (関数型言語の勉強にSICPを読もう - (48) 3章 - 標準部品化力、オブジェクトおよび状態 (192ページ) - Higepon’s blog). 自分でどうかしようとしても,なんだかおかしくて,結局 takuya-itoh さん (2008-06-11 - TAKUYA’s CODE RECORDER) 経由で ここ を参考にしてみました.

(define-macro (delay x)
  `(memo-proc (lambda () ,x)))
(define-macro (cons-stream a b)
  `(cons ,a (delay ,b)))
(define (force x) (x))
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
(define stream-null? null?)
(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))
(define (stream-map proc s)
  (if (stream-null? s)
      the-empty-stream
      (cons-stream (proc (stream-car s))
                   (stream-map proc (stream-cdr s)))))
(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))
(define (display-stream s)
  (stream-for-each display-line s))
(define (display-line x)
  (newline)
  (display x))
(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))
(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))
(define (memo-proc proc)
  (let ((already-run? #f) (result #f))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

すると,以下のものを実行すると何が起こるか.

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

stream-map では最初の要素に対して proc を適用したものを評価するので,ストリームの最初の要素である 0 が出力されるようになってます.他のものは遅延評価の対象だから,この段階では出てません.
次に (stream-ref x 5) を評価しますが,これは目標の要素 (5 番目の要素) に辿りつくまで,stream-ref によって force を呼び出し続けます.結局,5 番目の要素に辿り着くまでの全ての要素に対して proc が呼ばれるので,1 から 5 までの出力がなされます.(stream-ref x 7) も同じですね.