目錄
結構化程序理論
編輯結構化程序定理,也稱為 B?hm–Jacopini 定理,是編程語言理論的一個結果。 它指出,如果一類控制流圖(在此上下文中歷史上稱為流程圖)僅以三種特定方式(控制結構)組合子程序,則它可以計算任何可計算函數。 這些都是
- 執行一個子程序,然后執行另一個子程序(順序)
- 根據布爾表達式的值(選擇)執行兩個子程序之一
- 只要布爾表達式為真,就重復執行子程序(迭代)
然而,受制于這些約束的結構化圖表可以使用位形式的附加變量(存儲在原始證明中的額外整數變量中),以便跟蹤原始程序由程序位置表示的信息。 該結構基于 B?hm 的編程語言 P''。
該定理構成了結構化編程的基礎,結構化編程是一種避開 goto 命令并專門使用子例程、序列、選擇和迭代的編程范例。
起源和變體
編輯該定理通常歸功于 Corrado B?hm 和 Giuseppe Jacopini 1966 年的一篇論文。 David Harel 在 1980 年寫道,B?hm–Jacopini 論文廣受歡迎,尤其是在結構化編程的支持者中。 Harel 還指出,由于其相當技術性的風格 [1966 年的 B?hm–Jacopini 論文] 顯然被引用的次數多于詳細閱讀的次數,并且在回顧了 1980 年之前發表的大量論文之后,Harel 認為 B?hm 的內容—— Jacopini 證明通常被誤認為是一個民間定理,它本質上包含一個更簡單的結果,這個結果本身可以追溯到馮諾依曼和克萊恩的論文中現代計算理論的起源。
Harel 還寫道,更通用的名稱是由 H.D. 提出的。 米爾斯在 1970 年代初作為結構定理。
單 while 循環,定理的民間版本
這個版本的定理用單個全局 while 循環替換了所有原始程序的控制流,該循環模擬程序計數器遍歷原始非結構化程序中所有可能的標簽(流程圖框)。 Harel 將這個民間定理的起源追溯到兩篇標志著計算開始的論文。 一個是 1946 年對馮諾依曼體系結構的描述,它解釋了程序計數器如何根據 while 循環運行。 Harel 指出,結構化編程定理的民間版本使用的單循環基本上只是為在馮諾依曼計算機上執行流程圖提供了操作語義。 Harel 追溯該定理的民間版本的另一個更古老的來源是 Stephen Kleene 1936 年的范式定理。
Donald Knuth 批評了這種形式的證明,指出原始程序的結構在這種轉換中完全丟失了,從而導致如下所示的偽代碼。 同樣,布魯斯·伊恩·米爾斯 (Bruce Ian Mills) 寫過這種方法,塊結構的精神是一種風格,而不是一種語言。 通過模擬馮諾依曼機,我們可以在塊結構語言的范圍內生成任何意大利面條代碼的行為。
B?hm 和 Jacopini 的證明
B?hm 和 Jacopini 的論文中的證明是通過對流程圖的結構進行歸納來進行的。 因為它在圖形中使用了模式匹配,B?hm 和 Jacopini 的證明作為程序轉換算法并不真正實用,因此打開了在這個方向進一步研究的大門。
影響和改進
編輯B?hm–Jacopini 證明并沒有解決是否為軟件開發采用結構化編程的問題,部分原因是構造更有可能使程序變得模糊而不是改進程序。 相反,它標志著辯論的開始。 Edsger Dijkstra 的著名信件 Go To Statement Considered Harmful 隨后于 1968 年發表。

一些學者對 B?hm-Jacopini 結果采取了純粹主義的方法,并認為即使像 break 和 return 這樣的指令從循環中間返回也是不好的做法,因為在 B?hm-Jacopini 證明中不需要它們,因此他們主張所有循環都應該有 一個出口點。 這種純粹的方法體現在 Pascal 編程語言(設計于 1968 年至 1969 年)中,直到 1990 年代中期,它還是介紹性教學的首選工具。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/198193/
