立方之外:相继式演算

· · 算法·理论

前言

在 对 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} $$ 以及弱化、收缩、交换等结构规则,就构成了一个比较完整的相继式风格描述框架。