Two sides of the same coin: session types and game semantics
File(s)DTRS18-5.pdf (1.14 MB)
Published version
Author(s)
Castellan, Simon
Yoshida, Nobuko
Type
Report
Abstract
Game semantics and session types are two formalisations of the same concept: message-passing open programs
following certain protocols. Game semantics represents protocols as games, and programs as strategies; while
session types specify protocols, and well-typed π-calculus processes model programs. Giving faithful models
of the π-calculus and giving a precise description of strategies as a programming language are two difficult
problems. In this paper, we show how these two problems can be tackled at the same time by building an
accurate game semantics model of the session π-calculus.
Our main contribution is to fill a semantic gap between the synchrony of the (session) π-calculus and the
asynchrony of game semantics, by developing an event-structure based game semantics for synchronous
concurrent computation. This model supports the first truly concurrent fully abstract (for barbed congruence)
interpretation of the synchronous (session) π-calculus.We further strengthen this correspondence, establishing
finite definability of asynchronous strategies by the internal session π-calculus. As an application of these
results, we propose a faithful encoding of synchronous strategies into asynchronous strategies by call-return
protocols, which induces automatically an encoding at the level of processes. Our results bring session types
and game semantics into the same picture, proposing the session calculus as a programming language for
strategies, and strategies as a very accurate model of the session calculus. We implement a prototype which
computes the interpretation of session processes as synchronous strategies.
following certain protocols. Game semantics represents protocols as games, and programs as strategies; while
session types specify protocols, and well-typed π-calculus processes model programs. Giving faithful models
of the π-calculus and giving a precise description of strategies as a programming language are two difficult
problems. In this paper, we show how these two problems can be tackled at the same time by building an
accurate game semantics model of the session π-calculus.
Our main contribution is to fill a semantic gap between the synchrony of the (session) π-calculus and the
asynchrony of game semantics, by developing an event-structure based game semantics for synchronous
concurrent computation. This model supports the first truly concurrent fully abstract (for barbed congruence)
interpretation of the synchronous (session) π-calculus.We further strengthen this correspondence, establishing
finite definability of asynchronous strategies by the internal session π-calculus. As an application of these
results, we propose a faithful encoding of synchronous strategies into asynchronous strategies by call-return
protocols, which induces automatically an encoding at the level of processes. Our results bring session types
and game semantics into the same picture, proposing the session calculus as a programming language for
strategies, and strategies as a very accurate model of the session calculus. We implement a prototype which
computes the interpretation of session processes as synchronous strategies.
Date Issued
2018-01-01
Citation
Departmental Technical Report: 18/5, 2018, pp.1-57
Publisher
Department of Computing, Imperial College London
Start Page
1
End Page
57
Journal / Book Title
Departmental Technical Report: 18/5
Copyright Statement
© 2018 The Author(s). This report is available open access under a CC-BY-NC-ND (https://creativecommons.org/licenses/by-nc-nd/4.0/)
Publication Status
Published