3

こんにちは、Haskell で C ライクな静的型付け言語のインタープリターを書いています。コードの実行前に型チェックを実行したいのですが、いくつか問題があります。まず、以下に私の抽象構文からの型定義をいくつか示します。

newtype Ident = Ident String deriving (Eq,Ord,Show)
data Exp = {-- some other value constructors --} | EFuncWithParams Ident [Exp]
data Type = TInt | TDouble | {-- some other value constructors --} | TFunction [Exp]
type TCM a = ErrorT String (Reader Env) a

TCM は、エラーを報告し、環境を渡すためのものです。

typeof (EVar v) = do
env <- ask
case M.lookup v env of
    Nothing -> throwError $ "undefined variable" ++ v ++ "\n"
    Just t - > return t

今、式のタイプをチェックしたいので、チェックを実行する次の関数があります:

typeof Exp :: Exp -> TCM Type

1 つを除くすべてのケースに対して定義されます。

typeof (EFuncWithParams f l)

私はここで立ち往生しています。私がすべきだと思うのは、f の型をチェックすることです (つまり、最初にそれが本当に関数かどうかをチェックするということです)。f の定義に記録されている引数の型が、実際に渡される引数の型と一致するかどうかを確認します。残念ながら、私は Haskell の初心者であり、正しい方法で表現する方法がわかりません。どんな提案でも大歓迎です:)

編集: わかりました、以前ここに書いたことには暗示されていないかもしれませんが、EFuncWithParams Ident [Exp] は実際には関数呼び出しであり (はい、多少誤解を招くことはわかっています)、 f(2 + 3, a, b[0]) であり、これが TFunction [Exp] を使用した理由です。関数の宣言と定義はステートメントであり、次のように定義されます。

data Function_def =
   Func Type_specifier Declarator Compound_stm
   deriving (Eq,Ord,Show)

ここで、宣言子は次のとおりです。

data Declarator =  FuncDec Ident Parameter_declarations

パラメータ宣言は Type_specifiers と Idents のリストです

私がすべきだと思うのは、宣言を確認しながら関数型をマップに保存し、ここでフェッチすることです。私も持っていることを意味します：

typeof_stm :: Stm -> TCM Type -- Function_def is a statement

問題は、型チェック ステートメント用の別の関数があり、ある関数 (typeof_stm など) で使用されるマップが別の関数 (typeof など) に自動的に渡されるかどうか疑問です。これが起こる方法はないと思いますが、間違っているかもしれません。

4

3 に答える 3

3

関数のタイプが間違っていると思います。あなたはそれを持っていますTFunction [Exp]、そうあるべきですTFunction [Type] Type（引数の型と戻り値の型のリスト）。

関数呼び出しの型チェック コードは次のようになります。

case ... of ...
  EFuncWithParams ident args -> do
     t <- typeof (EVar ident)
     ts <- mapM typeof args
     case t of
         TFunction ps r -> if ts == ps
                               then return r
                               else throwError $ "parameter types do not match"
         _ -> throwError $ "called id " ++ ident ++ " which is not a function"

この疑似コードはおそらく不適切にモナドに出入りします。ご容赦ください。すべてのコードを持っているわけではないので、自分が行ったことを実際にタイプチェックすることはできません。しかし、全体的なスキームはこのようなものです。パラメーターの型が一致しない場合 (どの型が一致しないか、またはパラメーターの数が間違っている可能性があります)、より詳細なエラー レポートを提供することをお勧めします。

于 2012-04-19T15:53:38.363 に答える
1

私は Haskell では実用的ではありません。OCaml と C++ でやっただけですが、これから行うことは、各パラメーターで型チェッカー関数を再帰的に呼び出して、それらが対応しているかどうかを確認することです。

私が言いたいのは、次のようなものをタイプチェックする必要があるということです

FunCall ident, exp list

これで、パラメータのタイプが関連付けられた関数のエントリが環境内に作成されるため、順序で確認する必要があるのは次のとおりです。

  • 指定された関数identは環境に存在します
  • パラメーターの数は定義と同じです (これは、param チェック関数によって暗黙的に行うことができます。以下を参照してください)
  • 呼び出すすべてのパラメーターに対して、返されたパラメーターが対応するパラメーターと同じであるtypeof (exp1)ことを確認しますTCM Type

これがどのように機能するかです。OCaml (Haskell に多少似ています) では、次のようにします。

match exp with
    | FunCall ident, (param list) ->
      (* get fundecl from ident *)
      (* call check_params list_of_parameters, list_of_type_of_parameters *)
      (* if check params return true then type check value of the function is the return value *)


let check_params list decl_list =
  match list, decl_list with
    | [], [] -> true
    | p :: rp, d :: rd -> typeof(p) = d && check_params rp rd
    | _ -> false
于 2012-04-19T15:18:57.700 に答える
0 
EFuncWithParams Ident [Exp]

あなたのような言語では、入力に型注釈が必要であり、場合によっては出力にも型注釈が必要になるのが一般的です。したがって、この情報をそのコンストラクターに追加すると

EFuncWithparams { inType, outType :: Type
                , funcInput :: Ident
                , funcBody :: [Expr] }

タイプチェックするには、次のようにします。

  1. のバインディングをタイプ環境に追加funcInputしinTypeます
  2. funcBody新しいタイプの環境でのタイプを確認する
  3. と一致していることを確認してくださいoutType。

また、関数の適用をチェックして、入力が関数の と一致していることinType、および結果が に従って正しく使用されていることを確認する必要がありますoutType。

于 2012-04-19T15:29:39.773 に答える