Andreas Nuyts (KU Leuven (Be)), Degrees of Relatedness



Dependent type theory allows us to write programs and to prove properties about those programs in the same language. However, some properties do not require much proof, as they are evident from a program's implementation, e.g. if a polymorphic program is not ad hoc but relationally parametric, then we get parametricity theorems for free. If we want to safely shortcut proofs by relying on the evident good behaviour of a program, then we need a type-level guarantee that the program is indeed well-behaved. This can be achieved by annotating function types with a modality describing the behaviour of functions. We consider a dependent type system with modalities for relational parametricity, irrelevance (i.e. type-checking time erasability of an argument) and ad hoc polymorphism. The interplay of three modalities and dependent types raises a number of questions. For example: If a term depends on a variable with a given modality, then how should its type depend on it? Are all modalities always applicable, e.g. should we consider parametric functions from the booleans to the naturals? Do we need any further modalities in order to properly reason about these three?

We develop a type system, based on a denotational presheaf model, that answers these questions. The core idea is to equip every type with a number of relations --- just equality for small types, but more for larger types --- and to describe function behaviour by saying how functions act on those relations. The system has modality-aware equality judgements (ignoring irrelevant parts) and modality-aware proving operators (for proving free theorems) which are even self-applicable. It also supports sized types, some form of intersection and union types, and parametric quantification over algebraic structures. We prove soundness in a denotational presheaf model.

In this presentation I will give a relatively technical overview of how relational parametricity works in System F, Fω and dependent type theory. I will explain how and why a parametric modality is needed in dependent type theory to assert free theorems for all types. Next, I will explain how the framework in which we formulate this modality, is already powerful enough to accommodate the other modalities mentioned above. Finally, I will briefly discuss the novel structural modality which is of interest when working with algebraic structures, as well as union and intersection types and the presheaf model.

While prior knowledge about dependent type theory and relational parametricity is useful, the presentation is intended to be accessible without.