संरचित प्रोग्राम प्रमेय

From Vigyanwiki
Revision as of 23:02, 5 August 2023 by alpha>Aagman

संरचित कार्यक्रम प्रमेय, जिसे बोहम-जैकोपिनी प्रमेय भी कहा जाता है,[1][2] प्रोग्रामिंग भाषा सिद्धांत में परिणाम है। इसमें कहा गया है कि नियंत्रण-प्रवाह ग्राफ़ का वर्ग (ऐतिहासिक रूप से इस संदर्भ में प्रवाह संचित्र कहा जाता है) किसी भी गणना योग्य फ़ंक्शन की गणना कर सकता है यदि यह उपप्रोग्राम को केवल तीन विशिष्ट तरीकों (नियंत्रण संरचनाओं) में जोड़ता है। ये

  1. एक उपप्रोग्राम निष्पादित करना, और फिर दूसरा उपप्रोग्राम (अनुक्रम)
  2. बूलियन डेटा प्रकार अभिव्यक्ति (चयन) के मूल्य के अनुसार दो उपप्रोग्रामों में से को निष्पादित करना
  3. जब तक बूलियन अभिव्यक्ति सत्य है तब तक उपप्रोग्राम को बार-बार निष्पादित करना (पुनरावृत्ति)

इन बाधाओं के अधीन संरचित चार्ट, विशेष रूप से एकल निकास (जैसा कि इस लेख में बाद में वर्णित है) के लिए लूप बाधा, हालांकि जानकारी का ट्रैक रखने के लिए अंश ्स के रूप में अतिरिक्त चर का उपयोग कर सकता है (मूल प्रमाण में अतिरिक्त पूर्णांक चर में संग्रहीत) जो मूल कार्यक्रम कार्यक्रम स्थान द्वारा प्रस्तुत करता है। निर्माण बोहम की प्रोग्रामिंग भाषा P' पर आधारित था।

प्रमेय संरचित प्रोग्रामिंग का आधार बनाता है, प्रोग्रामिंग प्रतिमान जो के लिए जाओ से बचता है and exclusively uses subroutines, sequences, selection and iteration.700पीएक्स

उत्पत्ति और प्रकार

प्रमेय को आमतौर पर श्रेय दिया जाता है[3]: 381  कोराडो बोहम और ग्यूसेप जैकोपिनी द्वारा 1966 के पेपर में।[4] डेविड हरेल ने 1980 में लिखा था कि बोहम-जैकोपिनी पेपर को सार्वभौमिक लोकप्रियता मिली,[3]: 381  विशेष रूप से संरचित प्रोग्रामिंग के समर्थकों के साथ। हरेल ने यह भी कहा कि अपनी तकनीकी शैली के कारण [1966 बोहम-जैकोपिनी पेपर] को स्पष्ट रूप से विस्तार से पढ़ने की तुलना में अधिक बार उद्धृत किया जाता है।[3]: 381  और, 1980 तक प्रकाशित बड़ी संख्या में पत्रों की समीक्षा करने के बाद, हरेल ने तर्क दिया कि बोहम-जैकोपिनी प्रमाण की सामग्री को आमतौर पर गणितीय लोककथा के रूप में गलत तरीके से प्रस्तुत किया गया था जिसमें अनिवार्य रूप से सरल परिणाम शामिल है, परिणाम जो स्वयं जॉन वॉन न्यूमैन के पत्रों में आधुनिक कंप्यूटिंग सिद्धांत की शुरुआत से पता लगाया जा सकता है।[5] और स्टीफन कोल क्लेन।[3]: 383 

हरेल यह भी लिखते हैं कि अधिक सामान्य नाम हरलान मिल्स|एच.डी. द्वारा प्रस्तावित किया गया था। 1970 के दशक की शुरुआत में संरचना प्रमेय के रूप में मिल्स।[3]: 381 

सिंगल-व्हाइल-लूप, प्रमेय का लोक संस्करण

प्रमेय का यह संस्करण सभी मूल प्रोग्राम के नियंत्रण प्रवाह को वैश्विक से बदल देता है while लूप जो मूल गैर-संरचित प्रोग्राम में सभी संभावित लेबल (फ़्लोचार्ट बॉक्स) पर जाने वाले कार्यक्रम गणक का अनुकरण करता है। हरेल ने कंप्यूटिंग की शुरुआत को चिह्नित करने वाले दो पत्रों में इस लोक प्रमेय की उत्पत्ति का पता लगाया। इनमें से वॉन न्यूमैन वास्तुकला का 1946 का विवरण है, जो बताता है कि प्रोग्राम काउंटर थोड़ी देर के लूप के संदर्भ में कैसे संचालित होता है। हारेल का कहना है कि संरचित प्रोग्रामिंग प्रमेय के लोक संस्करण द्वारा उपयोग किया जाने वाला एकल लूप मूल रूप से वॉन न्यूमैन कंप्यूटर पर फ्लोचार्ट के निष्पादन के लिए परिचालन शब्दार्थ प्रदान करता है।[3]: 383  और, यहां तक ​​कि पुराना स्रोत कि हरेल ने प्रमेय के लोक संस्करण का पता लगाया, वह 1936 से स्टीफन क्लेन का क्लेन का टी विधेय है।[3]: 383 

डोनाल्ड नुथ ने प्रमाण के इस रूप की आलोचना की, जिसके परिणामस्वरूप नीचे दिए गए जैसा छद्मकोड मिलता है, यह इंगित करते हुए कि मूल कार्यक्रम की संरचना इस परिवर्तन में पूरी तरह से खो गई है।[6]: 274  इसी तरह, ब्रूस इयान मिल्स ने इस दृष्टिकोण के बारे में लिखा है कि ब्लॉक संरचना की भावना शैली है, भाषा नहीं। वॉन न्यूमैन मशीन का अनुकरण करके, हम ब्लॉक-संरचित भाषा की सीमा के भीतर किसी भी स्पेगेटी कोड के व्यवहार का उत्पादन कर सकते हैं। यह इसे स्पेगेटी होने से नहीं रोकता है।[7] 

p := 1
while p > 0 do
    if p = 1 then
        perform step 1 from the flowchart
        p := resulting successor step number of step 1 from the flowchart (0 if no successor)
    end if
    if p = 2 then
        perform step 2 from the flowchart
        p := resulting successor step number of step 2 from the flowchart (0 if no successor)
    end if
    ...
    if p = n then
        perform step n from the flowchart
        p := resulting successor step number of step n from the flowchart (0 if no successor)
    end if
end while

बोहम और जैकोपिनी का प्रमाण

बोहम और जैकोपिनी के पेपर में प्रमाण प्रवाह चार्ट के संरचनात्मक प्रेरण द्वारा आगे बढ़ता है।[3]: 381  क्योंकि इसमें सबग्राफ समरूपता समस्या को नियोजित किया गया था, बोहम और जैकोपिनी का प्रमाण वास्तव में कार्यक्रम परिवर्तन एल्गोरिदम के रूप में व्यावहारिक नहीं था, और इस प्रकार इस दिशा में अतिरिक्त शोध के लिए द्वार खुल गया।[8]

निहितार्थ और परिशोधन

बोहम-जैकोपिनी प्रमाण ने इस सवाल का समाधान नहीं किया कि सॉफ्टवेयर विकास के लिए संरचित प्रोग्रामिंग को अपनाया जाए या नहीं, आंशिक रूप से क्योंकि निर्माण में किसी प्रोग्राम को सुधारने की तुलना में उसे अस्पष्ट करने की अधिक संभावना थी। इसके विपरीत, इसने बहस की शुरुआत का संकेत दिया। एडवर्ड डिज्क्स्ट्रा का प्रसिद्ध पत्र, हानिकारक माना जाता है, 1968 में अनुसरण किया गया।[9] कुछ शिक्षाविदों ने बोहम-जैकोपिनी परिणाम के लिए शुद्धतावादी दृष्टिकोण अपनाया और तर्क दिया कि निर्देश भी पसंद करते हैं break और return लूप के बीच से निकालना खराब अभ्यास है क्योंकि बोहम-जैकोपिनी प्रमाण में उनकी आवश्यकता नहीं है, और इस प्रकार उन्होंने वकालत की कि सभी लूप में ही निकास बिंदु होना चाहिए। यह शुद्धतावादी दृष्टिकोण पास्कल (प्रोग्रामिंग भाषा) (1968-1969 में डिज़ाइन किया गया) में सन्निहित है, जो 1990 के दशक के मध्य तक शिक्षा जगत में परिचयात्मक प्रोग्रामिंग कक्षाओं को पढ़ाने के लिए पसंदीदा उपकरण था।[10] एडवर्ड योरडन कहते हैं कि 1970 के दशक में असंरचित कार्यक्रमों को स्वचालित माध्यमों से संरचित कार्यक्रमों में बदलने का दार्शनिक विरोध भी था, इस तर्क के आधार पर कि किसी को शुरू से ही संरचित प्रोग्रामिंग फैशन में सोचने की जरूरत थी। व्यावहारिक प्रतिवाद यह था कि ऐसे परिवर्तनों से मौजूदा कार्यक्रमों के बड़े समूह को लाभ हुआ।[11] स्वचालित परिवर्तन के पहले प्रस्तावों में एडवर्ड एशक्रॉफ्ट और जोहार मन्ना का 1971 का पेपर था।[12] बोहम-जैकोपिनी प्रमेय के प्रत्यक्ष अनुप्रयोग के परिणामस्वरूप संरचित चार्ट में अतिरिक्त स्थानीय चर पेश किए जा सकते हैं, और इसके परिणामस्वरूप कुछ कोड दोहराव भी हो सकता है।[13] बाद वाले मुद्दे को इस संदर्भ में लूप एंड हाफ समस्या कहा जाता है।[14] पास्कल इन दोनों समस्याओं से प्रभावित है और एरिक एस. रॉबर्ट्स द्वारा उद्धृत अनुभवजन्य अध्ययनों के अनुसार, छात्र प्रोग्रामरों को पास्कल में कई सरल समस्याओं के लिए सही समाधान तैयार करने में कठिनाई हुई, जिसमें सरणी में तत्व की खोज के लिए फ़ंक्शन लिखना भी शामिल था। रॉबर्ट्स द्वारा उद्धृत हेनरी शापिरो के 1980 के अध्ययन में पाया गया कि केवल पास्कल द्वारा प्रदान की गई नियंत्रण संरचनाओं का उपयोग करके, केवल 20% विषयों द्वारा सही समाधान दिया गया था, जबकि किसी भी विषय ने इस समस्या के लिए गलत कोड नहीं लिखा था, अगर उन्हें लूप के बीच से रिटर्न लिखने की अनुमति दी गई थी।[10]

1973 में, एस. राव कोसाराजू ने साबित किया कि संरचित प्रोग्रामिंग में अतिरिक्त चर जोड़ने से बचना संभव है, जब तक कि लूप से मनमानी-गहराई, बहु-स्तरीय ब्रेक की अनुमति है।[1][15] इसके अलावा, कोसाराजू ने साबित किया कि कार्यक्रमों का सख्त पदानुक्रम मौजूद है, जिसे आजकल कोसाराजू पदानुक्रम कहा जाता है, जिसमें प्रत्येक पूर्णांक n के लिए, गहराई n के बहु-स्तरीय ब्रेक वाला प्रोग्राम मौजूद होता है जिसे n से कम गहराई के बहु-स्तरीय ब्रेक वाले प्रोग्राम के रूप में फिर से नहीं लिखा जा सकता है (अतिरिक्त चर पेश किए बिना)।[1]कोसाराजू BLISS प्रोग्रामिंग भाषा में बहु-स्तरीय ब्रेक निर्माण का हवाला देते हैं। मल्टी-लेवल ब्रेक, फॉर्म ए में leave label कीवर्ड वास्तव में उस भाषा के BLISS-11 संस्करण में पेश किए गए थे; मूल BLISS में केवल एकल-स्तरीय ब्रेक थे। भाषाओं के BLISS परिवार ने अप्रतिबंधित गोटो प्रदान नहीं किया। जावा (प्रोग्रामिंग भाषा) भी बाद में इसी दृष्टिकोण का अनुसरण करेगी।[16]: 960–965 

कोसाराजू के पेपर से सरल परिणाम यह है कि प्रोग्राम संरचित प्रोग्राम (वैरिएबल जोड़े बिना) में कम किया जा सकता है यदि और केवल तभी इसमें दो अलग-अलग निकास के साथ लूप शामिल नहीं है। रिड्यूसिबिलिटी को कोसाराजू द्वारा परिभाषित किया गया था, मोटे तौर पर, ही फ़ंक्शन की गणना करने और मूल कार्यक्रम के रूप में समान आदिम क्रियाओं और विधेय का उपयोग करने के रूप में, लेकिन संभवतः विभिन्न नियंत्रण प्रवाह संरचनाओं का उपयोग करते हुए। (यह बोहम-जैकोपिनी द्वारा उपयोग की जाने वाली रिड्यूसिबिलिटी की तुलना में संकीर्ण धारणा है।) इस परिणाम से प्रेरित होकर, अपने अत्यधिक उद्धृत पेपर के खंड VI में, जिसने साइक्लोमैटिक जटिलता की धारणा पेश की, थॉमस जे। मैककेबे ने गैर-संरचित कार्यक्रमों के नियंत्रण-प्रवाह ग्राफ़ (सीएफजी) के लिए कुराटोस्की के प्रमेय के एनालॉग का वर्णन किया, जिसका अर्थ है, न्यूनतम प्रेरित सबग्राफ जो कार्यक्रम के सीएफजी को गैर-संरचित बनाता है। इन उपसमूहों का प्राकृतिक भाषा में बहुत अच्छा वर्णन है। वे हैं:

  1. लूप से शाखा निकलना (लूप चक्र परीक्षण के अलावा)
  2. एक लूप में शाखाबद्ध होना
  3. किसी निर्णय में शाखा लगाना (अर्थात if शाखा में)
  4. किसी निर्णय से बाहर निकलना

मैककेबे ने वास्तव में पाया कि सबग्राफ के रूप में प्रदर्शित होने पर ये चार ग्राफ स्वतंत्र नहीं होते हैं, जिसका अर्थ है कि किसी प्रोग्राम के गैर-संरचित होने के लिए आवश्यक और पर्याप्त शर्त यह है कि इसके सीएफजी में इन चार ग्राफ में से तीन में से किसी उपसमूह में से सबग्राफ के रूप में होना चाहिए। उन्होंने यह भी पाया कि यदि किसी गैर-संरचित कार्यक्रम में इन चार उप-ग्राफ़ों में से शामिल है, तो इसमें चार के सेट से और अलग होना चाहिए। यह बाद वाला परिणाम यह समझाने में मदद करता है कि कैसे गैर-संरचित प्रोग्राम का नियंत्रण प्रवाह लोकप्रिय रूप से स्पेगेटी कोड कहे जाने वाले में उलझ जाता है। मैककेबे ने संख्यात्मक माप भी तैयार किया, जो मनमाने कार्यक्रम को देखते हुए, यह निर्धारित करता है कि यह संरचित कार्यक्रम होने के आदर्श से कितनी दूर है; मैककेबे ने अपने माप को आवश्यक जटिलता (संरचनात्मकता का संख्यात्मक माप) कहा।[17] संरचित प्रोग्रामिंग के लिए निषिद्ध ग्राफ़ के मैककेब के लक्षण वर्णन को अधूरा माना जा सकता है, कम से कम अगर दिज्क्स्ट्रा की डी संरचनाओं को बिल्डिंग ब्लॉक माना जाता है।[18]: 274–275 

1990 तक मौजूदा कार्यक्रमों से गोटो को हटाने के लिए, उनकी अधिकांश संरचना को संरक्षित करते हुए, कई प्रस्तावित तरीके थे। इस समस्या के विभिन्न दृष्टिकोणों ने समतुल्यता की कई धारणाएँ भी प्रस्तावित कीं, जो ऊपर चर्चा किए गए लोक प्रमेय जैसे आउटपुट से बचने के लिए, केवल ट्यूरिंग समतुल्यता से अधिक कठोर हैं। समतुल्यता की चुनी गई धारणा की कठोरता आवश्यक नियंत्रण प्रवाह संरचनाओं के न्यूनतम सेट को निर्धारित करती है। लाइल रामशॉ द्वारा 1988 का जेएसीएम पेपर उस बिंदु तक क्षेत्र का सर्वेक्षण करता है, साथ ही अपनी विधि का प्रस्ताव भी करता है।[19] उदाहरण के लिए, रैमशॉ के एल्गोरिदम का उपयोग कुछ जावा decompiler ्स में किया गया था क्योंकि जावा वर्चुअल मशीन कोड में ऑफसेट के रूप में व्यक्त लक्ष्यों के साथ शाखा निर्देश होते हैं, लेकिन उच्च-स्तरीय जावा भाषा में केवल बहु-स्तरीय होता है break और continue बयान.[20][21][22] अम्मरगुएलाट (1992) ने परिवर्तन विधि प्रस्तावित की जो एकल-निकास को लागू करने पर आधारित है।[8]

कोबोल पर अनुप्रयोग

1980 के दशक में IBM के शोधकर्ता हरलान मिल्स ने COBOL स्ट्रक्चरिंग सुविधा के विकास का निरीक्षण किया, जिसने COBOL कोड के लिए स्ट्रक्चरिंग एल्गोरिदम लागू किया। मिल्स के परिवर्तन में प्रत्येक प्रक्रिया के लिए निम्नलिखित चरण शामिल थे।

  1. प्रक्रिया में बुनियादी ब्लॉकों की पहचान करें।
  2. प्रत्येक ब्लॉक के प्रवेश पथ के लिए अद्वितीय लेबल (प्रोग्रामिंग भाषा) निर्दिष्ट करें, और प्रत्येक ब्लॉक के निकास पथों को उन प्रवेश पथों के लेबल के साथ लेबल करें जिनसे वे जुड़ते हैं। प्रक्रिया से वापसी के लिए 0 और प्रक्रिया के प्रवेश पथ के लिए 1 का उपयोग करें।
  3. प्रक्रिया को उसके मूल खंडों में विभाजित करें।
  4. प्रत्येक ब्लॉक के लिए जो केवल निकास पथ का गंतव्य है, उस ब्लॉक को उस निकास पथ से पुनः कनेक्ट करें।
  5. प्रक्रिया में नया चर घोषित करें (संदर्भ के लिए एल कहा जाता है)।
  6. प्रत्येक शेष असंबद्ध निकास पथ पर, कथन जोड़ें जो उस पथ पर लेबल मान पर L सेट करता है।
  7. परिणामी प्रोग्रामों को चयन विवरण में संयोजित करें जो प्रोग्राम को एल द्वारा इंगित प्रवेश पथ लेबल के साथ निष्पादित करता है
  8. एक लूप बनाएं जो इस चयन कथन को तब तक निष्पादित करे जब तक L 0 न हो।
  9. एक अनुक्रम का निर्माण करें जो L से 1 आरंभ करता है और लूप निष्पादित करता है।

ध्यान दें कि चयन विवरण के कुछ मामलों को उपप्रक्रियाओं में परिवर्तित करके इस निर्माण में सुधार किया जा सकता है।

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 1.2 Dexter Kozen and Wei-Lung Dustin Tseng (2008). The Böhm–Jacopini Theorem Is False, Propositionally (PDF). pp. 177–192. CiteSeerX 10.1.1.218.9241. doi:10.1007/978-3-540-70594-9_11. ISBN 978-3-540-70593-2. {{cite book}}: |journal= ignored (help)
  2. ↑ "CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM". Cse.buffalo.edu. 2004-11-22. Retrieved 2013-08-24.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 Harel, David (1980). "लोक प्रमेयों पर" (PDF). Communications of the ACM. 23 (7): 379–389. doi:10.1145/358886.358892. S2CID 16300625.
  4. ↑ Bohm, Corrado; Giuseppe Jacopini (May 1966). "केवल दो गठन नियमों के साथ प्रवाह आरेख, ट्यूरिंग मशीनें और भाषाएँ". Communications of the ACM. 9 (5): 366–371. CiteSeerX 10.1.1.119.9119. doi:10.1145/355592.365646. S2CID 10236439.
  5. ↑ Burks, Arthur W.; Goldstine, Herman; von Neumann, John (1947), Preliminary discussion of the Logical Design of an Electronic Computing Instrument, Princeton, NJ: Institute for Advanced Study
  6. ↑ Donald Knuth (1974). "Structured Programming with go to Statements". Computing Surveys. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080.
  7. ↑ Bruce Ian Mills (2005). प्रोग्रामिंग का सैद्धांतिक परिचय. Springer. p. 279. ISBN 978-1-84628-263-8.
  8. ↑ 8.0 8.1 Ammarguellat, Z. (1992). "एक नियंत्रण-प्रवाह सामान्यीकरण एल्गोरिदम और इसकी जटिलता". IEEE Transactions on Software Engineering. 18 (3): 237–251. doi:10.1109/32.126773.
  9. ↑ Dijkstra, Edsger (1968). "हानिकारक माने जाने वाले कथन पर जाएँ". Communications of the ACM. 11 (3): 147–148. doi:10.1145/362929.362947. S2CID 17469809. Archived from the original on 2007-07-03.
  10. ↑ 10.0 10.1 Roberts, E. [1995] "Loop Exits and Structured Programming: Reopening the Debate," ACM SIGCSE Bulletin, (27)1: 268–272.
  11. ↑ E. N. Yourdon (1979). सॉफ्टवेयर इंजीनियरिंग में क्लासिक्स. Yourdon Press. pp. 49–50. ISBN 978-0-917072-14-7.
  12. ↑ Ashcroft, Edward; Zohar Manna (1971). "प्रोग्राम में जाने का अनुवाद 'जबकि' प्रोग्राम में". Proceedings of IFIP Congress. The paper, which is difficult to obtain in the original conference proceedings due to their limited distribution, was republished in Yourdon's 1979 book pp. 51-65
  13. ↑ David Anthony Watt; William Findlay (2004). प्रोग्रामिंग भाषा डिज़ाइन अवधारणाएँ. John Wiley & Sons. p. 228. ISBN 978-0-470-85320-7.
  14. ↑ Kenneth C. Louden; Kenneth A. Lambert (2011). Programming Languages: Principles and Practices (3 ed.). Cengage Learning. pp. 422–423. ISBN 978-1-111-52941-3.
  15. ↑ KOSARAJU, S. RAO. "Analysis of structured programs," Proc. Fifth Annual ACM Syrup. Theory of Computing, (May 1973), 240-252; also Kosaraju, S. Rao (1974). "Analysis of structured programs". Journal of Computer and System Sciences. 9 (3): 232–255. doi:10.1016/S0022-0000(74)80043-7. cited by Donald Knuth (1974). "Structured Programming with go to Statements". Computing Surveys. 6 (4): 261–301. CiteSeerX 10.1.1.103.6084. doi:10.1145/356635.356640. S2CID 207630080.
  16. ↑ Brender, Ronald F. (2002). "The BLISS programming language: a history" (PDF). Software: Practice and Experience. 32 (10): 955–981. doi:10.1002/spe.470. S2CID 45466625.
  17. ↑ The original paper is Thomas J. McCabe (December 1976). "A Complexity Measure". IEEE Transactions on Software Engineering. SE-2 (4): 315–318. doi:10.1109/tse.1976.233837. S2CID 9116234. For a secondary exposition see Paul C. Jorgensen (2002). Software Testing: A Craftsman's Approach, Second Edition (2nd ed.). CRC Press. pp. 150–153. ISBN 978-0-8493-0809-3.
  18. ↑ Williams, M. H. (1983). "फ़्लोचार्ट स्कीमाटा और नामकरण की समस्या". The Computer Journal. 26 (3): 270–276. doi:10.1093/comjnl/26.3.270.
  19. ↑ Ramshaw, L. (1988). "प्रोग्राम संरचना को संरक्षित करते हुए गो को हटाना". Journal of the ACM. 35 (4): 893–920. doi:10.1145/48014.48021. S2CID 31001665.
  20. ↑ Godfrey Nolan (2004). जावा को विघटित करना. Apress. p. 142. ISBN 978-1-4302-0739-9.
  21. ↑ https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf[bare URL PDF]
  22. ↑ http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf[bare URL PDF]


अग्रिम पठन

Material not yet covered above:

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=संरचित_प्रोग्राम_प्रमेय&oldid=243289’