解析边缘-case 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的导出，编译器必须检查从B导入的a是否与声明的a = 2相同，但B导出a的条件是，且仅当A导出a时。

module A(f) where
  import B(f)

module B(f) where
  import A(f)

在解析模块A期间，编译器可能假设从B导入的f存在，这意味着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模块？

假设一个模块只包含(简单)变量绑定、imports (可能使用as或qualified)和导出可能限定变量的列表和module ...缩写。该算法必须能够：

• 计算每个模块导出变量的有限列表
• 将每个导出的变量链接到其绑定
• 将每个模块中使用的(可能是限定的)变量链接到其绑定

Answer 1

您可能对Haskell 98模块系统的形式化规范感兴趣。

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

最后，我正在处理这个问题--一个处理Haskell模块的库。它叫哈斯克尔-名字。

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

要回答您的问题:递归模块是通过计算不动点来处理的。

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

您可以借鉴静态分析的一些思想来优化这个算法(社区非常擅长计算不动点)，但是我的包目前实现了朴素算法(代码)。