2

在我正在编写的玩具编译器中，我想使用通用递归数据类型来表示抽象语法树（AST），可能用一些属性进行注释。

解析器为表达式构建 AST，并用源代码中的位置进行注释。

语义分析器采用带有位置注释的 AST，并生成一个 monad，该 monad 在运行时返回相应的带有类型信息注释的 AST。

语义分析器的目的是对表达式进行类型检查，报告过程中发现的任何错误。表达式的计算类型应该用作原始树中的注释，以便最后每个树节点都将使用其类型进行注释。

完全实现语义分析器后，将使用 RWS monad，因为它需要一个环境来编译 let 表达式和变量，将生成发现错误的日志，并且表达式语言中的一些新结构将需要编译状态.

在尝试编写语义分析器时，我遇到了 Haskell 类型系统的问题。以下代码演示了我遇到的问题类型：

{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}

module Lang0 where

import Prelude hiding (foldr1,mapM,exp)
import Data.Foldable (Foldable)
import Data.Traversable (Traversable)
import Control.Monad.RWS (runRWS)

newtype Fix f = In { out :: f (Fix f) }

deriving instance Show (f (Fix f)) => Show (Fix f)


data Ann x f a = Ann { attr  :: x    -- ^ the annotation
                     , unAnn :: f a  -- ^ the original functor
                     }
                 deriving (Eq,Ord,Show,Functor,Foldable,Traversable)

data Range = Range Int Int

instance Show Range where
  show (Range a b) = show a ++ "-" ++ show b

type Name = String

data BinOp
  = Add | Sub | Mul | Div
  | Eq | Ne | Gt | Ge | Lt | Le
  | Con | Dis
  deriving (Eq,Show)

data ExpF r
  = Log Bool
  | Num Double
  | Var Name
  | Neg r
  | Bin BinOp r r
  | Let Name r r
  deriving (Eq,Show,Functor,Foldable,Traversable)

data Type = NUMERIC | LOGIC deriving (Eq,Show)

newtype Exp = Exp { runExp :: Fix ExpF } deriving (Show)
newtype ExpPos = ExpPos { runExpPos :: Fix (Ann Range ExpF) } deriving (Show)
newtype ExpType = ExpType { runExpType :: Fix (Ann ExpType ExpF) } deriving (Show)

type Env = [(Name, Type)]
type Log = [(Range, String)]

semantExp :: Monad m => Fix (Ann Range ExpF) -> m (Fix (Ann Type ExpF))
semantExp (In (Ann pos exp)) =
  case exp of
    Num _ -> return (In (Ann NUMERIC exp))
    _     -> error "unimplemented"

e1 :: ExpPos
e1 = ExpPos (In (Ann (Range 1 2) (Num 8)))

main :: IO ()
main = print (runRWS (semantExp (runExpPos e1)) [] ())

当将此代码提供给 ghc 编译器时，我得到以下信息：

$ ghc --make Lang0
[1 of 1] Compiling Lang0            ( Lang0.hs, Lang0.o )

Lang0.hs:60:38:
    Couldn't match type `Range' with `Type'
    Expected type: ExpF (Fix (Ann Type ExpF))
      Actual type: ExpF (Fix (Ann Range ExpF))
    In the second argument of `Ann', namely `exp'
    In the first argument of `In', namely `(Ann NUMERIC exp)'
    In the first argument of `return', namely `(In (Ann NUMERIC exp))'

为什么编译器希望参数中的注释和结果 AST 的类型相同？

有关如何解决此问题的任何线索？

附加观察：如果没有 的类型注释semantExp，编译器会为其推断以下类型：

semantExp
  :: Monad m => Fix (Ann Type ExpF) -> m (Fix (Ann Type ExpF))

为什么推断的类型在结果单子的参数中具有相同的注释类型？

4

1 回答 1

4

所以你有这个古老的术语，到处都有范围注释。你破坏它，它给你一个名为的范围注释pos和一个名为exp. 你扔掉pos它并用类型注释替换它，这是值得称赞的，但随后大胆地声称exp用类型注释。但这显然不是真的——你必须遍历整个子术语并撕掉所有旧的注释才能让它成为！

错误也说明了这一点，但它的语言枯燥乏味。

于 2013-09-12T23:48:46.187 回答