Scheme中的流

以指派為工具對現實世界對象的狀态進行模拟時基于以下原則：

1、用具有局部狀态的計算對象去模拟現實世界中具有局部狀态的對象；

2、用計算機裡面随着時間的變化去表示真實世界中随着時間的變化，在計算機中，被模拟對象随着時間的變化是通過對那些模拟對象中的局部變量的指派實作的。

在指派模型中，需要複雜的環境模型為基礎，并且需要考慮時間問題；在并發程式中所面臨的主要困難也主要是指派時刻的非确定性問題，多個并發程序對共享變量的計算結果嚴重依賴于對變量指派的順序。為了控制并發，不得不采用多種控制機制，如串行化，屏障同步等等。在處理時間和狀态時，複制模型狀态模型會遇到很大的困難以及複雜性。

為了緩和狀态模拟中的複雜性，人們引進了一種流的資料結構，流是一種基于延時求值技術的序列結構，流處理可以模拟包含狀态的系統，但是不需要利用指派和變動資料，避免了指派帶來的内在缺陷。

序列作為組合程式的一種标準界面，能夠建構功能強大的抽象機制，但是如果将序列簡單地表示為表，那麼這種标準界面的時間效率和空間效率常常會非常低下，因為将對序列的操作表示為對表的變換時，在程式運作的每個環節都必須去構造和指派各種資料結構（他們可能規模巨大）。

       求某個區間裡的素數之和的疊代風格程式如下：

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

這個程式隻需要維持兩個變量值count和accum就可以得到最終的結果，而采用序列操作的程式：

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

實作的是同樣的功能，但是首先需要enumerate-interval構造出包含區間[a  b]内的所有整數的表，然後filter才會用謂詞prime?過濾出區間[a  b]内的所有素數的表，最後accumulate将素數表内的數累加起來得到最終結果。這個程式需要比第一個程式大得多的記憶體空間。空間效率太低。

       倘若需要通過序列方式計算從10000到1000000之間的第二個素數，這個低效情況顯得更為突出：

(car (cdr (filter prime?
                   (enumerate-interval 100001000000))))
           

程式首先需要構造出區間[10000 1000000]内所有整數的表，然後篩選出其中所有的素數，最後再取出第二個素數。這種用表來表示序列的操作進行了許多無效的中間計算，導緻程式效率極其低下。

       而流是一種非常巧妙的資料結構，不但能夠使我們繼續利用序列操作的标準界面，而且避免了将序列作為表去操作帶來的負面影響。兼顧了程式的形式與效率，流的基本思想是。做出一種安排，隻是部分地構造出流的結構，并将這樣的部分結構送給使用流的結構，如果使用者需要通路這個流尚未構造出的那個部分，那麼這個流就會自動地構造下去，但隻是做出足夠滿足當時需要的那一部分，表面上看上去整個流就好像都存在一樣。基于流的序列操作看上去都是在處理完整的序列，但是，實際上流的構造和流的使用是交錯進行的，而這種交錯對流的使用者而言又是完全透明的。

       為了使流的實作能自動地、透明地完成一個流的構造與使用的交錯進行，使得對于流的cdr的求值要等到真正通過過程stream-cdr去通路它的時候再做，而不是在通過cons-stream構造流的時候做。作為一種資料抽象，流和表完全一樣，它們的不同點在于元素的求值時間，對于正常的表來說，其car和cdr都是在構造時求值，而對于流，其cdr則是在選取的時候求值，

       流的延時求值是基于delay和force這兩個過程實作的，(delay <exp>)的求值将不對表達式<exp>求值，而是傳回一個延時對象，延時對象是對未來的某個時刻求值<exp>的允諾；而force則以一個延時對象作為參數，兌現delay的允諾，也就是對<exp>進行求值，如圖所示：

       構造流的過程cons-stream是一個特殊形式，其定義将使

(cons-stream<a> <b>)
           

等價于

(cons <a>(delay <b>))
           

流的選擇函數stream-car和stream-cdr可以定義如下：

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

stream-car選取序對的car部分，stream-cdr選取序對的cdr部分，并且求值其延時表達式，以獲得這個流的後面部分。

       再以流的方式重新寫求從10000到1000000之間的第二個素數的程式：

(stream-car
  (stream-cdr
   (stream-filter prime?
                  (stream-enumerate-interval10000 1000000))))
           

類似地，首先stream-enumerate-interval構造出區間[10000 1000000]内的整數流：

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

可以看出，stream-enumerate-interval傳回的流是由cons-stream構造的，傳回一個如下的流：

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

也就是說，stream-enumerate-interval傳回一個流，其car是10000，而其cdr則是這個流經過延時的其餘部分，如果需要，可以枚舉出這個流裡的更多東西。

然後這個流被送去過濾出素數，這個過濾器stream-filter也是一個針對流的過程：

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

stream-filter檢查輸入流的stream-car，此時就是10000，由于這個數并非素數，是以在else語句中進一步檢查輸入流的stream-cdr。由于此時輸入流的stream-cdr是一個延時對象，是以會迫使系統對延時的stream-enumerate-interval進一步求值，得到結果流：

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

由于10001不是素數，是以進一步考察上述流的stream-cdr，由于此時輸入流的stream-cdr也是一個延時對象，是以會迫使系統對延時的stream-enumerate-interval進一步求值，得到結果流：

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

然後考察10002是不是素數，如此下去，直至結果流為：

(cons 10007 (delay(stream-enumerate-interval 10008 1000000)) )
           

stream-filter檢查輸入流的stream-car，此時就是10007，這個數是素數，是以stream-filter傳回一個流：

(cons 10007
      (delay
<span style="white-space:pre">	</span>(stream-filter
<span style="white-space:pre">	</span> prime?
 <span style="white-space:pre">	</span> (cons 10008
              (delay
<span style="white-space:pre">		</span>(stream-enumerate-interval 10009 1000000))))))
           

然後過程stream-cdr通路這個流的cdr部分，迫使stream-filter對延時部分求值，由于10008不是素數，進一步迫使stream-enumerate-interval對延時部分求值，由于10009是素數，是以結果：

(cons 10009
      (delay
<span>	</span>(stream-filter
<span>	</span> prime?
 <span>	</span> (cons 10010
              (delay
<span>		</span>(stream-enumerate-interval 10011 1000000))))))
           

被送給程式的最外層那個過程stream-car，得到最終結果10009.

總結一下：

1、流處理的每個階段都僅僅活動到足夠滿足下一階段所需要的程度，流計算總是本階段在對流求出形如：cons <p1> (delay <p2>)形式的表達式之後，就将之傳回給使用這個流的下一個階段，例如過程

(stream-enumerate-interval 10000 1000000)
           

傳回的流為：

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

,這個流又馬上傳回給stream-filter去過濾素數，stream-filter在求得第一個素數之後構造出形如：

(cons 10007
      (delay
<span>	</span>(stream-filter
<span>	</span> prime?
 <span>	</span> (cons 10008
              (delay
<span>		</span>(stream-enumerate-interval 10009 1000000))))))
           

的流之後将其傳回給stream-cdr繼續求值，求值得到形如：

(cons 10009
      (delay
<span>	</span>(stream-filter
<span>	</span> prime?
 <span>	</span> (cons 10010
              (delay
<span>		</span>(stream-enumerate-interval 10011 1000000))))))
           

的流之後傳回給stream-car求值。

2、流是一種“需求驅動”的資料結構，總是在程式需要的時候才去求值，是一種構造與使用互相交替進行的資料結構。與正常表不同的是，流的cdr是在選取時才去求值的，而正常表是在構造時求值的。例如，stream-filter檢查輸入流：

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

的stream-car，是10000，由于這個數并非素數，進一步對輸入流的stream-cdr求值，構造出一個新的流：

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

由于10001不是素數，是以進一步對新的流的stream-cdr求值，構造得到另外一個流：

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

然後考察10002是不是素數，如此下去，直至構造出流：

(cons 10007 (delay(stream-enumerate-interval 10008 1000000)) )
           

由此可見，流的構造和使用（求值）是交錯進行的。