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

Question

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

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

注意：此问题与 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

唯一的例外是float类型（由于另一个优化，该优化允许对数组或浮点数进行拆箱存储，否则将被破坏）。浮点数以框式值的形式存储在转发的符号中，其中的标题表示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

如我们所见，计算存储为大容量（并使用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中值的表示形式由标头决定。出于性能原因，OCaml多核团队决定禁止对标头进行任何更改，因此值不能再更改其表示形式（否则，如果它们允许更改标头，则对标头字段的每次访问都将需要昂贵的同步）。

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

在深入研究实现之前，还需要说明有关OCaml中的惰性值的另一件事。当强制使用惰性值时，由于计算本身可以递归并引用该惰性值，因此不会立即将其更新为计算结果。这就是为什么在调用附加到惰性值的计算之前的第一步，用引发Lazy.Undefined异常的函数替换了惰性函数的有效负载，从而使格式不正确的递归表达式仍然可以很好地终止。

当有多个线程试图同时强制执行懒惰值时，多核团队劫持并重用了该技巧。当强制使用一个懒惰值时，它们会用一个称为的函数替换其有效负载，该函数bomb检查在评估期间是否再次引用了该懒惰值（是由于计算递归还是因为它与另一个线程共享），以及该引用是否来自相同的域，则触发Undefined异常，表明这不是格式正确的惰性值；如果域不同，则引发RacyLazy异常，表明存在从不同域对同一惰性值的未序列化访问。

这里的关键时刻是要了解，由于惰性是可变值，因此用户仍然有责任正确地序列化对其的访问。如何正确有效地执行此操作仍在“未来工作”部分中。

实施参考

这是

• 惰性值如何编译
• 惰性值如何分类