首页 >
抽象释义
✍ dations ◷ 2025-06-27 16:15:07 #抽象释义
在计算机科学中,抽象释义是基于在有序集合特别是格上的单调函数,计算机程序的语义的可靠逼近理论。它可以被看作对计算机程序的部分执行,获取关于它的语义信息(比如,控制结构、信息流)而不进行所有计算。它的主要具体应用是形式静态分析,关于计算机程序的可能执行的信息的自动提取;比如这种分析有两个主要用途:抽象释义是 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 之间的相等关系;实际上,这个区间的域不考虑在变量间的任何关系,因此是非关联域。非关联域趋向更快和实现简单但不精确。关联数值抽象域的某些例子有:和它们的组合。在选择抽象域的时候,典型必须在保持精细关联和高计算代价之间作出权衡。
相关
- 心脏病心脏病(cardiovascular disease (CVD))是心脏疾病的总称,包括风湿性心脏病、先天性心脏病、高血压性心脏病、冠心病、心肌炎等各种心脏病:医学导航: 产科生理/发育/薄膜(英语:Temp
- 诺贝尔生理学与医学奖诺贝尔生理学或医学奖(瑞典语:Nobelpriset i fysiologi eller medicin),通常合称诺贝尔生理医学奖,由诺贝尔基金会管理,该奖项每年颁发一次,用于表彰在生理学或医学领域作出重要发
- 内皮内皮细胞或血管内皮是一薄层的专门上皮细胞,由一层扁平细胞所组成。它形成血管的内壁,是血管管腔内血液及其他血管壁(单层鳞状上皮)的界面。内皮细胞是沿着整个循环系统,由心脏直
- 苯丙胺安非他命(英文名称:Amphetamine也称为苯丙胺,为中枢神经刺激剂,用来治疗注意力不足过动症、嗜睡症、和肥胖症。“Amphetamine”一名撷取自alpha‑methylphenethylamine。 安非他
- 性心理发展性心理发展(Psychosexual Development)是西格蒙德·弗洛伊德在19世纪末、20世纪初提出的概念,是心理学理论的核心概念;包括5个阶段:口腔期、肛门期、性器期、潜伏期、生殖期。主
- 美国社会安全保险美国社会安全保险(Social Security),为美国联邦政府对老年人、遗属和部分残疾人提供的全国范围的财政补助金。据估计,2014年社会安全保险的开销约占美国联邦政府当年预算的24%。
- 伊本·赫勒敦伊本·赫勒敦(阿拉伯语:ابن خلدون,1332年5月27日-1406年3月19日),全名为阿布·扎伊德·阿卜杜勒拉赫曼·本·穆罕默德·本·赫勒敦·哈德拉米(阿拉伯语:أبو زيد ع
- 铁中毒铁中毒是由于摄入铁过量引起的中毒表现。它并不少见,大多是由于误食过量硫酸亚铁所致。注射铁制剂过量可以发生严重中毒。若长期内服大量铁剂,可能引起肺、肝、肾、心、胰等处
- 光气碳酰氯,俗称光成气(英语:phosgene;化学式:COCl2),简称光气,从化学结构上看是碳酸的二酰氯衍生物,是非常活泼的亲电试剂,容易水解,是剧烈窒息性毒气,高浓度吸入可致肺水肿,毒性比氯气约大1
- 分析哲学分析哲学(英语:analytic philosophy或analytical philosophy)可包含两个意思:一个是指20世纪初期出现的,具有特定目的和方法的哲学研究。另外它还指当今研究哲学的一种“风格”或