EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Tail Modulo Cons, OCaml, and Relational Separation Logic

Clément Allain, Frédéric Bour, Basile Clément, François Pottier, Gabriel Scherer

Proceedings of the ACM on Programming Languages · 07.01.2025 · 9 (POPL) · 2337-2363

DOI: 10.1145/3704915 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 09.01.2025. Verfasst von Clément Allain und 4 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: AJR.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Common functional languages incentivize tail-recursive functions, as opposed to general recursive functions that consume stack space and may not scale to large inputs. This distinction occasionally requires writing functions in a tail-recursive style that may be more complex and slower than the natural, non-tail-recursive definition. This work describes our implementation of the tail modulo constructor (TMC) transformation in the OCaml compiler, an optimization that provides stack-efficiency for a larger class of functions — tail-recursive modulo constructors — which includes in particular the natural definition of List.map and many similar recursive data-constructing functions. We prove the correctness of this program transformation in a simplified setting — a small untyped calculus — that captures the salient aspects of the OCaml implementation. Our proof is mechanized in the Coq proof assistant, using the Iris base logic. An independent contribution of our work is an extension of the Simuliris approach to define simulation relations that support different calling conventions. To our knowledge, this is the first use of Simuliris to prove the correctness of a compiler transformation.

Förderung

  • AJR

Zitieren

APA

Allain, C., Bour, F., Clément, B., Pottier, F., & Scherer, G. (2025). Tail Modulo Cons, OCaml, and Relational Separation Logic. Proceedings of the ACM on Programming Languages, 9(POPL), 2337-2363. https://doi.org/10.1145/3704915

Vancouver

Allain C, Bour F, Clément B, Pottier F, Scherer G. Tail Modulo Cons, OCaml, and Relational Separation Logic. Proceedings of the ACM on Programming Languages. 2025;9(POPL):2337-2363. doi:10.1145/3704915

BibTeX
@article{Allain2025,
  author = {Allain, Clément and Bour, Frédéric and Clément, Basile and Pottier, François and Scherer, Gabriel},
  title = {Tail Modulo Cons, OCaml, and Relational Separation Logic},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2025},
  volume = {9},
  number = {POPL},
  pages = {2337--2363},
  doi = {10.1145/3704915}
}
Kostenlos starten →