[推论] 良类型项求值到唯一的同类型值

采用 [定义] 词项的集合 的有限项、 [定义] 值与数值 的值、 [定义] 多步归约 的多步归约,以及 [定义] 类型与类型判断 的类型规则。若 𝑡:𝑇,则存在唯一的值 𝑣,使得

𝑡⟶ ∗𝑣 且 𝑣:𝑇.

证明

存在性。从 𝑡 出发,只要有后继就继续归约。由 [引理] 归约使大小严格下降 ,每步大小严格下降,归约链至多有 size( 𝑡 )−1 步,因而必能到达一个没有后继的项 𝑢。由 [定理] 保型 对链长归纳,𝑢:𝑇。再用 [定理] 进展 :𝑢 是值或能归约,而后一种情况已被排除,所以 𝑢 是具有类型 𝑇 的值。

唯一性。设 𝑡⟶ ∗𝑣 且 𝑡⟶ ∗𝑤,其中 𝑣、𝑤 都是值。对第一条链的长度归纳;归纳性质允许第二条链任意长。

  • 零步:𝑡=𝑣。由 [引理] 值不可归约 ,𝑡 没有后继,因此第二条链也只能有零步,𝑤=𝑡=𝑣。
  • 至少一步:第一条链形如 𝑡⟶𝑡 1⟶ ∗𝑣。𝑡 能归约,故由 [引理] 值不可归约 它不是值;第二条链不能有零步,形如 𝑡⟶𝑡 2⟶ ∗𝑤。由 [定理] 确定性 ,𝑡 1=𝑡 2。两条剩余链从同一项出发,第一条的长度更小,由 归纳假设 得 𝑣=𝑤。
∎

[推论] 类型安全 只排除受阻,不独自保证终止。这条推论还用到了另行证明的终止性与确定性;它针对上述未扩展语言,不能直接推广到含一般递归或其他求值规则的语言。

References

[定义] 归纳假设 [induction-hypothesis]

[定义] 多步归约 [multi-step-reduction]

[定理] 保型 [preservation]

[定理] 进展 [progress]

[定义] 词项的集合 [set-of-terms]

[引理] 归约使大小严格下降 [reduction-decreases-size]

[推论] 类型安全 [type-safety]

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

[定理] 确定性 [determinism]

[定义] 值与数值 [values-and-numeric-values]

[引理] 值不可归约 [values-do-not-reduce]

Backlinks

Based on Typsite