ऑटोमेटा-आधारित प्रोग्रामिंग: Difference between revisions

From Vigyanwiki
No edit summary
 
(9 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Programming paradigm based on formal automatons}}
{{Short description|Programming paradigm based on formal automatons}}
{{Other uses|ऑटोमेटा-आधारित प्रोग्रामिंग (शालीटो का दृष्टिकोण)}}
{{Programming paradigms}}
{{Programming paradigms}}


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


'''परिमित-अवस्था मशीन-आधारित प्रोग्रामिंग''' आम तौर पर समान होती है, लेकिन, औपचारिक रूप से बोलते हुए, सभी संभावित परिवर्ती को आवरण नहीं करती है, क्योंकि एफएसएम का मतलब परिमित-अवस्था मशीन है, और ऑटोमेटा-आधारित प्रोग्रामिंग आवश्यक रूप से सख्त अर्थों में एफएसएम को नियोजित नहीं करती है।
'''परिमित-अवस्था मशीन-आधारित प्रोग्रामिंग''' सामान्यतः समान होती है, लेकिन, औपचारिक रूप से बोलते हुए, सभी संभावित परिवर्ती को आवरण नहीं करती है, क्योंकि FSM (एफएसएम) का मतलब परिमित-अवस्था मशीन है, और ऑटोमेटा-आधारित प्रोग्रामिंग आवश्यक रूप से सख्त अर्थों में FSMs को नियोजित नहीं करती है।


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


ऑटोमेटा-आधारित कोड का संपूर्ण निष्पादन ऑटोमेटन चरणों का एक ''चक्र'' है।
ऑटोमेटा-आधारित कोड का संपूर्ण निष्पादन ऑटोमेटन चरणों का एक ''चक्र'' है।
Line 114: Line 113:
}
}
</syntaxhighlight>
</syntaxhighlight>
हालाँकि यह प्रोग्राम अब प्रतिकूल दिखता है, लेकिन इसका कम से कम एक महत्वपूर्ण लाभ है: इसमें केवल एक ही रीडिंग है (अर्थात,<code>getchar</code> फ़ंक्शन पर कॉल) निर्देश है। इसके अलावा, पारंपरिक संस्करण में मौजूद चार के बजाय केवल एक लूप है। <code>while</code> लूप की बॉडी ऑटोमेटन चरण है और लूप स्वयं ऑटोमेटन चरण का चक्र है। प्रोग्राम अवस्था आरेख में दिखाए गए परिमित-अवस्था मशीन के टास्क को कार्यान्वित करता है।
हालाँकि यह प्रोग्राम अब प्रतिकूल दिखता है, लेकिन इसका कम से कम एक महत्वपूर्ण लाभ है: इसमें केवल एक ही रीडिंग है (अर्थात,<code>getchar</code> फ़ंक्शन पर कॉल) निर्देश है। इसके अतिरिक्त, पारंपरिक संस्करण में सम्मिलित चार के अतिरिक्त केवल एक लूप है। <code>while</code> लूप की बॉडी ''ऑटोमेटन चरण'' है और लूप स्वयं ऑटोमेटन चरण का ''चक्र'' है। प्रोग्राम अवस्था आरेख में दिखाए गए परिमित-अवस्था मशीन के टास्क को कार्यान्वित करता है।


प्रोग्राम की सबसे महत्वपूर्ण गुण यह है कि ऑटोमेटन चरण कोड अनुभाग स्पष्ट रूप से स्थानीयकृत है। एक स्पष्ट टास्क के साथ <code>step</code> स्वचालन चरण के लिए, प्रोग्राम इस गुण को बेहतर ढंग से प्रदर्शित करता है:
प्रोग्राम की सबसे महत्वपूर्ण गुण यह है कि ऑटोमेटन चरण कोड अनुभाग स्पष्ट रूप से स्थानीयकृत है। एक स्पष्ट टास्क के साथ <code>step</code> स्वचालन चरण के लिए, प्रोग्राम इस गुण को बेहतर ढंग से प्रदर्शित करता है:
Line 174: Line 173:


{| class="wikitable" style="text-align: center; display: inline-table; vertical-align:top;"
{| class="wikitable" style="text-align: center; display: inline-table; vertical-align:top;"
|+ State-transition table
|+ अवस्था-संक्रमण तालिका
! {{diagonal split header|<small>Current state</small>|<small>Input</small>}}
! {{diagonal split header|<small>Current state</small>|<small>Input</small>}}
!नई पंक्ति
!नई पंक्ति
Line 196: Line 195:
|}
|}
{| style="text-align: center; display: inline-table; vertical-align:top;"
{| style="text-align: center; display: inline-table; vertical-align:top;"
|+ '''State diagram'''
|+ '''अवस्था आरेख'''
|-
|-
| [[File:Finite-state machine state-diagram.png|thumb|500px|The [[state diagram]] of a finite-state machine that prints the first word of each line of an input stream. The machine follows exactly one transition on each step, depending on the current state and the encountered character. The action accompanying a transition is either a no-operation or the printing of the encountered character, denoted with ''print''.]]
| [[File:Finite-state machine state-diagram.png|thumb|500px|परिमित-स्थिति मशीन का राज्य आरेख जो इनपुट स्ट्रीम की प्रत्येक पंक्ति के पहले शब्द को प्रिंट करता है। मशीन वर्तमान स्थिति और सामने आए चरित्र के आधार पर, प्रत्येक चरण पर ठीक एक संक्रमण का अनुसरण करती है। संक्रमण के साथ होने वाली क्रिया या तो नो-ऑपरेशन है या सामना किए गए चरित्र की छपाई है, जिसे ''प्रिंट'' के साथ दर्शाया गया है।]]
|}
|}
सामान्यतया, ऑटोमेटा-आधारित प्रोग्राम स्वाभाविक रूप से इस दृष्टिकोण का उपयोग कर सकता है। एक स्पष्ट द्वि-आयामी सरणी के साथ <code>transitions</code> अवस्था-संक्रमण तालिका के लिए, प्रोग्राम इस दृष्टिकोण का उपयोग करता है:
सामान्यतया, ऑटोमेटा-आधारित प्रोग्राम स्वाभाविक रूप से इस दृष्टिकोण का उपयोग कर सकता है। एक स्पष्ट द्वि-आयामी सरणी के साथ <code>transitions</code> अवस्था-संक्रमण तालिका के लिए, प्रोग्राम इस दृष्टिकोण का उपयोग करता है:
Line 323: Line 322:
''टिप्पणी''। — लेख के विषय, इनपुट/आउटपुट से सीधे संबंधित न होने वाले परिवर्तनों को कम करने के लिए <code>getchar</code> और <code>putchar</code> C (प्रोग्रामिंग लैंग्वेज) की मानक लाइब्रेरी के फ़ंक्शंस का उपयोग किया जा रहा है।
''टिप्पणी''। — लेख के विषय, इनपुट/आउटपुट से सीधे संबंधित न होने वाले परिवर्तनों को कम करने के लिए <code>getchar</code> और <code>putchar</code> C (प्रोग्रामिंग लैंग्वेज) की मानक लाइब्रेरी के फ़ंक्शंस का उपयोग किया जा रहा है।


[[ राज्य पैटर्न |अवस्था पैटर्न]] किसी ऑब्जेक्ट के लिए वर्चुअल फ़ंक्शन कॉल के लिए ''बड़े सशर्त बयानों या टेबल लुकअप का सहारा लिए बिना'' रनटाइम पर अपने आंतरिक स्थिति के अनुसार अपने व्यवहार को बदलने का तरीका है। बड़े सशर्त बयानों का उपयोग करने वाले कोड पर इसका मुख्य लाभ यह है कि अवस्था-विशिष्ट कोड को अखंड ब्लॉक में स्थानीयकृत करने के बजाय विभिन्न वस्तुओं में वितरित किया जाता है, जिससे रखरखाव में सुधार होता है। अवस्था-संक्रमण तालिकाओं का उपयोग करने वाले कोड पर इसका मुख्य लाभ यह है कि वर्चुअल फ़ंक्शन कॉल अक्सर तालिका लुकअप की तुलना में अधिक कुशल होते हैं, अवस्था-संक्रमण मानदंड सारणीबद्ध प्रारूप की तुलना में अधिक स्पष्ट होते हैं, और अवस्था संक्रमण के साथ क्रियाओं को जोड़ना आसान होता है। हालाँकि यह एक नई समस्या पेश करता है: कक्षाओं की संख्या कोड को अन्य दृष्टिकोणों की तुलना में कम सघन बनाती है। अवस्था डिज़ाइन पैटर्न का उपयोग करने वाला प्रोग्राम इस तरह दिख सकता है:
[[ राज्य पैटर्न |अवस्था पैटर्न]] किसी ऑब्जेक्ट के लिए वर्चुअल फ़ंक्शन कॉल के लिए ''बड़े सशर्त बयानों या टेबल लुकअप का सहारा लिए बिना'' रनटाइम पर अपने आंतरिक स्थिति के अनुसार अपने व्यवहार को बदलने का तरीका है। बड़े सशर्त बयानों का उपयोग करने वाले कोड पर इसका मुख्य लाभ यह है कि अवस्था-विशिष्ट कोड को अखंड ब्लॉक में स्थानीयकृत करने के अतिरिक्त विभिन्न ऑब्जेक्ट में वितरित किया जाता है, जिससे रखरखाव में सुधार होता है। अवस्था-संक्रमण तालिकाओं का उपयोग करने वाले कोड पर इसका मुख्य लाभ यह है कि वर्चुअल फ़ंक्शन कॉल अधिकांशतः तालिका लुकअप की तुलना में अधिक कुशल होते हैं, अवस्था-संक्रमण मानदंड सारणीबद्ध प्रारूप की तुलना में अधिक स्पष्ट होते हैं, और अवस्था संक्रमण के साथ क्रियाओं को जोड़ना आसान होता है। हालाँकि यह एक नई समस्या पेश करता है: कक्षाओं की संख्या कोड को अन्य दृष्टिकोणों की तुलना में कम सघन बनाती है। अवस्था डिज़ाइन पैटर्न का उपयोग करने वाला प्रोग्राम इस तरह दिख सकता है:


<syntaxhighlight lang="cpp">
<syntaxhighlight lang="cpp">
Line 484: Line 483:
ऑटोमेटा-आधारित प्रोग्रामिंग वास्तव में स्वचालन के क्षेत्र में पाई जाने वाली प्रोग्रामिंग आवश्यकताओं से काफी मेल खाती है।
ऑटोमेटा-आधारित प्रोग्रामिंग वास्तव में स्वचालन के क्षेत्र में पाई जाने वाली प्रोग्रामिंग आवश्यकताओं से काफी मेल खाती है।


एक उत्पादन चक्र आमतौर पर इस प्रकार तैयार किया जाता है:
एक उत्पादन चक्र सामान्यतः इस प्रकार तैयार किया जाता है:
* इनपुट डेटा (कैप्टर्स से) के अनुसार चरणों का क्रम;
* इनपुट डेटा (कैप्टर्स से) के अनुसार चरणों का क्रम;
* वर्तमान चरण के आधार पर की जाने वाली क्रियाओं का सेट।
* वर्तमान चरण के आधार पर की जाने वाली क्रियाओं का सेट।
Line 527: Line 526:
ऑटोमेशन के क्षेत्र में एक कदम से दूसरे कदम आगे बढ़ना मशीन से आने वाले इनपुट डेटा पर ही निर्भर करता है। इसे प्रोग्राम में किसी टेक्स्ट के पात्रों को पढ़कर दर्शाया जाता है। वास्तव में, वे डेटा किसी मशीन के महत्वपूर्ण तत्वों की स्थिति, गति, तापमान आदि के बारे में सूचित करते हैं।
ऑटोमेशन के क्षेत्र में एक कदम से दूसरे कदम आगे बढ़ना मशीन से आने वाले इनपुट डेटा पर ही निर्भर करता है। इसे प्रोग्राम में किसी टेक्स्ट के पात्रों को पढ़कर दर्शाया जाता है। वास्तव में, वे डेटा किसी मशीन के महत्वपूर्ण तत्वों की स्थिति, गति, तापमान आदि के बारे में सूचित करते हैं।


[[जीयूआई]] प्रोग्रामिंग की तरह, मशीन की स्थिति में बदलाव को अंतिम स्थिति तक पहुंचने तक अवस्था से दूसरे अवस्था में जाने वाली घटनाओं के रूप में माना जा सकता है। संभावित अवस्थाओं का संयोजन विभिन्न प्रकार की घटनाओं को उत्पन्न कर सकता है, इस प्रकार अधिक जटिल उत्पादन चक्र को परिभाषित किया जा सकता है। परिणामस्वरूप, चक्र आमतौर पर सरल रैखिक अनुक्रम होने से बहुत दूर होते हैं। आम तौर पर समानांतर शाखाएं एक साथ चलती हैं और विभिन्न घटनाओं के अनुसार विकल्प चुने जाते हैं, जिन्हें नीचे योजनाबद्ध तरीके से दर्शाया गया है:
[[जीयूआई]] प्रोग्रामिंग की तरह, मशीन की स्थिति में बदलाव को अंतिम स्थिति तक पहुंचने तक अवस्था से दूसरे अवस्था में जाने वाली घटनाओं के रूप में माना जा सकता है। संभावित अवस्थाओं का संयोजन विभिन्न प्रकार की घटनाओं को उत्पन्न कर सकता है, इस प्रकार अधिक जटिल उत्पादन चक्र को परिभाषित किया जा सकता है। परिणामस्वरूप, चक्र सामान्यतः सरल रैखिक अनुक्रम होने से बहुत दूर होते हैं। सामान्यतः समानांतर शाखाएं एक साथ चलती हैं और विभिन्न घटनाओं के अनुसार विकल्प चुने जाते हैं, जिन्हें नीचे योजनाबद्ध तरीके से दर्शाया गया है:


     s:stage c:condition
     s:stage c:condition
Line 564: Line 563:
</ref>
</ref>


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


अवस्था और अवस्था मशीनों की धारणाओं का उपयोग अक्सर औपचारिक विनिर्देशन के क्षेत्र में किया जाता है। उदाहरण के लिए, यूएमएल-आधारित सॉफ़्टवेयर आर्किटेक्चर विकास प्रोग्राम के व्यवहार को निर्दिष्ट करने के लिए अवस्था आरेखों का उपयोग करता है। इसके अलावा विभिन्न [[संचार प्रोटोकॉल]] अक्सर अवस्था की स्पष्ट धारणा का उपयोग करके निर्दिष्ट किए जाते हैं (उदाहरण के लिए, {{IETF RFC|793}}).
अवस्था और अवस्था मशीनों की धारणाओं का उपयोग अधिकांशतः औपचारिक विनिर्देशन के क्षेत्र में किया जाता है। उदाहरण के लिए, यूएमएल-आधारित सॉफ़्टवेयर आर्किटेक्चर विकास प्रोग्राम के व्यवहार को निर्दिष्ट करने के लिए अवस्था आरेखों का उपयोग करता है। इसके अतिरिक्त विभिन्न [[संचार प्रोटोकॉल]] अधिकांशतः अवस्था की स्पष्ट धारणा का उपयोग करके निर्दिष्ट किए जाते हैं (उदाहरण के लिए, {{IETF RFC|793}}).


कुछ [[प्रोग्रामिंग भाषा|प्रोग्रामिंग]] लैंग्वेज के शब्दार्थ का वर्णन करने के लिए ऑटोमेटा (चरण और स्थिति) के संदर्भ में सोचने का भी उपयोग किया जा सकता है। उदाहरण के लिए, रिफ़ल लैंग्वेज में लिखे गए प्रोग्राम के निष्पादन को तथाकथित अमूर्त रिफ़ल मशीन के चरणों के अनुक्रम के रूप में वर्णित किया गया है; मशीन की स्थिति एक ''दृश्य'' है (चर के बिना यादृच्छिक रिफ़ल अभिव्यक्ति)।
कुछ [[प्रोग्रामिंग भाषा|प्रोग्रामिंग]] लैंग्वेज के शब्दार्थ का वर्णन करने के लिए ऑटोमेटा (चरण और स्थिति) के संदर्भ में सोचने का भी उपयोग किया जा सकता है। उदाहरण के लिए, रिफ़ल लैंग्वेज में लिखे गए प्रोग्राम के निष्पादन को तथाकथित अमूर्त रिफ़ल मशीन के चरणों के अनुक्रम के रूप में वर्णित किया गया है; मशीन की स्थिति एक ''दृश्य'' है (चर के बिना यादृच्छिक रिफ़ल अभिव्यक्ति)।


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


अलेक्जेंडर ओलोंग्रेन ने अपनी पुस्तक में<ref>{{cite book
अलेक्जेंडर ओलोंग्रेन ने अपनी पुस्तक में<ref>{{cite book
Line 582: Line 581:
}}</ref> प्रोग्रामिंग लैंग्वेज के शब्दार्थ विवरण की तथाकथित वियना विधि की व्याख्या करता है जो पूरी तरह से औपचारिक ऑटोमेटा पर आधारित है।
}}</ref> प्रोग्रामिंग लैंग्वेज के शब्दार्थ विवरण की तथाकथित वियना विधि की व्याख्या करता है जो पूरी तरह से औपचारिक ऑटोमेटा पर आधारित है।


एसटीएटी प्रणाली [https://web.archive.org/web/20080202163122/http://www.cs.ucsb.edu/~seclab/projects/stat/index.html] ऑटोमेटा-आधारित दृष्टिकोण का उपयोग करने का अच्छा उदाहरण है; इस प्रणाली में, अन्य सुविधाओं के अलावा, ''एसटीएटीएल'' नामक सन्निहित लैंग्वेज शामिल है जो पूरी तरह से ऑटोमेटा-उन्मुख है।
एसटीएटी प्रणाली [https://web.archive.org/web/20080202163122/http://www.cs.ucsb.edu/~seclab/projects/stat/index.html] ऑटोमेटा-आधारित दृष्टिकोण का उपयोग करने का अच्छा उदाहरण है; इस प्रणाली में, अन्य सुविधाओं के अतिरिक्त, ''एसटीएटीएल'' नामक सन्निहित लैंग्वेज सम्मिलित है जो पूरी तरह से ऑटोमेटा-उन्मुख है।


== इतिहास ==
== इतिहास ==
Line 621: Line 620:
| s2cid = 189785656
| s2cid = 189785656
  }}
  }}
</ref> लेखक इस तकनीक को ''ट्यूरिंग मशीन'' दृष्टिकोण कहते हैं, हालाँकि पेपर में कोई वास्तविक ट्यूरिंग मशीन नहीं दी गई है; इसके बजाय, चरणों और अवस्थाओं पर आधारित तकनीक का वर्णन किया गया है।
</ref> लेखक इस तकनीक को ''ट्यूरिंग मशीन'' ''दृष्टिकोण'' कहते हैं, हालाँकि पेपर में कोई वास्तविक ट्यूरिंग मशीन नहीं दी गई है; इसके अतिरिक्त, चरणों और अवस्थाओं पर आधारित तकनीक का वर्णन किया गया है।


== अनिवार्य और प्रक्रियात्मक प्रोग्रामिंग के साथ तुलना ==
== आदेशसूचक और प्रक्रियात्मक प्रोग्रामिंग के साथ तुलना ==
[[राज्य (कंप्यूटर विज्ञान)|अवस्था (कंप्यूटर विज्ञान)]] की धारणा ऑटोमेटा-आधारित प्रोग्रामिंग की विशिष्ट गुण नहीं है।<ref>
[[राज्य (कंप्यूटर विज्ञान)|अवस्था (कंप्यूटर विज्ञान)]] की धारणा ऑटोमेटा-आधारित प्रोग्रामिंग की विशिष्ट गुण नहीं है।<ref>
{{Cite journal
{{Cite journal
Line 632: Line 631:
  | url = http://ntv.ifmo.ru/file/journal/61.pdf
  | url = http://ntv.ifmo.ru/file/journal/61.pdf
}}
}}
</ref>
</ref>सामान्यतया, अवस्था (या प्रोग्राम अवस्था) किसी भी [[कंप्यूटर प्रोग्राम]] के निष्पादन के दौरान सभी सूचनाओं के संयोजन के रूप में प्रकट होता है जो निष्पादन के दौरान बदल सकते हैं। उदाहरण के लिए, पारंपरिक [[अनिवार्य प्रोग्रामिंग|आदेशसूचक प्रोग्रामिंग]] प्रोग्राम की स्थिति में सम्मिलित हैं
सामान्यतया, अवस्था (या प्रोग्राम अवस्था) किसी भी [[कंप्यूटर प्रोग्राम]] के निष्पादन के दौरान सभी सूचनाओं के संयोजन के रूप में प्रकट होता है जो निष्पादन के दौरान बदल सकते हैं। उदाहरण के लिए, एक पारंपरिक [[अनिवार्य प्रोग्रामिंग]] प्रोग्राम की स्थिति में शामिल हैं
* सभी चरों के मान और गतिशील मेमोरी में संग्रहीत जानकारी;
* सभी चरों के मान और गतिशील मेमोरी में संग्रहीत जानकारी;
* रजिस्टरों में संग्रहीत मान;
* रजिस्टरों में संग्रहीत मान;
Line 641: Line 639:
इन्हें स्पष्ट भाग (जैसे चर में संग्रहीत मान) और अंतर्निहित भाग (वापसी एड्रेस और निर्देश सूचक) में विभाजित किया जा सकता है।
इन्हें स्पष्ट भाग (जैसे चर में संग्रहीत मान) और अंतर्निहित भाग (वापसी एड्रेस और निर्देश सूचक) में विभाजित किया जा सकता है।


ऐसा कहने के बाद, एक ऑटोमेटा-आधारित [[कार्यक्रम स्थिति|प्रोग्राम स्थिति]] एक अनिवार्य प्रोग्राम के एक विशेष मामले के रूप में माना जा सकता है, जिसमें अवस्था के निहित हिस्से को कम से कम किया जाता है। चरण कोड अनुभाग में प्रवेश करने के दो अलग-अलग क्षणों में ली गई पूरे प्रोग्राम की स्थिति केवल ऑटोमेटन स्थिति में भिन्न हो सकती है। इससे प्रोग्राम का विश्लेषण सरल हो जाता है.
ऐसा कहने के बाद, ऑटोमेटा-आधारित [[कार्यक्रम स्थिति|प्रोग्राम स्थिति]] आदेशसूचक प्रोग्राम के विशेष स्थिति के रूप में माना जाता है, जिसमें अवस्था के निहित हिस्से को कम से कम किया जाता है। ''चरण'' कोड अनुभाग में प्रवेश करने के दो अलग-अलग क्षणों में ली गई पूरे प्रोग्राम की स्थिति केवल ऑटोमेटन स्थिति में भिन्न हो सकती है। इससे प्रोग्राम का विश्लेषण सरल हो जाता है.


== ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग संबंध ==
== ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग संबंध ==
ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग के सिद्धांत में, एक ऑब्जेक्ट को एक आंतरिक स्थिति कहा जाता है और वह संदेश प्राप्त करने, उन पर प्रतिक्रिया देने, अन्य ऑब्जेक्ट को संदेश भेजने और संदेश हैंडलिंग के दौरान अपनी आंतरिक स्थिति को बदलने में सक्षम है। अधिक व्यावहारिक शब्दावली में, किसी ऑब्जेक्ट की विधि को कॉल करना ऑब्जेक्ट को संदेश भेजने के समान ही माना जाता है।
ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग के सिद्धांत में, ''ऑब्जेक्ट'' को आंतरिक ''स्थिति'' कहा जाता है और वह ''संदेश प्राप्त करने'', उन पर ''प्रतिक्रिया'' देने, अन्य ऑब्जेक्ट को संदेश ''भेजने'' और संदेश प्रबन्ध के दौरान अपनी आंतरिक स्थिति को बदलने में सक्षम है। अधिक व्यावहारिक शब्दावली में, किसी ''ऑब्जेक्ट की विधि को कॉल करना'' ऑब्जेक्ट को संदेश भेजने के समान ही माना जाता है।


इस प्रकार, एक ओर, ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग की वस्तुओं को ऑटोमेटा (या ऑटोमेटा के मॉडल) के रूप में माना जा सकता है, जिनकी स्थिति निजी क्षेत्रों का संयोजन है, और एक या अधिक तरीकों को चरण माना जाता है। ऐसी विधियों को न तो एक-दूसरे को कॉल करना चाहिए और न ही स्वयं, न तो प्रत्यक्ष और न ही अप्रत्यक्ष रूप से, अन्यथा ऑब्जेक्ट को ऑटोमेटा-आधारित तरीके से कार्यान्वित नहीं माना जा सकता है।
इस प्रकार, एक ओर, ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग की ऑब्जेक्ट को ऑटोमेटा (या ऑटोमेटा के मॉडल) के रूप में माना जा सकता है, जिनकी ''स्थिति'' निजी क्षेत्रों का संयोजन है, और एक या अधिक तरीकों को चरण माना जाता है। ऐसी विधियों को न तो एक-दूसरे को कॉल करना चाहिए और न ही स्वयं, न तो प्रत्यक्ष और न ही अप्रत्यक्ष रूप से, अन्यथा ऑब्जेक्ट को ऑटोमेटा-आधारित तरीके से कार्यान्वित नहीं माना जा सकता है।


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


== यह भी देखें ==
== यह भी देखें ==
Line 654: Line 652:
* [[गैर-नियतात्मक प्रोग्रामिंग]]
* [[गैर-नियतात्मक प्रोग्रामिंग]]
* अवस्था पैटर्न
* अवस्था पैटर्न
* [[एस्टरेल]], एक ऑटोमेटा-आधारित लैंग्वेज
* [[एस्टरेल]], ऑटोमेटा-आधारित लैंग्वेज
* [[भरना]], जावा और सी++ में ऑटोमेटा जोड़ने का एक उपकरण
* [[भरना|उम्पल]], जावा और C++ में ऑटोमेटा जोड़ने का उपकरण


== संदर्भ ==
== संदर्भ ==
Line 691: Line 689:
* <cite id="CITEREFPolikarpova2009">Polikarpova N. I., Shalyto A. A. [http://is.ifmo.ru/books/_book.pdf Automata-based programming] SPb.: Piter. 2009 (rus)</cite>
* <cite id="CITEREFPolikarpova2009">Polikarpova N. I., Shalyto A. A. [http://is.ifmo.ru/books/_book.pdf Automata-based programming] SPb.: Piter. 2009 (rus)</cite>
* [http://is.ifmo.ru ITMO University, "Programming Technology" department]
* [http://is.ifmo.ru ITMO University, "Programming Technology" department]
[[Category: प्रोग्रामिंग प्रतिमान]]


[[Category: Machine Translated Page]]
[[Category:Created On 24/07/2023]]
[[Category:Created On 24/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:प्रोग्रामिंग प्रतिमान]]

Latest revision as of 11:44, 21 August 2023

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

परिमित-अवस्था मशीन-आधारित प्रोग्रामिंग सामान्यतः समान होती है, लेकिन, औपचारिक रूप से बोलते हुए, सभी संभावित परिवर्ती को आवरण नहीं करती है, क्योंकि FSM (एफएसएम) का मतलब परिमित-अवस्था मशीन है, और ऑटोमेटा-आधारित प्रोग्रामिंग आवश्यक रूप से सख्त अर्थों में FSMs को नियोजित नहीं करती है।

निम्नलिखित गुण ऑटोमेटा-आधारित प्रोग्रामिंग के लिए प्रमुख संकेतक हैं:

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

ऑटोमेटा-आधारित कोड का संपूर्ण निष्पादन ऑटोमेटन चरणों का एक चक्र है।

ऑटोमेटा-आधारित प्रोग्रामिंग की धारणा का उपयोग करने का अन्य कारण यह है कि इस तकनीक में प्रोग्राम के बारे में प्रोग्रामर की सोचने की शैली ट्यूरिंग मशीन, मार्कोव एल्गोरिथ्म इत्यादि का उपयोग करके गणितीय कार्यों को हल करने के लिए उपयोग की जाने वाली सोच की शैली के समान है।

उदाहरण

टास्क

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

पारंपरिक प्रोग्राम

C (प्रोग्रामिंग लैंग्वेज) में पारंपरिक प्रोग्राम जो उपरोक्त टास्क करता है वह इस तरह दिख सकता है:

#include <ctype.h>
#include <stdio.h>


int main(void) {
  int c;

  do {
    do {
      c = getchar();
    } while (isspace(c));

    while (!isspace(c) && c != EOF) {
      putchar(c);
      c = getchar();
    }
    
    while (c != '\n' && c != EOF) {
      c = getchar();
    }
    
    if (c == '\n') {
      putchar(c);
    }
  } while (c != EOF);

  return 0;
}

उदाहरण के लिए, उपरोक्त प्रोग्राम को इस इनपुट पर संकलित करना और चलाना:

$ clang program.c && (printf "\t\v\f\r \n\n\t\v\f\r foo bar baz\n\n\t\v\f\r qux quux corge" | ./a.out)

देता है:

foo
qux

ऑटोमेटा-आधारित प्रोग्राम

प्रक्रियात्मक

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

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


int main(void) {
  int c;
  enum State s = BEFORE;

  while ((c = getchar()) != EOF) {
    switch (s) {
      case BEFORE:
        if (!isspace(c)) {
          putchar(c);
          s = INSIDE;
        }
        
        break;
      case INSIDE:
        if (c == '\n') {
          putchar(c);
          s = BEFORE;
        } else if (isspace(c)) {
          s = AFTER;
        } else {
          putchar(c);
        }
          
        break;
      case AFTER:
        if (c == '\n') {
          putchar(c);
          s = BEFORE;
        }
        
        break;
    }
  }

  return 0;
}

हालाँकि यह प्रोग्राम अब प्रतिकूल दिखता है, लेकिन इसका कम से कम एक महत्वपूर्ण लाभ है: इसमें केवल एक ही रीडिंग है (अर्थात,getchar फ़ंक्शन पर कॉल) निर्देश है। इसके अतिरिक्त, पारंपरिक संस्करण में सम्मिलित चार के अतिरिक्त केवल एक लूप है। while लूप की बॉडी ऑटोमेटन चरण है और लूप स्वयं ऑटोमेटन चरण का चक्र है। प्रोग्राम अवस्था आरेख में दिखाए गए परिमित-अवस्था मशीन के टास्क को कार्यान्वित करता है।

प्रोग्राम की सबसे महत्वपूर्ण गुण यह है कि ऑटोमेटन चरण कोड अनुभाग स्पष्ट रूप से स्थानीयकृत है। एक स्पष्ट टास्क के साथ step स्वचालन चरण के लिए, प्रोग्राम इस गुण को बेहतर ढंग से प्रदर्शित करता है:

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


void step(enum State* const s, int const c) {
  switch (*s) {
    case BEFORE:
      if (!isspace(c)) {
        putchar(c);
        *s = INSIDE;
      }
      
      break;
    case INSIDE:
      if (c == '\n') {
        putchar(c);
        *s = BEFORE;
      } else if (isspace(c)) {
        *s = AFTER;
      } else {
        putchar(c);
      }
        
      break;
    case AFTER:
      if (c == '\n') {
        putchar(c);
        *s = BEFORE;
      }
      
      break;
  }
}


int main(void) {
  int c;
  enum State s = BEFORE;

  while ((c = getchar()) != EOF) {
    step(&s, c);
  }

  return 0;
}

प्रोग्राम अब ऑटोमेटा-आधारित कोड के मूल गुणों को स्पष्ट रूप से प्रदर्शित करता है:

  • ऑटोमेटन चरण निष्पादन की समय अवधि अतिछादित नहीं हो सकती है;
  • पिछले चरण से अगले चरण तक भेजी गई एकमात्र जानकारी स्पष्ट रूप से निर्दिष्ट ऑटोमेटन स्थिति है।

परिमित ऑटोमेटन को अवस्था-संक्रमण तालिका द्वारा परिभाषित किया जा सकता है, जिसकी पंक्तियाँ वर्तमान स्थितियों के लिए होती हैं, कॉलम इनपुट के लिए होते हैं, और सेल अगले अवस्था और प्रदर्शन करने के लिए क्रियाओं के लिए होती हैं।

अवस्था-संक्रमण तालिका
Input
Current state
नई पंक्ति व्हीटस्पॉस अन्य
पहले पहले पहले अंदर/प्रिंट
अंदर पहले/प्रिंट बाद अंदर/प्रिंट
बाद पहले/प्रिंट बाद बाद
अवस्था आरेख
परिमित-स्थिति मशीन का राज्य आरेख जो इनपुट स्ट्रीम की प्रत्येक पंक्ति के पहले शब्द को प्रिंट करता है। मशीन वर्तमान स्थिति और सामने आए चरित्र के आधार पर, प्रत्येक चरण पर ठीक एक संक्रमण का अनुसरण करती है। संक्रमण के साथ होने वाली क्रिया या तो नो-ऑपरेशन है या सामना किए गए चरित्र की छपाई है, जिसे प्रिंट के साथ दर्शाया गया है।

सामान्यतया, ऑटोमेटा-आधारित प्रोग्राम स्वाभाविक रूप से इस दृष्टिकोण का उपयोग कर सकता है। एक स्पष्ट द्वि-आयामी सरणी के साथ transitions अवस्था-संक्रमण तालिका के लिए, प्रोग्राम इस दृष्टिकोण का उपयोग करता है:

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


void nop(int const c) {}


void print(int const c) {
  putchar(c);
}


struct Branch {
  enum State const next_state;
  void (*action)(int);
};


struct Branch const transitions[3][3] = {
  //   newline         whitespace         other             Inputs/States
  {{BEFORE,   &nop}, {BEFORE, &nop}, {INSIDE, &print}},  // before
  {{BEFORE, &print}, {AFTER,  &nop}, {INSIDE, &print}},  // inside
  {{BEFORE, &print}, {AFTER,  &nop}, {AFTER,    &nop}}   // after
};


void step(enum State* const s, int const c) {
  int const row = (*s == BEFORE) ? 0 : (*s == INSIDE) ? 1 : 2;
  int const column = (c == '\n') ? 0 : isspace(c) ? 1 : 2;
  struct Branch const* const b = &transitions[row][column];
  *s = b->next_state;
  b->action(c);
}


int main(void) {
  int c;
  enum State s = BEFORE;

  while ((c = getchar()) != EOF) {
    step(&s, c);
  }

  return 0;
}

ऑब्जेक्ट ओरिएंटेड

यदि कार्यान्वयन लैंग्वेज ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग का समर्थन करती है, तो प्रोग्राम का सरल पुनर्रचना ऑटोमेटन को ऑब्जेक्ट में एनकैप्सुलेशन (कंप्यूटर विज्ञान) करना है, इस प्रकार इसके कार्यान्वयन विवरण छिपाना है। ऑब्जेक्ट-ओरिएंटेड शैली का उपयोग करके C++ में प्रोग्राम इस तरह दिख सकता है:

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


struct Branch {
  enum State const next_state;
  void (*action)(int);
};


class StateMachine {
  public:
    StateMachine();
    void feedChar(int);

  protected:
    static void nop(int);
    static void print(int);

  private:
    enum State _state;
    static struct Branch const _transitions[3][3];
};


StateMachine::StateMachine(): _state(BEFORE) {}


void StateMachine::feedChar(int const c) {
  int const row = (_state == BEFORE) ? 0 : (_state == INSIDE) ? 1 : 2;
  int const column = (c == '\n') ? 0 : isspace(c) ? 1 : 2;
  struct Branch const* const b = &_transitions[row][column];
  _state = b->next_state;
  b->action(c);
}


void StateMachine::nop(int const c) {}


void StateMachine::print(int const c) {
  putchar(c);
}


struct Branch const StateMachine::_transitions[3][3] = {
  //   newline         whitespace         other             Inputs/States
  {{BEFORE,   &nop}, {BEFORE, &nop}, {INSIDE, &print}},  // before
  {{BEFORE, &print}, {AFTER,  &nop}, {INSIDE, &print}},  // inside
  {{BEFORE, &print}, {AFTER,  &nop}, {AFTER,    &nop}}   // after
};


int main() {
  int c;
  StateMachine m;

  while ((c = getchar()) != EOF) {
    m.feedChar(c);
  }

  return 0;
}

टिप्पणी। — लेख के विषय, इनपुट/आउटपुट से सीधे संबंधित न होने वाले परिवर्तनों को कम करने के लिए getchar और putchar C (प्रोग्रामिंग लैंग्वेज) की मानक लाइब्रेरी के फ़ंक्शंस का उपयोग किया जा रहा है।

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

#include <ctype.h>
#include <stdio.h>

class StateMachine;


class State {
  public:
    virtual void feedChar(StateMachine*, int) const = 0;
};


class Before: public State {
  public:
    static State const* instantiate();
    virtual void feedChar(StateMachine*, int) const override;

  protected:
    Before() = default;

  private:
    static State const* _instance;
};


class Inside: public State {
  public:
    static State const* instantiate();
    virtual void feedChar(StateMachine*, int) const override;

  protected:
    Inside() = default;

  private:
    static State const* _instance;
};


class After: public State {
  public:
    static State const* instantiate();
    virtual void feedChar(StateMachine*, int) const override;

  protected:
    After() = default;

  private:
    static State const* _instance;
};


class StateMachine {
  public:
    StateMachine();
    void feedChar(int);

  protected:
    void setState(State const*);

  private:
    State const* _state;
    friend class Before;
    friend class Inside;
    friend class After;
};


State const* Before::instantiate() {
  if (!_instance) {
    _instance = new Before;
  }

  return _instance;
}


void Before::feedChar(StateMachine* const m, int const c) const {
  if (!isspace(c)) {
    putchar(c);
    m->setState(Inside::instantiate());
  }
}


State const* Before::_instance = nullptr;


State const* Inside::instantiate() {
  if (!_instance) {
    _instance = new Inside;
  }

  return _instance;
}


void Inside::feedChar(StateMachine* const m, int const c) const {
  if (c == '\n') {
    putchar(c);
    m->setState(Before::instantiate());
  } else if (isspace(c)) {
    m->setState(After::instantiate());
  } else {
    putchar(c);
  }
}


State const* Inside::_instance = nullptr;


State const* After::instantiate() {
  if (!_instance) {
    _instance = new After;
  }

  return _instance;
}


void After::feedChar(StateMachine* const m, int const c) const {
  if (c == '\n') {
    putchar(c);
    m->setState(Before::instantiate());
  }
}


State const* After::_instance = nullptr;


StateMachine::StateMachine(): _state(Before::instantiate()) {}


void StateMachine::feedChar(int const c) {
  _state->feedChar(this, c);
}


void StateMachine::setState(State const* const s) {
  _state = s;
}


int main() {
  int c;
  StateMachine m;

  while ((c = getchar()) != EOF) {
    m.feedChar(c);
  }

  return 0;
}

स्वचालन और ऑटोमेटा

ऑटोमेटा-आधारित प्रोग्रामिंग वास्तव में स्वचालन के क्षेत्र में पाई जाने वाली प्रोग्रामिंग आवश्यकताओं से काफी मेल खाती है।

एक उत्पादन चक्र सामान्यतः इस प्रकार तैयार किया जाता है:

  • इनपुट डेटा (कैप्टर्स से) के अनुसार चरणों का क्रम;
  • वर्तमान चरण के आधार पर की जाने वाली क्रियाओं का सेट।

विभिन्न समर्पित प्रोग्रामिंग लैंग्वेज ऐसे मॉडल को अधिक या कम परिष्कृत तरीकों से व्यक्त करने की अनुमति देती हैं।

स्वचालन प्रोग्राम

ऊपर प्रस्तुत उदाहरण इस दृश्य के अनुसार निम्नलिखित छद्म कोड में व्यक्त किया जा सकता है ('सेट' तर्क चर को सक्रिय करता है, 'रीसेट' तर्क चर को निष्क्रिय करता है, ':' चर निर्दिष्ट करता है, और '=' समानता के लिए परीक्षण करता है):

newline: '\n'
whitespace: ('\t', '\n', '\v', '\f', '\r', ' ')
states: (before, inside, after)


setState(c) {
  if before and (c != newline and c not in whitespace) then set inside
  if inside then (if c in whitespace then set after else if c = newline then set before)
  if after and c = newline then set before
}


doAction(c) {
  if before and (c != newline and c not in whitespace) then write(c)
  if inside and c not in whitespace then write(c)
  if after and c = newline then write(c)
}


cycle {
  set before

  loop until (c: readCharacter) = EOL {
    setState(c)
    doAction(c)
  }
}

एक तरफ चक्र की प्रगति को व्यक्त करने वाली दिनचर्या का पृथक्करण, और दूसरी तरफ वास्तविक क्रिया (इनपुट और आउटपुट का मिलान) स्पष्ट और सरल कोड की अनुमति देता है।

घटनाएँ

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

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

   s:stage c:condition
   
   s1
   |
   |-c2
   |
   s2
   |
   ----------
   | |
   |-c31 |-c32
   | |
  s31 s32
   | |
   |-c41 |-c42
   | |
   ----------
   |
   s 4

अनुप्रयोग

ऑटोमेटा-आधारित प्रोग्रामिंग का व्यापक रूप से शाब्दी विश्लेषण और वाक्यविन्यास विश्लेषण में उपयोग किया जाता है।[1]

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

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

कुछ प्रोग्रामिंग लैंग्वेज के शब्दार्थ का वर्णन करने के लिए ऑटोमेटा (चरण और स्थिति) के संदर्भ में सोचने का भी उपयोग किया जा सकता है। उदाहरण के लिए, रिफ़ल लैंग्वेज में लिखे गए प्रोग्राम के निष्पादन को तथाकथित अमूर्त रिफ़ल मशीन के चरणों के अनुक्रम के रूप में वर्णित किया गया है; मशीन की स्थिति एक दृश्य है (चर के बिना यादृच्छिक रिफ़ल अभिव्यक्ति)।

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

अलेक्जेंडर ओलोंग्रेन ने अपनी पुस्तक में[2] प्रोग्रामिंग लैंग्वेज के शब्दार्थ विवरण की तथाकथित वियना विधि की व्याख्या करता है जो पूरी तरह से औपचारिक ऑटोमेटा पर आधारित है।

एसटीएटी प्रणाली [1] ऑटोमेटा-आधारित दृष्टिकोण का उपयोग करने का अच्छा उदाहरण है; इस प्रणाली में, अन्य सुविधाओं के अतिरिक्त, एसटीएटीएल नामक सन्निहित लैंग्वेज सम्मिलित है जो पूरी तरह से ऑटोमेटा-उन्मुख है।

इतिहास

ऑटोमेटा-आधारित तकनीकों का व्यापक रूप से उन डोमेन में उपयोग किया गया जहां ऑटोमेटा सिद्धांत पर आधारित एल्गोरिदम हैं, जैसे औपचारिक लैंग्वेज विश्लेषण।[1]

इस पर प्रारंभिक पत्रों में से एक जॉनसन एट अल., 1968 द्वारा लिखित है।[3]

एक सामान्य तकनीक के रूप में ऑटोमेटा-आधारित प्रोग्रामिंग का सबसे पहला उल्लेख पीटर नौर, 1963 के पेपर में पाया जाता है।[4] लेखक इस तकनीक को ट्यूरिंग मशीन दृष्टिकोण कहते हैं, हालाँकि पेपर में कोई वास्तविक ट्यूरिंग मशीन नहीं दी गई है; इसके अतिरिक्त, चरणों और अवस्थाओं पर आधारित तकनीक का वर्णन किया गया है।

आदेशसूचक और प्रक्रियात्मक प्रोग्रामिंग के साथ तुलना

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

  • सभी चरों के मान और गतिशील मेमोरी में संग्रहीत जानकारी;
  • रजिस्टरों में संग्रहीत मान;
  • स्टैक सामग्री (स्थानीय चर के मान और वापसी एड्रेस सहित);
  • निर्देश सूचक का वर्तमान मान।

इन्हें स्पष्ट भाग (जैसे चर में संग्रहीत मान) और अंतर्निहित भाग (वापसी एड्रेस और निर्देश सूचक) में विभाजित किया जा सकता है।

ऐसा कहने के बाद, ऑटोमेटा-आधारित प्रोग्राम स्थिति आदेशसूचक प्रोग्राम के विशेष स्थिति के रूप में माना जाता है, जिसमें अवस्था के निहित हिस्से को कम से कम किया जाता है। चरण कोड अनुभाग में प्रवेश करने के दो अलग-अलग क्षणों में ली गई पूरे प्रोग्राम की स्थिति केवल ऑटोमेटन स्थिति में भिन्न हो सकती है। इससे प्रोग्राम का विश्लेषण सरल हो जाता है.

ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग संबंध

ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग के सिद्धांत में, ऑब्जेक्ट को आंतरिक स्थिति कहा जाता है और वह संदेश प्राप्त करने, उन पर प्रतिक्रिया देने, अन्य ऑब्जेक्ट को संदेश भेजने और संदेश प्रबन्ध के दौरान अपनी आंतरिक स्थिति को बदलने में सक्षम है। अधिक व्यावहारिक शब्दावली में, किसी ऑब्जेक्ट की विधि को कॉल करना ऑब्जेक्ट को संदेश भेजने के समान ही माना जाता है।

इस प्रकार, एक ओर, ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग की ऑब्जेक्ट को ऑटोमेटा (या ऑटोमेटा के मॉडल) के रूप में माना जा सकता है, जिनकी स्थिति निजी क्षेत्रों का संयोजन है, और एक या अधिक तरीकों को चरण माना जाता है। ऐसी विधियों को न तो एक-दूसरे को कॉल करना चाहिए और न ही स्वयं, न तो प्रत्यक्ष और न ही अप्रत्यक्ष रूप से, अन्यथा ऑब्जेक्ट को ऑटोमेटा-आधारित तरीके से कार्यान्वित नहीं माना जा सकता है।

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

यह भी देखें

संदर्भ

  1. 1.0 1.1 Aho, Alfred V.; Ullman, Jeffrey D. (1973). The theory of parsing, translation and compiling. Vol. 1. Englewood Cliffs, N. J.: Prentice-Hall. ISBN 0-13-914564-8.
  2. Ollongren, Alexander (1974). Definition of programming languages by interpreting automata. London: Academic Press. ISBN 0-12-525750-3.
  3. Johnson, W. L.; Porter, J. H.; Ackley, S. I.; Ross, D. T. (1968). "Automatic generation of efficient lexical processors using finite state techniques". Comm ACM. 11 (12): 805–813. doi:10.1145/364175.364185. S2CID 17253809.
  4. Naur, Peter (September 1963). "The design of the GIER ALGOL compiler Part II". BIT Numerical Mathematics. 3 (3): 145–166. doi:10.1007/BF01939983. S2CID 189785656.
  5. "Automata-based programming" (PDF). Scientific and Technical Journal of Information Technologies, Mechanics and Optics (53). 2008.


बाहरी संबंध