Lazy Evaluation 的原理与实现

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.

Cyclic data dependencies will result in deadlock, and the program will fail to terminate.

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;
}

Lazy Evaluation 的原理与实现

Lazy 的实现

lazy graph reduction

Strictness

Lazy 实现示例

参考

Comments: