The Proof Monad

Abstract

A formalism for expressing the operational semantics of proof languages used in procedural theorem provers is proposed. It is argued that this formalism provides an elegant way to describe the computational features of proof languages, such as side effects, exception handling, and backtracking. The formalism, called proof monads, finds its roots in category theory, and in particular satisfies the monad laws. It is shown that the framework’s monadic operators are related to fundamental tactics and strategies in procedural theorem provers. Finally, the paper illustrates how proof monads can be used to implement semantically clean control structure mechanisms in actual proof languages.

Keywords: Proof languages, Deductive strategies, Category theory, Monadic structures