[例] 良类型与不良类型

使用 [定义] 类型与类型判断 的七条类型规则,良类型与不良类型的含义见 [定义] 良类型 。

良类型的例子。要说明 if ( iszero 0 ) then  succ 0 else 0: Nat,从结论往上搭推导:

  1. 项的最外层是 if,结论形如 if …:𝑇 的规则只有 T-If。取 𝑇= Nat,它要求三个前提:iszero 0: Bool、succ 0: Nat、0: Nat。
  2. 第一个前提 iszero 0: Bool:只有 T-IsZero 的结论形如 iszero …,结论类型恰好是 Bool,它要求 0: Nat。T-Zero 给出这一点。
  3. 第二个前提 succ 0: Nat:用 T-Succ,它要求 0: Nat,再用 T-Zero。
  4. 第三个前提 0: Nat:直接用 T-Zero。

每个前提都搭上了,合起来就是一棵完整的推导:

不良类型的例子。要说明 succ  true 没有类型,得证明对任何 𝑇 都搭不出 succ  true :𝑇 的推导。我们可以直接穷举七条规则:

  1. 结论左边形如 succ … 的规则只有 T-Succ,其余六条的结论形状对不上,直接排除。所以如果有推导,最后一步只能是 T-Succ,此时 𝑇= Nat,前提是 true : Nat。
  2. 再看 true : Nat。结论左边是 true 的规则只有 T-True,而它的结论是 true : Bool,类型是 Bool 不是 Nat,搭不上。没有别的规则可选。

唯一可能作为最后一步的 T-Succ 无法满足它的前提,因此不存在合法的推导树,succ  true 是不良类型的。

References

[定义] 良类型 [well-typed-terms]

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

Backlinks

Based on Typsite