9

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

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

这里的模块Fexport G.x，但G.x与 , 相同F.x，所以当且仅当它 export 时，模块才会F导出。xx

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)

在解析 module 期间A，编译器可能假设import ffromB存在，这意味着Aexport f，因此B可以 importA(f)和 export 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（可能带有asor qualified），并导出可能合格的变量和module ...缩写列表。该算法必须能够：

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

1 回答 1

9

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

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

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

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

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

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

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

于 2012-12-30T11:05:17.977 回答