此篇為 SICP教程 6a 的筆記

找出 1,000 ~ 1,000,000 中的第二個質數

若是 流 的方式來處理，流程如下：

1. map 所有 1,000 ~ 1,000,000 的數字
2. filter 其中的質數

這顯然是非常非常佔記憶體的事情，若是更大的範圍呢，況且只是要找第二個數，用這個例子來比較傳統 時序 概念與流概念誰比較適合的話，答案反而是前者。

現在反而矛盾了，之前把 流 吹捧得這麼厲害，能把邏輯複雜的規則呈現的簡單又清楚，但實務上卻是佔記憶體且無法處理大型數據，怎麼會這樣？

其實接下來才是真正厲害的地方。

流 之所以會輸 傳統時序 的地方，就是需要 先產生所有計算要用到的數據 才進行處理，那能不能讓數據在 需要計算 的時候再進行計算呢？

如果用圖形來表示(影片當中用道具)：
失敗的流：

想像中成功的流：

當result要求一個數據，就從 流 的尾部(tail)向最後一個process拉取一個數據，最後一個process再向前一個process拉取，以此類推。只有在末端要求一定量數據時，源頭才產生定量的數據。

但有什麼 data structure 可以這樣搞？ 有的! 而且是最基本的種類，就是 "function as data" 來達成這個夢幻的 流。

首先認識幾個基本元素 con-stream, head, tail

(defn con-stream [x y]
    (cons x (delay y)))
(defn head [s] (car s))
(defn tail [s] (force (cdr s)))

• delay 所做的有兩件事 1. 產生function的表達式 2.一個執行許可，當接收到執行許可時再去執行。
• force 就是 delay 的執行許可

回到最一開始的問題，來檢視一下 夢幻流 的執行過程

(head (tail (filter prime? (map 每一個數 1000 1000000)))))

(map 每一個數 1000 1000000) -> (cons 1000 (delay (map 每一個數 1001 1000000)))

• map第一個數 1000 出來計算
• 其他的先不計算

(filter prime? (map 每一個數 1000 1000000))
-> (filter prime? 1000)
-> (filter prime?(tail (cons 1000 (delay (map 每一個數 1001 1000000)))))

• filter prime? 計算第一個數 1000
• 執行tail，force (map 每一個數 1001 1000000)
• 遞迴的對 tail 做 filter prime?
• 產生第一個質數後停止，但要求是第二個因此繼續啟動

上述可見，filter出來的數據，不會比map的還要多，因為filter去要求(force delay)的時候，數據才會產生。

真正神奇的地方 delay 與 force ，實作上也非常的簡單

(defn delay [exp] (fn [] (exp)))
(defn force [fn] (fn))

delay 神奇的地方在於將 "預期事件的執行順序" 與 "實際電腦的執行順序" 解耦開來，以至於可以用 "綜觀全局不考慮每個時間狀態" 的表示方式，做出 "最有效率，不佔無效空間" 的執行。

還有一個問題，當執行遞迴的tail時會出現 (tail (tail (tail...)))，每一次計算新的數據，就要把以前的tail都計算一次，相當沒有效率，因此若能將之前計算過的tail都記錄下來就能避免，因此將delay改成為

(defn delay [exp] (memo-proc (fn [] (exp))))

memo-proc是一個function，記錄前面所有產生過的數據，讓每一次force tail時只做一次的計算。