Example. 良类型与不良类型

使用 类型与类型判断 的七条类型规则, 良类型与不良类型的含义见 良类型 .

先看良类型的例子. 要说明 if ( iszero 0 ) then  succ 0 else 0: Nat,可以从结论往上搭推导. 项的最外层是 if,结论形如 if …:𝑇 的规则只有 T-If; 取 𝑇= Nat,它要求 iszero 0: Bool、succ 0: Nat、0: Nat 三个前提. 第一个前提 iszero 0: Bool 只能匹配 T-IsZero(结论类型恰好是 Bool),再由 T-Zero 满足其前提 0: Nat; 第二个前提 succ 0: Nat 用 T-Succ,再接 T-Zero; 第三个前提 0: Nat 直接用 T-Zero. 每个前提都搭上了,合起来就是完整的推导:

T-If:前提 [T-IsZero:前提 [T-Zero:前提 [无];结论 0 : Nat];结论 iszero 0 : Bool;T-Succ:前提 [T-Zero:前提 [无];结论 0 : Nat];结论 succ 0 : Nat;T-Zero:前提 [无];结论 0 : Nat];结论 if (iszero 0) then succ 0 else 0 : Nat

再看不良类型的例子. 要说明 succ  true 没有类型, 得证明对任何 𝑇 都搭不出 succ  true :𝑇 的推导. 逐一检查七条规则:结论左边形如 succ … 的规则只有 T-Succ,其余六条形状不符,直接排除; 若存在推导,最后一步只能是 T-Succ,此时 𝑇= Nat,且前提要求 true : Nat. 再看 true : Nat,结论左边为 true 的规则只有 T-True,但 T-True 给出的类型是 Bool,与所需的 Nat 冲突,没有别的规则可选. 唯一可能作为最后一步的 T-Succ 无法满足前提, 因此不存在合法的推导树,succ  true 是不良类型的.