操作语义
操作语义通过指定程序的执行方式来定义其含义，使用描述计算步骤的推理规则。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
操作语义将程序的含义指定为其执行的计算步骤序列，该序列由程序配置上归纳定义的转换关系给出。
Scope
本主题涵盖小步（结构化）和大步（自然）操作语义，其中由语法导向推理规则定义的转换或求值关系描述了程序如何计算。它涉及归约策略、抽象机以及操作定义如何支持类型健全性和程序等价性的证明。
Core questions
- 推理规则如何捕捉计算的步骤？
- 小步语义和大步语义之间有什么区别？
- 操作语义如何支持健全性和等价性证明？
- 抽象机与基于规则的操作定义有何关联？
Key theories
- 结构化操作语义
- Plotkin通过根据语言语法构建的小步转换规则来定义执行，提供了对每个构造如何计算的组合式、语法导向的描述。
- 自然（大步）语义
- Kahn的自然语义通过求值规则将程序直接与其最终结果关联起来，抽象掉了中间步骤并简化了某些证明。
Clinical relevance
操作语义是指定真实语言行为并证明编译器和解释器正确性的标准工具。其基于规则的风格与实现紧密对应，并构成了机器验证语言元理论的基础。
History
操作思想出现在早期基于解释器的语言定义中。Plotkin于1981年发布的奥胡斯笔记将结构化操作语义确立为一个严谨的、语法导向的框架，而Kahn于1987年提出的自然语义则提供了一种大步替代方案。它们共同成为定义和推理编程语言的主导方法。
Debates
- 小步与大步形式化
- 语义学家在小步语义和大步语义之间进行选择：小步语义揭示中间状态并自然处理非终止和并发，而大步语义简洁但不太适合发散或交错的计算。
Key figures
- Gordon Plotkin
- Gilles Kahn
- Glynn Winskel
- Matthias Felleisen
Related topics
Seminal works
- plotkin1981
- kahn1987
- winskel1993
Frequently asked questions
- 小步语义和大步语义之间有什么区别？
- 小步语义描述了单个计算步骤及其之间的中间状态，而大步语义则将程序直接与其最终值关联起来，隐藏了中间步骤。
- 为什么操作语义对证明健全性很有用？
- 因为它明确了执行步骤，所以它与进展和保持方法自然结合，该方法推理程序在每一步中如何保持类型。