解决边缘案例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 2010规范的定义,所有这些示例都应该是有效的Haskell.

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

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

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

Answer 1

您可能对Haskell 98模块系统的正式规范感兴趣.

我还在一系列博客文章中介绍了一些有趣的边缘案例,其中第一篇仅截至目前已发布.

最后,我正在努力 - 一个处理Haskell模块的库.它叫做haskell-names.

根据您的目标,您可以在编译器中使用它,研究源代码或贡献.(您的示例将成为优秀的测试用例.)

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

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

您可以通过借用静态分析中的一些想法来优化此算法(该社区非常擅长计算固定点),但我的包目前实现了朴素算法(代码).