Specializing Scope Graph Resolution Queries

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)
18 Downloads (Pure)

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%.
Original languageEnglish
Title of host publicationSLE 2022
Subtitle of host publicationProceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering
EditorsBernd Fischer, Lola Burgueño, Walter Cazzola
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery (ACM)
Pages121-133
Number of pages13
ISBN (Electronic)9781450399197
DOIs
Publication statusPublished - 2022
Event15th ACM SIGPLAN International Conference on Software Language Engineering - Auckland, New Zealand
Duration: 6 Dec 20227 Dec 2022
Conference number: 15
https://2022.splashcon.org/home/sle-2022?

Conference

Conference15th ACM SIGPLAN International Conference on Software Language Engineering
Abbreviated titleSLE'22
Country/TerritoryNew Zealand
CityAuckland
Period6/12/227/12/22
Internet address

Keywords

  • scope graphs
  • graph query resolution
  • specialization
  • partial evaluation
  • declarative languages

Fingerprint

Dive into the research topics of 'Specializing Scope Graph Resolution Queries'. Together they form a unique fingerprint.

Cite this