我应该如何用附加信息表示AST注释？

Question

假设我有一种简单的数据类型,用某种语言表示AST:

data Term = Var String
          | Num Integer
          | Expr [Term]

(实际上它显然会有比这更多的构造函数.)

我可以用它来编写一个与AST结构匹配的简单评估函数:

eval :: Term -> Result
eval (Var name)   = lookup name
eval (Num n)      = return n
eval (Expr exprs) = ...

我可以使用行号等信息对AST进行注释,而无需更改模式匹配的工作方式吗？

(如果我不介意更改模式,我当然可以使用记录语法或视图模式.)

Answer 1

为什么不以多态方式表示AST

data Term term = Var String
      | Num Integer
      | Expr [term]

然后你的原始Term类型是

newtype SimplTerm = SimplTerm (Term (SimplTerm))

你可以轻松地用视图模式做你想做的事

data AtLine = AtLine (Term AtLine) Integer

view :: AtLine -> Term AtLine
view (AtLine x _) = x

eval (view -> Var name) = lookup name
eval (view -> Num n) = numResult n
eval (view -> Expr expr) = listResult (map eval expr)

或使视图多态

class AST t where
   term :: t -> Term t
instance AST SimplTemr where
   term (SimplTemr x) = x
instance AST AtLine where
   term (AtLine x _) = x

eval :: AST t => t -> Result
eval (view -> Var name) = lookup name
eval (view -> Num n) = numResult n
eval (view -> Expr expr) = listResult (map eval expr)

对于错误处理,我希望有一种方法可以让视图模式出现在monad中,但这就是生命(如果view函数是在cps中完成的,你可以这样做,因此将continuation作为参数而不是返回值).