Extending SMT Solvers to Higher-Order Logic

Haniel Barbosa, Andrew Reynolds, Daniel El Ouraoui, Cesare Tinelli, Clark W. Barrett

TL;DR

This paper tackles the challenge of enabling Satisfiability Modulo Theories (SMT) solvers, powerful tools for first-order logic reasoning, to handle higher-order logic (HOL). They propose two pragmatic approaches to extend existing SMT solvers, demonstrating competitive performance against specialized HOL provers and often outperforming traditional HOL-to-FOL encoding methods.

What Problem Does This Paper Address?

SMT solvers are incredibly effective at reasoning about first-order logic (FOL) formulas, forming the backbone of many automated reasoning systems. However, many real-world applications, particularly in proof assistants, require the expressiveness of higher-order logic (HOL). While HOL allows for quantification over functions and predicates, extending SMT solvers to natively support HOL is largely an unexplored area. Traditional approaches involve encoding HOL problems into FOL, which can lead to performance issues, soundness concerns, or incompleteness. This paper aims to bridge this gap by presenting methods to extend existing SMT solvers to directly handle HOL, leveraging their existing efficiency for FOL reasoning.

Methods

The authors propose two main strategies for extending SMT solvers to support HOL reasoning (HOSMT):

  • Pragmatic Extension: This approach modifies existing, highly optimized SMT solvers with minimal changes to their core data structures and algorithms. The key techniques involve:
  • Eliminating λ-abstractions: Using a technique called λ-lifting to transform λ-abstractions into fresh function symbols and quantified formulas, making the formulas λ-free.
  • Extending the Ground Solver: Adapting the decision procedure for equality and uninterpreted functions (EUF) to handle partial applications and extensionality. This involves a lazy applicative encoding where only partial applications are converted.
  • Extending Quantifier Instantiation: Adapting E-matching techniques to handle higher-order variables and functional equality, a significant challenge.
  • Redesign Approach: This strategy involves a more fundamental redesign of an SMT solver's data structures and algorithms specifically for HOL reasoning. This approach is better suited for less optimized, lightweight solvers and offers more flexibility for future HOL-specific techniques. The paper outlines a redesigned core ground solver using an E-graph and a modified congruence closure algorithm.

Crucially, both approaches avoid implementing full higher-order unification, which is undecidable, and instead rely on other techniques to manage HOL reasoning.

Datasets

The paper evaluates their approaches on several benchmark sets:

  • TPTP (Thousands of Problems for Theorem Provers): A collection of 1,253 provable HOL goals, encoded into λ-free monomorphic HOL problems. These are further categorized based on the number of facts used (e.g., JD, JD32, JD512) and whether λ-abstractions are removed via λ-lifting or SK-style combinators.
  • Sledgehammer (SH) benchmarks: A set of 832 provable goals randomly selected from Isabelle theories, encoded with 1,024 facts.
  • TH0, oTH0, λoTH0: Subsets of the TPTP benchmarks, categorized by the presence of λ-free and first-class Boolean features.

The authors also mention using the SMT-LIB standard test suite to evaluate the performance of their extensions on FOL benchmarks.

Key Insights and Ideas

  • Pragmatism Pays Off: The pragmatic extension, which minimally modifies existing SMT solvers, proves to be highly effective, achieving competitive results without a complete overhaul. This suggests that the robust infrastructure of modern SMT solvers can be effectively leveraged for HOL.
  • λ-Lifting as a Sweet Spot: Using λ-lifting for eliminating λ-abstractions is presented as a pragmatic choice that avoids the performance penalties of combinator-based approaches while still enabling HOL reasoning.
  • Lazy Applicative Encoding: Instead of a full upfront encoding of HOL to FOL, a lazy approach that converts only partial applications is shown to be efficient for the ground solver.
  • The Power of Axioms: Even without full HOL unification, judiciously chosen axioms (like the "store axiom" or SAX) can significantly improve the performance of the pragmatic extension, enabling it to solve problems that would otherwise be intractable.
  • Redesign Offers Potential: While the pragmatic approach is effective, the redesign approach highlights the potential for even greater gains by building HOL reasoning capabilities directly into the solver's architecture.

Key Results

  • Competitive Performance: The pragmatic extension of CVC4 (cvc and cvc-sax) and the redesigned veriT (vt) demonstrate performance competitive with state-of-the-art HOL provers like Leo-III and Satallax on various benchmark sets.
  • Outperforming Encoding: In many cases, the proposed extensions outperform the traditional approach of encoding HOL problems into FOL.
  • Minimal Impact on FOL Performance: The extensions to CVC4 and veriT do not significantly compromise their performance on FOL benchmarks. The redesigned veriT, in particular, shows strong performance on the QF_UF category of SMT-LIB.
  • Model Finding Capabilities: The paper also explores countermodel generation for HOL conjectures, showing that the redesigned veriT (cvc-fmf) significantly outperforms its standard encoding-based counterpart in this area.

Limitations and Future Work

  • No HOL Unification: The current approaches do not implement higher-order unification, which is undecidable. This limits their ability to solve certain problems that inherently require it. The authors explicitly state that extending instantiation techniques with HO unification is a significant challenge for future work.
  • Redesign Complexity: While the redesign approach offers potential, it requires a more substantial effort in terms of solver development.
  • Model Soundness: The paper notes that the @cvc-fmf solver is only model-sound when combined with the "-sax" option, indicating a limitation in its standalone model-finding capabilities for HOL.
  • Further Instantiation Techniques: The authors mention that extending other instantiation techniques (like model-based) for HOL is left as future work.
  • Scalability with Facts: While the Sledgehammer benchmarks show that handling more facts is crucial, the paper suggests that further advancements are needed to fully address scalability challenges.

Summary updated

Abstract

SMT solvers have throughout the years been able to cope with increasingly expressive formulas, from ground logics to full first-order logic (FOL). In contrast, the extension of SMT solvers to higher-order logic (HOL) is mostly unexplored. We propose a pragmatic extension for SMT solvers to support HOL reasoning natively without compromising performance on FOL reasoning, thus leveraging the extensive research and implementation efforts dedicated to efficient SMT solving. We show how to generalize data structures and the ground decision procedure to support partial applications and extensionality, as well as how to reconcile quantifier instantiation techniques with higher-order variables. We also discuss a separate approach for redesigning an HOL SMT solver from the ground up via new data structures and algorithms. We apply our pragmatic extension to the CVC4 SMT solver and discuss a redesign of the veriT SMT solver. Our evaluation shows they are competitive with state-of-the-art HOL provers and often outperform the traditional encoding into FOL.
BibTeX
@inproceedings{barbosa2019extending,
  author = {Haniel Barbosa and Andrew Reynolds and Daniel El Ouraoui and Cesare Tinelli and Clark W. Barrett},
  title = {{Extending SMT Solvers to Higher-Order Logic}},
  booktitle = {CADE},
  year = {2019},
  doi = {10.1007/978-3-030-29436-6\_3},
}
Figure