MobilityReadingGroup

Linear logic propositions as session types

Luís CAIRES, Frank PFENNING, Bernardo TONINHO

Throughout the years, several typing disciplines for the π-calculus have been proposed. Arguably, the most widespread of these typing disciplines consists of session types. Session types describe the input/output behaviour of processes and traditionally provide strong guarantees about this behaviour (i.e. deadlock-freedom and fidelity). While these systems exploit a fundamental notion of linearity, the precise connection between linear logic and session types has not been well understood.

This paper proposes a type system for the π-calculus that corresponds to a standard sequent calculus presentation of intuitionistic linear logic, interpreting linear propositions as session types and thus providing a purely logical account of all key features and properties of session types. We show the deep correspondence between linear logic and session types by exhibiting a tight operational correspondence between cut-elimination steps and process reductions. We also discuss an alternative presentation of linear session types based on classical linear logic, and compare our development with other more traditional session type systems.

@article{CPT2016,
  author = {Luís Caires and Frank Pfenning and Bernardo Toninho},
  title = {{Linear logic propositions as session types}},
  journal = {MSCS},
  volume = {26},
  issue = {SI3},
  pages = {367--423},
  publisher = {Cambridge University Press},
  year = 2016
}

@article{CPT2016,
  author = {Luís Caires and Frank Pfenning and Bernardo Toninho},
  title = {{Linear logic propositions as session types}},
  journal = {Mathematical Structures in Computer Science},
  volume = {26},
  issue = {SI3},
  pages = {367--423},
  publisher = {Cambridge University Press},
  doi = "10.1017/S0960129514000218",
  year = 2016
}