形式陈述
二元会话类型描述一对端点之间有先后次序的通信义务:下一步发送什么、接收什么、由谁选择分支,以及何时结束。本文先给出一个有限、同步的教学演算,以线性类型 理路 线性类型与仿射类型 Linear type · Affine type · Linear and affine types 分别以恰好一次和至多一次的上下文纪律约束值使用,并显式隔离可复制资源。 约束端点所有权,以小步语义 理路 小步操作语义 Small-step operational semantics · Structural operational semantics 用配置间的一步转移及有限或无限路径精确描述执行顺序、终止、卡住与发散。 描述双方同时完成一次通信。不含递归、共享端点、端点传递、子类型或进程失败;随后在单条无分支协议上加入异步FIFO队列并证明其保持。
协议、进程与基本计算
基本类型为 A ::= Int ∣ Bool 。整数取数学整数,故没有溢出;基本值为整数和布尔常量。会话类型为
S ::= end ∣ ! A . S ∣ ? A . S ∣ ⊕ { ℓ i : S i } i ∈ I ∣ & { ℓ i : S i } 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 : P i } i ∈ I ∣ ( P ∣ P ) ∣ ( ν x y ) P . 最后一行中的 P ∣ P 是并行组合。x ? ( a ) . P 绑定基本变量 a ;( ν x y ) P 绑定一对新鲜、互相连接的端点 x , y 。所有代换均避免变量捕获。基本上下文 Γ 允许复制和丢弃变量,包含通常的常量、变量规则以及
Γ ⊢ e 1 : Int Γ ⊢ e 2 : Int Γ ⊢ e 1 + e 2 : Int . 对闭的良型表达式,求值 e ⇓ v 总是终止且结果唯一:常量求值为自身,两个整数子表达式分别求值后相加。运行中输入变量先由通信代换为值,因此实际发送时表达式是闭的。基本计算无副作用,也不能读取或携带端点。
对偶 S ― 交换双方的义务,而不改变基本消息类型:
end ― = end , ! A . S ― = ? A . S ― , ? A . S ― = ! A . S ― , ⊕ { ℓ i : S i } i ∈ I ― = & { ℓ i : S i ― } i ∈ I , & { ℓ i : S i } i ∈ I ― = ⊕ { ℓ i : S i ― } 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 Γ ; Δ ⊢ ( ν x y ) 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 : S j ⊢ P Γ ; Δ , x : ⊕ { ℓ i : S i } i ∈ I ⊢ x ◃ ℓ j . P , ( Γ ; Δ , x : S i ⊢ P i ) i ∈ I Γ ; Δ , x : & { ℓ i : S i } i ∈ I ⊢ x ▹ { ℓ i : P i } i ∈ I . 所有分支使用同一份其他端点上下文 Δ ,但一次执行只进入一个分支。这是互斥选择,不能将这些前提误读成并行复制资源。
归约规则为
e ⇓ v ( ν x y ) ( x ! e . P ∣ y ? ( a ) . Q ) ⟶ ( ν x y ) ( P ∣ Q [ v / a ] ) , ( ν x y ) ( x ◃ ℓ j . P ∣ y ▹ { ℓ i : Q i } i ∈ I ) ⟶ ( ν x y ) ( P ∣ Q j ) , 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 。并行与限制规则最后给出闭判断 ∅ ; ∅ ⊢ ( ν x y ) ( C ∣ D ) 。
记 C 1 = x ◃ inc . x ? ( r ) .0 ,完整运行是
( ν x y ) ( C ∣ D ) ⟶ ( ν x y ) ( C 1 ∣ y ▹ { inc : y ! ( 41 + 1 ) .0 , cancel : 0 } ) ⟶ ( ν x y ) ( x ? ( r ) .0 ∣ y ! ( 41 + 1 ) .0 ) ⟶ ( ν x y ) ( 0 ∣ 0 ) . 第一步发送 41 并代换 n ;第二步同步选择 inc ;第三步由 41 + 1 ⇓ 42 发送 42 ,再作代换 [ 42 / r ] 。r 未用于后续计算,故结果仍为 0 。三步后的内部端点类型依次为
x y 1 ⊕ { inc : ? Int . end , cancel : end } & { inc : ! Int . end , cancel : end } 2 ? Int . end ! Int . end 3 end end 图片加载失败 图中的 T = ⊕ { inc : ? Int . end , cancel : end } ,T ― 是服务端的对应分支类型。每条消息箭头位于通信前后的两行状态之间;取消路径是第二次通信的另一种选择,不与 inc 同时执行。
若改用 C cancel = x ! 41. x ◃ cancel .0 ,客户端仍有类型 S 。第一步同样发送 41 ;第二步选择取消,直接留下 ( ν x y ) ( 0 ∣ 0 ) ,无需发送回复。相反,发送布尔值不能满足最初的 ! Int ;选择未声明标签违反 j ∈ I ;选择 inc 后直接停机则无法用 x : ? Int . end 推导 0 。
两条会话仍可形成死锁
考虑完全封闭、没有递归的网络
N = ( ν x y ) ( ν z w ) ( 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 = a 0 a 1 ⋯ a N − 1 . end , a k ∈ { ! Int , ! Bool , ? Int , ? Bool } . S [ i : ] 表示删去前 i 个动作后的后缀。A 持有 x 、初始类型 S ;B 持有 y 、初始类型 S ― 。配置写为
C = ( i , P ; j , Q ; q A B , q B A ) , 0 ≤ i , j ≤ N . i , j 是双方已执行的动作数,不是已完成的同步通信次数。q A B 保存 A 已发送、B 尚未接收的基本值,q B A 方向相反;队首在左。队列可靠、无容量限制,不丢失、不复制、不重排。沿用前述顺序前缀的类型规则,配置的局部要求是
∅ ; x : S [ i : ] ⊢ P , ∅ ; y : S [ j : ] ― ⊢ Q . 运行中的接收变量已经被先前的值代换,故这两项的基本变量均闭合。记 q ⋅ v 为队尾追加,v ⋅ q 为队首分解。A 的两条异步规则为
( i , x ! e . P ; j , Q ; q A B , q B A ) ⟶ ( i + 1 , P ; j , Q ; q A B ⋅ v , q B A ) ( e ⇓ v ) , ( i , x ? ( a ) . P ; j , Q ; q A B , v ⋅ q B A ) ⟶ ( i + 1 , P [ v / a ] ; j , Q ; q A B , q B A ) . B 的发送把值追加到 q B A 并增加 j ;B 的接收从 q A B 队首取值并增加 j ,其余完全对称。发送无需等待对端,接收空队列没有规则。类型安全将证明队首值具有正确类型;语义本身不偷偷搜索队列中“类型合适”的消息。
队列类型不变量 I S 。 除局部良型性外,要求下列二者之一成立:
若 i ≥ j ,则区间 [ j , i ) 中全是 A 的发送动作。写 a k = ! A k ,就有 q A B = [ v j , … , v i − 1 ] ,每个 v k : A k ,且 q B A = ϵ 。
若 i < j ,则区间 [ i , j ) 中全是 A 的接收动作。写 a k = ? A k ,就有 q B A = [ v i , … , v j − 1 ] ,每个 v k : A k ,且 q A B = ϵ 。
在 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 )
q A B
q B A
本步动作
初始
( 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 。这两种错误由不同的不变量分量捕获。
推论与应用
保持的是成对推进的不变量
沿用进展与保持 理路 进展与保持定理 Progress and preservation · Type safety 对按值调用的简单类型 lambda 演算逐层解释规范形、替换、进展与保持,以及类型安全的准确结论。 的证明方法,本演算满足:若 Γ ; Δ ⊢ 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 。分支规则已经检查 Q j ,其类型恰为选择端延续 S j 的对偶;重组并行与限制即可。上下文封闭的情形由归纳假设重建推导,结构同余由换名、上下文交换与作用域条件保持良型。因此示例从头到尾的外层判断都为空接口,内部状态却确实经历了三次变化。
单条会话何时保证下一步
限定为 ( ν x y ) ( P ∣ Q ) :只有两个顺序执行者,分别独占 x 与 y ;延续不含新的并行或限制,没有其他活跃信道;基本计算总是终止,且没有失败或外部交互。对这样良型、闭合的配置,若协议尚未结束,就存在下一步通信。
理由来自类型反演。若 x 的类型为 ! A . S ,左执行者必以 x ! e 开头,右执行者由对偶类型必以 y ? ( a ) 开头;闭的 e 可求值,所以发送规则可用。接收情形对称。选择情形中,一侧确定一个合法标签,另一侧已为该标签准备延续。到 end 时,两顺序执行者只能终止。有限协议每步严格减少剩余协议深度,所以持续执行可用归约的运行最终终止;这里没有对任意实际调度器作公平性承诺。
一旦允许每个线程持有多条活跃会话,上述反演只能确定“某条信道上的下一动作”,不能保证其对端此刻也在处理这条信道;N 正好展示断裂之处。若要证明一般网络的无死锁,还须增加会话依赖顺序等全局约束,不能仅引用逐对对偶。
异步保持:四种动作怎样维持同一不变量
初始配置 ( 0 , P ; 0 , Q ; ϵ , ϵ ) 满足 I S ,只需两进程分别具有 S , S ― 。异步保持定理 是:若 I S ( C ) 且 C → C ′ ,则 I S ( C ′ ) 。证明逐一处理两方向的发送与接收。
先看 A 发送。类型反演得 i < N 、a i = ! A i 、e : A i ,且发送延续具有 S [ i + 1 : ] 。不可能有 i < j :此时不变量要求 a i 是 A 的接收,与发送反演矛盾。因此 i ≥ j ,旧 q B A 为空,[ j , i ) 已全是发送;添加 a i 后,[ j , i + 1 ) 仍全是发送。基本求值保持给出 v : A i ,队尾追加恰好补齐该区间的最后一槽,B 的局部推导不变。
A 接收时,规则要求 q B A 非空,所以不变量迫使 i < j ,且队首 v i : A i 、a i = ? A i 。反演接收规则得延续在 a : A i 假设下具有 S [ i + 1 : ] ;基本值代换引理移除该假设并保持类型。出队删除区间首槽。如果 i + 1 < j ,仍满足第二分支;如果 i + 1 = j ,区间变空、两队列均空,转入第一分支的等号情形。
B 发送是 A 接收方向的生产者:其局部反演要求 a j = ? A j 。若 j < i ,第一分支却要求 a j = ! A j ,矛盾。因此 j ≥ i ,B 的发送将 [ i , j ) 的全接收区间扩为 [ i , j + 1 ) ,向 q B A 追加正确类型的值;从 i = j 出发时由空区间切换到第二分支。B 接收要求 q A B 非空,因而 j < i ;取出 v j : A j ,对延续使用代换引理,并将 [ j , i ) 缩成 [ j + 1 , i ) 。若追平 A,就得到空区间。四种情况都保持闭合、局部类型和两个队列的全部条件,定理成立。
这一证明还说明为什么同一时刻两队列不能都非空:领先端只可能继续同一方向发送,或等待落后端先收完消息并开始回送;它不能越过一个尚未由对端发送的接收动作。这是本有限顺序协议的结论,不是对任意异步网络的假设。
有限 FIFO 片段的进展与缓冲界
设 I S ( C ) 。若 i = j < N ,两队列为空,a i 规定的一方以发送开头,闭基本表达式可求值,故该发送可执行。若 i > j ,B 的下一动作是接收,q A B 的队首正是所需值,故 B 可执行;若 i < j 则 A 可执行。因此,除 i = j = N 外总有下一步,而该终态中的两进程为 0 、两队列为空。
每步将自然数 2 N − i − j 减一,构成良基排名 理路 终止性与良基关系 Termination · Well-founded relation · Ranking function 用不存在无限下降链与严格递减排名函数刻画程序或转移系统的终止。 。于是从初始配置 ( 0 , P ; 0 , Q ; ϵ , ϵ ) 出发,每条不能再延长的归约序列都恰好含 2 N 步,且完整结束;不能据此断言一个现实调度器不会永远暂停一个可执行线程。同步片段每次同时完成两端义务,这里每条消息则需要一次发送和一次接收。
令 L 是 S 中最长同方向连续动作段的长度,N = 0 时取 L = 0 。由不变量,非空队列恰好对应某个全发送或全接收区间,因此每个可达状态满足
| q A B | + | q B A | = | i − j | ≤ L . 这个上界可达到:先执行到最长段的起点并清空队列,再让该段的发送方连续执行 L 次。示例中 L = 2 ,第二步恰好占满两槽。若实现给每个方向至少 L 个槽,上述可达执行无需因满缓冲区阻塞;若容量更小,必须明确增加发送阻塞规则,原先“发送总可执行”的证明就需调整。
队列纪律解决的是单条会话内的进度错位。前面的双会话死锁网络在空队列下依然没有任何可执行的发送,因而不能从这里的两执行者定理推广出任意网络无死锁。
参考资料
[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证明保持。该系统还含子类型与通道传递;本页另行给出有限基本值协议的精确不变量及证明。