Realizability and parametricity in Pure Type Systems

This thesis focuses on the adaptation of realizability and parametricity to dependent types in the framework of Pure Type Systems. We describe a systematic method to build a logic from a programming language, both described as pure type systems. This logic provides formulas to express properties of programs and offers a formal framework that allows us to develop a theory of realizability in which realizers of formulas are exactly programs of the starting programming language. In our framework, the standard representation theorems of Gödel's system T and Girard's system F may be seen as two instances of a more general theorem. Then, we explain how the so-called « logical relations » of parametricity theory may be expressed in terms of realizability, which shows that the generated logic provides an adequate framework for developping a general theory of parametricity. Finally, we show how this parametricity theory can be adapted to the underlying type system of the proof assistant Coq and we give an original example of application of parametricity theory to the formalization of mathematics.

Data and Resources

Additional Info

Field Value
Source https://theses.hal.science/tel-00770669
Author Lasson, Marc
Maintainer CCSD
Last Updated May 15, 2026, 13:13 (UTC)
Created May 15, 2026, 13:13 (UTC)
Identifier NNT: 2012ENSL0764
Language fr
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire de l'Informatique du Parallélisme (LIP) ; École normale supérieure de Lyon (ENS de Lyon) ; Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
creator Lasson, Marc
date 2012-11-20T00:00:00
harvest_object_id c61b6589-83e7-42d8-85d2-a3a423f54374
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-03-30T00:00:00
set_spec type:THESE