TL;DR
This paper presents "Kalas," a verified, end-to-end compiler for a choreographic language. It bridges the gap between high-level, deadlock-free system descriptions and concrete, executable machine code, ensuring that the global communication guarantees are preserved throughout the compilation process. This work is significant because it provides a path towards building truly correct communicating systems by combining formal verification with practical implementation.
What Problem Does This Paper Address?
Building reliable, distributed, and communicating systems is notoriously difficult. While concurrency theory offers elegant ways to describe such systems and prove their properties (like deadlock freedom), bridging the gap to actual, low-level implementations has been a major challenge. Traditional approaches often involve writing separate programs for each participant, which can lead to subtle communication mismatches and bugs. Choreographic programming offers a solution by describing the global behavior of the system, guaranteeing properties like deadlock freedom by construction. However, compiling these high-level choreographies into efficient, executable code for each individual endpoint while preserving these guarantees is a complex task. This paper addresses the problem of creating a compiler that not only translates choreographies into code but also provides a machine-checked proof of its correctness, ensuring that the generated code behaves exactly as the original choreography intended, all the way down to machine code.
Methods
The paper introduces "Kalas," a choreographic language, and a verified, five-phase compiler. The core of their approach is a machine-checked, end-to-end proof of correctness using the HOL4 interactive theorem prover and the verified CakeML compiler.
Here's a breakdown of the compilation phases:
- Endpoint Projection: The global choreography is translated into a parallel composition of sequential programs for each endpoint, represented in an intermediate language called ENDPOINT.
- Refining Choice: ENDPOINT's choice primitives are encoded using simpler send and receive actions, simplifying subsequent phases.
- Splitting Large Messages: Messages are broken down into fixed-size chunks, reflecting real-world communication protocols and introducing a new intermediate language, PAYLOAD. This phase is more proof-relevant than implementation-relevant.
- Introducing Closures: The fixpoint operator in Kalas is translated into
letrecprimitives, aligning with functional programming idioms and preparing for CakeML's environment semantics. - Compilation into CakeML: The PAYLOAD endpoints are compiled into CakeML, a verified, sequential, functional programming language. This phase leverages CakeML's verified compiler, which extends down to machine code.
The correctness of each phase is formally proven, and these proofs are composed to establish the overall end-to-end correctness of the compiler. The proof relies heavily on techniques like local confluence and inert reduction to manage the complexity of asynchronous communication and interleavings.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- End-to-End Verified Compilation is Crucial: The paper emphasizes that simply verifying the compilation of individual phases isn't enough. An end-to-end proof is necessary to guarantee that the global properties of the choreography (like deadlock freedom) are preserved all the way to the machine code.
- Choreography as a Global Contract: Kalas treats choreographies as a global contract that dictates the communication behavior of all participants. This "by-construction" approach to deadlock freedom is a key advantage.
- Leveraging Existing Verified Tools: The project effectively reuses existing verified infrastructure, particularly the CakeML compiler, to achieve verified compilation down to machine code. This is a pragmatic approach to building complex verified systems.
- The Challenge of Asynchrony and Interleavings: The paper highlights the significant proof challenges posed by asynchronous communication and the combinatorial explosion of possible interleavings. Techniques like local confluence and inert reduction are vital for taming these complexities.
- Projectability as a Key Criterion: For endpoint projection to work correctly, certain criteria must be met to ensure that choices made by one endpoint can be communicated to others without ambiguity. This concept of "projectability" is formalized and used to guide the compilation process.
Key Results
- The paper presents a verified, end-to-end compiler for the choreographic language Kalas.
- The compiler translates Kalas choreographies into executable CakeML code, which can then be compiled to machine code.
- The compiler's correctness is proven using machine-checked proofs in HOL4, ensuring that the generated code preserves the deadlock-freedom guarantees of the original choreography.
- A proof-of-concept deployment on the seL4 microkernel is demonstrated, showcasing the practical applicability of the verified compiler.
Limitations and Future Work
- Data Types Beyond Strings: The current model primarily deals with strings for communication. Future work could extend this to support arbitrary data types, requiring verified marshalling and de-marshalling.
- Unbounded Message Queues: The model assumes unbounded message queues, which is unrealistic. Investigating deadlock freedom in a model with bounded, non-lossy queues is suggested.
- Projectability Criteria: Exploring alternative semantics (e.g., co-inductive observational semantics) and more relaxed projectability criteria could simplify proofs and enhance flexibility.
- Livelock and Memory: While deadlock freedom is guaranteed, the "unless the compiler output runs out of memory" caveat from CakeML's correctness theorem means liveness properties are not fully guaranteed at the machine code level. Further work could address this with verified space-cost semantics.
- Communication Backends: While a seL4-based IPC backend was used, deploying on other backends like TCP/IP would demonstrate verified distributed computation over the internet.
Summary updated