Session types have emerged as a typing discipline for communication protocols. Existing calculi with session types come equipped with many different primitives that combine communication with the introduction or elimination of the transmitted value. We present a foundational session type calculus with a lightweight operational semantics. It fully decouples communication from the introduction and elimination of data and thus features a single communication reduction, which acts as a rendezvous between senders and receivers. We achieve this decoupling by introducing label-dependent session types, a minimalist value-dependent session type system with subtyping. The system is sufficiently powerful to simulate existing functional session type systems. Compared to such systems, label-dependent session types place fewer restrictions on the code. We further introduce primitive recursion over natural numbers at the type level, thus allowing to describe protocols whose behaviour depends on numbers exchanged in messages. An algorithmic type checking system is introduced and proved equivalent to its declarative counterpart. The new calculus showcases a novel lightweight integration of dependent types and linear typing, with has uses beyond session type systems. This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License. Peter Thiemann and Vasco T. Vasconcelos Padovani [2017a] proposes a different encoding that does not require the creation of new channels or channel passing. The encoding of internal choice sends one of the constructor functions of the sum type and clever typing guarantees that the type of the channel changes appropriately. Our calculus LDST of Label-Dependent Session Types is yet more economic in that it requires just a single pair of communication operations, send and receive, to implement a binary sessiontype calculus. Moreover, this implementation does not require higher-order communication, nor transmission of functions, nor clever retyping to achieve type soundness, session fidelity, and communication safety. In particular, the encoding of binary choice only needs to transmit one bit. Label dependency is a very limited form of dependent types where values can depend on labels drawn from a finite set. The labels play the role of labels in internal and external choices, similar to variant labels in polymorphic variant types [Castagna et al. 2016; Garrigue 1998] or first-class record labels [Nishimura 1998 ]. Hence, session types in LDST are dependent as in !(x ∶ A)B or ?(x ∶ A)B, which means to send A (or receive A) and continue as B, which may depend on x. Labels can further serve as end markers in protocols and thus the label-dependent calculus is łwire compatiblež to the standard encoding of functional session types like the LAST calculus [Gay and Vasconcelos 2010] of Linear Asynchronous Session Types. In fact, a synchronous version of LAST can be fully emulated in LDST. Label dependency does not require a full-blown lambda calculus in the types: a large elimination construct for a finite set of labelsÐa case expression on labelsÐsuffices. As a more general example, we outline an extension with natural numbers and large elimination with a recursor. LDST reinforces the connection between session types and linear logic [Caires and Pfenning 2010; Caires et al. 2016; Toninho et al. 2011; Wadler 2012] . The send operation maps a channel of dependent type !(x ∶ A)B into a single-use function Π lin (x ∶ A)B whereas the receive operation takes a channel of dependent type ?(x ∶ A)B to a single-use dependent sum Σ(x ∶ A)B.
Label-dependent session types REF use a limited form of dependent types where values can depend on labels drawn from a finite set.
Label-dependent session types
PACMPL
Computer Science