抽象释义

✍ dations ◷ 2025-06-06 21:38:29 #抽象释义
在计算机科学中,抽象释义是基于在有序集合特别是格上的单调函数,计算机程序的语义的可靠逼近理论。它可以被看作对计算机程序的部分执行,获取关于它的语义信息(比如,控制结构、信息流)而不进行所有计算。它的主要具体应用是形式静态分析,关于计算机程序的可能执行的信息的自动提取;比如这种分析有两个主要用途:抽象释义是 Patrick Cousot 和 Radhia Cousot 所形式化的。我们现在展示一下抽象释义在现实世界中非计算例子的意味着什么。让我们考虑在会议室中人们。如果我希望证明某个人不在场,一个具体的方式是查看所有参与者的名字和唯一于他们的某种标识符比如美国的社会保障编号的列表。因为没有两个人有相同的编号,有可能证明或反证一个参与者的出席,简单的通过在列表中查找他的名字或他的编号。但是我们可以限制自己只登记他们的名字。如果一个人的名字在列表中没有找到,我们可以安全的结论说这个人不在场;但是如果有这个名字,我们不能明确的结论而不做进一步的质询,原因是有可能重名。我们要注意这个不精确的信息对多数用途是足够的,因为实践中重名是很少见的。但是在严格的情况下,我们不能确切的说某个人在屋子里;我们只能说他可能在这里。如果我们查找的这个人是罪犯,我们将发出“警报”;但是当然有可能发出“假警报”。类似的现象将出现在程序的分析中。如果我们只感兴趣于某些特定信息,比如“有年龄 n 岁的人在屋子中吗?”,则必须保存所有人的名字和生日的列表是不必需的。我们可以安全和不损失精确的限制自身保存参与者的年龄的列表。如果这处理起来太多了,我们可以只保存极小年龄 m 和极大年龄 M。如果问题是关于严格小于 m 或严格大于 M 的年龄,则我们可以安全的回应没有这个参与者在场。否则,我们只能说不知道。在计算的情况下,具体的精确的信息在有限时间和内存内一般是不能计算的(参见Rice定理和停机问题)。 抽象被用来把问题一直简化到有职能自动解答的问题。减少精度的一个关键要点是使问题易于处理而对回答你感兴趣的问题(比如“程序会崩溃吗?”)仍保持足够的精度。给定一个编程或规定语言,抽象释义一般由抽象关系连接的一些语义所构成。语义是程序的可能行为的数学特征化。描述了非常接近程序的实际执行的最精确的语义被称为具体语义。例如,指令式编程语言的具体语义可能对每个程序关联上它可以生成的执行跟踪的集合 – 执行跟踪是程序执行的一序列的可能的连续状态;状态典型的构成自程序计数器和内存位置(全局、栈和堆)的值。更抽象的语义是导出的,比如你可以只考虑在执行中可触及的状态的集合(相当于考虑在有限跟踪中的最后状态)。静态分析的目标是在某些点上导出可计算的语义释义。例如,可以选择表示操纵整数变量的程序的状态,通过忘记变量的实际值并只保持它们的符号(+, - 或 0)。对于某些基本运算比如乘法,这种抽象不丢失任何精度: 要得到乘积的符号,知道操作数的符号就足够了。对于某些其他运算,抽象可能丢失精度: 比如不可能知道操作数分别是正和负的求和的符号。有时精度的丢失对使语义成为可决定性的是必需的(参见Rice定理, 停机问题)。一般的说,在分析的精度和它的可决定性(可计算性)或可跟踪性(复杂性)之间要做出妥协。在实践中定义的抽象适合于想要分析的程序性质和目标程序的集合二者。设 L 是叫做具体集合的有序集合,并设 L′是叫做抽象集合的另一个有序集合。通过定义映射一个的元素到另一个的元素的全函数,把这两个集合相互联系起来。函数 α 叫做抽象函数,如果它映射在具体集合 L 中的元素 x 到抽象集合 L′中的元素 α(x)。就是说,在 L′中的元素 α(x) 是 L 中的元素 x 的抽象。函数 γ 叫做具体化函数,如果它映射在抽象集合 L′中的元素 x′到具体集合 L 中的元素 γ(x′)。就是说,在 L 中的元素 γ(x′) 是 L′中的元素的 x′的具体化。设 L1, L2, L′1 和 L′2 是有序集合。具体语义 f 是从 L1 到 L2 的单调函数。从 L′1 到 L′2 的函数 f′被称为 f 的有效抽象,如果对于所有 L′1 中的 x′有 (f ∘γ)(x′) ≤ (γ∘f′)(x′)。程序语义在循环或递归过程在场的情况下一般使用不动点来描述。我们设 L 是完全格并设 f 是从 L 到 L 的单调函数。则任何 x′使得 f′(x′) ≤ x′是 f 的最小不动点的抽象,它依据 Knaster-Tarski定理而存在。困难现在是获得这样的 x′。如果 L' 是有限高度的,或最多检验“升链条件”(所有上升序列最终都固定),则这样的 x′可获得为通过如下归纳法定义的上升序列 x′n 的固定极限: x′0=⊥ (L′的最小元素) 并且 x′n+1=f′(x′n)。在其他情况,仍有可能通过拓宽算子∇ 来的得到这种 x′: 对于所有的 x 和 y,x ∇ y 应当大于等于 x 和 y 二者,并且对于所有序列 y′n,定义自 x′0=⊥ 并且 x′n+1=x′n ∇ y′n 的序列最终是固定的。我们接着选取 y′n=f(x′n)。在某些情况,有可能使用伽罗瓦连接 (α, γ) 来定义抽象,这里的 α 是从 L 到 L′而 γ 是从 L′到 L 的单调函数。这假定了最好抽象的存在性,这不是必然的情况。例如,如果我们通过套入凸多面体抽象实数对 (x,y) 的集合,则对于 x2+y2 ≤ 1 定义的圆盘没有最优抽象。在一个给定程序点上可以向每个变量 x 指派一个区间 。指派值 v(x) 到变量 x 的状态是这些区间的具体化,如果对于所有 x 有 v(x) 在 中。从给变量 x 和 y 的区间 和,可以轻易的获得 x+y 的区间() 和 x-y 的区间();注意这些是精确抽象,因为可能结果比如 x+y 的集合,精确的是区间 ()。可以为乘法、除法等推导出更复杂的公式,生成所谓的区间算术。现在我们考虑下列非常简单的程序:带有合理的算术类型,z 的结果应当是零。但是如果我们做区间算术开始于 x 在 中。我们得到 z 在 。尽管进行的每个运算都单独的精确抽象了,它们的复合不是。问题是显然的: 我们不跟踪在 x 和 y 之间的相等关系;实际上,这个区间的域不考虑在变量间的任何关系,因此是非关联域。非关联域趋向更快和实现简单但不精确。关联数值抽象域的某些例子有:和它们的组合。在选择抽象域的时候,典型必须在保持精细关联和高计算代价之间作出权衡。

相关

  • 古巴斯捷氏综合征古德巴斯捷氏综合征(Goodpasture syndrome,GPS),又称古德巴斯捷氏病(Goodpasture's disease)、肺出血肾炎综合征、抗肾小球基底膜抗体病(anti-glomerular basement antibody diseas
  • 多孔动物门多孔动物门(学名:Porifera)为原始的多细胞生物,也称海绵动物门(Spongiatia或Spongia),一般称为海绵。海绵没有神经元/神经系统、消化和循环系统,相反,它们大多依靠海水流过自己的身体
  • 曲霉属See List of Aspergillus species麹菌属(Aspergillus)是一个由几百种多细胞霉菌菌种所组成的菌属,在许多气候条件下皆可发现它们的踪影。麹菌属于1729年被皮耶尔·安东尼奥·米
  • 恩前列素恩前列素是一种合成的类地诺前列酮前列腺素,它可以用来作胃部HCl分泌的强效抑制剂。 因而常被用来作抗酸或溃疡药。它的药理作用基本与米索前列醇相同。医学导航:遗传代谢缺陷
  • 恒温动物恒温动物(Homeotherms),俗称温体动物,与内温动物(Endotherms)不 同。在动物学指的是那些能够调节自身体温的动物,其活动性并不像变温动物那样依赖外界温度。在鸟和哺乳动物会通过新
  • 胆结石胆结石(英语:gallstones)是在胆囊内由胆汁化合物组成的结石。胆石症(choleliths)可以指胆囊中的结石,也可以指此一疾病。大多数胆结石患者(约80%)不曾有过症状。胆结石的患者中,有1-4
  • 医师誓言希波克拉底誓词(希腊语:Όρκος του Ιπποκράτη,英语:Hippocratic Oath),俗称医师誓词,是西方医生传统上行医前的誓言,希波克拉底乃古希腊医者,被誉为西方“医学之父”
  • 西法兰克王国西法兰克王国(法语:Francie occidentale)为西欧的一个君主制国家,存在时间为843年至987年。843年,法兰克国王虔诚者路易的三个儿子,洛泰尔、日耳曼人路易及秃头查理签署《凡尔登条
  • 黑素瘤黑色素瘤,又称恶性黑色素瘤,是一种从黑色素细胞发展而来的癌症,是皮肤癌中罕见的癌症。好发于皮肤但也可能出现在口腔、肠道或眼睛中。女性患者的黑色素瘤最常出现在腿,而男性患
  • 平滑在图论中,边收缩是指将一个图的其中一个边移除,并将被移除边的两个顶点合并,同时保持与被移除边之顶点相连的其他顶点之连接关系的一种变换,为图子式理论中的基本算子之一,然而此