Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This work extends computational progress guarantees in type theories with compile-time erasure to systems containing identity types, quotient types, and erased postulates. Postulating classical axioms or quotient equivalence relations traditionally destroys program execution in proof assistants by causing terms to get stuck during reduction. The paper establishes that runtime evaluation remains sound when casting along erased equalities implementable via equality reflection, while characterizing the limits of erased univalence and formalizing a restricted transport operator (`[]-cong`) in Agda.
You can safely postulate quotient equalities and cast along erased identity proofs without runtime programs getting stuck—until univalence enters the picture.
This text is concerned with the question of whether, in type theory with erasure annotations, one can postulate that some type is inhabited and still have a guarantee that a program will not get stuck. Previous work has provided such guarantees for consistent erased postulates, i.e. postulates that are restricted to be used in erased contexts. Here those guarantees are extended to type theory with identity types. Similar ideas provide a simple way to support quotient types: it is shown that one can let things like"the equivalence classes for two related values are equal"be erased postulates and have an eliminator that only computes for the equivalence class constructor, and still get a guarantee that programs will compute correctly. Another question is whether programs compute correctly if one is allowed to transport (cast) using erased identity proofs. It is shown that this is safe in the absence of quotients and postulates, and in the presence of quotients and erased postulates that can be implemented using equality reflection. However, unrestricted transports of this kind are not compatible with erased, postulated univalence. For that reason the text includes a study of the function []-cong, which encapsulates a limited form of transport for erased identity proofs. The text is accompanied by machine-checked Agda proofs.