Exploring bidirectional typing for the Semi-Axiomatic sequent calculus

Abstract

A type system acts as a programmers guide through a language, a set of logical rules through which the compiler can discern programs which have meaning from those that do not and hence protect the programmer from being able to write nonsensical programs. Unfortunately many of the type systems for mainstream programming languages do not provide any protections for concurrent programs. As it so happens implementing concurrent software is a notoriously difficult task. The interactions of different concurrent processes with each other and with shared resources introduce whole new families of software bugs. Furthermore the non-deterministic nature of concurrency make these bugs exceedingly hard to locate, understand and ultimately fix. This work focuses on a particular Session Type formalism, the Semi-Axiomatic Sequent Calculus (SAX) whose operational interpretation corresponds to asynchronous message passing concurrency. The aim is to adapt SAX’s theoretical type specification so that it is suitable for implementation and practical for the programmer by applying the technique of Bidirectional Typing to the existent type system.