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

Question

此 chapter在现实世界中，OCaml 描述了不同数据类型的运行时内存布局。但是，没有讨论惰性值。

怎么样lazy_t已实现，即它的运行时表示是什么以及编译器内置的关键操作是什么？源代码的链接将不胜感激。我看了CamlinternalLazy模块，但仅基于对 Obj 中的函数的调用，实际表示似乎很难破译。那里的模块。

有人可以提供对表示/操作所做更改的摘要，以使其对 OCaml 多核项目线程安全吗？此 commit似乎是实现的那个，但作为局外人，这对我来说似乎有点不透明。

注意:这个问题是关于 OCaml 编译器/运行时的。我知道对于 OCaml 编译器/运行时应该如何实现惰性值没有标准规范。

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

唯一的异常(exception)是 float类型(因为另一种优化可以对数组或浮点数记录进行未装箱存储，否则会被破坏)。浮点数存储在转发的表示法中，作为带有指示 Forward_tag 的 header 的装箱值。唯一的字段是存储的值。

归类为计算的值存储为 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 字段的每次访问都需要昂贵的同步)。

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

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

这个技巧被多核团队劫持和重用，以在多个线程试图同时强制执行时使惰性值安全。当强制使用惰性值时，它们会用名为 bomb 的函数替换其负载。它检查在评估期间是否再次引用了惰性值(因为计算递归，或者因为它与另一个线程共享)，如果引用来自同一域，则触发 Undefined异常，表明这不是一个格式良好的惰性值，或者如果域不同，则引发 RacyLazy异常，这表明存在对来自不同域的相同惰性值的未序列化访问。

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

实现引用

这是

how lazy values are compiled

how lazy values are classified