Denotation-based Compositional Compiler Verification
ACM Transactions on Programming Languages and Systems · 31.03.2026 · 48 (1) · 1-65
DOI: 10.1145/3797874 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Programming Languages and Systems, online erschienen am 23.03.2026. Verfasst von Zhang Cheng und 3 weiteren Autor:innen. Die Arbeit nennt 79 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
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.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Cheng, Z., Wu, J., Wang, D., & Cao, Q. (2026). Denotation-based Compositional Compiler Verification. ACM Transactions on Programming Languages and Systems, 48(1), 1-65. https://doi.org/10.1145/3797874
Vancouver
Cheng Z, Wu J, Wang D, Cao Q. Denotation-based Compositional Compiler Verification. ACM Transactions on Programming Languages and Systems. 2026;48(1):1-65. doi:10.1145/3797874
BibTeX
@article{Cheng2026,
author = {Cheng, Zhang and Wu, Jiyang and Wang, Di and Cao, Qinxiang},
title = {Denotation-based Compositional Compiler Verification},
journal = {ACM Transactions on Programming Languages and Systems},
year = {2026},
volume = {48},
number = {1},
pages = {1--65},
doi = {10.1145/3797874}
}
EUVIMED