Scope states: Guarding safety of name resolution in parallel type checkers

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

8 Downloads (Pure)

Abstract

Compilers that can type check compilation units in parallel can make more efficient use of multi-core architectures, which are nowadays widespread. Developing parallel type checker implementations is complicated by the need to handle concurrency and synchronization of parallel compilation units. Dependencies between compilation units are induced by name resolution, and a parallel type checker needs to ensure that units have defined all relevant names before other units do a lookup. Mutually recursive references and implicitly discovered dependencies between compilation units preclude determining a static compilation order for many programming languages. In this paper, we present a new framework for implementing hierarchical type checkers that provides implicit parallel execution in the presence of dynamic and mutual dependencies between compilation units. The resulting type checkers can be written without explicit handling of communication or synchronization between different compilation units. We achieve this by providing type checkers with an API for name resolution based on scope graphs, a language-independent formalism that supports a wide range of binding patterns. We introduce the notion of scope state to ensure safe name resolution. Scope state tracks the completeness of a scope, and is used to decide whether a scope graph query between compilation units must be delayed. Our framework is implemented in Java using the actor paradigm. We evaluated our approach by parallelizing the solver for Statix, a meta-language for type checkers based on scope graphs, using our framework. This parallelizes every Statix-based type checker, provided its specification follows a split declaration-type style. Benchmarks show that the approach results in speedups for the parallel Statix solver of up to 5.0x on 8 cores for real-world code bases.

Original languageEnglish
Title of host publication35th European Conference on Object-Oriented Programming, ECOOP 2021
EditorsAnders Moller, Manu Sridharan
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771900
DOIs
Publication statusPublished - 2021
Event35th European Conference on Object-Oriented Programming, ECOOP 2021 - Virtual, Aarhus, Denmark
Duration: 11 Jul 202117 Jul 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume194
ISSN (Print)1868-8969

Conference

Conference35th European Conference on Object-Oriented Programming, ECOOP 2021
CountryDenmark
CityVirtual, Aarhus
Period11/07/2117/07/21

Keywords

  • Name resolution
  • Parallel algorithms
  • Type checking

Fingerprint

Dive into the research topics of 'Scope states: Guarding safety of name resolution in parallel type checkers'. Together they form a unique fingerprint.

Cite this