inria-00496988, version 1
Equality is typable in Semi-Full Pure Type Systems
Vincent Siles 1, 2, 3Hugo Herbelin
1, 2
Logic In Computer Science - LICS 2010 (2010) 10 p.
Résumé : There are two usual ways to describe equality in a dependent typing system, one that uses an external notion of computation like beta-reduction, and one that introduces a typed judgement of beta-equality directly in the typing system. After being an open problem for some time, the general equivalence between both approaches has been solved by Adams for a class of pure type systems (PTSs) called functional. In this paper, we relax the functionality constraint and prove the equivalence for all semi-full PTSs by combining the ideas of Adams with a study of the general shape of types in PTSs. As one application, an extension of this result to systems with sub-typing would be a first step toward bringing closer the theory behind a proof assistant such as Coq to its implementation.
- 1 : Preuves, Programmes et Systèmes (PPS)
- CNRS : UMR7126 – Université Paris VII - Paris Diderot
- 2 : PI.R2 (INRIA Paris - Rocquencourt)
- INRIA – Université Paris VII - Paris Diderot – CNRS : UMR7126
- 3 : Laboratoire d'informatique de l'école polytechnique (LIX)
- CNRS : UMR7161 – Polytechnique - X
- Domaine : Informatique/Langage de programmation
- Mots-clés : Pure Type Systems – Judgemental Equality – Church-Rosser – Subject Reduction
- inria-00496988, version 1
- http://hal.inria.fr/inria-00496988
- oai:hal.inria.fr:inria-00496988
- Contributeur : Vincent Siles
- Soumis le : Vendredi 2 Juillet 2010, 10:36:24
- Dernière modification le : Mercredi 7 Juillet 2010, 10:06:09