[ 目次, 前節, 次節, 索引 ]

   困ったことに, 並びをリストで表現したら, この優美さは計算が必要とする時と空間に関しての厳しい非効率の代価として得られている. 並びの操作をリストの変換として表現すると, プログラムは処理の各ステップで(巨大になりそうな)データ構造を構成し, 複写しなければならない.

   なぜこれがそうなのかを見るため, ある区間の素数の総和を計算する二つのプログラムを比べよう. 第一のプログラムは標準的反復の形で書いてある:53

(define (sum-primes a b)
  (define (iter count accum)
    (cond ((> count b) accum)
          ((prime? count) (iter (+ count 1) (+ count accum)))
          (else (iter (+ count 1) accum))))
  (iter a 0))

(define (sum-primes a b)
  (accumulate +
              0
              (filter prime? (enumerate-interval a b))))

   計算を実行するのに, 第一のプログラムは累積する合計を格納する記憶場所だけを必要とする. それに対し, 第二のプログラムのフィルタは, enumerate-intervalが区間内の数の完全なリストを構成するまでは, 何もすることが出来ない. フィルタは, もう一つのリストを生成する. 次にそのリストは, 総和を作って潰される前にaccumulateに渡される. そういう大きな中間記憶は第一のプログラムでは必要なかった. そこでは区間を順次に数え上げ, 素数が生成される度にそれを総和に足していると思っている.

   リストを使う非効率は, 式

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

   ストリームは並びをリストとして操作するコストを負うことなく, 並びの操作を使わせる賢明な方法である. ストリームがあれば, 二つの世界のよい所が得られる: われわれは並びの操作としてプログラムを優美に形式化し, しかも漸進的計算の効率を保つ. 基本の考えはストリームを部分的に構成するようにし, その部分的構成を, ストリームを消費するプログラムへ渡すのである. 消費側がまだ構成されていないストリームの部分にアクセスしようとすると, ストリームは要求された部分を作るべく, 自分のもう少し十分なだけを自動的に構成し, ストリーム全体が存在するかのような幻想を保つ. 別のいい方では, われわれは完全な並びを処理しているかのようにプログラムを書くが, ストリームの構成と使用が自動的かつ透明に混ざり合うようストリームの実装を設計する.

   表面的にはストリームはそれを操作する手続きに, 異る名前がついているリストである. 構成子cons-streamと二つの選択子 stream-carと stream-cdrがあり, 制約

(stream-car (cons-stream x y)) = x
(stream-cdr (cons-stream x y)) = y

を満す. 他と区別出来るオブジェクト the-empty-streamがあり, これはcons-stream演算の結果とならず, 述語 stream-null?で識別される.54 従って並びとして配置されたデータの集りを表現するのにリストを作り, 使うのと同様に, ストリームを作り, 使うことが出来る. 特にlist-ref, mapおよびfor-eachのような, 2章のリスト演算のストリーム版を作ることが出来る:55

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

   ストリームの構成と使用が自動的かつ透明に混ざり合うようにストリームを実装するためには, cons-streamでストリームが構成された時ではなく, stream-cdr手続きでアクセスされた時にストリームのcdrが評価されるようにする. この実装の選択は, 2.1.2節の有理数議論を思い起させる. そこでわれわれは有理数の実装で, 分子と分母の既約までの簡約を, 構成時と選択時のどちらで実行するか選ぶことが出来るのを見た. 有理数の両方の実装は, 同じデータ構造を生じるが, 選び方は効率に影響する. ストリームと通常のリストの間にも同様の関係がある. データ抽象としてはストリームはリストと同じである. 違いは要素が評価される時である. 通常のリストではcar とcdrは共に構成時に評価される. ストリームではcdrは選択時に評価される.

   われわれのストリームの実装はdelayという特殊形式を使う. (delay  ⟨exp⟩)の評価は式⟨exp⟩を評価せず, いわゆる 遅延オブジェクト(delayed object)を返す. これは将来ある時点に⟨exp⟩を評価する「約束」と考えることが出来る. delayの仲間に, 引数として遅延オブジェクトをとり, その評価を実行する forceという手続きがある. ---効果としてはdelayに約束を果させる. delayとforceをどう実装するかは後で見ることにし, まずこれらを使ってストリームを構成しよう.

   cons-streamは

(cons-stream ⟨a⟩ ⟨b⟩)

(cons ⟨a⟩ (delay ⟨b⟩))

(define (stream-car stream) (car stream))


(define (stream-cdr stream) (force (cdr stream)))

ストリームの実装の働き

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

   stream-enumerate-intervalを引数10,000と1,000,000で呼び出して始める. stream-enumerate-intervalはenumerate-intervalのストリーム版である(2.2.3節参照):

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

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

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

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

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

(cons 10007
      (delay
        (stream-filter
         prime?
         (cons 10008
               (delay
                 (stream-enumerate-interval 10009
                                            1000000))))))

(cons 10009
      (delay
        (stream-filter
         prime?
         (cons 10010
               (delay
                 (stream-enumerate-interval 10011
                                            1000000))))))

   一般に遅延評価は 「要求駆動」プログラミングと考えることが出来る. ストリーム処理の各段階は次の段階を満足させるのに十分なだけ起動される. これまでやったのは計算における事象の実際の順を, 手続きの見かけの構造と 切り離すことである. われわれは伝統的なプログラミングスタイルでのように, ストリームがあたかも「みんな一緒に」存在したかのように手続きを書くが, 実際は計算が漸進的に実行される.

delayとforceの実装

(delay ⟨exp⟩)

(lambda () ⟨exp⟩)

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

   この実装はdelayとforceが宣伝されているように働くには十分であるが, それに取り込み得る重要な最適化がある. 多くの応用では同一の遅延オブジェクトを何回も強制することになる. これはストリームを含む再帰プログラムではきびしい非効率になる. (問題3.57参照) 解決法は遅延オブジェクトを,最初に評価した時, 計算した値を格納するように作ることである. それに続く強制は計算を繰り返さず, 単に格納した値を返す. つまりdelay を問題3.27で述べたような特殊目的のメモ化手続きとして実装するのである. これを達成する一つの方法は, 引数として(引数なしの)手続きをとり, 手続きのメモ化版を返す次の手続きを使うことである. メモ化手続きが最初に走った時, 計算結果を退避しておく. その後の評価では, 単にその結果を返す.

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

(memo-proc (lambda () ⟨exp⟩))

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

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

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

(stream-ref x 5)

(stream-ref x 7)

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

53 素数性をテストする(1.2.6節のような)述語prime?があると仮定せよ.

54 MITの実装では, the-empty-streamは空リスト'()と同じであり, stream-null?はnull?と同じである.

55 このことで思い煩うかも知れない. ストリームとリストに対してかくも類似な手続きを定義することは, 基盤の抽象のいくらかを失うことである. 困ったことに, この抽象を利用するためには, 評価のプロセスに対し, 今出来るよりも, 細かい制御をしなければならない. この点については, 3.5.4節の最後で更に論じよう. 4.2節ではリストとストリームを統合する枠組を開発する.

56 stream-carとstream-cdrは手続きとして定義出来るが, cons-streamは特殊形式でなければならない. cons-streamが手続きなら, われわれの評価モデルに従って, (cons-stream ⟨a⟩  ⟨b⟩)は自動的に⟨b⟩を評価させ, それはまさに起きて欲しくないところである. 同様な理由でforceは通常の手続きだが, delayは特殊形式でなければならない.

57 ここに示す数値は遅延式には実際には現れない. 実際に現れるのは, 変数が適切な値に束縛されている環境での元々の式である. 例えば10001となっているところは実際は(+ low 1)が現れていて, low が10,000に束縛されている.

58 本節に述べたの以外にもストリームの可能な実装はいろいろある. ストリームを実用的にする鍵の遅延評価は Algol 60の名前呼び(call-by-name)のパラメタ渡しに由来する. この機構を使ってのストリームの実装は Landin(1965)が最初に述べた. ストリームの遅延評価は Friedmanと Wise(1976)がLispに導入した. 彼らの実装ではconsは常にその引数を遅延評価したので, リストは自動的にストリームとして振舞った. メモ化の最適化は 必要呼び(call-by-need)としても知られている. Algol社会は, われわれの遅延オブジェクトより名前呼びサンク(call-by-name thunk)といい, 最適化版より必要呼びサンク(call-by-need thunk)という方を好む.

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

[ 目次, 前節, 次節, 索引 ]