Lune

PLDI2021Top-tier venue

Proof repair across type equivalences

Talia Ringer, RanDair Porter, Nathaniel Yazdani, John Leo, Dan Grossman

Abstract

We describe a new approach to automatically repairing broken proofs in the Coq proof assistant in response to changes in types. Our approach combines a configurable proof term transformation with a decompiler from proof terms to suggested tactic scripts. The proof term transformation implements transport across equivalences in a way that removes references to the old version of the changed type and does not rely on axioms beyond those Coq assumes.

We have implemented this approach in Pumpkin Pi, an extension to the Pumpkin Patch Coq plugin suite for proof repair. We demonstrate Pumpkin Pi's flexibility on eight case studies, including supporting a benchmark from a user study, easing development with dependent types, porting functions and proofs between unary and binary numbers, and supporting an industrial proof engineer to interoperate between Coq and other verification tools more easily.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

9 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • QED in Context: An Observation Study of Proof Assistant Users cites Mostly Automated Proof Repair for Verified Libraries
  • Diversity-Driven Automated Formal Verification cites TacTok: semantics-aware proof synthesis
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers9

  1. Diversity-Driven Automated Formal VerificationEmily First, Yuriy BrunICSE 2022 · 28 citations
  2. Mostly Automated Proof Repair for Verified LibrariesKiran Gopinathan, Mayank Keoliya, Ilya SergeyPLDI 2023 · 11 citations
  3. Extensible Metatheory Mechanization via Family PolymorphismEnde Jin, Nada Amin, Yizhou ZhangPLDI 2023 · 10 citations
  4. APE-Bench: Evaluating Automated Proof Engineering for Formal Math LibrariesHuajian Xin, Zheng Yuan, Jacques Fleuriot, Wenda LiICML 2026 · 4 citations
  5. QED in Context: An Observation Study of Proof Assistant UsersJessica Shi, Cassia Torczon, Harrison Goldstein, Benjamin C. Pierce et al.OOPSLA 2025 · 2 citations

Builds on2

  1. TacTok: semantics-aware proof synthesisEmily First, Yuriy Brun, Arjun GuhaOOPSLA 2020 · 39 citations
  2. Internalizing representation independence with univalenceCarlo Angiuli, Evan Cavallo, Anders Mörtberg, Max ZeunerPOPL 2021 · 18 citations

Related papers

  1. Proof Repair across Quotient Type EquivalencesCosmo Viola, Max Fan, Talia RingerOOPSLA 2025 · 1 citation
  2. All Your Base Are Belong to Us: Sort Polymorphism for Proof AssistantsJosselin Poiret, Gaëtan Gilbert, Kenji Maillard, Pierre-Marie Pédrot et al.POPL 2025 · 6 citations
  3. Impredicative Observational EqualityLoïc Pujet, Nicolas TabareauPOPL 2023 · 14 citations
  4. Lean-Auto: An Interface Between Lean 4 and Automated Theorem ProversYicheng Qian, Joshua Clune, Clark W. Barrett, Jeremy AvigadCAV 2025 · 6 citations
  5. Proof Artifact Co-Training for Theorem Proving with Language ModelsJesse Michael Han, Jason Rute, Yuhuai Wu, Edward W. Ayers et al.ICLR 2022 · 149 citations
Dusk over the sea between two cliffs drawn in fine vertical lines