संरचित प्रोग्राम प्रमेय: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (7 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{short description|Control-flow graphs with 3 types of control structures can compute any computable function}} | {{short description|Control-flow graphs with 3 types of control structures can compute any computable function}} | ||
संरचित | '''संरचित प्रोग्राम प्रमेय''', जिसे '''बोहम-जैकोपिनी''' की '''प्रमेय''' भी कहा जाता है,<ref name="kozen">{{cite book|url= http://www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf |title=The Böhm–Jacopini Theorem Is False, Propositionally|author=[[Dexter Kozen]] and Wei-Lung Dustin Tseng|doi=10.1007/978-3-540-70594-9_11|journal=MPC 2008|volume=5133|pages=177–192|series=Lecture Notes in Computer Science|year=2008|isbn=978-3-540-70593-2|citeseerx=10.1.1.218.9241}}</ref><ref>{{cite web|url=http://www.cse.buffalo.edu/~rapaport/111F04/greatidea3.html |title=CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM |publisher=Cse.buffalo.edu |date=2004-11-22 |access-date=2013-08-24}}</ref> [[प्रोग्रामिंग भाषा सिद्धांत|प्रोग्रामिंग लैंग्वेज सिद्धांत]] का एक परिणाम है। इसमें कहा गया है कि [[नियंत्रण-प्रवाह ग्राफ|कंट्रोल-फ्लो ग्राफ]] का वर्ग (ऐतिहासिक रूप से इस संदर्भ में [[प्रवाह संचित्र|फ्लो संचित्र]] कहा जाता है) किसी भी गणना योग्य संक्रिया की गणना कर सकता है यदि यह उपप्रोग्राम को मात्र तीन विशिष्ट विधियों ([[नियंत्रण संरचना|कंट्रोल संरचनाओं]]) में जोड़ता है। ये इस प्रकार निम्नलिखित हैं- | ||
#एक उपप्रोग्राम निष्पादित करना, और फिर दूसरा उपप्रोग्राम (अनुक्रम) | #एक उपप्रोग्राम निष्पादित करना, और फिर दूसरा उपप्रोग्राम (अनुक्रम)। | ||
#[[बूलियन डेटा प्रकार]] अभिव्यक्ति (चयन) के | #[[बूलियन डेटा प्रकार]] अभिव्यक्ति (चयन) के मान के अनुसार दो उपप्रोग्रामों में से को निष्पादित करना। | ||
#जब तक बूलियन अभिव्यक्ति सत्य है तब तक उपप्रोग्राम को बार-बार निष्पादित करना (पुनरावृत्ति) | #जब तक बूलियन अभिव्यक्ति सत्य है तब तक उपप्रोग्राम को बार-बार निष्पादित करना (पुनरावृत्ति)। | ||
इन बाधाओं के अधीन संरचित चार्ट, विशेष रूप से एकल निकास (जैसा कि इस लेख में बाद में वर्णित है) के लिए लूप बाधा, | इन बाधाओं के अधीन संरचित चार्ट, विशेष रूप से एकल निकास (जैसा कि इस लेख में बाद में वर्णित है) के लिए लूप बाधा, यद्यपि सूचना का ट्रैक रखने के लिए [[ अंश |बिट्स]] के रूप में अतिरिक्त चर का उपयोग कर सकता है (मूल प्रमाण में अतिरिक्त पूर्णांक चर में संग्रहीत) जो मूल प्रोग्राम प्रोग्राम स्थान द्वारा प्रस्तुत करता है। इस प्रकार से निर्माण बोहम की प्रोग्रामिंग लैंग्वेज P' पर आधारित था। | ||
प्रमेय [[संरचित प्रोग्रामिंग]] का आधार बनाता है, प्रोग्रामिंग प्रतिमान जो [[ के लिए जाओ ]] से बचता है | अतः प्रमेय [[संरचित प्रोग्रामिंग]] का आधार बनाता है, प्रोग्रामिंग प्रतिमान जो [[ के लिए जाओ |गोटो कमांड]] से बचता है, और विशेष रूप से प्रक्रिया, अनुक्रम, चयन और पुनरावृत्ति का उपयोग करता है।[[File:Structured program patterns.svg|संरचित कार्यक्रम प्रमेय के तीन बुनियादी पैटर्न का ग्राफिकल प्रतिनिधित्व - अनुक्रम, चयन, और पुनरावृत्ति - नासी-श्नीडरमैन आरेख (नीला) और [[प्रवाह चार्ट]] (हरा) का उपयोग करके।|अंगूठा|केंद्र|सीमा|700पीएक्स]] | ||
== उत्पत्ति और प्रकार == | == उत्पत्ति और प्रकार == | ||
प्रमेय | प्रमेय का श्रेय सामान्यतः<ref name="Harel"/>{{rp|381}} कोराडो बोहम और ग्यूसेप जैकोपिनी द्वारा 1966 के लेख को दिया जाता है।<ref>{{cite journal|last=Bohm|first=Corrado|author2=Giuseppe Jacopini |date=May 1966|title=केवल दो गठन नियमों के साथ प्रवाह आरेख, ट्यूरिंग मशीनें और भाषाएँ|journal=[[Communications of the ACM]]|volume=9|issue=5|pages=366–371|doi=10.1145/355592.365646|citeseerx=10.1.1.119.9119|s2cid=10236439 }}</ref> इस प्रकार से [[डेविड हरेल]] ने 1980 में लिखा था कि बोहम-जैकोपिनी लेख को सार्वभौमिक लोकप्रियता मिली,<ref name="Harel"/>{{rp|381}} विशेष रूप से संरचित प्रोग्रामिंग के समर्थकों के बीच में। हरेल ने यह भी कहा कि "अपनी तकनीकी शैली के कारण [1966 बोहम-जैकोपिनी लेख] को स्पष्ट रूप से विस्तार से पढ़ने की तुलना में अधिक बार उद्धृत किया जाता है"<ref name="Harel"/>{{rp|381}} और, 1980 तक प्रकाशित बड़ी संख्या में लेखों की समीक्षा करने के बाद, हरेल ने तर्क दिया कि बोहम-जैकोपिनी प्रमाण को सामान्यतः एक फोक प्रमेय के रूप में अनुचित विधि से प्रस्तुत किया गया था जिसमें अनिवार्य रूप से सरल परिणाम सम्मिलित था, एक परिणाम जिसका स्वयं [[जॉन वॉन न्यूमैन]]<ref>{{Citation|last1= Burks|first1= Arthur W.|last2= Goldstine|first2= Herman|last3= von Neumann|first3= John|author-link= Arthur W. Burks|author2-link= Herman Goldstine|author3-link = John von Neumann|title= Preliminary discussion of the Logical Design of an Electronic Computing Instrument|publisher= Institute for Advanced Study|location= Princeton, NJ|year= 1947}}</ref> और [[स्टीफन कोल क्लेन]] के लेखों में आधुनिक कंप्यूटिंग सिद्धांत के प्रारंभ से ज्ञात किया जा सकता है।<ref name="Harel"/>{{rp|383}} | ||
हरेल यह भी लिखते हैं कि अधिक सामान्य नाम | इस प्रकार से हरेल यह भी लिखते हैं कि अधिक सामान्य नाम 1970 के दशक के प्रारंभ में मिल्स हरलान द्वारा संरचना प्रमेय के रूप में प्रस्तावित किया गया था।<ref name="Harel">{{cite journal|last=Harel|first=David|author-link=David Harel|year=1980|title=लोक प्रमेयों पर|journal=Communications of the ACM|volume=23|issue=7|pages=379–389|doi=10.1145/358886.358892|s2cid=16300625 |url=http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/OnFolkTheorems.pdf}}</ref>{{rp|381}} | ||
=== सिंगल-व्हाइल-लूप, प्रमेय का | === सिंगल-व्हाइल-लूप, प्रमेय का फोक संस्करण === | ||
प्रमेय का यह संस्करण सभी मूल प्रोग्राम के | अतः प्रमेय का यह संस्करण सभी मूल प्रोग्राम के कंट्रोल फ्लो को एक एकल वैश्विक <code>while</code> लूप से बदल देता है जो मूल गैर-संरचित प्रोग्राम में सभी संभावित लेबल (फ्लोचार्ट बॉक्स) पर जाने वाले [[ कार्यक्रम गणक |प्रोग्राम गणित्र]] का अनुकरण करता है। इस प्रकार से हरेल ने कंप्यूटिंग के प्रारंभ को चिह्नित करने वाले दो लेखों में इस फोक प्रमेय की उत्पत्ति को ज्ञात किया। इनमें से [[वॉन न्यूमैन वास्तुकला]] का 1946 का विवरण है, जो बताता है कि प्रोग्राम काउंटर थोड़ी विलम्ब के लूप के संदर्भ में कैसे संचालित होता है। अतः हारेल का कहना है कि संरचित प्रोग्रामिंग प्रमेय के फोक संस्करण द्वारा उपयोग किया जाने वाला एकल लूप मूल रूप से वॉन न्यूमैन कंप्यूटर पर फ्लोचार्ट के निष्पादन के लिए [[परिचालन शब्दार्थ]] प्रदान करता है।<ref name="Harel"/>{{rp|383}} एक और, यहां तक कि प्राचीन स्रोत कि हरेल ने प्रमेय के फोक संस्करण को ज्ञात किया, वह 1936 से [[स्टीफन क्लेन]] का सामान्य रूप प्रमेय है।<ref name="Harel"/>{{rp|383}} | ||
[[डोनाल्ड नुथ]] ने प्रमाण के इस रूप की आलोचना की, जिसके परिणामस्वरूप नीचे दिए गए जैसा [[छद्मकोड]] मिलता है, यह इंगित करते हुए कि मूल | इस प्रकार से [[डोनाल्ड नुथ]] ने प्रमाण के इस रूप की आलोचना की, जिसके परिणामस्वरूप नीचे दिए गए जैसा [[छद्मकोड|स्कोडोकोड]] मिलता है, यह इंगित करते हुए कि मूल प्रोग्राम की संरचना इस परिवर्तन में पूर्ण रूप से लुप्त हो गई है।<ref>{{cite journal | ||
| author = Donald Knuth | | author = Donald Knuth | ||
| title = Structured Programming with go to Statements | | title = Structured Programming with go to Statements | ||
| Line 28: | Line 28: | ||
| citeseerx = 10.1.1.103.6084 | | citeseerx = 10.1.1.103.6084 | ||
| s2cid = 207630080 | | s2cid = 207630080 | ||
}}</ref>{{rp|274}} इसी | }}</ref>{{rp|274}} अतः इसी प्रकार, ब्रूस इयान मिल्स ने इस दृष्टिकोण के विषय में लिखा है कि ब्लॉक संरचना की भावना शैली है, लैंग्वेज नहीं। वॉन न्यूमैन मशीन का अनुकरण करके, हम ब्लॉक-संरचित लैंग्वेज की सीमा के भीतर किसी भी स्पेगेटी कोड के व्यवहार का उत्पादन कर सकते हैं। इस प्रकार से यह इसे स्पेगेटी होने से नहीं रोकता है।<ref name="Mills2005">{{cite book|author=Bruce Ian Mills|title=प्रोग्रामिंग का सैद्धांतिक परिचय|year=2005|publisher=Springer|isbn=978-1-84628-263-8|page=279}}</ref> | ||
<syntaxhighlight lang="pascal"> | <syntaxhighlight lang="pascal"> | ||
| Line 50: | Line 50: | ||
=== बोहम और जैकोपिनी का प्रमाण === | === बोहम और जैकोपिनी का प्रमाण === | ||
बोहम और जैकोपिनी के | अतः बोहम और जैकोपिनी के लेख में प्रमाण फ्लो चार्ट के [[संरचनात्मक प्रेरण]] द्वारा आगे बढ़ता है।<ref name="Harel"/>{{rp|381}} क्योंकि इसमें [[सबग्राफ समरूपता समस्या|उपग्राफ समरूपता समस्या]] को नियोजित किया गया था, इस प्रकार से बोहम और जैकोपिनी का प्रमाण वस्तुतः [[कार्यक्रम परिवर्तन|प्रोग्राम परिवर्तन]] एल्गोरिदम के रूप में व्यावहारिक नहीं था, और इस प्रकार इस दिशा में अतिरिक्त शोध के लिए द्वार विवृत हुआ।<ref name="amma92"/> | ||
== निहितार्थ और परिशोधन == | == निहितार्थ और परिशोधन == | ||
बोहम-जैकोपिनी प्रमाण ने इस सवाल का | अतः बोहम-जैकोपिनी प्रमाण ने इस सवाल का हल नहीं किया कि सॉफ्टवेयर विकास के लिए संरचित प्रोग्रामिंग को अपनाया जाए या नहीं, आंशिक रूप से क्योंकि निर्माण में किसी प्रोग्राम को सुधारने की तुलना में उसे अस्पष्ट करने की अधिक संभावना थी। इसके विपरीत, इसने चर्चा के प्रारंभ का संकेत दिया। इस प्रकार से [[एडवर्ड डिज्क्स्ट्रा]] का प्रसिद्ध लेख, [[हानिकारक माना जाता है|"गो टू स्टेटमेंट कंसीडर्ड हार्मफुल,"]] 1968 में आया।<ref>{{cite journal|last=Dijkstra|first=Edsger|author-link=Edsger W. Dijkstra|year=1968|title=हानिकारक माने जाने वाले कथन पर जाएँ|journal=Communications of the ACM|volume=11|issue=3|pages=147–148|doi=10.1145/362929.362947|s2cid=17469809 |url=http://www.acm.org/classics/oct95/|url-status=dead|archive-url=https://web.archive.org/web/20070703050443/http://www.acm.org/classics/oct95/|archive-date=2007-07-03}}</ref> | ||
1973 में, एस. राव कोसाराजू ने | कुछ शिक्षाविदों ने बोहम-जैकोपिनी परिणाम के लिए एक शुद्धतावादी दृष्टिकोण अपनाया और तर्क दिया कि लूप के बीच से <code>break</code> और <code>return</code> जैसे निर्देश भी निकृष्ट अभ्यास हैं क्योंकि बोहम-जैकोपिनी प्रमाण में उनकी आवश्यकता नहीं है, और इस प्रकार उन्होंने समर्थन किया कि सभी लूपों का एक ही निकास बिंदु होना चाहिए। इस प्रकार से यह शुद्धतावादी दृष्टिकोण [[पास्कल (प्रोग्रामिंग भाषा)|पास्कल (प्रोग्रामिंग लैंग्वेज)]] (1968-1969 में डिज़ाइन किया गया) में सन्निहित है, जो 1990 के दशक के मध्य तक शिक्षा जगत में परिचयात्मक प्रोग्रामिंग कक्षाओं को पढ़ाने के लिए चयनित उपकरण था।<ref name="roberts">Roberts, E. [1995] "[http://cs.stanford.edu/people/eroberts/papers/SIGCSE-1995/LoopExits.pdf Loop Exits and Structured Programming: Reopening the Debate]," ACM SIGCSE Bulletin, (27)1: 268–272.</ref> | ||
अतः एडवर्ड योरडन कहते हैं कि 1970 के दशक में असंरचित प्रोग्रामों को स्वचालित माध्यमों से संरचित प्रोग्रामों में बदलने का दार्शनिक विरोध भी था, इस तर्क के आधार पर कि किसी को प्रारंभ से ही संरचित प्रोग्रामिंग फैशन में सोचने की आवश्यकता थी। इस प्रकार से व्यावहारिक प्रतिवाद यह था कि ऐसे परिवर्तनों से वर्तमान प्रोग्रामों के बड़े समूह को लाभ हुआ।<ref name="Yourdon1979">{{cite book|author=E. N. Yourdon|title=सॉफ्टवेयर इंजीनियरिंग में क्लासिक्स|year=1979|publisher=Yourdon Press|isbn=978-0-917072-14-7|pages=[https://archive.org/details/classicsinsoftwa00your/page/49 49–50]|url-access=registration|url=https://archive.org/details/classicsinsoftwa00your/page/49}}</ref> अतः स्वचालित परिवर्तन के पहले प्रस्तावों में एडवर्ड एशक्रॉफ्ट और [[जोहार मन्ना]] का 1971 का लेख था।<ref>{{cite journal|last=Ashcroft|first=Edward|author2=Zohar Manna |year=1971|title=प्रोग्राम में जाने का अनुवाद 'जबकि' प्रोग्राम में|journal=[[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</ref> | |||
बोहम-जैकोपिनी प्रमेय के प्रत्यक्ष अनुप्रयोग के परिणामस्वरूप संरचित चार्ट में अतिरिक्त स्थानीय चर प्रस्तुत किए जा सकते हैं, और इसके परिणामस्वरूप कुछ [[कोड दोहराव]] भी हो सकता है।<ref name="WattFindlay2004">{{cite book|author1=David Anthony Watt|author2=William Findlay|title=प्रोग्रामिंग भाषा डिज़ाइन अवधारणाएँ|url=https://archive.org/details/programminglangu00watt_497|url-access=limited|year=2004|publisher=John Wiley & Sons|isbn=978-0-470-85320-7|page=[https://archive.org/details/programminglangu00watt_497/page/n246 228]}}</ref> बाद वाली समस्या को इस संदर्भ में लूप एंड हाफ समस्या कहा जाता है।<ref name="LoudenLambert2011">{{cite book|author1=Kenneth C. Louden|author2=Kenneth A. Lambert|title=Programming Languages: Principles and Practices|url=https://archive.org/details/programminglangu00loud_140|url-access=limited|year=2011|publisher=Cengage Learning|isbn=978-1-111-52941-3|pages=[https://archive.org/details/programminglangu00loud_140/page/n426 422]–423|edition=3}}</ref> इस प्रकार से पास्कल इन दोनों समस्याओं से प्रभावित है और एरिक एस. रॉबर्ट्स द्वारा उद्धृत अनुभवजन्य अध्ययनों के अनुसार, छात्र प्रोग्रामरों को पास्कल में कई सरल समस्याओं के लिए उचित हल तैयार करने में जटिलता हुई, जिसमें सरणी में तत्व की खोज के लिए संक्रिया लिखना भी सम्मिलित था। अतः रॉबर्ट्स द्वारा उद्धृत हेनरी शापिरो के 1980 के अध्ययन में पाया गया कि मात्र पास्कल द्वारा प्रदान की गई कंट्रोल संरचनाओं का उपयोग करके, मात्र 20% विषयों द्वारा उचित हल दिया गया था, जबकि किसी भी विषय ने इस समस्या के लिए अनुचित कोड नहीं लिखा था, यदि उन्हें लूप के बीच से पुनरावृत्ति लिखने की अनुमति दी गई थी।<ref name="roberts" /> | |||
इस प्रकार से 1973 में, एस. राव कोसाराजू ने सिद्ध किया कि संरचित प्रोग्रामिंग में अतिरिक्त चर जोड़ने से बचना संभव है, जब तक कि लूप से यादृच्छिक-गहनता, बहु-स्तरीय ब्रेक की अनुमति है।<ref name="kozen" /><ref>KOSARAJU, S. RAO. "Analysis of structured programs," Proc. Fifth Annual ACM Syrup. | |||
Theory of Computing, (May 1973), 240-252; also {{cite journal | doi = 10.1016/S0022-0000(74)80043-7 | volume=9 | title=Analysis of structured programs | year=1974 | journal=Journal of Computer and System Sciences | pages=232–255 | last1 = Kosaraju | first1 = S. Rao| issue=3 | doi-access=free }} cited by {{cite journal | Theory of Computing, (May 1973), 240-252; also {{cite journal | doi = 10.1016/S0022-0000(74)80043-7 | volume=9 | title=Analysis of structured programs | year=1974 | journal=Journal of Computer and System Sciences | pages=232–255 | last1 = Kosaraju | first1 = S. Rao| issue=3 | doi-access=free }} cited by {{cite journal | ||
| author = [[Donald Knuth]] | | author = [[Donald Knuth]] | ||
| Line 69: | Line 72: | ||
| citeseerx = 10.1.1.103.6084 | | citeseerx = 10.1.1.103.6084 | ||
| s2cid = 207630080 | | s2cid = 207630080 | ||
}}</ref> इसके | }}</ref> अतः इसके अतिरिक्त, कोसाराजू ने सिद्ध किया कि प्रोग्रामों का स्पष्ट पदानुक्रम स्थित है, जिसे आजकल कोसाराजू पदानुक्रम कहा जाता है, जिसमें प्रत्येक पूर्णांक n के लिए, गहनता n के बहु-स्तरीय ब्रेक वाला प्रोग्राम स्थित होता है जिसे n से कम गहनता के बहु-स्तरीय ब्रेक वाले प्रोग्राम के रूप में फिर से नहीं लिखा जा सकता है (अतिरिक्त चर प्रस्तुत किए बिना)।<ref name="kozen" /> इस प्रकार से कोसाराजू [[BLISS|ब्लिस]] प्रोग्रामिंग लैंग्वेज में बहु-स्तरीय ब्रेक निर्माण का उद्धृत कर देते हैं। अतः बहु-स्तरीय ब्रेक, <code>leave ''label''</code> कीवर्ड के रूप में, वस्तुतः उस लैंग्वेज के ब्लिस-11 संस्करण में प्रस्तुत किए गए थे; मूल ब्लिस में मात्र एकल-स्तरीय ब्रेक थे। लैंग्वेज के ब्लिस वर्ग ने अप्रतिबंधित गोटो प्रदान नहीं किया। [[जावा (प्रोग्रामिंग भाषा)|जावा (प्रोग्रामिंग लैंग्वेज)]] भी बाद में इसी दृष्टिकोण का अनुसरण करेगी।<ref>{{cite journal | doi = 10.1002/spe.470 | title=The BLISS programming language: a history | journal=Software: Practice and Experience | date=2002 | volume=32 | issue=10 | pages=955–981 | first=Ronald F. | last=Brender | s2cid=45466625 | url = https://www.cs.tufts.edu/~nr/cs257/archive/ronald-brender/bliss.pdf}}</ref>{{rp|960–965}} | ||
कोसाराजू के | इस प्रकार से कोसाराजू के लेख से सरल परिणाम यह है कि प्रोग्राम संरचित प्रोग्राम (वैरिएबल जोड़े बिना) में कम किया जा सकता है यदि और मात्र तभी इसमें दो अलग-अलग निकास के साथ लूप सम्मिलित नहीं है। अतः समानेयता को कोसाराजू द्वारा परिभाषित किया गया था, साधारणतया, एक ही संक्रिया की गणना करने और मूल प्रोग्राम के रूप में समान आदिम क्रियाओं और विशेषण का उपयोग करने के रूप में, परन्तु संभवतः विभिन्न कंट्रोल फ्लो संरचनाओं का उपयोग करते हुए। (यह बोहम-जैकोपिनी द्वारा उपयोग की जाने वाली समानेयता की तुलना में संकीर्ण धारणा है।) इस परिणाम से प्रेरित होकर, अपने अत्यधिक उद्धृत लेख के खंड VI में, जिसने चक्रीय जटिलता की धारणा प्रस्तुत की, थॉमस जे. मैककेबे ने गैर-संरचित प्रोग्रामों के कंट्रोल-फ्लो ग्राफ़ (सीएफजी) के लिए कुराटोस्की के प्रमेय के एनालॉग का वर्णन किया, जिसका अर्थ है, न्यूनतम उपग्राफ जो किसी कार्यक्रम के सीएफजी को गैर-संरचित बनाते हैं। इन उपसमूहों का प्राकृतिक लैंग्वेज में बहुत अच्छा वर्णन है। इस प्रकार से वे निम्नलिखित हैं: | ||
# लूप से | # लूप से शाखन निकलना (लूप चक्र परीक्षण के अतिरिक्त)। | ||
# एक लूप में | # एक लूप में शाखनबद्ध होना। | ||
# किसी निर्णय में | # किसी निर्णय में शाखन लगाना (अर्थात यदि शाखन में)। | ||
#किसी निर्णय से बाहर | #किसी निर्णय से बाहर निकलना। | ||
मैककेबे ने | अतः मैककेबे ने वस्तुतः पाया कि उपग्राफ के रूप में प्रदर्शित होने पर ये चार ग्राफ स्वतंत्र नहीं होते हैं, जिसका अर्थ है कि किसी प्रोग्राम के गैर-संरचित होने के लिए आवश्यक और पर्याप्त प्रतिबन्ध यह है कि इसके सीएफजी में इन चार ग्राफ में से तीन में से किसी उपसमूह में से उपग्राफ के रूप में होना चाहिए। इस प्रकार से उन्होंने यह भी पाया कि यदि किसी गैर-संरचित प्रोग्राम में इन चार उप-ग्राफ़ों में से सम्मिलित है, तो इसमें चार के सेट से और अलग होना चाहिए। यह बाद वाला परिणाम यह समझाने में सहायता करता है कि कैसे गैर-संरचित प्रोग्राम का कंट्रोल फ्लो लोकप्रिय रूप से [[स्पेगेटी कोड]] कहे जाने वाले जटिल हो जाता है। अतः मैककेबे ने संख्यात्मक माप भी तैयार किया, जो यादृच्छिक प्रोग्राम को देखते हुए, यह निर्धारित करता है कि यह संरचित प्रोग्राम होने के आदर्श से कितनी दूर है; मैककेबे ने अपने माप को आवश्यक जटिलता (संरचनात्मकता का संख्यात्मक माप) कहा।<ref name="McCabe">The original paper is {{cite journal |author=Thomas J. McCabe |date=December 1976 |journal=IEEE Transactions on Software Engineering |issue=4 |pages=315–318 |title=A Complexity Measure|url=https://books.google.com/books?id=vtNWAAAAMAAJ&pg=PA3 |doi=10.1109/tse.1976.233837 |volume=SE-2|s2cid=9116234 }} For a secondary exposition see {{cite book|author=Paul C. Jorgensen|title=Software Testing: A Craftsman's Approach, Second Edition|url=https://books.google.com/books?id=Yph_AwAAQBAJ&pg=PA150|year=2002|publisher=CRC Press|isbn=978-0-8493-0809-3|pages=150–153|edition=2nd}}</ref> | ||
1990 तक | इस प्रकार से संरचित प्रोग्रामिंग के लिए [[निषिद्ध ग्राफ]] के मैककेब के लक्षण वर्णन को अधूरा माना जा सकता है, कम से कम यदि दिज्क्स्ट्रा की डी संरचनाओं को बिल्डिंग ब्लॉक माना जाता है।<ref>{{cite journal | doi = 10.1093/comjnl/26.3.270 | title=फ़्लोचार्ट स्कीमाटा और नामकरण की समस्या| journal=The Computer Journal | date=1983 | volume=26 | issue=3 | pages=270–276 | first=M. H. | last=Williams| doi-access=free }}</ref>{{rp|274–275}} | ||
अतः 1990 तक वर्तमान प्रोग्रामों से "गोटो" को हटाने के लिए, उनकी अधिकांश संरचना को संरक्षित करते हुए, कई प्रस्तावित विधि थे। इस प्रकार से इस समस्या के विभिन्न दृष्टिकोणों ने समतुल्यता की कई धारणाएँ भी प्रस्तावित कीं थी, जो ऊपर चर्चा किए गए फोक प्रमेय जैसे आउटपुट से बचने के लिए, मात्र ट्यूरिंग समतुल्यता से अधिक जटिल हैं। समतुल्यता की चुनी गई धारणा की जटिलता आवश्यक कंट्रोल फ्लो संरचनाओं के न्यूनतम सेट को निर्धारित करती है। अतः लाइल रामशॉ द्वारा 1988 का [[जेएसीएम]] लेख उस बिंदु तक क्षेत्र का सर्वेक्षण करता है, साथ ही अपनी विधि का प्रस्ताव भी करता है।<ref>{{Cite journal | doi = 10.1145/48014.48021| title = प्रोग्राम संरचना को संरक्षित करते हुए गो को हटाना| journal = Journal of the ACM| volume = 35| issue = 4| pages = 893–920| year = 1988| last1 = Ramshaw | first1 = L. | s2cid = 31001665}}</ref> उदाहरण के लिए, रैमशॉ के एल्गोरिदम का उपयोग कुछ जावा [[ decompiler |डीकंपाइलर]] में किया गया था क्योंकि [[जावा वर्चुअल मशीन]] कोड में ऑफसेट के रूप में व्यक्त लक्ष्यों के साथ शाखन निर्देश होते हैं, परन्तु मल्टी-लेवल जावा लैंग्वेज में मात्र मल्टी-लेवल <code>break</code> और <code>continue</code> स्टेटमेंट होते हैं।<ref name="Nolan2004">{{cite book|author=Godfrey Nolan|title=जावा को विघटित करना|year=2004|publisher=Apress|isbn=978-1-4302-0739-9|page=142}}</ref><ref>https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf {{Bare URL PDF|date=March 2022}}</ref><ref>http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf {{Bare URL PDF|date=March 2022}}</ref> इस प्रकार से अम्मरगुएलाट (1992) ने परिवर्तन विधि प्रस्तावित की जो एकल-निकास को लागू करने पर आधारित है।<ref name="amma92">{{cite journal | doi = 10.1109/32.126773 | title=एक नियंत्रण-प्रवाह सामान्यीकरण एल्गोरिदम और इसकी जटिलता| journal=IEEE Transactions on Software Engineering | date=1992 | volume=18 | issue=3 | pages=237–251 | first=Z. | last=Ammarguellat}}</ref> | |||
==कोबोल पर अनुप्रयोग== | ==कोबोल पर अनुप्रयोग== | ||
1980 के दशक में [[IBM]] के शोधकर्ता [[हरलान मिल्स]] ने [[COBOL]] | अतः 1980 के दशक में [[IBM|आईबीएम]] के शोधकर्ता [[हरलान मिल्स]] ने [[COBOL|कोबोल]] संरचना सुविधा के विकास का निरीक्षण किया, जिसने कोबोल कोड के लिए संरचना एल्गोरिदम लागू किया। इस प्रकार से मिल्स के परिवर्तन में प्रत्येक प्रक्रिया के लिए निम्नलिखित चरण सम्मिलित थे। | ||
#प्रक्रिया में [[बुनियादी ब्लॉक]] | #प्रक्रिया में [[बुनियादी ब्लॉक|बेसिक ब्लॉक]] की पहचान करें। | ||
#प्रत्येक ब्लॉक के प्रवेश पथ के लिए अद्वितीय [[लेबल (प्रोग्रामिंग भाषा)]] निर्दिष्ट करें, और प्रत्येक ब्लॉक के निकास पथों को उन प्रवेश पथों के लेबल के साथ लेबल करें जिनसे वे जुड़ते हैं। प्रक्रिया से वापसी के लिए 0 और प्रक्रिया के प्रवेश पथ के लिए 1 का उपयोग करें। | #प्रत्येक ब्लॉक के प्रवेश पथ के लिए अद्वितीय [[लेबल (प्रोग्रामिंग भाषा)|लेबल (प्रोग्रामिंग लैंग्वेज)]] निर्दिष्ट करें, और प्रत्येक ब्लॉक के निकास पथों को उन प्रवेश पथों के लेबल के साथ लेबल करें जिनसे वे जुड़ते हैं। प्रक्रिया से वापसी के लिए 0 और प्रक्रिया के प्रवेश पथ के लिए 1 का उपयोग करें। | ||
#प्रक्रिया को उसके मूल खंडों में विभाजित करें। | #प्रक्रिया को उसके मूल खंडों में विभाजित करें। | ||
#प्रत्येक ब्लॉक के लिए जो | #प्रत्येक ब्लॉक के लिए जो मात्र निकास पथ का गंतव्य है, उस ब्लॉक को उस निकास पथ से पुनः संयोजित करें। | ||
#प्रक्रिया में | #प्रक्रिया में नवीन चर घोषित करें (संदर्भ के लिए L कहा जाता है)। | ||
# प्रत्येक शेष असंबद्ध निकास पथ पर, | # प्रत्येक शेष असंबद्ध निकास पथ पर, स्टेटमेंट जोड़ें जो उस पथ पर लेबल मान पर L सेट करता है। | ||
#परिणामी प्रोग्रामों को चयन विवरण में संयोजित करें जो प्रोग्राम को | #परिणामी प्रोग्रामों को चयन विवरण में संयोजित करें जो प्रोग्राम को L द्वारा इंगित प्रवेश पथ लेबल के साथ निष्पादित करता है | ||
# एक लूप बनाएं जो इस चयन | # एक लूप बनाएं जो इस चयन स्टेटमेंट को तब तक निष्पादित करे जब तक L 0 न हो। | ||
# एक अनुक्रम का निर्माण करें जो L से 1 आरंभ करता है और लूप निष्पादित करता है। | # एक अनुक्रम का निर्माण करें जो L से 1 आरंभ करता है और लूप निष्पादित करता है। | ||
ध्यान दें कि चयन विवरण के कुछ | इस प्रकार से ध्यान दें कि चयन विवरण के कुछ स्थितियों को उपप्रक्रियाओं में परिवर्तित करके इस निर्माण में सुधार किया जा सकता है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
| Line 101: | Line 105: | ||
==संदर्भ== | ==संदर्भ== | ||
{{Reflist}} | {{Reflist}} | ||
==अग्रिम पठन== | ==अग्रिम पठन== | ||
| Line 107: | Line 110: | ||
* {{cite journal | doi = 10.1145/322169.322180 | title=Space-Time Trade-Offs in Structured Programming: An Improved Combinatorial Embedding Theorem | journal=Journal of the ACM | date=1980 | volume=27 | issue=1 | pages=123–127 | first=Richard A. | last=DeMillo| s2cid=15669719 | doi-access=free }} | * {{cite journal | doi = 10.1145/322169.322180 | title=Space-Time Trade-Offs in Structured Programming: An Improved Combinatorial Embedding Theorem | journal=Journal of the ACM | date=1980 | volume=27 | issue=1 | pages=123–127 | first=Richard A. | last=DeMillo| s2cid=15669719 | doi-access=free }} | ||
* {{cite book | doi = 10.1007/3-540-57785-8_128 | chapter=One binary horn clause is enough | volume=775 | date=1994 | pages=19–32 | first=Philippe | last=Devienne| title=Stacs 94 | series=Lecture Notes in Computer Science | isbn=978-3-540-57785-0 | citeseerx=10.1.1.14.537 }} | * {{cite book | doi = 10.1007/3-540-57785-8_128 | chapter=One binary horn clause is enough | volume=775 | date=1994 | pages=19–32 | first=Philippe | last=Devienne| title=Stacs 94 | series=Lecture Notes in Computer Science | isbn=978-3-540-57785-0 | citeseerx=10.1.1.14.537 }} | ||
[[Category: | [[Category:All articles with bare URLs for citations]] | ||
[[Category:Articles with PDF format bare URLs for citations]] | |||
[[Category:Articles with bare URLs for citations from March 2022]] | |||
[[Category:Created On 25/07/2023]] | [[Category:Created On 25/07/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Short description with empty Wikidata description]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:कम्प्यूटेशनल जटिलता सिद्धांत में प्रमेय]] | |||
[[Category:गणना के मॉडल]] | |||
[[Category:प्रोग्रामिंग भाषा सिद्धांत]] | |||
Latest revision as of 14:00, 14 August 2023
संरचित प्रोग्राम प्रमेय, जिसे बोहम-जैकोपिनी की प्रमेय भी कहा जाता है,[1][2] प्रोग्रामिंग लैंग्वेज सिद्धांत का एक परिणाम है। इसमें कहा गया है कि कंट्रोल-फ्लो ग्राफ का वर्ग (ऐतिहासिक रूप से इस संदर्भ में फ्लो संचित्र कहा जाता है) किसी भी गणना योग्य संक्रिया की गणना कर सकता है यदि यह उपप्रोग्राम को मात्र तीन विशिष्ट विधियों (कंट्रोल संरचनाओं) में जोड़ता है। ये इस प्रकार निम्नलिखित हैं-
- एक उपप्रोग्राम निष्पादित करना, और फिर दूसरा उपप्रोग्राम (अनुक्रम)।
- बूलियन डेटा प्रकार अभिव्यक्ति (चयन) के मान के अनुसार दो उपप्रोग्रामों में से को निष्पादित करना।
- जब तक बूलियन अभिव्यक्ति सत्य है तब तक उपप्रोग्राम को बार-बार निष्पादित करना (पुनरावृत्ति)।
इन बाधाओं के अधीन संरचित चार्ट, विशेष रूप से एकल निकास (जैसा कि इस लेख में बाद में वर्णित है) के लिए लूप बाधा, यद्यपि सूचना का ट्रैक रखने के लिए बिट्स के रूप में अतिरिक्त चर का उपयोग कर सकता है (मूल प्रमाण में अतिरिक्त पूर्णांक चर में संग्रहीत) जो मूल प्रोग्राम प्रोग्राम स्थान द्वारा प्रस्तुत करता है। इस प्रकार से निर्माण बोहम की प्रोग्रामिंग लैंग्वेज P' पर आधारित था।
अतः प्रमेय संरचित प्रोग्रामिंग का आधार बनाता है, प्रोग्रामिंग प्रतिमान जो गोटो कमांड से बचता है, और विशेष रूप से प्रक्रिया, अनुक्रम, चयन और पुनरावृत्ति का उपयोग करता है।
उत्पत्ति और प्रकार
प्रमेय का श्रेय सामान्यतः[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] इस प्रकार से कोसाराजू ब्लिस प्रोग्रामिंग लैंग्वेज में बहु-स्तरीय ब्रेक निर्माण का उद्धृत कर देते हैं। अतः बहु-स्तरीय ब्रेक, leave label कीवर्ड के रूप में, वस्तुतः उस लैंग्वेज के ब्लिस-11 संस्करण में प्रस्तुत किए गए थे; मूल ब्लिस में मात्र एकल-स्तरीय ब्रेक थे। लैंग्वेज के ब्लिस वर्ग ने अप्रतिबंधित गोटो प्रदान नहीं किया। जावा (प्रोग्रामिंग लैंग्वेज) भी बाद में इसी दृष्टिकोण का अनुसरण करेगी।[16]: 960–965
इस प्रकार से कोसाराजू के लेख से सरल परिणाम यह है कि प्रोग्राम संरचित प्रोग्राम (वैरिएबल जोड़े बिना) में कम किया जा सकता है यदि और मात्र तभी इसमें दो अलग-अलग निकास के साथ लूप सम्मिलित नहीं है। अतः समानेयता को कोसाराजू द्वारा परिभाषित किया गया था, साधारणतया, एक ही संक्रिया की गणना करने और मूल प्रोग्राम के रूप में समान आदिम क्रियाओं और विशेषण का उपयोग करने के रूप में, परन्तु संभवतः विभिन्न कंट्रोल फ्लो संरचनाओं का उपयोग करते हुए। (यह बोहम-जैकोपिनी द्वारा उपयोग की जाने वाली समानेयता की तुलना में संकीर्ण धारणा है।) इस परिणाम से प्रेरित होकर, अपने अत्यधिक उद्धृत लेख के खंड VI में, जिसने चक्रीय जटिलता की धारणा प्रस्तुत की, थॉमस जे. मैककेबे ने गैर-संरचित प्रोग्रामों के कंट्रोल-फ्लो ग्राफ़ (सीएफजी) के लिए कुराटोस्की के प्रमेय के एनालॉग का वर्णन किया, जिसका अर्थ है, न्यूनतम उपग्राफ जो किसी कार्यक्रम के सीएफजी को गैर-संरचित बनाते हैं। इन उपसमूहों का प्राकृतिक लैंग्वेज में बहुत अच्छा वर्णन है। इस प्रकार से वे निम्नलिखित हैं:
- लूप से शाखन निकलना (लूप चक्र परीक्षण के अतिरिक्त)।
- एक लूप में शाखनबद्ध होना।
- किसी निर्णय में शाखन लगाना (अर्थात यदि शाखन में)।
- किसी निर्णय से बाहर निकलना।
अतः मैककेबे ने वस्तुतः पाया कि उपग्राफ के रूप में प्रदर्शित होने पर ये चार ग्राफ स्वतंत्र नहीं होते हैं, जिसका अर्थ है कि किसी प्रोग्राम के गैर-संरचित होने के लिए आवश्यक और पर्याप्त प्रतिबन्ध यह है कि इसके सीएफजी में इन चार ग्राफ में से तीन में से किसी उपसमूह में से उपग्राफ के रूप में होना चाहिए। इस प्रकार से उन्होंने यह भी पाया कि यदि किसी गैर-संरचित प्रोग्राम में इन चार उप-ग्राफ़ों में से सम्मिलित है, तो इसमें चार के सेट से और अलग होना चाहिए। यह बाद वाला परिणाम यह समझाने में सहायता करता है कि कैसे गैर-संरचित प्रोग्राम का कंट्रोल फ्लो लोकप्रिय रूप से स्पेगेटी कोड कहे जाने वाले जटिल हो जाता है। अतः मैककेबे ने संख्यात्मक माप भी तैयार किया, जो यादृच्छिक प्रोग्राम को देखते हुए, यह निर्धारित करता है कि यह संरचित प्रोग्राम होने के आदर्श से कितनी दूर है; मैककेबे ने अपने माप को आवश्यक जटिलता (संरचनात्मकता का संख्यात्मक माप) कहा।[17]
इस प्रकार से संरचित प्रोग्रामिंग के लिए निषिद्ध ग्राफ के मैककेब के लक्षण वर्णन को अधूरा माना जा सकता है, कम से कम यदि दिज्क्स्ट्रा की डी संरचनाओं को बिल्डिंग ब्लॉक माना जाता है।[18]: 274–275
अतः 1990 तक वर्तमान प्रोग्रामों से "गोटो" को हटाने के लिए, उनकी अधिकांश संरचना को संरक्षित करते हुए, कई प्रस्तावित विधि थे। इस प्रकार से इस समस्या के विभिन्न दृष्टिकोणों ने समतुल्यता की कई धारणाएँ भी प्रस्तावित कीं थी, जो ऊपर चर्चा किए गए फोक प्रमेय जैसे आउटपुट से बचने के लिए, मात्र ट्यूरिंग समतुल्यता से अधिक जटिल हैं। समतुल्यता की चुनी गई धारणा की जटिलता आवश्यक कंट्रोल फ्लो संरचनाओं के न्यूनतम सेट को निर्धारित करती है। अतः लाइल रामशॉ द्वारा 1988 का जेएसीएम लेख उस बिंदु तक क्षेत्र का सर्वेक्षण करता है, साथ ही अपनी विधि का प्रस्ताव भी करता है।[19] उदाहरण के लिए, रैमशॉ के एल्गोरिदम का उपयोग कुछ जावा डीकंपाइलर में किया गया था क्योंकि जावा वर्चुअल मशीन कोड में ऑफसेट के रूप में व्यक्त लक्ष्यों के साथ शाखन निर्देश होते हैं, परन्तु मल्टी-लेवल जावा लैंग्वेज में मात्र मल्टी-लेवल break और continue स्टेटमेंट होते हैं।[20][21][22] इस प्रकार से अम्मरगुएलाट (1992) ने परिवर्तन विधि प्रस्तावित की जो एकल-निकास को लागू करने पर आधारित है।[8]
कोबोल पर अनुप्रयोग
अतः 1980 के दशक में आईबीएम के शोधकर्ता हरलान मिल्स ने कोबोल संरचना सुविधा के विकास का निरीक्षण किया, जिसने कोबोल कोड के लिए संरचना एल्गोरिदम लागू किया। इस प्रकार से मिल्स के परिवर्तन में प्रत्येक प्रक्रिया के लिए निम्नलिखित चरण सम्मिलित थे।
- प्रक्रिया में बेसिक ब्लॉक की पहचान करें।
- प्रत्येक ब्लॉक के प्रवेश पथ के लिए अद्वितीय लेबल (प्रोग्रामिंग लैंग्वेज) निर्दिष्ट करें, और प्रत्येक ब्लॉक के निकास पथों को उन प्रवेश पथों के लेबल के साथ लेबल करें जिनसे वे जुड़ते हैं। प्रक्रिया से वापसी के लिए 0 और प्रक्रिया के प्रवेश पथ के लिए 1 का उपयोग करें।
- प्रक्रिया को उसके मूल खंडों में विभाजित करें।
- प्रत्येक ब्लॉक के लिए जो मात्र निकास पथ का गंतव्य है, उस ब्लॉक को उस निकास पथ से पुनः संयोजित करें।
- प्रक्रिया में नवीन चर घोषित करें (संदर्भ के लिए L कहा जाता है)।
- प्रत्येक शेष असंबद्ध निकास पथ पर, स्टेटमेंट जोड़ें जो उस पथ पर लेबल मान पर L सेट करता है।
- परिणामी प्रोग्रामों को चयन विवरण में संयोजित करें जो प्रोग्राम को L द्वारा इंगित प्रवेश पथ लेबल के साथ निष्पादित करता है
- एक लूप बनाएं जो इस चयन स्टेटमेंट को तब तक निष्पादित करे जब तक L 0 न हो।
- एक अनुक्रम का निर्माण करें जो L से 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) - ↑ "CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM". Cse.buffalo.edu. 2004-11-22. Retrieved 2013-08-24.
- ↑ 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.
- ↑ 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.
- ↑ 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
- ↑ 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.
- ↑ Bruce Ian Mills (2005). प्रोग्रामिंग का सैद्धांतिक परिचय. Springer. p. 279. ISBN 978-1-84628-263-8.
- ↑ 8.0 8.1 Ammarguellat, Z. (1992). "एक नियंत्रण-प्रवाह सामान्यीकरण एल्गोरिदम और इसकी जटिलता". IEEE Transactions on Software Engineering. 18 (3): 237–251. doi:10.1109/32.126773.
- ↑ 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.0 10.1 Roberts, E. [1995] "Loop Exits and Structured Programming: Reopening the Debate," ACM SIGCSE Bulletin, (27)1: 268–272.
- ↑ E. N. Yourdon (1979). सॉफ्टवेयर इंजीनियरिंग में क्लासिक्स. Yourdon Press. pp. 49–50. ISBN 978-0-917072-14-7.
- ↑ 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
- ↑ David Anthony Watt; William Findlay (2004). प्रोग्रामिंग भाषा डिज़ाइन अवधारणाएँ. John Wiley & Sons. p. 228. ISBN 978-0-470-85320-7.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ Williams, M. H. (1983). "फ़्लोचार्ट स्कीमाटा और नामकरण की समस्या". The Computer Journal. 26 (3): 270–276. doi:10.1093/comjnl/26.3.270.
- ↑ Ramshaw, L. (1988). "प्रोग्राम संरचना को संरक्षित करते हुए गो को हटाना". Journal of the ACM. 35 (4): 893–920. doi:10.1145/48014.48021. S2CID 31001665.
- ↑ Godfrey Nolan (2004). जावा को विघटित करना. Apress. p. 142. ISBN 978-1-4302-0739-9.
- ↑ https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf[bare URL PDF]
- ↑ http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf[bare URL PDF]
अग्रिम पठन
Material not yet covered above:
- DeMillo, Richard A. (1980). "Space-Time Trade-Offs in Structured Programming: An Improved Combinatorial Embedding Theorem". Journal of the ACM. 27 (1): 123–127. doi:10.1145/322169.322180. S2CID 15669719.
- Devienne, Philippe (1994). "One binary horn clause is enough". Stacs 94. Lecture Notes in Computer Science. Vol. 775. pp. 19–32. CiteSeerX 10.1.1.14.537. doi:10.1007/3-540-57785-8_128. ISBN 978-3-540-57785-0.
