A Shorter Compiler Correctness Proof for Language IMP

Title:	A Shorter Compiler Correctness Proof for Language IMP
Author:	Pasquale Noce (pasquale /dot/ noce /dot/ lavoro /at/ gmail /dot/ com)
Submission date:	2021-06-04
Abstract:	This paper presents a compiler correctness proof for the didactic imperative programming language IMP, introduced in Nipkow and Klein's book on formal programming language semantics (version of March 2021), whose size is just two thirds of the book's proof in the number of formal text lines. As such, it promises to constitute a further enhanced reference for the formal verification of compilers meant for larger, real-world programming languages. The presented proof does not depend on language determinism, so that the proposed approach can be applied to non-deterministic languages as well. As a confirmation, this paper extends IMP with an additional non-deterministic choice command, and proves compiler correctness, viz. the simulation of compiled code execution by source code, for such extended language.
BibTeX:	@article{IMP_Compiler-AFP, author = {Pasquale Noce}, title = {A Shorter Compiler Correctness Proof for Language IMP}, journal = {Archive of Formal Proofs}, month = jun, year = 2021, note = {\url{https://isa-afp.org/entries/IMP_Compiler.html}, Formal proof development}, ISSN = {2150-914x}, }
License:	BSD License
Status: [ok]	This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.