On polymorphic sessions and functions: A talk of two (fully abstract) encodings
File(s)On_Polymorphic_Sessions_and_Functions.pdf (566.71 KB)
Published version
Author(s)
Parente Coutinho Fernandes Toninho, B
Yoshida, N
Type
Conference Paper
Abstract
This work exploits the logical foundation of session types to determine what kind of type discipline for the π -calculus can exactly capture, and is captured by, λ -calculus behaviours. Leveraging the proof theoretic content of the soundness and completeness of sequent calculus and natural deduction presentations of linear logic, we develop the first mutually inverse and fully abstract processes-as-functions and functions-as-processes encodings between a polymorphic session π -calculus and a linear formulation of System F. We are then able to derive results of the session calculus from the theory of the λ -calculus: (1) we obtain a characterisation of inductive and coinductive session types via their algebraic representations in System F; and (2) we extend our results to account for value and process passing, entailing strong normalisation.
Date Issued
2018-04-14
Date Acceptance
2017-12-22
Citation
Programming Languages and Systems, 2018, 10801, pp.827-855
ISBN
9783319898834
Publisher
Springer
Start Page
827
End Page
855
Journal / Book Title
Programming Languages and Systems
Volume
10801
Copyright Statement
© 2018 The Authors. This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
Sponsor
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (E
Grant Number
ERI 025567 (EP/K034413/1)
PO 20015393
EP/K011715/1
EP/N027833/1
PO 20015391
Source
ESOP 2018 27th European Symposium on Programming (ESOP)
Subjects
08 Information and Computing Sciences
Artificial Intelligence & Image Processing
Publication Status
Published
Start Date
2018-04-14
Finish Date
2018-04-20
Coverage Spatial
Thessaloniki, Greece
Date Publish Online
2018-04-14