用规则规定计算行为

操作语义是编程语言形式语义的一种方法:先确定程序执行时需要描述的配置,再给出哪些配置能够转变、如何得到结果的规则。对简单算术表达式,配置可以只有表达式本身;对带变量赋值的命令,通常还要包括存储状态。记作 σ 的状态可把变量名映射到整数,例如 σ(x)=2。

这些规则不是一段程序的运行日志,而是适用于所有符合条件程序的定义。规则的前提说明某个子表达式如何求值,结论说明较大表达式或命令如何继续。语法相同的语言若采用不同求值顺序、不同变量绑定方式,行为可能不同,操作语义正把这些容易隐含在实现中的选择明确写出来。

参考:[1] [2]

小步语义保留中间过程

小步语义用一步转移关系描述计算,例如 e→e′ 表示表达式 e 可执行一步得到 e′。若规定先计算加号左侧,再计算右侧,表达式 (1+2)+(3+4) 的过程就是 (1+2)+(3+4)→3+(3+4)→3+7→10。这里每一步由具体求值规则支持,不是任意选择一种看起来方便的化简顺序。

这种定义需要区分基本运算规则和上下文规则:前者规定两个数怎样相加,后者规定较大表达式中哪个子表达式可以先走一步。对赋值命令 x:=x+1,初始状态若令 x 为 2,右侧可先读出 2,再算成 3,最后更新状态,使 x 映射到 3,并把命令化为已完成的 skip。

小步中的一步是语言定义选取的抽象粒度,并不天然对应一条机器指令。把存储变化纳入配置后,程序顺序、循环展开及不同执行路径都能在转移关系中讨论。

参考:[2]

大步语义联系输入与结果

大步语义通常写作 e⇓v,表示表达式 e 求值为 v。上述算术例子不必逐项列出整个转移链,而是分别证明两个子表达式求值为 3 和 7,再由加法规则推出总体结果为 10。对命令,则可把初始配置与最终存储状态联系起来。

大步并不是不关心子计算,也不是凭直觉直接写答案。它的推导树仍须证明各个前提;顺序命令的规则会把第一条命令得到的状态交给第二条命令。区别在于,关系主要总结完整计算的起点和终点,而不是把每个中间配置都作为单独一步暴露出来。对设计相容的规则,可以证明大步结果与小步执行到终态的结果一致。

参考:[1] [2]

非终止与实现之间的距离

差别在不结束的计算中尤其明显。不断执行的循环可以形成无限小步序列;在通常以有限推导树定义的大步关系中,它没有最终结果的推导。单看“无法推导出结果”,往往又不能区分一直循环与卡在没有适用规则的错误配置。要讨论这些差异,就需分析转移结构,或扩充所用语义形式,而不能把所有无结果情况统称为同一种失败。

操作语义可以作为解释器正确性的参照,也可用于证明程序等价或语言安全性质,但不等于指定某个解释器的代码布局与性能。实现可以使用栈、寄存器或其他内部结构;需要核对的是这些实现步骤是否保持语言规定的可观察行为,而不是要求它逐字照抄语义规则。

参考:[1] [2]