18

Haskell で C に似た言語のコンパイラを作成しようとしています。コンパイラは、AST を変換することによって進行します。最初のパスでは、入力を解析して AST を作成し、シンボル テーブルと結び目を結び、シンボルが定義される前に前方参照を必要とせずにシンボルを配置できるようにします。

AST には型と式に関する情報が含まれており、それらの間に接続が存在する可能性があります。たとえば、型にsizeof(T)依存する式TでありT[e]、定数式に依存する配列型ですe。

型と式は、次のような Haskell データ型で表されます。

data Type = TypeInt Id
          | TypePointer Id Type -- target type
          | TypeArray Id Type Expr -- elt type, elt count
          | TypeStruct Id [(String, Type)] -- [(field name, field type)]
          | TypeOf Id Expr
          | TypeDef Id Type

data Expr = ExprInt Int -- literal int
          | ExprVar Var -- variable
          | ExprSizeof Type
          | ExprUnop Unop Expr
          | ExprBinop Binop Expr Expr
          | ExprField Bool Expr String -- Bool gives true=>s.field, false=>p->field

whereUnopには、address-of ( &) や dereference ( *) などのBinop演算子が含まれ、plus ( +) や times ( *) などの演算子が含まれます...

各タイプには一意の が割り当てられていることに注意してくださいId。これは、無限の型につながるサイクルを検出するために、型依存グラフを構築するために使用されます。型グラフに循環がないことを確認したら、無限ループに陥ることなく再帰関数を安全に適用できます。

次の手順では、各型のサイズを決定し、構造体フィールドにオフセットを割り当て、ExprFields をポインター演算に置き換えます。そうすることで、式の型を決定し、型グラフから s ExprSizeof、ExprFields、TypeDefs、およびTypeOfs を削除できるため、型と式は進化し、次のようになります。

data Type' = TypeInt Id
           | TypePointer Id Type'
           | TypeArray Id Type' Int -- constant expression has been eval'd
           | TypeStruct Id [(String, Int, Type')] -- field offset has been determined

data Expr' = ExprInt Type' Int
           | ExprVar Type' Var
           | ExprUnop Type' Unop Expr'
           | ExprBinop Type' Binop Expr' Expr'

一部のデータ コンストラクターを削除し、その他の一部をわずかに変更したことに注意してください。特に、 にType'はもはや が含まれておらずExpr'、everyExpr'はその を決定していType'ます。

では、最後に質問です。ほとんど同じデータ型のセットを 2 つ作成するのと、それらを 1 つのデータ型に統合するのとではどちらがよいのでしょうか。

2 つの別個のデータ型を保持すると、特定のコンストラクターが表示されなくなることが明示されます。ただし、定数式を評価するために定数の折りたたみを実行する関数には、次の型があります。

foldConstants :: Expr -> Either String Expr'

しかし、これは後で s を使用して定数の折りたたみを実行できないことを意味します( を操作し、出現した定数式を折りたたみたいExpr'パスを想像してください)。Expr'別の実装が必要になります。

foldConstants' :: Expr' -> Either String Expr'

一方、単一の型を維持すると、定数の折り畳みの問題は解決しますが、型チェッカーが静的な不変条件を強制することはできなくなります。

さらに、最初のパスで不明なフィールド (フィールド オフセット、配列サイズ、式の型など) に何を入力するのでしょうか? undefined、 またはで穴をふさぐこともできますがerror "*hole*"、それは災害が発生するのを待っているように感じます (NULLチェックすることさえできないポインターのように)。不明なフィールドをMaybes に変更し、穴をNothing(チェックできるNULLポインターのように) 塞ぐこともできますが、後続のパスで、常に s になる値を s から引き出し続けなければならないのは煩わしいでしょう。MaybeJust

4

2 に答える 2

16

うまくいけば、より多くの経験を持つ誰かが、より洗練された、戦いでテストされた、すぐに使える答えを持っているでしょうが、これが私のショットです。

GADTを使用すると、比較的少ないコストでパイを持ってその一部を食べ​​ることができます。

{-# LANGUAGE GADTs #-}

data P0 -- phase zero
data P1 -- phase one

data Type p where
     TypeInt     :: Id -> Type p
     TypePointer :: Id -> Type p -> Type p             -- target type
     TypeArray   :: Id -> Type p -> Expr p -> Type p   -- elt type, elt count
     TypeStruct  :: Id -> [(String, Type p)] -> Type p -- [(field name, field type)]
     TypeOf      :: Id -> Expr P0 -> Type P0
     TypeDef     :: Id -> Type P0 -> Type P0

data Expr p where
     ExprInt     :: Int -> Expr p                        -- literal int
     ExprVar     :: Var -> Expr p                        -- variable
     ExprSizeof  :: Type P0 -> Expr P0
     ExprUnop    :: Unop -> Expr p -> Expr p
     ExprBinop   :: Binop -> Expr p -> Expr p -> Expr p
     ExprField   :: Bool -> Expr P0 -> String -> Expr P0 -- Bool gives true=>s.field, false=>p->field

ここで変更したものは次のとおりです。

  • データ型はGADT構文を使用するようになりました。これは、コンストラクターが型アノテーションを使用して宣言されることを意味します。data Foo = Bar Int Charになりdata Foo where Bar :: Int -> Char -> Fooます（構文を除けば、2つは完全に同等です）。

  • との両方に型変数を追加しましTypeたExpr。これは、いわゆるファントム型変数です。型の実際のデータは格納されてpおらず、型システムで不変条件を適用するためにのみ使用されます。

  • 変換の前後のフェーズを表すダミータイプを宣言しました：フェーズ0とフェーズ1。（複数のフェーズを持つより複雑なシステムでは、タイプレベルの番号を使用してそれらを示すことができる可能性があります。）

  • GADTを使用すると、タイプレベルの不変条件をデータ構造に格納できます。ここに2つあります。1つ目は、再帰的な位置は、それらを含む構造と同じフェーズでなければならないということです。たとえば、を見ると、コンストラクターにTypePointer :: Id -> Type p -> Type paを渡して、結果としてaを取得します。これらのは、同じ型である必要があります。（異なるタイプを許可したい場合は、とを使用できます。）Type pTypePointerType pppq

  • 2つ目は、一部のコンストラクターは最初のフェーズでのみ使用できるという事実を強制することです。ほとんどのコンストラクターはファントム型変数pでポリモーフィックですが、一部のコンストラクターではそれがである必要がありますP0。つまり、これらのコンストラクターは、タイプType P0またはの値を作成するためにのみ使用できExpr P0、他のフェーズは使用できません。

GADTは2つの方向で機能します。1つ目は、を返す関数がありType P1、それを構築するためにを返すコンストラクターの1つを使用しようとするとType P0、型エラーが発生することです。これは「構築による修正」と呼ばれるものです。無効な構造を構築することは静的に不可能です（型システムで関連するすべての不変条件をエンコードできる場合）。逆に、の値がある場合はType P1、正しく構築されていることを確認できます。コンストラクターTypeOfとTypeDefコンストラクターは使用できません（実際、それらでパターンマッチングを行おうとすると、コンパイラーは文句を言います） 、および再帰的な位置もフェーズである必要がありますP1。基本的に、GADTを作成するときは、型の制約が満たされているという証拠を保存し、パターンマッチを行うときは、その証拠を取得して利用できます。

それは簡単な部分でした。残念ながら、2つのタイプの間には、コンストラクターが許可される範囲を超えていくつかの違いがあります。コンストラクター引数の一部はフェーズ間で異なり、一部は変換後のフェーズにのみ存在します。GADTを使用してこれをエンコードすることもできますが、低コストでエレガントではありません。1つの解決策は、異なるコンストラクターをすべて複製し、とにそれぞれ1つずつ持つことP0ですP1。しかし、複製は良くありません。私たちはそれをよりきめ細かくすることを試みることができます：

-- a couple of helper types
-- here I take advantage of the fact that of the things only present in one phase,
-- they're always present in P1 and not P0, and not vice versa
data MaybeP p a where
     NothingP :: MaybeP P0 a
     JustP    :: a -> MaybeP P1 a

data EitherP p a b where
     LeftP  :: a -> EitherP P0 a b
     RightP :: b -> EitherP P1 a b

data Type p where
     TypeInt     :: Id -> Type p
     TypePointer :: Id -> Type p -> Type p
     TypeArray   :: Id -> Type p -> EitherP p (Expr p) Int -> Type p
     TypeStruct  :: Id -> [(String, MaybeP p Int, Type p)] -> Type p
     TypeOf      :: Id -> Expr P0 -> Type P0
     TypeDef     :: Id -> Type P0 -> Type P0

-- for brevity
type MaybeType p = MaybeP p (Type p)

data Expr p where
     ExprInt     :: MaybeType p -> Int -> Expr p
     ExprVar     :: MaybeType p -> Var -> Expr p
     ExprSizeof  :: Type P0 -> Expr P0
     ExprUnop    :: MaybeType p -> Unop -> Expr p -> Expr p
     ExprBinop   :: MaybeType p -> Binop -> Expr p -> Expr p -> Expr p
     ExprField   :: Bool -> Expr P0 -> String -> Expr P0

MaybePここでは、いくつかのヘルパータイプを使用して、一部のコンストラクター引数はフェーズ1（ ）にのみ存在でき、一部は2つのフェーズ（）間で異なるという事実を強制しましたEitherP。これにより完全にタイプセーフになりますが、少しアドホックな感じがします。それでも、常にMaybePsとEitherPsの内外で物事をラップする必要があります。その点でもっと良い解決策があるかどうかはわかりません。ただし、完全な型安全性は何かですfromJustP :: MaybeP P1 a -> a。完全かつ完全に安全であることを記述して確認することができます。

更新：別の方法は次を使用することTypeFamiliesです：

data Proxy a = Proxy

class Phase p where
    type MaybeP  p a
    type EitherP p a b
    maybeP  :: Proxy p -> MaybeP p a -> Maybe a
    eitherP :: Proxy p -> EitherP p a b -> Either a b
    phase   :: Proxy p
    phase = Proxy

instance Phase P0 where
    type MaybeP  P0 a   = ()
    type EitherP P0 a b = a
    maybeP  _ _ = Nothing
    eitherP _ a = Left a

instance Phase P1 where
    type MaybeP  P1 a   = a
    type EitherP P1 a b = b
    maybeP  _ a = Just  a
    eitherP _ a = Right a

Expr以前のバージョンとの唯一の変更点Typeは、コンストラクターにPhase p制約を追加する必要があることExprInt :: Phase p => MaybeType p -> Int -> Expr pです。

ここpで、Typeまたはのタイプがわかっている場合は、 sがであるか、指定されたタイプであるか、およびsがどのタイプであるExprかを静的に知ることができ、明示的にアンラップすることなく、それらをそのタイプとして直接使用できます。不明な場合は、クラスから使用して、それらが何であるかを調べることができます。（引数が必要です。そうしないと、コンパイラーは意図したフェーズを判断できません。）これはGADTバージョンに類似しており、既知の場合は何が含まれているのかを確認できますが、そうでない場合は次のようになります。両方の可能性にパターンマッチします。この解決策は、「欠落している」引数が次のようになるという点でも完全ではありません。MaybeP()EitherPpmaybePeitherPPhaseProxypMaybePEitherP()完全に消えるのではなく。

sExprとTypesの作成も、2つのバージョン間でほぼ同じように見えます。作成する値にフェーズ固有の値がある場合は、そのタイプでそのフェーズを指定する必要があります。p多態的な関数を記述したいが、それでもフェーズ固有の部分を処理したい場合に問題が発生するようです。GADTを使用すると、これは簡単です。

asdf :: MaybeP p a -> MaybeP p a
asdf NothingP  = NothingP
asdf (JustP a) = JustP a

asdf _ = NothingP出力のタイプが入力と同じであることが保証されないため、私が単に記述した場合、コンパイラは文句を言うことに注意してください。パターンマッチングにより、入力がどのタイプであるかを把握し、同じタイプの結果を返すことができます。

ただし、このTypeFamiliesバージョンでは、これは非常に困難です。使用するだけmaybePで、結果としてMaybe、型についてコンパイラに何も証明できません。maybePを持ってeitherP戻る代わりに、MaybeとのようにEitherデコンストラクター関数を作成することで、その途中の一部を取得できます。これにより、型の同等性も利用できるようになります。maybeeither

maybeP  :: Proxy p -> (p ~ P0 => r) -> (p ~ P1 => a -> r) -> MaybeP p a -> r
eitherP :: Proxy p -> (p ~ P0 => a -> r) -> (p ~ P1 => b -> r) -> EitherP p a b -> r

（これが必要であることに注意してください。また、これらは基本的にとRank2TypesのGADTバージョンのCPS変換バージョンであることに注意してください。）MaybePEitherP

次に、次のように書くことができます。

asdf :: Phase p => MaybeP p a -> MaybeP p a
asdf a = maybeP phase () id a

しかし、GHCは次のように述べているため、それでも十分ではありません。

data.hs:116:29:
 Could not deduce (MaybeP p a ~ MaybeP p0 a0)
 from the context (Phase p)
   bound by the type signature for
              asdf :: Phase p => MaybeP p a -> MaybeP p a
   at data.hs:116:1-29
 NB: `MaybeP' is a type function, and may not be injective
 In the fourth argument of `maybeP', namely `a'
 In the expression: maybeP phase () id a
 In an equation for `asdf': asdf a = maybeP phase () id a

どこかで型アノテーションを使ってこれを解決できるかもしれませんが、その時点では、それは価値があるよりも面倒なようです。したがって、他の誰かからのさらなる情報が保留されているので、少し構文上のノイズを犠牲にして、より単純でより堅牢なGADTバージョンを使用することをお勧めします。

再度更新する：ここでの問題MaybeP p aは、は型関数であり、他に通過する情報がないため、GHCには何pをaすべきかを知る方法がないということでした。を渡して、Proxy pその代わりにそれを使用すると、がphase解決されますが、それでも不明です。pa

于 2012-05-25T23:53:04.493 に答える
4

それぞれに長所と短所があるため、この問題に対する理想的な解決策はありません。

個人的には、単一のデータ型「ツリー」を使用し、区別する必要があるものに対して個別のデータ コンストラクターを追加します。すなわち:

data Type
  = ...
  | TypeArray Id Type Expr
  | TypeResolvedArray Id Type Int
  | ...

includeあなたが言うように、これには同じツリーで同じフェーズを複数回実行できるという利点がありますが、その理由はそれよりも深くなります:より多くのASTを生成する構文要素(またはC++テンプレートのようなもの)を実装しているとしましょう一種の取引であり、あなたのような定数 expr に依存する可能性があるTypeArrayため、最初の反復で評価することはできません)。統一されたデータ型のアプローチでは、既存のツリーに新しい AST を挿入するだけで済みます。以前と同じフェーズをそのツリーで直接実行できるだけでなく、無料でキャッシュを取得できます。つまり、新しい AST がまたは何かを使用して配列を作成する場合、その型は既に以前の解決フェーズからのものであるため、定数サイズを再度sizeof(typeof(myarr))決定する必要はありません。myarrTypeResolvedArray

すべてのコンパイル段階を過ぎて、コード (または何か) を解釈するときが来たら、別の表現を使用できます。そうすれば、AST を変更する必要がなくなるという事実を確信でき、より合理化された表現が得策となる可能性があります。

ちなみに、配列サイズData.Word.Wordの代わりに使用する必要があります。Data.Int.Int配列のインデックス付けに sを使用するのは、C でよくあるエラーですが、intC ポインターは実際には符号なしです。負のサイズの配列を本当にサポートしたい場合を除き、あなたの言語でもこの間違いを犯さないでください。

于 2012-05-25T23:04:10.760 に答える