族谱网 头条 人物百科

操作语义学

2020-10-16
出处:族谱网
作者:阿族小谱
浏览:458
转发:0
评论:0
结构操作语义戈登·普罗特金(GordonPlotkin)在(Plotkin04a)中引入了结构操作语义的概念作为一个定义操作语义的逻辑方式。其基本主意是使用程序组成部分的行为来定义一个程序的行为,由此来提供一个对操作语义结构性的,即按照句法和归纳性的,分析。结构操作语义对一个程序的行为的说明是通过一(组)变化关系来表示的。其形式是一系列推理规则,这些推理规则通过一组句法的转换来定义该组的合理转换。比如我们考虑一个简单计算机语言的部分语义,在Plotkin04a和Hennessy90以及其它教科书中有相应的图像。设C1,C2{\displaystyleC_{1},C_{2}}为该语言的程序域,s{\displaystyles}是状态域(即函数的存储地址及值)。假如我们有表述(E{\displaystyleE}的域)、值(V{\displaystyleV})和存储地址(L{\displayst...

结构操作语义

戈登·普罗特金(Gordon Plotkin)在(Plotkin04a)中引入了结构操作语义的概念作为一个定义操作语义的逻辑方式。其基本主意是使用程序组成部分的行为来定义一个程序的行为,由此来提供一个对操作语义结构性的,即按照句法和归纳性的,分析。结构操作语义对一个程序的行为的说明是通过一(组)变化关系来表示的。其形式是一系列推理规则,这些推理规则通过一组句法的转换来定义该组的合理转换。

比如我们考虑一个简单计算机语言的部分语义,在Plotkin04a和Hennessy90以及其它教科书中有相应的图像。设C1,C2{\displaystyle C_{1},C_{2}}为该语言的程序域,s{\displaystyle s}是状态域(即函数的存储地址及值)。假如我们有表述(E{\displaystyle E}的域)、值(V{\displaystyle V})和存储地址(L{\displaystyle L}),则一个存储更新指令的语义为: ⟨ ⟨ -->E,s⟩ ⟩ -->⇒ ⇒ -->V⟨ ⟨ -->L:=E,s⟩ ⟩ -->⟶ ⟶ -->(s⊎ ⊎ -->(L↦ ↦ -->V)){\displaystyle {\frac {\langle E,s\rangle \Rightarrow V}{\langle L:=E\,,\,s\rangle \longrightarrow (s\uplus (L\mapsto V))}}}

使用普通语言,这个公式说假如在s{\displaystyle s}状态的E{\displaystyle E}的值为V{\displaystyle V}则程序L:=E{\displaystyle L:=E}会通过L=V{\displaystyle L=V}更新s{\displaystyle s}的状态。

系列的语义可以用下列规则来表达: ⟨ ⟨ -->C1,s⟩ ⟩ -->⟶ ⟶ -->⟨ ⟨ -->C1′,s′⟩ ⟩ -->⟨ ⟨ -->C1;C2,s⟩ ⟩ -->⟶ ⟶ -->⟨ ⟨ -->C1′;C2,s′⟩ ⟩ -->⟨ ⟨ -->C1,s⟩ ⟩ -->⟶ ⟶ -->s′⟨ ⟨ -->C1;C2,s⟩ ⟩ -->⟶ ⟶ -->⟨ ⟨ -->C2,s′⟩ ⟩ -->⟨ ⟨ -->skip,s⟩ ⟩ -->⟶ ⟶ -->s{\displaystyle {\frac {\langle C_{1},s\rangle \longrightarrow \langle C_{1}",s"\rangle }{\langle C_{1};C_{2}\,,s\rangle \longrightarrow \langle C_{1}";C_{2}\,,s"\rangle }}\quad {\frac {\langle C_{1},s\rangle \longrightarrow s"}{\langle C_{1};C_{2}\,,s\rangle \longrightarrow \langle C_{2},s"\rangle }}\quad {\frac {}{\langle \mathbf {skip} ,s\rangle \longrightarrow s}}}

第一个规则说假如处于状态s{\displaystyle s}的程序C1{\displaystyle C_{1}}可以被简化为处于状态s′{\displaystyle s"}的程序C1′{\displaystyle C_{1}"}的话则处于状态s{\displaystyle s}的程序C1;C2{\displaystyle C_{1};C_{2}}能被简化为处于状态s′{\displaystyle s"}的程序C1′;C2{\displaystyle C_{1}";C_{2}}。第二个规则说假如处于状态s{\displaystyle s}的程序C1{\displaystyle C_{1}}以状态s′{\displaystyle s"}结束的话,则处于状态s{\displaystyle s}的程序C1;C2{\displaystyle C_{1};C_{2}}可以简化为处于状态s′{\displaystyle s"}的程序C2{\displaystyle C_{2}}。这里的语义是结构化的,因为程序序列C1;C2{\displaystyle C_{1};C_{2}}的意义是由C1{\displaystyle C_{1}}的意义和C2{\displaystyle C_{2}}的意义定义的。

假如我们还有状态的布尔函数表示B{\displaystyle B}的话我们可以定义while指令的语义: ⟨ ⟨ -->B,s⟩ ⟩ -->⇒ ⇒ -->true⟨ ⟨ -->while B do C,s⟩ ⟩ -->⟶ ⟶ -->⟨ ⟨ -->C;while B do C,s⟩ ⟩ -->⟨ ⟨ -->B,s⟩ ⟩ -->⇒ ⇒ -->false⟨ ⟨ -->while B do C,s⟩ ⟩ -->⟶ ⟶ -->s{\displaystyle {\frac {\langle B,s\rangle \Rightarrow \mathbf {true} }{\langle \mathbf {while} \ B\ \mathbf {do} \ C,s\rangle \longrightarrow \langle C;\mathbf {while} \ B\ \mathbf {do} \ C,s\rangle }}\quad {\frac {\langle B,s\rangle \Rightarrow \mathbf {false} }{\langle \mathbf {while} \ B\ \mathbf {do} \ C,s\rangle \longrightarrow s}}}

这样的定义允许对程序行为进行公式化的分析和研究程序间的关系。

由于结构操作语义看上去非常易懂,结构简单,因此它获得了很大的欢迎,实际上成为定义操作语义的标准。结构操作语义最初的报告因此获得了约900次引用,成为计算机科学中被引用最多的技术报告之一。

参考资料

Adriaan van Wijngaarden等,《Revised Report on the Algorithmic Language ALGOL 68》,IFIP,1968年([2])

Gordon D. Plotkin,《The Origins of Structural Operational Semantics》,JALP,60-61:3-15, 2004年(preprint)

Dana S. Scott,《Outline of a Mathematical Theory of Computation, Programming Research Group, Technical Monograph PRG–2》,牛津大学,1970年

Gordon D. Plotkin,A Structural Approach to Operational Semantics,(1981年),Tech. Rep. DAIMI FN-19, Computer Science Department, Aarhus University, Aarhus, Denmark. Reprinted with corrections in J. Log. Algebr. Program. 60-61: 17-139(2004年)(preprint).

Matthew Hennessy,《Semantics of Programming Languages》. Wiley, 1990年.网上.


免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。

——— 没有了 ———
编辑:阿族小谱
发表评论
写好了,提交
{{item.label}}
{{commentTotal}}条评论
{{item.userName}}
发布时间:{{item.time}}
{{item.content}}
回复
举报
点击加载更多
打赏作者
“感谢您的打赏,我会更努力的创作”
— 请选择您要打赏的金额 —
{{item.label}}
{{item.label}}
打赏成功!
“感谢您的打赏,我会更努力的创作”
返回

更多文章

更多精彩文章
打赏
私信

推荐阅读

· 语义学
语言学的语义学若从严格意义上的语言学研究来分类,在现代语言学的语义学中,可以分为结构主义的语义学研究和生成语言学的语义学研究。结构主义语义学是从20世纪上半叶以美国为主的结构主义语言学发展而来的,研究的内容主要在于词汇的意义和结构,比如说义素分析,语义场,词义之间的结构关系等等。这样的语义学研究也可以称为词汇语义学,词和词之间的各种关系是词汇语义学研究的一个方面,例如同义词、反义词,同音词等,找出词语之间的细微差别。生成语义学是20世纪六七十年代流行于生成语言学内部的一个语义学分支,是介于早期的结构主义语言学和后来的形式语义学之间的一个理论阵营。生成语义学借鉴了结构语义学对义素的分析方法,比照生成音系学的音位区别特征理论,主张语言的最深层的结构是义素,通过句法变化和词汇化的各种手段而得到表层的句子形式。形式语义学是从20世纪70年代开始发展出来的一个理论阵营。最初的研究开始于蒙太古以数理逻...
· 公理语义学
参见代数语义学(英语:Algebraicsemantics(computerscience))指称语义学操作语义学形式语义学谓词变换语义学(英语:Predicatetransformersemantics)断言(程序)参考文献
· 形式语义学
外部链接SemanticswithApplications定义
· 操作系统
历史各类平台上操作系统的功能演化综观电脑之历史,操作系统与电脑硬件的发展息息相关。操作系统之本意原为提供简单的工作排序能力,后为辅助更新更复杂的硬件设施而渐渐演化。从最早的批量模式开始,分时机制也随之出现,在多处理器时代来临时,操作系统也随之添加多处理器协调功能,甚至是分布式系统的协调功能。其他方面的演变也类似于此。另一方面,在个人电脑上,个人电脑之操作系统因袭大型机的成长之路,在硬件越来越复杂、强大时,也逐步实践以往衹有大型机才有的功能。总而言之,操作系统的历史就是一部解决电脑系统需求与问题的历史。1980年代前IBMSystem/360,大型主机的经典之作第一部电脑并没有操作系统。这是由于早期电脑的创建方式(如同建造机械算盘)与性能不足以运行如此程序。但在1947年发明了晶体管,以及莫里斯·威尔克斯发明的微程序方法,使得电脑不再是机械设备,而是电子产品。系统管理工具以及简化硬件操作流程...
· 实时操作系统
设计理念通常,实时操作系统分为两大类:事件驱动型。当一个高优先级的任务需要执行时,系统会自动切换到这个任务。这种根据优先级调度任务的方式称为抢占式任务处理。时间触发型。每个任务在各自设定好的的时间间隔内重复、轮流调度。时间触发型设计往往比较严格地调度任务,具有更好的多任务处理能力。多个任务被不停地轮流调度,在宏观上,就相当于一个CPU同时执行多个任务。在过去,CPU在切换任务时往往需要多个机器周期,在这段时间内,CPU不能处理其他任何任务。例如,一个20MHz的摩托罗拉68000处理器(1980年代后期),在切换任务时需要花费20微秒。(相比之下,一个100MHz的ARM架构的处理器(2008年之后的)只需要3微秒。)因此,早期的实时操作系统通过减少任务切换次数来避免消耗过多CPU时间。任务调度在典型的设计中,一个任务有以下三种状态:正在运行(Running,正在CPU中执行)待命(Rea...

关于我们

关注族谱网 微信公众号,每日及时查看相关推荐,订阅互动等。

APP下载

下载族谱APP 微信公众号,每日及时查看
扫一扫添加客服微信