Haskell中用于简单语言的AST的良好类型设计

Question

我是Haskell的新手,正在研究Haskell LLVM教程.在其中,作者定义了一个简单的代数数据类型来表示AST.

type Name = String

data Expr
  = Float Double
  | BinOp Op Expr Expr
  | Var String
  | Call Name [Expr]
  | Function Name [Expr] Expr
  | Extern Name [Expr]
  deriving (Eq, Ord, Show)

data Op
  = Plus
  | Minus
  | Times
  | Divide
  deriving (Eq, Ord, Show)

但是,这不是一个理想的结构,因为解析器实际上期望Expr一个Externwill 中的列表只包含表示变量的表达式(即在这种情况下的参数不能是任意表达式).我想让类型反映这个约束(使用QuickCheck更容易生成随机有效的AST); 但是,为了解析器函数(所有类型都有Parser Expr)的一致性,我不只是想说| Expr Name [Name].我想做这样的事情:

data Expr
  = ...
  | Var String
    ...
  | Function Name [Expr] Expr
  | Extern Name [Var] -- enforce constraint here
  deriving (Eq, Ord, Show)

但这在Haskell中是不可能的.

总结一下,Extern并且Var应该都是Expr,并且Extern应该有一个Vars表示参数的列表.最好的方法是将所有这些分开并使它们成为Expr类型类的实例(没有任何方法)？或者是否有更惯用的方法(或者更好地废弃这些类型并做一些完全不同的事情)？

Answer 1

免责声明,我是您提到的LLVM教程的作者.

只需使用Extern Name [Name],教程中第3章之后的所有内容都会使用该确切的定义.我想我只是忘了让第2章Syntax.hs与其他人保持一致.

我不担心使解析器定义一致,它们可以返回不同的类型.这是后来解析器使用的内容.identifier只是来自LanguageDef的字母数字标识符的parsec内置,它成为NameAST中的类型.

extern :: Parser Expr
extern = do
  reserved "extern"
  name <- identifier
  args <- parens $ many identifier
  return $ Extern name args