A deep embedding of parametric polymorphism in Coq
Atkey, Bob (2009) A deep embedding of parametric polymorphism in Coq. In: 4rd Informal ACM SIGPLAN Workshop on Mechanizing Metatheory, 2009-09-04.
Preview |
Text.
Filename: Atkey_ACM2009_A_deep_embedding_parametric_polymorphism_Coq.pdf
Accepted Author Manuscript Download (100kB)| Preview |
Abstract
We describe a deep embedding of System F inside Coq, along with a denotational semantics that supports reasoning using Reynolds parametricity. The denotations of System F types are given exactly by objects of sort Set in Coq, and the relations used to formalise Reynolds parametricity are Coq predicates with values in Prop. A key feature of the model is the extensive use of dependent types to maintain agreement between the parts of the model. We use type dependency to represent well-formedness of types and terms, and to keep track of the relation between the denotations of types and the parametricity relations between them. We have used an extension of this formalisation in other research, where we proved that the parametric polymorphic representation of Higher-Order Abstract Syntax is adequate.
ORCID iDs
Atkey, Bob ORCID: https://orcid.org/0000-0002-4414-5047;-
-
Item type: Conference or Workshop Item(Paper) ID code: 74288 Dates: DateEvent4 September 2009PublishedSubjects: Science > Mathematics Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 15 Oct 2020 15:03 Last modified: 11 Nov 2024 17:02 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/74288