Semantics-Directed Compiler Construction: From Formal Semantics to Certified Compilers

Compilers are central to computing, translating programs written by people into code for machines. Some aspects of compiler development, such as syntax analysis, bridge the theory and the implementation in a principled way, with lexers and parsers being algorithmically derived from high-level specifications. On the other hand, there is currently an unbridged gap between the theoretical specification of a programming language, given by a formal semantics, and the code produced by the compiler. Relating the two post hoc is possible, but difficult and rarely done. However, it doesn't have to be this way.

A more principled approach is to begin with a semantics for the language, and seek to derive an implementation that is correct-by-construction. The investigators (Graham Hutton and Dan Ghica) have independently developed two such methodologies, which are based on complementary approaches to semantics (evaluators and abstract machines), but utilise different approaches to syntax (trees and graphs). The aim of this project is to reconcile the two methodologies to develop scalable and reusable frameworks for constructing certified compilers from semantics.

The project combines the strengths of two leading research groups, is enhanced by a team of expert collaborators (Patrick Bahr, Mario Lavarez-Picallo, Edwin Brady, Simon Marlow, Anil Madhavapeddy, and Beniamino Accattoli), and is supported by fully-funded PhD studentships from the host departments.