[例] 保型

对 [例] 多步归约到值 的归约链,按 [定义] 类型与类型判断 在每一项旁边写上类型。归约关系使用 [定义] 一步归约 ,保型性质及其证明见 [定理] 保型 :

 if ( iszero ( pred ( succ 0 ) ) ) then  succ 0 else 0: Nat ⟶ if ( iszero 0 ) then  succ 0 else 0: Nat ⟶ if  true  then  succ 0 else 0: Nat ⟶ succ 0: Nat

类型始终是 Nat。以第一步为例看保型的证明怎样工作:这一步的推导是 E-If,前提是 iszero ( pred ( succ 0 ) )⟶ iszero 0。由 [引理] 反演 对 𝑡: Nat 反演,得到条件 : Bool、两个分支 : Nat;对前提用 归纳假设 (取类型 Bool),得到 iszero 0: Bool;两个分支原封不动,再用 T-If 拼回去,得到新项 : Nat。

注意项本身变了很多,从一个 if 变成了 succ 0,但类型这个“静态描述”一直成立。保型说的就是:运行不会让类型说过的话失效。

References

[引理] 反演 [typing-inversion]

[定义] 归纳假设 [induction-hypothesis]

[例] 多步归约到值 [multi-step-reduction-to-a-value]

[定义] 类型与类型判断 [types-and-typing-judgments]

[定义] 一步归约 [one-step-reduction]

[定理] 保型 [preservation]

Based on Typsite