profile image(wat-aro)
2015/12/09

SICP 3.5章のstreamについて

整理しなおす．
環境はGauche 0.9.4.
streamを本文通りに実装するとうまくいかない．
遅延リストになっていない．
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))))))

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

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

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

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

ここでREPLには

gosh> (define x (stream-map show (stream-enumerate-interval 0 10)))

0x

と表示されてほしい．
stream-mapのifのelse節の一行目．
(apply proc (map stream-car angstreams))となっているので(show 0)となり改行してから0を印字して
次に(define x ...)なのでxと印字することを期待したい．

ここで以下のようにstreamを実装したとする．

(define (delay exp)           
  (memo-proc (lambda () exp)))

(define (cons-stream a b)
  (cons a (delay b)))

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

(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 (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

(define (stream-null? stream)
  (null? stream))

(define the-empty-stream '())

ここで先ほどの

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

を実行すると

gosh> (define x (stream-map show (stream-enumerate-interval 0 10)))

0
1
2
3
4
5
6
7
8
9
10x

となる．
リストの先頭の要素以降の評価は遅延してほしいのにすべて評価してしまっている．
ここでマクロが必要となる．
delayとstream-cdrをマクロで実装する.

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

(define-syntax cons-stream
  (syntax-rules ()
    ((_ a b) (cons a (delay b)))))

ストリームの実装と問題3.50-3.51 - nrvctの日記

ここでふたたび

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

を実行する．

gosh> (define x (stream-map show (stream-enumerate-interval 0 10)))

0x

期待通りに動いている．
ではなぜdefineでdelayとcons-streamを実装した場合に期待通りに動かなかったのかを考える．
schemeでまはず引数を評価する．

(define s (stream-enumerate-interval 0 10)

(define x (stream-map show s))

として考えやすくする．

;; ①
(stream-map show s)

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

(cons-stream (apply show (map stream-car s))
                   (apply stream-map
                          (cons show (map stream-cdr s))))

;; cons-streamの定義
(define (cons-stream a b)
  (cons a (delay b)))

(cons (apply show (map stream-car s))
      (delay (apply stream-map
                    (cons show (map stream-cdr s)))))

;; ここでは前の引数から順に評価すると考える．
(apply show (map stream-car s))
;; -> 0

(delay (apply stream-map
              (cons show (map stream-cdr s))))

(apply stream-map
       (cons show (map stream-cdr s)))

(stream-map show (stream-cdr s))

①の式のsが(stream-cdr s)に変わっただけの式となった．
つまりここからsがnilになるまですべての要素が再帰的に評価されてしまう．
ほしいのは遅延リストなのでこれは困る.
手続きをsquareに変えると一見遅延リストのように見える．

gosh> (define x (stream-map square (stream-enumerate-interval 0 10)))
x
gosh> x
(0 . #<closure (memo-proc memo-proc)>)

ただしshowで見たように内部ではリストの末尾までmapで評価され，その評価された値がdelayで包まれている． defineだとdelayの引数とcons-streamの第二引数が先に評価されてしまうので意味がない． 評価順序を変えるためにここではマクロが必要になる．

今の理解はこんなところです．
突っ込みどころがあればお願いします．

© 2022 wat-aro