Reference. Proof Repair across Quotient Type Equivalences
Proofs in proof assistants like Rocq can be brittle, breaking easily in response to changes. To address this, recent work introduced an algorithm and tool in Rocq to automatically repair broken proofs in response to changes that correspond to type equivalences. However, many changes remained out of the scope of this algorithm and tool—especially changes in underlying behavior . We extend this proof repair algorithm so that it can express certain changes in behavior that were previously out of scope. We focus in particular on equivalences between quotient types —types equipped with a relation that describes what it means for any two elements of that type to be equal. Quotient type equivalences can be used to express interesting changes in representations of mathematical structures, as well as changes in the implementations of data structures. We extend this algorithm and tool to support quotient type equivalences in Rocq. Notably, since Rocq lacks quotient types entirely, our extensions use Rocq’s setoid machinery in place of quotients. Specifically, (1) our extension to the algorithm supports new changes corresponding to setoids, and (2) our extension to the tool supports this new class of changes and further automates away some of the new proof obligations. We demonstrate our extensions on proof repair case studies for previously unsupported changes. We also perform manual proof repair in Cubical Agda, a language with a univalent metatheory, which allows us to construct the first ever internal proofs of correctness for proof repair.
Cite
Cites 41 works (10 here)
With notes (10)
The Univalence Principle ahrens-2021-the
The Univalence Principle is the statement that equivalent mathematical structures are indistinguishable. We prove a general version of this principle that applies to all set-based, categorical, and higher-categorical structures defined in a non-algebraic and space-based style, as well as models of higher-order theories such as topological spaces. In particular, we formulate a general definition of indiscernibility for objects of any such structure, and a corresponding univalence condition that generalizes Rezk’s completeness condition for Segal spaces and ensures that all equivalences of structures are levelwise equivalences. Our work builds on Makkai’s First-Order Logic with Dependent Sorts, but is expressed in Voevodsky’s Univalent Foundations (UF), extending previous work on the Structure Identity Principle and univalent categories in UF. This enables indistinguishability to be expressed simply as identification, and yields a formal theory that is interpretable in classical homotopy theory, but also in other higher topos models. It follows that Univalent Foundations is a fully equivalence-invariant foundation for higher-categorical mathematics, as intended by Voevodsky.
A Cubical Language for Bishop Sets sterling-2022-a
We present XTT, a version of Cartesian cubical type theory specialized for Bishop sets à la Coquand, in which every type enjoys a definitional version of the uniqueness of identity proofs. Using cubical notions, XTT reconstructs many of the ideas underlying Observational Type Theory, a version of intensional type theory that supports function extensionality. We prove the canonicity property of XTT (that every closed boolean is definitionally equal to a constant) using Artin gluing.
Proof repair across type equivalences ringer-2021-proof
Internalizing representation independence with univalence angiuli-2021-internalizing
In their usual form, representation independence metatheorems provide an external guarantee that two implementations of an abstract interface are interchangeable when they are related by an operation-preserving correspondence. If our programming language is dependently-typed, however, we would like to appeal to such invariance results within the language itself, in order to obtain correctness theorems for complex implementations by transferring them from simpler, related implementations. Recent work in proof assistants has shown that Voevodsky’s univalence principle allows transferring theorems between isomorphic types, but many instances of representation independence in programming involve non-isomorphic representations. In this paper, we develop techniques for establishing internal relational representation independence results in dependent type theory, by using higher inductive types to simultaneously quotient two related implementation types by a heterogeneous correspondence between them. The correspondence becomes an isomorphism between the quotiented types, thereby allowing us to obtain an equality of implementations by univalence. We illustrate our techniques by considering applications to matrices, queues, and finite multisets. Our results are all formalized in Cubical Agda, a recent extension of Agda which supports univalence and higher inductive types in a computationally well-behaved way.
REPLica: REPL instrumentation for Coq analysis ringer-2020-replica
QED at Large: A Survey of Engineering of Formally Verified Software ringer-2019-qed
Development of formal proofs of correctness of programs can increase actual and perceived reliability and facilitate better understanding of program specifications and their underlying assumptions. Tools supporting such development have been available for over 40 years, but have only recently seen wide practical use. Projects based on construction of machine-checked formal proofs are now reaching an unprecedented scale, comparable to large software projects, which leads to new challenges in proof development and maintenance. Despite its increasing importance, the field of proof engineering is seldom considered in its own right; related theories, techniques, and tools span many fields and venues. This survey of the literature presents a holistic understanding of proof engineering for program correctness, covering impact in practice, foundations, proof automation, proof organization, and practical proof development.
Cubical Agda: A Dependently Typed Programming Language with Univalence and Higher Inductive Types VezzosiMortbergAbel2019
Proof assistants based on dependent type theory provide expressive languages for both programming and proving within the same system. However, all of the major implementations lack powerful extensionality principles for reasoning about equality, such as function and propositional extensionality. These principles are typically added axiomatically which disrupts the constructive properties of these systems. Cubical type theory provides a solution by giving computational meaning to Homotopy Type Theory and Univalent Foundations, in particular to the univalence axiom and higher inductive types. This paper describes an extension of the dependently typed functional programming language Agda with cubical primitives, making it into a full-blown proof assistant with native support for univalence and a general schema of higher inductive types. These new primitives make function and propositional extensionality as well as quotient types directly definable with computational content. Additionally, thanks also to copatterns, bisimilarity is equivalent to equality for coinductive types. This extends Agda with support for a wide range of extensionality principles, without sacrificing type checking and constructivity.
Adapting proof automation to adapt proofs ringer-2018-adapting
Computational higher-dimensional type theory angiuli-2017-computational
External (31)
- Proof Repair across Quotient Type Equivalences - Artifact (2025)
- Trocq: Proof Transfer for Free, With or Without Univalence (2024)
- Mostly Automated Proof Repair for Verified Libraries (2023)
- Rocq Reference Manual, Generalized Rewriting (2023)
- Rocq Reference Manual, Reasoning with equalities (2023)
- The Marriage of Univalence and Parametricity (2021)
- Setoid Type Theory—A Syntactic Translation (2019)
- The Rocq Prover Standard Library, Coq.Classes.Morphisms (2019)
- Cubical Type Theory: A Constructive Interpretation of the Univalence Axiom (2018)
- On Higher Inductive Types in Cubical Type Theory (2018)
- Automatic Software Repair: A Bibliography (2018)
- Front-end tooling for building and maintaining dependently-typed functional programs (2018)
- Equivalences for free: univalent parametricity for effective transport (2018)
- The HoTT library: a formalization of homotopy type theory in Coq (2017)
- Theorem Proving in Lean (2017)
- Planning for change in a formal verification of the raft consensus protocol (2016)
- First Steps Towards Cumulative Inductive Types in CIC (2015)
- Certified Programming with Dependent Types - A Pragmatic Introduction to the Coq Proof Assistant (2013)
- Refinements for Free! (2013)
- Isomorphism is equality (2013)
- Lifting and Transfer: A Modular Design for Quotients in Isabelle/HOL (2013)
- Product lines of theorems (2011)
- Structured Formal Development with Quotient Types in Isabelle/HOL (2010)
- The Isabelle/Isar reference manual (2004)
- Setoids in type theory (2003)
- About Effective Quotients in Constructive Type Theory (1999)
- Extensional concepts in intensional type theory (1995)
- Elimination of extensionality in Martin-Löf type theory (1994)
- Inductively defined types (1990)
- The calculus of constructions (1988)
- Foundations of Constructive Analysis (1967)