<p>Lazy Evaluation 是Haskell进程的求值方式。当把一个表达式与一个变量绑定时，这个表达式并没有被立即求值，而是当它的结果需要被其他的计算用到时才会求值。因此，在调用函数时，参数也不会在调用前求值，
而是当它的值被用到是才会求值。Technically, lazy evaluation means call-by-name plus Sharing.
Lazy 的实现
Thunks are primarily used to represent an additional calculation that a subroutine needs to execute, or to call a routine that does not support the usual calling mechanism.
Haksell 的惰性求值正是通过将表达式包装成一个thunk实现的。例如计算 f (g x)，实际上给f传递的参数就是一个类似于包装成 (_ > (g x)) 的一个 thunk 然后在真正需要计算 g x
的时候才会调用这个thunk。这个thunk里面还包含一个boolean表示该thunk是否已经被计算过（若已经被计算过，则还包含一个返回值），用来防止重复计算。
接下来，我们使用Haskell的 ghc-heap-view 工具来举例说明 Haskell 的惰性求值是如何运作的。
Prelude> let x = map show [(0::Int) ..]
Prelude> :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的隐含参数的。
Prelude> head x
"0"
Prelude> :printHeap x
_bh ("0" : _thunk _fun (_thunk _fun{9223372036854775807} 9223372036854775807 0))
_bh 指的是BLACKHOLE。这里
(_bh _fun)应该是instace Show Int中的show(_thunk _fun{9223372036854775807} 9223372036854775807 0)本应该是instance Enum Int中的enumFrom，不过从这个数值 9223372036854775807 可以猜测到enumFrom n = enumFromTo n maxBound
这时x已经被求值到了，而show和enumFrom本身也被求值了。
Prelude> x !! 3
"3"
Prelude> :printHeap x
let x1 = []
f1 = _fun
in _bh ((C# '0' : x1) : _bh (_thunk f1 (I# 1) : _thunk f1 (I# 2) : (C# '3' : x1)
: _thunk f1 (_thunk _fun{9223372036854775807} 9223372036854775807 3)))
这里f1就是show。虽然List前4项被展开了，但show 1和show 2本身并没有被求值！
Prelude> System.Mem.performGC
Prelude> :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{9223372036854775807} 9223372036854775807 3)
Prelude>
performGC消灭BLACKHOLE。BLACKHOLE是为了兼顾多线程和效率而存在。Black Hole 的详细定义和解释:
The concurrent runtime system uses black holes as synchronisation points for subexpressions which are shared among multiple threads. In “sequential Haskell”, a black hole indicates a cyclic data dependency, which is a fatal error. However, in concurrent execution, a black hole may simply indicate that the desired expression is being evaluated by another thread. Therefore, when a thread encounters a black hole, it simply blocks and waits for the black hole to be updated.
lazy graph reduction
Graph reduction, 是惰性求值的实现方式，Spineless Tarless G-Machine 和 G-Machine 之类的抽象机器可以专门用于实现惰性求值语言中的 Graph reduction。
关于 Lazy Evaluation 的时间和空间消耗，惰性求值不会需要比贪婪求值更多的求值步骤，因此，二者的时间复杂度不会有本质上的差异，Haskell 中，用于判断一个 object 的值是否已经求出的重复的检查，但是，Lazy Evaluation 的空间消耗值得关注。
例如这段代码的求值过程：
foldl (+) 0 [1..100]
=> foldl (+) 0 (1:[2..100])
=> foldl (+) (0 + 1) [2..100]
=> foldl (+) (0 + 1) (2:[3..100])
=> foldl (+) ((0 + 1) + 2) [3..100]
=> foldl (+) ((0 + 1) + 2) (3:[4..100])
=> foldl (+) (((0 + 1) + 2) + 3) [4..100]
=> ...
在求值的过程中，累积参数占用的空间会越来越大，这个问题称为 space leak, space leak 会增加GC的负担，而不是重复检查。
Strictness
Haskell求值顺序的不确定性确实又会给编译器的优化带来不小的挑战。所以Haskell有时候确实要放弃一些lazyness，引入一些strictness，例如:
- seq：是对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
- unsafe[Dupable]PerformIO
使用GHC来编译Haskell代码时，打开某些编译选项也可以是的使用lazy evaluation的代码采用某些strict的数据类型，以提升进程的运行效率。
Lazy 实现示例
了解了 thunk 的原理，我们可以使用既非函数式的、不支持 first-class function 的编程语言来实现 Lazy Evaluation。
#include <stdlib.h>
typedef struct {
void *val; // store result when evaluated.
int evaluated;
void *(*thunk)(void *); // deferred computation.
void *args; // args to pass to deferred computation.
} lazy;
// create lazy evaluated thunk.
lazy make_lazy(void (thunk)(void ), void args) {
lazy l = malloc(sizoof(lazy));
l->val = NULL;
l->evaluated = 0;
l->thunk = thunk;
l->args = args;
return l;
}
// force evaluation of the thunk.
void force(lazy l) {
if(!l->evaluated) {
l->val = l->thunk(l->args)
l->evaluated = 1;
}
return l->val;
}