Several induction theorem provers have been developed which support mechanized verification of functional programs. Unfortunately, a major problem is that they often fail in verifying tail recursive functions (which correspond to imperative programs). However, in practice imperative programs are used almost exclusively. We present an automatic transformation to tackle this problem. It transforms functions which are hard to verify into functions whose correctness can be shown by the existing provers. In contrast to classical program transformations, the aim of our technique is not to increase efficiency, but to increase verifiability. Therefore, this paper introduces a novel application area for program transformations and it shows that such techniques can in fact solve some of the most urgent current challenge problems in automated verification and induction theorem proving.
['Jürgen Giesl']
Context-Moving Transformations for Function Verification