Abstract
To warrant programmer productivity, type checker results should be correct and available quickly. Correctness can be provided when a type checker implementation corresponds to a declarative type system specification. Statix is a type system specification language which achieves this by automatically deriving type checker implementations from declarative typing rules. A key feature of Statix is that it uses scope graphs for declarative specification of name resolution. However, compared to hand-written type checkers, type checkers derived from Statix specifications have sub-optimal run time performance.
In this paper, we identify and resolve a performance bottleneck in the Statix solver, namely part of the name resolution algorithm, using partial evaluation. To this end, we introduce a tailored procedural intermediate query resolution language, and provide a specializer that translates declarative queries to this language.
Evaluating this specializer by comparing type checking run time performance on three benchmarks (Apache Commons CSV, IO, and Lang3), shows that our specializer improves query resolution time up to 7.7x, which reduces the total type checking run time by 38 - 48%.
In this paper, we identify and resolve a performance bottleneck in the Statix solver, namely part of the name resolution algorithm, using partial evaluation. To this end, we introduce a tailored procedural intermediate query resolution language, and provide a specializer that translates declarative queries to this language.
Evaluating this specializer by comparing type checking run time performance on three benchmarks (Apache Commons CSV, IO, and Lang3), shows that our specializer improves query resolution time up to 7.7x, which reduces the total type checking run time by 38 - 48%.
Original language | English |
---|---|
Title of host publication | SLE 2022 |
Subtitle of host publication | Proceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering |
Editors | Bernd Fischer, Lola Burgueño, Walter Cazzola |
Place of Publication | New York, NY, USA |
Publisher | Association for Computing Machinery (ACM) |
Pages | 121-133 |
Number of pages | 13 |
ISBN (Electronic) | 9781450399197 |
DOIs | |
Publication status | Published - 2022 |
Event | 15th ACM SIGPLAN International Conference on Software Language Engineering - Auckland, New Zealand Duration: 6 Dec 2022 → 7 Dec 2022 Conference number: 15 https://2022.splashcon.org/home/sle-2022? |
Conference
Conference | 15th ACM SIGPLAN International Conference on Software Language Engineering |
---|---|
Abbreviated title | SLE'22 |
Country/Territory | New Zealand |
City | Auckland |
Period | 6/12/22 → 7/12/22 |
Internet address |
Keywords
- scope graphs
- graph query resolution
- specialization
- partial evaluation
- declarative languages