2

命令型プログラミング言語で記述されたプログラムを型チェックするために、Haskell でプログラムを記述しようとしています。

抽象構文は次のとおりです。

    type Name = String

-- プログラムは一連の変数宣言 (リスト) と一連のステートメント (リスト) です。

    type Prog = ([TypeEnv],[Stmt])

-- 変数宣言は型と変数名です

    type TypeEnv = (Type,Name)

-- タイプは「int」または「bool」、または「int[]..[]」または「bool[]..[]」のいずれかです。

   data Type = BaseType BT | ArrayType BT Int deriving Show
   data BT = TyInt | TyBool deriving Show

-- ステートメントは次のいずれかです...

   data Stmt =
   Assign Name Exp                -- ...assignment (<name> := <exp>;)
   | If Exp [Stmt] [Stmt]           -- ...if-then-else (if <bexp> { <stmt>* } else { <stmt>* })
   | While Exp [Stmt]               -- ...a while-loop (while <bexp> { <stmt>*> })
   | Let Name Exp [Stmt]            -- ...let bindings (let <name>=<exp> in { <stmt> *}) 
   | LetArray Name [Exp] Exp [Stmt] -- ...let-array binding (letarray <name> [ <exp> ] .. [ <exp> ] := <exp> in { <stmt>* })
   | Case Exp [(Int,[Stmt])]        -- ...a case statements
   | For Name Exp Exp [Stmt]        -- ...a for-loop
   | ArrayAssign Name [Exp] Exp       -- ...or array assignment (<name> [ <exp> ] .. [ <exp> ] := <exp>;)
   deriving Show

-- 式は次のいずれかです...

data Exp =
Add Exp Exp             -- ...addition (<exp> + <exp>)
| Sub Exp Exp             -- ...subtract (<exp> - <exp>)
| Mul Exp Exp             -- ...multiplication (<exp> * <exp>)
| Neg Exp                 -- ...negation (-<exp>)
| Var Name                -- ...a variable (<name>)
| LitInt Int              -- ...an integer literal (e.g. 3, 0, 42, 1999)
| VarArray Name [Exp]     -- ...or an array lookup (<name> [ <exp> ])
| IsEq Exp Exp            -- ...test for equality (<exp> == <exp>)
| IsNEq Exp Exp           -- ...test for inequality (<exp> != <exp>)
| IsGT Exp Exp            -- ...test for greater-than (<exp> > <exp>)
| IsLT Exp Exp            -- ...test for less-than (<exp> < <exp>)
| IsGTE Exp Exp           -- ...test for greater-or-equal (<exp> >= <exp>)
| IsLTE Exp Exp           -- ...test for less-or-equal (<exp> <= <exp>)
| And Exp Exp             -- ...boolean and (<bexp> && <bexp>)
| Or Exp Exp              -- ...boolean or (<bexp> || <bexp>)
| Not Exp                 -- ...boolean negation (!<bexp>)
| LitBool Bool            -- ... or a boolean literal (true or false)
deriving Show

誰かが私の質問に完全に答える必要はありませんが、これまでに持っているものを提供したいと思います。誰かが私を正しい方向に向けたり、私が完全に間違っているかどうかを教えてくれたりすると、それは非常に役に立ちます.

プログラムを型チェックする関数は typecheck から始まります。typecheck は typecheckstmt を使用して最初のステートメントを型チェックし、typecheckstmtlist を使用してプログラムの残りを型チェックします。次に、これらの関数は typecheckexp を使用して式を型チェックします。明らかに、私は実装の非常に基本的なスケルトンを持っています。私が正しい方向に向かっているかどうか、そして誰かが指針を持っているかどうかを知りたいだけです。

   typecheck :: Prog -> Bool
   typecheck _ = True
   typecheck (types, x: xs) = (typecheckstmt types x) && (typecheckstmtlist types xs)

   typecheckstmt :: [TypeEnv] -> Stmt -> Bool
   typecheckstmt _ _ = True
   typecheckstmt types (Assign x e) = if checkequaltypes x e
                  then True && typecheckexp types e
                  else False
   typecheckstmt types (If e stmtlst1 stmtlst2) = typecheckexp types e 
                       && typecheckstmtlist types stmtlst1 
                       && typecheckstmtlist types stmtlst2
   typecheckstmt types (While e stmtlst) = typecheckexp types e 
                    && typecheckstmtlist types stmtlst
   typecheckstmt types (Let x e stmtlst) = if checkequaltype types x e
                       then True && typecheckexp types e
                             && typecheckstmtlist types stmtlst
                       else False
   typecheckstmt types (LetArray x es e2 stmtlst) = 
   typecheckstmt types (Case e cases) = 
   typecheckstmt types (For x e1 e2 stmtlst) = if checkequaltype types x e1 
                           && checkequaltype types x e2 
                           then True && typecheckstmtlist stmtlst 
                           else False
   typecheckstmt types (ArrayAssign x es e2) = 

   typecheckstmtlist :: [TypeEnv] -> [Stmt] -> Bool
   typecheckstmtlist _ _ = True
   typecheckstmtlist types [x] = typecheckstmt types x
   typecheckstmtlist types x:xs = typecheckstmt types x && typecheckstmtlist types xs


   typecheckexp :: [TypeEnv] -> Exp -> Bool
   typecheckexp types (Add e1 e2) = 
   typecheckexp types (Sub e1 e2) =
   typecheckexp types (Mul e1 e2) =
   typecheckexp types (Neg e1) =
   typecheckexp types (Var x) =
   typecheckexp types (LitInt i) = 
   typecheckexp types (VarArray x explist) =
   typecheckexp types (IsEq e1 e2) = 
   typecheckexp types (IsNEq e1 e2) = 
   typecheckexp types (IsGT e1 e2) = 
   typecheckexp types (IsLT e1 e2) = 
   typecheckexp types (IsGTE e1 e2) =
   typecheckexp types (IsLTE e1 e2) = 
   typecheckexp types (And e1 e2) =
   typecheckexp types (Or e1 e2) = 
   typecheckexp types (Not e) = 
   typecheckexp types (LitBool Bool) = 

   typecheckexplist :: [TypeEnv] -> [Exp] -> Bool
   typecheckexplist _ _ = True
   typecheckexplist types [x] = typecheckexp types x
   typecheckexplist types x:xs = typecheckexp types x && typecheckexplist types xs

   checkequaltype :: [TypeEnv] -> Name -> Exp -> Bool
   checkequaltype types x e = getTypeOfVar types x && getTypeOfExp types e

   getTypeOfVar :: [TypeEnv] -> Name -> Type

   getTypeOfExp :: [TypeEnv] -> Exp -> Type

また、何をチェックする必要があるのか​​ についても少し曖昧です。明らかに、変数/式を割り当てて比較する場合は、それらを同じ型にする必要があります。

どんな助けでも大歓迎です。

4

1 に答える 1

5

具体的な質問はないので、問題に関する一般的なアドバイスをいくつか提供します。

正しい軌道に乗っているようです。あなたのアプローチは正しいです。構文ツリーをたどって各部分式をチェックする必要があり、型が一致しない場合は失敗します。

typecheckexp :: [TypeEnv] -> Exp -> Bool
typecheckexp types (Add e1 e2) = 
  case (te1, te2) of
    (Just TyInt, Just TyInt) -> True
     _ -> False
  where
    te1 = getTypeOfExp e1
    te2 = getTypeOfExp e2

トップレベルでは、式レベル チェッカーをすべての式に適用し、andすべての結果をまとめて、プログラム全体として型チェックを行うかどうかを取得します。

typecheckexplist :: [TypeEnv] -> [Exp] -> Bool
typecheckexplist env stmts = and (map (typecheckexp env) stmts)

型がすべて事前に宣言されていて、AST をたどった結果として TypeEnv が変更されない場合、このアプローチは機能します。ツリーをたどって定義を構築している場合は、タイプチェッカーをState モナドでラップすることを検討してください。

明らかに、変数/式を割り当てて比較している場合、

フロントエンド言語に応じて、int a変数の明示的な型宣言 (つまり ) を追加するか、プログラムのコンテキストからそれらを推測しようとするかを決定する必要があります。これは、型推論と呼ばれる別のタスクです。ユーザーからの明示的な宣言がある場合は、変数の使用に対して指定された型を機械的にチェックし、それらが一致するかどうかを判断するだけです。derving Eqあなたのタイプはすべて単純なモノタイプなので、( ) をあなたTypeに付けてタイプ比較を取得できるので、これは簡単です。

考慮すべきもう 1 つのケースは、エラー レポートです。与えられた AST には位置情報が添付されていないため、ツリーをたどって途中で失敗した場合、何がどこで失敗したかをユーザーに伝える方法がありません。Parsec のようなパーサーからフロントエンド言語を解析している場合はExpr Pos、構文ツリーを構築するときに、各データ型 ( ) に情報をタグ付けできます。

data Expr t = Add t (Expr t) (Expr t) | ... 
data Pos = Pos { line :: Integer , col :: Integer }

使いやすさのために、Uniplate のようなジェネリック ライブラリを調べて、関数を適用し、ボイラープレートをそれほど使わずに AST をトラバースできるようにすることができます。特定のタイプのすべてのノードを抽出するための不自然な例は、次のようになります。

{-# LANGUAGE DeriveDataTypeable #-}
module Expr where

import Data.Data
import Data.Typeable
import Data.Generics.Uniplate.Data

data Expr = Val String
          | Add Expr Expr
          | Sub Expr Expr
          | Div Expr Expr
          | Mul Expr Expr
          | Neg Expr
          deriving (Show, Eq, Data, Typeable)

vars :: Expr -> [String]
vars ex = [i | Val i <- universe ex]

test :: [String]
test = vars (Add (Val "a") (Mul (Val "b") (Val "c")))
于 2013-12-03T05:49:48.483 に答える