没有合适的资源?快使用搜索试试~ 我知道了~
《理论计算机科学电子札记》55卷第3期(2001年)网址:http://www.elsevier.nl/locate/entcs/volume55.html18页Erlang程序的模型检测{抽象上下文无关结构Frank Huch1LehrstuhlfurInformatikII亚琛D-52056 Aachen,Germany摘要我们提出了一种使用抽象解释和模型检查来验证Erlang程序的方法在以前的工作中,我们为Erlang定义了一个抽象解释框架在这个框架中,保证了抽象操作语义保持标准操作语义的所有路径我们考虑必须在系统的所有路径上保持的属性,如LTL中的属性。如果这些属性可以为抽象操作语义证明,那么它们也适用于Erlang程序。如果抽象操作语义是一个nite变迁系统,证明可以通过模型检查自动化但由于非{尾递归函数调用,所以不能保证无中断性。 甚至对于NITE域抽象解释,我们得到NITE状态系统,并且模型检查是不可判定的。在本文中,我们定义了一个抽象的控制{ow。它通过跳转到同一函数的最后一次调用来替换非尾部位置的递归调用相应的返回被替换为跳转到可能的返回点。我们已经实现了这种方法作为一个原型,并能够证明适当的关系,如互斥或没有死锁和生命锁的一些Erlang程序。关键词:抽象,模型检测,Erlang,分布式系统,上下文无关结构1引言工业和社会需求的增长使软件开发变得更加复杂。因此,无法保证可理解性、维护性和再责任性.当我们离开顺序领域而开发分布式系统时,事情变得更加困难。在这里,许多进程同时运行并通过通信进行交互这可以例如良率问题1 电邮地址:huch@informatik.rwth-aachen.dec2001年由Elsevier Science B出版。诉 在CC BY-NC-ND许可下开放访问。F. 胡赫2比如死锁或者救生锁为了保证软件的正确性,需要进行形式化验证。我们提出了一个扩展的模型检查程序编写的真正的编程语言。然而,模型检查问题一般是不可判定的系统实现使用编程语言和有趣的逻辑描述的因此,我们需要抽象[5,13,16]。在工业上,编程语言Erlang [1]用于实现分布式系统。我们在[10]中为Erlang的核心片段开发了一个抽象解释框架,其属性是由抽象操作语义(AOS)定义的转换系统包括标准操作语义(SOS)的所有路径。因为AOS有时可能比SOS有更多的路径,所以只能证明必须在所有路径上填充的属性,就像线性时间逻辑(LTL)一样。如果一个抽象函数完整地使用了一个用LTL表示的属性,那么程序也会完整地使用它,但反之则不然。如果AOS是一个夜间转换系统,那么模型检验是可判定的[14,18]。定义的抽象只为Erlang程序的一个子类产生一个nite转换系统,称为分层程序[10]。递归只允许在尾部位置。然而,在实践中,许多Erlang程序并不满足这个限制。例如,append或length的标准定义已经不是分层的。因此,使用这种函数的程序不能用所提出的抽象解释技术抽象成有限状态转换系统原因是函数式程序的上下文无关结构在本文中,我们将这种上下文无关结构抽象我们得到了一个nite态过渡系统。通过LTL模型检验,系统的性能可以自动得到验证在第2节中,我们定义了Erlang核心部分的语法。我们在第3节中简述了操作语义。第4节简要介绍了抽象解释的框架,第5节介绍了其限制。在第6节中,我们提出了一个图的语义,我们的抽象的基础上。我们在第7节中激发了抽象的想法,并在第8节中将其第9节介绍了它在模型检查中的使用,最后,我们在第10节总结并讨论未来的工作2Core Erlang设是一组具有元数的预定函数符号。 例如+/22 . 设Var=fX;Y; Z;g 是一组变量,A是一组原子,例如 f1;2;fai l;succ; :g. 设C是Erlang构造函数的集合,具有arity:C=f[:|:]=2;[]=0g [f{: : :}=nj n2IN g [fa=0j a2Atom s g;(1)一个用于构建列表的构造函数,一个用于空列表的构造函数,用于构建任意元数的元组的构造函数,以及作为元数为0的构造函数的原子F. 胡赫3构造项的集合被定义为最小集合TC(S)使得:STC(S) 和c=n2C,t1; :;tn2TC(S)=)c(t1; :;tn)2TC(S)Core Erlang程序的语法定义如下:p::=f(X1,:,Xn)->e. jppe::=(e1,:,en)j Xj pat=ej selfj e1,e2j e1!e2j情况e的m端j接收m端 j生成n(f,e)M::= p1-> e1;:; p n-> e npat::=c(p1,:,pn)jX一个程序的所有定义函数,用它们的arity扩展,建立了集合FS(p)。=n是f=n 2 FS(p),F=n 2和c=n 2 C的缩写。在每个CoreErlang程序中,都定义了一个main函数:main=0 2 FS(p)。我们称核心Erlang项的集合为e ET(;)。集合ET(S)是通过为Core Erlang术语添加语法规则e::= v 2 S来定义的。例2.1设Core Erlang程序p0为:main()->DB= spawn(dataBase,[[]]),spawn(client,[DB]),客户端(DB)。dataBase(L)-> receive{allocate,Key,P} -> case lookup(Key,L)offail-> P!自由,接收{value,V,P} -> dataBase(insert(Key,V,L))end;{succ,V} -> P!allocated,dataBase(L)end;{lookup,Key,P} -> P!lookup(Key,L),dataBase(L)end.insert(K,V,L)-> case L of[]->[{K,V}];[{K',V'}| L ']->情况K'< K,true-> [{K',V'}| insert(K,V,L')]; false ->[{K,V}| L]端端F. 胡赫4该程序创建一个数据库进程,该进程保持存储数据库信息的状态数据库由一个元组列表表示,每个元组由一个键和一个对应的值组成。数据库的接口由消息{allocate,Key,P}和{lookup,Key,P}给出。分配分两步进行首先,接收并检查密钥如果F. 胡赫5C如果没有冲突,则可以接收相应的值并将其存储在数据库中。这种在多个步骤中的消息交换必须保证数据库上的互斥,因为否则可能会有两个客户端进程向数据库发送键和值,并且它们以错误的组合存储。客户端可以相应地定义[10]。我们稍后将证明,数据库与两个访问客户端的组合满足此属性。3核心ErlangErlang是一种严格的函数式编程语言。它扩展了并发执行的进程。使用spawn(f;[ a1;:::; an])可以在程序中的任何位置创建新进程。该过程从f(a1;:; an)的求值开始。如果spawn的第二个参数不是ground,则在创建新进程之前对其进行评估。spawn的函数结果是新创建进程的进程标识符(pid)用P!任意值(包括PID)可以被发送到其他进程。这些进程通过它们的pid(p)来寻址 进程可以通过Erlang函数self/0访问自己的pid。 发送给进程的消息存储在邮箱中,进程可以通过receive语句中的模式匹配方便地访问它们。特别是,可以忽略一些消息并从更后面获取消息。更多详情请参见[1]。在[10]中,我们提出了Core Erlang的形式语义。在下文中,我们将其称为标准操作语义(SOS)。 它是一组进程上的交错语义。从形式上讲,一个进程由一个pid(2Pid:=f@nj n2IN g)、Core Erlang评估项(e2ET(TC(Pid)和表示邮箱的构造器项上的字(q 2 T(P id))。对于最左最内的求值策略的定义,我们使用求值上下文的技术[7]:E::=[ ]j(v1,:,vi,E,ei+2, :,en)j E,ej p=Espawn(f,E)j E!e j v!E j case Eofm end这里v表示一个已求值的表达式,E表示redex所在的子项,e和m表示不能求值的部分。 []被称为孔并标记下一次评估的点。然后,我们将上下文E写成E[e],其中洞被e替换,下一步的评估在这里进行。类似于集合S上的核心Erlang项ET(S),我们将核心Erlang上下文命名为EC(S)。集合S定义值的集合:v2 TC(S)。在[10]中定义的操作语义中,我们有(S = TC(Pid))。对于本文中提出的抽象,S也将包含变量。语义学是一个非并发的转换系统。对过程的评价是交错进行的。只有沟通和过程创造才有副作用。为了对这些动作进行建模,涉及到不止一个过程。为了给语义的印象,我们提出了发送值F. 胡赫61b bbbbBBBBb一pretation函数b定义了prede ned函数符号的语义,到另一个进程v =0 2PID!v2;(;E[v1!v2];q)(0;e;q0)=);(;E[v2];q)(0;e;q0:v2)该值被添加到进程0的邮箱中,发送操作的功能结果是发送的值。4核心Erlang程序在[10]中,我们开发了一个框架,用于对Core Erlang程序进行抽象解释.抽象操作语义(AOS)产生一个转换系统,其中包括所有路径的SOS。对于Core Erlang程序,抽象解释为A=(A;;v;),A是抽象域,这对于我们在模型检查中的应用来说应该是合适的。抽象的inter-建筑师。 它的c o结构域是AB。因此,例如,在Nite域抽象中自由地解释构造函数同时,模式匹配在方程、事例和接收器中抽象行为。在这里,抽象可以产生额外的非确定性,因为分支在抽象中可以变得不可判定。因此产生一组结果,这些结果确定了可能的后继者。此外,一个抽象的解释包含一个偏序v,描述A中哪些元素比其他元素更精确。我们不需要完全偏序,因为我们不计算任何固定点。我们只是用这个抽象的解释来评估操作语义 一个抽象的例子是:INv fvj v 10gv fvj v 5g。它是更精确地知道,一个值是5,比10比任何数字。A的最后一个组成部分是抽象函数::T C(P id)!A将每个实值映射到一个抽象表示。通常这是最精确的表示。最后,抽象解释必须具有将抽象解释与标准解释联系起来的它们保证SOS的所有路径都在AOS中表示,例如在分支中。下面是这些属性的示例(P1)为所有 =n 2[C; v1;:; vn2 TC(P id)和iv(vi)成立b(1; :;evn)v(A(v1; :;vn)).它假定,评估一个predefened函数或构造函数的抽象值,这是一些具体的值表示产生抽象的评估相同的功能的具体值。其他属性假设了匹配和模式匹配,以及由抽象值表示的pid。更多细节和一些示例抽象可以在[10,11]中找到我们不会-又来了。 在下一节中,我们将定义这个语义的修改版本,它对我们的目标更有用F. 胡赫75数据抽象例5.1考虑下面的Core Erlang程序:main()-> f(42)。f(X)-> f(f(X))。最小可能的抽象域是只包含元素的域?,它代表了所有可能的值。有了这个抽象域,程序的抽象语义包含路径:(@1;main();())!(@1;f(42);())!(@1;f(?);())!(@1;f(?));())!“ ……”(@1;fn(?);())!(@1;fn+1(?);())!* *它包含许多不同的状态。这种抽象语义相对于操作语义是正确的,在这个意义上,SOS的所有路径都被表示。但是我们不能使用简单的模型检查算法来证明这个抽象语义的属性,因为它有一个inite状态空间。这个例子在实践中似乎是无关紧要的,但是在nite转换系统中,对于nite域上的抽象语义,也会产生列表的常用函数,如append或length函数。我们在[10]中,ned的层次程序类,其中递归调用只允许在尾部位置。对于这个类,我们得到一个nite抽象模型。然而,这种限制对程序员来说太强了。一个函数的尾部递归版本,如果存在的话,可能是非常复杂和低效的。 这也可以在示例2.1中看到。函数insert/2将一个新元素插入到列表中,相对于键的排序,也是非层次的。因此,这个程序的抽象域对于每个抽象解释都有一个内部状态空间。问题的根源在于函数调用的上下文无关结构。对于特殊类的上下文无关的转移系统,已经证明,模型检查是可判定的[4,3],并且这些理论结果似乎可以在这里使用。但我们并不是只有一个与上下文无关的过渡系统。我们在多个进程中有几个这样的进程,它们可以相互通信。因此,我们可以模拟几个可以交换数据的堆栈。 可以使用只包含ve值的nite域抽象来模拟图灵机。在LTL中,可以指定其终止。因此,这些系统的验证一般是不可判定的。我们需要将上下文无关的结构抽象为一个nite或上下文无关的模型,它只产生于一个上下文无关的过程。第二种可能性对于实践来说似乎是复杂的,并且不清楚应该从哪个过程保留上下文无关结构。因此,我们抽象出nite模型。抽象必须包含上下文无关结构的所有路径,因为我们希望用线性时间逻辑(LTL)的模型检查来证明程序的性质F. 胡赫8一1n1n6图语义在[10]中定义的Core Erlang语义中,我们无法检测Erlang术语的哪些部分属于哪个函数调用。在应用函数定义之后,右侧在调用它的上下文中消失。我们无法探测到它的终点。调用堆栈未显式表示。为了使这些调用和返回更加可见,我们在某种程度上更接近实现。我们将一个Erlang术语拆分为一个Erlang上下文堆栈当一个函数被调用时,它的上下文被存储在堆栈上,对应的右手边是下一个项,它必须被评估。如果实际值是基础值(不能再计算),则从堆栈中弹出下一个上下文,并将值放入孔中。评估将继续此Erlang项。评估项的这些堆栈表示由SR(S):= ET(S)(FS(p)EC(S))定义,其中S是可能的值。堆栈还包含在压入此上下文时调用的函数的名称。这在图表示中是非常不合理的,但我们稍后将使用这些信息进行抽象。这种技术可以应用于Erlang语义。但是在Core Erlang的语义中,所有进程都是交错的,进程的关键调用和返回不能被轻易地识别和修改。这里我们只描述一个进程的行为。这使得分析更容易。我们-一个预编译,它将一个Core Erlang函数转换为一个transi-描述以该函数开始的进程行为的函数系统这个想法是所有的行为都可以自由解释该过渡系统中的弧标记有该过程可以执行的行为/动作状态用Erlang项标记,必须对其进行评估。与SOS的唯一区别是,变量也可能出现在CoreErlang术语中。这些变量稍后将使用值实例化。因此,我们也可以将自由解释中的变量作为值来下一次求值的位置与具体的变量绑定无关。结果就是关系!SR(TC(Var))ActSR(TC(Var))在图1中定义。所有行为的集合应该从图中清楚地前八条规则只是对行为的自由解释。在receive和case的规则中,我们必须考虑分支。图案的正确顺序很重要。因此,我们对相应弧中的模式进行编号并保持其顺序。如果一个动作的结果必须在后续的状态中使用,那么我们引入一个新的变量Y。操作的结果绑定到Y,Redex被Y替换。函数的调用为上下文产生一个新的堆栈帧,函数在其中被调用(10)。在SOS中,我们还必须在此时将变量绑定推送到运行时堆栈,并继续绑定参数调用函数f。这被转换标签c:X=2保留。如果一个函数在空的上下文中被调用,我们使用尾部递归优化(9)。2我们将X写成X的缩写;:;X,a表示[a;:;a],c:X=a表示c:X1=a1; : : : ;Xn =an. 从正文中可以清楚地看出。F. 胡赫9一Y =(a1;:;an)r:Y =a“啊!B1. (E[a;e]; W)! (E[e]; W)2. (E[a!b]; W)!(英[b];西)3.(E[selfY =自身];W)!(E[Y ];W)P = a其中Y2=Vars(E)4. (E[p=a];W)!(E[a];W)(i;?pi)5. (E[receivep 1->e1;:; pn->enen d]; W)!(E[ei]; W)81in(i; pi = a)6. (E[caseaofp 1->e1;:; pn->enen d]; W)!(E[ei]; W)81in7.(E[(a 1;:; a n)];W)!(E[Y];W)其中Y Y =spawn(f; a)2=Vars(E)8. (E[spaw n(f;a)]; W)!(E[Y]; W)其中YIc:X= a9. (f(a); W)! (ef; W) 其中f(X)->ef. 2个pc:X=2=Vars(E)10. (E[f(a)]; W)! (ef;(f;E)W)其中f(X)->ef. 2p和E6=[]11. (a;(f;E)W)!(E[Y]; W),其中a2TC(Vars)和Y2=Vars(E)图一: Core Erlang的堆栈图表示如果我们不再有求值上下文,换句话说,Core Erlang术语是变量上的构造器术语,那么我们必须返回到最后一个上下文(11)。我们不能简单地将值a复制到洞中,因为a可能包含变量,这些变量也会出现在E中。在SOS中,这些变量通常被绑定到不同的值。因此,我们引入一个新的变量Y,它不会出现在E中,并将此变量绑定到求值结果,即a。在该图形表示之上,可以容易地定义(抽象)语义。对于只在尾部位置使用递归的Core Erlang程序,图形表示是一个nite transition系统。我们将使用这种图表示来进行抽象,但我们也可以使用它来更有效地实现抽象和模型检查。在第一个实现中,我们使用Core Erlang评估术语来识别状态。在构造抽象模型时,需要对循环进行检测。因此,必须存储状态。对于转换系统中的每个新状态,计算其后继状态并与存储的状态进行比较。只有对于新的状态,必须计算进一步的后继者。但是状态的存储需要大量的空间,状态的比较需要大量的时间。因此,状态的紧凑表示是期望的。图表示是一个转换系统,其中的转换表示一个进程的行为。国家的标签只用于它的建设,但他们是超级乌伊之后。我们可以用数字代替它们。然后我们用这些数字作为进程所处状态的名称来构造交错转移系统。这是一个更紧凑的状态表示,并允许更快的验证,甚至更大的系统。此外,我们不必在生成模型的过程中降低评估上下文。可以更有效地评估一个国家的继任者。F. 胡赫10Ic:X=X(f(X)j“)(f :j“的情况X)(2;N)(1;0)(bj“)“(bj“)(self!a,f(X-1),self!bj“)(P!b)、(P!a)、(f(Z),self!bj“)(Y,self!bj“)c:X=Z(1;0)r:Y=b(caseXof: j(f;[],self!b))(bj(f;[],self!(b))(2;N)(self!a,f(X-1),self!bj(f;[],self!b))(P!b)、(P!a)、(f(Z),self!bj(f;[],self!b)) (Y,self!b;(fj(f;[],self!(b))c:X=Z(1;0)r:Y=b(caseXof:j(f;[],self!b)2)(bj(f;[],self!(b)(2)(2;N)P!B(self!a,f(X-1),self!bj(f;[],self!b)2) (P!bj(f;[],self!(b)(2)..图2:示例6.1的图形表示但是对于非层次化的Core Erlang程序,这个图形表示是在nite中的:例6.1考虑以下函数定义:f(X)-> case Xof0 -> b;N->self!a,f(X-1),self!b端。执行此函数的进程将X次原子a发送给自己,然后再发送X次b。 图2中描绘了所得到的图形表示。为了更好地区分核心Erlang术语和堆栈中的逗号,我们使用j将评估术语F. 胡赫11与上下文堆栈分开7抽象上下文无关结构正如第4节所讨论的,我们需要抽象Core Erlang程序的上下文无关结构。我们使用与抽象F. 胡赫12!(f(X)j“)Ic:X=X(case Xof:j“)(2;N)(1;0)(bj“)“(bj“)(self!a,f(X-1),self!bj“)(P!b)、(P!a)、(f(Z),self!bj“)(Y,self!bj“)c:X=Z(1;0)r:Y=b(caseXof: j(f;[],self!b))(bj(f;[],self!(b))(2;N)(self!a,f(X-1),self!bj(f;[],self!b))(P!b)、(P!a)、(f(Z),self!bj(f;[],self!b))(Y,self!bj(f;[],self!(b))图3: 示例6.1的抽象图形表示解释。我们构造了程序的抽象图表示,这是nite状态。该构造保证其语义相对于SOS是安全的。我们的方法是一种程序级的调用字符串方法[17]。抽象的主要思想是用跳转替换调用和返回。对于例6.1,一个很好的抽象是,发送rst n次a,然后发送m次ab。像“b之后不发送a”这样的属性可以自动证明。抽象的思想是通过跳转到一个已经调用f的precederator节点来替换f的调用(参见图2)因此,我们将第二个非尾部调用替换为以下弧:(f(Z),self!bj(f;[];self!b))c:X=Z(caseX: j(f;[];self!(b))(f(Z),self!bj(f;[];self!图2中的b))可以不考虑。但是我们如何执行相应的返回步骤呢? 我们知道我们跳转到的状态的堆栈,而不是调用f。 因此,如果Core Erlang项被求值为与我们跳转到的堆栈相同的值,而不是调用,则此调用的求值将被终止。这些都是形式为r(0):Y=bc(0):X=ZF. 胡赫13(aj(f;[];self!b))与2TC(Var)。在我们的例子中,这只是状态(bj(f;[];self!(b))。这次返回跳跃的目的地F. 胡赫14!BB由发起呼叫的州定义调用的结果是b:(bj(f;[];self!b))r:Y=b(Y,self!bj(f;[];self!(b))我们不像通常在返回步骤中那样弹出顶层上下文。上下文堆栈没有被修改。结果是一个nite图表示,其中发送n次a,然后发送m次ab。例6.1的抽象图表示如图3所示。添加的返回跳跃用虚线绘制当我们推广这种技术时,出现了一些问题。一般来说,我们并不是只有一个递归调用自己的函数。我们有多种功能。因此,我们用被调用函数的名称扩展了调用堆栈。我们可以区分不同的函数调用。因此,我们只跳回到与我们调用的函数的右侧相对应的状态。这个扩展的另一个特点是,我们可以检测到,如果一个函数已经被调用。如果它没有被调用,那么它就不会出现在堆栈中。 一个子求值,它终止并且不递归地调用自身之外的东西,将不会被抽象。抽象图表示与非抽象图表示类似。没有调用转换为跳转,也没有添加其他路径。只有当我们在非尾部位置检测到递归时,我们才切断转换系统并跳回去。例7.1例6.1的修改版本暴露了另一个问题.我们发送变量X的值而不是原子b:f(X)-> caseX of0 -> b;N -> self!a,f(X-1),self!X端。首先,进程发送n次a给自己,然后发送数字1;:; n,其中n2 IN是值,f被调用。在上面的抽象中,我们将通信替换为发送n次a和m次b。但我们能做什么呢?在抽象域中,这些值由抽象值表示,这些抽象值不能是一个内部集合(特别是在一个内部域抽象中)。 返回而不是调用,我们无法知道X绑定到哪个值。因此,我们将X绑定到值?,它表示抽象域A中的每个值。 我们主张,这样的价值存在于我们的抽象领域。否则我们可以一直加?与?vv 8v 2 A.此外,我们用这个替换来注释return arc的标签:r:Y=b;[X =?](b j(f;[];self!X))! (Y,self!Xj(f;[];self!(X))在这个抽象返回跳转中,我们不删除调用堆栈的顶部元素。如果递归调用是间接的,也就是说,它调用了中间的一些其他函数,那么我们甚至可能需要添加更多的条目。当我们从函数调用返回时,我们必须将调用堆栈重构为旧的F. 胡赫15堆栈,因为在AOS中,这些存储的上下文仍然必须被执行。 但是在这些上下文中使用变量绑定时,我们会遇到同样的问题,就像使用CoreErlang术语中的变量一样,求值返回。解决方案是将这些上下文的变量绑定添加到?。我们还必须注意标签中调用堆栈的这些变化,因为在AOS中,我们以与图表示相同的方式堆叠替换。因此,我们在抽象调用中注释堆栈元素的数量,这些元素被移除而不是推送一个新块。类似地,我们注意到堆栈元素的数量,这些元素必须在抽象返回跳转中添加,并将替换添加到?这些框架。对于相应的调用和返回,这些数字是一致的。在我们的示例中,它为零,因为在此期间c(0):X=Z(f(Z),self!Xj(f;[];self!X))! (caseXof:j(f;[];self!(X))r(0):Y=b;[X=?];()下一页(b j(f;[];self!X))! (Y,self!Xj(f;[];self!(X))到目前为止,我们把所有变量都绑定到?抽象的返回跳跃。 这是安全的,但不是必要的。 只将绑定的变量绑定到?.稍后将被模式匹配绑定的变量不需要被替换。由于Erlang没有作用域,我们不知道出现在子项中的变量是自由的还是绑定的。我们需要一个分析,它标记已经绑定到值的变量。这种分析可以与抽象图表示的构造相结合。构建我们可以检测到的图形表示,当变量被实例化时。我们用标记(0)标记它。当我们模拟抽象调用的返回时,我们可以将所有标记的变量绑定到?。其他的可以在返回跳转中保持不变f(X)-> caseX of0 -> b;N -> self!a,f(X-1),B=b,self!B端。在这个例子中,变量B在递归调用之前没有被实例化。我们可以保持不变:r(0):Y=b,[],()(bj(f;[],B=b,self!B))0! (Y,B=b,self!Bj(f;[];B=b;self!(B))8形式化描述在最后一节中,我们用一些例子来激励我们的抽象。现在我们给出它的F. 胡赫16正式定义。F. 胡赫17!一8D首先,我们定义一个函数标记,它标记一组变量。(V; X)=x0的 ,如果X 2 V: X,否则它被规范地扩展到Core Erlang术语和上下文。在图表示中,我们标记变量,这些变量被绑定在标签中。例如40: (E[p=a];W)p =a(tag(Vars(p); E[a]);W)这种标记只是一种附加信息,标记的变量通常被在转换标签中,我们只使用变量的名称,而忽略标签。递归是通过跳回到同一函数的最后一次调用来抽象的。如果已经调用了相同的函数,则在调用堆栈中检测到它。此跳转的目标状态的调用堆栈小于调用将产生的堆栈。为了将图形表示中的调用堆栈与它们的抽象表示相关联,我们定义了一个抽象函数。此函数生成调用堆栈,调用堆栈通过逐步扩展调用堆栈并通过减少来替换发生的递归而增长这种递减表示跳回到先前的调用。(“)=“> (f; E)(W);如果j(W)jf = 0((f; E)W)=<(f;E0)V ;如果(W)=U(f;E0)V:>其中jU jf= jV jf=0从定义上看,并不能直接清楚地表明是全部的。 但是通过下面的引理,我们看到((f; E)W)的两种情况中总是有一种匹配。因此,为所有调用堆栈定义。引理8.1j(W)j f对于所有调用栈W和所有函数f2 FS(p),这个抽象函数现在可以用来分析一个给定的调用堆栈,当调用一个函数时。利用这个抽象函数可以直接定义抽象图表示。=)SR(TC(Var))dActSR(TC(Var))动作Act是来自Act的动作加上抽象调用和返回的动作。 =)由规则(1)-(9)和(11)定义!. 代替调用堆栈(10),我们使用它们的抽象表示:c(n):X =(E[f(a)];(W))==)(tag(fXg;ef);((f;E)W))其中f(X)-> e f。 2 p和E 6=[]和n = j(W)j j((f; E 0)F. 胡赫18W)jF. 胡赫19(X0j(g;[],self!X0))(f(X0)j“)Ic:X=X(caseX0of:j“)(2;N)(g(X0- 1),self!X0j“)Z=X 1(g(Z0),self!X0j“)c:X=Z(1;0)(bj“)(1;0)(f(X0- 1),self!X0j(g;[],self!X0))Z=X 1(f(Z0),self!X0j(g;[],self!X0))c:X=Z(caseX0of:j(f;[],self!X0)(g;[],self!X0))(2;N)(g(X0- 1),self!X0j(f;[],self!X0)(g;[],self!X0))Z=X 1(g(Z0),self!X0j(f;[],self!X0)(g;[],self!X0))c(1):X=Z(bj(f;[],self!X0)(g;[],self!X0))(X0j“)r:Y = bP!X(Y0,self!X0j(g;[],self!X0))(P!X0j“)P=自我(P0!X0j(g;[],self!X0))(Y0,self!X0j“)P!Xr:Y=Xr(1):Y=XX=?([X=?])(Y,self!X0j(f;[],self!X0)(g;[],self!X0))P=自身F. 胡赫20(P!X0j(f;[],self!X0)(g;[],self!X0))P!X(X0j(f;[],self!X0)(g;[],self!X0))r:Y=X图4:例8.2的
下载后可阅读完整内容,剩余1页未读,立即下载
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 利用迪杰斯特拉算法的全国交通咨询系统设计与实现
- 全国交通咨询系统C++实现源码解析
- DFT与FFT应用:信号频谱分析实验
- MATLAB图论算法实现:最小费用最大流
- MATLAB常用命令完全指南
- 共创智慧灯杆数据运营公司——抢占5G市场
- 中山农情统计分析系统项目实施与管理策略
- XX省中小学智慧校园建设实施方案
- 中山农情统计分析系统项目实施方案
- MATLAB函数详解:从Text到Size的实用指南
- 考虑速度与加速度限制的工业机器人轨迹规划与实时补偿算法
- Matlab进行统计回归分析:从单因素到双因素方差分析
- 智慧灯杆数据运营公司策划书:抢占5G市场,打造智慧城市新载体
- Photoshop基础与色彩知识:信息时代的PS认证考试全攻略
- Photoshop技能测试:核心概念与操作
- Photoshop试题与答案详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)