Pilsner: a compositionally verified compiler for a higher-order imperative language

Georg Neis, Chung-Kil Hur, Jan-Oliver Kaiser, Craig McLaughlin, Derek Dreyer, Viktor VafeiadisICFP 2015 · DOI

TL;DR

This paper introduces Pilsner, the first compositionally verified compiler for a higher-order imperative language. It achieves this by developing a novel technique called Parametric Inter-Language Simulations (PILS), which allows for modular and transitive proofs of compiler correctness, enabling the safe linking of separately compiled modules.

What Problem Does This Paper Address?

Traditionally, compiler verification has focused on proving the correctness of entire programs. This is a significant achievement, as demonstrated by projects like CompCert. However, in real-world software development, programs are often built from multiple independently compiled modules. This practice, known as separate compilation, poses a challenge for traditional compiler verification because it requires a notion of correctness that applies to individual modules and can be composed transitively through linking. Existing approaches often fall short in one or more of these crucial aspects: modularity (correctness preserved under linking), transitivity (proofs can be chained), and flexibility (applicability to diverse languages and transformations). The paper addresses this gap by developing a compositional verification method that satisfies all three desiderata.

Methods

The core innovation of this paper is the development of Parametric Inter-Language Simulations (PILS). PILS build upon two prior lines of research:

  • Parametric Bisimulations (PBs): A simulation method for higher-order imperative languages designed to be modular and transitive, and capable of inter-language reasoning.
  • Kripke Logical Relations (KLRs): A rich and flexible approach for inter-language reasoning, but lacking transitivity.

PILS combine the strengths of PBs and KLRs. They introduce a formal relation between target and source modules that captures semantics preservation. This relation is designed to be:

  • Modular: Correctness is defined at the module level and preserved under linking. If module A refines A' and module B refines B', then linking A and B refines linking A' and B'.
  • Transitive: Proofs of correctness can be composed sequentially, allowing for verification of multi-pass compilers by proving each pass independently.
  • Flexible: The method imposes minimal restrictions on program transformations and language features, allowing for the linking of code from different compilers or even hand-optimized code.

The paper also details the structure of the Pilsner compiler, which translates a higher-order imperative language (S) through a CPS-based intermediate language (I) to an idealized assembly-like target language (T). Pilsner includes several optimization passes at the intermediate level.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Compositionality is Key for Modern Software: The paper strongly argues that for practical software engineering, compiler verification must move beyond whole-program proofs to embrace compositional verification that supports separate compilation.
  • PILS as a Unifying Framework: PILS elegantly bridge the gap between modularity and transitivity, which were often conflicting goals in previous compositional verification approaches.
  • Flexibility for Heterogeneous Systems: The PILS framework is designed to be flexible enough to handle diverse program transformations and even link code produced by different compilers or hand-written assembly. This is crucial for real-world scenarios where not all code might originate from a single verified compiler.
  • "Awkward" Example as a Benchmark: The paper demonstrates the flexibility of PILS by verifying a challenging "awkward" example involving self-modifying machine code, a feat previously achieved with KLRs. This highlights the power of PILS in handling low-level, state-manipulating transformations.
  • Untyped Intermediate Languages are Manageable: The paper shows that PILS can effectively handle untyped intermediate languages, which are common in compiler design, by adapting the verification framework.

Key Results

  • Pilsner Compiler Verified: The paper presents Pilsner, a multi-pass optimizing compiler for a higher-order imperative language, which has been compositionally and mechanically verified using PILS. This is a significant achievement, representing over 48,000 lines of Coq proof code.
  • Formal Guarantees for Separate Compilation: The paper provides formal theorems (Theorems 1, 2, and 3) that establish the modularity and adequacy of the PILS framework, guaranteeing that separately compiled modules can be safely linked.
  • Transitivity Demonstrated: Theorem 4 formally proves the transitivity of the PILS approach, enabling the verification of multi-pass compilers by composing proofs of individual passes.
  • Flexibility Shown: The paper demonstrates the flexibility of PILS by successfully verifying a complex self-modifying code example, showcasing its ability to handle intricate low-level transformations.

Limitations and Future Work

  • Language Genericity: While PILS are defined in a language-generic way, the metatheory for transitivity and adequacy is not fully generic and requires instantiation for specific language pairs. The authors suggest that further work could axiomatize properties of abstract languages to achieve greater genericity.
  • Source Language Specificity: The current generic PILS model is somewhat tied to the type structure of the source language S. Extending it to support multiple source languages and their interoperability is identified as future work.
  • Eta Law for Functions: The paper notes that PILS, like PBs, do not admit the eta law for function values. While a solution exists, it has not yet been incorporated into PILS.
  • Non-Determinism Handling: While the paper discusses handling non-determinism by making configurations deterministic, it acknowledges that this can be restrictive. Future work could explore more flexible approaches to non-determinism.
  • Realism of Target Language: The target language T is an idealized assembly language. Extending the verification to more realistic machine models would be a valuable next step.

Summary updated

BibTeX
@inproceedings{neis2015pilsner,
  author = {Georg Neis and Chung-Kil Hur and Jan-Oliver Kaiser and Craig McLaughlin and Derek Dreyer and Viktor Vafeiadis},
  title = {{Pilsner: a compositionally verified compiler for a higher-order imperative language}},
  booktitle = {ICFP},
  year = {2015},
  doi = {10.1145/2784731.2784764},
}
Figure