parsing - Haskell 中针对简单语言 AST 的良好类型设计

Question

我是 Haskell 新手，正在研究 Haskell LLVM tutorial 。在其中，作者定义了一个简单的代数数据类型来表示 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 的列表在 Extern将仅包含表示变量的表达式(即这种情况下的参数不能是任意表达式)。我想让类型反射(reflect)这个约束(使得使用 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 的实例。 typeclass(没有任何方法)？或者是否有更惯用的方法(或者最好放弃这些类型并做一些完全不同的事情)？

Answer 1

免责声明，我是您提到的 LLVM 教程的作者。

只需使用外部名称[Name]，教程中第 3 章之后的所有内容都使用 exact definition无论如何。我想我只是忘记使第 2 章 Syntax.hs 与其他章节保持一致。

我不担心解析器定义是否一致，它们返回不同的类型就可以了。这是后来的解析器使用的。 identifier 只是来自 LanguageDef 的字母数字标识符的内置秒差距，该标识符成为 AST 中的 Name 类型。

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