The Curry-Howard Isomorphism Adapted for Imperative Program Synthesis and Reasoning

The Curry-Howard isomorphism permits the representation of intuitionistic logic as a constructive type thoery. It has often been exploited in the implementation of interactive theorem provers. It also forms the basis of the proofs-asprograms paradigm, an approach to the synthesis of functional programs from intuitionistic proofs (see e.g., [1-3]). In this paper, we present a constructive logical system for reasoning about imperative programs to which the Curry- Howard isomosphism may be adapted. This allows us to take advantage of the isomorphism for theorem proving implementation, and for the synthesis of correct imperative programs, following the proofs-as-programs paradigm.