TL;DR
This paper introduces CCT, a new type theory that extends the Calculus of Constructions (CC) with decidable equational theories. This allows for more intuitive proofs and programming while maintaining decidability, a crucial feature for proof assistants. The authors provide a formal semantic model for CCT, proving its consistency and strong normalization, and demonstrate its applicability by instantiating it with Presburger Arithmetic.
What Problem Does This Paper Address?
Proof assistants like Coq typically use intensional type theory because extensional type theory, which equates terms that compute to the same value, often leads to undecidable type-checking. However, purely intensional type theory can be awkward for programming with dependent types, as it doesn't automatically recognize intuitively equal terms. Previous attempts to incorporate extensionality often sacrificed decidability or were not fully understood theoretically. This paper addresses this by proposing CCT, which integrates decidable first-order equational theories into an intensional type theory. This offers a practical trade-off: gaining some of the benefits of extensionality (more intuitive equality) without losing the crucial decidability of type-checking.
Methods
The core of the paper is the development of a formal semantic model for CCT. This involves:
- Abstract Decidable Theory (CCT): A new type theory schema that abstracts over specific first-order equational theories. This allows for a uniform meta-theoretical study applicable to any theory that meets certain criteria.
- Set-Theoretical Realizability Model: The authors build a model based on set theory and realizability semantics. This is a standard technique for proving consistency and strong normalization (SN) of type theories.
- Modular Framework: They leverage a modular framework for modeling type theories, adapting it to accommodate CCT's extensions.
- Abstract Parameterized Models: The paper defines abstract models for both consistency and SN, which can then be instantiated with concrete theories.
- Formalization in Coq: All theoretical results and proofs are formalized using the Coq proof assistant, ensuring their correctness.
- Presburger Arithmetic Instantiation: As a concrete example, they instantiate CCT with Presburger Arithmetic, a decidable first-order theory, demonstrating the practical applicability of their framework.
Datasets
Not discussed in the paper. The paper focuses on theoretical foundations and formalization, not empirical evaluation on datasets.
Key Insights and Ideas
- Decidable Equational Theories as a Sweet Spot: The paper argues that integrating decidable equational theories is a pragmatic way to bridge the gap between the expressiveness of extensionality and the necessity of decidability in proof assistants.
- Uniform Meta-Theory: By abstracting the equational theory, the authors achieve a uniform meta-theoretical proof (consistency and SN) for CCT, which can then be applied to any specific instance of the abstract theory.
- Presburger Arithmetic as a Test Case: Successfully instantiating CCT with Presburger Arithmetic demonstrates the framework's practical viability and its ability to handle common mathematical theories.
- Separation of Equality and Reduction: Unlike some previous approaches (like CoqMTU), CCT does not embed equational reasoning directly into reduction rules. This separation is key to maintaining consistency and SN while still allowing for decidable equality checking.
Key Results
- Formalization of CCT: The paper presents CCT, a type theory extending CC with abstract decidable equational theories.
- Sound Model for CCT: A set-theoretical realizability model for CCT is constructed.
- Consistency and Strong Normalization: The model proves that CCT is consistent and that all well-typed terms are strongly normalizing, even with strong elimination rules.
- Presburger Arithmetic Instantiation: The paper shows how Presburger Arithmetic can be soundly instantiated within CCT, confirming its applicability to a significant decidable theory.
- Foundation for CICUT: The work lays the groundwork for the sound implementation of CICUT, a proof assistant that incorporates these extensions.
Limitations and Future Work
- Church-Rosser Property and Type-Checking Decidability: The authors acknowledge that because they don't embed equational theories into reduction, proving the Church-Rosser property (a prerequisite for standard type-checking decidability proofs) in the usual way is not straightforward.
- Future Work on Type-Checking Decidability: The next step for the authors is to formalize the syntax of CCT and CICUT and build a complete formal proof of all required properties, including type-checking decidability.
- Handling of Complex Reductions: While the paper proves SN for CCT with Presburger Arithmetic, it notes that the reduction rules considered do not include all possible reductions for NatRec. This means they cannot yet claim full type-checking decidability for the presented version of CICUT.
Summary updated