EMTST: Engineering the Meta-theory of Session Types
Open Access
- 17 April 2020
- book chapter
- Published by Springer Nature
- Vol. 12079, 278-285
Abstract
Session types provide a principled programming discipline for structured interactions. They represent a wide spectrum of type-systems for concurrency. Their type safety is thus extremely important. EMTST is a tool to aid in representing and validating theorems about session types in the Coq proof assistant. On paper, these proofs are often tricky, and error prone. In proof assistants, they are typically long and difficult to prove. In this work, we propose a library that helps validate the theory of session types calculi in proof assistants. As a case study, we study two of the most used binary session types systems: we show the impossibility of representing the first system in $$\alpha $$ -equivalent representations, and we prove type preservation for the revisited system. We develop our tool in the Coq proof assistant, using locally nameless for binders and small scale reflection to simplify the handling of linear typing environments.
Keywords
This publication has 17 references indexed in Scilit:
- An extensible approach to session polymorphismMathematical Structures in Computer Science, 2015
- The Locally Nameless RepresentationJournal of Automated Reasoning, 2011
- Multiparty asynchronous session types2008
- Engineering formal metatheory2008
- Subtyping for session types in the pi calculusActa Informatica, 2005
- Functional pearl2004
- Some Lambda Calculus and Type Theory FormalizedJournal of Automated Reasoning, 1999
- Language primitives and type discipline for structured communication-based programming1998
- A mechanisation of name-carrying syntax up to alpha-conversionLecture Notes in Computer Science, 1994
- Types for dyadic interaction1993