程序變換技術精品課件

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

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

3、立時，輸入模式S1可用輸出模式S2來代替。 第5頁，共18頁，2022年，5月20日，11點55分，星期五4 基本的變換規(guī)則. 定義規(guī)則將謂詞中的存在量詞的每次呈現都用全稱量詞代替。. 取樣規(guī)則容許代入參數的特定值，得到輸入模式的一個樣品。. 展開和封疊規(guī)則展開是將函數調用用相應的函數體來替代。封疊是展開的逆規(guī)則。. 用定律規(guī)則容許在程序變換中直接利用各種代數定律。. 抽象規(guī)則容許把函數體中的公共子表達式抽象為新的標識符。第6頁，共18頁，2022年，5月20日，11點55分，星期五5. 程序生成階段思路：分析問題制定形式規(guī)定生成函數型遞歸程序。例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，以保證程序分支的完備性。把特殊情形的參數代入程序的形式規(guī)定，推導出非遞歸分支（終止分支）的計算表達式。找出一般情形下函數值和“較小”參數的函數之間的等價關系，推導出遞歸分支。把所有分支用條件表達式綜合成一個完整的程序，這個程序是一個可終結的函數型遞歸程序。第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