为我的语言记住标记位置的 AST 设计类型

Question

我为一种简单的编程语言编写了一个解析器和求值器。这是 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]

不过我不太喜欢这个。首先，它扰乱了评估者的定义，模式匹配每次都有一个额外的层。另外，我不认为说函数调用将定位值作为参数是完全正确的。函数调用应该将值作为参数，位置应该是不干扰计算器的元数据。

我需要帮助重新定义我的类型，以便解决方案尽可能干净。也许有我不知道的语言扩展或设计模式可能会有所帮助。

Answer 1

有许多种方法来注释 AST！这是所谓的 AST typing problem 的一半，另一半是如何管理在编译过程中发生变化的 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 #-}

对于您的目的来说，这可能已经足够整洁了。但这里还有一些我觉得有用的提示。

Put annotations first: 当直接在AST中添加注解类型时，我通常更喜欢把它作为每个构造函数的第一个参数，这样可以方便的部分应用。

data LocatedExpr
  = LocatedIf     Location Value [Expr]
  | LocatedVarDef Location String Value

如果注释是一个位置，那么这也使得在编写某些类型的解析器时更方便地获取，就像解析器组合库中的AnnotatedIf <$> (getSourceLocation <* ifKeyword) <*> value <*> many expr一样。

Parameterise your annotations: 我经常把注解类型做成类型参数，这样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 -> -- …

未注释的术语不是你的敌人：没有源位置的术语不利于错误报告，但我认为将模式同义词设为双向仍然是个好主意使用 unit () 注释构造未注释术语的便利性。（或者等效的东西，如果你使用例如 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 and/or Data Types à la Carte^PDF：将注释表达式树的“递归”部分与“注释”部分分开，并使用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 Grow^PDF 对于源代码位置来说有点过分了，但在一个严肃的编译器中它非常有用。如果你希望有不止一种注释类型（例如推断类型或其他分析结果）或随时间变化的 AST，那么你可以为“编译阶段”添加一个类型参数（解析，重命名，类型检查，脱糖，&c .) 和 select 字段类型或基于该索引启用和禁用构造函数。

一个 really 不幸的缺点是，即使在没有任何改变的地方，你也经常不得不重写树，因为一切都取决于“阶段”。我使用的另一种方法是为每种类型的阶段或注释添加一个类型参数 可以独立变化 ，例如data Expr annotation termVarName typeVarName，并用 type 和 pattern 同义词对其进行抽象。这使您可以独立更新索引并仍然使用类，如 Functor 和 Bitraversable。

为我的语言记住标记位置的 AST 设计类型

Type design for the AST of my language remembering token locations

haskell

abstract-syntax-tree