[TOPLAS] Denotation-based Compositional Compiler Verification
This program is tentative and subject to change.
A desired but challenging property of compiler verification is compositionality, in the sense that the compilation correctness of a program can be deduced incrementally from that of its substructures ranging from statements, functions, and modules. This article proposes a novel compiler verification framework based on denotational semantics for better compositionality, compared to previous approaches based on small-step operational semantics and simulation theories. Our denotational semantics is defined by semantic functions that map a syntactic component to a semantic domain composed of multiple behavioral sets, with compiler correctness established through behavior refinement between the semantic domains of the source and target programs. The main contributions of this article include proposing a denotational semantics for open modules, a novel semantic linking operator, and a refinement algebra that unifies various behavior refinements, making compiler verification structured and compositional. Furthermore, our formalization captures the full meaning of a program and bridges the gap between traditional power-domain-based denotational semantics and the practical needs of compiler verification. We apply our denotation-based framework to verify the front-end of CompCert and typical optimizations on simple prototypes of imperative languages. Our results demonstrate that the compositionality from sub-statements to statements, from functions to modules, and from modules to the whole program can be effectively achieved.
This program is tentative and subject to change.
Fri 19 JunDisplayed time zone: Mountain Time (US & Canada) change
10:30 - 12:10 | |||
10:30 20mTalk | Let It Flow: A Formally Verified Compilation Framework for Asynchronous Dataflow PLDI Research Papers Zhengyao Lin Carnegie Mellon University, Yi Cai University of Maryland at College Park, Milijana Surbatovich University of Maryland at College Park DOI | ||
10:50 20mTalk | Compiling to Recurrent Neurons PLDI Research Papers Joey Velez-Ginorio University of Pennsylvania, Nada Amin Harvard University, Konrad Kording University of Pennsylvania, Steve Zdancewic University of Pennsylvania DOI | ||
11:10 20mTalk | [TOPLAS] Denotation-based Compositional Compiler Verification PLDI Research Papers Zhang Cheng Shanghai Jiao Tong University, Jiyang Wu , Di Wang Peking University, Qinxiang Cao Shanghai Jiao Tong University | ||
11:30 20mTalk | Responsive Parallelism with Dynamic and First-Class Priorities PLDI Research Papers Marelle León Illinois Institute of Technology, My Dinh Illinois Institute of Technology, Stefan K. Muller University of Connecticut DOI | ||
11:50 20mTalk | Escape with Your Self: Sound and Expressive Bidirectional Typing with Avoidance for Reachability Types PLDI Research Papers Songlin Jia Purdue University, Guannan Wei Tufts University, Siyuan He Purdue University, Yuyan Bao Augusta University, Tiark Rompf Purdue University DOI | ||