Verifying an Open Compiler Using Multi-Language Semantics

James T. Perconti and Amal Ahmed



Existing verified compilers are proved correct under a closed-world assumption, i.e., that the compiler will only be used to compile whole programs. We present a new methodology for verifying correct compilation of program components, while formally allowing linking with target code of arbitrary prove- nance. To demonstrate our methodology, we present a two-pass type-preserving open compiler and prove that compilation preserves semantics. The central novelty of our approach is that we define a combined language that embeds the source, intermediate, and target languages and formalizes a semantics of interoperability between them, using boundaries in the style of Matthews and Findler. Compiler correctness is stated as contextual equivalence in the combined language.