Mechanizing Synthetic Tait Computability in Istari
By: Runming Li, Yue Yao, Robert Harper
Potential Business Impact:
Makes computer proofs correct and easier.
Categorical gluing is a powerful technique for proving meta-theorems of type theories such as canonicity and normalization. Synthetic Tait Computability (STC) provides an abstract treatment of the complex gluing models by internalizing the gluing category into a modal dependent type theory with a phase distinction. This work presents a mechanization of STC in the Istari proof assistant. Istari is a Martin-L\"{o}f-style extensional type theory with equality reflection. Equality reflection eliminates the nuisance of transport reasoning typically found in intensional proof assistants. This work develops a reusable library for synthetic phase distinction, including modalities, extension types, and strict glue types, and applies it to two case studies: (1) a canonicity model for dependent type theory with dependent products and booleans with large elimination, and (2) a Kripke canonicity model for the cost-aware logical framework. Our results demonstrate that the core STC constructions can be formalized essentially verbatim in Istari, preserving the elegance of the on-paper arguments while ensuring machine-checked correctness.
Similar Papers
Canonicity for Cost-Aware Logical Framework via Synthetic Tait Computability
Programming Languages
Proves a math idea to make computer costs clear.
A Judgmental Construction of Directed Type Theory
Logic in Computer Science
Makes computer code safer and more organized.
Mechanizing a Proof-Relevant Logical Relation for Timed Message-Passing Protocols
Programming Languages
Helps computers check if smart devices follow time rules.