Skip to content

定义Definition

二元会话类型

施工中 · 内容逐步修订

Binary session types · 二元会话协议

从同步对偶推进到有限FIFO队列不变量,逐项证明异步保持、单会话进展与精确缓冲界。

形式陈述 ​

二元会话类型描述一对端点之间有先后次序的通信义务:下一步发送什么、接收什么、由谁选择分支,以及何时结束。本文先给出一个有限、同步的教学演算,以线性类型约束端点所有权,以小步语义描述双方同时完成一次通信。不含递归、共享端点、端点传递、子类型或进程失败;随后在单条无分支协议上加入异步FIFO队列并证明其保持。

协议、进程与基本计算 ​

基本类型为 A::=Int∣Bool。整数取数学整数,故没有溢出;基本值为整数和布尔常量。会话类型为

S::=end∣!A.S∣?A.S∣⊕{ℓi:Si}i∈I∣&{ℓi:Si}i∈I,

其中 I 有限非空、标签互异。!A.S 表示发送一个 A 后遵循 S,?A.S 表示接收;⊕ 主动选择一个标签,& 准备接受所列的任一标签。end 是惰性的完成状态,本文没有额外的关闭握手。

把基本表达式与值区分开,才能准确描述发送 n+1:

v::=k∣true∣false(k∈Z),e::=v∣a∣e+e,P::=0∣x!e.P∣x?(a).P∣x◃ℓ.P∣x▹{ℓi:Pi}i∈I∣(P∣P)∣(νxy)P.

最后一行中的 P∣P 是并行组合。x?(a).P 绑定基本变量 a;(νxy)P 绑定一对新鲜、互相连接的端点 x,y。所有代换均避免变量捕获。基本上下文 Γ 允许复制和丢弃变量,包含通常的常量、变量规则以及

Γ⊢e1:IntΓ⊢e2:IntΓ⊢e1+e2:Int.

对闭的良型表达式,求值 e⇓v 总是终止且结果唯一:常量求值为自身,两个整数子表达式分别求值后相加。运行中输入变量先由通信代换为值,因此实际发送时表达式是闭的。基本计算无副作用,也不能读取或携带端点。

对偶 S― 交换双方的义务,而不改变基本消息类型:

end―=end,!A.S―=?A.S―,?A.S―=!A.S―,⊕{ℓi:Si}i∈I―=&{ℓi:Si―}i∈I,&{ℓi:Si}i∈I―=⊕{ℓi:Si―}i∈I.

结构归纳立即给出 S――=S;特别地,对偶分支具有完全相同的标签集。

类型规则与同步归约 ​

判断 Γ;Δ⊢P 中,Δ 记录端点的当前剩余协议,端点名互异。记 end(Δ) 表示其所有条目均为 end;这些惰性条目可以保留或去掉。以下规则中的 Δ,x:S 要求 x 不在 Δ 中:

end(Δ)Γ;Δ⊢0Γ;Δ1⊢PΓ;Δ2⊢QΓ;Δ1⊎Δ2⊢P∣QΓ;Δ,x:S,y:S―⊢PΓ;Δ⊢(νxy)P.

不相交并 ⊎ 保证一个活跃端点只属于一个并行分量;限制规则要求两端当前类型互为对偶。发送与接收分别消耗当前通信义务:

Γ⊢e:AΓ;Δ,x:S⊢PΓ;Δ,x:!A.S⊢x!e.PΓ,a:A;Δ,x:S⊢PΓ;Δ,x:?A.S⊢x?(a).P.

接收规则的 a 是新鲜变量。选择只检查实际选择的延续;提供分支则必须检查每一种可能:

j∈IΓ;Δ,x:Sj⊢PΓ;Δ,x:⊕{ℓi:Si}i∈I⊢x◃ℓj.P,(Γ;Δ,x:Si⊢Pi)i∈IΓ;Δ,x:&{ℓi:Si}i∈I⊢x▹{ℓi:Pi}i∈I.

所有分支使用同一份其他端点上下文 Δ,但一次执行只进入一个分支。这是互斥选择,不能将这些前提误读成并行复制资源。

归约规则为

e⇓v(νxy)(x!e.P∣y?(a).Q)⟶(νxy)(P∣Q[v/a]),(νxy)(x◃ℓj.P∣y▹{ℓi:Qi}i∈I)⟶(νxy)(P∣Qj),j∈I.

另有交换两端角色的规则。归约对并行组合和限制封闭,不进入尚未通信的前缀;允许 α 换名、并行的交换结合与 0 单位律,以及不捕获自由名字的作用域外移。发送和接收在同一步完成,没有消息队列。

直觉

普通消息类型只说明“这里传整数”。会话类型还能说明“先传整数,再由客户端选择继续或取消;继续就必须收到一个整数”。对偶不是两边写同一份程序,而是发送对应接收、选择对应等待选择。两端协议一致,才可能在同一个通信位置对接。

线性纪律管理的是当前协议能力的唯一所有者,不是端点名字在源码中只能出现一次。x!41.x?(r).0 中的两个 x 由顺序前缀连接:第一个动作结束后,同一绑定以剩余类型进入延续。函数式接口可以改用“消费旧句柄、返回新句柄”表达同一推进;这里直接在推导上下文中更新剩余协议。

基本值与端点的纪律不同。服务端收到的整数 n 放入 Γ,可以反复参与计算,也可以在取消分支中不用;活跃端点放入 Δ,不能在两个同时运行的线程之间复制,也不能在仍有通信义务时被 0 丢弃。

例子与边界

从 41 到 42,或在分支处取消 ​

令客户端与服务端类型分别为

S=!Int.⊕{inc:?Int.end,cancel:end},S―=?Int.&{inc:!Int.end,cancel:end}.

完整程序为

C=x!41.x◃inc.x?(r).0,D=y?(n).y▹{inc:y!(n+1).0, cancel:0}.

客户端由 r:Int;x:end⊢0 向上应用接收、选择和发送规则,得到 ∅;x:S⊢C。服务端在 Γ=n:Int 下有 n+1:Int,所以 Γ;y:!Int.end⊢y!(n+1).0;取消分支则有 Γ;y:end⊢0。两分支共享空的其他端点上下文,经分支及接收规则得到 ∅;y:S―⊢D。并行与限制规则最后给出闭判断 ∅;∅⊢(νxy)(C∣D)。

记 C1=x◃inc.x?(r).0,完整运行是

(νxy)(C∣D)⟶(νxy)(C1∣y▹{inc:y!(41+1).0,cancel:0})⟶(νxy)(x?(r).0∣y!(41+1).0)⟶(νxy)(0∣0).

第一步发送 41 并代换 n;第二步同步选择 inc;第三步由 41+1⇓42 发送 42,再作代换 [42/r]。r 未用于后续计算,故结果仍为 0。三步后的内部端点类型依次为

xy1⊕{inc:?Int.end,cancel:end}&{inc:!Int.end,cancel:end}2?Int.end!Int.end3endend

图中的 T=⊕{inc:?Int.end,cancel:end},T― 是服务端的对应分支类型。每条消息箭头位于通信前后的两行状态之间;取消路径是第二次通信的另一种选择,不与 inc 同时执行。

若改用 Ccancel=x!41.x◃cancel.0,客户端仍有类型 S。第一步同样发送 41;第二步选择取消,直接留下 (νxy)(0∣0),无需发送回复。相反,发送布尔值不能满足最初的 !Int;选择未声明标签违反 j∈I;选择 inc 后直接停机则无法用 x:?Int.end 推导 0。

两条会话仍可形成死锁 ​

考虑完全封闭、没有递归的网络

N=(νxy)(νzw)(x?(n).z!true.0∣w?(b).y!1.0).

左线程的推导从结束条目开始:

n:Int;x:end,z:end⊢0,n:Int;x:end,z:!Bool.end⊢z!true.0,∅;x:?Int.end,z:!Bool.end⊢x?(n).z!true.0.

右线程同理:

b:Bool;w:end,y:end⊢0,b:Bool;w:end,y:!Int.end⊢y!1.0,∅;w:?Bool.end,y:!Int.end⊢w?(b).y!1.0.

两个上下文不相交;x,y 对偶,z,w 也对偶。因此并行规则及两次限制规则得到 ∅;∅⊢N。但左边等待 x 接收,右边等待 w 接收;对应发送 y!1 与 z!true 都藏在尚未完成的接收前缀之后。没有归约规则可用。线性所有权与逐对对偶均成立,跨会话的循环等待仍然存在。

有限 FIFO 会话:把尚未接收的消息记入状态 ​

现在另取异步片段,保留上述基本表达式、顺序发送和接收,只允许一对端点与两个顺序执行者;不含选择、并行延续、新建会话、递归或端点传递。协议是长度 N 的有限字

S=a0a1⋯aN−1.end,ak∈{!Int,!Bool,?Int,?Bool}.

S[i:] 表示删去前 i 个动作后的后缀。A 持有 x、初始类型 S;B 持有 y、初始类型 S―。配置写为

C=(i,P; j,Q; qAB,qBA),0≤i,j≤N.

i,j 是双方已执行的动作数,不是已完成的同步通信次数。qAB 保存 A 已发送、B 尚未接收的基本值,qBA 方向相反;队首在左。队列可靠、无容量限制,不丢失、不复制、不重排。沿用前述顺序前缀的类型规则,配置的局部要求是

∅;x:S[i:]⊢P,∅;y:S[j:]―⊢Q.

运行中的接收变量已经被先前的值代换,故这两项的基本变量均闭合。记 q⋅v 为队尾追加,v⋅q 为队首分解。A 的两条异步规则为

(i,x!e.P; j,Q; qAB,qBA)⟶(i+1,P; j,Q; qAB⋅v,qBA)(e⇓v),(i,x?(a).P; j,Q; qAB,v⋅qBA)⟶(i+1,P[v/a]; j,Q; qAB,qBA).

B 的发送把值追加到 qBA 并增加 j;B 的接收从 qAB 队首取值并增加 j,其余完全对称。发送无需等待对端,接收空队列没有规则。类型安全将证明队首值具有正确类型;语义本身不偷偷搜索队列中“类型合适”的消息。

队列类型不变量 IS。 除局部良型性外,要求下列二者之一成立:

  • 若 i≥j,则区间 [j,i) 中全是 A 的发送动作。写 ak=!Ak,就有 qAB=[vj,…,vi−1],每个 vk:Ak,且 qBA=ϵ。
  • 若 i<j,则区间 [i,j) 中全是 A 的接收动作。写 ak=?Ak,就有 qBA=[vi,…,vj−1],每个 vk:Ak,且 qAB=ϵ。

在 i=j 时,第一个条件的区间和两个队列均为空。索引在这里给每个未完成的协议位置保留一个消息槽;不仅队长等于进度差,还逐项检查消息类型与 FIFO 顺序。例如 !Int.!Bool 的两个消息不能换位。两个连续整数即使类型相同也不能换位:入队/出队规则保存其实际值的先后,而单独的类型判断不会表达整数之间的业务关系。

异步发送后通常没有 S[i:]=S[j:]――,即双方当前后缀不在同一位置。让落后端依次接收队列中对应的前缀以后,两端才重新对齐。一般异步会话系统也用队列匹配与剩余协议组织配置类型;这里的有限字不变量由本页规则独立证明,不使用含子类型系统中的兼容关系替代精确后缀。[4, §§5–6]

六步运行:发送两次以后再接收 ​

取

S=!Int.!Bool.?Int.end,P=x!7.x!true.x?(r).0,Q=y?(n).y?(b).y!(n+2).0.

接收的 b 可不使用,因为它是基本变量。以下一种合法调度让 A 先连续发送,队列的每一项都保留到对端实际接收:

步骤 (i,j) qAB qBA 本步动作
初始 (0,0) ϵ ϵ 两端开始
1 (1,0) [7] ϵ A 发送整数
2 (2,0) [7,true] ϵ A 发送布尔值
3 (2,1) [true] ϵ B 接收,代换 n=7
4 (2,2) ϵ ϵ B 接收,代换 b=true
5 (2,3) ϵ [9] B 计算并发送 7+2
6 (3,3) ϵ ϵ A 接收,代换 r=9

第二步后,A 已在 ?Int.end,B 还在 ?Int.?Bool.!Int.end;两个前缀都是接收,并不构成同步对偶。B 此时可以接收队首 7,所以没有死锁。第五步 B 已经到 end,但回复 9 仍在队列里;只有双方都到 N 才是本配置的完成状态。

若错误实现从第二步的队尾取出 true 交给 B 的整数接收,局部类型与队列位置立即失配;若发送后只增加 i 而忘记入队,则队长不等于 i−j。这两种错误由不同的不变量分量捕获。

推论与应用

保持的是成对推进的不变量 ​

沿用进展与保持的证明方法,本演算满足:若 Γ;Δ⊢P 且 P⟶P′,则 Γ;Δ⊢P′。这里外部接口 Δ 不变;发生通信的受限制端点,其内部类型同时从 S,S― 推进到相应的对偶延续,不能把定理误读成“每个端点一直保持最初类型”。

证明先建立基本值代换引理:若 Γ,a:A;Δ⊢Q 且 Γ⊢v:A,则 Γ;Δ⊢Q[v/a]。对类型推导归纳即可;v 不包含端点,所以代换既不改变线性上下文,也不复制端点。基本表达式求值另满足 Γ⊢e:A 且 e⇓v 蕴含 Γ⊢v:A,由表达式结构归纳得到。

对一次发送归约,反演并行、限制和前缀规则,得到发送端 x:!A.S、接收端 y:?A.S―,以及两延续分别具有 x:S、y:S―。求值与代换引理使接收延续保持良型,再用原先不相交的其他端点上下文合成并行,最后重新限制 x,y。唯一所有权确保没有第三个并行分量还握着此次被推进的活跃端点。

对标签归约,反演得到相同标签集及被选择的 j。分支规则已经检查 Qj,其类型恰为选择端延续 Sj 的对偶;重组并行与限制即可。上下文封闭的情形由归纳假设重建推导,结构同余由换名、上下文交换与作用域条件保持良型。因此示例从头到尾的外层判断都为空接口,内部状态却确实经历了三次变化。

单条会话何时保证下一步 ​

限定为 (νxy)(P∣Q):只有两个顺序执行者,分别独占 x 与 y;延续不含新的并行或限制,没有其他活跃信道;基本计算总是终止,且没有失败或外部交互。对这样良型、闭合的配置,若协议尚未结束,就存在下一步通信。

理由来自类型反演。若 x 的类型为 !A.S,左执行者必以 x!e 开头,右执行者由对偶类型必以 y?(a) 开头;闭的 e 可求值,所以发送规则可用。接收情形对称。选择情形中,一侧确定一个合法标签,另一侧已为该标签准备延续。到 end 时,两顺序执行者只能终止。有限协议每步严格减少剩余协议深度,所以持续执行可用归约的运行最终终止;这里没有对任意实际调度器作公平性承诺。

一旦允许每个线程持有多条活跃会话,上述反演只能确定“某条信道上的下一动作”,不能保证其对端此刻也在处理这条信道;N 正好展示断裂之处。若要证明一般网络的无死锁,还须增加会话依赖顺序等全局约束,不能仅引用逐对对偶。

异步保持:四种动作怎样维持同一不变量 ​

初始配置 (0,P;0,Q;ϵ,ϵ) 满足 IS,只需两进程分别具有 S,S―。异步保持定理是:若 IS(C) 且 C→C′,则 IS(C′)。证明逐一处理两方向的发送与接收。

先看 A 发送。类型反演得 i<N、ai=!Ai、e:Ai,且发送延续具有 S[i+1:]。不可能有 i<j:此时不变量要求 ai 是 A 的接收,与发送反演矛盾。因此 i≥j,旧 qBA 为空,[j,i) 已全是发送;添加 ai 后,[j,i+1) 仍全是发送。基本求值保持给出 v:Ai,队尾追加恰好补齐该区间的最后一槽,B 的局部推导不变。

A 接收时,规则要求 qBA 非空,所以不变量迫使 i<j,且队首 vi:Ai、ai=?Ai。反演接收规则得延续在 a:Ai 假设下具有 S[i+1:];基本值代换引理移除该假设并保持类型。出队删除区间首槽。如果 i+1<j,仍满足第二分支;如果 i+1=j,区间变空、两队列均空,转入第一分支的等号情形。

B 发送是 A 接收方向的生产者:其局部反演要求 aj=?Aj。若 j<i,第一分支却要求 aj=!Aj,矛盾。因此 j≥i,B 的发送将 [i,j) 的全接收区间扩为 [i,j+1),向 qBA 追加正确类型的值;从 i=j 出发时由空区间切换到第二分支。B 接收要求 qAB 非空,因而 j<i;取出 vj:Aj,对延续使用代换引理,并将 [j,i) 缩成 [j+1,i)。若追平 A,就得到空区间。四种情况都保持闭合、局部类型和两个队列的全部条件,定理成立。

这一证明还说明为什么同一时刻两队列不能都非空:领先端只可能继续同一方向发送,或等待落后端先收完消息并开始回送;它不能越过一个尚未由对端发送的接收动作。这是本有限顺序协议的结论,不是对任意异步网络的假设。

有限 FIFO 片段的进展与缓冲界 ​

设 IS(C)。若 i=j<N,两队列为空,ai 规定的一方以发送开头,闭基本表达式可求值,故该发送可执行。若 i>j,B 的下一动作是接收,qAB 的队首正是所需值,故 B 可执行;若 i<j 则 A 可执行。因此,除 i=j=N 外总有下一步,而该终态中的两进程为 0、两队列为空。

每步将自然数 2N−i−j 减一,构成良基排名。于是从初始配置 (0,P;0,Q;ϵ,ϵ) 出发,每条不能再延长的归约序列都恰好含 2N 步,且完整结束;不能据此断言一个现实调度器不会永远暂停一个可执行线程。同步片段每次同时完成两端义务,这里每条消息则需要一次发送和一次接收。

令 L 是 S 中最长同方向连续动作段的长度,N=0 时取 L=0。由不变量,非空队列恰好对应某个全发送或全接收区间,因此每个可达状态满足

|qAB|+|qBA|=|i−j|≤L.

这个上界可达到:先执行到最长段的起点并清空队列,再让该段的发送方连续执行 L 次。示例中 L=2,第二步恰好占满两槽。若实现给每个方向至少 L 个槽,上述可达执行无需因满缓冲区阻塞;若容量更小,必须明确增加发送阻塞规则,原先“发送总可执行”的证明就需调整。

队列纪律解决的是单条会话内的进度错位。前面的双会话死锁网络在空队列下依然没有任何可执行的发送,因而不能从这里的两执行者定理推广出任意网络无死锁。

参考资料
  • Kohei Honda、Vasco T. Vasconcelos、Makoto Kubo,Language Primitives and Type Discipline for Structured Communication-Based Programming,ESOP 1998,LNCS 1381,122–138 页,§§2、5 与 §6.1;Theorem 5.4 讨论 subject reduction 与交互错误排除,§6.1 区分同步原语及异步实现。
  • Vasco T. Vasconcelos,Fundamentals of Session Types,2012 年 5 月 17 日作者预印本,对应 Information and Computation 217,52–70 页,§§2–3、6–7;第 9 页明确区分会话类型安全与进展,并展示良型死锁。本文只抽取有限、基本值通信的教学片段,规则与证明已在正文独立给出。
  • Frank Pfenning,Lecture 7: Preservation and Progress,2023 年 9 月 19 日,§§3–5、Theorems 2 与 4。其配置纪律加入提供者与客户端的次序约束,进展定理的前提强于本文任意不相交端点分配。

[4] Simon J. Gay、Vasco T. Vasconcelos,Linear Type Theory for Asynchronous Session Types,Journal of Functional Programming 20(1),2010,19–50页;§3 Figure 4 给出缓冲通信,§5 Figures 11–12定义队列匹配与剩余类型,§6 Lemmas 20–21及Theorem 24证明保持。该系统还含子类型与通道传递;本页另行给出有限基本值协议的精确不变量及证明。

关系图谱11 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系