族谱网 头条 人物百科

指称语义

2020-10-16
出处:族谱网
作者:阿族小谱
浏览:501
转发:0
评论:0
递归程序的语义在本节中我们概览作为指称语义的最初主题的函数式递归程序的语义。问题如下。我们需要给予程序如阶乘函数的定义以语义这个阶乘程序的意义应当是在自然数上一个函数,但是由于它的递归定义,如何以复合方式理解它是不明白的。在递归的语义中,域典型的是偏序,它可以被理解为已定义性(definedness)的次序。例如,在自然数上的偏函数的集合可以给出为如下次序:通常假定这个域的某个性质,比如链的极限的存在性(参见cpo)和一个底元素。偏函数的偏序有一个底元素,完全未定义函数。它还有链的最小上界。各种额外性质经常是合理的和有用的:在域理论条目中有更详尽细节。我们特别感兴趣于在域之间的“连续”函数。它们是保持次序结构和保持最小上界的函数。在这种设置下,类型被指示为域,而域的元素粗略的捕获了类型的元素。给予带有自由变量的一个程序段的指称语义,依据它从它的环境类型的指称到它的类型的指称的连续函数。例如...

递归程序的语义

在本节中我们概览作为指称语义的最初主题的函数式递归程序的语义。

问题如下。我们需要给予程序如阶乘函数的定义以语义

这个阶乘程序的意义应当是在自然数上一个函数,但是由于它的递归定义,如何以复合方式理解它是不明白的。

在递归的语义中,域典型的是偏序,它可以被理解为已定义性(definedness)的次序。例如,在自然数上的偏函数的集合可以给出为如下次序:

通常假定这个域的某个性质,比如链的极限的存在性(参见cpo)和一个底元素。偏函数的偏序有一个底元素,完全未定义函数。它还有链的最小上界。各种额外性质经常是合理的和有用的: 在域理论条目中有更详尽细节。

我们特别感兴趣于在域之间的“连续”函数。它们是保持次序结构和保持最小上界的函数。

在这种设置下,类型被指示为域,而域的元素粗略的捕获了类型的元素。给予带有自由变量的一个程序段的指称语义,依据它从它的环境类型的指称到它的类型的指称的连续函数。例如,段落 n*g(n-1) 有类型 Nat,它有两个自由变量: Nat 类型的n 和 Nat -> Nat 类型的 g。所以它的指称将是连续函数

在这个偏函数的次序下,可以如下这样给出阶乘程序的指称。首先,我们必须开发基本构造如 if-then-else, ==, 和乘法的指称。还必须开发函数抽象和应用的指称语义。程序段

可以接着被给予作为在偏函数的域之间的连续函数的一个指称

阶乘程序的指称被定义为函数 F 的最小不动点。它因此是域 (N⇀ ⇀ -->N){\displaystyle (\mathbb {N} \rightharpoonup \mathbb {N} )} 的一个元素。

这种不动点存在的原因是 F 是连续函数。一种版本的Tarski不动点定理声称在域上的连续函数有最小不动点。

证明不动点定理的一种方式给出了为什么以这种方式给出递归的语义合适的直觉认识,所有在域 D 的带有底元素 ⊥ 的连续函数 F:D→D 都有不动点,它给出自

这里的符号 F 指示 F 的 i 次应用。符号“⊔”意味着“最小上界”。

把这个链的构件认为是“迭代”的有益的。在上述阶乘的情况下,我们有在偏函数的域上的函数 F。

F(⊥) 是完全未定义偏函数 N→N;

F(⊥) 是定义在 0 上,得到 1,在其他地方未定义的函数;

F(⊥) 是定义直到 4 的阶乘函数: F(⊥)(4) = 24。它对于大于 4 的参数是未定义的。

所以这个链的最小上界是完全定义的阶乘函数(它凑巧是全函数)。

指称语义的发展

通过研究编程语言的更精细的构造和不同的计算模型,指称语义已经发展起来了。

状态的指称语义

状态(比如堆)和命令特征可以直接用上述指称语义来建模。下面列出的所有教科书都有详情。关键想法是把命令当作在某个状态域上的偏函数。“x:=3”的指称是使一个状态成为带有 3 被赋值给 x 的状态。顺序算符“;”被指示为函数复合。不动点构造被用来给予循环构造如“while”的语义。

在建模有局部变量的程序的时候事情变得更加困难。一种途径是不在使用域,转而把类型解释为从世界的范畴到域的范畴的函子。程序被指示为在这些函子之间的自然连续函数。

数据类型的指称

很多编程语言允许用户定义递归数据类型。例如,数的列表的类型可以指定为

本节只处理不能变更的泛函数据类型。常规编程语言将典型的允许这种递归列表的元素被变更。

另一个例子: 无类型 lambda 演算的指称为

“解域方程”问题关注找到建模这类数据类型的域。有一种途径,粗略的说把所有域的搜集自身当作一个域,并接着在这里解这个递归定义。下面的教科书给出详情。

多态数据类型是定义时带有参数的数据类型。比如 α lists 的类型被定义为

数的列表,接着是有类型 Nat list,而字符串的列表有类型 String list。

一些研究者开发了多态性的域理论模型。其他研究者还在构造性集合论内建模了参数化多态。详情可见下面列出的教科书。

一个新近研究领域已经涉及了基于编程语言的对象和类的指称语义。

受限复杂性的程序的指称语义

随着基于线性逻辑的编程语言的开发,指称语义已经被给予了线性使用(参见 证明网、一致空间)和多项式时间复杂性的语言。

非确定性程序的指称语义

要给出非确定性程序顺序程序指称语义,研究者已经开发出了幂域理论。对幂域构造写上 P,域 P(D) 是指示为 D 的类型的非确定性计算的域。

在非确定性域理论模型中在公正性和无界性上有困难。参见非确定性的幂域。

并发性的指称语义

很多研究者争论说域理论模型不捕获并发计算的本质。为此介入各种新模型。在 1980 年代早期,人们开始使用指称语义的方式给予并发语言以语义。例子包括Will Clinger 关于演员模型的工作;Glynn Winskel 关于事件结构和petri网的工作 ;和 Francez, Hoare, Lehmann 和 de Roever (1979) 关于CSP的跟踪语义的工作。对所有这些工作的质询仍在研究中。

最近,Winskel 和其他人已经提议了 profunctor 范畴作为并发的域理论。

顺序性的指称语义

顺序编程语言 PCF 的完全抽象问题是在指称语义中长时间的重要的开放问题。PCF 的困难在它是绝对的顺序语言。例如,在 PCF 中无法定义并行或函数。为此如上述介绍的使用域的方式,产生了不是完全抽象的指称语义。

这个开放问题在1990年代随着博弈语义和涉及逻辑关系的技术的发展基本解决了。 详情请参见PCF语言。

源到源转换的指称语义

把一个程序语言转换成另一个语言经常是有用的。例如一个并发编程语言可被转换成进程演算;高级编程语言可以被转换成字节码(实际上,常规指称语义可以被看作把编程语言解释成域的范畴的内部语言)。

在这个语境中,来自指称语义的概念,不如完全抽象,有助于满足安全关注。

完全抽象

完全抽象的概念关心程序的指称语义是否精确的匹配它的操作语义。完全抽象的关键性质有:

抽象性: 指称语义必须使用独立于编程语言的表示和操作语义的数学结构来做形式化;

可靠性: 所有观察有区别的程序必须有不同的语义;

完备性: 有不同指称的任何两个程序必须有观察区别。

我们希望在操作语义和指称语义之间的额外想要的性质有:

“构造性”: 语义模型应当在只包含在可以直觉上构造的元素的意义上是构造性的。公式化这个性质的一种方式所有元素必须是有限元素的的有向集合的极限。

“累进性”: 对于每个系统 S,都有语义的一个 progressions 函数,使得系统 S 的指称(意义)是 ∨i∈ωprogressions(⊥S),这里的 ⊥S 是 S 的初始格局(configuration)。

完全完备性: 语义模型的所有态射应当是程序的指称。

在指称语义中长期存在的重点是完全抽象存在于归纳类型中,特别是自然数的类型,作为接受用做递归的一种方法的类型。这个问题的传统解释是作为系统 PCF语言的语义。在 1990年代成功的用博弈语义为 PCF 提供了完全抽象模型,导致了对指称语义的工作在方式上的根本改变。

语义与实现

依据 Dana Scott [1980]:

依据 Clinger [1981]:

指称语义的早期历史

如前面提到过的,这个领域最初由 Christopher Strachey 和 Dana Scott 在 1960年代,接着由 Joe Stoy 在 1970年代于“Oxford University Computing Laboratory”的“Programming Research Group”开发。

Montague文法是英语的理想片段的某种形式的指称语义。

同其他计算机科学领域的联系

某些指称语义的著作把类型解释为域理论意义上的域,因而可以被看作模型论的分支,导致了同类型论和范畴论的联系。在计算机科学内与抽象释义、程序验证和函数式编程有联系,参见函数式编程语言中的单子(monad)。特别是,指称语义使用了续体(continuation)来依据函数式编程语义表达顺序编程中的控制流。


域理论

演员模型的指称语义

指称语义的历史


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

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

更多文章

更多精彩文章
打赏
私信

推荐阅读

· 博弈语义
直觉主义逻辑,指称语义,线性逻辑Lorenzen和KunoLorenz的主要动机是为直觉主义逻辑找到一种博弈论(他们的术语是"对话式"DialogischeLogik)语义。Blass首先指出在博弈语义和线性逻辑之间的联系。这个路线进一步由SamsonAbramsky、RadhakrishnanJagadeesan、PasqualeMalacaria和独立的由MartinHyland和LukeOng发展,对组合性加以特别强调,就是递归的在语法上定义策略。使用博弈语义,上面提及的作者们解决了长期存在的为可计算函数的编程语言定义完全抽象模型的问题。于是,在博弈语义的基础上,产生了为各种编程语言提供了完全抽象的语义模型,以及由此产生了用软件模型检测进行软件验证的新的语义导向的方法。量词博弈语义的基础性考虑被JaakkoHintikka和GabrielSandu更加强调,特别是...
· 语义网
应用通过下列方法可以提升万维网以及其互连的资源的易用性(usability)和实用性(usefulness):"标记"了语义信息的文档。这可以是机器可以理解的关于文档内容(例如文档的作者,标题,简介等)的描述,或者是描述该网站所拥有的服务和资源.(注意:任何东西都是能被URI-统一资源定位符-所描述的,因此语义网能理解人物、地方、想法、类别等等)通用元数据词汇表(本体论)及词汇间的影射使得文档作者知道如何来标记文档方可让机器识别他想提供的元数据.利用元数据为语义网用户执行任务的自动软件代理(agent).为自动软件代理提供特定信息的网络服务(例如,可信度服务可以让软件代理查询某个在线商店是否曾经有过不良纪录或者发送过垃圾邮件).语义网应用示例目前的各种万维网技术都有可能被应用于语义网(在语义环球网的意义上),例如:DOM文档对象模型,一组访问XML和HTML文档组成部分...
· 语义安全
历史语义安全的概念首先由戈德瓦塞尔(Goldwasser)和米卡里(Micali)在1982年提出,两人后来证明了语义安全和另一性质密文不可辨别性是等价的。后者定义比语义安全更通用,因为它更能实施于检验实际加密方式的安全性。对称密钥加密在语义安全的对称密钥加密加密算法系统中,对抗者不可能从密文获得明文。如交给两段相同长度的明文与其中之一的密文,将不可分辨该密文所对应的明文。公钥加密参考文献
· 语义信息
科学哲学领域从科学哲学领域的角度说,不只是日常语言提供的信息,GPS和温度表提供的信息,甚至电池正负号提供的信息也都是语义信息。因为电池上一个加号(+)等价于一个命题:“这是正极”。语义信息的概念主要是用以区别Shannon信息的。与Shannon信息论的比较语义信息与信号(message)的含义及知识有关,存在对错问题;Shannon信息与信号含义或知识无关,不存在对错问题(Floridi,2011)。语义信息可以包含在单个信号(message)或命题中,而Shannon信息只能存在于一连串信号中,只能通过统计得到平均信息(Shannon,1948)。广义信息在大多数地方指除了随机性还涉及语言模糊性的信息,主要也是指语义信息。语义信息研究语义信息研究,即如何度量语义信息的研究,最早可以追溯到Weaver,Bar-Hillel,Carnap,Popper等人。Weaver提出信息论研究应当...
· 语义学
语言学的语义学若从严格意义上的语言学研究来分类,在现代语言学的语义学中,可以分为结构主义的语义学研究和生成语言学的语义学研究。结构主义语义学是从20世纪上半叶以美国为主的结构主义语言学发展而来的,研究的内容主要在于词汇的意义和结构,比如说义素分析,语义场,词义之间的结构关系等等。这样的语义学研究也可以称为词汇语义学,词和词之间的各种关系是词汇语义学研究的一个方面,例如同义词、反义词,同音词等,找出词语之间的细微差别。生成语义学是20世纪六七十年代流行于生成语言学内部的一个语义学分支,是介于早期的结构主义语言学和后来的形式语义学之间的一个理论阵营。生成语义学借鉴了结构语义学对义素的分析方法,比照生成音系学的音位区别特征理论,主张语言的最深层的结构是义素,通过句法变化和词汇化的各种手段而得到表层的句子形式。形式语义学是从20世纪70年代开始发展出来的一个理论阵营。最初的研究开始于蒙太古以数理逻...

关于我们

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

APP下载

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