处理OCaml中的循环依赖

Question

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

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

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

看起来这需要所有类型的代码都在同一个文件中.有没有办法解决？你如何处理代码中的循环定义？

Answer 1

递归定义需要出现在同一个文件中.如果要将定义,语句和表达式分隔为单独的模块,可以使用递归模块,但它们仍然需要出现在同一个文件中.DAG-ifying文件间依赖性是OCaml的烦恼之一.

Answer 2

通过在类型引用的类型上参数化来轻松解决这个问题:

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

这种技术被称为"解开递归结"(参考Gordian的结),并在OCaml期刊文章中有所描述.

干杯,Jon Harrop.

Answer 3

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

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

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