haskell - 解决极端情况 Haskell 模块导入和导出

Question

我正在编写一个小 Haskell 编译器，我想尽可能多地实现 Haskell 2010。我的编译器可以解析一个模块，但完成一个程序的模块似乎是一项不平凡的任务。我制作了一些棘手但可能有效的 Haskell 模块示例:

module F(G.x) where
  import F as G
  x = 2

这里是模块F导出 G.x , 但是 G.x与 F.x 相同, 所以模块 F导出 x当且仅当它导出 x .

module A(a) where
  import B(a)
  a = 2

module B(a) where
  import A(a)

在本例中，解析模块 A 的导出编译器必须检查 a从 B 导入与声明的 a = 2 相同, 但是 B导出 a当且仅当 A导出 a .

module A(f) where
  import B(f)

module B(f) where
  import A(f)

在解析模块 A ，编译器可能假设 f从 B 导入存在，暗示 A导出 f ，因此 B可以进口A(f)和导出 f .唯一的问题是没有 f在任何地方定义:)。

module A(module X) where
  import A as X
  import B as X
  import C as X
  a = 2

module B(module C, C.b) where
  import C
  b = 3

module C(module C)
  import B as C
  c = 4

在这里，module导出导致导出列表相互依赖并依赖于它们自身。

所有这些示例都应该是有效的 Haskell，如 Haskell 2010 规范所定义。

我想问是否有任何想法如何正确和完整地实现 Haskell 模块？

假设一个模块只包含(简单的)变量绑定(bind)，import s (可能带有 as 或 qualified )，并导出可能合格的变量列表和 module ...缩写。该算法必须能够:

计算每个模块的导出变量的有限列表

将每个导出的变量链接到其绑定(bind)

将每个模块中使用的每个(可能是合格的)变量链接到它的绑定(bind)

Answer 1

您可能对 A Formal Specification for the Haskell 98 Module System 感兴趣.

我还在一系列博客文章中介绍了一些有趣的边缘案例，其中只有 first one现已发布。

最后，我正在研究那个——一个处理 Haskell 模块的库。它被称为 haskell-names .

根据您的目标，您可以简单地在编译器中使用它、研究源代码或贡献代码。 (您的示例将成为出色的测试用例。)

回答你的问题:递归模块是通过计算一个固定点来处理的。

您从模块图中的强连接组件开始。对于此组件中的每个模块，您首先假设它不导出任何内容。然后您重新访问这些模块，并根据新信息计算新的导出列表。你可以证明这个过程是单调的——每次导出列表增长(或者，至少不会缩小)。它迟早会停止增长——然后你就达到了固定点。

您可以通过借鉴静态分析中的一些想法来优化此算法(该社区非常擅长计算不动点)，但我的包目前实现了朴素算法(code)。