結構化程式理論

結構化程式理論也稱為伯姆-贾可皮尼理論或Böhm-Jacopini理論^[1][2]，是一項程式語言研究的結果，說明只要一種程式語言可以依三個方式組合其子程式及調整控制流程，每個可计算函数都可以用此種程式語言來表示。三個調整控制流程的方式為

1. 執行一個子程式，然後執行下一個（顺序）
2. 依照布尔變數的結果，決定執行二段子程式中的一段（選擇）
3. 重覆執行某子程式，直到特定布尔變數為真為止（循环）

符合上述條件的結構圖需要額外的位元變數（在原始證明中放在額外的整數變數中），以紀錄原來程式執行到的位置，此種建構法是以伯姆的程式語言P′′（英语：P′′）為基礎。

一般认为^[3]:381此理論最早是在1966年科拉多·伯姆（英语：Corrado Böhm）及朱塞佩·贾可皮尼（Giuseppe Jacopini）的論文中提出^[4]。大卫·哈雷尔（英语：David Harel）在1980年曾提到这篇论文广受认可，^[3]:381尤其在結構化程式理論的支持者中。哈雷尔也提到「由於其論文比較技術的風格，因此較常被引用，較少人真正詳讀過內容。」^[3]:381，在看了1980年以前的大量論文後，哈雷尔認為結構化程式理論被錯誤詮釋為一個結果較簡單的大眾定理（folk theorem），而此結果可以追溯到冯·诺依曼及斯蒂芬·科尔·克莱尼現代計算理論的論文^[3]:383。

哈雷尔也提到較通用的「結構化程式理論」名稱是在1970年代初由哈伦·米尔斯（英语：Harlan Mills）提出^[3]:381。

此版本的定理將原來定理中的程式控制流程改為一個while迴圈，模擬在原來非結構化的程式中，程式計數器走過所有可能標記（流程圖方塊）的情形。哈雷尔将此版大眾定理的源头追溯到两篇論文，一篇是1946年描述冯·诺伊曼结构，用單一while迴圈說明程式計數器的運作原理，哈雷尔也注意到大眾定理中用到的單一迴圈基本上可以提供冯·诺伊曼式電腦執行流程的操作語義。^[3]:383。另一篇更早期的論文則是斯蒂芬·科尔·克莱尼1936年的正规形式定理（Kleene's T predicate）論文^[3]:383。

高德纳批評這種轉換後的結果類似以下的伪代码，重點是在此轉換中完全破壞了原程式的結構^[5]:274。Bruce Ian Mills也有類似的看法：「塊狀結構的精神是其風格，不是使用的語言。利用模擬冯·诺伊曼结构的方式，可以將任何一個面条式代码轉換為塊狀結構的語言，但它面条式代码的本質沒有改變。」^[6]

p := 1;
while p > 0 do begin
  if p = 1 then begin
    進行流程圖的步驟1;
    p := 流程圖的步驟1之後的步驟編號（若沒有後續步驟，數值為0）;
  end;
  if p = 2 then begin
    進行流程圖的步驟2;
    p := 流程圖的步驟2之後的步驟編號（若沒有後續步驟，數值為0）;
  end;
  ...
  if p = n then begin
    進行流程圖的步驟n;
    p := 流程圖的步驟n之後的步驟編號（若沒有後續步驟，數值為0）;
  end;
end.

此章节需要扩充。 (2015年5月27日)

伯姆及賈可皮尼的證明是以流桯圖的結構歸納法為基礎^[3]:381，由於用到图模式匹配，其證明在實務上不能當作是程式轉換（英语：program transformation）演算法，因此開创了此一領域的研究^[7]。

因為伯姆及贾可皮尼建構的方式過於複雜，因此此證明沒有回答結構化編程是否適用於軟體開發的問題，而是引發了後續相關的討論及爭議。在两年之後的1968年，艾茲赫爾·戴克斯特拉就提出著名的「GOTO有害論」^[8]。

有些學者試圖使伯姆及贾可皮尼的研究結果更加純粹，因為其論文中沒有用到從迴圈中間跳出迴圈的break及return指令，因此學者認為這是不好的實作方式，學者們鼓勵每一個迴圈都只能有唯一的結束點，這種設計觀點整合到1968至1969年開發的Pascal中。从1969年到1990年代中期，學校常用Pascal來讲授程式語言入门课程^[9]。

愛德華·尤登注意到1970年代時在有關是否用自動化方式改寫非結構化程式一事，有二元對立的觀點，反對者認為需要以結構化程式的方式去思考，而非一味改寫，而贊成者的論點是這類的修改实际上可以改善大部份已有的程式^[10]。最早提出自動化改寫程式概念的有1971年Edward Ashcroft及Zohar Manna的論文^[11]。

直接應用伯姆及贾可皮尼定理可能要引入額外的局部变量，也可能产生代码重覆的問題^[12]，後者也稱為loop and a half problem^[13]。Pascal受到這些問題的影響，依照埃里克·S·罗伯茨（英语：Eric S. Roberts）的實驗研究，學習程式設計的學生难以用Pascal設計正确程式碼来解决简单的問題，其中甚至包括從陣列中找尋一個元素的問題。一篇1980年由Henry Shapiro进行，而后被被罗伯茨引用的研究指出，若只用Pascal提出的流程控制指令，只有20%的人的解答是正確的，但若允許在迴圈中直接加入return的話，所有人都写出了正確的答案^[9]。

S. Rao Kosaraju（英语：S. Rao Kosaraju）在1973年證明只要允許可以從任意深度迴圈中多層次跳出，就可以將程式轉換成結構化編程，而不用引入額外的变量^[1][14]。而且Kosaraju證明了存在一個嚴格的程式階層（現在稱為Kosaraju階層），針對任一整數n，存在一個程式，其中包括深度n的多層次跳出，而且在不引入額外变量的條件下，無法用深度小於n的跳出來實現^[1]。Kosaraju称這種多層次跳出結構源于BLISS（英语：BLISS）語言。BLISS語言中的多層次跳出形式為leave label，实际上在BLISS-11版本中才引入到BLISS中，原始的BLISS只有單一層次的跳出。BLISS語言家族不提供無限制的跳转指令，Java語言後來也引入類似BLISS語言中的多層次跳出指令^[15]:960-965。

Kosaraju的論文中有另一個較簡單的結論：若程式可以在不用額外变量（及多層次的跳出）下化約為結構化程式，其充份必要條件是程式中沒有一個迴圈有二個或二個以上的結束點。簡單來說，此處Kosaraju定義的化約是指用相同的「基本動作」及判斷，計算相同的函数，但是可能用不同的控制流程（此處的化約比伯姆及贾可皮尼定理中提及的範圍要窄）。受到這個結論的启发，Thomas J. McCabe（英语：Thomas J. McCabe）在他引入循環複雜度的論文中的第四部份，描述了對應非結構化程式控制流圖（CFG）的Kuratowski定理（英语：Kuratowski's theorem）。使控制流圖變得无法結構化的最小子圖是：

1. 从循環測試以外的地方跳出迴圈
2. 直接跳躍到迴圈中
3. 直接跳躍到一個判斷分支之中
4. 直接跳出一個判斷分支

McCabe發現上述這些子圖不是彼此獨立的，程式無法結構化的充份必要條件是控制流圖中有子圖有上述四種條件中的三種（或三種以上）。McCabe也發現若非結構化的程式中包括其中四個條件中的一個，它一定還會包含另一个。這也是非結構化的程式流程會糾結到類似義大利麵的原因。McCabe也提供一個量化方式，說明一個程式和理想結構化程式之間的距離，并稱其為本質複雜度^[16]。

到1990年為止，學者們提出許多消除既有程式中跳转指令，但又維持大部份控制架構的方式，也提出許多標示程式等價的方式，這些方式比简单的圖靈等價要嚴格，以免造成類似上述大眾定理般的转换結果。這些等價標示的嚴格程度指定了所需控制流結構的最小集合。1998年Lyle Ramshaw在ACM期刊的論文進行了相關的調查，也提出了自己的方法^[17]。Ramshaw的演算法也用在Java反編譯器中，因為Java虚拟机有分支指令，以位移來表示分支跳转的目標，但高级的Java語言只有多層次的break及continue指令^[18][19][20]。Ammarguellat在1992年提出一種轉換方式，回到強制單一結束點的作法^[7]。

此章節需要提供更多來源，否則內容可能無法查證。

1980年代IBM研究員哈倫·米爾斯（英语：Harlan Mills）管理COBOL構建設備（COBOL Structuring Facility）的開發时，将程式的結構化演算法应用到COBOL语言中。^[21]。米爾斯的轉換方式包括以下的步驟。

1. 找出程序中的基礎方塊。
2. 將每一個方塊的起始點指定不重覆的編號，將每個方塊的結束點用所連接方塊起始點的編號來標示，程式結束點編號指定為0，程式起始點編號指定為1。
3. 將程序分割為基礎方塊。
4. 若某方塊的起始點只對應一個方塊的結束點，將二個方塊合併。
5. 定義程序中的一個新的变量，假設為L。
6. 針對其他沒有合併的結束點，增加一行指令，將L設定為該結束點的編號。
7. 將所有基礎方塊合并成一個选择执行指令，依L的數值執行對應的程式。
8. 建立一個迴圈，若L不為0，繼續執行迴圈。
9. 建立程序，一開始將L設為1，並開始迴圈。

注：將一些選擇分支轉變為子程序可以改进所得結果。

• 結構化程式設計
• 图灵完全