基于查询的编译器体系结构

注意：这是一篇来自Sixten编程语言文档的老帖子，我对它进行了润色和充实。在写完之后，我发现了Salsa，这是一个与我的Rock库有着非常相似目标的Rust库，它也绝对值得一看！

编译器不再仅仅是获取一堆源文件并产生汇编代码的黑匣子。我们期望他们：

是增量的，这意味着如果我们在做了一些更改之后重新编译一个项目，我们只会重新编译受更改影响的内容。

提供编辑器工具，例如通过语言服务器，支持转到定义、查找特定位置的表达式类型以及动态显示错误消息等功能。

这就是Anders Hejlsberg在他关于现代编译器构建的视频中谈到的，你们中的一些人可能已经看到了。

在这篇文章中，我将介绍如何在Sixten中通过围绕查询系统构建编译器来实现这一点。

对于那些不知道的人来说，Sixten是一种实验性的函数式编程语言，创建它的目的是让程序员比传统语言更好地控制内存布局和装箱。Sixten的最新开发是在Sixty存储库中完成的，并且完全是基于查询的。下面是一个小视频，让您体验一下它的语言服务器可以做些什么，其中显示了基于类型的完成：

+-++|源文本|-解析->；|AST|-类型检查-+->；|核心AST|--生成->；|ASSEMBLY|^|+-++-+|+-++-|读写类型|v+-+||类型表|+-+

有许多变化，通常比插图中的步骤和中间表示法更多，但想法保持不变：

我们沿着管道向下推送源文本，并运行一组固定的转换，直到最终输出汇编代码或其他目标语言。在此过程中，我们经常需要阅读和更新一些状态。例如，我们可以在类型检查期间更新类型表，以便稍后可以查找代码引用的实体类型。

我们中的许多人可能对传统的编译器流水线非常熟悉，但是基于查询的编译器应该如何构建可能不是那么广为人知。在这里，我将描述一种方法来做到这一点。

如何才能获得限定名称的类型，如"；Data.List.map"；？在基于管道的体系结构中，我们只需在类型表中查找它。对于问题，我们必须以不同的方式思考。我们不再依赖于更新某个状态，而是将其视为从头开始。

作为第一次迭代，我们完全从头开始。它可能看起来有点像这样：

fetchType：：QualifiedName->；IO类型fetchType(QualifiedName模块名称)=do文件名<；-module eFileName模块名称源代码<；-readFile文件名parsedModule<；-parseModule源代码解析模块<；-solveNames parsedModule let定义=查找名称解析模块推断DefinitionType定义。

我们首先找出名称来自哪个文件，可能是Data.List的data/List.vix，然后读取文件内容，解析它，也许我们进行名称解析以找出代码中的名称在给定导入内容的情况下引用了什么，最后我们查找名称解析的定义并键入check，返回它的类型。

这一切仅仅是为了获取标识符的类型吗？这似乎很荒谬，因为在模块的类型检查过程中，查找名称的类型是我们会做很多次的事情。幸运的是，我们还没有做完。

fetchParsedModule：：ModuleName->；IO ParsedModule fetchParsedModule module eName=do filename<；-module eFileName module eName sourceCode<；-readFile filename parseModule module name fetchResolvedModule：：ModuleName->；IO ResolvedModule fetchResolvedModule fetchResolvedModule module eName=do parsedModule<；-fetchParsedModule modeName：：ModuleName->；IO ResolvedModule fetchResolvedModule module eName=do parsedModule<；-fetchParsedModule module。

请注意，每个函数都是自己从头开始做所有事情的，也就是说，它们每个都在做流水线中要做的工作的前缀(越来越长)。我发现这是我的基于查询的编译器中的一种常见模式。

提高效率的一种方法是在每个函数周围添加一个记忆层。这样，当我们第一次使用特定参数调用函数时，我们会做一些代价高昂的工作，但后续调用的代价很低，因为它们可以返回缓存的结果。

这基本上就是我们要做的，但是我们不会为每个函数使用单独的缓存，而是有一个由查询索引的中央缓存。此功能由Rock提供，Rock是一个将一些功能打包以创建基于查询的编译器的库。

Rock是一个实验性的图书馆，灵感主要来自Shake和点菜纸上的构建系统。它实质上实现了构建系统框架，如make。

构建系统与现代编译器有很多共同之处，因为我们希望它们是增量的，也就是说，在重新构建时只需很少的更改就可以利用以前的构建结果。但也有一个不同之处：大多数构建系统并不关心它们的查询类型，因为它们在文件和文件系统级别上工作。

按单方式构建系统更接近我们想要的。在那里，用户编写了一系列计算、任务，为键选择合适的类型，为值选择类型。这些任务是假定它们在这样的环境中运行的：存在Key->Task Value类型的函数获取，其中Task是用于描述构建系统规则的类型，可用于获取具有特定键的依赖项的值。在上面的示例中，密钥类型可能如下所示：

构建系统可以控制我们执行FETCH时运行的代码，因此通过变化，它可以执行细粒度的依赖项跟踪、记忆和增量更新。

按菜单构建系统也是关于探索当我们改变允许Task做什么时，我们会得到什么样的构建系统，例如它是Monad还是Applicative。在Rock，我们没有探索这一点，所以我们的任务是IO之上的一层薄薄的东西。

然而，现在出现的一个问题是，没有令人满意的价值类型。我们希望FETCH(ParsedModuleKey"；Data.List"；)返回ParsedModule，而FETCH(TypeKey"；Data.List.map"；)应该返回类型为Type的内容。

ROCK允许我们根据查询的返回类型来索引键类型。我们运行示例中的键类型变为以下GADT：

数据键a其中ParsedModuleKey：：ModuleName->；密钥解析模块ResolvedModuleKey：：ModuleName->；密钥解析模块TypeKey：：QualifiedName->；密钥类型。

FETCH函数获取所有a.Key a->；任务a的类型，因此我们在运行FETCH(ParsedModuleKey"；Data.List"；)时会获得一个ParsedModule，这是我们想要的，因为返回类型取决于我们使用的键。

现在我们知道了Fetch应该是什么样子，更具体地说，它也值得透露一下Rock中的任务类型是什么样子。如前所述，它是IO周围的一层薄层，提供了一种获取密钥(如上面的密钥)的方法：

Newtype Task Key a=Task{unTask：：ReaderT(Fetch Key)IO a}Newtype Fetch Key=Fetch(for All a.。键a->；IO a)。

然后，我们编译器的规则(即其Makefile)变成以下函数，重用上面的函数：

规则：：key a->；Task a Rules Key=Case Key of ParsedModuleKey模块名称->；fetchParsedModule模块名称ResolvedModuleKey模块名称->；fetchResolvedModule ModeName TypeKey QualifiedName->；fetchType QualifiedName。

在Rock中运行Task的最基本方式是在Task获取密钥时直接调用规则函数。这会导致效率低下的构建系统从头开始重新计算每个查询。

但是Rock库允许我们在我们的规则函数上添加更多的功能，我们可以添加的一件事就是备忘录。如果我们这样做，Rock通过将已经执行的读取的键-值对存储在依赖的哈希图中来缓存每个提取的键的结果。这样，在编译器的一次运行期间，我们最多执行一次每个查询。

可以分层到规则功能上的另一种功能是增量更新。当它被使用时，Rock会跟踪任务在表中执行时使用的依赖项(很像Shake)，例如它获取了哪些键以及值是什么。使用此信息，即使依赖关系图的其他部分可能发生更改，它也能够确定何时可以安全地重用编译器上一次运行的缓存。

此细粒度依赖项跟踪还允许在任务的依赖项以不起作用的方式更改时重用缓存。例如，空格更改可能会触发重新解析，但由于AST是相同的，因此可以在依赖于解析结果的查询中重用缓存。

对于像语言服务器这样的实时工具来说，验证依赖关系可能太慢了，因为必须遍历依赖关系图的大部分，才能检查它的大部分即使是很小的更改也是不变的。

例如，如果我们对具有许多大型导入的源文件进行更改，则需要遍历所有导入的依赖关系树，以便更新该单个文件的编辑器状态。这是因为依赖关系验证本身需要一直遍历到给定查询的所有依赖关系的根查询，这通常会占整个依赖关系树的很大比例。

要解决这个问题，还可以让Rock跟踪查询之间的反向依赖关系。例如，当语言服务器检测到单个文件已经改变时，通过从改变的文件开始遍历反向依赖关系，使用反向依赖关系树来使高速缓存仅对于依赖于该文件的查询无效。

由于导入的模块不依赖于该文件，因此它们不需要重新检查，从而使工具制作更快了！？

大多数现代语言都需要一种工具策略，在我看来，围绕查询系统构建编译器似乎是一种非常有前途的方法。

使用查询，编译器编写器不必处理对一组特别缓存的更新和失效，这可能是向传统编译器流水线添加增量更新时的结果。在基于查询的系统中，它都是一劳永逸地集中处理，这意味着出错的可能性较小。

查询是极好的工具，因为它们允许我们随时询问任何查询的值，而无需担心顺序或时间影响，就像编写良好的Makefile一样。系统将以增量方式自动计算或检索查询及其依赖项的缓存值。

基于查询的编译器也非常容易并行化。由于我们被允许在任何时候进行任何查询，而且它们在第一次重新运行时都会被记住，所以我们可以不需要考虑太多就可以并行地发出查询。在Sixty中，默认行为是并行检查所有输入模块的类型。

最后，我希望这篇文章能启发您使用基于查询的编译器体系结构，并让您了解如何做到这一点。