在 OCaml 中处理循环依赖

Question

我正在为一种实验语言编写一个解释器。该语言的三个主要结构是定义、语句和表达式。定义可以包含语句和表达式，语句可以包含定义和表达式，一种表达式可以包含语句。我使用联合类型表示所有这些，因此我可以轻松地对它们使用模式匹配。理想情况下，我想将这些代码放在不同的文件中，但 OMake 抱怨循环依赖问题。据我所知，跨模块的循环类型定义是不允许的。

我知道解决这个问题的唯一方法是同时定义所有三种类型：

type defn = ...
and stmt = ...
and expr = ...

似乎这需要类型的所有代码都位于同一个文件中。有没有办法解决？您如何处理代码中的循环定义？

Answer 1

递归定义需要出现在同一文件中。如果要将定义、语句和表达式分离到单独的模块中，可以使用 递归模块, ，但它们仍然需要出现在同一个文件中。DAG 化文件间依赖关系是 OCaml 的烦恼之一。

Answer 2

通过参数化您的类型所引用的类型可以轻松解决此问题：

type ('stmt, 'expr) defn = ...
type ('defn, 'expr) stmt = ...
type ('defn, 'stmt) expr = ...

这种技术被称为“解开递归结”（参考戈尔迪安结），并在 OCaml杂志 文章。

欢呼，乔恩·哈罗普（Jon Harrop）。

Answer 3

另一个经常使用的解决方案是抽象接口中的类型。由于接口中的类型是抽象的，因此这些接口不是递归依赖的。在实现中，您可以指定类型，并且由于实现仅依赖于接口，因此它们也不是递归的。

唯一的问题是，使用此解决方案，您无法再在其实现之外对这些类型进行模式匹配。

就我个人而言，但这可能是一个品味问题，我喜欢将程序的所有类型定义在一个模块中（我认为这有助于提高程序的可读性）。所以，OCaml 的这个限制对我来说并不是真正的问题。