Replicate, Reuse, Repeat: Capturing Non-Linear Communication via Session Types and Graded Modal Types

Daniel Marshall
(University of Kent)
Dominic Orchard
(University of Kent)

Session types provide guarantees about concurrent behaviour and can be understood through their correspondence with linear logic, with propositions as sessions and proofs as processes. However, a strictly linear setting is somewhat limiting, since there exist various useful patterns of communication that rely on non-linear behaviours. For example, shared channels provide a way to repeatedly spawn a process with binary communication along a fresh linear session-typed channel. Non-linearity can be introduced in a controlled way in programming through the general concept of graded modal types, which are a framework encompassing various kinds of coeffect typing (describing how computations make demands on their context). This paper shows how graded modal types can be leveraged alongside session types to enable various non-linear concurrency behaviours to be re-introduced in a precise manner in a type system with a linear basis. The ideas here are demonstrated using Granule, a functional programming language with linear, indexed, and graded modal types.

In Marco Carbone and Rumyana Neykova: Proceedings of the 13th International Workshop on Programming Language Approaches to Concurrency and Communication-cEntric Software (PLACES 2022), Munich, Germany, 3rd April 2022, Electronic Proceedings in Theoretical Computer Science 356, pp. 1–11.
Published: 24th March 2022.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: