一句话：从 Statix 类型系统规范自动派生增量类型检查器，借助作用域图查询依赖只重分析受影响单元。
IDE 需要快速的分析响应时间，增量类型检查是可扩展的解决途径，但现有技术难以跨语言复用，且类型检查中的互递归与动态依赖使传统增量方法失效。本文提出一种技术，从用 Statix 元 DSL 书写的类型系统规范自动派生增量类型检查器。其核心是利用作用域图（Statix 内嵌的通用名字绑定模型）中的名字解析查询来推导编译单元之间的依赖；一个新的查询确认算法（query confirmation）找出因程序编辑而答案发生变化的查询，只有包含此类查询的单元需要重新分析。为提升算法效率，作者将类型检查任务拆分为上下文无关与上下文相关两部分，并复用通用机制来解析相互依赖。由此，任何 Statix 规范都能自动获得增量类型检查器。评估显示，相对于非增量的并行执行，在合成基准上取得最高 147 倍加速，在真实项目中最高 21 倍，初始开销低于 10%。
Fast analysis response times in IDEs are essential for a good editor experience. Incremental type-checking can provide that in a scalable fashion. However, existing techniques are not reusable between languages. Moreover, mutual and dynamic dependencies preclude traditional approaches to incrementality. This makes finding automatic approaches to incremental type-checking a challenging but important open question. In this paper, we present a technique that automatically derives incremental type-checkers from type system specifications written in the Statix meta-DSL. We use name resolution queries in scope graphs (a generic model of name binding embedded in Statix) to derive dependencies between compilation units. A novel query confirmation algorithm finds queries for which the answer changed due to an edit in the program. Only units with such queries require reanalysis. The effectiveness of this algorithm is improved by (1) splitting the type-checking task into a context-free and a context-sensitive part, and (2) reusing a generic mechanism to resolve mutual dependencies. This automatically yields incremental type-checkers for any Statix specification. Compared to non-incremental parallel execution, we achieve speedups up to 147x on synthetic benchmarks, and up to 21x on real-world projects, with initial overheads below 10%. This suggests that our framework can provide efficient incremental type-checking to the wide range of languages supported by Statix.
@article{paperbot1464,
title = {Incremental type-checking for free: using scope graphs to derive incremental type-checkers},
author = {Aron Zwaan and Hendrik van Antwerpen and Eelco Visser},
journal = {Proceedings of the ACM on Programming Languages},
volume = {6},
number = {OOPSLA2},
year = {2022},
doi = {10.1145/3563303}
}