[] 范式、受阻与多步归约

1 [定义] 范式与受阻 [normal-forms-and-stuck-terms]

采用 [定义] 一步归约 的关系 ⟶。若不存在 𝑡 ′ 使 𝑡⟶𝑡 ′,称 𝑡 是范式(normal form)。按 [定义] 值与数值 判断,不是值的范式称为受阻的(stuck)。

“范式”这个词的意思是“标准的、最终的形式”:一个项归约到不能再归约,就到了它的范式,好比把 ( 1+2 )×3 化简到 9 就化简不下去了。注意范式是按能不能归约定义的,和项“好不好”无关。范式分成两种:

  • 值:算完了,而且是一个合法的结果。由 [引理] 值不可归约 ,值都是范式。例如 true、succ 0。
  • 非值(受阻的项):不能再归约,但也不是值,计算停在了一个没有意义的地方。例如:

    • succ  true:唯一可能的规则 E-Succ 要求 true 能归约,而它不能;它又不是数值,所以不是值;
    • if 0 then  true  else  false:E-IfTrue、E-IfFalse 要求条件是 true 或 false,E-If 要求 0 能归约,三条都用不上;
    • iszero  false:E-IsZeroZero、E-IsZeroSucc 要求参数是数值,E-IsZero 要求 false 能归约,都不行。

2 [附注] 为什么译作“受阻” [translation-of-stuck]

stuck 字面是“卡住”,TAPL 的一些中文译本也这样译。 [定义] 范式与受阻 采用“受阻”这个译名,理由有两点。第一,“卡住”在日常语言里也指程序“卡死、没反应”,即无限循环或死锁,而 stuck 恰恰不是这个意思:受阻的项已经停下来了,只是停错了地方。第二,“受阻”点出了停下来的原因:计算想往前推进,却被一个没有定义的情形挡住了。例如按 [定义] 一步归约 的规则,succ  true 既不是值,也没有可用的归约步骤。英文原名始终写在括号里,读文献时对得上即可。

受阻对应真实语言里的错误(error):程序要做一件语义里没有定义的事,比如把布尔值加一,目前我们只能把这个错误拖到运行时,也就是运行时错误(runtime error)。下一节的类型系统要做的,就是在不运行程序的前提下,提前把会走到受阻状态的程序找出来,可以让它们成为编译期错误(compiletime error)。

3 多步归约

一步归约只描述“一次改写”。程序真正运行时要连续改写很多次,所以需要把若干步串起来。

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

以 [定义] 一步归约 的关系 ⟶ 为基础,𝑡⟶ ∗𝑡 ′ 读作“𝑡 多步归约到 𝑡 ′”,表示从 𝑡 出发经过零步或有限多步一步归约到达 𝑡 ′。精确地说,它是对下面两条规则封闭的最小关系:

M-Refl 说“零步归约”永远成立(自反),M-Step 说在一步后面接上若干步还是若干步。由于取的是最小关系,𝑡⟶ ∗𝑡 ′ 成立当且仅当存在一条有限的链 𝑡=𝑡 0⟶𝑡 1⟶⋯⟶𝑡 𝑛=𝑡 ′(𝑛≥0)。⟶ ∗ 上角的星号来自正则表达式里的 Kleene 星号,意思是“重复零次或多次”,数学上称 ⟶ ∗ 为 ⟶ 的自反传递闭包(reflexive transitive closure)。

3.2 [例] 多步归约到值 [multi-step-reduction-to-a-value]

采用 [定义] 一步归约 的十条规则,⟶ ∗ 表示 [定义] 多步归约 的零步或有限多步归约;终点是否为值按 [定义] 值与数值 判断。

 if ( iszero ( pred ( succ 0 ) ) ) then  succ 0 else 0⟶ if ( iszero 0 ) then  succ 0 else 0 E-If + E-IsZero + E-PredSucc ⟶ if  true  then  succ 0 else 0 E-If + E-IsZeroZero ⟶ succ 0 E-IfTrue

每行右边列出了这一步推导用到的规则,从外层的同余规则写到最里层的计算规则。三步之后到达值 succ 0,所以

if ( iszero ( pred ( succ 0 ) ) ) then  succ 0 else 0⟶ ∗ succ 0

由 [定理] 确定性 ,每一步都别无选择,所以这条链是唯一的。⟶ ∗ 也包括中间每一站:这个项也多步归约到第二行、第三行的项,以及它自己(零步)。

3.3 [例] 归约到受阻 [reduction-to-a-stuck-term]

按 [定义] 一步归约 的规则,取 𝑡= succ ( if  true  then  false  else 0 )。是否为值采用 [定义] 值与数值 ,是否受阻采用 [定义] 范式与受阻 。

第一步。𝑡 的最外层是 succ。结论左边形如 succ … 的规则只有 E-Succ,它要求里面的 if  true  then  false  else 0 能归约。这个 if 的条件是 true,E-IfTrue 适用,得到 false。于是推导是:

第二步。现在的项是 succ  false。仍然只有 E-Succ 可能适用,它要求 false ⟶𝑡 1 ′ 对某个 𝑡 1 ′ 成立。但 false 是值,由 [引理] 值不可归约 不能归约,于是 E-Succ 的前提搭不上,没有任何规则可用:succ  false 是范式。它又不是值(succ 后面必须是数值),所以它受阻了。

第一步完全合法,问题出在第二步。所以一个项“现在还能归约”并不说明它“永远不会出错”。

4 练习:求值
本节练习(5题)

练习3.1:值、范式与受阻别混在一起

对下列五个项分别判断:是否为值、是否为范式、是否受阻。能够归约的,还要给出下一项和规则名:succ ( succ 0 )、pred ( succ 0 )、succ  true、if  true  then 0 else ( succ  true )、if 0 then 0 else 0。
提示先用 [定义] 值与数值 判断值,再问是否存在一步归约;“范式”与“受阻”按 [定义] 范式与受阻 判断。
参考答案
  • succ ( succ 0 ) 是数值,也是值和范式,不受阻。
  • pred ( succ 0 ) 不是值,也不是范式:E-PredSucc 给出后继 0,所以现在不受阻。
  • succ  true 不是值,是受阻的范式:唯一候选 E-Succ 的前提无法成立。
  • if  true  then 0 else ( succ  true ) 不是值,也不是范式;E-IfTrue 直接给出 0。未选中的坏分支不参与求值。
  • if 0 then 0 else 0 不是值,是受阻的范式:条件不是布尔值,也不能归约。

因此“不是值”不等于“受阻”,“有坏的子项”也不等于“现在受阻”。

练习3.2:一条链与第一步的推导树

写出 pred ( if ( iszero ( pred 0 ) ) then  succ ( succ 0 ) else 0 ) 到范式的完整归约链,标明每一步用到的规则,并画出第一步的推导树。使用 [定义] 一步归约 ,不要把两次计算并成一步。
提示第一步不是消去最外层 pred,而是经由三条同余规则进入条件中的 pred 0。
参考答案

 pred ( if ( iszero ( pred 0 ) ) then  succ ( succ 0 ) else 0 )⟶ pred ( if ( iszero 0 ) then  succ ( succ 0 ) else 0 )⟶ pred ( if  true  then  succ ( succ 0 ) else 0 )⟶ pred ( succ ( succ 0 ) )⟶ succ 0

四步所用的规则依次是 E-Pred + E-If + E-IsZero + E-PredZero,E-Pred + E-If + E-IsZeroZero,E-Pred + E-IfTrue,E-PredSucc。第一步的完整推导是:

最后 succ 0 是值,没有后继。多步归约还包括链的中间各站与起点自身,不只是最终结果。

练习3.3:扩展:函数选一条路,不等于关系只有一条路

只把 E-PredSucc 的 放宽为任意项,其余规则不变。为 pred ( succ ( iszero 0 ) ) 找出两个不同的一步后继,并分别继续归约。这个例子证明了什么、没有证明什么?如果 step step 用 match match 只返回其中一个,能否据此声称扩展关系仍确定?
提示使用 [附注] 为什么 E-PredSucc 要求 的放宽规则时,可以消去外层,也可以先在 iszero 0 里计算。
参考答案

把 E-PredSucc 改成允许任意 𝑡 的 pred ( succ 𝑡 )⟶𝑡 后,取 𝑠= pred ( succ ( iszero 0 ) )。直接消去外层得到 𝑠⟶ iszero 0;先用同余规则进入内部,得到 𝑠⟶ pred ( succ  true )。

两个后继不同,所以一步关系不确定。第一条路线再用 E-IsZeroZero 到 true,第二条路线再用放宽的 E-PredSucc 到 true;因此这个分叉可以汇合。但一个可汇合的例子不证明整套扩展关系合流。

Rust 函数即使按分支优先级选出唯一返回值,也没有消除关系的另一条合法路线。要么实现“所有后继”的接口,要么明确说这个单后继函数实现的是选定策略限制后的关系。注意扩展规则下 pred ( succ  true ) 能归约,不能照搬它在原语言中受阻的判断。

练习3.4:换一个相等三角形

对 "" "" 、 0 0 、 "0" "0" 两两计算 == == 与 === === 的结果,画出另一个相等三角形。再按“新值与任何已保留值满足 == == 就丢弃”的算法,分别去重 ["", 0, "0"] ["", 0, "0"] 与 [0, "", "0"] [0, "", "0"] 。它们为什么连保留下来的数量都可能不同?
提示比较空字符串 "" "" 、数字 0 0 和字符串 "0" "0" 。同类字符串的 == == 不会再把两边都转成数字。
参考答案

"" == 0 "" == 0 和 0 == "0" 0 == "0" 为 true true , "" == "0" "" == "0" 为 false false ;三组 === === 都为 false false 。前两次把字符串转为数字,第三次只比较两个不同的字符串。

使用 [附注] 相等关系的“地狱”给语言设计什么教训 的自定义 == == 去重算法,输入 ["", 0, "0"] ["", 0, "0"] 留下 ["", "0"] ["", "0"] ,输入 [0, "", "0"] [0, "", "0"] 只留下 [0] [0] 。规则明确仍可能失去算法所依赖的传递性;改用 === === 后这三种输入彼此不同,不会在这个例子中被合并,但仍要留意对象身份和 NaN NaN 的特殊处理。

练习3.5:扩展:错误只沿实际求值的位置传播

比较原语言与显式错误扩展对 if  true  then 0 else ( succ  true ) 和 pred ( succ  false ) 的处理,写出每一步。最后说明 wrong、Kotlin 的异常对象与 ⊥ 为什么不能当作同一个东西。
提示使用 [附注] 显式错误规则与 Kotlin 的底类型 的错误扩展;不要把未选中的分支当作正在求值的操作数。
参考答案

对 if  true  then 0 else ( succ  true ),原语言与错误扩展都用 E-IfTrue 直接得到 0,不计算 else 分支。

原语言中的 pred ( succ  false ) 没有后继,是受阻的范式。错误扩展先在内部用 E-OpBool,并由 E-Pred 提升到整项,得到 pred  wrong;再用 E-OpWrong 到 wrong。它是明确的异常终点,不是普通数值。

wrong 是错误项, IllegalArgumentException IllegalArgumentException 是异常对象,⊥ 是底类型。Kotlin 的抛异常表达式可以具有 Nothing Nothing 类型,不意味着异常对象是底类型的值,也不意味着未选中的异常分支必须先执行。

References

[附注] 显式错误规则与 Kotlin 的底类型 [explicit-errors-and-kotlin-bottom-type]

[定义] 一步归约 [one-step-reduction]

[] 形式化入门:从 BNF 到类型安全 [index]

[] 确定性:从推导归纳到求值器 [determinism]

[] 类型:语法导向、反演与唯一性 [typing]

[附注] 为什么 E-PredSucc 要求 [numeric-value-restriction-in-predecessor-reduction]

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

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

[附注] 相等关系的“地狱”给语言设计什么教训 [equality-and-language-design]

Backlinks

Based on Typsite