संचालनात्मक शब्दार्थ

From Vigyanwiki
Revision as of 22:01, 24 July 2023 by alpha>Indicwiki (Created page with "{{Short description|Category of formal programming language semantics}} {{Semantics}} ऑपरेशनल सेमेन्टिक्स औपचारिक भा...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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

शायद परिचालन शब्दार्थ का पहला औपचारिक अवतार लिस्प (प्रोग्रामिंग भाषा) के शब्दार्थ को परिभाषित करने के लिए लैम्ब्डा कैलकुलस का उपयोग था।[1] एसईसीडी मशीन की परंपरा में सार मशीनें भी निकटता से संबंधित हैं।

इतिहास

अल्गोल 68 के शब्दार्थ को परिभाषित करने में पहली बार परिचालन शब्दार्थ की अवधारणा का उपयोग किया गया था। निम्नलिखित कथन संशोधित ALGOL 68 रिपोर्ट का एक उद्धरण है:

<ब्लॉककोट> सख्त भाषा में किसी प्रोग्राम का अर्थ एक काल्पनिक कंप्यूटर के संदर्भ में समझाया गया है जो उस कार्यक्रम के विस्तार को बनाने वाली क्रियाओं का समूह निष्पादित करता है। (#एल्गोल68, धारा 2) </ब्लॉककोट>

ऑपरेशनल सिमेंटिक्स शब्द का इसके वर्तमान अर्थ में पहला उपयोग किसके लिए जिम्मेदार है दाना स्कॉट (#plotkin04)। औपचारिक शब्दार्थ विज्ञान पर स्कॉट के मौलिक पेपर का एक उद्धरण इस प्रकार है, जिसमें उन्होंने शब्दार्थ के परिचालन पहलुओं का उल्लेख किया है।

<ब्लॉककोट> अधिक 'सार' और 'स्वच्छ' दृष्टिकोण का लक्ष्य रखना बहुत अच्छी बात है शब्दार्थ, लेकिन यदि योजना अच्छी होनी है, तो परिचालन संबंधी पहलू नहीं हो सकते पूरी तरह से नजरअंदाज किया जाए. (#स्कॉट70) </ब्लॉककोट>

दृष्टिकोण

गॉर्डन प्लॉटकिन ने संरचनात्मक परिचालन शब्दार्थ, मैथ्यू फेलिसेन और रॉबर्ट हीब ने कमी शब्दार्थ, पेश किया।[2] और गाइल्स कहन प्राकृतिक शब्दार्थ।

लघु-चरण शब्दार्थ

संरचनात्मक परिचालन शब्दार्थ

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

एक सरल उदाहरण के लिए, हम एक साधारण प्रोग्रामिंग भाषा के शब्दार्थ के भाग पर विचार करते हैं; #plotkin81 और #hennessybook, और अन्य पाठ्यपुस्तकों में उचित चित्रण दिए गए हैं। होने देना भाषा के कार्यक्रमों की रेंज, और चलो विभिन्न राज्यों में सीमा (उदाहरण के लिए मेमोरी स्थानों से लेकर मानों तक के फ़ंक्शन)। यदि हमारे पास अभिव्यक्तियाँ हैं (क्रमानुसार)। ), मान () और स्थान (), तो मेमोरी अपडेट कमांड में शब्दार्थ होगा:

अनौपचारिक रूप से, नियम कहता है कि यदि अभिव्यक्ति राज्य में मूल्य कम कर देता है , फिर कार्यक्रम राज्य को अद्यतन करेगा असाइनमेंट के साथ .

अनुक्रमण का शब्दार्थ निम्नलिखित तीन नियमों द्वारा दिया जा सकता है:

अनौपचारिक रूप से, पहला नियम कहता है कि, यदि प्रोग्राम राज्य में अवस्था में समाप्त होता है , फिर कार्यक्रम राज्य में कार्यक्रम में कमी आएगी राज्य में . (आप इसे औपचारिकता के रूप में सोच सकते हैं आप चला सकते हैं , और फिर चलाएँ परिणामी मेमोरी स्टोर का उपयोग करना।) दूसरा नियम यही कहता है यदि प्रोग्राम राज्य में प्रोग्राम को कम कर सकते हैं राज्य के साथ , फिर कार्यक्रम राज्य में कार्यक्रम में कमी आएगी राज्य में . (आप इसे एक अनुकूलन कंपाइलर के लिए सिद्धांत को औपचारिक बनाने के रूप में सोच सकते हैं:

आपको बदलने की अनुमति है  मानो यह अकेला हो, भले ही यह सिर्फ हो

किसी कार्यक्रम का पहला भाग. ) शब्दार्थ संरचनात्मक है, क्योंकि अनुक्रमिक कार्यक्रम का अर्थ है , के अर्थ से परिभाषित किया गया है और का अर्थ .

यदि हमारे पास राज्य पर बूलियन अभिव्यक्तियाँ भी हैं, तो सीमा से अधिक , तो हम while कमांड के शब्दार्थ को परिभाषित कर सकते हैं: ऐसी परिभाषा कार्यक्रमों के व्यवहार के औपचारिक विश्लेषण की अनुमति देती है, कार्यक्रमों के बीच संबंध (गणित) के अध्ययन की अनुमति देती है। महत्वपूर्ण संबंधों में अनुकरण पूर्वआदेश और द्विसिमुलेशन शामिल हैं। ये Concurrency (कंप्यूटर विज्ञान) के संदर्भ में विशेष रूप से उपयोगी हैं।

इसके सहज स्वरूप और अनुसरण करने में आसान संरचना के लिए धन्यवाद, एसओएस ने काफी लोकप्रियता हासिल की है और परिभाषित करने में यह एक वास्तविक मानक बन गया है परिचालन शब्दार्थ. सफलता के संकेत के रूप में, मूल रिपोर्ट (तथाकथित आरहूस)। CiteSeer [1] के अनुसार SOS (#plotkin81) पर रिपोर्ट ने 1000 से अधिक उद्धरण आकर्षित किए हैं। इसे कंप्यूटर विज्ञान में सर्वाधिक उद्धृत तकनीकी रिपोर्टों में से एक बना दिया गया है।

न्यूनीकरण शब्दार्थ

न्यूनीकरण शब्दार्थ परिचालन शब्दार्थ की एक वैकल्पिक प्रस्तुति है। इसके मुख्य विचारों को पहली बार 1975 में गॉर्डन प्लॉटकिन द्वारा लैम्ब्डा कैलकुलस के नाम और कॉल द्वारा मूल्य वेरिएंट के अनुसार पूरी तरह से कार्यात्मक कॉल पर लागू किया गया था।[3] और अपने 1987 के शोध प्रबंध में मैथियास फेलिसेन द्वारा अनिवार्य विशेषताओं के साथ उच्च-क्रम कार्यात्मक भाषाओं के लिए सामान्यीकृत किया गया।[4] इस विधि को 1992 में मैथियास फेलिसेन और रॉबर्ट हीब द्वारा नियंत्रण प्रवाह और कार्यक्रम स्थिति के लिए एक पूर्ण समीकरण सिद्धांत में विस्तारित किया गया था।[2]वाक्यांश "रिडक्शन सिमेंटिक्स" पहली बार फेलिसेन और फ्रीडमैन द्वारा PARLE 1987 के पेपर में गढ़ा गया था।[5] कटौती शब्दार्थ को कमी नियमों के एक सेट के रूप में दिया गया है, जिनमें से प्रत्येक एक संभावित कमी चरण को निर्दिष्ट करता है। उदाहरण के लिए, निम्नलिखित कटौती नियम में कहा गया है कि एक असाइनमेंट स्टेटमेंट को कम किया जा सकता है यदि वह अपने परिवर्तनीय घोषणा के ठीक बगल में बैठता है:

असाइनमेंट स्टेटमेंट को ऐसी स्थिति में लाने के लिए इसे फ़ंक्शन एप्लिकेशन और असाइनमेंट स्टेटमेंट के दाईं ओर के माध्यम से "बबल अप" किया जाता है जब तक कि यह उचित बिंदु तक नहीं पहुंच जाता। हस्तक्षेप करने के बाद से अभिव्यक्ति अलग-अलग चर घोषित कर सकती है, कैलकुलस भी एक एक्सट्रूज़न नियम की मांग करता है भाव. कटौती शब्दार्थ के अधिकांश प्रकाशित उपयोग मूल्यांकन संदर्भों की सुविधा के साथ ऐसे "बबल नियमों" को परिभाषित करते हैं। उदाहरण के लिए, मूल्य भाषा द्वारा एक साधारण कॉल में मूल्यांकन संदर्भों का व्याकरण इस प्रकार दिया जा सकता है

कहाँ मनमाना अभिव्यक्ति को दर्शाता है और पूरी तरह से कम किए गए मूल्यों को दर्शाता है। प्रत्येक मूल्यांकन संदर्भ में बिल्कुल एक छेद शामिल होता है जिसमें एक शब्द को कैप्चरिंग फैशन में प्लग किया गया है। संदर्भ का आकार इस छेद से इंगित करता है कि कहां कमी हो सकती है। मूल्यांकन संदर्भों की सहायता से "बुलबुले" का वर्णन करने के लिए, एक एकल सिद्धांत पर्याप्त है:

यह एकल कटौती नियम असाइनमेंट स्टेटमेंट के लिए फेलिसेन और हिएब के लैम्ब्डा कैलकुलस से लिफ्ट नियम है। मूल्यांकन संदर्भ इस नियम को कुछ शर्तों तक सीमित रखते हैं, लेकिन यह लैम्ब्डा सहित किसी भी अवधि में स्वतंत्र रूप से लागू होता है।

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

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


बड़ा कदम शब्दार्थ

प्राकृतिक शब्दार्थ

बिग-स्टेप स्ट्रक्चरल ऑपरेशनल सिमेंटिक्स को प्राकृतिक सिमेंटिक्स, रिलेशनल सिमेंटिक्स और मूल्यांकन सिमेंटिक्स के नाम से भी जाना जाता है।[8] मिनी-एमएल, एमएल (प्रोग्रामिंग भाषा) की एक शुद्ध बोली प्रस्तुत करते समय गाइल्स काह्न द्वारा बिग-स्टेप ऑपरेशनल सिमेंटिक्स को प्राकृतिक सिमेंटिक्स के नाम से पेश किया गया था।

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

एक बड़ा कदम शब्दार्थ विभाजन-और-जीत तरीके से वर्णन करता है कि कैसे भाषा निर्माण के अंतिम मूल्यांकन परिणाम उनके वाक्यात्मक समकक्षों (उपअभिव्यक्ति, उपकथन, आदि) के मूल्यांकन परिणामों को मिलाकर प्राप्त किए जा सकते हैं।

तुलना

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

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

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


यह भी देखें

संदर्भ

  1. McCarthy, John. "प्रतीकात्मक अभिव्यक्तियों के पुनरावर्ती कार्य और मशीन द्वारा उनकी गणना, भाग I". Archived from the original on 2013-10-04. Retrieved 2006-10-13.
  2. 2.0 2.1 Felleisen, M.; Hieb, R. (1992). "अनुक्रमिक नियंत्रण और राज्य के वाक्यात्मक सिद्धांतों पर संशोधित रिपोर्ट". Theoretical Computer Science. 103 (2): 235–271. doi:10.1016/0304-3975(92)90014-7.
  3. Plotkin, Gordon (1975). "Call-by-name, call-by-value and the λ-calculus" (PDF). Theoretical Computer Science. 1 (2): 125–159. doi:10.1016/0304-3975(75)90017-1. Retrieved July 22, 2021.
  4. Felleisen, Matthias (1987). The calculi of Lambda-v-CS conversion: a syntactic theory of control and state in imperative higher-order programming languages (PDF) (PhD). Indiana University. Retrieved July 22, 2021.
  5. Felleisen, Matthias; Friedman, Daniel P. (1987). "अनिवार्य उच्च-क्रम भाषाओं के लिए एक न्यूनीकरण शब्दार्थ". Proceedings of the Parallel Architectures and Languages Europe. International Conference on Parallel Architectures and Languages Europe. Vol. 1. Springer-Verlag. pp. 206–223. doi:10.1007/3-540-17945-3_12.
  6. Abadi, M.; Cardelli, L. (8 September 2012). वस्तुओं का एक सिद्धांत. ISBN 9781441985989.
  7. Felleisen, Matthias; Findler, Robert Bruce; Flatt, Matthew (2009). पीएलटी रिडेक्स के साथ सिमेंटिक्स इंजीनियरिंग. The MIT Press. ISBN 978-0-262-06275-6.
  8. University of Illinois CS422
  9. 9.0 9.1 9.2 Xavier Leroy. "Coinductive big-step operational semantics".


अग्रिम पठन


बाहरी संबंध