समवर्ती बाधा तर्क प्रोग्रामिंग

समवर्ती बाधा तर्क प्रोग्रामिंग बाधा तर्क प्रोग्रामिंग का एक संस्करण है जिसका उद्देश्य मुख्य रूप से बाधा संतुष्टि समस्याओं को हल करने के बजाय (या इसके अलावा) समवर्ती प्रक्रियाओं को प्रोग्रामिंग करना है। बाधा तर्क प्रोग्रामिंग में लक्ष्यों का मूल्यांकन समवर्ती रूप से किया जाता है; एक समवर्ती प्रक्रिया इसलिए दुभाषिया (कंप्यूटिंग) द्वारा एक लक्ष्य के मूल्यांकन के रूप में क्रमादेशित है।

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

बाधा प्रबंधन नियमों को समवर्ती बाधा तर्क प्रोग्रामिंग के रूप में देखा जा सकता है, लेकिन समवर्ती प्रक्रियाओं के बजाय बाधा सरलीकरण या सॉल्वर प्रोग्रामिंग के लिए उपयोग किया जाता है।

विवरण

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

स्टोर में एक बाधा जोड़ना नियमित बाधा तर्क प्रोग्रामिंग की तरह किया जाता है। एक बाधा की जांच गार्ड (कंप्यूटिंग) के माध्यम से क्लॉज के माध्यम से की जाती है। गार्ड्स को सिंटैक्टिक एक्सटेंशन की आवश्यकता होती है: समवर्ती बाधा तर्क प्रोग्रामिंग का एक खंड इस रूप में लिखा जाता है H :- G | B कहाँ G एक बाधा है जिसे क्लॉज का गार्ड कहा जाता है। मोटे तौर पर बोलते हुए, इस क्लॉज का एक नया संस्करण लक्ष्य में एक शाब्दिक को बदलने के लिए इस्तेमाल किया जा सकता है, अगर शाब्दिक के समीकरण के बाद बाधा स्टोर द्वारा गार्ड को शामिल किया जाता है और क्लॉज हेड को इसमें जोड़ा जाता है। इस नियम की सटीक परिभाषा अधिक जटिल है, और नीचे दी गई है।

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

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

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

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

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

समवर्ती और गैर-समवर्ती तर्क प्रोग्रामिंग के बीच अंतर का तीसरा प्रभाव यह है कि एक लक्ष्य को एक खंड के नए संस्करण के शीर्ष के बराबर किया जाता है। क्रियात्मक रूप से, यह जाँच कर किया जाता है कि क्या सिर में चर को इस तरह से समान किया जा सकता है कि सिर लक्ष्य के बराबर है। यह नियम कंस्ट्रेंट लॉजिक प्रोग्रामिंग के संगत नियम से भिन्न है जिसमें यह केवल वेरिएबल = टर्म के रूप में कंस्ट्रेंट जोड़ने की अनुमति देता है, जहां वेरिएबल एक प्रमुख है। इस सीमा को दिशात्मकता के एक रूप के रूप में देखा जा सकता है, जिसमें लक्ष्य और क्लॉज हेड को अलग-अलग व्यवहार किया जाता है।

संक्षेप में, नियम बता रहा है कि क्या एक नया संस्करण है H:-G|B एक लक्ष्य को फिर से लिखने के लिए एक खंड का उपयोग किया जा सकता है A इस प्रकार है। सबसे पहले, यह जाँच की जाती है कि क्या A और H एक ही विधेय है। दूसरा, यह जाँचा जाता है कि क्या समीकरण करने का कोई तरीका मौजूद है $A$ साथ $H$ वर्तमान बाधा स्टोर दिया गया; नियमित लॉजिक प्रोग्रामिंग के विपरीत, यह एकतरफा एकीकरण के तहत किया जाता है, जो केवल सिर के एक चर को एक शब्द के बराबर होने की अनुमति देता है। तीसरा, गार्ड को कंस्ट्रेंट स्टोर से प्रवेश और दूसरे चरण में उत्पन्न समीकरणों के लिए जाँच की जाती है; गार्ड में ऐसे वेरिएबल्स हो सकते हैं जिनका क्लॉज हेड में उल्लेख नहीं किया गया है: इन वेरिएबल्स की व्याख्या अस्तित्वगत रूप से की जाती है। एक लक्ष्य को बदलने के लिए एक खंड के एक नए संस्करण की प्रयोज्यता को निर्धारित करने के लिए इस पद्धति को संक्षेप में निम्नानुसार व्यक्त किया जा सकता है: वर्तमान बाधा स्टोर में यह शामिल है कि सिर और गार्ड के चर का मूल्यांकन मौजूद है जैसे कि सिर के बराबर है लक्ष्य और गार्ड शामिल है। व्यवहार में, अपूर्णता को अपूर्ण विधि से जांचा जा सकता है।

समवर्ती तर्क प्रोग्रामिंग के सिंटैक्स और सिमेंटिक्स का एक विस्तार एटॉमिक टेल है। जब दुभाषिया एक खंड का उपयोग करता है, तो उसके गार्ड को बाधा स्टोर में जोड़ा जाता है। हालांकि, शरीर की बाधाओं को भी जोड़ा गया है। इस क्लॉज के प्रति प्रतिबद्धता के कारण, दुभाषिया पीछे नहीं हटता है यदि शरीर की बाधाएँ स्टोर के साथ असंगत हैं। एटॉमिक टेल के उपयोग से इस स्थिति से बचा जा सकता है, जो एक प्रकार है जिसमें खंड में एक प्रकार का दूसरा गार्ड होता है जिसे केवल स्थिरता के लिए जांचा जाता है। ऐसा उपवाक्य लिखा है H :- G:D|B. इस उपवाक्य का प्रयोग केवल शाब्दिक पुनर्लेखन के लिए किया जाता है G बाधा स्टोर द्वारा प्रवेश किया जाता है और D इसके अनुरूप है। इस मामले में दोनों G और D बाधा स्टोर में जोड़े जाते हैं।

इतिहास

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

यह भी देखें

• करी (प्रोग्रामिंग भाषा) , एक लॉजिक फंक्शनल प्रोग्रामिंग लैंग्वेज, जो प्रोग्रामिंग समवर्ती सिस्टम [1] की अनुमति देती है।
• टूनटॉक
• जानूस (समवर्ती बाधा प्रोग्रामिंग भाषा)
• ऐलिस (प्रोग्रामिंग भाषा)

संदर्भ

• Marriott, Kim; Peter J. Stuckey (1998). Programming with constraints: An introduction. MIT Press. ISBN 0-262-13341-5
• Frühwirth, Thom; Slim Abdennadher (2003). Essentials of constraint programming. Springer. ISBN 3-540-67623-6
• Jaffar, Joxan; Michael J. Maher (1994). "Constraint logic programming: a survey". Journal of Logic Programming. 19/20: 503–581. doi:10.1016/0743-1066(94)90033-7.

Specific