程序变换技术

程序变换技术第1页，课件共18页，创作于2023年2月1.引言递归程序的优缺点优点：比较符合人的思维习惯，结构紧凑简洁，容易理解。缺点：由于使用堆栈技术，要耗费较多的计算时间和存储空间。程序的等价变换：递归迭代第2页，课件共18页，创作于2023年2月2.程序变换的思想程序变换的基本思想是把程序设计工作分成两个阶段进行：程序生成阶段和程序改进阶段。程序生成阶段 设计面向问题的、易于理解的、正确的函数型递归程序，不考虑效率。程序改进阶段 通过一系列变换规则，将程序转换成具体的面向过程且效率较高的程序。第3页，课件共18页，创作于2023年2月2.程序变换的思想程序变换的方法：即根据某些程序变换规则把一种程序变换成另一新的程序，这两个程序必须是等价的。如用Dijkstra的谓词转换器定义，则有程序P1和P2等价，当且仅当对任意谓词R满足：wp(P1,R)=wp(P2,R)程序变换可以看作是一种严格的数学演算，因此为了保证程序的正确性，只要对变换前的程序文本加以验证就行了，而变换后程序的正确性将由变换规则加以保证。第4页，课件共18页，创作于2023年2月3.程序变换的基本规则程序变换规则是在程序集合上的一个映射，每个变换规则一般仅对一类程序有定义，故可用程序模式的有序对来描述变换规则。当可用性条件B成立时，输入模式S1可用输出模式S2来代替。

第5页，课件共18页，创作于2023年2月4基本的变换规则①.

定义规则将谓词中的存在量词的每次呈现都用全称量词代替。②.取样规则容许代入参数的特定值，得到输入模式的一个样品。③.展开和封叠规则展开是将函数调用用相应的函数体来替代。封叠是展开的逆规则。④.用定律规则容许在程序变换中直接利用各种代数定律。⑤.抽象规则容许把函数体中的公共子表达式抽象为新的标识符。第6页，课件共18页，创作于2023年2月5.程序生成阶段思路：分析问题制定形式规定生成函数型递归程序。例1，计算自然数n的阶乘函数FAC(n)。 根据定义：FAC(n)≡thatz:z=n!

讨论：当n=1时，FAC(1)=1!=1

当n>1时，FAC(n)=n*(n-1)!=n*FAC(n-1)

递归程序为：

FAC(n)≡ifn=1then1 elsen*FAC(n-1)第7页，课件共18页，创作于2023年2月5.程序生成阶段例2，计算两个自然数x和y的最大公约数的函数GCD(x,y)。 根据定义：GCD(x,y)≡thatz:max{u,u|x∧u|y}

讨论：当x=y时，GCD(x,y)=max{u,u|x∧u|y} =max{u,u|y}=y

当x>y时，GCD(x,y)=max{u,u|x∧u|y}

=max{u,u|x-y∧u|y}=GCD(x-y,y)

当x<y时，GCD(x,y)=max{u,u|x∧u|y}

=max{u,u|x∧u|y-x}=GCD(x,y-x) 递归程序为：

GCD(x,y)≡ifx=ytheny elseifx>ythenGCD(x-y,y) elseGCD(x,y-x)第8页，课件共18页，创作于2023年2月5.程序生成阶段例3，计算正实数x的自然数幂的函数POW(x,n)。 根据定义：POW(x,n)≡thatz:z=x**n

讨论：当n=1时，POW(x,n)=POW(x,1)=x

当n>1时，POW(x,n)=x**n=x**(n-1)*x =POW(x,n-1)*x

递归程序为：POW(x,n)≡ifn=1thenx elsePOW(x,n-1)*x第9页，课件共18页，创作于2023年2月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)≡ifCDR(L)=NILthenCAR(L)

elseifCAR(L)>MAX(CDR(L))thenCAR(L) elseMAX(CDR(L))第10页，课件共18页，创作于2023年2月5.程序生成阶段步骤总结：对参数分情形进行适当讨论其中必须包括某些特殊情形作为递归终止条件；各情形的析取必须为true，以保证程序分支的完备性。把特殊情形的参数代入程序的形式规定，推导出非递归分支（终止分支）的计算表达式。找出一般情形下函数值和“较小”参数的函数之间的等价关系，推导出递归分支。把所有分支用条件表达式综合成一个完整的程序，这个程序是一个可终结的函数型递归程序。第11页，课件共18页，创作于2023年2月6.程序改进阶段尾递归型程序所含有递归调用的分支只递归调用一次；所含有递归调用的分支都以递归调用结束。尾递归型程序可以直接转换为迭代程序。例子：G(x,

y)

if

x

=

1

then

1

*

y

else

G(x-1,

x

*

y)F(x)ifx=1then1elsex*F(x-1) 是不是第12页，课件共18页，创作于2023年2月6.程序改进阶段尾递归是指具有如下形式的递归函数

f(x)

≡

if

b(x)

then

h(x)

else

f(k(x));

其中：

x,

k:

TYPE1,

k(x)

x

(

符号

表示偏序)

h,

f:

TYPE2

b:

boolean且b,

h,

k中都不含f。第13页，课件共18页，创作于2023年2月尾递归例子T2

f(T1

x){

T1

x1;

if

(b(x))

{

return

h(x);

} else

{

x1

=

k(x);

return

f(x1); }}

T2

f(T1

x){

T1

x1;

loop:

if

(b(x))

{

return

h(x);

}else

{

x1

=

k(x);

x

=

x1;

//

注意，这两行语句

goto

loop;

//

用goto把尾递归改

//为了迭代

}}第14页，课件共18页，创作于2023年2月Cooper变换Cooper变换作用：将非尾递归程序转换为尾递归程序第15页，课件共18页，创作于2023年2月Cooper变换形式输入模式:

f(x)

≡

if

b(x)

then

h(x)

else

F(f(k(x)),

g(x))输出模式:

f(x)

≡

G(x,

e)

G(x,

y)

≡

if

b(x)

then

F(h(x),

y)

else

G(

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页，创作于2023年2月例如考虑计算阶乘的函数f(x)

≡

if

(x

=1)

then

1

else

f(x-1)*x;

对照cooper变换，易见该函数是满足cooper变换的输入模式和适用性条件的。其中

b(x)

≡

(x

=

1);h(x)

≡

1F(x,

y)

≡

x

*

y,

F的右单位元e

=

1k(x)

≡

x

-

1（取良序关系为通常的<，x-1<x）

g(x)

≡

x

于是我们可以根据cooper变换将f(x)改写为：

f(x)

≡

G(x,

1);G(x,

y)

≡

if

(x

=

1)

then

1

*

y

else

G(x-1,

x

*

y);

FAC(4)=G(4,1)=G(3,4)=G(2,12)=G(1,24)=24第17页，课件共18页，创作于2023年2月用C++写的代码为：

int

G(int

x,

int

y){

int

x1,

y1;

if

(x

==

1)

{

return

1

*

y;

} else

{

x1

=

x

-

1;

y1

=

x

*y;

return

G(x1,

y1);

}}

int

f(int

x){

r