結(jié)構(gòu)化程序理論

數(shù)理科學(xué)術(shù)語(yǔ)結(jié)構(gòu)化程序理論01控制流程討論研究起源變體應(yīng)用目錄030204基本信息結(jié)構(gòu)化程序理論也稱為伯姆-賈可皮尼理論或B?hm-Jacopini理論，是一項(xiàng)編程語(yǔ)言研究的結(jié)果，說(shuō)明只要一種編程語(yǔ)言可以依三個(gè)方式組合其子程序及調(diào)整控制流程，每個(gè)可計(jì)算函數(shù)都可以用此種編程語(yǔ)言來(lái)表示。控制流程控制流程三個(gè)調(diào)整控制流程的方式為匹配上述條件的結(jié)構(gòu)圖需要額外的比特變量（在原始證明中放在額外的整數(shù)變量中），以紀(jì)錄原來(lái)程序運(yùn)行到的位置，此種建構(gòu)法是以伯姆的編程語(yǔ)言P′′為基礎(chǔ)。起源變體起源變體一般認(rèn)為此理論最早是在1966年科拉多·伯姆及朱塞佩·賈可皮尼（GiuseppeJacopini）的論文中提出

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

哈雷爾也提到較通用的“結(jié)構(gòu)化程序理論”名稱是在1970年代初由哈倫·米爾斯提出。單一while循環(huán)的大眾定理版本此版本的定理將原來(lái)定理中的程控流程改為一個(gè)while循環(huán)，模擬在原來(lái)非結(jié)構(gòu)化的程序中，程序計(jì)數(shù)器走過(guò)所有可能標(biāo)記（流程圖方塊）的情形。哈雷爾將此版大眾定理的源頭追溯到兩篇論文，一篇是1946年描述馮·諾伊曼結(jié)構(gòu)，用單一while循環(huán)說(shuō)明程序計(jì)數(shù)器的運(yùn)作原理，哈雷爾也注意到大眾定理中用到的單一循環(huán)基本上可以提供馮·諾伊曼式電腦運(yùn)行流程的操作語(yǔ)義。。另一篇更早期的論文則是斯蒂芬·科爾·克萊尼1936年的正規(guī)形式定理（Kleene'sTpredicate）論文。高德納批評(píng)這種轉(zhuǎn)換后的結(jié)果類似以下的偽代碼，重點(diǎn)是在此轉(zhuǎn)換中完全破壞了原程序的結(jié)構(gòu)。BruceIanMills也有類似的看法：“塊狀結(jié)構(gòu)的精神是其風(fēng)格，不是使用的語(yǔ)言。討論研究討論研究因?yàn)椴芳百Z可皮尼建構(gòu)的方式過(guò)于復(fù)雜，因此此證明沒(méi)有回答結(jié)構(gòu)化編程是否適用于軟件開(kāi)發(fā)的問(wèn)題，而是引發(fā)了后續(xù)相關(guān)的討論及爭(zhēng)議。在兩年之后的1968年，艾茲赫爾·戴克斯特拉就提出著名的“GOTO有害論”。有些學(xué)者試圖使伯姆及賈可皮尼的研究結(jié)果更加純粹，因?yàn)槠湔撐闹袥](méi)有用到從循環(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年開(kāi)發(fā)的Pascal中。從1969年到1990年代中期，學(xué)校常用Pascal來(lái)講授編程語(yǔ)言入門(mén)課程。愛(ài)德華·尤登注意到1970年代時(shí)在有關(guān)是否用自動(dòng)化方式改寫(xiě)非結(jié)構(gòu)化程序一事，有二元對(duì)立的觀點(diǎn)，反對(duì)者認(rèn)為需要以結(jié)構(gòu)化程序的方式去思考，而非一味改寫(xiě)，而贊成者的論點(diǎn)是這類的修改實(shí)際上可以改善大部分已有的程序。最早提出自動(dòng)化改寫(xiě)程序概念的有1971年EdwardAshcroft及ZoharManna的論文。直接應(yīng)用伯姆及賈可皮尼定理可能要引入額外的局部變量，也可能產(chǎn)生代碼重復(fù)的問(wèn)題，后者也稱為loopandahalfproblem。Pascal受到這些問(wèn)題的影響，依照埃里克·S·羅伯茨的實(shí)驗(yàn)研究，學(xué)習(xí)程序設(shè)計(jì)的學(xué)生難以用Pascal設(shè)計(jì)正確代碼來(lái)解決簡(jiǎn)單的問(wèn)題，其中甚至包括從數(shù)組中找尋一個(gè)元素的問(wèn)題。一篇1980年由HenryShapiro進(jìn)行，而后被被羅伯茨引用的研究指出，若只用Pascal提出的流程控制指令，只有20%的人的解答是正確的，但若允許在循環(huán)中直接加入return的話，所有人都寫(xiě)出了正確的答案。S.應(yīng)用應(yīng)用1980年代IBM研究員哈倫·米爾斯管理COBOL構(gòu)建設(shè)備（COBOLStructuri