ocaml中的类型建模

Question

我有一组Ocaml类型来表示一个语法树。有类型的程序，类，方法，表达式等。例如，一种方法是通过一个记录类型是这样表示的：

type method = { return:typeid; args:typeid list; body:expr } 

它包括一个返回类型，一种类型的每个参数，并且主体定义。我想键入检查语法树，并产生一种新的树，看起来非常像旧的树，除了每个表达式都有一个明确的typeid（仅在类型检查后知道）与它相关联。

一种选择是声明一组平行的类型：

type typed_expr = expr * typeid 
type typed_method = { return:typeid; args:typeid list; body:typed_expr } 
(* ... there are more types *) 

的typed_method是必要的，因为typed_expr是不同的类型。但我不想为未检查的AST和检查的AST维护两组几乎相同的类型。

另一种方法是如下定义表达式：

type expr = {...; typ:typeid option} 

这使我使用相同的类型定义为输入既检验器和输出。区别在于我将大量检查移动到检查的语法树的使用者代码中。这里有一个合同，typ字段永远不会在类型检查器输出中为None，并且在类型检查器输入中始终为None。

现在，每次我使用键入的树时，访问typ字段内部值的唯一方法是首先检查它是否为None（它不应该是）。这使得所有后来的消费者代码因为额外的检查而变得丑陋。

这些方法都不令我感到满意。你会如何模型？

Answer 1

第一个比第二个更好：可能有两组数据类型看起来很相似，但是很安全：第二种方法需要处理的不变量可以通过类型来解决。实际上OCaml编译器实现采用这种方法：请参阅parsetree.mli和typedtree.mli。

第一和第二之间，你可能要定义的数据类型，其typ字段参数：

type 'typ expr = { ...; typ : 'typ } 

然后你可以使用unit expr对于非类型化AST和typeid expr为类型化的AST。

我仍然更喜欢第一种方法为不同类型和不同类型的数据类型设置不同的集合，因为这两个世界的AST通常会比类型有一些其他差异。