University of British Columbia
Compilation as normalization : a multi-language semantics approach to compiler correctness
Abstract
dc:descriptionModern compiler projects link together diverse components, which may come from multiple source languages and be at varying stages of compilation. Compositional compiler correctness (CCC), a property which captures these intricacies, has previously required complex semantic proof theories to reason about interoperation between linked programs. We present a purely syntactic approach for specifying and proving CCC that models compilation entirely as a reduction system. This allows us to use established techniques from term rewriting systems (TRS). To illustrate our method, we define a formal model of an A-Normal Form (ANF) compiler using a multi-language operational semantics and show that CCC reduces to confluence, a property of rewrite systems. We also explore several common techniques for proving confluence and prove several related but weaker properties to motivate that the property should hold for the model.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Bryant, Lily
- Contributors dc:contributor
-
- Bowman, William J. (Professor of computer science)
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/89101