11 min to read
CIS 194 06 Lazy evaluation 惰性評估
Source: 06-laziness
▌Lazy evaluation 惰性評估
CIS 194 第 6 週 2012 年 2 月 18 日
建議閱讀：
- foldr foldl foldl’ from the Haskell wiki
在上課的第一天，我提到 Haskell 是 惰性 (Lazy)，並承諾最終會詳細解釋這意味著什麼。時機已到！
▌Strict evaluation 嚴格評估
在我們討論 惰性評估 (Lazy evaluation)之前，先看看一些相反的示例會很有用 —— 嚴格評估 (Strict evaluation)
在嚴格的評估策略下，在 將函數參數傳遞給函數 之前 ，會對它們進行完全評估。例如，假設我們已經定義
f x y = x + 2
用嚴格的語言來說，在將結果傳遞給之前，評估 f 5 (29^35792) 會先完全評估 5（已經完成）和 29^35792（這是很多工作），然後再將結果傳遞給 f
當然，在此特定示例中，這很愚蠢，因為 f 忽略了它的第二個參數，所以所有用於計算 29 ^ 35792 的工作都被浪費了。 那麼為什麼我們要這個呢？
嚴格評估的好處在於，很容易預測事情發生的 時間 和 順序 。通常，具有嚴格評估的語言甚至會指定函數參數評估的順序（例如，從左到右）
例如，在 Java 中，如果我們編寫
f (release_monkeys(), increment_counter())
我們知道猴子將被釋放，然後計數器將增加，然後將執行這些操作的結果傳遞給f，而 f 實際上是否最終使用這些結果也無關緊要
如果釋放猴子和計數器的增加可以獨立發生，或不以任何順序發生，無論哪種順序，這取決於 f 是否恰好使用它們的結果，這將非常令人困惑。 如果允許這種 “副作用 (side effects)”，那麼您真正想要的是嚴格評估
▌Side effects and purity 副作用和純度
因此，真正的問題是副作用的存在與否。 所謂“副作用”，是指導致表達式評估與自身之外的事物發生相互作用的任何事物。 根本問題是這種外部交互對時間敏感。 例如：
- 修改全局變量 — 這很重要，因為這可能會影響其他表達式的求值
- 在屏幕上打印 — 發生這種情況很重要，因為相對於屏幕上的其他寫入，可能需要按照一定的順序進行
- 從文件或網絡讀取 — 發生這種情況很重要，因為文件的內容會影響表達式的結果
如我們所見，懶惰的評估使人們難以推理何時評估事物。因此在懶惰的語言中包含副作用將非常不直觀。從歷史上看，這就是 Haskell 純粹的原因：最初，Haskell 的設計師想要製作一種懶惰的函數式語言，並很快意識到，除非它也不允許副作用，否則這是不可能的
但是 …… 沒有 副作用的語言不是很有用。使用這種語言唯一可以做的就是將程序加載到解釋器中並評估表達式。（嗯 …… 聽起來很熟悉 ……）您將無法從用戶那裡獲得任何輸入，也無法在屏幕上打印任何內容，也無法從文件中讀取內容。Haskell 設計師面臨的挑戰是想出一種方法，以一種有原則的，受限制的方式允許這種效果，而又不會干擾語言的本質純淨。他們最終確實提出了一些建議（即 IOmonad），我們將在幾週後討論它們
▌Lazy evaluation 惰性評估
現在，我們了解了嚴格的評估，讓我們看看惰性評估的實際效果。在惰性評估策略下，函數參數的評估會 盡可能延遲 ：只有在實際需要時才對它們進行評估。當某些表達式作為函數的參數提供時，它只是打包成未經評估的表達式（稱為“ thunk”，不要問我為什麼），而無需進行任何實際工作
例如，在評估時 f 5 (29^35792)，第二個參數將被簡單地打包成一個 thunk，而不進行任何實際計算，並且 f 將立即被調用。由於 f 從不使用第二個參數，因此垃圾回收器只會丟棄垃圾
▌Pattern matching drives evaluation
模式匹配驅動評估
那麼，什麼時候 ”有必要” 對表達式求值？ 上面的示例集中於一個函數是否使用其參數，但這實際上並不是最重要的區別。 請考慮以下示例：
f1 :: Maybe a -> [Maybe a]
f1 m = [m,m]
f2 :: Maybe a -> [a]
f2 Nothing = []
f2 (Just x) = [x]
f1 和 f2 都使用它們的參數。 但是它們之間仍然有很大的差異。 儘管 f1 使用其參數 m，但它不需要了解任何信息。 m 可以保持完全未評估，並且未評估的表達式只是放在列表中。 換句話說，f1 e 的結果不依賴於 e 的形狀。
f2，另一方面，需要對它的參數有所了解才能繼續：它是用 Nothing 還是 Just 構造？也就是說，為了評估 f2 e ，我們必須首先評估 e ，因為 f2 的結果取決於 e 的形狀
另一個要注意的重要事項是，對 thunk 的評估 僅足以 進行模式匹配，而不能進行進一步的評估！例如，假設我們要評估 f2 (safeHead [3^500, 49]) 。f2 將強制評估對safeHead [3^500, 49]的調用，該調用的評估結果將為 Just (3^500) — 注意的是，3^500沒有 評估，因為 safeHead 並不需要查看它，而且也沒有 f2 。 3^500 是否稍後獲得評估取決於 f2 的結果如何使用
要記住的口號是 “模式匹配驅動評估 (Pattern matching drives evaluation)” 。重申要點：
- 僅當模式匹配時才對表達式求值
- … 僅在進行匹配所需的範圍內，並且沒有更進一步！
讓我們做一個更有趣的示例：我們將進行評估 take 3 (repeat 7)。作為參考，在這裡是定義 repeat 和 take：
repeat :: a -> [a]
repeat x = x : repeat x
take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
逐步進行評估如下所示：
take 3 (repeat 7)
{ 3 <= 0 is False, so we proceed to the second clause, which
needs to match on the second argument. So we must expand
repeat 7 one step. }
= take 3 (7 : repeat 7)
{ the second clause does not match but the third clause
does. Note that (3-1) does not get evaluated yet! }
= 7 : take (3-1) (repeat 7)
{ In order to decide on the first clause, we must test (3-1)
<= 0 which requires evaluating (3-1). }
= 7 : take 2 (repeat 7)
{ 2 <= 0 is False, so we must expand repeat 7 again. }
= 7 : take 2 (7 : repeat 7)
{ The rest is similar. }
= 7 : 7 : take (2-1) (repeat 7)
= 7 : 7 : take 1 (repeat 7)
= 7 : 7 : take 1 (7 : repeat 7)
= 7 : 7 : 7 : take (1-1) (repeat 7)
= 7 : 7 : 7 : take 0 (repeat 7)
= 7 : 7 : 7 : []
（請注意，儘管可以 完全像上面那樣實現求值，但是大多數 Haskell 編譯器會做一些更複雜的事情。特別是，GHC 使用了一種稱為 圖歸約 (graph reduction) 的技術，其中要求值的表達式實際上表示為 圖 ，因此不同表達式的各個部分可以共享指向同一子表達式的指針。這確保了工作不會被不必要地重複。例如，如果 f x = [x,x] ，則運算 f (1+1) 僅做 一個 加法運算，因為子表達式 1+1 將在。的兩次出現之間共享 x
▌Consequences 後果
惰性帶來一些非常有趣，普遍且非顯而易見的後果。讓我們探索其中的一些
▌Purity 純度
正如我們已經看到的，選擇惰性評估策略本質上 迫使 您也選擇了純度（假設您不希望程序員發瘋）
▌Understanding space usage 了解空間使用情況
懶惰並不全是玫瑰 (Laziness is not all roses)。缺點之一是，有時無法合理地推斷出程序的空間使用情況。考慮下面的例子（無害）：
-- Standard library function foldl, provided for reference
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
讓我們考慮一下 foldl (+) 0 [1,2,3] 的評估如何進行 （將列表中的數字相加）：
foldl (+) 0 [1,2,3]
= foldl (+) (0+1) [2,3]
= foldl (+) ((0+1)+2) [3]
= foldl (+) (((0+1)+2)+3) []
= (((0+1)+2)+3)
= ((1+2)+3)
= (3+3)
= 6
因為直到遍歷整個列表才需要累加器的值，因此累加器只建立了一個未評估的大表達式 (((0+1)+2)+3)，最終將其最終減小為一個值。至少有兩個問題。一個就是效率低下：將所有數字從列表轉移到另一個類似列表的東西（累加器）之前沒有意義。 第二個問題更加微妙，更隱蔽：計算表達式 (((0+1)+2)+3) 實際上需要將 3 和 2 推入堆棧，然後才能計算 0+1 然後展開堆棧 ，一路添加。 對於這個小例子來說，這不是問題，但是對於很長的列表來說，這是個大問題：通常堆棧沒有足夠的可用空間，因此這可能導致堆棧溢出
在這種情況下，解決方案是使用 foldl' 函數而不是 foldl，這增加了一點嚴格性：特別是，在執行 foldl' 該函數之前，需要對其第二個參數（累加器）進行求值，因此不會產生大量的重擊：
foldl' (+) 0 [1,2,3]
= foldl' (+) (0+1) [2,3]
= foldl' (+) 1 [2,3]
= foldl' (+) (1+2) [3]
= foldl' (+) 3 [3]
= foldl' (+) (3+3) []
= foldl' (+) 6 []
= 6
如您所見，foldl' 一直在進行添加，這是我們真正想要的。 但是關鍵是在這種情況下，惰性成為了障礙，我們不得不減少程序的惰性
（如果您想了解 foldl 如何實現此目的，可以在 Haskell Wiki 上閱讀有關 seq 的信息。）
▌Short-circuiting operators 短路運算子
在某些語言（Java，C++）中，布爾運算符 && 和 || （邏輯 AND 和 OR）是 短路的 (Short-circuiting)：例如，如果 && 的第一個參數的計算結果為 false，則整個表達式將立即計算為 false，而無需計算第二個參數。 但是，作為特殊情況，必須將此行為關聯到 Java 和 C++ 語言標準中。 通常，在嚴格的語言中，在調用函數之前會先評估兩個參數的函數的兩個參數。 因此 && 和 || 的短路行為 是該語言通常嚴格的語義的特殊例外
但是，在 Haskell 中，我們可以定義短路運算符而沒有任何特殊情況。事實上，(&&) 和 (||) 只是計劃中的舊庫函數！例如，以下是 (&&) 的定義方式：
(&&) :: Bool -> Bool -> Bool
True && x = x
False && _ = False
請注意 (&&) 的定義如何在第二個參數上不進行模式匹配。 此外，如果第一個參數為 False，則第二個參數將被完全忽略。 由於 (&&) 根本不對第二個參數進行模式匹配，因此它的短路方式與 Java 或 C++ 中的 && 運算符完全相同
注意，(&&) 也可以這樣定義：
(&&!) :: Bool -> Bool -> Bool // 請注意 (&&!) 是我們定義的一個新的運算符，這個不是 &&(!(...))
True &&! True = True
True &&! False = False
False &&! True = False
False &&! False = False
儘管此版本採用與相同的值 (&&)，但它具有不同的行為。例如，考慮以下內容：
False && (34^9784346 > 34987345)
False &&! (34^9784346 > 34987345)
這些都將計算為 False，但是第二個將花費更長的時間！還是這樣：
False && (head [] == 'x')
False &&! (head [] == 'x')
第一個是 False，而第二個將崩潰。試試吧！
所有這些都指出，在定義函數時，圍繞惰性存在一些有趣的問題
▌User-defined control structures 用戶定義的控制結構
將短路運算子的想法再進一步一步，在 Haskell 中，我們可以定義自己的控制結構
大多數語言都有某種特殊的內置 if 構造。 一些想法揭示了原因：以類似於短路布爾運算符的方式，如果具有特殊行為。 根據測試的值，它僅執行/評估兩個分支之一。 如果每次都對兩個分支都進行評估，那將破壞整個目標！
但是，在 Haskell 中，我們可以定義 if 為庫函數！
if' :: Bool -> a -> a -> a
if' True x _ = x
if' False _ y = y
當然，Haskell 確實 具有特殊的內置 if 表達式，但是我從未完全理解為什麼。也許僅僅是因為語言設計師認為人們會期望它。“你是什麼意思，這種語言沒有 if！！” 無論如何， if 無論如何在 Haskell 中不會使用太多。在大多數情況下，我們更喜歡模式匹配或後衛 (guards)
我們還可以定義其他控制結構 — 討論 monad 時將看到其他示例
▌Infinite data structures 無限數據結構
惰性評估還意味著我們可以使用 無限的數據結構 。實際上，我們已經看到了一些示例，例如 repeat 7，它表示一個無限列表，其中僅包含 7。定義一個無限的數據結構實際上只會創建一個 thunk，我們可以將其視為“種子” ，根據實際使用/需要的部分，整個數據結構 可能 會從中增長
另一個實際的應用領域是“有效無限”的數據結構，例如可能作為遊戲狀態空間（例如圍棋或國際象棋）出現的樹。儘管樹在理論上是有限的，但它是如此之大以至於實際上是無限的 —— 它肯定不適合存儲在內存中。使用Haskell，我們可以定義所有可能動作的樹，然後編寫單獨的算法以所需的任何方式探索樹。僅計算實際探索的樹的部分
▌Pipelining/wholemeal programming 流水線/全餐編程
如前所述，對大型數據結構進行 “流水線式” 增量轉換實際上可以提高內存效率。現在我們可以看到原因：由於惰性，流水線的每個階段都可以按步進行操作，僅生成結果的每一位，這是流水線的下一階段所需要的
▌Dynamic programming 動態編程
惰性評估為我們提供了一個很酷的事物的更具體的例子，請考慮 動態編程 技術。通常情況下，人們必須非常謹慎地填寫正確的順序動態規劃表的條目，讓我們每次計算一個單元格的值，它的依賴已經被計算。 如果我們得到的順序不對，我們得到虛假的結果
但是，使用惰性評估，我們可以獲得 Haskell 運行時為我們確定正確的評估順序！例如，下面是一些Haskell代碼來解決 0-1背包問題 。注意，我們如何使用標準遞歸簡單地根據數組本身定義數組 m，並讓惰性計算得出計算其單元格的正確順序
import Data.Array
knapsack01 :: [Double] -- values
-> [Integer] -- nonnegative weights
-> Integer -- knapsack size
-> Double -- max possible value
knapsack01 vs ws maxW = m!(numItems-1, maxW)
where numItems = length vs
m = array ((-1,0), (numItems-1, maxW)) $
[((-1,w), 0) | w <- [0 .. maxW]] ++
[((i,0), 0) | i <- [0 .. numItems-1]] ++
[((i,w), best)
| i <- [0 .. numItems-1]
, w <- [1 .. maxW]
, let best
| ws!!i > w = m!(i-1, w)
| otherwise = max (m!(i-1, w))
(m!(i-1, w - ws!!i) + vs!!i)
]
example = knapsack01 [3,4,5,8,10] [2,3,4,5,9] 20
