A Modular Type-checking algorithm for Type Theory with Singleton Types
and Proof IrrelevanceArticle
Authors: Andreas Abel ; Thierry Coquand ; Miguel Pagano
NULL##NULL##NULL
Andreas Abel;Thierry Coquand;Miguel Pagano
We define a logical framework with singleton types and one universe of small
types. We give the semantics using a PER model; it is used for constructing a
normalisation-by-evaluation algorithm. We prove completeness and soundness of
the algorithm; and get as a corollary the injectivity of type constructors.
Then we give the definition of a correct and complete type-checking algorithm
for terms in normal form. We extend the results to proof-irrelevant
propositions.
András Kovács, 2022, Staged compilation with two-level type theory, Proceedings of the ACM on Programming Languages, 6, ICFP, pp. 540-569, 10.1145/3547641, https://doi.org/10.1145/3547641.
Andreas Abel;Andrea Vezzosi;Theo Winterhalter, 2017, Normalization by evaluation for sized dependent types, Proceedings of the ACM on Programming Languages, 1, ICFP, pp. 1-30, 10.1145/3110277, https://doi.org/10.1145/3110277.
Daniel Fridlender;Miguel Pagano, Lecture notes in computer science, A Type-Checking Algorithm for Martin-Löf Type Theory with Subtyping Based on Normalisation by Evaluation, pp. 140-155, 2013, 10.1007/978-3-642-38946-7_12.