在Haskell中使用附加数据注释嵌套ADT

Question

在使用Haskell编写编译器时，我多次遇到了处理嵌套数据类型的问题。通常我会定义一个类似于以下的抽象数据类型：

data AST = AST [GlobalDecl]

data GlobalDecl = Func Type Identifier [Stmt] | ...

data Stmt = Assign Identifier Exp | ...

data Exp = Var Identifier | ...

在对AST进行某些转换时，我可能希望在表达式中使用的变量中暂时携带一些额外的数据。到目前为止，我考虑过的所有选项似乎都相当笨拙。我可以创建一个新的数据类型：

data Exp' = Var' Identifier ExtraInfo | ...

但这意味着我需要一个新的定义 Stmt',GDecl'，以便形成稍微改变的 AST'。另一个选项是向原始的 Exp 添加另一个数据构造函数，但仅在程序的那一特定部分中使用它。

data Exp = Var Identifier | Var' Identifier ExtraInfo | ...

如果您这样做，类型检查器就无法防止您错误地在程序的其他部分中使用Var'了。

第三种选择是始终保留额外的信息，即使它对程序的其余部分没有影响：

data Exp = Var Identifier ExtraInfo | ...

可做，但不太美观，特别是如果您只需要简要的额外信息。目前我已经将额外信息放在Map Indentifier ExtraInfo中，并将其与AST一起传递，无论是明确地还是通过状态单子隐式地进行。如果您需要用不同的信息注释相同的Identifier的不同出现，则可能很快变得笨拙。

有没有人有优雅的技巧来注释嵌套数据类型？

- John G

---

也许可以尝试使用 data Exp a = Var Identifier a | ...？这样，可以通过注释传递函数，但实际上不使用它们的函数将在 a 中具有多态性，不能处理注释的函数将使用 Exp（），要注释，则需要类型为 Exp（）-> Exp ExtraInfo 的函数，需要额外信息的转换将使用 Exp ExtraInfo。基本上是“始终保留它”的选项，但类型检查器能够强制执行使用它的阶段。 - Ben

Answer 1

一个将结构与额外数据标记的选项是使用高级类型参数。如果您只需要标记变量，可以使用以下方法：

data AST f = AST [GlobalDecl f]
data GlobalDecl f = Func Type Identifier [Stmt f] | ...
data Stmt = Assign Identifier (Exp f) | ...
data Exp f = Var (f Identifier) | ...

这类似于Peter所建议的，但是它只将你想要改变的部分参数化，而不是使类型完全通用。

使用AST Identity可以获得原始未标记的结构，或者您可以使用AST ((,) ExtraInfo)这样的类型，它会将Var (f Identifier)转换为Var (ExtraInfo, Identifier)。

如果您需要在AST的每个级别上标记一些额外信息（例如令牌位置），甚至可以定义数据类型为：

data AST f = AST [f (GlobalDecl f)]
data GlobalDecl f = Func (f (Type f)) (f (Identifier f)) [f (Stmt f)] | ...
data Stmt f = Assign (f (Identifier f)) (f (Exp f)) | ...
data Exp f = Var (f (Identifier f)) | ...

现在，AST((,) ExtraInfo) 将在语法树的每个分支点包含额外的信息（尽管使用上述结构会变得有些繁琐）。

- shang

---

嗯...这是可行的。虽然，正如你所说，随着事情的深度嵌套，它很快就会变得尴尬。我喜欢它可以强制执行哪些函数允许接受增强类型的功能。 - John G

Answer 2

如果您将所有类型都更加多态化，就像这样：

data AST a = AST a
data GlobalDecl t i s = Func t i [s] | ...
data Stmt i e = Assign i e | ...
data Exp a = Var a | ...

如果需要，在中间计算过程中，您可以使用元组（例如Exp（Int，Identifier））暂时实例化它们。如果方便的话，您还可以使用newtype来表示上述具体类型。

- Peter Hall