EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Asynchronous Probabilistic Couplings in Higher-Order Separation Logic

Simon Oddershede Gregersen, Alejandro Aguirre, Philipp G. Haselwarter, Joseph Tassarotti, Lars Birkedal

Proceedings of the ACM on Programming Languages · 02.01.2024 · 8 (POPL) · 753-784

DOI: 10.1145/3632868 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 05.01.2024. Verfasst von Simon Oddershede Gregersen und 4 weiteren Autor:innen. Die Arbeit wurde bisher 23-mal zitiert (Crossref) und nennt 74 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: ERC, NSF, VILLUM Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Probabilistic couplings are the foundation for many probabilistic relational program logics and arise when relating random sampling statements across two programs. In relational program logics, this manifests as dedicated coupling rules that, e.g ., say we may reason as if two sampling statements return the same value. However, this approach fundamentally requires aligning or “synchronizing” the sampling statements of the two programs which is not always possible. In this paper, we develop Clutch, a higher-order probabilistic relational separation logic that addresses this issue by supporting asynchronous probabilistic couplings. We use Clutch to develop a logical step-indexed logical relation to reason about contextual refinement and equivalence of higher-order programs written in a rich language with a probabilistic choice operator, higher-order local state, and impredicative polymorphism. Finally, we demonstrate our approach on a number of case studies. All the results that appear in the paper have been formalized in the Coq proof assistant using the Coquelicot library and the Iris separation logic framework.

Förderung

  • ERC
  • NSF
  • VILLUM Foundation

Zitieren

APA

Gregersen, S. O., Aguirre, A., Haselwarter, P. G., Tassarotti, J., & Birkedal, L. (2024). Asynchronous Probabilistic Couplings in Higher-Order Separation Logic. Proceedings of the ACM on Programming Languages, 8(POPL), 753-784. https://doi.org/10.1145/3632868

Vancouver

Gregersen SO, Aguirre A, Haselwarter PG, Tassarotti J, Birkedal L. Asynchronous Probabilistic Couplings in Higher-Order Separation Logic. Proceedings of the ACM on Programming Languages. 2024;8(POPL):753-784. doi:10.1145/3632868

BibTeX
@article{Gregersen2024,
  author = {Gregersen, Simon Oddershede and Aguirre, Alejandro and Haselwarter, Philipp G. and Tassarotti, Joseph and Birkedal, Lars},
  title = {Asynchronous Probabilistic Couplings in Higher-Order Separation Logic},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {POPL},
  pages = {753--784},
  doi = {10.1145/3632868}
}
Kostenlos starten →