Sebastian Erdweg from the Technical University of Darmstadt presents a novel formulation of typing rules that is more amenable to incremental type checking than the usual representation with typing contexts.

Abstract

Type rules associate types to expressions given a typing context. As the type checker traverses the expression tree top-down, it extends the typing context with additional context information that becomes available. This way, the typing context coordinates type checking in otherwise independent subexpressions, which inhibits parallelization and incrementalization of type checking.

We propose a co-contextual formulation of type rules that only take an expression as input and produce a type and a set of context requirements. Co-contextual type checkers traverse an expression tree bottom-up and merge context requirements of independently checked subexpressions. We describe a method for systematically constructing a co-contextual formulation of type rules from a regular context-based formulation and we show how co-contextual type rules give rise to incremental type checking. Using our method, we derive incremental type checkers for PCF and for extensions that introduce records, parametric polymorphism, and subtyping. Our performance evaluation shows that co-contextual type checking has performance comparable to standard context-based type checking, and incrementalization can improve performance significantly.

(Joint work with Oliver Bračevac, Edlira Kuci, Matthias Krebs, and Mira Mezini)

About the Speaker

Sebastian Erdweg is a post-doctoral researcher and leads the Programming-Language Theory and Engineering subgroup of the Software Technology Group at TU Darmstadt.