Example.
良类型与不良类型
Example. 良类型与不良类型
使用 类型与类型判断 的七条类型规则, 良类型与不良类型的含义见 良类型 .
先看良类型的例子. 要说明 ,可以从结论往上搭推导. 项的最外层是 ,结论形如 的规则只有 T-If; 取 ,它要求 、、 三个前提. 第一个前提 只能匹配 T-IsZero(结论类型恰好是 ),再由 T-Zero 满足其前提 ; 第二个前提 用 T-Succ,再接 T-Zero; 第三个前提 直接用 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
再看不良类型的例子. 要说明 没有类型, 得证明对任何 都搭不出 的推导. 逐一检查七条规则:结论左边形如 的规则只有 T-Succ,其余六条形状不符,直接排除; 若存在推导,最后一步只能是 T-Succ,此时 ,且前提要求 . 再看 ,结论左边为 的规则只有 T-True,但 T-True 给出的类型是 ,与所需的 冲突,没有别的规则可选. 唯一可能作为最后一步的 T-Succ 无法满足前提, 因此不存在合法的推导树, 是不良类型的.