結構化程式理論

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

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

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

## 起源及變體

一般認為此理論最早是在 1966 年科拉多・伯姆及朱塞佩・賈可皮尼（Giuseppe Jacopini）的論文中提出。大衛・哈雷爾在 1980 年曾提到這篇論文廣受認可，尤其在結構化程式理論的支持者中。哈雷爾也提到「由於其論文比較技術的風格，因此較常被參照，較少人真正詳讀過內容。」，在看了 1980 年以前的大量論文後，哈雷爾認為結構化程式理論被錯誤詮釋為一個結果較簡單的大眾定理（folk theorem），而此結果可以追溯到馮・諾依曼及史蒂芬・科爾・克萊尼現代計算理論的論文。

哈雷爾也提到較通用的「結構化程式理論」名稱是在 1970 年代初由哈倫・米爾斯提出。

### 單一 while 迴圈的大眾定理版本

此版本的定理將原來定理中的程式控制流程改為一個 `while` 迴圈，類比在原來非結構化的程式中，程式計數器走過所有可能標記（流程圖方塊）的情形。哈雷爾將此版大眾定理的源頭追溯到兩篇論文，一篇是 1946 年描述馮・紐曼結構，用單一 while 迴圈說明程式計數器的運作原理，哈雷爾也注意到大眾定理中用到的單一迴圈基本上可以提供馮・紐曼式電腦執行流程的操作語義。。另一篇更早期的論文則是史蒂芬・科爾・克萊尼 1936 年的正規形式定理（Kleene's T predicate）論文。

高德納批評這種轉換後的結果類似以下的虛擬碼，重點是在此轉換中完全破壞了原程式的結構。Bruce Ian Mills 也有類似的看法：「塊狀結構的精神是其風格，不是使用的語言。利用類比馮・紐曼結構的方式，可以將任何一個麵條式代碼轉換為塊狀結構的語言，但它麵條式代碼的本質沒有改變。」

### 伯姆及賈可皮尼的證明

伯姆及賈可皮尼的證明是以流桯圖的結構歸納法為基礎，由於用到圖模式匹配，其證明在實務上不能當作是程式轉換演算法，因此開創了此一領域的研究。

## 相關的討論及研究

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

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

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

直接應用伯姆及賈可皮尼定理可能要引入額外的局部變數，也可能產生代碼重覆的問題，後者也稱為 loop and a half problem。Pascal 受到這些問題的影響，依照埃里克・S・羅伯茨的實驗研究，學習程式設計的學生難以用 Pascal 設計正確程式碼來解決簡單的問題，其中甚至包括從陣列中找尋一個元素的問題。一篇 1980 年由 Henry Shapiro 進行，而後被被羅伯茨參照的研究指出，若只用 Pascal 提出的流程控制指令，只有 20% 的人的解答是正確的，但若允許在迴圈中直接加入 `return` 的話，所有人都寫出了正確的答案。

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

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

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

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

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

## 在 Cobol 上的應用

1980 年代 IBM 研究員哈倫・米爾斯管理 COBOL 構建裝置（COBOL Structuring Facility）的開發時，將程式的結構化演算法應用到 COBOL 語言中。。米爾斯的轉換方式包括以下的步驟。

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

註：將一些選擇分支轉變為子程式可以改進所得結果。

## 相關條目

* 結構化程式設計
* 圖靈完全

## 參考資料