程序變換技術(shù)精品課件

1、程序變換技術(shù)第1頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五1. 引言遞歸程序的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：比較符合人的思維習(xí)慣，結(jié)構(gòu)緊湊簡(jiǎn)潔，容易理解。缺點(diǎn)：由于使用堆棧技術(shù)，要耗費(fèi)較多的計(jì)算時(shí)間和存儲(chǔ)空間。程序的等價(jià)變換：遞歸 迭代第2頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五2. 程序變換的思想程序變換的基本思想是把程序設(shè)計(jì)工作分成兩個(gè)階段進(jìn)行：程序生成階段和程序改進(jìn)階段。程序生成階段設(shè)計(jì)面向問(wèn)題的、易于理解的、正確的函數(shù)型遞歸程序，不考慮效率。程序改進(jìn)階段通過(guò)一系列變換規(guī)則，將程序轉(zhuǎn)換成具體的面向過(guò)程且效率較高的程序。第3頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分

2、，星期五2. 程序變換的思想程序變換的方法：即根據(jù)某些程序變換規(guī)則把一種程序變換成另一新的程序，這兩個(gè)程序必須是等價(jià)的。如用Dijkstra的謂詞轉(zhuǎn)換器定義，則有程序P1和P2等價(jià)，當(dāng)且僅當(dāng)對(duì)任意謂詞R滿足：wp(P1,R)=wp(P2,R)程序變換可以看作是一種嚴(yán)格的數(shù)學(xué)演算，因此為了保證程序的正確性，只要對(duì)變換前的程序文本加以驗(yàn)證就行了，而變換后程序的正確性將由變換規(guī)則加以保證。第4頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五3. 程序變換的基本規(guī)則程序變換規(guī)則是在程序集合上的一個(gè)映射，每個(gè)變換規(guī)則一般僅對(duì)一類程序有定義，故可用程序模式的有序?qū)?lái)描述變換規(guī)則。當(dāng)可用性條件B成

3、立時(shí)，輸入模式S1可用輸出模式S2來(lái)代替。 第5頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五4 基本的變換規(guī)則. 定義規(guī)則將謂詞中的存在量詞的每次呈現(xiàn)都用全稱量詞代替。. 取樣規(guī)則容許代入?yún)?shù)的特定值，得到輸入模式的一個(gè)樣品。. 展開(kāi)和封疊規(guī)則展開(kāi)是將函數(shù)調(diào)用用相應(yīng)的函數(shù)體來(lái)替代。封疊是展開(kāi)的逆規(guī)則。. 用定律規(guī)則容許在程序變換中直接利用各種代數(shù)定律。. 抽象規(guī)則容許把函數(shù)體中的公共子表達(dá)式抽象為新的標(biāo)識(shí)符。第6頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五5. 程序生成階段思路：分析問(wèn)題制定形式規(guī)定生成函數(shù)型遞歸程序。例1，計(jì)算自然數(shù)n的階乘函數(shù)FAC(n)。根據(jù)定

4、義：FAC(n) that z:z=n!討論：當(dāng)n=1時(shí)，F(xiàn)AC(1)=1!=1 當(dāng)n1時(shí)，F(xiàn)AC(n)=n*(n-1)!=n*FAC(n-1) 遞歸程序?yàn)椋?FAC(n) if n=1 then 1 else n*FAC(n-1)第7頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五5. 程序生成階段例2，計(jì)算兩個(gè)自然數(shù)x和y的最大公約數(shù)的函數(shù)GCD(x,y)。根據(jù)定義：GCD(x,y) that z:maxu,u|xu|y討論：當(dāng)x=y時(shí)，GCD(x,y)=maxu,u|xu|y = maxu,u|y=y 當(dāng)xy時(shí)，GCD(x,y)=maxu,u|xu|y = maxu,u|x-y

5、u|y=GCD(x-y,y) 當(dāng)xy then GCD(x-y,y) else GCD(x,y-x)第8頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五5. 程序生成階段例3，計(jì)算正實(shí)數(shù)x的自然數(shù)冪的函數(shù)POW(x,n)。根據(jù)定義：POW(x,n) that z:z=x*n討論：當(dāng)n=1時(shí)，POW(x,n)=POW(x,1)=x 當(dāng)n1時(shí)，POW(x,n)=x*n=x*(n-1)*x=POW(x,n-1)*x遞歸程序?yàn)椋篜OW(x,n) if n=1 then x else POW(x,n-1)*x第9頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五5. 程序生成階段例4

6、求實(shí)數(shù)型數(shù)組(x1 , x2 , xn )的最大元素的函數(shù)MAX(x1 , x2 , xn )。把實(shí)型數(shù)組(x1 , x2 , xn )看成是一個(gè)由實(shí)數(shù)組成的表L。討論：當(dāng)L表只有一個(gè)元素時(shí)，CDR(L)=NIL，MAX(L)=CAR(L)。 當(dāng)L表包含兩個(gè)以上元素時(shí)，假定已求出MAX(CDR(L)，則：當(dāng)CAR(L)MAX(CDR(L), MAX(L)=CAR(L)；當(dāng)CAR(L)MAX(CDR(L), MAX(L)= MAX(CDR(L) 。遞歸程序?yàn)椋?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頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五5. 程序生成階段步驟總結(jié)：對(duì)參數(shù)分情形進(jìn)行適當(dāng)討論其中必須包括某些特殊情形作為遞歸終止條件；各情形的析取必須為true，以保證程序分支的完備性。把特殊情形的參數(shù)代入程序的形式規(guī)定，推導(dǎo)出非遞歸分支（終止分支）的計(jì)算表達(dá)式。找出一般情形下函數(shù)值和“較小”參數(shù)的函數(shù)之間的等價(jià)關(guān)系，推導(dǎo)出遞歸分支。把所有分支用條件表達(dá)式綜合成一個(gè)完整的程序，這個(gè)程序是一個(gè)可終結(jié)的函數(shù)型遞歸程序。第11頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五6. 程序改進(jìn)階段尾遞歸型程序所含有遞歸調(diào)用的分支只遞歸調(diào)用

8、一次；所含有遞歸調(diào)用的分支都以遞歸調(diào)用結(jié)束。尾遞歸型程序可以直接轉(zhuǎn)換為迭代程序。例子：G(x,y) ifx=1then1*yelseG(x-1,x*y) F(x) if x=1 then 1 else x*F(x-1) 是不是第12頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五6. 程序改進(jìn)階段尾遞歸是指具有如下形式的遞歸函數(shù)f(x)ifb(x)thenh(x)elsef(k(x);其中：x,k:TYPE1,k(x) x(符號(hào) 表示偏序)h,f:TYPE2 b:boolean 且b,h,k中都不含f 。第13頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)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; /注意，這兩行語(yǔ)句gotoloop;/用goto把尾遞歸改 /為了迭代 第14頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五Cooper 變換Cooper變換作用：將非尾遞歸程序轉(zhuǎn)換為尾遞歸程序第15頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)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滿足結(jié)合律，即F(F(x,y),z)=F(x,F(y,z)； (2)F有右單位元e； (3)b,h,g,k中都不含f。第16頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五例如考慮計(jì)算階乘的函數(shù)f(x)if(x=1)then1elsef(x-1)*x;對(duì)照cooper變換，易見(jiàn)該函數(shù)是滿足cooper變換的輸入模式和適用性條件的。其中 b(x)(x=1); h(x)1 F(x,y)x*y,F的右單位元e=1 k(x)x-1 （取良序關(guān)系為通常的，x-1x） g(x)x 于是我們可以根據(jù)cooper變換將f(x)改寫(xiě)為： 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頁(yè)，共18頁(yè)，2022年，5月20日，11點(diǎn)55分，星期五用C+寫(xiě)的代碼為：intG(intx,inty)intx1,y1;if(x=1)return1*y;elsex1=x-1;y1=x*y;retu