We report on work in progress on automatic procedures for proving properties of programs written in higher-order functional languages. Our approach encodes higher-order programs directly as first-order SMT problems over Horn clauses. It is straight-forward to reduce Hoare-style verification of first-order programs into satisfiability of Horn clauses. The presence of closures offers several challenges: relatively complete proof systems have to account for closures; and in practice, the effectiveness of search procedures depend on encoding strategies and capabilities of underlying solvers. We here use algebraic data-types to encode closures and rely on solvers that support algebraic datatypes. The viability of the approach is examined using examples from [14] . Automatic verification of programs in higher-order languages has received significant attention in recent years. The Liquid Type systems have been used successfully on a large set of challenges from Ocaml [12] and Haskell [15] . Liquid types rely checking program properties as type checking of refinement types. Not all refinement types need to be provided fully, instead users can supply a space of templates that the type inference engine instantiates and refines the template invariants (using the Houdini approach [4]). A very different approach is taken in HALO [16] where the denotational semantics of Haskell, using types that include error states, is encoded using quantified equalities. HALO relies on quantifier instantiation engines and finite model building capabilities to discharge correctness proof conditions. Unno et.al. [14] develop a custom engine that realizes proof rules for Hoare logic for programs with procedure parameters [5] . There are several other systems that use first-order/SMT technologies for establishing properties of higher-order languages. They typically rely on user-annotated refinement types. The executable subset of the PVS specification language uses decision procedures for discharging type checking conditions and the F⋆ system includes verification condition generation from a higher-order language with higher-order refinement types. These systems have in common that they rely on SMT solvers, CVC4, Yices and Z3. We are here examining whether program verification (in the presence of closures) can be reduced directly to SMT solving.
A method to verify higher-order programs more directly using first-order constrained Horn clauses has been suggested by REF .
Higher-order Program Verification as Satisfiability Modulo Theories with Algebraic Data-types
ArXiv
ArXiv
Mathematics Computer Science