🤖 AI

When Agda met Vampire

This paper presents a prototype system that bridges Agda and the Vampire ATP by translating proof obligations through a shared equational Horn fragment, enabling the automatic generation of constructive proofs for complex mathematical properties that previously required days of manual effort.

Original authors: Artjoms Šinkarovs, Michael Rawson

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Artjoms Šinkarovs, Michael Rawson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master architect (the Proof Assistant, specifically Agda) building a skyscraper that must be perfectly safe. Every single brick, beam, and bolt must be inspected and approved by a strict, by-the-book inspector. If even one brick is slightly out of place, the whole building is considered unsafe.

The problem is that this inspector is incredibly thorough but also incredibly slow. They check every single detail manually. If you need to prove that a specific window fits a specific frame, the inspector might take hours to verify it, even though it's a standard window.

Enter Vampire, a super-fast, high-speed robot detective. Vampire is amazing at solving puzzles and finding connections instantly. However, Vampire has a catch: it speaks a different language (Classical Logic) and uses a different set of rules than your strict inspector. If you ask Vampire to solve a problem, it might shout, "I found the answer!" but its explanation is written in a code your inspector doesn't understand or trust.

This paper is about building a translator and a bridge between the slow, strict Architect and the fast, chaotic Robot.

The Core Problem: Two Different Worlds

Agda (The Architect): Works in "Constructive Logic." This means to prove something exists, you must actually build it. It's like saying, "I can prove I have a key because I'm holding one in my hand."
Vampire (The Robot): Works in "Classical Logic." It's okay with saying, "I can prove a key exists because if it didn't, the door would be locked, which is impossible." It's faster but doesn't always "hold the key" in its hand; it just knows it's there.

Usually, these two can't talk to each other. If you send a job to Vampire, it comes back with a proof that Agda rejects because it's "too classical."

The Solution: The "Horn Clause" Bridge

The authors realized that while the two languages are very different, they share a small, common dialect called Horn Clauses. Think of this as a simple, universal "pidgin" language that both the Architect and the Robot can understand. It's like a simplified version of English where you only say things like:

"If A is true, and B is true, then C is true."
"If X equals Y, and Y equals Z, then X equals Z."

They didn't try to translate the entire complex language of the Architect. Instead, they identified the specific, routine tasks (like checking if two algebraic expressions are equal) that fit into this simple dialect.

How It Works: The Three-Step Dance

The Translation (Agda to Vampire):
When the Architect (Agda) gets stuck on a boring, repetitive task (like proving a complex math property about roots of unity), it uses a special mirror (called Reflection) to look at the problem. It translates the complex math problem into the simple "Horn Clause" dialect and sends it to the Robot (Vampire).
The Detective Work (Vampire Solves):
Vampire zooms in, solves the puzzle in a fraction of a second, and shouts back a solution. But, because Vampire is a classical detective, its solution looks like a refutation (e.g., "It is impossible for the answer to be false!").
The Reconstruction (Vampire to Agda):
This is the magic trick. The authors built a small, clever engine (written in Prolog, a language good at logic puzzles) that acts as a translator.
- It takes Vampire's "impossible to be false" proof.
- It mechanically rewrites it, step-by-step, into a "here is the key" proof.
- It turns the classical logic back into constructive logic.
- Finally, it hands this new, perfectly formatted proof back to the Architect (Agda).

Agda checks the new proof. Since it was built step-by-step according to Agda's strict rules, Agda accepts it immediately.

The Real-World Test: The Complex Field

To prove this works, the authors tried it on a real, difficult problem: verifying properties of a "complex field with roots of unity."

Without the bridge: A professional mathematician using Agda had to spend two full days manually proving these properties.
With the bridge: The system did it automatically in a fraction of a second.

Why This Matters

Think of it like a spell-checker for mathematicians.
Before, if you wanted to write a long, complex book of proofs, you had to check every single sentence manually. It was exhausting and slow.
Now, this system acts like a "Hammer" (a term used in this field). It handles the boring, repetitive, mechanical parts of the proof so the human mathematician can focus on the big, creative ideas.

In summary:
The authors built a lightweight translator that lets a slow, strict, constructive proof assistant borrow the speed of a fast, classical theorem prover. They translate the problem into a simple language, let the robot solve it, and then translate the robot's messy solution back into a clean, trustworthy proof that the strict inspector will accept. It saves days of work and makes building verified software much easier.

1. Problem Statement

Dependently-typed proof assistants (e.g., Agda, Lean, Rocq) offer strong correctness guarantees via the Curry-Howard correspondence but suffer from a lack of effective automation. While interactive theorem provers (ITPs) rely on user-guided tactics, non-trivial proof obligations are often routine yet labor-intensive.

Existing "hammer" systems (like Isabelle's Sledgehammer) bridge ITPs and Automated Theorem Provers (ATPs) by translating goals to classical first-order logic (FOL), finding a proof, and reconstructing it. However, this approach faces significant hurdles in dependently-typed systems:

Logic Mismatch: ATPs like Vampire operate in classical FOL, while Agda is based on constructive Martin-Löf type theory.
Trust and Reconstruction: ATPs do not produce proof terms; they produce classical proofs by refutation. Reconstructing these into constructive proof terms that Agda can type-check is difficult, especially when the ITP lacks strong internal automation to guide the reconstruction.
Implementation Burden: Deep integration often requires invasive changes to the proof assistant's kernel or complex internal proof search procedures.

2. Methodology

The authors propose a lightweight integration strategy that avoids invasive changes to Agda or Vampire. The core idea is to identify a specific, expressive fragment of Agda that maps naturally to the Horn clause fragment of FOL, allowing for a sound, bidirectional translation.

A. The Expressive Fragment

The system restricts translation to a fragment of Agda that corresponds to Horn clauses:

Definite Clauses: Implications of the form $R_1 \to R_2 \to \dots \to R_n \to G$ , where $R_i$ and $G$ are atomic types.
Constraints:
- No dependent functions (arguments must be simple, non-dependent types).
- No parameters or indices on inductive datatypes.
- Theorems must reside in the Horn fragment (using propositional equality as the primary relation).
Assumption: The system assumes Uniqueness of Identity Proofs (UIP), treating propositional equality as proof-irrelevant for the translation.

B. The Workflow

The integration follows a four-step round-trip process:

Reflection & Translation (Agda $\to$ Vampire):
- Using Agda's reflection facilities, the system extracts the current goal and environment (definitions, axioms).
- Macros translate Agda definitions into SMT-LIB format (a standard input for ATPs).
- Inductive types become datatypes; functions become function symbols with axioms derived from pattern-matching equations.
- The goal is negated and added to the axioms to form a refutation problem for Vampire.
Proof Search (Vampire):
- Vampire (a classical ATP) attempts to refute the negated goal using the superposition calculus.
- It outputs a proof in TSTP (Thousands of Solutions from Theorem Provers) format.
Proof Transformation (Classical $\to$ Constructive):
- The authors observe that Vampire's core inference rules (Resolution, Factoring, Superposition) are constructively valid when applied to Horn clauses.
- The Transformation Trick: Vampire proves $\Gamma, \neg G \vdash \bot$ . The system mechanically transforms this proof into a constructive proof of $\Gamma \vdash G$ by replacing the root goal clause ( $G \to \bot$ ) with the tautology ( $G \to G$ ) and systematically replacing occurrences of $\bot$ in the proof steps with $G$ . This is analogous to Friedman's A-translation.
Reconstruction (Vampire $\to$ Agda):
- A Prolog script parses the TSTP proof.
- It performs a backtracking search to map Vampire's inference steps to corresponding Agda proof terms (e.g., mapping a Superposition step to an Agda rewrite term).
- The resulting Agda term is emitted and type-checked by Agda's kernel, ensuring total trust.

3. Key Contributions

Lightweight Integration: A novel approach that uses Agda's reflection to interface with an external ATP without modifying the Agda kernel or the Vampire source code.
Sound Translation Mechanism: A rigorous method for translating constructive Horn clauses to classical FOL and back, preserving correctness via a specific transformation of the proof structure (replacing $\bot$ with the goal).
Prolog-Based Reconstruction Engine: A concise (<500 lines) Prolog script that handles the complex task of reconstructing proof terms from TSTP proofs, leveraging Prolog's native backtracking and unification to handle variable renaming and inference matching efficiently.
Handling Edge Cases: The system addresses domain emptiness (a difference between classical and constructive logic) by checking for inhabited sorts and leaving holes for the user if necessary.

4. Results

The authors evaluated the prototype on a real-world formalization case study involving Fast Fourier Transform (FFT) algorithms and roots of unity in a commutative ring.

Complexity: The case study involved a complex field with roots of unity, requiring the verification of 12 theorems (8 ring properties, 4 root-of-unity properties).
Performance:
- A professional Agda developer required two full days to manually construct these proofs.
- The prototype system automatically discharged all 12 theorems in a fraction of a second.
- The generated proofs were approximately 300 lines of code each but were verified by Agda's type checker.
Robustness: The system successfully handled the CASC (CADE ATP System Competition) portfolio of strategies, demonstrating that the lightweight approach works even with the full range of Vampire's inference capabilities.

5. Significance

Bridging the Gap: This work demonstrates that a carefully chosen fragment of dependent type theory can serve as a robust bridge between interactive and automated provers, enabling substantial automation without sacrificing the "trusted core" guarantees of ITPs.
Practicality: It proves that "hammer" style automation is feasible for Agda, a system previously lacking strong built-in automation, significantly reducing the development burden for formalizing complex algebraic structures.
Extensibility: The methodology is not tied to Agda or Vampire. The authors argue it can be adapted to other dependently-typed assistants (like Lean or Idris) and other ATPs (like E or Zipperposition) with minimal engineering effort.
Future Directions: The paper outlines paths to expand the supported fragment (e.g., handling parameterized types and proof-relevant types) and improving the readability of generated proofs, moving toward a full-fledged hammer system for dependently-typed logic.

In summary, "When Agda met Vampire" presents a pragmatic and highly effective solution to the automation bottleneck in dependently-typed proof assistants, leveraging the strengths of both constructive type theory and classical automated reasoning through a clever, low-overhead translation layer.