Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Matthieu Sozeau Connect in order to contact the contributor
Submitted on : Monday, December 28, 2015 - 7:06:47 PM
Last modification on : Friday, January 21, 2022 - 3:22:30 AM

Links full text




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. ⟨10.4204/EPTCS.185.5⟩. ⟨hal-01248807⟩



Record views