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)

其中PDefsDFunADecl是语言的抽象语法中定义的代数数据类型的构造者, checkDefupdateFun是函数。 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.
    
    链接地址: http://www.djcxy.com/p/42919.html

    上一篇: Monadic type checker in Haskell

    下一篇: Is a state monad with two state variable types (in and out) still a monad?