9

私はちょっとした 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、コンパイラはaimport fromBが宣言された と同じかどうかをチェックする必要がありますa = 2が、Bexportsのa場合にのみAエクスポートしaます。

module A(f) where
  import B(f)

module B(f) where
  import A(f)

module の解決中Aに、コンパイラは import ffromが存在すると想定し、 exportsがimportおよび exportできることBを暗示している可能性があります。唯一の問題は、どこにも定義されていないことです:)。AfBA(f)ff

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 ...略語のリストをエクスポートすると仮定します。アルゴリズムは、次のことができる必要があります。

  • 各モジュールのエクスポートされた変数の有限リストを計算する
  • エクスポートされたすべての変数をそのバインディングにリンクする
  • すべてのモジュールで使用されるすべての (おそらく修飾された) 変数をそのバインディングにリンクします
4

1 に答える 1

9

A Formal Specification for the Haskell 98 Module Systemに興味があるかもしれません。

また、一連のブログ投稿でいくつかの興味深いエッジ ケースを取り上げていますが、現時点で公開されているのは最初の1 つだけです。

最後に、まさにそれ、つまり Haskell モジュールを処理するライブラリに取り組んでいます。これはhaskell-namesと呼ばれます。

目的に応じて、コンパイラで使用したり、ソース コードを調べたり、貢献したりできます。（あなたの例は優れたテストケースになります。）

あなたの質問に答えるには: 再帰モジュールは、固定小数点を計算することによって処理されます。

モジュール グラフの強結合コンポーネントから始めます。このコンポーネントの各モジュールは、何もエクスポートしないという前提から始めます。次に、これらのモジュールに再度アクセスし、新しい情報に基づいて新しいエクスポート リストを計算します。このプロセスが単調であることを証明できます — エクスポート リストが大きくなるたびに (または、少なくとも縮小しません)。遅かれ早かれ、成長が止まります。そのとき、固定点に到達します。

このアルゴリズムを最適化するには、静的解析 (そのコミュニティは固定小数点の計算に非常に優れています) からいくつかのアイデアを借りることができますが、私のパッケージは現在単純なアルゴリズム ( code ) を実装しています。

于 2012-12-30T11:05:17.977 に答える