抽象释义

✍ dations ◷ 2025-09-19 11:12:38 #抽象释义
在计算机科学中,抽象释义是基于在有序集合特别是格上的单调函数,计算机程序的语义的可靠逼近理论。它可以被看作对计算机程序的部分执行,获取关于它的语义信息(比如,控制结构、信息流)而不进行所有计算。它的主要具体应用是形式静态分析,关于计算机程序的可能执行的信息的自动提取;比如这种分析有两个主要用途:抽象释义是 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 之间的相等关系;实际上,这个区间的域不考虑在变量间的任何关系,因此是非关联域。非关联域趋向更快和实现简单但不精确。关联数值抽象域的某些例子有:和它们的组合。在选择抽象域的时候,典型必须在保持精细关联和高计算代价之间作出权衡。

相关

  • 支气管支气管是连接呼吸道内将空气输往肺部的通道。支气管末梢又分支为许多小管,最终成为小支气管。支气管并不是进行气体交换的场所。支气管管壁有平滑肌,过敏时平滑肌过度收缩,导致
  • 藻类藻类,又称作悬浮植物,包括数种不同类以光合作用产生能量的生物,其中有属于真核细胞的藻类,也有属于原核细胞的藻类。它们一般被认为是简单的植物,并且一些藻类与比较高等的植物有
  • 植物病理学植物病理学,是对于引起植物疾病的病原体(感染性微生物)和环境条件(生理因素)的科学研究 。引起感染性疾病的生物体包括真菌,卵菌,细菌,病毒,类病毒,病毒样生物,植原体,原生动物,线虫和寄
  • 热浪热浪是指天气在某一段时间内持续地保持异常高的气温(相对于该地区多年平均气温而言),也有可能伴随有很高的空气湿度。这个术语通常与地区相联系,所以一个处于相对较热气候的地区
  • 存在主义存在主义(英语:existentialism),是一个哲学的非理性主义思潮,它认为人存在的意义是无法经由理性思考而得到答案的,以强调个人、独立自主和主观经验。尼采和克尔凯郭尔可被看作其先
  • 49,XXXXYXXXXY综合征,是一种极为罕见的非整倍染色体异常,男性中发病率约为1/100,000至1/85,000。此综合征病因为母体卵细胞在第一次减数分裂和第二次减数分裂时未分离。首次诊断于1960
  • 乌头碱乌头碱(Aconitine)是常用中药乌头中所含有的一种化学物质,具强烈毒性,口服0.2mg左右即能使人中毒,3-5mg即可致死。民间常用草乌、川乌等植物来泡制药酒,但这种药酒可能是极端危险
  • 维生工资维生工资是指一个劳工为了支付生活开销(包含食、衣、住、行)的所需的最低收入,往往比最低工资高。在英国及瑞士,维生工资的标准是每周工作40个小时所能获得的工资,不含额外的收入
  • 年鉴年鉴是系统汇辑一年内的重要资料,逐年编纂连续出版的资料性工具书。有人认为年鉴属于期刊性质的年刊。资料相对完整,内容具有权威性和时间性,具有资政、鉴戒和史料作用。中文的
  • 国际辅助语国际辅助语(International Auxiliary Language(IAL、auxlang)、Interlanguage)是为帮助使用不同的民族语言的人们更好的进行语言交往而设计的一种辅助性语言。其目的并非是为了