Abstract Interpreters: A Monadic Approach to Modular Verification
Open Access
- 15 August 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (ICFP) , 602-629
Abstract
We argue that monadic interpreters built as layers of handlers stacked atop the free monad, as advocated notably by the ITree library, also constitute a promising way to implement and verify abstract interpreters in dependently-typed theories such as the one underlying the Coq proof assistant. The approach enables both code reuse across projects and modular proofs of soundness of the resulting interpreters. We provide generic abstract control flow combinators proven correct once and for all against their concrete counterpart. We demonstrate how to relate concrete handlers implementing effects to abstract variants of these handlers, essentially capturing the traditional soundness of transfer functions in the context of monadic interpreters. Finally, we provide generic results to lift soundness statements via the interpretation of stateful and failure effects. We formalize all the aforementioned combinators and theories into a Coq library, and demonstrate their benefits by implementing and proving correct two illustrative abstract interpreters respectively for a structured imperative language and a toy assembly.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Skeletal semantics and their interpretationsProceedings of the ACM on Programming Languages, 2019
- Refinement to Certify Abstract Interpretations: Illustrated on Linearization for PolyhedraJournal of Automated Reasoning, 2018
- Compositional soundness proofs of abstract interpretersProceedings of the ACM on Programming Languages, 2018
- RustBelt: securing the foundations of the Rust programming languageProceedings of the ACM on Programming Languages, 2017
- Abstracting definitional interpreters (functional pearl)Proceedings of the ACM on Programming Languages, 2017
- Galois transformers and modular abstract interpreters: reusable metatheory for program analysis | Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications2015
- Freer monads, more extensible effectsACM SIGPLAN Notices, 2015
- A Formally-Verified C Static Analyzer2015
- Modular monadic meta-theoryACM SIGPLAN Notices, 2013
- Meta-theory à la carte2013