Equations for Hereditary Substitution in Leivant's Predicative System F: A Case Study

Cyprien Mangin 1 Matthieu Sozeau 1
1 PI.R2 - Design, study and implementation of languages for proofs and programs
PPS - Preuves, Programmes et Systèmes, Inria Paris-Rocquencourt, UPD7 - Université Paris Diderot - Paris 7, CNRS - Centre National de la Recherche Scientifique : UMR7126
Abstract : This paper presents a case study of formalizing a normalization proof for Leivant's Predicative System F using the Equations package. Leivant's Predicative System F is a stratified version of System F, where type quantification is annotated with kinds representing universe levels. A weaker variant of this system was studied by Stump & Eades, employing the hereditary substitution method to show normalization. We improve on this result by showing normalization for Leivant's original system using hereditary substitutions and a novel multiset ordering on types. Our development is done in the Coq proof assistant using the Equations package, which provides an interface to define dependently-typed programs with well-founded recursion and full dependent pattern-matching. Equations allows us to define explicitly the hereditary substitution function, clarifying its algorithmic behavior in presence of term and type substitutions. From this definition, consistency can easily be derived. The algorithmic nature of our development is crucial to reflect languages with type quantification, enlarging the class of languages on which reflection methods can be used in the proof assistant.
Type de document :
Communication dans un congrès
Tenth International Workshop on Logical Frameworks and Meta Languages: Theory and Practice, Aug 2015, Berlin, Germany. Proceedings Tenth International Workshop on Logical Frameworks and Meta Languages: Theory and Practice, 185, EPTCS. 〈10.4204/EPTCS.185.5〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01248807
Contributeur : Matthieu Sozeau <>
Soumis le : lundi 28 décembre 2015 - 19:06:47
Dernière modification le : jeudi 11 janvier 2018 - 06:22:37

Identifiants

Collections

INRIA | PPS | USPC

Citation

Cyprien Mangin, Matthieu Sozeau. Equations for Hereditary Substitution in Leivant's Predicative System F: A Case Study. Tenth International Workshop on Logical Frameworks and Meta Languages: Theory and Practice, Aug 2015, Berlin, Germany. Proceedings Tenth International Workshop on Logical Frameworks and Meta Languages: Theory and Practice, 185, EPTCS. 〈10.4204/EPTCS.185.5〉. 〈hal-01248807〉

Partager

Métriques

Consultations de la notice

74