在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和结果.最后,acc值与结果共享100%.所以这两个值是相同的.

这是一个简单的基本案例.现在让我们看一下归纳步骤:

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

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

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

该vh值将共享这两个值v和h.要创建vhOCaml,将分配一个新的链表节点,即一对指针.一个指针将引用v,另一个将引用h.值vhacc将与vh和共享值acc.因为,共享关系是可传递的,这意味着它将与v,h和共享值acc.在内部,它会创建一对指针,一个指向vh另一个指向acc.通过归纳,result意志分享v,h和t.

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

函数let insert v l = insertAux v l l将生成一个值,该值将共享两个输入值.这将创建一个列表,将包含名单的副本l,并且N其中将包含一个指向列表v的头部,而重复l的尾巴.

最后,函数子列表将产生一个值,即将共享其输入.它将创建一个列表,其中包含N+1元素,其中每个元素将是原始列表的子集,从输入列表的组件(共享)中精心构建.

总而言之,OCaml将分享所有价值观.如果值具有可变字段,则可能会出现问题.如果它们是不可变的,那么它对程序员来说是绝对透明的(即,不可见,不会影响语义等),并且可以对它们进行推理,就像它们总是被复制一样,并且每个新的构造函数都会创建一个全新的值没有分享,如果它使事情更容易.实际上,共享仅对可变数据结构有意义.此外,进一步的编译器优化,如Common Subexpression Elimination(CLE)可能会发现更多的共享机会.还有其他优化技术可以重用现有的值,如果有可能证明它们在程序的其他部分未被使用,那么就将它们变异(尽管据我所知,目前OCaml不会执行此优化).

还有一件事要知道.OCaml统一表示值,如果值可以适合单词,则表示为单词;如果不能,则表示为堆分配值的指针.基本上,它意味着,所有可以适合OCaml单词的值都将被取消装箱(例如,int,Nullary构造函数,字符等).