Complete First-Order Reasoning for Properties of Functional Programs
summary
The paper proves that the unfolding-then-SMT procedure (USMT heuristic) used by Liquid Haskell, Leon and Stainless is sound and complete for the combined first-order theory of algebraic datatypes plus decidable background theories: every VC valid in the agatized models is eventually discharged by USMT, and every USMT success is valid in those models. Failures coincide with rogue non-standard models (e.g., infinite lists); a practical remedy is user-supplied inductive lemmas, assuming definitions are provably acyclic (ranking-function termination), and the authors give a model-construction proof and diagnostics tying this to real tool benchmarks.
AI-written summary · about