OCaml 中的列表共享

Question

我对 OCaml 中的内存管理感到好奇。当列表通过程序调用共享时。例如:

let rec insertAux v acc l =
   match l with
   | [] -> acc 
   | h::t -> insertAux v ((v::h) :: acc) t;;

let insert v l = insertAux v l l;;
let rec sublist l = 
   match l with
   | [] -> [[]]
   | head::tail ->  insert head (sublist tail);;

insertAux 中的哪些元素/列表被复制或共享？

Answer 1

在我知道将共享什么以及在哪里共享之前，我需要确保我们对“共享”一词有一个共同的定义。我提出以下定义:“一个值在两个数据结构之间共享，前提是它们都包含指向该值的指针”。

让我们首先看一下 insertAux 函数，它接受三个值并生成结果值。那么，我们来推断一下输入值和结果之间的共享关系。如果l为空，则v和result之间不共享，l和result之间也不共享。最后，acc 值与结果 100% 共享。所以这两个值是相同的。

这是简单的基本情况。现在让我们看看归纳步骤:

| h::t -> insertAux v ((v::h) :: acc) t

让我们将中间值绑定(bind)到名称，以便我们可以轻松地在文本中引用它们:

| h::t -> 
  let vh = v :: h in
  let vhacc = vh :: acc in 
  let result = insertAux v vhacc t in
  result

vh 值将与 v 和 h 共享值。为了创建 vh，OCaml 将分配一个新的链表节点，即一对指针。一个指针将引用v，另一个指针将引用h。值 vhacc 将与 vh 和 acc 共享值。由于共享关系是传递的，这意味着它将与 v、h 和 acc 共享值。在内部，它将创建一对指针，一个指向vh，另一个指向acc。通过归纳，结果将共享v、h和t。

总而言之，insertAux 将构建一个新值，该值将共享输入值的所有组件。它将分配2*N个节点以新的方式连接共享值，其中N是列表l的长度。

函数let insert v l = insertAux v l l将产生一个值，该值将共享两个输入值。它将创建一个列表，其中包含列表 l 的副本，以及 N 列表，其中包含指向 v 的指针作为头，并重复 l 作为尾部。

最后，函数 sublist 将生成一个值，该值将共享其输入。它将创建一个列表，其中包含 N+1 元素，其中每个元素都是原始列表的子集，是根据输入列表的组件(共享的)新构建的。

总而言之，OCaml 将共享所有值(value)观。如果值具有可变字段，则可能会带来问题。如果它们是不可变的，那么它对程序员来说是绝对透明的(即不可见，不影响语义等)，并且可以像它们总是被复制一样推理它们，并且每个新的构造函数都会创建一个全新的值如果共享能让事情变得更容易，则无需共享。事实上，共享仅对可变数据结构才有意义。此外，进一步的编译器优化，例如公共(public)子表达式消除(CLE)，可能会发现更多的共享机会。还有其他优化技术，可以重用现有值，并就地改变它们，如果可以证明它们在程序的其他部分中未使用(尽管据我所知，目前 OCaml 不执行此优化) )。

还有一件事需要知道。 OCaml 统一表示值，如果值可以放入单词中，则表示为单词；如果不能放入堆分配值，则表示为指向堆分配值的指针。基本上，这意味着所有可以放入 OCaml 单词的值都将被拆箱(例如，整数、无效构造函数、字符等)。