立方之外:相继式演算
myz142857
·
·
算法·理论
前言
在 对 STLC 的介绍 中,为了描述 STLC 的规则,我们用到了如下的一种形式化语言:
\frac{x : \tau \in \Gamma}{\Gamma \vdash x : \tau}
\frac{\Gamma, x : \tau_1 \vdash M : \tau_2}{\Gamma \vdash (\lambda x : \tau_1.M): \tau_1 \to \tau_2}
\frac{\Gamma \vdash M : \tau_1 \to \tau_2 \qquad \Gamma \vdash N : \tau_1}{\Gamma \vdash M \, N : \tau_2}
这种用横线、前提和结论来描述推导的形式,常见于相继式演算(sequent calculus)和类型论中的推导规则。STLC 的三条规则属于类型论中的类型判断(typing judgment),写法与相继式演算非常相似。
语法描述
相继式演算一般由公式(formula)、相继式(sequent)和规则(rule)三种“组件”组成。
公式
公式是相继式演算中最基本的组成成分。在不同的形式系统中,公式可能有不同的结构,比如在 STLC 中,公式就是形如
M : \tau
的类型判断,而在其他系统中,公式还可能是命题(形如 P)、类型(形如 \tau)等。
相继式
相继式是形如
A_1, A_2, \cdots, A_n \vdash B_1, B_2, \cdots,B_m
的基础判断。
这个相继式的含义为:
> 如果 $A_1, A_2, \cdots, A_n$ 全部成立,则 $B_1, B_2, \cdots, B_m$ 中至少有一个成立。
特别地,当 $A$ 为空($n = 0$)时,说明 $B$ 的成立不需要条件;当 $B$ 为空($m = 0$)时,则说明 $A$ 不可能成立。
::::warning[注意]{open}
现在很多文章都会采用“单结论”的规则,即令 $m$ 恒为 1,此时相继式形式变为
$$
A_1, A_2, \cdots, A_n \vdash B
$$
然后还会有人把 $\Gamma \vdash B_1 \quad \Gamma \vdash B_2 \quad \cdots \quad \Gamma \vdash B_n$ 缩写成 $\Gamma \vdash B_1, B_2, \cdots, B_n$,导致同一套符号出现了完全相反的语义……
为避免歧义,本系列文在 $\vdash$ 右侧只允许单个公式;多结论相继式会在使用时另行说明。
::::
### 规则
规则是形如
$$
\frac{P_1 \quad P_2 \quad \cdots \quad P_n}{Q}
$$
的推导规则,其中 $P_i$ 和 $Q$ 都是相继式,$P_i$ 称为**前提**(**premise**),$Q$ 称为**结论**(**conclusion**)。与后继不同,结论有且只有一个。
这个规则的含义为:
> 如果 $P_1 \quad P_2 \quad \cdots \quad P_n$ 全部成立,则 $Q$ 成立。
特别地,当 $P$ 为空($n = 0$)时,$Q$ 也称作**公理**(**axiom**)。
::::info[没了?]{open}
对,没了。就是这么简单。
以及,
$$
\frac{x : \tau \in \Gamma}{\Gamma \vdash x : \tau}
$$
中的 $\in$ 符号并不是标准的相继式演算语法,待会我们会用更标准的方式重写它。
::::
## 结构规则
前面给出的推导规则已经能描述很多基本推理,但在实际证明中,我们通常还会用到一些**结构规则**。它们不直接引入新的逻辑连接词或类型构造子,而是处理上下文中的重复、顺序和多余假设。
常见的结构规则包括:**弱化**(**weakening**)、**收缩**(**contraction**)和**交换**(**exchange**)。
### 弱化
弱化规则表示,如果一个判断已经成立,那么在上下文中增加一个额外假设后,它仍然成立:
$$
\frac{\Gamma \vdash M : \tau}{\Gamma, x : \sigma \vdash M : \tau}
$$
直观上,这相当于说:如果我们在已有假设下已经能推出 $M : \tau$,那么再额外假设一个与 $M$ 无关的 $x : \sigma$,并不会破坏原来的推导。
### 收缩
收缩规则表示,如果同一个假设在上下文中出现了两次,可以合并为一次:
$$
\frac{\Gamma, x : \sigma, x : \sigma \vdash M : \tau}{\Gamma, x : \sigma \vdash M : \tau}
$$
在类型论中,上下文通常被约定为不包含重复绑定(称作重影,shadowing),所以收缩规则更多出现在逻辑系统的讨论中。
#### 交换
交换规则表示,上下文中假设的顺序不影响推导结果:
$$
\frac{\Gamma_1, x : \sigma, y : \rho, \Gamma_2 \vdash M : \tau}{\Gamma_1, y : \rho, x : \sigma, \Gamma_2 \vdash M : \tau}
$$
如果上下文被看作集合或无序映射,交换规则通常会被隐含地接受;如果上下文被严格看作序列,则需要显式写出交换规则。
## 截断规则
**截断规则**,也叫**切规则**,它描述的是,如果某个中间结论可以作为另一个推导的前提,那么可以把这个中间结论“消去”:
$$
\frac{\Gamma \vdash N : \sigma \qquad \Gamma, x : \sigma \vdash M : \tau}{\Gamma \vdash M[N / x] : \tau}
$$
这里的 $M[N / x]$ 表示把 $M$ 中所有**自由出现**[^1] 的 $x$ 替换为 $N$。
[^1]: 意为未被绑定。例如,$x$ 中的 $x$ 是自由出现的,而 $\lambda x.x$ 中的 $x$ 则不是,因为它被一个 $\lambda$ 绑定。
截断规则对应于证明中的“中间引理”:你可以先证明 $N : \sigma$,再在假设 $x : \sigma$ 下证明 $M : \tau$,最后把两者连接起来。
截断规则与 **$\beta$-归约**密切相关。也就是说,截断消除过程可以对应到项的归约过程。
## 变量规则的改写
前面我们曾用
$$
\frac{x : \tau \in \Gamma}{\Gamma \vdash x : \tau}
$$
表示变量规则。这里的 $\in$ 并不是相继式演算或类型论推导规则本身的正式语法,它只是说明“$x : \tau$ 出现在上下文 $\Gamma$ 中”。
重新审视一下变量规则:如果一个类型推断出现在上下文里,我们就可以直接推导出它。于是更形式化地,我们可以写:
$$
\frac{}{\Gamma, x : \tau, \Delta \vdash x : \tau}
$$
并且约定上下文 $\Gamma$ 和 $\Delta$ 中不包含其他关于 $x$ 的绑定。
## 整合后的 STLC 基础规则
综合起来,STLC 的基础类型推导规则可以写成:
$$
\frac{}{\Gamma, x : \tau, \Delta \vdash x : \tau}
$$
$$
\frac{\Gamma, x : \tau_1 \vdash M : \tau_2}{\Gamma \vdash \lambda x : \tau_1.\, M : \tau_1 \to \tau_2}
$$
$$
\frac{\Gamma \vdash M : \tau_1 \to \tau_2 \qquad \Gamma \vdash N : \tau_1}{\Gamma \vdash M \, N : \tau_2}
$$
再加上截断规则:
$$
\frac{\Gamma \vdash N : \sigma \qquad \Gamma, x : \sigma \vdash M : \tau}{\Gamma \vdash M[N / x] : \tau}
$$
以及弱化、收缩、交换等结构规则,就构成了一个比较完整的相继式风格描述框架。