程序变换技术精品课件

1、程序变换技术第1页，共18页，2022年，5月20日，11点55分，星期五1. 引言递归程序的优缺点优点：比较符合人的思维习惯，结构紧凑简洁，容易理解。缺点：由于使用堆栈技术，要耗费较多的计算时间和存储空间。程序的等价变换：递归 迭代第2页，共18页，2022年，5月20日，11点55分，星期五2. 程序变换的思想程序变换的基本思想是把程序设计工作分成两个阶段进行：程序生成阶段和程序改进阶段。程序生成阶段设计面向问题的、易于理解的、正确的函数型递归程序，不考虑效率。程序改进阶段通过一系列变换规则，将程序转换成具体的面向过程且效率较高的程序。第3页，共18页，2022年，5月20日，11点55分

2、，星期五2. 程序变换的思想程序变换的方法：即根据某些程序变换规则把一种程序变换成另一新的程序，这两个程序必须是等价的。如用Dijkstra的谓词转换器定义，则有程序P1和P2等价，当且仅当对任意谓词R满足：wp(P1,R)=wp(P2,R)程序变换可以看作是一种严格的数学演算，因此为了保证程序的正确性，只要对变换前的程序文本加以验证就行了，而变换后程序的正确性将由变换规则加以保证。第4页，共18页，2022年，5月20日，11点55分，星期五3. 程序变换的基本规则程序变换规则是在程序集合上的一个映射，每个变换规则一般仅对一类程序有定义，故可用程序模式的有序对来描述变换规则。当可用性条件B成

3、立时，输入模式S1可用输出模式S2来代替。 第5页，共18页，2022年，5月20日，11点55分，星期五4 基本的变换规则. 定义规则将谓词中的存在量词的每次呈现都用全称量词代替。. 取样规则容许代入参数的特定值，得到输入模式的一个样品。. 展开和封叠规则展开是将函数调用用相应的函数体来替代。封叠是展开的逆规则。. 用定律规则容许在程序变换中直接利用各种代数定律。. 抽象规则容许把函数体中的公共子表达式抽象为新的标识符。第6页，共18页，2022年，5月20日，11点55分，星期五5. 程序生成阶段思路：分析问题制定形式规定生成函数型递归程序。例1，计算自然数n的阶乘函数FAC(n)。根据定

4、义：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)第7页，共18页，2022年，5月20日，11点55分，星期五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|xu|y = maxu,u|x-y

5、u|y=GCD(x-y,y) 当xy then GCD(x-y,y) else GCD(x,y-x)第8页，共18页，2022年，5月20日，11点55分，星期五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第9页，共18页，2022年，5月20日，11点55分，星期五5. 程序生成阶段例4

6、求实数型数组(x1 , x2 , xn )的最大元素的函数MAX(x1 , x2 , xn )。把实型数组(x1 , x2 , xn )看成是一个由实数组成的表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

7、)else MAX(CDR(L) 第10页，共18页，2022年，5月20日，11点55分，星期五5. 程序生成阶段步骤总结：对参数分情形进行适当讨论其中必须包括某些特殊情形作为递归终止条件；各情形的析取必须为true，以保证程序分支的完备性。把特殊情形的参数代入程序的形式规定，推导出非递归分支（终止分支）的计算表达式。找出一般情形下函数值和“较小”参数的函数之间的等价关系，推导出递归分支。把所有分支用条件表达式综合成一个完整的程序，这个程序是一个可终结的函数型递归程序。第11页，共18页，2022年，5月20日，11点55分，星期五6. 程序改进阶段尾递归型程序所含有递归调用的分支只递归调用

8、一次；所含有递归调用的分支都以递归调用结束。尾递归型程序可以直接转换为迭代程序。例子：G(x,y) ifx=1then1*yelseG(x-1,x*y) F(x) if x=1 then 1 else x*F(x-1) 是不是第12页，共18页，2022年，5月20日，11点55分，星期五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 。第13页，共18页，2022年，5月20日，11点55分，星期五尾递归例子T2f

9、(T1x)T1x1;if(b(x)returnh(x);elsex1=k(x);returnf(x1); T2f(T1x)T1x1;loop:if(b(x)returnh(x); elsex1=k(x);x=x1; /注意，这两行语句gotoloop;/用goto把尾递归改 /为了迭代 第14页，共18页，2022年，5月20日，11点55分，星期五Cooper 变换Cooper变换作用：将非尾递归程序转换为尾递归程序第15页，共18页，2022年，5月20日，11点55分，星期五Cooper变换形式输入模式:f(x)ifb(x)thenh(x) elseF(f(k(x),g(x)输出模式:f

10、(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。第16页，共18页，2022年，5月20日，11点55分，星期五例如考虑计算阶乘的函数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第17页，共18页，2022年，5月20日，11点55分，星期五用C+写的代码为：intG(intx,inty)intx1,y1;if(x=1)return1*y;elsex1=x-1;y1=x*y;retu