Back to search

University of Kent,

Verified compilation of a purely functional language to a realistic machine semantics

Abstract

dc:description.abstract

Formal verification of a compiler offers the ultimate understanding of the behaviour of compiled code: a mathematical proof relates the semantics of each output program to that of its corresponding input. Users can rely on the same formally-specified understanding of source-level behaviour as the compiler, so any reasoning about source code applies equally to the machine code which is actually executed. Critically, these guarantees demand faith only in a minimal trusted computing base (TCB). To date, only two general-purpose, end-to-end verified compilers exist: CompCert and CakeML, which compile a C-like and an ML-like language respectively. In this dissertation, I advance the state of the art in general-purpose, end-to-end compiler verification in two ways. First, I present PureCake, the first such verified compiler for a purely functional, Haskell-like language. Second, I derive the first compiler correctness theorem backed by a realistic machine semantics, that is, an official specification for the Armv8 instruction set architecture. Both advancements build on CakeML. PureCake extends CakeML's guarantees outwards, using it as an unmodified building block to demonstrate that we can reuse verified compilers as we do unverified ones. The key difference is that reuse of a verified compiler must consider not only its external implementation interface, but also its proof interface: its top-level theorems and TCB. Conversely, a realistic machine semantics for Armv8 strengthens the root of CakeML's trust, reducing its TCB. Now, both CakeML and the hardware it targets share a common understanding of Armv8 behaviour which is derived from the same official sources. Composing these two advancements fulfils the title of this dissertation: PureCake has an end-to-end correctness theorem which spans from a purely functional, Haskell-like language to a realistic, official machine semantics.

Degree

thesis:*
Name dc:type.qualificationname
phd
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Kent,
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kanabar, Hrutvik
Advisor dc:contributor.advisor
  • Chitil, Olaf

Subjects

dc:subject × 1

Rights

Language dc:language
en

Chain of custody

source
Harvested from
University of Kent
Base URL
kar.kent.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kanabar, Hrutvik. Verified compilation of a purely functional language to a realistic machine semantics. doctoral thesis, University of Kent,, 2024.