License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2021.1
URN: urn:nbn:de:0030-drops-140441
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14044/
Go to the corresponding LIPIcs Volume Portal

van Antwerpen, Hendrik ; Visser, Eelco

Scope States: Guarding Safety of Name Resolution in Parallel Type Checkers

pdf-format:
LIPIcs-ECOOP-2021-1.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{vanantwerpen_et_al:LIPIcs.ECOOP.2021.1,
  author =	{van Antwerpen, Hendrik and Visser, Eelco},
  title =	{{Scope States: Guarding Safety of Name Resolution in Parallel Type Checkers}},
  booktitle =	{35th European Conference on Object-Oriented Programming (ECOOP 2021)},
  pages =	{1:1--1:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-190-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{194},
  editor =	{M{\o}ller, Anders and Sridharan, Manu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14044},
  URN =		{urn:nbn:de:0030-drops-140441},
  doi =		{10.4230/LIPIcs.ECOOP.2021.1},
  annote =	{Keywords: type checking, name resolution, parallel algorithms}
}

Keywords: type checking, name resolution, parallel algorithms
Collection: 35th European Conference on Object-Oriented Programming (ECOOP 2021)
Issue Date: 2021
Date of publication: 06.07.2021
Supplementary Material: Software (ECOOP 2021 Artifact Evaluation approved artifact): https://doi.org/10.4230/DARTS.7.2.1

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI