Example.
进展
Example. 进展
采用 类型与类型判断 的类型规则 和 一步规约 的求值规则. 取良类型的项 , 跟着 进展 的证明走一遍.
的推导最后一步是 T-Pred, 前提为 ,对这个子项用 归纳假设 . 子项的推导最后一步是 T-If,前提里有 ; 是值,由 典范形式 知它必为 或 , 这里恰好是 ,于是用 E-IfFalse 得子项 . 回到整项 ,由于子项能规约,用 E-Pred 即得 .
这段证明在断定“能规约”的同时,直接构造出了这一步的推导. 对 再用一次进展: 子项 是值,由 典范形式 它是数值, 且形如 succ nv,于是用 E-PredSucc 得到 . 对 再用一次进展:它是值,停止.