我应该如何表示用附加信息注释的AST？ [英] How should I represent an AST annotated with additional information?

问题描述

  data Term = Var String 
 |数字整数
 | Expr [Term] 
  

（实际上它显然会有比这更多的构造函数。）

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

  eval :: Term  - >结果
 eval（Var name）=查找名称
 eval（Num n）=返回n 
 eval（Expr exprs）= ... 
  

我可以使用行号等信息对AST进行注释，而不会改变模式匹配的工作方式吗？

（如果我不介意更改模式，当然可以使用记录语法或查看模式。）

解决方案

为什么不用多态表示AST

  data术语term = Var String 
 |数字整数
 | Expr [term] 
  

然后您的原信息字词 type是

  newtype SimplTerm = SimplTerm（Term（SimplTerm））
  

你可以很容易地用视图模式做你想做的事情

 数据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其中
 term：t  - >术语t 
实例AST SimplTemr其中
术语（SimplTemr x）= x 
实例AST AtLine其中
术语（AtLine x _）= x 
 
 eval :: AST t => t  - >结果
 eval（view  - > Var name）= lookup name 
 eval（view  - > Num n）= numResult n 
 eval（view  - > Expr expr）= listResult eval expr）
  

用于错误处理我希望有一种方法可以让视图模式出现在monad中，但那就是生活（如果 view >函数在cps中完成，并且将延续作为参数而不是返回值，则可以这样做）。

Let's say I have a simple data type representing an AST in some language:

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

(In reality it would obviously have more constructors than this.)

I can use this to write a simple evaluation function which matches against the AST structure:

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

Can I annotate the AST with information like line numbers without changing how the pattern matching works?

(If I didn't mind changing the patterns, I could use record syntax or view patterns, of course.)

解决方案

Why not represent the AST polymorphically

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

then your orignal Term type is

newtype SimplTerm = SimplTerm (Term (SimplTerm))

and you can easily do what you want with view patterns

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)

or making view polymorphic

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)

for error handling I wish there was a way to get view patterns to appear in a monad, but that is life (which you could do if the view function were done in cps and so took the continuation as an argument rather than returning a value).

这篇关于我应该如何表示用附加信息注释的AST？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！