Haskell中的惰性求值如何實現？

12-27

有很多程序語言都實現了惰性求值，比如最典型的Haskell。通過惰性求值可以簡化很多運算，但是我有一個步明白的地方，惰性求值在編譯器中是如何實現的，難道維護了一個表之類的東西來記錄哪些被計算過？每次查找這樣一個表會不會降低性能？

補充：這個問題緣起於我查看了這篇博客談惰性求值，裡面有一段話提到：
～～～～
這種不確定性，並沒有帶來總體計算開銷的增加。然而「惰性」卻在另外一方面帶來了巨大的開銷，這就是「問問題」的開銷。每當看到一個變數，Haskell
都會問它一個問題：「你被求值了沒有？」即使這變數已經被求值，而且已經被取值一百萬次，Haskell
仍然會問這個問題：「你被求值了沒有？」問一個變數這問題可能不要緊，可是 Haskell
會問幾乎所有的變數這個問題，反覆的問這個問題。這就累積成了巨大的開銷。跟我在另一篇博文里談到的「解釋開銷」差不多，這種問題是「運行時」的，所以沒
法被編譯器「優化」掉。
～～～～
誠然，如果表達式在源代碼里顯示的出現時，編譯器可以知道應該保存哪些已經計算過的變數。如果表達式沒有顯示出現呢？比如下面這個計算階乘的函數：
import System.Environment
fac 0 = 1 fac n = n * fac (n-1)
seq" from to = [fac i| i &<- [from..to]] main = print (seq" 9 10)
姑且不論這個實現的效率，在seq"中執行fac 10的時候，是否知道fac 9已經計算過？fac 9 這樣的表達式是否被放入某種表中。如果計算過，是否意味著系統還會保存fac 0 到fac 8 這樣的表達式？然而fac 1， fac 2，fac 3 等有可能根本不會再被用到。假如我第一次計算了一個很大的數的階乘，是否比這個數小的那些階乘都被保存下來？

GHC中的惰性求值是如何實現的

Haskell語言只要求惰性求值，並不考慮怎麼實現。就比如Haskell語言對編譯器們說你們可以提供個C++的FFI，但完全沒規定怎麼實現，結果也沒有任何編譯器實現了這個功能。所以假設問題是」GHC中的惰性求值是如何實現的「。

要一窺GHC是如何實現惰性求值的，這有個再合適不過的工具：ghc-heap-view: Extract the heap representation of Haskell values and thunks。其中的Demo.hs提供了幾個了解惰性求值實現非常好的例子：

Here are a four different lists, where the first three are already evaluated. The first one, l, was defined as a top level constant as &> l = [1,2,3] and is now found at 0xaf305d90 (where the /2 is the pointer tag information) and fully evaluated: &> ConsClosure {info = StgInfoTable {ptrs = 2, nptrs = 0, tipe = CONSTR_2_0, srtlen = 1}, ptrArgs = [0xb2efaff4,0xaf2d4248], dataArgs = [], pkg = "ghc-prim", modl = "GHC.Types", name = ":"} The second one, l2, is locally defined &> let l2 = 4:l and now found at 0xaf305870. See how the cons-cell references l! &> ConsClosure {info = StgInfoTable {ptrs = 2, nptrs = 0, tipe = CONSTR_2_0, srtlen = 1}, ptrArgs = [0xb2efb00c,0xaf305d90], dataArgs = [], pkg = "ghc-prim", modl = "GHC.Types", name = ":"} And the binding &> args &<- map length `fmap` getArgs gives us at 0xb2f6920c/1 a static, but at compile time unknown list: &> ConsClosure {info = StgInfoTable {ptrs = 0, nptrs = 0, tipe = CONSTR_NOCAF_STATIC, srtlen = 0}, ptrArgs = [], dataArgs = [], pkg = "ghc-prim", modl = "GHC.Types", name = "[]"} And now we have, at 0xaf305858, the concatenation of them, but unevaluated: &> let x = l ++ l2 ++ args The thunk keeps a reference to l2 and args, but not l, as that is at a static address, unless you are running this in GHCi: &> APClosure {info = StgInfoTable {ptrs = 0, nptrs = 0, tipe = AP, srtlen = 0}, arity = 21669, n_args = 2, fun = 0xaf305d74, payload = [0xaf305870,0xb2f6920c/1]}


Now to some more closure types. m and m" locally bound of type the unboxed type Int#, with values 42 resp. 23.

&> let f = x n -&> take (I# m + I# x) n ++ args

&>     t = f m" l2

So here is (0xafd3be14), referencing its free variables args and 42:

&> APClosure {info = StgInfoTable {ptrs = 0, nptrs = 0, tipe = AP, srtlen = 0}, arity = 57205, n_args = 2, fun = 0xaeff8360, payload = [0xb2f6920c/1]}

And t is a thunk that applies f (also referenced here) to an unboxed value (23) and l2:

&> APClosure {info = StgInfoTable {ptrs = 0, nptrs = 0, tipe = AP, srtlen = 0}, arity = 58149, n_args = 3, fun = 0xaeff837c, payload = [0xafd3be14,0xaf305870]}

Lastly, here is the standard example for self reference: &> let x = id (:) () x This is what x (0xb05d0108) looks like, at least without -O: &> APClosure {info = StgInfoTable {ptrs = 0, nptrs = 0, tipe = AP, srtlen = 0}, arity = 216, n_args = 1, fun = 0xaeff7084, payload = [0xb05d0108]} So it is unevaluated. Let us evaluate it using seq. Now we have, still at 0xb05d0108: &> BlackholeClosure {info = StgInfoTable {ptrs = 1, nptrs = 0, tipe = BLACKHOLE, srtlen = 0}, indirectee = 0xb0417d20/2} The thunk was replaced by an indirection. If we look at the target, 0xb0417d20/2, we see that it is a newly created cons-cell referencing the original location of x: &> ConsClosure {info = StgInfoTable {ptrs = 2, nptrs = 0, tipe = CONSTR_2_0, srtlen = 1}, ptrArgs = [0xb2f690f4,0xb05d0108], dataArgs = [], pkg = "ghc-prim", modl = "GHC.Types", name = ":"} After running the garbage collector (performGC), we find that the address of x is now 0xb0056094/2 and that the self-reference is without indirections: &> ConsClosure {info = StgInfoTable {ptrs = 2, nptrs = 0, tipe = CONSTR_2_0, srtlen = 1}, ptrArgs = [0xb2f690f4,0xb0056094/2], dataArgs = [], pkg = "ghc-prim", modl = "GHC.Types", name = ":"}

我們可以在ghci中玩玩ghc-heap-view：

&> let x = map show [(0::Int) ..] &> :printHeap x &> let f1 = _fun &> in (_bco (_bco (D:Enum _fun _fun f1 f1 _fun _fun _fun _fun) _fun) (_bco (D:Show _fun _fun _fun) _fun) _fun)() 惰性求值，_bco指的是bytecode object。這裡 * (_bco (D:Enum _fun _fun f1 f1 _fun _fun _fun _fun) _fun)應該是class Enum中的enumFrom * (_bco (D:Show _fun _fun _fun) _fun)應該是class Show中的show 可以看出GHC在實現中其實是將instance作為一個record of functions的隱含參數的，不過這與這個問題無關。


&> head x

&> "0"

&> :printHeap x

&> _bh (_bh "0" : _thunk (_bh _fun) (_thunk _fun{2147483647} 2147483647 0))

_bh指的是BLACKHOLE，暫時先不管它。這裡

 * (_bh _fun)應該是instace Show Int中的show

 * (_thunk _fun{2147483647} 2147483647 0)本應該是instance Enum Int中的enumFrom，不過從這個熟悉的2147483647可以猜測到enumFrom n = enumFromTo n maxBound

這時x已經被求值到了WHNF，而show和enumFrom本身也被求值了。
&> x!!3

&> "3"

&> :printHeap x

&> let x1 = []

&>     f1 = _fun

&> in (C# "0" : x1) : _bh (_thunk f1 (I# 1) : _bh (_thunk f1 (I# 2) : _bh (_bh (C# "3" : x1) : _thunk f1 (_thunk _fun{2147483647} 2147483647 3))))

這裡f1就是show，值得注意的是，雖然List前4項被展開了，但show 1和show 2本身並沒有被求值！

&> System.Mem.performGC &> :printHeap x &> let x1 = [] &> f1 = _fun &> in (C# "0" : x1) : _thunk f1 (I# 1) : _thunk f1 (I# 2) : (C# "3" : x1) : _thunk f1 (_thunk _fun{2147483647} 2147483647 3) performGC消滅BLACKHOLE。BLACKHOLE是為了兼顧多線程和效率而存在的黑魔法。所以GHC的惰性求值並不是非黑即白的，中間還有個灰的狀態，即是BLACKHOLE。

想要詳細了解可以參考Commentary/Rts/Storage/HeapObjects

補充一：惰性求值的overhead與GHC的優化

這種問題是「運行時」的，所以沒法被編譯器「優化」掉。

這顯然是錯誤的。GHC會推斷出哪些檢查是完全沒有必要的，從而把他們優化掉，而且GHC喪心病狂的inline可以發現更多這樣不必要的檢查。這個可以通過ghc -ddump-simpl來得到驗證：
下面這段求積分的代碼：

module Test (gao) where gao :: Double -&> Double -&> Double gao a x = let b = sqrt $ x * x + a * a in 0.5 * (x * b + a * a * log (x + b))

如果不開優化，得到的是：

Test.gao :: GHC.Types.Double -&> GHC.Types.Double -&> GHC.Types.Double [GblId, Arity=2, Str=DmdType] Test.gao = (a_apE :: GHC.Types.Double) (x_apF :: GHC.Types.Double) -&> let { b_apG :: GHC.Types.Double [LclId, Str=DmdType] b_apG = GHC.Float.sqrt @ GHC.Types.Double GHC.Float.$fFloatingDouble (GHC.Num.+ @ GHC.Types.Double GHC.Float.$fNumDouble (GHC.Num.* @ GHC.Types.Double GHC.Float.$fNumDouble x_apF x_apF) (GHC.Num.* @ GHC.Types.Double GHC.Float.$fNumDouble a_apE a_apE)) } in GHC.Num.* @ GHC.Types.Double GHC.Float.$fNumDouble (GHC.Types.D# 0.5) (GHC.Num.+ @ GHC.Types.Double GHC.Float.$fNumDouble (GHC.Num.* @ GHC.Types.Double GHC.Float.$fNumDouble x_apF b_apG) (GHC.Num.* @ GHC.Types.Double GHC.Float.$fNumDouble (GHC.Num.* @ GHC.Types.Double GHC.Float.$fNumDouble a_apE a_apE) (GHC.Float.log @ GHC.Types.Double GHC.Float.$fFloatingDouble (GHC.Num.+ @ GHC.Types.Double GHC.Float.$fNumDouble x_apF b_apG))))

打開-O優化後，得到的是：

Test.gao = (a_arV :: GHC.Types.Double) (x_arW :: GHC.Types.Double) -&> case x_arW of _ [Occ=Dead] { GHC.Types.D# x1_XPe -&> case a_arV of _ [Occ=Dead] { GHC.Types.D# x2_XPj -&> let { y_aP8 :: GHC.Prim.Double# [LclId, Str=DmdType] y_aP8 = GHC.Prim.sqrtDouble# (GHC.Prim.+## (GHC.Prim.*## x1_XPe x1_XPe) (GHC.Prim.*## x2_XPj x2_XPj)) } in case GHC.Prim.logDouble# (GHC.Prim.+## x1_XPe y_aP8) of wild2_aPC { __DEFAULT -&> GHC.Types.D# (GHC.Prim.*## 0.5 (GHC.Prim.+## (GHC.Prim.*## x1_XPe y_aP8) (GHC.Prim.*## (GHC.Prim.*## x2_XPj x2_XPj) wild2_aPC))) } } }

啥區別？乘法由前面的GHC.Num.* @ GHC.Types.Double GHC.Float.$fNumDouble變成了GHC.Prim.*##，而類型由Double變成了Double#。這個Double#是Unboxed type，就是個雙精度浮點數，所以實際編譯得到的代碼就是一條彙編指令。

Unboxed type這個概念C#和Java里也有，雖然不完全一樣，有時候我們說這是為了性能做出的妥協。在Haskell代碼中直接使用Unboxed type的情況極少，通常是為了直接調用GHC.Prim中一些類型為Int#之類的奇葩函數。再說一遍，這種情況真的少之又少，通常都交給編譯器去做這個優化。

另一方面，Haskell求值順序的不確定性確實又會給編譯器的優化帶來不小的挑戰。所以Haskell有時候確實要放棄一些lazyness，引入一些strictness，常用的有：

seq：破壞Haskell和諧的源頭，也是對RealWorld做的妥協
BangPatterns：其實就是更優雅的寫seq，這樣就引入的順序，使得編譯器能做更多的推斷。在函數內也就不再需要檢查這些參數了
strict fields和UNPACK：datatype里的BangPatterns
使用帶有strictness的函數，比如foldl"
使用Unboxed的容器，比如Data.Array.Unboxed、Data.Vector.Unboxed
使用自帶strictness的module，比如Data.Map.Strict，Data.HashMap.Strict
Control.DeepSeq：這個太喪失了……一般都是benchmark的時候才用。說到benchmark，Haskell的惰性求值帶來最大的坑絕對不是所謂的重複檢查，恐怕也不是space leak，而是benchmark！

其實更多的時候，我們擔心的更多是space leak和增加GC的負擔，而不是重複檢查。

還有千萬不要看完這個就喪心病狂的往代碼里一股腦兒的加這些東西，你的代碼十有八九不會變快，但一定會變醜，丑得嫁不出去……何況

Premature optimization is the root of all evil.

HaskellWiki相關條目：Performance/Strictness

補充二：惰性求值和記憶化
@邵成已經點出了這一點。Haskell是不會記得你曾求過fac 9的值的。

很多語言或其中的庫都提供了對惰性求值的支持，但需要程序員去顯示的使用他們。而Haskell默認的惰性求值即便帶來一些額外開銷，但不是大問題，而且也有有利的一面。

同樣很多語言或其中的庫都提供了對簡單的記憶化的支持：比如python3中的@lru_cache。Haskell也有基於TempleteHaskell的memoize: A memoization library和記憶化Monadmonad-memo: Memoization monad transformer等hackage。記憶化運用不當很可能適得其反，不但在時間上，更可怕的是內存上……所以，還沒發現有哪個通用編程語言是默認記憶化的，在我看來也不會有，DSL倒是有。

有幾個抽象機器專門用於實現惰性語言的graph reduction，以G-machine為代表。
讀一下Implementing Functional Languages: A Tutorial就知道怎樣實現了。

======

另外題主和若干個答主把兩個概念搞混淆了：惰性求值（lazy evaluation）和記憶化（memoization）。

fib :: Int -&> Integer fib 0 = 0 fib 1 = 1 fib n = (fib (n-1))+(fib (n-2))

比如上面求fibonacci的代碼，不管用什麼策略求值，時間複雜度都是O(2^n)。但是如果在實現語言的編譯器/解釋器時，任何一次函數調用都存表/查表來緩存的話，可以在上層代碼不變的情況下自動降時間複雜度為O(n)。但是這叫做記憶化，不是惰性求值，而且Haskell的編譯器ghc沒有實現這個機制。Haskell是需要手寫記憶化的邏輯的，一個小例子：https://gist.github.com/TerrorJack/1fc8f0eb8a8a45f78f14

惰性求值則是一種求值策略：

節選自《Programming in Haskell》。為什麼編譯器不做記憶化優化，主要原因是用得到的場合太少，開銷太大。

這週把惰性求值實現了一遍，終於覺得有自信回答這個問題了。我在這裡的解釋會比較簡略，不過推薦來讀我翻譯的文章《Haskell 怎麼實現惰性求值》（原文），和實現了惰性求值的 Loli 語言。

首先，Loli 類似 Haskell 惰性求值的實現主要在兩方面：第一，動態閉包的傳參方式實現 non-strict 的語意；第二，用自訂類型支持方便的 streaming，為了接近 Haskell，我在 Loli 中用的是 ADT 的支持。

動態閉包（dynamic closure）的傳參方式就是說，求值器在求值一個 function application 的時候不會對其參數求值，而是會封到一個動態閉包裡。動態閉包其實就是一個帶 binding 的表達式，動態閉包有很多名字，有的叫之 thunk，也有些地方稱之為 redex，不過就我的理解動態閉包不能和 redex 畫上等號，因為在我的實現裡 redex 還包括其他一些表達式類型。所有的值只有在用到的時候才會被規約到模範型（normal form）。做到這點並不會很難，scheme 的 delay 和 force 函數就可以用來實現簡單的手動惰性求值功能。

其實第二個的要點在於支持弱首模範式（weak-head normal form），來實現自訂數據類型值的 non-strict 語意。也就是說，數據類型構造子（data type constructor）的參數也像函數參數一樣被封入動態閉包裡，即使這個數據類型值被要求強行規約也不會對其構造子參數進行規約。

唉，我不太擅長用人類語言描述這個過程，其實 Loli 核心的惰性求值代碼不過是下面一段，不介意的話直接讀 Racket 代碼吧：

(define (eval-preliminary force?) (λ (expr env) (cond [(normal? expr) expr] [(redex? expr) (if force? (reduce expr env) expr)] [(appl? expr) (let ([ecar (eval-force (cadr expr) env)]) (define (reduce-opt val) (if force? (reduce val env) val)) (cond [(λ? ecar) (reduce-opt (eval-lambda ecar (make-closure env (caddr expr))))] [(proc? ecar) (reduce-opt (eval-proc ecar (make-closure env (caddr expr))))] [else (error "unknown expression")]))])))


(define eval       (eval-preliminary #f))

(define eval-force (eval-preliminary #t))

(define (reduce expr env) (let ([result (cond [(ref? expr) (follow-ref-force (cadr expr) env)] [(λraw? expr) (make-lambda expr env)] [(closure? expr) (resolve-closure expr)] [(normal? expr) expr] [else (error "neither redex nor normal!")])]) (if (redex? result) (reduce result env) result)))

不一定要用一個外部的表來維護呀--value本身就可以攜帶這個信息。

強烈推薦SPJ的 Implementing functional languages: a tutorial，介紹了不少實現的方法。當然還有Spineless tagless g-machine的幾篇。

通過將表達式包裝成一個thunk實現的
例如計算f (g x)，實際上給f傳遞的參數就是一個類似於包裝成(\_ -&> (g x))的一個thunk
然後在真正需要計算g x的時候才會調用這個thunk
事實上這個thunk裡面還包含一個boolean表示該thunk是否已經被計算過（若已經被計算過，則還包含一個返回值），用來防止重複計算

GHC RTS 確實內部維護了很多表……

只要能將「計算」這個行為保存成數據，然後在取數據的時候再觸發計算的行為，就能實現惰性求值啦，流啦。
C++裡面的 expression template 也是類似的思想。

嗯，一樓說的很對，就是一個thunk，第一個是bool，第二個是表達式，false時候表明還未求值，true代表已經被求值。具體可以看這部分，很容易看懂

https://courses.cs.washington.edu/courses/cse341/13wi/videos/unit5/95_thunks.mp4

可以學習一下 sicp 的流式計算那章，講了惰性求值的原理。

如何實踐？那就給你用python實踐一個lazy的fac。（並不是strict 的lazy，但是idea在這裡）
不返回值，而返回一個當空call的時候才會計算的函數。這就是惰性求值。
這裡沒有做memo，不過要做也很簡單，有人感興趣的話我可以把我sml寫的generic memoizer改成python的。

def lazymult(a,b): return lambda: a*b


def lazyfac (n):

    if n == 0:

        return (lambda : 1)

    else:

        return lambda: lazymult(n, (lazyfac(n-1))())()

a=lazyfac(5) print a print a()

output:

& at 0x10ccc0398&> 120

http://streamjs.org/stream/stream.js
先把上面的源碼閱讀一下，非常短，不會花費多少時間的。
這段代碼的作用：stream.js — streams in javascript

如果還有時間的話，把 SICP的第 3.5節看一下。只要看這一節，也不會花費多少時間。

如果題主至少做了上面兩件事中的一件，會得到答案的。

sicp 4.2節就是實現惰性求值和記憶化

大家回答都很好
我來抖個激靈

看大概90年的一篇巨硬的Spinless Tag Machine的論文，這是GHC的實現

題主是想問實現細節？否則各位是不是有點答偏了。。。

Lazy evaluation和eager evaluation只是lambda表達式做規約時候的策略不同，lazy的時候是leftmost outermost，eager的時候是leftmost innermost。Haskell在desugar之後其實就是簡單的lambda表達式，這個本身也不太語言相關，也沒啥Trick在裡頭。

有興趣推薦看看spj1987：The Implementation of Functional Programming Languages