Score: 0

Mechanizing Synthetic Tait Computability in Istari

Published: September 14, 2025 | arXiv ID: 2509.11418v1

By: Runming Li, Yue Yao, Robert Harper

Potential Business Impact:

Makes computer proofs correct and easier.

Business Areas:
Industrial Automation Manufacturing, Science and Engineering

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.

Country of Origin
🇺🇸 United States

Page Count
16 pages

Category
Computer Science:
Programming Languages