5

Haskellを使ったコンパイラ構築を勉強しています。固定小数点データ型の再帰を使用して抽象構文木 (ast) を表現しています。

単純な式 (数値定数と論理定数、二項演算、ローカル変数宣言) を持つおもちゃの言語の型チェッカーを作成する方法を調査しています。

型チェッカーは read-write-state ( RWS) モナドです:

  • リーダーは、シンボル定義 (シンボルとそのタイプの連想リスト) を含む環境から構成されるコンテキストを使用するためです。
  • エラーメッセージのリストを生成するためのライター。
  • state は後で名目上の型の等価性を実装するために必要になりますが、今はプログラムで定義されている変数の数を数えているだけです (その使用方法のデモンストレーションとして)。

モナドによって返される値は、型 (式の場合) または環境 (宣言の場合) で注釈が付けられた ast です。

この関数checkerは入力プログラムの ast を受け取り、RWS実行時に型 (ast が式の場合) または環境 (ast が宣言の場合) を与えるモナド アクションで注釈が付けられた新しい ast を生成します。

たとえば、入力プログラムを考えてみましょう

let x = 2 + 3 in 1 + x

対応する ast:

                    Let                     
                     |                      
          -----------------------           
         |                      |           
     VarDec: x               Bin Add        
         |                      |           
         |                ------------      
         |                |          |      
      Bin Add          Num 1.0     Var x    
         |                                  
    -----------                             
   |          |                             
Num 2.0    Num 3.0

型チェックを行うと、次の ast が生成されます。

                  action1
                    Let                     
                     |                      
          -----------------------           
         |                      |           
      action2                action3
     VarDec: x               Bin Add        
         |                      |           
         |                ------------      
         |                |          |      
      action4          action5    action6
      Bin Add          Num 1.0     Var x    
         |                                  
    -----------                             
   |          |                   
action7    action8      
Num 2.0    Num 3.0

RWSモナドアクションで再帰的に注釈が付けられています。

コンパイラの後のフェーズでは、ast (およびその子、再帰的に) の注釈によって生成された情報を知る必要があります。したがって、それを取得するには、対応するアクションを実行する必要があります。

ルート アクションは、言語の規則に従って、子のアクションを構成することによって構築されます。

たとえば、ルート式 ( let 式) の型を取得するには、を実行する必要があります。これは、作成時に and を使用したため、 action1makeaction2およびaction3も実行されます。action1action2action3

追加のタイプ1+xが必要な場合action3は、それを取得するために実行する必要があります。

したがって、アクションは繰り返し実行されます。型チェッカーが (RWSモナド アクションを使用して) 構造化される方法では、ast の各ノードの計算された情報の共有が失われます。

この共有を回復して、アクションを再計算する必要をなくす手法はありますか?

4

2 に答える 2

1

あなたのデザインが袋小路になってしまったようですね。あなたはそれがどのように見えるかを少し見せています。

Haskellを使ったコンパイラ構築を勉強しています。

勉強するということは、他の人がどのように型チェックを行っているかを読むことができるということです (例: GHC またはOlegの例)。あるいは、発明を試みることによって、より多くのことを学びたいというあなたの意味かもしれません。

型チェッカーが構造化されている方法... ast の各ノードの計算された情報の共有が失われます。

だから情報を逃さない。型チェッカーがモナド内で実行される場合、最終的には、状態を記憶するように設計できます。

この共有を回復して、アクションを再計算する必要をなくす手法はありますか?

より具体的には、実行後に actionX をその結果に置き換えたいとします。これは、遅延値に対する欲求に非常に非常によく似ています。一度計算して結果を記憶します (エラーが発生した場合は少し注意が必要です)。

おそらく、各アクションは、それ自体を含め、そのノードからサブツリーを再計算します。子のアクションは、その結果 (および再計算されたサブツリー) に置き換えられます。

または、AST が 1 つの不変のものである場合、おそらく状態は並列 AST である必要があります。

于 2012-05-18T08:17:24.730 に答える
0

アクションは常に型を指定し、場合によっては変更する必要があります環境。レキシカル環境自体は、それぞれがスコープをキャプチャし、型への識別子のマップを含むレキシカル フレームのスタック (またはリスト) として、モナド内で直接持ち運ぶことができます。統合を行っている場合は、型を実際の型にするか、型変数から型への別のマップを指す単純な型変数にします。(この側面により、変更可能なストアが提供されます。) そのマップに型変数の値がない場合、型はまだ開いています。タイプが何に統合されるかを把握したら、その統合を関連付けとしてマップに追加します。(もちろん、2 つの型変数を統合するということは、新しい型変数を作成し、他の両方をそれに統合することを意味します。これが、基本的な統合の唯一の「トリック」です)。

いずれにせよ、実装テクニックへのいくつかのポインタについては、wren の統合ライブラリを参照してください: http://hackage.haskell.org/package/unification-fd。STVar彼が真の可変性を使用するバックエンドと、フードの下で不変マップを使用するバックエンドをどのように持っているかに注意してくださいIntVar(これは、上で説明したもののようなものです)。

編集: また、各アクションが RWS の背後にある場合、定義上、それらの間で共有する方法がないことも思い浮かびます! AST の再帰的な修正点は素晴らしいですが、実際に回避しようとしている「非共有」動作を明示的に作成したい場合を除き、モナドを各レベルに「プッシュ」する利点はありません。

編集: AST にすべてのレベルの型で注釈を付けるには、型をtypecheckfromExpr () -> m TypeからExpr -> m (Expr Type)expr が何らかの注釈でパラメータ化されている場所に変更するだけです! 現在、AST に型で注釈を付けていません。型を生成できる計算で注釈を付けています! それでは、最初に計算を実行してください...

于 2012-05-18T12:32:52.677 に答える