Formal polytypic programs and proofs

Abstract

The aim of our work is to be able to do fully formal, machine-verified proofs over Generic Haskell-style polytypic programs. In order to achieve this goal, we embed polytypic programming in the proof assistant Coq and provide an infrastructure for polytypic proofs. Polytypic functions are reified within Coq as a datatype and they can then be specialized by applying a dependently typed term specialization function. Polytypic functions are thus first-class citizens and can be passed as arguments or returned as results. Likewise, we reify polytypic proofs as a datatype and provide a lemma that a polytypic proof can be specialized to any datatype in the universe. The correspondence between polytypic functions and their polytypic proofs is very clear: programmers need to give proofs for, and only for, the same cases that they need to give instances for when they define the polytypic function itself. Finally, we discuss how to write (co)recursive functions and do (co)recursive proofs in a similar way that recursion is handled in Generic Haskell.