OCaml 如何在运行时表示惰性值？

Question

Real World OCaml中的这个chapter描述了不同数据类型的运行时内存布局。但是没有讨论lazy值。

lazy_t是如何实现的，即它的运行时表示是什么以及编译器内置的关键操作是什么？链接到源代码将不胜感激。我查看了 CamlinternalLazy 模块，但仅根据对 Obj 模块中的函数的调用，实际的表示似乎很难破译。
有人可以提供对 representation/operations 所做的更改的摘要，以使其对 OCaml 多核项目线程安全吗？这个commit貌似是有实现的，但对我这个外行人来说似乎有点不透明

注意：这个问题是关于 OCaml compiler/runtime的。我知道 an OCaml compiler/runtime.

应该如何实现惰性值没有标准规范

Answer 1

简而言之，需要计算的惰性值表示为一个 thunk，一旦该值是被迫。不需要计算（并且不是浮点数）的惰性值按原样表示。

首先，让我们关注不需要计算的值。这些是常量、函数（不是它们的应用程序，也不是部分应用程序）或标识符。它们的表示没有任何额外的装箱，并且与热切的对应物具有相同的表示，例如，

# Obj.repr (lazy 42) == Obj.repr 42;;
- : bool = true

# Obj.tag (Obj.repr sin) = (Obj.tag (Obj.repr (lazy sin)));;
- : bool = true

# Obj.closure_tag = (Obj.tag (Obj.repr (lazy sin)));;
- : bool = true

通常具有盒装表示的类型也是如此，例如字符串，

let s = "hello" in
Obj.repr s == Obj.repr (lazy s);;
- : bool = true

唯一的例外是 float 类型（因为另一个优化允许数组或浮点数记录的未装箱存储，否则会被破坏）。浮点数以 forwarded 表示法存储，作为带 header 表示 Forward_tag 且唯一字段是存储值的装箱值。

分类为计算的值存储为 thunk。如果我们讲 OCaml（注意，那不是实际的实现，但概念是一样的）

type 'a value = Deferred of (unit -> 'a) | Ready of 'a 
type 'a lazy_t = {
  mutable lazy : 'a value;
}

和 lazy 运算符捕获封闭的表达式，即在语言的语法级别上，它翻译如下：

lazy x => {lazy = Deferred (fun () -> x)

以下是与 OCaml 的一些交互，展示了表示形式：

let x = lazy (2+2) in
Obj.lazy_tag = Obj.tag (Obj.repr x);;
- : bool = true

let x = lazy (2+2) in
let _ = Lazy.force x in
Obj.forward_tag = Obj.tag (Obj.repr x);;
- : bool = true

正如我们所见，计算存储为 thunk（并使用 4 个字）

let x = lazy (2+2) in
Obj.reachable_words (Obj.repr x);;
  - : int = 4

而在我们强制计算之后，它将被存储为转发（装箱）int，

let x = lazy (2+2) in
let _ = Lazy.force x in
Obj.reachable_words (Obj.repr x);;
- : int = 2

^†) 异常也有一种特殊情况，即计算发散，因此没有值，因此无法转换为转发形式。结果，异常即使在被强制之后仍然是惰性值，例如，

let x = lazy (raise Not_found) in 
Obj.lazy_tag = Obj.tag (Obj.repr x);;
- : bool = true

let x = lazy (raise Not_found) in 
try Lazy.force x with Not_found -> 
Obj.lazy_tag = Obj.tag (Obj.repr x)

在实现方面，引发异常的计算由引发此异常的函数代替。所以仍然有一些记忆发生，换句话说，如果你有 lazy (x (); y (); z ()) 并且 y () 引发异常 E，那么惰性值有效负载将被函数 fun () -> raise E，即它永远不会重复 x ()，也永远不会到达 z ()。

多核中的惰性值

惰性是可变性的一种受限形式，与任何其他可变性一样，当并行计算发挥作用时，它会使事情复杂化。

在 OCaml 实现中，惰性值不仅会随时间改变它们的值，还会改变类型和表示形式。 OCaml 中值的表示由 header 决定。出于性能原因，OCaml 多核团队决定禁止对 header 进行任何更改，因此值不能再更改其表示（否则，如果允许更改 header，则每次访问 header 字段需要昂贵的同步）。

此问题的解决方案引入了一个新的间接级别，其中惰性值的状态存储在其有效负载中（这实际上使新的惰性表示更接近我们的概念视图）。

在我们深入研究实现之前，还有一件事需要解释一下 OCaml 中的惰性值。当强制使用惰性值时，它不会立即更新为计算结果，因为计算本身可以递归并引用惰性值。这就是为什么在调用附加到惰性值的计算之前的第一步，惰性函数的有效负载被引发 Lazy.Undefined 异常的函数替换，因此 not well-formed 递归表达式仍然终止很好。

这个技巧被多核团队劫持并重用，以在多个线程试图同时强制执行惰性值的情况下确保惰性值安全。当一个惰性值被强制时，他们用一个名为 bomb 的函数替换它的有效负载，该函数检查在评估期间是否再次引用惰性值（因为计算递归，或者因为它与另一个线程共享），并且如果引用来自同一个域，那么它会触发 Undefined 异常，表明这不是一个 well-formed 惰性值，或者如果域不同，那么它会引发 RacyLazy 异常, 这表明存在对来自不同域的相同惰性值的非序列化访问。

这里的关键时刻是要理解，由于惰性是一个可变值，因此正确序列化对其访问仍然是用户的责任。如何正确有效地做到这一点仍然在未来的工作部分。

实施参考

这是

OCaml 如何在运行时表示惰性值？

How does OCaml represent lazy values at runtime?

ocaml

lazy-evaluation

memory-layout

data-representation

多核中的惰性值

实施参考