纯函数式编译器如何使用类型信息注释 AST？

Question

在语法分析阶段，命令式编译器可以从已经包含 type 字段的节点构建 AST，该字段在构造期间设置为 null，然后在语义中分析阶段，通过将 declared/inferred 类型分配到 type 字段来填写类型。

纯函数式语言如何处理这个问题，而您没有赋值的奢侈？无类型 AST 是否映射到不同的种类类型丰富的 AST？这是否意味着我需要为每个 AST 节点定义两种类型，一种用于语法阶段，一种用于语义阶段？

是否有纯函数式编程技巧可以帮助编译器编写者解决这个问题？

Answer 1

有几个选项可以对此进行建模。您可以使用与命令式情况相同的可空数据字段：

data Exp = Var Name (Maybe Type) | ...
parse :: String -> Maybe Exp     -- types are Nothings here
typeCheck :: Exp -> Maybe Exp    -- turns Nothings into Justs

甚至，使用更精确的类型

data Exp ty = Var Name ty | ...
parse :: String -> Maybe (Exp ())
typeCheck :: Exp () -> Maybe (Exp Type)

Answer 2

我通常将源代码（或已经降低的几个步骤）AST 重写为新形式，用一对 (tag, expression) 替换每个 expression 节点。

标签是唯一的数字或符号，然后由下一次从 AST 派生类型方程式使用。例如，a + b 会产生类似于 { numeric(Tag_a). numeric(Tag_b). equals(Tag_a, Tag_b). equals(Tag_e, Tag_a).}.

然后求解类型方程（例如，简单地运行它们作为 Prolog 程序），如果成功，所有标签（在这个程序中是变量）现在都绑定到具体类型，如果不是，它们将保留为类型参数。

在下一步中，我们之前的 AST 再次被重写，这次用所有推断的类型信息替换标签。

整个过程是一系列纯重写，不需要破坏性地替换 AST 中的任何内容。一个典型的编译管道可能需要几十次重写，其中一些会改变 AST 数据类型。

Answer 3

我不能说应该如何完成，但我确实在 F# 中为 C# 编译器做了这个 here

该方法基本上是 - 从源构建 AST，使类型信息不受约束 - 所以 AST.fs 基本上是 AST，其中包含类型名称、函数名称等的字符串。

随着 AST 开始被编译为（在本例中）.NET IL，我们最终得到更多的类型信息（我们在源代码中创建类型——让我们称之为类型存根）。然后，这为我们提供了创建方法存根所需的信息（代码可能具有包括类型存根和内置类型的签名）。从这里我们现在有足够的类型信息来解析代码中的任何类型名称或方法签名。

我将其存储在 TypedAST.fs 文件中。我一次完成此操作，但该方法可能很幼稚。

现在我们有了一个完全类型化的 AST，您可以对它进行编译、完全分析或任何您喜欢的操作。

所以在回答问题“这是否意味着我需要为每个 AST 节点定义两种类型，一种用于语法阶段，一种用于语义阶段？”，我不能肯定地说是这种情况，但这确实是我所做的，而且它似乎是 MS 对 Roslyn 所做的（尽管他们基本上用类型信息 IIRC 装饰了原始树）

"是否有纯函数式编程技巧可以帮助编译器编写者解决这个问题？" 鉴于 AST 在我的案例中基本上是镜像的，因此可以使其通用并转换树，但代码可能最终（更多）可怕。

即

type 'type AST;
| MethodInvoke of 'type * Name * 'type list
| ....

Answer 4

就像处理关系数据库的情况一样，在函数式编程中，最好不要将所有内容都放在一个数据结构中。

特别是，可能没有"the AST"的数据结构。

很可能会有表示已解析表达式的数据结构。处理类型信息的一种可能方法是在解析期间为树的每个节点分配一个唯一标识符（如整数），并具有一些合适的数据结构（如哈希映射）将这些节点 ID 与类型相关联。那么，类型推断过程的工作就是创建这个映射。

纯函数式编译器如何使用类型信息注释 AST？

How do purely functional compilers annotate the AST with type info?

compiler-construction

f#

haskell

functional-programming

scala