Type checker for a language with a substructural type system using scope graphs

Substructural typing imposes additional constraints on variable usage during type checking and requires specialized approaches to ensure type soundness. In this study, we investigate the implementation of a type checker using scope graphs for languages with substructural type systems. Scope graphs, a data structure representing scoping, provide...

Phased Type Checker For Java: A Type Checker For a Subset of Java Built On Scope Graph Semantics

Traditional type-checking programs are typically designed for specific programming languages, re- sulting in complex and tightly coupled imperative implementations. One of the challenges faced by type checkers is ensuring consistent name-binding resolution in the presence of new names and sym- bols added to the environment. To address this issue...

Building Type Checkers Using Scope Graphs: Scope Graph-Based Type Checking for a Scala Subset

This paper investigates the viability of using scope graphs to implement type checkers for programming languages, specifically for a Scala subset. The primary objective is to determine if scope graphs can offer a declarative and extensible approach to type checking. To achieve this, we used a phased Haskell library to implement such a type...

A Monadic Framework for Name Resolution in Multi-phased Type Checkers

An important aspect of type checking is name resolution — i.e., determining the types of names by resolving them to a matching declaration. For most languages, we can give typing rules that define name resolution in a way that abstracts from what order different units of code should be checked in. However, implementations of type checkers in...

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

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...

Validating Type Checkers Using Property-Based Testing

Manually testing definitional interpreters and their type checkers is a tedious and error-prone process which can largely benefit from automation. This study evaluates the effectiveness of property-based testing on errors in type checkers. Metrics used include the ability to catch different types of errors as well as the ability to provide a...

Knowing when to ask: Sound scheduling of name resolution in type checkers derived from declarative specifications

There is a large gap between the specification of type systems and the implementation of their type checkers, which impedes reasoning about the soundness of the type checker with respect to the specification. A vision to close this gap is to automatically obtain type checkers from declarative programming language specifications. This moves...

Declarative and Algorithmic Implementation of Refinement Types

Type systems and their accompanying checkers provide support for the programmer to write better and safer code, faster, with less effort and with less errors. There are however properties that can not be checked at compile time yet. Refinement types are potentially the solution. They can prove properties of the behaviour of code without actually...