抽象释义

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

相关

  • 红斑性肢痛症红斑性肢痛病 一种罕见的血管病。表现为手足血管阵发性地扩张收缩,伴有灼痛、皮肤温度升高并发红。可能是遗传性疾病,也可能是皮肤对热和张力过敏所致。
  • 口服糖耐量试验糖耐力测试(Oral glucose tolerance test, OGTT)是一种测试血糖在人体内代谢水平的医学实验。具体步骤是,要求被测试对象在空腹情况下喝下75克无水葡萄糖或82.5克含一分子水的
  • 抗高血压药抗高血压药(英文:Anti-hypertensives)肼屈嗪 米诺地尔 硝普钠含羧基类: 依那普利# • 雷米普利 • 喹那普利 • 培哚普利 • 赖诺普利 • 贝那普利含次膦酸基类: 福辛普利 其
  • 脉翅目广翅亚目 Megaloptera 蛇蛉亚目 Raphidioptera 蛟蛉亚目 Planipennia脉翅目(学名:Neuroptera)包括草蛉、蚁蛉、长角蛉等,属于完全变态的昆虫。这个目的成虫有两对膜状的的翅膀,前
  • 迪乔治综合征迪乔治综合征(DiGeorge syndrome;22q11.2缺失综合征/22q11.2 deletion syndrome)是一种遗传疾病,会导致鼻及鼻梁基部宽大、人中短、上唇薄、耳廓异常、颚裂、心脏容易出现多重异
  • 呼吸呼吸(英语:breathing),生物的一种生理现象,为一种生物细胞的生化作用(称作“呼吸作用”)所呈现出来的外在生理现象,动物及植物皆有。一般人的认知,则是指高等生物,尤其是人类利用肺部
  • 有氧运动有氧运动(英语:Aerobic exercise),又称有氧训练、需氧运动、带氧运动,是一种以提高人体耐力质素,增强心肺功能为目的的体育运动,很多时候也被用作减轻体重。人体运动需要ATP来提供
  • 环甲关节环甲关节(cricothyroid articulation、或 joint(关节)、环甲状关节)是连接环状软骨及甲状软骨的关节。它通过改变声带的张紧度来调节人声的音调起到关键性的作用。这种张力主
  • 早期现代英语近代英语(英语:Early Modern English,可缩写为 EModE),又译近世英语,指从英国都铎时期到王政复辟时期的英语,也就是从十五世纪末的中古英语到十七世纪中晚期的现代英语之间的英语语
  • 中心语短语的中心词(英语:head 或 nucleus),也称中心语,指的是决定短语的语法范畴的词,是一个短语的中心部分。 短语的其他成分与中心词在语法或语义上有着某些联系。如名词短语(英语:noun