本页使用了标题或全文手工转换

結構化程式理論

维基百科,自由的百科全书
跳转至: 导航搜索
3個調整控制流程的方式
3個調整控制流程的方式

結構化程式理論也稱為伯姆-贾可皮尼理論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

相關條目[编辑]

參考資料[编辑]

  1. ^ Dexter Kozen and Wei-Lung Dustin Tseng. The Böhm–Jacopini Theorem Is False, Propositionally. MPC 2008. doi:10.1007/978-3-540-70594-9_11. 
  2. ^ CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM. Cse.buffalo.edu. 2004-11-22 [2013-08-24]. 
  3. ^ 3.0 3.1 3.2 3.3 3.4 Harel, David. On Folk Theorems. Communications of the ACM. 1980, 23 (7): 379–389. doi:10.1145/358886.358892. 
  4. ^ Bohm, Corrado; Giuseppe Jacopini. Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules. Communications of the ACM. May 1966, 9 (5): 366–371. doi:10.1145/355592.365646.