程序设计学PPT课件 第9章 程序变换技术.ppt

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:max{u,u|x∧u|y} 讨论：当x=y时，GCD(x,y)=max{u,u|x∧u|y} = max{u,u|y}=y 当xy时，GCD(x,y)=max{u,u|x∧u|y} = max{u,u|x-y∧u|y}=GCD(x-y,y) 当xy时，GCD(x,y)=max{u,u|x∧u|y} = max{u,u|x∧u|y-x}=GCD(x,y-x) 递归程序为： GCD(x,y) ≡if x=y then y else if 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 求实数型数组(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) else MAX(CDR(L)) 5. 程序生成阶段 步骤总结： 对参数分情形进行适当讨论 其中必须包括某些特殊情形作为递归终止条件； 各情形的析取必须为true，以保证程序分支的完备性。 把特殊情形的参数代入程序的形式规定，推导出非递归分支（终止分支）的计算表达式。 找出一般情形下函数值和“较小”参数的函数之间的等价关系，推导出递归分支。 把所有分支用条件表达式综合成一个完整的程序，这个程序是一个可终结的函数型递归程序。 6. 程序改进阶段 尾递归