निश्चित असाइनमेंट विश्लेषण: Difference between revisions

From Vigyanwiki
No edit summary
 
(9 intermediate revisions by 3 users not shown)
Line 5: Line 5:


इस समस्या को हल करने के दो सामान्य तरीके हैं। एक यह सुनिश्चित करना है कि सभी स्थानों को पढ़ने से पहले लिखा गया हो। राइस की प्रमेय स्थापित करती है कि इस समस्या को सामान्य रूप से सभी कार्यक्रमों के लिए हल नहीं किया जा सकता है; हालाँकि, एक अपरिवर्तनवादी (अशुद्ध) विश्लेषण बनाना संभव है जो केवल उन कार्यक्रमों को स्वीकार करेगा जो इस बाधा को संतुष्ट करते हैं, जबकि कुछ सही कार्यक्रमों को अस्वीकार करते हैं, और निश्चित कार्यभार विश्लेषण ऐसा विश्लेषण है जो[[जावा प्रोग्रामिंग भाषा]]<ref>{{cite web |author1=J. Gosling |author2=B. Joy |author3=G. Steele |author4=G. Bracha | title = The Java Language Specification, 3rd Edition | url= http://java.sun.com/docs/books/jls/third_edition/html/defAssign.html | accessdate = December 2, 2008 | pages = Chapter 16 (pp.527&ndash;552)}}</ref> और सी शार्प (प्रोग्रामिंग भाषा)|सी#<ref>{{cite web | title = Standard ECMA-334, C# Language Specification | work = ECMA International | url = http://www.ecma-international.org/publications/standards/Ecma-334.htm | accessdate = December 2, 2008 | pages = Section 12.3 (pp.122&ndash;133)}}</ref> प्रोग्रामिंग भाषा विनिर्देशों के लिए आवश्यक है कि विश्लेषण विफल होने पर संकलक एक संकलन-समय त्रुटि की प्रतिवेदन करे। दोनों भाषाओं को विश्लेषण के एक विशिष्ट रूप की आवश्यकता होती है जिसे सावधानीपूर्वक विस्तार से लिखा गया है। जावा में, इस विश्लेषण को स्टार्क एट अल द्वारा औपचारिक रूप दिया गया था।<ref>{{cite book |title=Java and the Java Virtual Machine: Definition, Verification, Validation |last=Stärk |first=Robert F. |author2=E. Borger |author3=Joachim Schmid  |year=2001 |publisher=Springer-Verlag New York, Inc. |location=Secaucus, NJ, USA |isbn=3-540-42088-6 |pages=Section 8.3}}</ref> और कुछ सही कार्यक्रमों को अस्वीकार कर दिया गया है और स्पष्ट अनावश्यक कार्यभार पेश करने के लिए उन्हें बदला जाना चाहिए। सी # में, इस विश्लेषण को फ्रुजा द्वारा औपचारिक रूप दिया गया था, और यह  सही होने के साथ-साथ आवाज़ भी है, इस अर्थ में कि सभी नियंत्रण प्रवाह पथों के साथ निर्दिष्ट सभी चर निश्चित रूप से निर्दिष्ट माने जाएंगे।<ref name="fruja">{{cite journal |doi=10.5381/jot.2004.3.9.a2 |last=Fruja |first=Nicu G. |date=October 2004|title=The Correctness of the Definite Assignment Analysis in C# |journal=Journal of Object Technology |volume=3 |issue=9 |pages=29&ndash;52 |url=http://www.jot.fm/issues/issue_2004_10/article2 |accessdate=2008-12-02 | quote=We actually prove more than correctness: we show that the solution of the analysis is a perfect solution (and not only a safe approximation).|citeseerx=10.1.1.165.6696 }}</ref> [[चक्रवात (प्रोग्रामिंग भाषा)]]  भाषा को को एक निश्चित कार्यभार विश्लेषण पास करने के लिए प्रोग्राम की भी आवश्यकता होती है, लेकिन सी प्रोग्राम के पोर्टिंग को आसान बनाने के लिए केवल सूचक प्रकार वाले चर की आवश्यकता होती है।<ref>{{cite web | title = Cyclone: Definite Assignment | work = Cyclone User's Manual | url = http://cyclone.thelanguage.org/wiki/Definite%20Assignment | accessdate = December 16, 2008 }}</ref>
इस समस्या को हल करने के दो सामान्य तरीके हैं। एक यह सुनिश्चित करना है कि सभी स्थानों को पढ़ने से पहले लिखा गया हो। राइस की प्रमेय स्थापित करती है कि इस समस्या को सामान्य रूप से सभी कार्यक्रमों के लिए हल नहीं किया जा सकता है; हालाँकि, एक अपरिवर्तनवादी (अशुद्ध) विश्लेषण बनाना संभव है जो केवल उन कार्यक्रमों को स्वीकार करेगा जो इस बाधा को संतुष्ट करते हैं, जबकि कुछ सही कार्यक्रमों को अस्वीकार करते हैं, और निश्चित कार्यभार विश्लेषण ऐसा विश्लेषण है जो[[जावा प्रोग्रामिंग भाषा]]<ref>{{cite web |author1=J. Gosling |author2=B. Joy |author3=G. Steele |author4=G. Bracha | title = The Java Language Specification, 3rd Edition | url= http://java.sun.com/docs/books/jls/third_edition/html/defAssign.html | accessdate = December 2, 2008 | pages = Chapter 16 (pp.527&ndash;552)}}</ref> और सी शार्प (प्रोग्रामिंग भाषा)|सी#<ref>{{cite web | title = Standard ECMA-334, C# Language Specification | work = ECMA International | url = http://www.ecma-international.org/publications/standards/Ecma-334.htm | accessdate = December 2, 2008 | pages = Section 12.3 (pp.122&ndash;133)}}</ref> प्रोग्रामिंग भाषा विनिर्देशों के लिए आवश्यक है कि विश्लेषण विफल होने पर संकलक एक संकलन-समय त्रुटि की प्रतिवेदन करे। दोनों भाषाओं को विश्लेषण के एक विशिष्ट रूप की आवश्यकता होती है जिसे सावधानीपूर्वक विस्तार से लिखा गया है। जावा में, इस विश्लेषण को स्टार्क एट अल द्वारा औपचारिक रूप दिया गया था।<ref>{{cite book |title=Java and the Java Virtual Machine: Definition, Verification, Validation |last=Stärk |first=Robert F. |author2=E. Borger |author3=Joachim Schmid  |year=2001 |publisher=Springer-Verlag New York, Inc. |location=Secaucus, NJ, USA |isbn=3-540-42088-6 |pages=Section 8.3}}</ref> और कुछ सही कार्यक्रमों को अस्वीकार कर दिया गया है और स्पष्ट अनावश्यक कार्यभार पेश करने के लिए उन्हें बदला जाना चाहिए। सी # में, इस विश्लेषण को फ्रुजा द्वारा औपचारिक रूप दिया गया था, और यह  सही होने के साथ-साथ आवाज़ भी है, इस अर्थ में कि सभी नियंत्रण प्रवाह पथों के साथ निर्दिष्ट सभी चर निश्चित रूप से निर्दिष्ट माने जाएंगे।<ref name="fruja">{{cite journal |doi=10.5381/jot.2004.3.9.a2 |last=Fruja |first=Nicu G. |date=October 2004|title=The Correctness of the Definite Assignment Analysis in C# |journal=Journal of Object Technology |volume=3 |issue=9 |pages=29&ndash;52 |url=http://www.jot.fm/issues/issue_2004_10/article2 |accessdate=2008-12-02 | quote=We actually prove more than correctness: we show that the solution of the analysis is a perfect solution (and not only a safe approximation).|citeseerx=10.1.1.165.6696 }}</ref> [[चक्रवात (प्रोग्रामिंग भाषा)]]  भाषा को को एक निश्चित कार्यभार विश्लेषण पास करने के लिए प्रोग्राम की भी आवश्यकता होती है, लेकिन सी प्रोग्राम के पोर्टिंग को आसान बनाने के लिए केवल सूचक प्रकार वाले चर की आवश्यकता होती है।<ref>{{cite web | title = Cyclone: Definite Assignment | work = Cyclone User's Manual | url = http://cyclone.thelanguage.org/wiki/Definite%20Assignment | accessdate = December 16, 2008 }}</ref>
समस्या को हल करने का दूसरा तरीका सभी स्थानों को स्वचालित रूप से कुछ निश्चित, पूर्वानुमेय मूल्य पर उस बिंदु पर प्रारंभ करना है जिस पर उन्हें परिभाषित किया गया है, लेकिन यह नए असाइनमेंट पेश करता है जो प्रदर्शन को बाधित कर सकते हैं। इस मामले में, निश्चित असाइनमेंट विश्लेषण एक [[संकलक अनुकूलन]] को सक्षम करता है जहां अनावश्यक असाइनमेंट - असाइनमेंट केवल अन्य असाइनमेंट के बाद बिना किसी संभावित हस्तक्षेप के पढ़ता है - समाप्त किया जा सकता है। इस मामले में, कोई कार्यक्रम अस्वीकार नहीं किया जाता है, लेकिन जिन कार्यक्रमों के लिए विश्लेषण निश्चित असाइनमेंट को पहचानने में विफल रहता है, उनमें अनावश्यक आरंभीकरण हो सकता है। [[सामान्य भाषा अवसंरचना]] इस दृष्टिकोण पर निर्भर करता है।<ref>{{cite web | title = Standard ECMA-335, Common Language Infrastructure (CLI) | work = ECMA International | url = http://www.ecma-international.org/publications/standards/Ecma-335.htm | accessdate = December 2, 2008 | pages=Section 1.8.1.1 (Partition III, pg. 19)}}</ref>
समस्या को हल करने का दूसरा तरीका सभी स्थानों को स्वचालित रूप से कुछ निश्चित, पूर्वानुमेय रूप से मूल्य पर उस बिंदु पर प्रारंभ करना है जिस पर उन्हें परिभाषित किया गया है, लेकिन यह नए कार्यभार पेश करता है जो प्रदर्शन को बाधित कर सकते हैं। इस मामले में, निश्चित कार्यभार विश्लेषण एक [[संकलक अनुकूलन]] को सक्षम करता है जहां अनावश्यक कार्यभार केवल अन्य कार्यभार के बाद बिना किसी संभावित हस्तक्षेप के पढ़े जाते हैं और समाप्त किये जाते है। इस मामले में, किसी भी कार्यक्रम को अस्वीकार नहीं किया जाता है, लेकिन जिन कार्यक्रमों के लिए विश्लेषण निश्चित कार्यभा को पहचानने में विफल रहता है, उनमें अनावश्यक आरंभीकरण हो सकता है। [[सामान्य भाषा अवसंरचना]] इस दृष्टिकोण पर निर्भर करती है।<ref>{{cite web | title = Standard ECMA-335, Common Language Infrastructure (CLI) | work = ECMA International | url = http://www.ecma-international.org/publications/standards/Ecma-335.htm | accessdate = December 2, 2008 | pages=Section 1.8.1.1 (Partition III, pg. 19)}}</ref>




== शब्दावली ==
== शब्दावली ==
कार्यक्रम में किसी दिए गए बिंदु पर एक चर या स्थान को तीन राज्यों में से एक में कहा जा सकता है:
एक चर या स्थान को कार्यक्रम में किसी भी बिंदु पर तीन राज्यों में से एक में कहा जा सकता है:


* निश्चित रूप से असाइन किया गया: वेरिएबल निश्चित रूप से असाइन किए जाने के लिए जाना जाता है।
* निश्चित रूप से निरुपित किया गया: चर निश्चित रूप से निरुपित किए जाने के लिए जाना जाता है।
* निश्चित रूप से असाइन नहीं किया गया: वेरिएबल निश्चित रूप से असाइन किए जाने के लिए जाना जाता है।
* निश्चित रूप से निरुपित नहीं किया गया: चर निश्चित रूप से निरुपित किए जाने के लिए जाना जाता है।
* अज्ञात: चर असाइन या असाइन नहीं किया जा सकता है; विश्लेषण यह निर्धारित करने के लिए पर्याप्त सटीक नहीं है कि कौन सा।
* अज्ञात: चर निरुपित नहीं किया जा सकता है; विश्लेषण यह निर्धारित करने के लिए पर्याप्त सही नहीं है।


== विश्लेषण ==
== विश्लेषण ==
निम्नलिखित सी # इंट्राप्रोसेडुरल (एकल विधि) निश्चित असाइनमेंट विश्लेषण के फ्रूजा की औपचारिकता पर आधारित है, जो यह सुनिश्चित करने के लिए ज़िम्मेदार है कि सभी स्थानीय चरों का उपयोग करने से पहले उन्हें असाइन किया गया है।<ref name="fruja"/>यह एक साथ निश्चित असाइनमेंट विश्लेषण और बूलियन मूल्यों का [[निरंतर प्रसार]] करता है। हम पाँच स्थैतिक कार्यों को परिभाषित करते हैं:
निम्नलिखित C# अंतःक्रियात्मक (एकल विधि) निश्चित कार्यभार विश्लेषण के फ्रूजा की औपचारिकता पर आधारित है, जो यह सुनिश्चित करने के लिए ज़िम्मेदार है कि सभी स्थानीय चरों का उपयोग करने से पहले उन्हें निरुपित किया गया है।<ref name="fruja"/>यह एक साथ निश्चित कार्यभार विश्लेषण और बूलियन मूल्यों का [[निरंतर प्रसार]] करता है। हम पाँच स्थिर कार्यों को परिभाषित करते हैं:


{|class="wikitable"
{|class="wikitable"
!Name!!Domain!!Description
!Name!!Domain!!Description
|-
|-
|''before'' || All statements and expressions || Variables definitely assigned before the evaluation of the given statement or expression.
|''पहले'' || सभी कथन और भाव। || दिए गए कथन या अभिव्यक्ति के मूल्यांकन से पहले चर निश्चित रूप से निर्दिष्ट किए जाते हैं।
|-
|-
|''after'' || All statements and expressions || Variables definitely assigned after the evaluation of the given statement or expression, assuming it completes normally.
|''बाद'' || सभी कथन और भाव। || दिए गए कथन या अभिव्यक्ति के मूल्यांकन के बाद चर निश्चित रूप से निरुपित किए जाते हैं, यह मानते हुए कि यह सामान्य रूप से पूरा होता है।
|-
|-
|''vars'' || All statements and expressions || All variables available in the scope of the given statement or expression.
|''संस्करण'' || सभी कथन और भाव। || दिए गए बयान या अभिव्यक्ति के दायरे में सभी चर उपलब्ध हैं।
|-
|-
|''true'' || All boolean expressions || Variables definitely assigned after the evaluation of the given expression, assuming the expression evaluates to '''true'''.
|''सत्य'' || सभी बूलियन अभिव्यक्तियाँ। || दिए गए अभिव्यक्ति के मूल्यांकन के बाद चर को निश्चित रूप से निरुपित किया जाता है, यह मानते हुए कि अभिव्यक्ति का मूल्यांकन '''सही''' है।
|-
|-
|''false'' || All boolean expressions || Variables definitely assigned after the evaluation of the given expression, assuming the expression evaluates to '''false'''.
|''असत्य'' || सभी बूलियन अभिव्यक्तियाँ। || दिए गए अभिव्यक्ति के मूल्यांकन के बाद निश्चित रूप से चर को निरुपित किया जाता है, यह मानते हुए कि अभिव्यक्ति का मूल्यांकन '''गलत''' है।
|}
|}
हम डेटा-प्रवाह समीकरणों की आपूर्ति करते हैं जो इन कार्यों के मूल्यों को उनके सिंटैक्टिक उप-अभिव्यक्तियों पर कार्यों के मूल्यों के संदर्भ में, विभिन्न अभिव्यक्तियों और बयानों पर परिभाषित करते हैं। इस क्षण के लिए मान लें कि कोई गोटो, ब्रेक, जारी, रिटर्न या अपवाद हैंडलिंग स्टेटमेंट नहीं हैं। इन समीकरणों के कुछ उदाहरण निम्नलिखित हैं:
हम डेटा-प्रवाह समीकरणों की आपूर्ति करते हैं जो इन कार्यों के मूल्यों को उनके वाक्य-विन्यास उप-अभिव्यक्तियों पर कार्यों के मूल्यों के संदर्भ में, विभिन्न अभिव्यक्तियों और बयानों पर परिभाषित करते हैं। इस क्षण के लिए मान लें कि कोई गोटो, ब्रेक, जारी, वापसी या अपवाद प्रबंधन कथन नहीं हैं। इन समीकरणों के कुछ उदाहरण निम्नलिखित हैं:


* कोई भी अभिव्यक्ति या बयान ई जो निश्चित रूप से असाइन किए गए चर के सेट को प्रभावित नहीं करता है: के बाद (ई) = पहले (ई)
* कोई भी अभिव्यक्ति या कथन ई जो निश्चित रूप से असाइन किए गए चर के सेट को प्रभावित नहीं करता है: बाद (e) = पहले (e)
* ई को असाइनमेंट एक्सप्रेशन loc = v होने दें। फिर पहले (v) = पहले (ई), और बाद में (ई) = के बाद (v) यू {लोक}।
* ई को असाइनमेंट एक्सप्रेशन लोक = वी होने दें। फिर पहले (v) = पहले (e), और बाद में (e) = के बाद (v) U {loc}।
* आइए अभिव्यक्ति 'सत्य' बनें। फिर सच (ई) = पहले (ई) और झूठा (ई) = संस्करण (ई)। दूसरे शब्दों में, यदि ई 'गलत' का मूल्यांकन करता है, तो सभी चर (रिक्त सत्य) निश्चित रूप से निर्दिष्ट होते हैं, क्योंकि ई गलत का मूल्यांकन नहीं करता है।
* आइए अभिव्यक्ति ''''सत्य'''<nowiki/>' बनें। फिर सच (e) = पहले (e) और झूठा (e) = संस्करण (e)। दूसरे शब्दों में, यदि ई ''''गलत'''<nowiki/>' का मूल्यांकन करता है, तो सभी चर (रिक्त सत्य) निश्चित रूप से निर्दिष्ट होते हैं, क्योंकि ई गलत का मूल्यांकन नहीं करता है।
* चूँकि विधि तर्कों का मूल्यांकन बाएँ से दाएँ किया जाता है, इससे पहले (arg<sub>''i''&nbsp;+&nbsp;1</sub>) = के बाद (तर्क<sub>''i''</sub>). एक विधि पूर्ण होने के बाद, आउट पैरामीटर निश्चित रूप से असाइन किए जाते हैं।
* चूँकि विधि तर्कों का मूल्यांकन बाएँ से दाएँ किया जाता है, इससे पहले (arg<sub>''i''&nbsp;+&nbsp;1</sub>) = के बाद (तर्क<sub>''i''</sub>). एक विधि पूर्ण होने के बाद, आउट पैरामीटर निश्चित रूप से असाइन किए जाते हैं।
* चलो सशर्त बयान 'अगर' (ई) एस हो<sub>1</sub> और ''स''<sub>2</sub>. फिर पहले (ई) = पहले (एस), पहले (एस<sub>1</sub>) = सच (ई), पहले (एस<sub>2</sub>) = झूठा (ई), और उसके बाद (एस) = के बाद (एस<sub>1</sub>) के बाद प्रतिच्छेद करें (एस<sub>2</sub>).
* चलो सशर्त बयान 'अगर' (ई) s<sub>1</sub> और ''s''<sub>2</sub>. फिर पहले (ई) = पहले (एस), पहले (एस<sub>1</sub>) = सच (ई), पहले (एस<sub>2</sub>) = झूठा (ई), और उसके बाद (एस) = के बाद (एस<sub>1</sub>) के बाद प्रतिच्छेद करें (एस<sub>2</sub>).
* चलो जबकि लूप स्टेटमेंट 'जबकि' (ई) एस<sub>1</sub>. फिर पहले (ई) = पहले (एस), पहले (एस<sub>1</sub>) = सच (ई), और बाद में (एस) = गलत (ई)।
* चलो जबकि लूप स्टेटमेंट 'जबकि' (ई) एस<sub>1</sub>. फिर पहले (ई) = पहले (एस), पहले (एस<sub>1</sub>) = सच (ई), और बाद में (एस) = गलत (ई)।
* और इसी तरह।
* और इसी तरह।


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


गोटो, ब्रेक, कंटीन्यू, रिटर्न और एक्सेप्शन हैंडलिंग जैसे कंट्रोल-फ्लो जंप की शुरुआत से एल्गोरिथ्म जटिल है। कोई भी कथन जो इन छलांगों में से किसी एक का लक्ष्य हो सकता है, उसे कूद स्रोत पर निश्चित रूप से निर्दिष्ट चर के सेट के साथ सेट करने से पहले इसे काटना चाहिए। जब इन्हें पेश किया जाता है, परिणामी डेटा प्रवाह में कई निश्चित बिंदु हो सकते हैं, जैसा कि इस उदाहरण में है:
गोटो, ब्रेक, कंटीन्यू, रिटर्न और एक्सेप्शन हैंडलिंग जैसे कंट्रोल-फ्लो जंप की शुरुआत से एल्गोरिथ्म जटिल है। कोई भी कथन जो इन छलांगों में से किसी एक का लक्ष्य हो सकता है, उसे कूद के स्रोत पर निश्चित रूप से निर्दिष्ट चर के सेट के साथ पहले सेट करना चाहिए। जब इन्हें पेश किया जाता है, तो परिणामी डेटा प्रवाह में कई निश्चित बिंदु हो सकते हैं, जैसा कि इस उदाहरण में है:
<वाक्यविन्यास लैंग = सी लाइन>
<वाक्यविन्यास लैंग = सी लाइन>
  इंट आई = 1;
  इंट आई = 1;
  एल:
  एल:
  गोटो एल;
  गोटो एल;
</वाक्यविन्यास हाइलाइट>
चूँकि लेबल L को दो स्थानों से पहुँचा जा सकता है, गोटो के लिए नियंत्रण-प्रवाह समीकरण यह निर्धारित करता है कि पहले (2) = बाद (1) पहले (3) को काटता है। लेकिन पहले (3) = पहले (2), तो पहले (2) = के बाद (1) पहले (2) को छेड़छाड़ करें। इसमें पहले (2), {i} और खाली सेट के लिए दो नियत बिंदु हैं। हालांकि, यह दिखाया जा सकता है कि डेटा-प्रवाह समीकरणों के मोनोटोनिक रूप के कारण, एक अद्वितीय अधिकतम निश्चित बिंदु (सबसे बड़े आकार का निश्चित बिंदु) होता है जो निश्चित रूप से असाइन किए गए चर के बारे में सबसे अधिक संभव जानकारी प्रदान करता है। इस तरह के अधिकतम (या अधिकतम) निश्चित बिंदु की गणना मानक तकनीकों द्वारा की जा सकती है; डेटा प्रवाह विश्लेषण देखें।
चूँकि लेबल L को दो स्थानों से पहुँचा जा सकता है, गोटो के लिए नियंत्रण-प्रवाह समीकरण तय करता है कि पहले (2) = बाद (1) पहले (3) को काटता है। लेकिन पहले (3) = पहले (2), इसलिए पहले (2) = के बाद (1) पहले (2) प्रतिच्छेद करें। इसमें पहले (2), {i} और खाली सेट के लिए दो निश्चित बिंदु हैं। हालांकि, यह दिखाया जा सकता है कि डेटा-प्रवाह समीकरणों के मोनोटोनिक रूप के कारण, एक अद्वितीय अधिकतम निश्चित बिंदु (सबसे बड़े आकार का निश्चित बिंदु) है जो निश्चित रूप से निर्दिष्ट चर के बारे में सबसे अधिक संभव जानकारी प्रदान करता है। इस तरह के अधिकतम (या अधिकतम) निश्चित बिंदु की गणना मानक तकनीकों द्वारा की जा सकती है; डेटा प्रवाह विश्लेषण देखें।


एक अतिरिक्त मुद्दा यह है कि एक नियंत्रण-प्रवाह कूद कुछ नियंत्रण प्रवाहों को अव्यवहार्य बना सकता है; उदाहरण के लिए, इस कोड खंड में चर i निश्चित रूप से उपयोग किए जाने से पहले असाइन किया गया है:
एक अतिरिक्त मुद्दा यह है कि एक नियंत्रण-प्रवाह कूद कुछ नियंत्रण प्रवाहों को अव्यवहार्य बना सकता है; उदाहरण के लिए, इस कोड खंड में चर i निश्चित रूप से उपयोग किए जाने से पहले निरुपित किया गया है:
<वाक्यविन्यास लैंग = सी लाइन>
  int मैं;
  int मैं;
  अगर (जे <0) वापसी; और मैं = जे;
  अगर (जे <0) वापसी; और मैं = जे;
  प्रिंट (मैं);
  प्रिंट (मैं);
</वाक्यविन्यास हाइलाइट>
यदि के लिए डेटा-फ्लो समीकरण कहता है कि बाद (2) = के बाद (वापसी) के बाद (i = j) प्रतिच्छेद करता है। इस कार्य को सही ढंग से करने के लिए, हम सभी नियंत्रण-प्रवाह कूदों के बाद (e) = संस्करण(e) को परिभाषित करते हैं; यह एक ही अर्थ में रिक्त रूप से मान्य है कि समीकरण गलत (सत्य) = संस्करण (ई) मान्य है, क्योंकि नियंत्रण-प्रवाह कूद के तुरंत बाद नियंत्रण के लिए एक बिंदु तक पहुंचना संभव नहीं है।
if के लिए डेटा-फ्लो समीकरण कहता है कि after(2) = after('return') after(i = j) प्रतिच्छेद करता है। इस कार्य को सही ढंग से करने के लिए, हम सभी नियंत्रण-प्रवाह कूदों के लिए after(e) = var(e) परिभाषित करते हैं; यह उसी अर्थ में रिक्त रूप से मान्य है कि समीकरण false('true') = vars(e) मान्य है, क्योंकि नियंत्रण-प्रवाह कूद के तुरंत बाद नियंत्रण के लिए एक बिंदु तक पहुंचना संभव नहीं है।


==संदर्भ==
==संदर्भ==
<references />
<references />


{{DEFAULTSORT:Definite Assignment Analysis}}[[Category: डेटा प्रवाह विश्लेषण]]
{{DEFAULTSORT:Definite Assignment Analysis}}
 
 


[[Category: Machine Translated Page]]
[[Category:Created On 17/02/2023|Definite Assignment Analysis]]
[[Category:Created On 17/02/2023]]
[[Category:Machine Translated Page|Definite Assignment Analysis]]
[[Category:Templates Vigyan Ready]]
[[Category:डेटा प्रवाह विश्लेषण|Definite Assignment Analysis]]

Latest revision as of 17:27, 3 March 2023

कंप्यूटर विज्ञान में, निश्चित कार्यभार विश्लेषण एक डेटा-प्रवाह विश्लेषण है जिसका उपयोग संकलक द्वारा अपरिवर्तनवादी रूप से यह सुनिश्चित करने के लिए किया जाता है कि उपयोग किए जाने से पहले एक चर या स्थान हमेशा निरुपित किया जाता है।

प्रेरणा

सी प्रोग्रामिंग भाषा और C++ कार्यक्रमों में, विशेष रूप से कठिन-से-निदान त्रुटियों का एक स्रोत गैर-नियतात्मक व्यवहार है, जो कि अस्वीकृति चर पढ़ने के परिणामस्वरूप होता है; यह व्यवहार प्लेटफार्मों, निर्माण और यहां तक ​​कि रन से चलाने के लिए भी भिन्न हो सकता है।

इस समस्या को हल करने के दो सामान्य तरीके हैं। एक यह सुनिश्चित करना है कि सभी स्थानों को पढ़ने से पहले लिखा गया हो। राइस की प्रमेय स्थापित करती है कि इस समस्या को सामान्य रूप से सभी कार्यक्रमों के लिए हल नहीं किया जा सकता है; हालाँकि, एक अपरिवर्तनवादी (अशुद्ध) विश्लेषण बनाना संभव है जो केवल उन कार्यक्रमों को स्वीकार करेगा जो इस बाधा को संतुष्ट करते हैं, जबकि कुछ सही कार्यक्रमों को अस्वीकार करते हैं, और निश्चित कार्यभार विश्लेषण ऐसा विश्लेषण है जोजावा प्रोग्रामिंग भाषा[1] और सी शार्प (प्रोग्रामिंग भाषा)|सी#[2] प्रोग्रामिंग भाषा विनिर्देशों के लिए आवश्यक है कि विश्लेषण विफल होने पर संकलक एक संकलन-समय त्रुटि की प्रतिवेदन करे। दोनों भाषाओं को विश्लेषण के एक विशिष्ट रूप की आवश्यकता होती है जिसे सावधानीपूर्वक विस्तार से लिखा गया है। जावा में, इस विश्लेषण को स्टार्क एट अल द्वारा औपचारिक रूप दिया गया था।[3] और कुछ सही कार्यक्रमों को अस्वीकार कर दिया गया है और स्पष्ट अनावश्यक कार्यभार पेश करने के लिए उन्हें बदला जाना चाहिए। सी # में, इस विश्लेषण को फ्रुजा द्वारा औपचारिक रूप दिया गया था, और यह सही होने के साथ-साथ आवाज़ भी है, इस अर्थ में कि सभी नियंत्रण प्रवाह पथों के साथ निर्दिष्ट सभी चर निश्चित रूप से निर्दिष्ट माने जाएंगे।[4] चक्रवात (प्रोग्रामिंग भाषा) भाषा को को एक निश्चित कार्यभार विश्लेषण पास करने के लिए प्रोग्राम की भी आवश्यकता होती है, लेकिन सी प्रोग्राम के पोर्टिंग को आसान बनाने के लिए केवल सूचक प्रकार वाले चर की आवश्यकता होती है।[5] समस्या को हल करने का दूसरा तरीका सभी स्थानों को स्वचालित रूप से कुछ निश्चित, पूर्वानुमेय रूप से मूल्य पर उस बिंदु पर प्रारंभ करना है जिस पर उन्हें परिभाषित किया गया है, लेकिन यह नए कार्यभार पेश करता है जो प्रदर्शन को बाधित कर सकते हैं। इस मामले में, निश्चित कार्यभार विश्लेषण एक संकलक अनुकूलन को सक्षम करता है जहां अनावश्यक कार्यभार केवल अन्य कार्यभार के बाद बिना किसी संभावित हस्तक्षेप के पढ़े जाते हैं और समाप्त किये जाते है। इस मामले में, किसी भी कार्यक्रम को अस्वीकार नहीं किया जाता है, लेकिन जिन कार्यक्रमों के लिए विश्लेषण निश्चित कार्यभा को पहचानने में विफल रहता है, उनमें अनावश्यक आरंभीकरण हो सकता है। सामान्य भाषा अवसंरचना इस दृष्टिकोण पर निर्भर करती है।[6]


शब्दावली

एक चर या स्थान को कार्यक्रम में किसी भी बिंदु पर तीन राज्यों में से एक में कहा जा सकता है:

  • निश्चित रूप से निरुपित किया गया: चर निश्चित रूप से निरुपित किए जाने के लिए जाना जाता है।
  • निश्चित रूप से निरुपित नहीं किया गया: चर निश्चित रूप से निरुपित किए जाने के लिए जाना जाता है।
  • अज्ञात: चर निरुपित नहीं किया जा सकता है; विश्लेषण यह निर्धारित करने के लिए पर्याप्त सही नहीं है।

विश्लेषण

निम्नलिखित C# अंतःक्रियात्मक (एकल विधि) निश्चित कार्यभार विश्लेषण के फ्रूजा की औपचारिकता पर आधारित है, जो यह सुनिश्चित करने के लिए ज़िम्मेदार है कि सभी स्थानीय चरों का उपयोग करने से पहले उन्हें निरुपित किया गया है।[4]यह एक साथ निश्चित कार्यभार विश्लेषण और बूलियन मूल्यों का निरंतर प्रसार करता है। हम पाँच स्थिर कार्यों को परिभाषित करते हैं:

Name Domain Description
पहले सभी कथन और भाव। दिए गए कथन या अभिव्यक्ति के मूल्यांकन से पहले चर निश्चित रूप से निर्दिष्ट किए जाते हैं।
बाद सभी कथन और भाव। दिए गए कथन या अभिव्यक्ति के मूल्यांकन के बाद चर निश्चित रूप से निरुपित किए जाते हैं, यह मानते हुए कि यह सामान्य रूप से पूरा होता है।
संस्करण सभी कथन और भाव। दिए गए बयान या अभिव्यक्ति के दायरे में सभी चर उपलब्ध हैं।
सत्य सभी बूलियन अभिव्यक्तियाँ। दिए गए अभिव्यक्ति के मूल्यांकन के बाद चर को निश्चित रूप से निरुपित किया जाता है, यह मानते हुए कि अभिव्यक्ति का मूल्यांकन सही है।
असत्य सभी बूलियन अभिव्यक्तियाँ। दिए गए अभिव्यक्ति के मूल्यांकन के बाद निश्चित रूप से चर को निरुपित किया जाता है, यह मानते हुए कि अभिव्यक्ति का मूल्यांकन गलत है।

हम डेटा-प्रवाह समीकरणों की आपूर्ति करते हैं जो इन कार्यों के मूल्यों को उनके वाक्य-विन्यास उप-अभिव्यक्तियों पर कार्यों के मूल्यों के संदर्भ में, विभिन्न अभिव्यक्तियों और बयानों पर परिभाषित करते हैं। इस क्षण के लिए मान लें कि कोई गोटो, ब्रेक, जारी, वापसी या अपवाद प्रबंधन कथन नहीं हैं। इन समीकरणों के कुछ उदाहरण निम्नलिखित हैं:

  • कोई भी अभिव्यक्ति या कथन ई जो निश्चित रूप से असाइन किए गए चर के सेट को प्रभावित नहीं करता है: बाद (e) = पहले (e)
  • ई को असाइनमेंट एक्सप्रेशन लोक = वी होने दें। फिर पहले (v) = पहले (e), और बाद में (e) = के बाद (v) U {loc}।
  • आइए अभिव्यक्ति 'सत्य' बनें। फिर सच (e) = पहले (e) और झूठा (e) = संस्करण (e)। दूसरे शब्दों में, यदि ई 'गलत' का मूल्यांकन करता है, तो सभी चर (रिक्त सत्य) निश्चित रूप से निर्दिष्ट होते हैं, क्योंकि ई गलत का मूल्यांकन नहीं करता है।
  • चूँकि विधि तर्कों का मूल्यांकन बाएँ से दाएँ किया जाता है, इससे पहले (argi + 1) = के बाद (तर्कi). एक विधि पूर्ण होने के बाद, आउट पैरामीटर निश्चित रूप से असाइन किए जाते हैं।
  • चलो सशर्त बयान 'अगर' (ई) s1 और s2. फिर पहले (ई) = पहले (एस), पहले (एस1) = सच (ई), पहले (एस2) = झूठा (ई), और उसके बाद (एस) = के बाद (एस1) के बाद प्रतिच्छेद करें (एस2).
  • चलो जबकि लूप स्टेटमेंट 'जबकि' (ई) एस1. फिर पहले (ई) = पहले (एस), पहले (एस1) = सच (ई), और बाद में (एस) = गलत (ई)।
  • और इसी तरह।

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

गोटो, ब्रेक, कंटीन्यू, रिटर्न और एक्सेप्शन हैंडलिंग जैसे कंट्रोल-फ्लो जंप की शुरुआत से एल्गोरिथ्म जटिल है। कोई भी कथन जो इन छलांगों में से किसी एक का लक्ष्य हो सकता है, उसे कूद के स्रोत पर निश्चित रूप से निर्दिष्ट चर के सेट के साथ पहले सेट करना चाहिए। जब इन्हें पेश किया जाता है, तो परिणामी डेटा प्रवाह में कई निश्चित बिंदु हो सकते हैं, जैसा कि इस उदाहरण में है: <वाक्यविन्यास लैंग = सी लाइन> 

इंट आई = 1;
एल:
गोटो एल;

चूँकि लेबल L को दो स्थानों से पहुँचा जा सकता है, गोटो के लिए नियंत्रण-प्रवाह समीकरण यह निर्धारित करता है कि पहले (2) = बाद (1) पहले (3) को काटता है। लेकिन पहले (3) = पहले (2), तो पहले (2) = के बाद (1) पहले (2) को छेड़छाड़ करें। इसमें पहले (2), {i} और खाली सेट के लिए दो नियत बिंदु हैं। हालांकि, यह दिखाया जा सकता है कि डेटा-प्रवाह समीकरणों के मोनोटोनिक रूप के कारण, एक अद्वितीय अधिकतम निश्चित बिंदु (सबसे बड़े आकार का निश्चित बिंदु) होता है जो निश्चित रूप से असाइन किए गए चर के बारे में सबसे अधिक संभव जानकारी प्रदान करता है। इस तरह के अधिकतम (या अधिकतम) निश्चित बिंदु की गणना मानक तकनीकों द्वारा की जा सकती है; डेटा प्रवाह विश्लेषण देखें।

एक अतिरिक्त मुद्दा यह है कि एक नियंत्रण-प्रवाह कूद कुछ नियंत्रण प्रवाहों को अव्यवहार्य बना सकता है; उदाहरण के लिए, इस कोड खंड में चर i निश्चित रूप से उपयोग किए जाने से पहले निरुपित किया गया है: 

int मैं;
अगर (जे <0) वापसी; और मैं = जे;
प्रिंट (मैं);

यदि के लिए डेटा-फ्लो समीकरण कहता है कि बाद (2) = के बाद (वापसी) के बाद (i = j) प्रतिच्छेद करता है। इस कार्य को सही ढंग से करने के लिए, हम सभी नियंत्रण-प्रवाह कूदों के बाद (e) = संस्करण(e) को परिभाषित करते हैं; यह एक ही अर्थ में रिक्त रूप से मान्य है कि समीकरण गलत (सत्य) = संस्करण (ई) मान्य है, क्योंकि नियंत्रण-प्रवाह कूद के तुरंत बाद नियंत्रण के लिए एक बिंदु तक पहुंचना संभव नहीं है।

संदर्भ

  1. ↑ J. Gosling; B. Joy; G. Steele; G. Bracha. "The Java Language Specification, 3rd Edition". pp. Chapter 16 (pp.527–552). Retrieved December 2, 2008.
  2. ↑ "Standard ECMA-334, C# Language Specification". ECMA International. pp. Section 12.3 (pp.122–133). Retrieved December 2, 2008.
  3. ↑ Stärk, Robert F.; E. Borger; Joachim Schmid (2001). Java and the Java Virtual Machine: Definition, Verification, Validation. Secaucus, NJ, USA: Springer-Verlag New York, Inc. pp. Section 8.3. ISBN 3-540-42088-6.
  4. ↑ 4.0 4.1 Fruja, Nicu G. (October 2004). "The Correctness of the Definite Assignment Analysis in C#". Journal of Object Technology. 3 (9): 29–52. CiteSeerX 10.1.1.165.6696. doi:10.5381/jot.2004.3.9.a2. Retrieved 2008-12-02. We actually prove more than correctness: we show that the solution of the analysis is a perfect solution (and not only a safe approximation).
  5. ↑ "Cyclone: Definite Assignment". Cyclone User's Manual. Retrieved December 16, 2008.
  6. ↑ "Standard ECMA-335, Common Language Infrastructure (CLI)". ECMA International. pp. Section 1.8.1.1 (Partition III, pg. 19). Retrieved December 2, 2008.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=निश्चित_असाइनमेंट_विश्लेषण&oldid=99900’