在使用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
的不同出现,则可能很快变得笨拙。有没有人有优雅的技巧来注释嵌套数据类型?
data Exp a = Var Identifier a | ...
?这样,可以通过注释传递函数,但实际上不使用它们的函数将在a
中具有多态性,不能处理注释的函数将使用Exp()
,要注释,则需要类型为Exp()-> Exp ExtraInfo
的函数,需要额外信息的转换将使用Exp ExtraInfo
。基本上是“始终保留它”的选项,但类型检查器能够强制执行使用它的阶段。 - Ben