A Co-contextual Formulation of Type Rules and Its Application to Incremental Type Checking

Type rules associate types to expressions given a typing con-text. 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 incremen-talization 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 tra-verse an expression tree bottom-up and merge context require-ments of independently checked subexpressions. We describe a method for systematically constructing a co-contextual for-mulation of type rules from a regular context-based formu-lation 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