将类型检查器干净地转换为 AST 注释器

Question

我正在以函数式风格编写编译器。类型检查器目前相当简单：它（大部分）只是一个函数 from Exprto Type。

现在，我想在工作流中添加一个步骤，为后续阶段保留类型信息。有很多方法可以做到这一点（符号表等），但一个简单的方法是将其转换为一个看起来像 AST 但包含类型信息的 IR。例如，如果 AST 数据类型是：

datatype Expr = Literal of int
              | Add of Expr * Expr
              | ...

然后键入的 IR 将是：

type TExpr = Type * TExpr'
datatype TExpr' = TLiteral of int
                | TAdd of TExpr * TExpr
                | ...

所以我现在的目标是将我的类型检查器转换为类型注释器：一个函数Expr -> TExpr而不是Expr -> Type. 这是我的问题：如果不向类型检查器功能添加一堆样板混乱，您将如何做到这一点？

天真地，我需要到处添加包装和解包代码，破坏了类型检查器功能的简单易读性。也就是说，Add类型检查器中的情况目前看起来像：

let lhs_t = check lhs in
let rhs_t = check rhs in
case (lhs_t, rhs_t) of
  (Int, Int) => Int
| (_, _) => Error

漂亮干净！完全符合形式主义中的打字判断！??

如果我用额外的翻译逻辑来处理类型检查器，它看起来像这样（现在check有 type Expr -> TExpr）：

(* Recursive calls to translate the children. *)
let lhs_typed = check lhs in
let rhs_typed = check rhs in
(* We don't care about the expression for checking, just the resulting
 * type. So extract that from each child. *)
let lhs_t, _ = lhs_typed in
let rhs_t, _ = rhs_typed in
case (Int, Int) =>
  (* Construct a TExpr with the new type. *)
  (Int, TAdd (lhs_typed, rhs_typed))
| (_, _) => Error

这令人不快地将有趣的类型检查逻辑与用于破坏和构造的枯燥样板混合在一起TExpr。

有没有办法分离这些组件？也就是说，类型检查逻辑是否可以存在于一个递归函数中，而翻译机器充当它的外部客户端？如果您愿意的话，如果无需翻译就可以轻松运行类型检查器，则可以加分。

---

附加上下文：这遵循Edward Z. Yang 在“The AST Typing Problem”上的帖子中的“Separate IR”选项。我已经考虑过将通用编程作为废样板，但不能完全适应这种情况。关于 SO 的相关但不同的问题：

• 纯函数式编译器如何用类型信息注释 AST？
• 我应该如何表示带有附加信息注释的 AST？