第9章 程序变换技术.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,第,9,章 程序变换技术,1.引言,递归程序的优缺点,优点：比较符合人的思维习惯，结构紧凑简洁，容易理解。,缺点：由于使用堆栈技术，要耗费较多的计算时间和存储空间。,程序的等价变换：递归,迭代,2.,程序变换的思想,程序变换的基本思想是把程序设计工作分成两个阶段进行：,程序生成阶段,和,程序改进阶段,。,程序生成阶段,设计面向问题的、易于理解的、正确的函数型递归程序，不考虑效率。,程序改进阶段,通过一系列变换规则，将程序转换成具体的面向过程且效率较高的程序。,2.,程序变换的思想,程序变换的方法：,即根据某些程序变换规则把一种程序变换成另一新的程序，这两个程序必须是等价的。,如用,Dijkstra,的谓词转换器定义，则有程序,P1,和,P2,等价，当且仅当对任意谓词,R,满足：,wp(P1,R)=wp(P2,R),程序变换可以看作是一种严格的数学演算，因此为了保证程序的正确性，只要对变换前的程序文本加以验证就行了，而变换后程序的正确性将由变换规则加以保证。,3.程序变换的基本规则,程序变换规则是在程序集合上的一个映射，每个变换规则一般仅对一类程序有定义，故可用程序模式的有序对来描述变换规则。,当可用性条件,B,成立时，输入模式,S1,可用输出模式,S2,来代替。,4 基本的变换规则,.,定义规则,将谓词中的存在量词的每次呈现都用全称量词代替。,.,取样规则,容许代入参数的特定值，得到输入模式的一个样品。,.,展开,和,封叠规则,展开是将函数调用用相应的函数体来替代。,封叠是展开的逆规则。,.,用定律规则,容许在程序变换中直接利用各种代数定律。,.,抽象规则,容许把函数体中的公共子表达式抽象为新的标识符。,5.程序生成阶段,思路,：分析问题,制定形式规定生成函数型递归程序。,例,1,，计算自然数,n,的阶乘函数,FAC(n,),。,根据定义：,FAC(n,),that,z:z,=n!,讨论：当,n=1,时，,FAC(1)=1!=1,当,n1,时，,FAC(n,)=n*(n-1)!=n*FAC(n-1),递归程序为：,FAC(n,),if n=1 then 1,else n*FAC(n-1),5.程序生成阶段,例,2,，计算两个自然数,x,和,y,的最大公约数的函数,GCD(x,y,),。,根据定义：,GCD(x,y,)that,z:maxu,u|xu|y,讨论：当,x=y,时，,GCD(x,y,)=,maxu,u|xu|y,=,maxu,u|y,=y,当,xy,时，,GCD(x,y,)=,maxu,u|x,u|y,=,maxu,u|x-y,u|y,=,GCD(x-y,y,),当,xy then,GCD(x-y,y,),else,GCD(x,y-x,),5.程序生成阶段,例,3,，计算正实数,x,的自然数幂的函数,POW(x,n,),。,根据定义：,POW(x,n,),that,z:z,=x*n,讨论：当,n=1,时，,POW(x,n,)=POW(x,1)=x,当,n1,时，,POW(x,n,)=x*n=x*(n-1)*x,=POW(x,n-1)*x,递归程序为：,POW(x,n,)if n=1 then x,else POW(x,n-1)*x,5.程序生成阶段,例,4,求实数型数组,(x,1,x,2,x,n,),的最大元素的函数,MAX(x,1,x,2,x,n,),。,把实型数组,(x,1,x,2,x,n,),看成是一个由实数组成的表,L,。,讨论：当,L,表只有一个元素时，,CDR(L)=NIL,，,MAX(L)=CAR(L),。,当,L,表包含两个以上元素时，假定已求出,MAX(CDR(L),，则：当,CAR(L)MAX(CDR(L),MAX(L)=CAR(L),；,当,CAR(L),MAX(CDR(L),MAX(L)=MAX(CDR(L),。,递归程序为：,MAX(L),if CDR(L)=NIL then CAR(L),else if CAR(L)MAX(CDR(L)then CAR(L),else MAX(CDR(L),5.程序生成阶段,步骤总结：,对参数分情形进行适当讨论,其中必须包括某些特殊情形作为递归终止条件；,各情形的析取必须为,true，,以保证程序分支的完备性。,把特殊情形的参数代入程序的形式规定，推导出非递归分支（终止分支）的计算表达式。,找出一般情形下函数值和,“,较小,”,参数的函数之间的等价关系，推导出递归分支。,把所有分支用条件表达式综合成一个完整的程序，这个程序是一个可终结的函数型递归程序。,6.程序改进阶段,尾递归型程序,所含有递归调用的分支只递归调用一次；,所含有递归调用的分支都以递归调用结束。,尾递归型程序可以直接转换为迭代程序。,例子：,G(x,y)ifx=1then1*yelseG(x-1,x*y),F(x,)if x=1 then 1 else x*F(x-1),是,不是,6.程序改进阶段,尾递归是指具有如下形式的递归函数,f(x),ifb(x)thenh(x),elsef(k(x);,其中：,x,k:TYPE1,k(x)x(,符号,表示偏序,),h,f:TYPE2,b:,boolean,且,b,h,k,中都不含,f,。,尾递归例子,T2f(T1x),T1x1;,if(b(x),returnh(x);,else,x1=k(x);,returnf(x1);,T2f(T1x),T1x1;,loop:,if(b(x),returnh(x);,else,x1=k(x);,x=x1;/,注意，这两行语句,goto,loop;,/,用,goto,把尾递归改,/,为了迭代,Cooper,变换,Cooper,变换作用：将非尾递归程序转换为尾递归程序,Cooper,变换形式,输入模式,:,f(x),ifb(x)thenh(x)elseF(f(k(x),g(x),输出模式,:,f(x),G(x,e),G(x,y),ifb(x)thenF(h(x),y),elseG(k(x),F(g(x),y),其中：,x,k:TYPE1,k(x)x,y,G,h,g,f,F:TYPE2,b:,boolean,e:F,的右单位元，即,F(x,e)=x,可用性条件：,(1),F,满足结合律，即,F(F(x,y),z)=F(x,F(y,z),；,(2)F,有右单位元,e,；,(3)b,h,g,k,中都不含,f,。,例如考虑计算阶乘的函数,f(x),if(x=1)then1elsef(x-1)*x;,对照,cooper,变换，易见该函数是满足,cooper,变换的输入模式和适用性条件的。,其中,b(x),(x=1);,h(x),1,F(x,y),x*y,F,的右单位元,e=1,k(x),x-1,（取良序关系为通常的,，,x-1x,）,g(x),x,于是我们可以根据,cooper,变换将,f(x),改写为：,f(x),G(x,1);,G(x,y),if(x=1)then1*yelseG(x-1,x*y);,FAC(4)=G(4,1)=G(3,4)=G(2,12)=G(1,24)=24,用,C+,写的代码为,：,int,G(int,x,int,y),int,x1,y1;,if(x=1),return1*y;,else,x1=x-1;,y1=x*y;,returnG(x1,y1);,int,f(int,x),returnG(x,1);,其中尾递归函数,G,又可以进一步改写为迭代形式：,int,G(int,x,int,y),int,x1,y1;,loop:,if(x=1),return1*y;,else,x1=x-1;,y1=x*y;,x=x1;y=y1;,goto,loop;,