我为一种简单的编程语言编写了一个解析器和计算器。以下是AST:类型的简化版本
data Value = IntV Int | FloatV Float | BoolV Bool
data Expr = IfE Value [Expr] | VarDefE String Value
type Program = [Expr]
我希望错误消息告诉发生错误的源代码的行和列。例如,如果If
表达式中的值不是布尔值,我希望计算器显示一个错误,即"expected boolean at line x, column y"
,其中x
和y
指的是值的位置。
所以,我需要做的是重新定义以前的类型,这样它们就可以存储不同事物的相关位置。一种选择是为表达式的每个构造函数添加一个位置,如下所示:
type Location = (Int, Int)
data Expr = IfE Value [Expr] Location | VarDef String Value Location
这显然不是最优的,因为我必须将这些Location
字段添加到每个可能的表达式中,例如,如果一个值包含其他值,我也需要将位置添加到该值中:
{-
this would turn into FunctionCall String [Value] [Location],
with one location for each value in the function call
-}
data Value = ... | FunctionCall String [Value]
我想出了另一个解决方案,它允许我在所有内容中添加位置:
data Located a = Located Location a
type LocatedExpr = Located Expr
type LocatedValue = Located Value
data Value = IntV Int | FloatV Float | BoolV Bool | FunctionCall String [LocatedValue]
data Expr = IfE LocatedValue [LocatedExpr] | VarDef String LocatedValue
data Program = [LocatedExpr]
不过我不太喜欢这个。首先,它混淆了评估器的定义,并且模式匹配每次都有一个额外的层。此外,我不认为函数调用将定位值作为参数是正确的。函数调用应该将值作为参数,位置应该是不会干扰计算器的元数据。
我需要帮助重新定义我的类型,以便解决方案尽可能干净。也许有一个我不知道的语言扩展或设计模式可能会有所帮助。
有许多方法可以注释AST!这是AST类型问题的一半,另一半是如何管理在编译过程中发生变化的AST。这个问题并没有完全"解决":所有的解决方案都有权衡,选择哪一个取决于您的预期用例。我会在最后介绍一些你可能想调查的内容。
无论您选择哪种方法来组织实际的数据类型,如果它使模式匹配变得丑陋或笨拙,那么自然的解决方案就是PatternSynonyms
。
考虑你的第一个例子:
{-# Language PatternSynonyms #-}
type Location = (Int, Int)
data Expr
= LocatedIf Value [Expr] Location
| LocatedVarDef String Value Location
-- Unidirectional pattern synonyms which ignore the location:
pattern If :: Value -> [Expr] -> Expr
pattern If val exprs <- LocatedIf val exprs _loc
pattern VarDef :: String -> Value -> Expr
pattern VarDef name expr <- LocatedVarDef name expr _loc
-- Inform GHC that matching ‘If’ and ‘VarDef’ is just as good
-- as matching ‘LocatedIf’ and ‘LocatedVarDef’.
{-# Complete If, VarDef #-}
这可能已经足够整洁了。但这里还有一些我觉得有用的提示。
将注释放在第一位:当直接向AST添加注释类型时,我通常更喜欢将其作为每个构造函数的第一个参数,这样就可以方便地部分应用它。
data LocatedExpr
= LocatedIf Location Value [Expr]
| LocatedVarDef Location String Value
如果注释是一个位置,那么这也使得在编写某些类型的解析器时更方便地获得,就像解析器组合子库中的AnnotatedIf <$> (getSourceLocation <* ifKeyword) <*> value <*> many expr
一样。
参数化你的注释:我经常把注释类型变成类型参数,这样GHC就可以派生出一些有用的类:
{-# Language
DeriveFoldable,
DeriveFunctor,
DeriveTraversable #-}
data AnnotatedExpr a
= AnnotatedIf a Value [Expr]
| AnnotatedVarDef a String Value
deriving (Functor, Foldable, Traversable)
type LocatedExpr = AnnotatedExpr Location
-- Get the annotation of an expression.
-- (Total as long as every constructor is annotated.)
exprAnnotation :: AnnotatedExpr a -> a
exprAnnotation = head
-- Update annotations purely.
mapAnnotations
:: (a -> b)
-> AnnotatedExpr a -> AnnotatedExpr b
mapAnnotations = fmap
-- traverse, foldMap, &c.
如果您想要"不干扰",请使用多态性:您可以强制评估器不能通过对注释类型进行多态性检查。模式同义词仍然可以方便地匹配这些表达式:
pattern If :: Value -> [AnnotatedExpr a] -> AnnotatedExpr a
pattern If val exprs <- AnnotatedIf _anno val exprs
-- …
eval :: AnnotatedExpr a -> Value
eval expr = case expr of
If val exprs -> -- …
VarDef name expr -> -- …
未注释的术语不是你的敌人:一个没有源位置的术语不适合错误报告,但我认为让模式同义词双向仍然是一个好主意,以方便用单元()
注释构建未注释的词汇。(或者类似的东西,如果你使用例如Maybe Location
作为注释类型。)
原因是这对于编写单元测试非常方便,在单元测试中,您希望检查输出,但希望使用Eq
而不是模式匹配,并且不希望必须比较测试中与它们无关的所有源位置。使用派生类,void :: (Functor f) => f a -> f ()
去掉AST上的所有注释。
import Control.Monad (void)
type BareExpr = AnnotatedExpr ()
-- One way to define bidirectional synonyms, so e.g.
-- ‘If’ can be used as either a pattern or a constructor.
pattern If :: Value -> [BareExpr] -> BareExpr
pattern If val exprs = AnnotatedIf () val exprs
-- …
stripAnnotations :: AnnotatedExpr a -> BareExpr
stripAnnotations = void
等效地,您可以使用GADTs
/ExistentialQuantification
来表示data AnyExpr where { AnyExpr :: AnnotatedExpr a -> AnyExpr }
/data AnyExpr = forall a. AnyExpr (AnnotatedExpr a)
;这样,注释的信息与()
的信息一样多,但您不需要用void
在整个树上fmap
来剥离它,只需应用AnyExpr
构造函数来隐藏类型即可。
最后,这里简要介绍了一些AST打字解决方案。
用标签(例如唯一ID)注释每个AST节点,然后从AST:中单独存储所有元数据,如源位置、类型等
import Data.IntMap (IntMap) -- More sophisticated/stronglier-typed tags are possible. newtype Tag = Tag Int newtype TagMap a = TagMap (IntMap a) data Expr = If !Tag Value [Expr] | VarDef !Tag String Expr type Span = (Location, Location) type SourceMap = TagMap Span type CommentMap = TagMap (Span, String) parse :: String -- Input -> Either ParseError ( Expr -- Parsed expression , SourceMap -- Source locations of tags , CommentMap -- Sideband for comments -- … )
其优点是,您可以非常容易地在任何地方混合任意新类型的注释,而不会影响AST本身,并避免仅仅为了更改注释而重写AST。您可以将树和注释表视为一种数据库,其中的标记是与它们相关的"外键"。缺点是,当重写AST时,必须小心维护这些标签。
我不知道这种方法是否有一个既定的名称;我认为它只是"标记"或"标记AST"。
recursion-schemes
和/或数据类型àla CartePDF:将带注释的表达式树的"递归"部分与"注释"部分分离,并使用Fix
将它们重新绑定在一起,Compose
(或Cofree
)将添加注释"在中间"。data ExprF e = IfF Value [e] | VarDefF String e -- … deriving (Foldable, Functor, Traversable, …) -- Unannotated: Expr ~ ExprF (ExprF (ExprF (…))) type Expr = Fix ExprF -- With a location at each recursive step: -- -- LocatedExpr ~ Located (ExprF (Located (ExprF (…)))) type LocatedExpr = Fix (Compose Located ExprF) data Located a = Located Location a deriving (Foldable, Functor, Traversable, …) -- or: type Located = (,) Location
一个明显的优势是,你可以免费获得一堆不错的遍历内容,比如
cata
,这样你就可以避免在AST上一遍又一遍地编写手动遍历。缺点是,它会添加一些模式混乱来清理,就像"点菜"方法一样,但它们确实提供了很大的灵活性。Trees That GrowPDF对于源位置来说过于夸张,但在一个严肃的编译器中,它非常有用。如果您希望有多个注释类型(如推断类型或其他分析结果)或一个随时间变化的AST,那么您可以为"编译阶段"添加一个类型参数(已解析、已重命名、已类型检查、已取消标记等),并选择字段类型或启用&禁用基于该索引的构造函数。
一个真正不幸的缺点是,即使在什么都没有改变的地方,你也经常不得不重写树,因为一切都取决于"阶段"。我使用的另一种选择是为每种类型的阶段或注释添加一个类型参数,它们可以独立地变化,例如
data Expr annotation termVarName typeVarName
,并使用type
和pattern
同义词对其进行抽象。这允许您独立更新索引,并且仍然使用Functor
和Bitraversable
之类的类。