[科普中國]-結(jié)構(gòu)化程序理論

結(jié)構(gòu)化程序理論也稱為伯姆-賈可皮尼理論或B?hm-Jacopini理論1，是一項(xiàng)編程語言研究的結(jié)果，說明只要一種編程語言可以依三個(gè)方式組合其子程序及調(diào)整控制流程，每個(gè)可計(jì)算函數(shù)都可以用此種編程語言來表示。

調(diào)整控制流程三個(gè)調(diào)整控制流程的方式為

運(yùn)行一個(gè)子程序，然后運(yùn)行下一個(gè)（順序）

依照布爾變量的結(jié)果，決定運(yùn)行二段子程序中的一段（選擇）

重復(fù)運(yùn)行某子程序，直到特定布爾變量為真為止（循環(huán)）

匹配上述條件的結(jié)構(gòu)圖需要額外的比特變量（在原始證明中放在額外的整數(shù)變量中），以紀(jì)錄原來程序運(yùn)行到的位置，此種建構(gòu)法是以伯姆的編程語言P′′為基礎(chǔ)。

起源及變體一般認(rèn)為此理論最早是在1966年科拉多·伯姆及朱塞佩·賈可皮尼（Giuseppe Jacopini）的論文中提出2。大衛(wèi)·哈雷爾在1980年曾提到這篇論文廣受認(rèn)可，尤其在結(jié)構(gòu)化程序理論的支持者中。哈雷爾也提到“由于其論文比較技術(shù)的風(fēng)格，因此較常被引用，較少人真正詳讀過內(nèi)容。”，在看了1980年以前的大量論文后，哈雷爾認(rèn)為結(jié)構(gòu)化程序理論被錯(cuò)誤詮釋為一個(gè)結(jié)果較簡(jiǎn)單的大眾定理（folk theorem），而此結(jié)果可以追溯到馮·諾依曼及斯蒂芬·科爾·克萊尼現(xiàn)代計(jì)算理論的論文。3

哈雷爾也提到較通用的“結(jié)構(gòu)化程序理論”名稱是在1970年代初由哈倫·米爾斯提出。

單一while循環(huán)的大眾定理版本此版本的定理將原來定理中的程控流程改為一個(gè)while循環(huán)，模擬在原來非結(jié)構(gòu)化的程序中，程序計(jì)數(shù)器走過所有可能標(biāo)記（流程圖方塊）的情形。哈雷爾將此版大眾定理的源頭追溯到兩篇論文，一篇是1946年描述馮·諾伊曼結(jié)構(gòu)，用單一while循環(huán)說明程序計(jì)數(shù)器的運(yùn)作原理，哈雷爾也注意到大眾定理中用到的單一循環(huán)基本上可以提供馮·諾伊曼式電腦運(yùn)行流程的操作語義。。另一篇更早期的論文則是斯蒂芬·科爾·克萊尼1936年的正規(guī)形式定理（Kleene's T predicate）論文。

高德納批評(píng)這種轉(zhuǎn)換后的結(jié)果類似以下的偽代碼，重點(diǎn)是在此轉(zhuǎn)換中完全破壞了原程序的結(jié)構(gòu)。Bruce Ian Mills也有類似的看法：“塊狀結(jié)構(gòu)的精神是其風(fēng)格，不是使用的語言。利用模擬馮·諾伊曼結(jié)構(gòu)的方式，可以將任何一個(gè)面條式代碼轉(zhuǎn)換為塊狀結(jié)構(gòu)的語言，但它面條式代碼的本質(zhì)沒有改變?！?/p>

p := 1;while p > 0 do begin if p = 1 then begin 進(jìn)行流程圖的步驟1; p := 流程圖的步驟1之后的步驟編號(hào)（若沒有后續(xù)步驟，數(shù)值為0）; end; if p = 2 then begin 進(jìn)行流程圖的步驟2; p := 流程圖的步驟2之后的步驟編號(hào)（若沒有后續(xù)步驟，數(shù)值為0）; end; ... if p = n then begin 進(jìn)行流程圖的步驟n; p := 進(jìn)行流程圖的步驟n之后的步驟編號(hào)（若沒有后續(xù)步驟，數(shù)值為0）; end;end.伯姆及賈可皮尼的證明伯姆及賈可皮尼的證明是以流桯圖的結(jié)構(gòu)歸納法為基礎(chǔ)，由于用到圖模式匹配，其證明在實(shí)務(wù)上不能當(dāng)作是程序轉(zhuǎn)換算法，因此開創(chuàng)了此一領(lǐng)域的研究。

相關(guān)的討論及研究因?yàn)椴芳百Z可皮尼建構(gòu)的方式過于復(fù)雜，因此此證明沒有回答結(jié)構(gòu)化編程是否適用于軟件開發(fā)的問題，而是引發(fā)了后續(xù)相關(guān)的討論及爭(zhēng)議。在兩年之后的1968年，艾茲赫爾·戴克斯特拉就提出著名的“GOTO有害論”。

有些學(xué)者試圖使伯姆及賈可皮尼的研究結(jié)果更加純粹，因?yàn)槠湔撐闹袥]有用到從循環(huán)中間跳出循環(huán)的break及return指令，因此學(xué)者認(rèn)為這是不好的實(shí)現(xiàn)方式，學(xué)者們鼓勵(lì)每一個(gè)循環(huán)都只能有唯一的結(jié)束點(diǎn)，這種設(shè)計(jì)觀點(diǎn)集成到1968至1969年開發(fā)的Pascal中。從1969年到1990年代中期，學(xué)校常用Pascal來講授編程語言入門課程。

愛德華·尤登注意到1970年代時(shí)在有關(guān)是否用自動(dòng)化方式改寫非結(jié)構(gòu)化程序一事，有二元對(duì)立的觀點(diǎn)，反對(duì)者認(rèn)為需要以結(jié)構(gòu)化程序的方式去思考，而非一味改寫，而贊成者的論點(diǎn)是這類的修改實(shí)際上可以改善大部分已有的程序。最早提出自動(dòng)化改寫程序概念的有1971年Edward Ashcroft及Zohar Manna的論文。

直接應(yīng)用伯姆及賈可皮尼定理可能要引入額外的局部變量，也可能產(chǎn)生代碼重復(fù)的問題，后者也稱為loop and a half problem。Pascal受到這些問題的影響，依照埃里克·S·羅伯茨的實(shí)驗(yàn)研究，學(xué)習(xí)程序設(shè)計(jì)的學(xué)生難以用Pascal設(shè)計(jì)正確代碼來解決簡(jiǎn)單的問題，其中甚至包括從數(shù)組中找尋一個(gè)元素的問題。一篇1980年由Henry Shapiro進(jìn)行，而后被被羅伯茨引用的研究指出，若只用Pascal提出的流程控制指令，只有20%的人的解答是正確的，但若允許在循環(huán)中直接加入return的話，所有人都寫出了正確的答案。

S. Rao Kosaraju在1973年證明只要允許可以從任意深度循環(huán)中多層次跳出，就可以將程序轉(zhuǎn)換成結(jié)構(gòu)化編程，而不用引入額外的變量。而且Kosaraju證明了存在一個(gè)嚴(yán)格的程序?qū)哟谓Y(jié)構(gòu)（現(xiàn)在稱為Kosaraju層次結(jié)構(gòu)），針對(duì)任一整數(shù)n，存在一個(gè)程序，其中包括深度n的多層次跳出，而且在不引入額外變量的條件下，無法用深度小于n的跳出來實(shí)現(xiàn)。Kosaraju稱這種多層次跳出結(jié)構(gòu)源于BLISS語言。BLISS語言中的多層次跳出形式為leave label，實(shí)際上在BLISS-11版本中才引入到BLISS中，原始的BLISS只有單一層次的跳出。BLISS語言家族不提供無限制的跳轉(zhuǎn)指令，Java語言后來也引入類似BLISS語言中的多層次跳出指令。

Kosaraju的論文中有另一個(gè)較簡(jiǎn)單的結(jié)論：若程序可以在不用額外變量（及多層次的跳出）下化約為結(jié)構(gòu)化程序，其充份必要條件是程序中沒有一個(gè)循環(huán)有二個(gè)或二個(gè)以上的結(jié)束點(diǎn)。簡(jiǎn)單來說，此處Kosaraju定義的化約是指用相同的“基本動(dòng)作”及判斷，計(jì)算相同的函數(shù)，但是可能用不同的控制流程（此處的化約比伯姆及賈可皮尼定理中提及的范圍要窄）。受到這個(gè)結(jié)論的啟發(fā)，Thomas J. McCabe在他引入循環(huán)復(fù)雜度的論文中的第四部分，描述了對(duì)應(yīng)非結(jié)構(gòu)化程序控制流圖（CFG）的Kuratowski定理。使控制流圖變得無法結(jié)構(gòu)化的最小子圖是：

從循環(huán)測(cè)試以外的地方跳出循環(huán)

直接跳躍到循環(huán)中

直接跳躍到一個(gè)判斷分支之中

直接跳出一個(gè)判斷分支

McCabe發(fā)現(xiàn)上述這些子圖不是彼此獨(dú)立的，程序無法結(jié)構(gòu)化的充份必要條件是控制流圖中有子圖有上述四種條件中的三種（或三種以上）。McCabe也發(fā)現(xiàn)若非結(jié)構(gòu)化的程序中包括其中四個(gè)條件中的一個(gè)，它一定還會(huì)包含另一個(gè)。這也是非結(jié)構(gòu)化的程序流程會(huì)糾結(jié)到類似意大利面的原因。McCabe也提供一個(gè)量化方式，說明一個(gè)程序和理想結(jié)構(gòu)化程序之間的距離，并稱其為本質(zhì)復(fù)雜度。4

到1990年為止，學(xué)者們提出許多消除既有程序中跳轉(zhuǎn)指令，但又維持大部分控制架構(gòu)的方式，也提出許多標(biāo)示程序等價(jià)的方式，這些方式比簡(jiǎn)單的圖靈等價(jià)要嚴(yán)格，以免造成類似上述大眾定理般的轉(zhuǎn)換結(jié)果。這些等價(jià)標(biāo)示的嚴(yán)格程度指定了所需控制流結(jié)構(gòu)的最小集合。1998年Lyle Ramshaw在ACM期刊的論文進(jìn)行了相關(guān)的調(diào)查，也提出了自己的方法5。Ramshaw的算法也用在Java反編譯器中，因?yàn)镴ava虛擬機(jī)有分支指令，以位移來表示分支跳轉(zhuǎn)的目標(biāo)，但高級(jí)的Java語言只有多層次的break及continue指令。Ammarguellat在1992年提出一種轉(zhuǎn)換方式，回到強(qiáng)制單一結(jié)束點(diǎn)的作法。

在Cobol上的應(yīng)用1980年代IBM研究員哈倫·米爾斯管理COBOL構(gòu)建設(shè)備（COBOL Structuring Facility）的開發(fā)時(shí)，將程序的結(jié)構(gòu)化算法應(yīng)用到COBOL語言中。米爾斯的轉(zhuǎn)換方式包括以下的步驟。

找出程序中的基礎(chǔ)方塊。

將每一個(gè)方塊的起始點(diǎn)指定不重復(fù)的編號(hào)，將每個(gè)方塊的結(jié)束點(diǎn)用所連接方塊起始點(diǎn)的編號(hào)來標(biāo)示，程序結(jié)束點(diǎn)編號(hào)指定為0，程序起始點(diǎn)編號(hào)指定為1。

將程序分區(qū)為基礎(chǔ)方塊。

若某方塊的起始點(diǎn)只對(duì)應(yīng)一個(gè)方塊的結(jié)束點(diǎn)，將二個(gè)方塊合并。

定義程序中的一個(gè)新的變量，假設(shè)為L。

針對(duì)其他沒有合并的結(jié)束點(diǎn)，增加一行指令，將L設(shè)置為該結(jié)束點(diǎn)的編號(hào)。

將所有基礎(chǔ)方塊合并成一個(gè)選擇執(zhí)行指令，依L的數(shù)值運(yùn)行對(duì)應(yīng)的程序。

創(chuàng)建一個(gè)循環(huán)，若L不為0，繼續(xù)運(yùn)行循環(huán)。

創(chuàng)建程序，一開始將L設(shè)為1，并開始循環(huán)。

注：將一些選擇分支轉(zhuǎn)變?yōu)樽映绦蚩梢愿倪M(jìn)所得結(jié)果。

本詞條內(nèi)容貢獻(xiàn)者為:

胡建平 - 副教授 - 西北工業(yè)大學(xué)