Home > Research > Publications & Outputs > A co-contextual formulation of type rules and i...


Text available via DOI:

View graph of relations

A co-contextual formulation of type rules and its application to incremental type checking

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

  • Sebastian Erdweg
  • Oliver Bračevac
  • Edlira Kuci
  • Matthias Krebs
  • Ermira Mezini
Publication date25/10/2015
Host publicationOOPSLA 2015 Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications
Place of PublicationNew York
Number of pages18
ISBN (Print)9781450336895
<mark>Original language</mark>English


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.