निश्चित असाइनमेंट विश्लेषण
कंप्यूटर विज्ञान में, निश्चित कार्यभार विश्लेषण एक डेटा-प्रवाह विश्लेषण है जिसका उपयोग संकलक द्वारा अपरिवर्तनवादी रूप से यह सुनिश्चित करने के लिए किया जाता है कि उपयोग किए जाने से पहले एक चर या स्थान हमेशा निरुपित किया जाता है।
प्रेरणा
सी प्रोग्रामिंग भाषा और 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) को परिभाषित करते हैं; यह एक ही अर्थ में रिक्त रूप से मान्य है कि समीकरण गलत (सत्य) = संस्करण (ई) मान्य है, क्योंकि नियंत्रण-प्रवाह कूद के तुरंत बाद नियंत्रण के लिए एक बिंदु तक पहुंचना संभव नहीं है।
संदर्भ
- ↑ J. Gosling; B. Joy; G. Steele; G. Bracha. "The Java Language Specification, 3rd Edition". pp. Chapter 16 (pp.527–552). Retrieved December 2, 2008.
- ↑ "Standard ECMA-334, C# Language Specification". ECMA International. pp. Section 12.3 (pp.122–133). Retrieved December 2, 2008.
- ↑ 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.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).
- ↑ "Cyclone: Definite Assignment". Cyclone User's Manual. Retrieved December 16, 2008.
- ↑ "Standard ECMA-335, Common Language Infrastructure (CLI)". ECMA International. pp. Section 1.8.1.1 (Partition III, pg. 19). Retrieved December 2, 2008.
