Actris: Session-type based reasoning in separation logic

Journal Article (2020)
Author(s)

J.K. Hinrichsen (IT University of Copenhagen)

Jesper Bengtson (IT University of Copenhagen)

Robbert Krebbers (TU Delft - Programming Languages)

Research Group
Programming Languages
Copyright
© 2020 J.K. Hinrichsen, Jesper Bengtson, R.J. Krebbers
DOI related publication
https://doi.org/10.1145/3371074
More Info
expand_more
Publication Year
2020
Language
English
Copyright
© 2020 J.K. Hinrichsen, Jesper Bengtson, R.J. Krebbers
Research Group
Programming Languages
Issue number
POPL
Volume number
4
Pages (from-to)
1-30
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

Message passing is a useful abstraction to implement concurrent programs. For real-world systems, however, it is often combined with other programming and concurrency paradigms, such as higher-order functions, mutable state, shared-memory concurrency, and locks. We present Actris: a logic for proving functional correctness of programs that use a combination of the aforementioned features. Actris combines the power of modern concurrent separation logics with a first-class protocol mechanism - based on session types - for reasoning about message passing in the presence of other concurrency paradigms. We show that Actris provides a suitable level of abstraction by proving functional correctness of a variety of examples, including a distributed merge sort, a distributed load-balancing mapper, and a variant of the map-reduce model, using relatively simple specifications. Soundness of Actris is proved using a model of its protocol mechanism in the Iris framework. We mechanised the theory of Actris, together with tactics for symbolic execution of programs, as well as all examples in the paper, in the Coq proof assistant.