TL;DR
This paper introduces Duper, a new theorem prover for Lean that uses the superposition calculus to automatically generate proofs. It's designed to work seamlessly within Lean's dependently typed environment and aims to bridge the gap between interactive and automated theorem proving by producing verifiable proofs that can be used by future "hammer" tools.
What Problem Does This Paper Address?
Interactive theorem provers (ITPs) like Lean offer high confidence in proofs but require significant user effort. Automated theorem provers (ATPs) are convenient but often limited in scope and don't provide strong correctness guarantees. "Hammer" tools aim to combine these by using ATPs to find proofs and then reconstructing them within the ITP. However, existing hammers are often limited to simpler logics. Dependent type theories (DTTs), like the one used in Lean, offer greater expressivity but introduce significant challenges for automation, such as complex unification and implicit argument inference. There was a need for a proof-producing ATP specifically designed for DTTs like Lean, capable of handling its unique complexities and producing proofs that can be integrated back into the ITP.
Methods
Duper is built upon the superposition calculus, a well-established technique for automated reasoning. Its core innovation lies in adapting this calculus to the specific demands of dependent type theory. Key methodological aspects include:
- Proof-Producing Superposition: Duper doesn't just find a proof; it generates a proof term directly in Lean's axiomatic foundation. This is crucial for verification within the ITP.
- Native Dependent Type Theory Reasoning: Instead of translating problems into a simpler logic (which can lose expressivity or become intractable), Duper directly handles DTT features. This involves specialized handling of:
- Higher-Order Unification: Extended to support DTT, allowing for more flexible variable instantiations.
- Type Class Inference: Integrated into the reasoning process.
- Universe Polymorphism: Handled natively to reason about theorems that apply across different type universes.
- Inhabitation Reasoning: Explicitly reasoning about whether types are empty, which is critical for the soundness of certain inferences in DTT.
- Main Saturation Loop (DISCOUNT variant): Duper employs a given-clause procedure, similar to other saturation-based provers, but adapted for DTT. This involves managing active and passive sets of clauses and iteratively deriving new facts.
- Proof Reconstruction: When a contradiction is found, Duper uses the derived clauses to construct a proof term. This process is carefully designed to pair each inference rule with a corresponding proof reconstruction procedure.
- Transfer Expressions: A novel mechanism to pass necessary information (beyond just parent proof terms) to proof reconstruction procedures, particularly for complex higher-order rules.
- Monomorphization (via LeanAuto): A preprocessing step (handled by a separate tool, LeanAuto) that simplifies the problem by abstracting away type class instances and identifying definitionally equal expressions, making the problem more amenable to the core prover.
Datasets
The paper evaluates Duper on benchmarks from:
- Seventeen Provers under the Hammer [16]: These are provided in both first-order (FOF) and typed higher-order (THF) formats.
- GRUNGE: A Grand Unified ATP Challenge [11]: Also provided in FOF and THF formats.
The evaluation uses both the original benchmark problems and "minimized" versions where only axioms relevant to the proof are kept.
Key Insights and Ideas
- DTT is a significant hurdle for ATPs: The expressivity of dependent types, while powerful for interactive proof, makes automated reasoning much harder due to complex unification and implicit reasoning.
- Native DTT support is key: Translating DTT problems to simpler logics is often insufficient. Duper's approach of handling DTT features directly is crucial for its effectiveness.
- Proof reconstruction is a first-class citizen: Duper is designed from the ground up to produce verifiable proofs, not just answers. This is essential for its role in future hammer tools.
- Inhabitation reasoning is non-trivial but necessary: The possibility of empty types in DTT requires careful handling to avoid unsound inferences, and Duper integrates this reasoning into its saturation loop.
- Monomorphization is a powerful preprocessing step: Offloading type class resolution and expression normalization to a separate tool significantly simplifies the core prover's task.
Key Results
- Performance Comparison: Duper's performance is comparable to established provers like Metis on standard benchmarks.
- On original benchmark problems (30-second timeout): Duper (-) solved 1176/5000 FOF problems (16 facts) and 1111/5000 THF problems (16 facts). Duper (+) (with expensive rules) performed slightly worse on FOF but better on THF. Metis outperformed Duper on FOF.
- On minimized benchmark problems (from Vampire/Zipperposition): Duper and Metis performed very similarly, with less than a 2% disparity on FOF problems. This suggests Duper is effective at reconstructing proofs generated by more powerful provers.
- Expensive Rules: Enabling "expensive" rules (inspired by Zipperposition) generally hurt Duper's performance on FOF problems but helped on THF problems, suggesting these rules are more relevant for higher-order reasoning.
- Niche for DTT: The paper highlights that Duper can handle problems that require native higher-order reasoning, which might be intractable for provers that rely on first-order translations.
Limitations and Future Work
- Relevance Filter: Duper currently requires users to manually supply relevant lemmas. Integrating a relevance filter would significantly improve its usability.
- Hammer Integration: The primary future work is to integrate Duper into a full Lean hammer pipeline, which would drastically increase its usefulness.
- Experimental Scope: The current evaluation is limited to TPTP benchmarks, which are primarily first-order or higher-order. Evaluating Duper on benchmarks directly from Lean's Mathlib library is a desired next step.
- Performance Tuning: Further optimization of Duper's performance, particularly for specific types of problems, is an ongoing area.
Summary updated