EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Modular Denotational Semantics for Effects with Guarded Interaction Trees

Dan Frumin, Amin Timany, Lars Birkedal

Proceedings of the ACM on Programming Languages · 02.01.2024 · 8 (POPL) · 332-361

DOI: 10.1145/3632854 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 05.01.2024. Verfasst von Dan Frumin und 2 weiteren Autor:innen. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 38 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Villum Fonden.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present guarded interaction trees — a structure and a fully formalized framework for representing higherorder computations with higher-order effects in Coq, inspired by domain theory and the recently proposed interaction trees. We also present an accompanying separation logic for reasoning about guarded interaction trees. To demonstrate that guarded interaction trees provide a convenient domain for interpreting higher-order languages with effects, we define an interpretation of a PCF-like language with effects and show that this interpretation is sound and computationally adequate; we prove the latter using a logical relation defined using the separation logic. Guarded interaction trees also allow us to combine different effects and reason about them modularly. To illustrate this point, we give a modular proof of type soundness of cross-language interactions for safe interoperability of different higher-order languages with different effects. All results in the paper are formalized in Coq using the Iris logic over guarded type theory.

Förderung

  • Villum Fonden

Zitieren

APA

Frumin, D., Timany, A., & Birkedal, L. (2024). Modular Denotational Semantics for Effects with Guarded Interaction Trees. Proceedings of the ACM on Programming Languages, 8(POPL), 332-361. https://doi.org/10.1145/3632854

Vancouver

Frumin D, Timany A, Birkedal L. Modular Denotational Semantics for Effects with Guarded Interaction Trees. Proceedings of the ACM on Programming Languages. 2024;8(POPL):332-361. doi:10.1145/3632854

BibTeX
@article{Frumin2024,
  author = {Frumin, Dan and Timany, Amin and Birkedal, Lars},
  title = {Modular Denotational Semantics for Effects with Guarded Interaction Trees},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {POPL},
  pages = {332--361},
  doi = {10.1145/3632854}
}
Kostenlos starten →