Building Type Checker Using Scope Graphs

Building Type Checker Using Scope Graphs: For a Language with Type Classes

Mocanu, Andreea (TU Delft Electrical Engineering, Mathematics and Computer Science)

Zwaan, A.S. (mentor)
Poulsen, C.B. (mentor)
Durieux, T. (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2023-06-29

In this paper, we explore scope graphs as a formal model for constructing type checkers for programming languages that support type classes. Type classes provide a powerful mechanism for ad hoc-polymorphism and code reuse. Nevertheless, the incorporation of type classes into type checkers poses challenges, as it necessitates the resolution of instances and the assurance of coherence amidst overlapping instances. Our approach facilitates the separation of concerns between type class resolution and type checking, promoting extensibility and maintainability of the type checker. We contribute with a formal definition of scope graphs for languages with type classes, accompanied by algorithms for type class resolution and type checking. To assess the correctness of this approach, we implement a prototype type checker, and conduct experiments on a collection of representative programs. The results demonstrate the effectiveness of this baseline approach.

type checking
type classes
scope graphs
ad-hoc polymorphism

http://resolver.tudelft.nl/uuid:64aa6cc8-9039-47b1-99f6-decf150dcab8

Student theses

bachelor thesis

© 2023 Andreea Mocanu