Parametriciteit in Type Theorie: Taalprimitieven en Toepassingen

Abstract

Formal software verification systems aim to provide rigorous mathematical proofs that programs adhere to their specifications. In particular, proof assistants like Agda, Rocq and Lean can express programs, specifications and proofs within a single unifying language called Dependent Type Theory (DTT). This thesis makes contributions to parametricity within the setting of DTT and proof assistants. As a first approximation, parametricity is a uniformity property regarding polymorphic, i.e. generic programs. A generic program behaves identically regardless of the type it is instantiated with, because it cannot inspect its type argument. This simple observation leads to useful knowledge when performing proofs about the program (Wadler calls such knowledge ``theorems for free''). More generally, Reynolds mathematically defined the notion of parametricity as relational parametricity, the statement that every type can be turned into a certain reflexive graph. An edge in the graph between two values is a proof that the values have a similar structure. For instance an edge between polymorphic programs is a proof that they map related types to related outputs, and this formalizes what it means to be uniform. The parametricity translation, mapping types to reflexive graphs, is defined externally as a meta-operation on DTT expressions and is not an operation that is available inside, or internal to DTT. For example, given a type of polymorphic functions, one cannot prove inside DTT the formal statement expressing that every such function is uniform (we call such statements global free theorems). Internally parametric type theories (PTTs) achieve this by equipping DTT with a so-called Bridge type former, whose role is to represent the parametricity translation inside the theory. A landmark example is the interval-based theory of Cavallo and Harper (the CH theory), in which bridges are functions from a postulated bridge interval, in analogy with the path types of cubical type theory. Within the CH theory, global free theorems become provable. However, a practical limitation persists: contrary to the Reynolds translation of a type, the Bridge translation of a type does not directly provide an actionable parametricity result. Indeed tedious case-by-case rote work is required of the user to establish that the Bridge type former commutes with each type former appearing in the type under consideration. The first main contribution of this thesis is to improve the practical usability of internally parametric type theories. Firstly, we address the lack of a full-fledged proof-assistant implementation of binary internal parametricity and contribute the Agda-bridges proof assistant. Agda-bridges is an extension of the Agda proof assistant and implements an interactive typechecker for the CH parametric type theory. More precisely, Agda-bridges extends Agda-cubical, itself an implementation of cubical type theory. In fact, Agda-bridges typechecks the standard library of Agda-cubical, hence important theorems provided by Agda-cubical, like univalence, remain available to the user of Agda-bridges. Moreover, Agda-bridges validates key theorems for internal parametricity, in particular the relativity equivalence. This makes it possible to provide formal proofs of free theorems, including global ones. Yet the rote work challenge described above persists. Hence, secondly, we contribute Relational Observational Type Theory (ROTT), a library, or domain-specific language, written in Agda-bridges that eliminates the rote work in a principled way. ROTT lets the user obtain concise and modular proofs of actionable parametricity statements. Once a type is written using the ROTT DSL, a corresponding proof can be extracted as a one-liner. Using this methodology we are able to formalize global free theorems of practical and theoretical relevance. Notably, we expand on a proof communicated to us by Andrea Vezzosi and can show that higher-order abstract syntax is an adequate representation of the untyped lambda calculus (previously known proofs relied on the strictly stronger notion of Kripke parametricity). The second main contribution of this thesis concerns nullary internal parametricity and its relationship to the formal study of languages with variable binding. When studying a language on paper it is common to think of variables as strings, and to adopt the convention that alpha-equivalent terms are equal. However, when working formally it is preferable to represent the syntax of the object language in such a way that alpha-equivalent terms are equal by construction. Nominal frameworks are type systems featuring a so-called name abstraction type former, used to give a type to the binders of the object language. This type former enables a string-like but alpha-equivalence-respecting representation of syntax with binders. Yet existing nominal frameworks either feature typing rules hard to implement in a proof assistant environment, or lack expressivity to reason about nominal syntax. We solve these issues by contributing Parametric Nominal Type Theory, which is an extension of the nullary CH theory, a version of the CH theory where bridges have zero endpoints instead of two. Firstly, we recognize that the nullary CH theory is itself the basis of a nominal framework in which name abstraction corresponds to the nullary bridge type former. In fact the other primitives of the CH theory can be understood from a nominal point of view and existing nominal primitives can be implemented in terms of the CH ones. Secondly, we identify the missing piece that suffices to turn the nullary CH theory into an actual nominal framework, in which one can reason about object languages in a nominal fashion without the aforementioned lack of expressivity. The missing piece is a type of names Nm such that its nullary Bridge type/nullary translation is the sum type 1+Nm. We provide an induction principle for Nm that entails the property. We demonstrate that Parametric Nominal Type Theory is a suitable nominal framework. One of our examples involves emulating a restricted form of Kripke parametricity by nullary parametricity.