encoding - 可推断记录的编码

Question

您可能知道，记录在ocaml中有些特殊，因为每个标签都必须唯一地分配给名义上的记录类型，即以下函数不能在没有上下文的情况下键入：

let f r = r.x

适当的头等记录（即行为类似于带有标签的元组的记录）使用对象进行琐碎的编码，例如

let f r = r#x 

当以正确的方式创建对象（即不进行自我递归，不进行突变）时，它们的行为就像记录。

但是，我对此解决方案有些不满意，原因有二：


当使记录可更新时（即通过为每个标签l添加显式的“ with_l”方法），类型有点太松散（应该与原始记录相同）。公认，可以强制执行这种平等，但这仍然很不方便。
我怀疑OCaml编译器不会推断这些记录实际上是不可变的：在函数中

令f r = r＃x + r＃x


编译器是否可以运行公共子表达式消除？

由于这些原因，我想知道是否有更好的编码：

在OCaml中是否还有另一种类型安全的记录（例如，使用对象）对类型可推断的记录进行类型安全编码（例如，使用多态变体）？
这种编码可以避免上述问题吗？

Answer 1

如果我对您的理解正确，那么您正在寻找一种非常特殊的多态性。您想要编写一个适用于所有类型的函数，以使该类型是具有某些字段的记录。这听起来更像是C ++风格的语法多态，而不是ML风格的语义多态。如果我们通过捕获字段访问只是字段投影函数的语法糖的想法来稍微改写任务，那么可以说，您要编写一个在提供特定集合的所有类型上都是多态的函数操作。 OCaml可以使用以下一种机制来捕获这种多态性：


函子
头等舱模块
对象


我认为函子是显而易见的，因此我将展示具有一流模块的示例。我们将编写一个函数print_student，该函数可用于满足Student签名的任何类型：

module type Student = sig
  type t
  val name : t -> string
  val age : t -> int
end


let print_student (type t)
    (module S : Student with type t = t) (s : t) =
  Printf.printf "%s %d" (S.name s) (S.age s)

print_student函数的类型为(module Student with type t = 'a) -> 'a -> unit。因此，它适用于满足Student接口的任何类型，因此它是多态的。这是一个非常强大的价格附带的多态性，调用该函数时需要显式传递模块结构，因此它是System F样式的多态性。函子还将要求您指定具体的模块结构。因此两者都是不可推论的（即您要寻找的不是隐式的类似于Hindley-Milner的样式多态性）。对于后者，只有对象可以工作（还有模块化的隐式对象，可以放宽对显式性的要求，但它们仍不在主干中，但实际上可以满足您的要求）。

使用对象样式的行多态性，可以编写一个在一组符合某个签名的类型上具有多态性的函数，并从函数定义中隐式地推断出此签名。但是，这种能力是有代价的。由于对象操作使用方法进行编码，并且方法只是在运行时中动态分配的函数指针，因此不应期望任何编译时优化。无法对动态绑定的对象执行任何静态分析。因此，当然，没有Common Subexpression消除，也没有内联。对于函子和一流模块，可以使用flamba在编译器的较新分支上进行优化（请参见4.03.0+flambda opam开关）。但是，在常规编译器安装中，不会执行内联。

不同的方法

关于其他技术。首先，我们可以使用camlp{4,5}或ppx甚至m4和cpp来预处理代码，但这几乎不是惯用的，而且用途不确定。

另一种方法是，代替编写多态函数，我们可以尝试找到合适的单态数据类型。一种直接的方法是使用多态变体列表，例如

type attributes = [`name of string | `age of int]
type student = attribute list  

实际上，我们甚至不需要预先指定所有这些类型，并且我们的函数可以只需要那些需要的字段，即行多态的一种形式：

let rec name = function
  | [] -> raise Not_found
  | `name n -> n
  | _ :: student -> name student

这种编码的唯一问题是，您不能保证同一命名属性只能出现一次且只能出现一次。因此，一个学生可能根本没有名字，或者更糟的是，学生可能只有一个名字。根据您的问题域，这是可以接受的。

如果不是，那么我们可以使用GADT和可扩展的变体对异构映射进行编码，即，将键映射到
不同类型（在常规（均匀）映射或assoc列表值类型中是统一的）。如何构造这样的容器超出了答案的范围，但是幸运的是，至少有两个可用的实现。我个人使用的一种称为通用映射（Univ_map），由Core library（实际上是Core_kernel）提供。它允许您指定两种异构映射，有和没有默认值。前者对应于带有可选字段的记录，后者对应每个字段的默认值，因此访问器是一个总功能。例如，

 open Core_kernel.Std

 module Dict = Univ_map.With_default

 let name = Dict.Key.create ~name:"name" ~default:"Joe" sexp_of_string
 let age  = Dict.Key.create ~name:"age"  ~default:18 sexp_of_int

 let print student = 
   printf "%s %d" 
     (Dict.get student name) (Dict.get age name)

您可以隐藏您使用的是抽象类型的通用映射，因为只能在不同的抽象之间使用一个Dict.t，这可能会破坏模块化。异构映射实现的另一个示例来自Daniel Bunzli。它不提供With_default类型的映射，但是依赖性要少得多。

附言当然，对于这种多余的情况，仅此一个操作，将该操作显式传递为函数要容易得多，而不是将其打包到结构中，因此我们可以从示例中编写函数f，就像。但这将与一流的模块/功能相同，只是简化了。我假设您的示例专门减少到一个字段，并且在您的实际用例中，您拥有更复杂的字段集。