A Bunch of Sessions: A Propositions-as-Sessions Interpretation of Bunched Implications in Channel-Based Concurrency
The emergence of propositions-as-sessions, a Curry-Howard correspondence between propositions of Linear Logic and session types for concurrent processes, has settled the logical foundations of message-passing concurrency. Central to this approach is the resource consumption paradigm heralded by Linear Logic. In this paper, we investigate a new point in the design space of session type systems for message-passing concurrent programs. We identify O'Hearn and Pym's Logic of Bunched Implications (BI) as a fruitful basis for an interpretation of the logic as a concurrent programming language. This leads to a treatment of non-linear resources that is radically different from existing approaches based on Linear Logic. We introduce a new π-calculus with sessions, called πBI; its most salient feature is a construct called spawn, which expresses new forms of sharing that are induced by structural principles in BI. We illustrate the expressiveness of πBI and lay out its fundamental theory: type preservation, deadlock-freedom, and weak normalization results for well-typed processes; an operationally sound and complete typed encoding of an affine λ-calculus; and a non-interference result for access of resources.
Thu 8 DecDisplayed time zone: Auckland, Wellington change
15:30 - 17:00 | |||
15:30 30mTalk | A Bunch of Sessions: A Propositions-as-Sessions Interpretation of Bunched Implications in Channel-Based Concurrency OOPSLA Daniel Frumin University of Groningen, Emanuele D’Osualdo MPI-SWS, Bas van den Heuvel University of Groningen, Jorge A. Pérez University of Groningen DOI Pre-print | ||
16:00 30mTalk | A case for DOT: Theoretical Foundations for Objects with Pattern Matching and GADT-Style Reasoning OOPSLA Aleksander Boruch-Gruszecki EPFL, Radosław Waśko University of Warsaw, Yichen Xu Beijing University of Posts and Telecommunications, Lionel Parreaux Hong Kong University of Science and Technology DOI | ||
16:30 30mTalk | Coeffects for Sharing and Mutation OOPSLA Riccardo Bianchini University of Genoa, Francesco Dagnino University of Genoa, Paola Giannini University of Eastern Piedmont, Elena Zucca University of Genoa, Marco Servetto Victoria University of Wellington DOI |