[例]
良类型与不良类型
[例] 良类型与不良类型
使用 [定义] 类型与类型判断 的七条类型规则,良类型与不良类型的含义见 [定义] 良类型 。
良类型的例子。要说明 ,从结论往上搭推导:
- 项的最外层是 ,结论形如 的规则只有 T-If。取 ,它要求三个前提:、、。
- 第一个前提 :只有 T-IsZero 的结论形如 ,结论类型恰好是 ,它要求 。T-Zero 给出这一点。
- 第二个前提 :用 T-Succ,它要求 ,再用 T-Zero。
- 第三个前提 :直接用 T-Zero。
每个前提都搭上了,合起来就是一棵完整的推导:
不良类型的例子。要说明 没有类型,得证明对任何 都搭不出 的推导。我们可以直接穷举七条规则:
- 结论左边形如 的规则只有 T-Succ,其余六条的结论形状对不上,直接排除。所以如果有推导,最后一步只能是 T-Succ,此时 ,前提是 。
- 再看 。结论左边是 的规则只有 T-True,而它的结论是 ,类型是 不是 ,搭不上。没有别的规则可选。
唯一可能作为最后一步的 T-Succ 无法满足它的前提,因此不存在合法的推导树, 是不良类型的。