Haskell中的Monadic类型检查器
我正在从BNFC开始编写一个解析器和Haskell中的类型检查器。 类型检查器的主要功能实现如下：
typecheck :: Program -> Err ()
typecheck (PDefs ds) = do
env <- foldM (env (DFun typ id args _ _) ->
updateFun env id (argTypes args,typ) ) (emptyEnv) (ds)
mapM_ (checkDef env) ds
where argTypes = map ((ADecl _ typ _) -> typ)
其中PDefs ， DFun和ADecl是语言的抽象语法中定义的代数数据类型的构造者， checkDef和updateFun是函数。 Program是语法的“起点”。 monad使用的是monad Err ：
data Err a = Ok a | Bad String
deriving (Read, Show, Eq, Ord)
instance Monad Err where
return = Ok
fail = Bad
Ok a >>= f = f a
Bad s >>= f = Bad s
typechecker函数在“main”模块中调用（类型检查之前有词法分析和sintax分析）：
check :: String -> IO ()
check s = do
case pProgram (myLexer s) of
Bad err -> do
putStrLn "SYNTAX ERROR"
putStrLn err
exitFailure
Ok tree -> do
case typecheck tree of
Bad err -> do
putStrLn "TYPE ERROR"
putStrLn err
exitFailure
Ok _ -> do
putStrLn "nParsing e checking ok!"
showTree tree
（ tree是解析器构建的抽象语法树）
如果在作为输入传递的程序中存在类型错误，类型检查器将返回一个错误，指出错误并且不会继续。 有没有办法允许类型检查器在单次执行中列出输入中的所有错误？
正如@ mb14的评论大部分所涵盖的，通常的方法涉及两件事情：
Writer monad很容易完成。 在这个简单的方案中，类型检查总是返回一个类型树。 如果错误消息的日志为空，则类型检查已成功，并且类型树有效。 否则，对于给定的一组错误，类型检查失败，并且可以放弃输入的树。 在更复杂的方案中，您可以区分日志中的警告和错误，并且如果类型检查包含零个或多个警告但没有错误，则认为类型检查已成功。
我已经在下面介绍了一个非常简化的语法的完整示例。 它只返回顶层类型而不是类型树，但这只是为了简化代码 - 返回类型检查树并不困难。 将它应用到语法中的难点在于确定如何在发生错误时开拓前进（即提供哪种有效类型），并且它将高度依赖于程序的细节。 一些常规技术如下所示：
Len ），那么即使该节点没有进行类型检查，也总是假定该节点的类型。 Plus或BNF交替），那么当检测到类型不兼容时，根据其第一个参数的类型确定节点的类型。 无论如何，这里是完整的例子：
import Control.Monad.Writer
-- grammar annotated with node ids ("line numbers")
type ID = String
data Exp = Num ID Double -- numeric literal
| Str ID String -- string literal
| Len ID Exp -- length of a string expression
| Plus ID Exp Exp -- sum of two numeric expressions
-- or concat of two strings
-- expression types
data Type = NumT | StrT deriving (Show, Eq)
-- Expressions:
-- exp1 = 1 + len ("abc" + "def")
-- exp2 = "abc" + len (3 + "def")
-- annotated with node ids
exp1, exp2 :: Exp
exp1 = Plus "T1" (Num "T2" 1)
(Len "T3" (Plus "T4" (Str "T5" "abc")
(Str "T6" "def")))
exp2 = Plus "T1" (Str "T2" "abc")
(Len "T3" (Plus "T4" (Num "T5" 3)
(Str "T6" "def")))
-- type check an expression
data Error = Error ID String deriving (Show)
type TC = Writer [Error]
typeCheck :: Exp -> TC Type
typeCheck (Num _ _) = return NumT
typeCheck (Str _ _) = return StrT
typeCheck (Len i e) = do
t <- typeCheck e
when (t /= StrT) $
tell [Error i ("Len: applied to bad type " ++ show t)]
return NumT -- whether error or not, assume NumT
typeCheck (Plus i d e) = do
s <- typeCheck d
t <- typeCheck e
when (s /= t) $
tell [Error i ("Plus: incompatible types "
++ show s ++ " and " ++ show t
++ ", assuming " ++ show s ++ " result")]
return s -- in case of error assume type of first arg
compile :: String -> Exp -> IO ()
compile progname e = do
putStrLn $ "Running type check on " ++ progname ++ "..."
let (t, errs) = runWriter (typeCheck e)
case errs of
[] -> putStrLn ("Success! Program has type " ++ show t)
_ -> putStr ("Errors:n" ++
unlines (map fmt errs) ++ "Type check failed.n")
where fmt (Error i s) = " in term " ++ i ++ ", " ++ s
main :: IO ()
main = do compile "exp1" exp1
compile "exp2" exp2
它生成输出：
Running type check on exp1...
Success! Program has type NumT
Running type check on exp2...
Errors:
in term T4, Plus: incompatible types NumT and StrT, assuming NumT result
in term T3, Len: applied to bad type NumT
in term T1, Plus: incompatible types StrT and NumT, assuming StrT result
Type check failed.
上一篇: Monadic type checker in Haskell
下一篇: Is a state monad with two state variable types (in and out) still a monad?