Strength Induction in a Haskell Program Verifier

AbstractHaskell employs a melange of strict and non-strict evaluation semantics, hence a Haskell verifier should be capable of checking assumptions that program variables may or may not denote well-defined values. The paper introduces a new strategy, called strength induction, that supports automatic checking of definedness assumptions.Strength induction has been implemented in Plover, an automated property-verifier for Haskell programs that has been under development for the past three years as a component of the Programatica project. In Programatica, predicate definitions and property assertions written in P-logic, a programming logic for Haskell, can be embedded in the text of a Haskell program module. Properties refine the type system of Haskell but cannot be verified by type-checking alone; a more powerful logical verifier is required.Plover codes the proof rules of P-logic, and additionally, embeds strategies and decision procedures for their application and discharge. It integrates a reduction system that implements a rewriting semantics for Haskell terms with a congruence-closure algorithm that supports reasoning with equality