EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Abstract Interpreters: A Monadic Approach to Modular Verification

Sébastien Michelland, Yannick Zakowski, Laure Gonnord

Proceedings of the ACM on Programming Languages · 15.08.2024 · 8 (ICFP) · 602-629

DOI: 10.1145/3674646 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 15.08.2024. Verfasst von Sébastien Michelland und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 47 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Michelland, S., Zakowski, Y., & Gonnord, L. (2024). Abstract Interpreters: A Monadic Approach to Modular Verification. Proceedings of the ACM on Programming Languages, 8(ICFP), 602-629. https://doi.org/10.1145/3674646

Vancouver

Michelland S, Zakowski Y, Gonnord L. Abstract Interpreters: A Monadic Approach to Modular Verification. Proceedings of the ACM on Programming Languages. 2024;8(ICFP):602-629. doi:10.1145/3674646

BibTeX
@article{Michelland2024,
  author = {Michelland, Sébastien and Zakowski, Yannick and Gonnord, Laure},
  title = {Abstract Interpreters: A Monadic Approach to Modular Verification},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {ICFP},
  pages = {602--629},
  doi = {10.1145/3674646}
}
Kostenlos starten →