Incremental Type-Checking for Free: Using Scope Graphs to Derive Incremental Type-Checkers

Research output: Contribution to journalConference articleScientificpeer-review

3 Citations (Scopus)
53 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article number140
Number of pages25
JournalProceedings of the ACM on Programming Languages
Volume6
Issue numberOOPSLA2
DOIs
Publication statusPublished - 2022
EventOOPSLA/SPLASH 22 - Auckland, New Zealand
Duration: 5 Dec 202210 Dec 2022

Keywords

  • type-checker
  • incremental type-checking
  • scope graphs
  • type systems
  • name binding
  • reference resolution
  • Statix

Fingerprint

Dive into the research topics of 'Incremental Type-Checking for Free: Using Scope Graphs to Derive Incremental Type-Checkers'. Together they form a unique fingerprint.

Cite this