Session types are a type-based approach to the verification of message-passing programs. They specify communication structures essential for program correctness; a session type says what and when should be exchanged through a channel. Central to session-typed languages are sequencing constructs in types and processes that explicitly specify the order of actions in a protocol. In this paper we study session types without sequencing. The resulting framework of minimal session types is arguably the simplest form of session types one could conceive. In the context of a core process calculus with sessions and higher-order concurrency (abstraction-passing), we establish two main technical results. First, we prove that every process $P$ typable with standard session types can be compiled down into a process $\mathcal{D}(P)$ typable with minimal session types. Second, we prove that $P$ and $\mathcal{D}(P)$ are behaviorally equivalent. These results indicate that having sequencing constructs in processes and session types is convenient but redundant: only sequentiality in processes is truly indispensable, as it can correctly codify sequentiality in types. Our developments draw inspiration from work by Parrow on behavior-preserving decompositions of untyped processes. By casting Parrow's results in the realm of typed processes, our developments reveal a conceptually simple formulation of session types and a principled avenue to the integration of session types into programming languages without sequencing in types.
翻译:届会类型是用于核实信件传递程序的一种基于类型的方法。 届会类型指定了对程序正确性至关重要的通信结构; 届会类型指定了应该通过一个渠道交换的内容和时间。 届会类型的核心语言是以明确指定协议中行动顺序的类型和程序来排序结构。 在本文中, 我们无需顺序来研究届会类型。 由此形成的最小届会类型框架可以说是人们可以想象的最简单的届会类型类型的形式。 在以届会和更高级别货币( 通缩) 进行核心计算的过程中, 我们设定了两个主要的技术结果。 首先, 我们证明每个可使用标准会类型的进程类型的美元( $P$) 都可以被汇编成一个进程 $\ mathcal{D} (P) 的排序。 其次, 我们证明, $P$ 和 $\ mathcall{D} (P) 的排序框架是行为等同的。 这些结果表明, 以进程类型进行进程排序是方便但多余的: 只有进程的顺序是真正不可或缺的, 因为它可以准确地将非顺序编成类型。 我们的发展通过将类型排序方式向方向显示方向的排序, 将方向的顺序显示方向的排序, 方向的顺序显示方向的顺序显示, 方向方向的排序的排序将显示方向的排序进程。