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

बाधा तर्क प्रोग्रामिंग बाधा प्रोग्रामिंग का एक रूप है, जिसमें बाधा संतुष्टि से अवधारणाओं को शामिल करने के लिए तर्क प्रोग्रामिंग को बढ़ाया जाता है। एक बाधा तर्क कार्यक्रम एक तर्क कार्यक्रम है जिसमें खंडों के शरीर में बाधाएं होती हैं। एक बाधा सहित एक खंड का एक उदाहरण है A(X,Y) :- X+Y>0, B(X), C(Y). इस खंड में, X+Y>0 एक बाधा है; A(X,Y), B(X), और C(Y) शाब्दिक (गणितीय तर्क) हैं जैसा कि नियमित तर्क प्रोग्रामिंग में होता है। यह खंड एक शर्त बताता है जिसके तहत बयान A(X,Y) रखती है: X+Y शून्य से बड़ा है और दोनों B(X) और C(Y) सच हैं।

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

सिंहावलोकन

औपचारिक रूप से, बाधा तर्क कार्यक्रम नियमित तर्क कार्यक्रमों की तरह होते हैं, लेकिन खंड के शरीर में नियमित तर्क प्रोग्रामिंग शाब्दिक के अलावा बाधाएं हो सकती हैं। उदहारण के लिए, X>0 एक बाधा है, और निम्नलिखित बाधा तर्क कार्यक्रम के अंतिम खंड में शामिल है।

B(X,1):- X<0.
B(X,Y):- X=1, Y>0.
A(X,Y):- X>0, B(X,Y).

नियमित लॉजिक प्रोग्रामिंग की तरह, एक लक्ष्य का मूल्यांकन करना जैसे A(X,1) के साथ अंतिम खंड के शरीर का मूल्यांकन करने की आवश्यकता है Y=1. नियमित लॉजिक प्रोग्रामिंग की तरह, इसके बदले में लक्ष्य को साबित करने की आवश्यकता होती है B(X,1). नियमित लॉजिक प्रोग्रामिंग के विपरीत, इसके लिए संतुष्ट होने के लिए एक बाधा की भी आवश्यकता होती है: X>0, अंतिम खंड के शरीर में बाधा (नियमित तर्क प्रोग्रामिंग में, X> 0 को तब तक साबित नहीं किया जा सकता जब तक कि X पूरी तरह से जमीनी अवधि के लिए बाध्य न हो और यदि ऐसा नहीं है तो कार्यक्रम का निष्पादन विफल हो जाएगा)।

जब बाधा का सामना करना पड़ता है तो एक बाधा संतुष्ट होती है या नहीं यह हमेशा निर्धारित नहीं किया जा सकता है। इस मामले में, उदाहरण के लिए, का मूल्य X अंतिम खंड का मूल्यांकन होने पर निर्धारित नहीं होता है। नतीजतन, विवशता X>0 इस बिंदु पर संतुष्ट नहीं है और न ही इसका उल्लंघन किया गया है। के मूल्यांकन में आगे बढ़ने के बजाय B(X,1) और फिर जांचना कि क्या परिणामी मान X बाद में सकारात्मक है, दुभाषिया बाधा को संग्रहीत करता है X>0 और फिर के मूल्यांकन में आगे बढ़ता है B(X,1); इस तरह, दुभाषिया बाधा के उल्लंघन का पता लगा सकता है X>0 मूल्यांकन के दौरान B(X,1)के मूल्यांकन की प्रतीक्षा करने के बजाय, यदि ऐसा है तो तुरंत पीछे हटें B(X,1) समाप्त करने के लिए।

सामान्य तौर पर, एक बाधा तर्क कार्यक्रम का मूल्यांकन एक नियमित तर्क कार्यक्रम के रूप में होता है। हालाँकि, मूल्यांकन के दौरान आने वाली बाधाओं को एक सेट में रखा जाता है जिसे एक बाधा स्टोर कहा जाता है। एक उदाहरण के रूप में, लक्ष्य का मूल्यांकन A(X,1) के साथ पहले खंड के शरीर का मूल्यांकन करके आगे बढ़ता है Y=1; यह मूल्यांकन जोड़ता है X>0 बाधा स्टोर के लिए और लक्ष्य की आवश्यकता है B(X,1) सिद्ध होना। इस लक्ष्य को सिद्ध करने का प्रयास करते समय प्रथम उपवाक्य का प्रयोग किया जाता है परन्तु उसका मूल्यांकन जुड़ जाता है X<0 बाधा स्टोर के लिए। यह जोड़ कंस्ट्रेंट स्टोर को असंतोषजनक बनाता है। दुभाषिया फिर पीछे हट जाता है, बाधा स्टोर से अंतिम जोड़ को हटा देता है। दूसरे खंड का मूल्यांकन जोड़ता है X=1 और Y>0 बाधा स्टोर के लिए। चूंकि कंस्ट्रेंट स्टोर संतोषजनक है और साबित करने के लिए कोई अन्य शाब्दिक नहीं बचा है, दुभाषिया समाधान के साथ रुक जाता है X=1, Y=1.

शब्दार्थ

बाधा तर्क कार्यक्रमों के शब्दार्थ को एक आभासी दुभाषिया के संदर्भ में परिभाषित किया जा सकता है जो एक जोड़ी बनाए रखता है $\langle G,S\rangle$ निष्पादन के दौरान। इस जोड़ी के पहले तत्व को वर्तमान लक्ष्य कहा जाता है; दूसरे तत्व को कंस्ट्रेंट स्टोर कहा जाता है। वर्तमान लक्ष्य में वे अक्षर शामिल हैं जिन्हें दुभाषिया सिद्ध करने का प्रयास कर रहा है और इसमें कुछ बाधाएँ भी हो सकती हैं जिन्हें वह संतुष्ट करने का प्रयास कर रहा है; कंस्ट्रेंट स्टोर में वे सभी कंस्ट्रेंट शामिल हैं जिन्हें दुभाषिया ने अब तक संतोषजनक माना है।

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

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

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

दुभाषिया ने लक्ष्य को साबित कर दिया है जब वर्तमान लक्ष्य खाली है और बाधा स्टोर को असंतोषजनक नहीं पाया गया है। निष्पादन का परिणाम (सरलीकृत) बाधाओं का वर्तमान सेट है। इस सेट में बाधाएँ शामिल हो सकती हैं जैसे $X=2$ वह एक विशिष्ट मूल्य के लिए चर को बल देता है, लेकिन इसमें बाधाएं भी शामिल हो सकती हैं $X>2$ जो केवल चरों को एक विशिष्ट मान दिए बिना बाध्य करता है।

औपचारिक रूप से, बाधा तर्क प्रोग्रामिंग के शब्दों को व्युत्पत्तियों के संदर्भ में परिभाषित किया गया है। एक संक्रमण जोड़े लक्ष्य/स्टोर की एक जोड़ी है, नोट किया गया $\langle G,S\rangle \rightarrow \langle G',S'\rangle$. ऐसा जोड़ा राज्य से जाने की संभावना बताता है $\langle G,S\rangle$ कहना $\langle G',S'\rangle$. ऐसा संक्रमण तीन संभावित मामलों में संभव है:

• का एक तत्व G एक बाधा है C, $G'=G\backslash \{C\}$ और $S'=S\cup \{C\}$; दूसरे शब्दों में, एक बाधा को लक्ष्य से बाधा स्टोर में ले जाया जा सकता है
• का एक तत्व G शाब्दिक है $L(t_{1},\ldots ,t_{n})$, वहाँ एक खंड मौजूद है, जो नए चर का उपयोग करके फिर से लिखा गया है $L(t_{1}',\ldots ,t_{n}'):-B$, $G'$ है G साथ $L(t_{1},\ldots ,t_{n})$ द्वारा प्रतिस्थापित $t_{1}=t_{1}',\ldots ,t_{n}=t_{n}',B$, और $S'=S$; दूसरे शब्दों में, एक शाब्दिक को एक खंड के नए संस्करण के शरीर द्वारा प्रतिस्थापित किया जा सकता है, जिसमें सिर में समान विधेय होता है, नए संस्करण के शरीर और लक्ष्य के शब्दों की उपरोक्त समानताएं जोड़ते हुए
• S और $S'$ विशिष्ट बाधा शब्दार्थ के अनुसार समतुल्य हैं

संक्रमण का एक क्रम एक व्युत्पत्ति है। एक लक्ष्य G साबित किया जा सकता है अगर वहाँ से कोई व्युत्पत्ति मौजूद है $\langle G,\emptyset \rangle$ को $\langle \emptyset ,S\rangle$ कुछ संतोषजनक बाधा स्टोर के लिए S. यह शब्दार्थ एक दुभाषिया के संभावित विकास को औपचारिक रूप देता है जो मनमाने ढंग से प्रक्रिया के लक्ष्य का शाब्दिक चयन करता है और शाब्दिक को बदलने के लिए खंड। दूसरे शब्दों में, इस शब्दार्थ के तहत एक लक्ष्य सिद्ध होता है यदि शाब्दिक और खंडों के विकल्पों का एक क्रम मौजूद होता है, संभवतः कई लोगों के बीच, जो एक खाली लक्ष्य और संतोषजनक स्टोर की ओर ले जाता है।

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

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

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

दो शाब्दिक शब्दों की जोड़ीवार समानता को अक्सर संक्षिप्त रूप से निरूपित किया जाता है $L(t_{1},\ldots ,t_{n})=L(t_{1}',\ldots ,t_{n}')$: यह बाधाओं के लिए एक आशुलिपि है $t_{1}=t_{1}',\ldots ,t_{n}=t_{n}'$. बाधा तर्क प्रोग्रामिंग के लिए शब्दार्थ का एक सामान्य संस्करण जोड़ता है $L(t_{1},\ldots ,t_{n})=L(t_{1}',\ldots ,t_{n}')$ लक्ष्य के बजाय सीधे बाधा स्टोर में।

नियम और शर्तें

शब्दों की विभिन्न परिभाषाओं का उपयोग किया जाता है, जिससे विभिन्न प्रकार की बाधा तर्क प्रोग्रामिंग उत्पन्न होती है: वृक्षों, वास्तविक या परिमित डोमेन पर। एक प्रकार की बाधा जो हमेशा मौजूद रहती है वह शर्तों की समानता है। ऐसी बाध्यताएँ आवश्यक हैं क्योंकि दुभाषिया जोड़ता है t1=t2 लक्ष्य के लिए जब भी एक शाब्दिक P(...t1...) क्लॉज फ्रेश वैरिएंट की बॉडी से रिप्लेस किया गया है जिसका हेड है P(...t2...).

पेड़ की शर्तें

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

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

यदि दो पदों में से एक एक चर है, तो चर का एकमात्र अनुमत मान दूसरा पद हो सकता है। नतीजतन, अन्य शब्द चर को वर्तमान लक्ष्य और बाधा स्टोर में बदल सकते हैं, इस प्रकार व्यावहारिक रूप से चर को विचार से हटा सकते हैं। स्वयं के साथ एक चर की समानता के विशेष मामले में, बाधा को हमेशा संतुष्ट के रूप में हटाया जा सकता है।

बाधा संतुष्टि के इस रूप में, चर मान पद हैं।

असली

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

सटीक होने के लिए, पद चर और वास्तविक स्थिरांक पर व्यंजक हैं। शर्तों के बीच समानता एक प्रकार की बाधा है जो हमेशा मौजूद रहती है, क्योंकि दुभाषिया निष्पादन के दौरान शर्तों की समानता उत्पन्न करता है। उदाहरण के तौर पर, यदि वर्तमान लक्ष्य का पहला अक्षर है A(X+1) और दुभाषिया ने एक खंड चुना है जो है A(Y-1):-Y=1 पुनर्लेखन के बाद चर है, वर्तमान लक्ष्य में जोड़े गए अवरोध हैं X+1=Y-1 और $Y=1$. फ़ंक्शन प्रतीकों के लिए उपयोग किए जाने वाले सरलीकरण के नियम स्पष्ट रूप से उपयोग नहीं किए जाते हैं: X+1=Y-1 केवल इसलिए असंतुष्ट नहीं है क्योंकि पहली अभिव्यक्ति का उपयोग करके बनाया गया है + और दूसरा उपयोग कर रहा है -.

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

यदि दो शब्दों में से कोई भी वास्तविक अभिव्यक्ति नहीं है, तो दो शब्दों की समानता को वृक्ष शर्तों के नियमों का उपयोग करके सरल बनाया जा सकता है। उदाहरण के लिए, यदि दो शब्दों में एक ही फ़ंक्शन प्रतीक और सबटर्म की संख्या है, तो उनकी समानता की बाधा को सबटर्म की समानता से बदला जा सकता है।

परिमित डोमेन

See also: Constraint satisfaction problem

बाधा तर्क प्रोग्रामिंग में प्रयुक्त बाधाओं की तीसरी श्रेणी परिमित डोमेन की है। चर के मान इस मामले में एक परिमित डोमेन से लिए गए हैं, जो अक्सर पूर्णांक संख्याओं के होते हैं। प्रत्येक चर के लिए, एक अलग डोमेन निर्दिष्ट किया जा सकता है: X::[1..5] उदाहरण के लिए इसका मतलब है कि का मूल्य X के बीच है 1 और 5. एक चर का क्षेत्र सभी मानों की गणना करके भी दिया जा सकता है जो एक चर ले सकता है; इसलिए, उपरोक्त डोमेन घोषणा भी लिखी जा सकती है X::[1,2,3,4,5]. डोमेन निर्दिष्ट करने का यह दूसरा तरीका उन डोमेन के लिए अनुमति देता है जो पूर्णांकों से बना नहीं है, जैसे कि X::[george,mary,john]. यदि एक चर का डोमेन निर्दिष्ट नहीं है, तो इसे भाषा में प्रतिनिधित्व करने योग्य पूर्णांकों का समूह माना जाता है। चरों के एक समूह को एक घोषणा का उपयोग करके एक ही डोमेन दिया जा सकता है [X,Y,Z]::[1..5].

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

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

बाधा स्टोर

कंस्ट्रेंट स्टोर में वे कंस्ट्रेंट होते हैं जिन्हें वर्तमान में संतोषजनक माना जाता है। यह माना जा सकता है कि नियमित तर्क प्रोग्रामिंग के लिए वर्तमान प्रतिस्थापन क्या है। जब केवल ट्री शर्तों की अनुमति होती है, तो कंस्ट्रेंट स्टोर में फॉर्म में कंस्ट्रेंट होते हैं t1=t2; इन बाधाओं को एकीकरण द्वारा सरल किया जाता है, जिसके परिणामस्वरूप फॉर्म की कमी होती है variable=term; ऐसी बाधाएं एक प्रतिस्थापन के बराबर हैं।

हालाँकि, बाधा स्टोर में प्रपत्र में बाधाएँ भी हो सकती हैं t1!=t2, यदि अंतर है != शर्तों के बीच की अनुमति है। जब वास्तविक या परिमित डोमेन पर बाधाओं की अनुमति दी जाती है, तो बाधा स्टोर में डोमेन-विशिष्ट बाधाएँ भी हो सकती हैं X+2=Y/2, वगैरह।

कंस्ट्रेंट स्टोर वर्तमान प्रतिस्थापन की अवधारणा को दो तरह से विस्तारित करता है। सबसे पहले, इसमें न केवल एक खंड के एक नए संस्करण के सिर के साथ एक शाब्दिक समानता से उत्पन्न बाधाएं शामिल हैं, बल्कि खंडों के शरीर की बाधाएं भी शामिल हैं। दूसरा, इसमें केवल प्रपत्र की बाधाएँ नहीं हैं variable=value लेकिन माना बाधा भाषा पर भी बाधाएं। जबकि एक नियमित लॉजिक प्रोग्राम के सफल मूल्यांकन का परिणाम अंतिम प्रतिस्थापन है, एक कंस्ट्रेंट लॉजिक प्रोग्राम का परिणाम अंतिम कंस्ट्रेंट स्टोर है, जिसमें फॉर्म वेरिएबल=वैल्यू का कंस्ट्रेंट हो सकता है लेकिन सामान्य रूप से मनमाना प्रतिबंध हो सकता है।

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

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

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

लेबलिंग

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

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

लेबलिंग शाब्दिक का दूसरा उपयोग वास्तव में उन चरों का मूल्यांकन निर्धारित करना है जो बाधा स्टोर को संतुष्ट करते हैं। शाब्दिक लेबलिंग के बिना, वेरिएबल्स को मान तभी दिए जाते हैं जब कंस्ट्रेंट स्टोर में फॉर्म का कंस्ट्रेंट होता है X=value और जब स्थानीय संगति एक चर के डोमेन को एक मान तक कम कर देती है। कुछ चरों पर शाब्दिक लेबलिंग इन चरों का मूल्यांकन करने के लिए बाध्य करता है। दूसरे शब्दों में, शाब्दिक लेबलिंग पर विचार करने के बाद, सभी चरों को एक मान निर्दिष्ट किया जाता है।

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

solve(X):-constraints(X), labeling(X)
constraints(X):- (all constraints of the CSP)

जब दुभाषिया लक्ष्य का मूल्यांकन करता है solve(args), यह वर्तमान लक्ष्य में पहले खंड के नए संस्करण के मुख्य भाग को रखता है। चूंकि पहला लक्ष्य है constraints(X'), दूसरे क्लॉज का मूल्यांकन किया जाता है, और यह ऑपरेशन सभी बाधाओं को वर्तमान लक्ष्य में और अंततः बाधा स्टोर में ले जाता है। शाब्दिक labeling(X') तब मूल्यांकन किया जाता है, जिससे बाधा भंडार के समाधान की तलाश की जाती है। चूंकि कंस्ट्रेंट स्टोर में मूल कंस्ट्रेंट संतुष्टि समस्या के बिल्कुल कंस्ट्रेंट होते हैं, इसलिए यह ऑपरेशन मूल समस्या के समाधान की तलाश करता है।

कार्यक्रम सुधार

इसकी दक्षता में सुधार के लिए दिए गए बाधा तर्क कार्यक्रम को सुधारा जा सकता है। पहला नियम यह है कि लेबलिंग लिटरल को तब रखा जाना चाहिए जब लेबल लिटरल पर अधिक से अधिक प्रतिबंध कंस्ट्रेंट स्टोर में जमा हो जाएं। जबकि सिद्धांत रूप में A(X):-labeling(X),X>0 के बराबर है A(X):-X>0,labeling(X), वह खोज जो तब की जाती है जब दुभाषिया लेबलिंग शाब्दिक का सामना करता है, एक बाधा स्टोर पर होता है जिसमें बाधा नहीं होती है X>0. नतीजतन, यह समाधान उत्पन्न कर सकता है, जैसे X=-1, जो बाद में इस बाधा को पूरा नहीं करने के लिए पाए गए। दूसरी ओर, दूसरे सूत्रीकरण में खोज तभी की जाती है जब बाधा पहले से ही बाधा भंडार में हो। नतीजतन, खोज केवल उन समाधानों को लौटाती है जो इसके अनुरूप हैं, इस तथ्य का लाभ उठाते हुए कि अतिरिक्त बाधाएं खोज स्थान को कम करती हैं।

एक दूसरा सुधार जो दक्षता में वृद्धि कर सकता है, खंड के शरीर में शाब्दिक से पहले बाधाओं को रखना है। दोबारा, A(X):-B(X),X>0 और A(X):-X>0,B(X) सिद्धांत रूप में समतुल्य हैं। हालाँकि, पहले को अधिक संगणना की आवश्यकता हो सकती है। उदाहरण के लिए, यदि बाधा स्टोर में बाधा है X<-2, दुभाषिया पुनरावर्ती मूल्यांकन करता है B(X) पहले मामले में; यदि यह सफल होता है, तो यह पता चलता है कि जोड़ते समय बाधा स्टोर असंगत है X>0. दूसरे मामले में, उस खंड का मूल्यांकन करते समय, दुभाषिया पहले जोड़ता है X>0 बाधा स्टोर में और फिर संभवतः मूल्यांकन करता है B(X). के अलावा के बाद बाधा दुकान के बाद से X>0 असंगत हो जाता है, का पुनरावर्ती मूल्यांकन B(X) बिल्कुल नहीं किया जाता है।

एक तीसरा सुधार जो दक्षता बढ़ा सकता है, वह अनावश्यक बाधाओं को जोड़ना है। यदि प्रोग्रामर जानता है (किसी भी तरह से) कि किसी समस्या का समाधान एक विशिष्ट बाधा को संतुष्ट करता है, तो वे उस बाधा को जल्द से जल्द बाधा स्टोर की असंगति पैदा करने के लिए शामिल कर सकते हैं। उदाहरण के लिए, यदि यह पहले से ज्ञात है कि का मूल्यांकन B(X) के लिए एक सकारात्मक मूल्य देगा X, प्रोग्रामर जोड़ सकता है X>0 किसी भी घटना से पहले B(X). उदहारण के लिए, A(X,Y):-B(X),C(X) लक्ष्य में विफल रहेगा A(-2,Z), लेकिन यह केवल उपलक्ष्य के मूल्यांकन के दौरान ही पता चला है B(X). दूसरी ओर, यदि उपरोक्त खंड द्वारा प्रतिस्थापित किया जाता है A(X,Y):-X>0,A(X),B(X), जैसे ही बाधा उत्पन्न होती है, दुभाषिया पीछे हट जाता है X>0 बाधा स्टोर में जोड़ा जाता है, जो मूल्यांकन से पहले होता है B(X) यहां तक ​​कि शुरू हो जाता है।

बाधा से निपटने के नियम

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

ए(एक्स) <=> बी(एक्स) | सी (एक्स)
ए (एक्स) ==> बी (एक्स) | सी (एक्स)

पहला नियम बताता है कि, अगर B(X) दुकान, बाधा द्वारा उलझा हुआ है A(X) के रूप में पुनः लिखा जा सकता है C(X). उदहारण के लिए, N*X>0 के रूप में पुनः लिखा जा सकता है X>0 अगर दुकान का तात्पर्य है N>0. प्रतीक <=> तर्क में समानता जैसा दिखता है, और बताता है कि पहली बाधा बाद के बराबर है। व्यवहार में, इसका तात्पर्य है कि पहली बाधा को बाद वाले से बदला जा सकता है।

इसके बजाय दूसरा नियम निर्दिष्ट करता है कि बाद की बाधा पहले का परिणाम है, यदि बीच में बाधा बाधा स्टोर से जुड़ी हुई है। नतीजतन, अगर A(X) बाधा स्टोर में है और B(X) तब बाधा स्टोर द्वारा प्रवेश किया जाता है C(X) स्टोर में जोड़ा जा सकता है। तुल्यता के मामले से अलग, यह एक जोड़ है और प्रतिस्थापन नहीं है: नया अवरोध जोड़ा जाता है लेकिन पुराना बना रहता है।

समानता कुछ बाधाओं को सरल लोगों के साथ बदलकर बाधा संग्रह को सरल बनाने की अनुमति देती है; विशेष रूप से, यदि एक तुल्यता नियम में तीसरी बाधा है true, और दूसरी बाधा दर्ज की जाती है, पहली बाधा बाधा स्टोर से हटा दी जाती है। अनुमान नई बाधाओं को जोड़ने की अनुमति देता है, जिससे बाधा स्टोर की असंगतता साबित हो सकती है, और आमतौर पर इसकी संतुष्टि को स्थापित करने के लिए आवश्यक खोज की मात्रा कम हो सकती है।

कंस्ट्रेंट हैंडलिंग नियमों के संयोजन में लॉजिक प्रोग्रामिंग क्लॉज का उपयोग कंस्ट्रेंट स्टोर की संतुष्टि की स्थापना के लिए एक विधि निर्दिष्ट करने के लिए किया जा सकता है। विधि के विभिन्न विकल्पों को लागू करने के लिए विभिन्न खंडों का उपयोग किया जाता है; निष्पादन के दौरान बाधा स्टोर को फिर से लिखने के लिए बाधा प्रबंधन नियमों का उपयोग किया जाता है। एक उदाहरण के रूप में, इकाई प्रसार के साथ बैकट्रैकिंग को इस तरह लागू किया जा सकता है। होने देना holds(L) एक प्रस्तावित खंड का प्रतिनिधित्व करता है, जिसमें सूची में शाब्दिक L उसी क्रम में हैं जैसे उनका मूल्यांकन किया जाता है। एल्गोरिथम को सही या गलत के लिए शाब्दिक निर्दिष्ट करने के विकल्प के लिए क्लॉज का उपयोग करके लागू किया जा सकता है, और प्रसार को निर्दिष्ट करने के लिए बाधाओं से निपटने के नियमों को लागू किया जा सकता है। ये नियम निर्दिष्ट करते हैं holds([l|L]) अगर हटाया जा सकता है l=true स्टोर से अनुसरण करता है, और इसे फिर से लिखा जा सकता है holds(L) अगर l=false दुकान से पीछा करता है। इसी प्रकार, holds([l]) द्वारा प्रतिस्थापित किया जा सकता है l=true. इस में उदाहरण के लिए, एक चर के लिए मान का चुनाव लॉजिक प्रोग्रामिंग के क्लॉज का उपयोग करके कार्यान्वित किया जाता है; हालाँकि, इसे डिसजंक्टिव कंस्ट्रेंट हैंडलिंग रूल्स या CHR नामक एक्सटेंशन का उपयोग करके बाधा से निपटने के नियमों में एन्कोड किया जा सकता है^∨.

बॉटम-अप मूल्यांकन

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

नीचे से ऊपर की मूल्यांकन रणनीति मूल्यांकन के दौरान अब तक साबित तथ्यों के सेट को बनाए रखती है। यह सेट प्रारंभ में खाली है। प्रत्येक चरण के साथ, मौजूदा तथ्यों के लिए एक प्रोग्राम क्लॉज लागू करके नए तथ्य निकाले जाते हैं, और सेट में जोड़े जाते हैं। उदाहरण के लिए, निम्नलिखित कार्यक्रम के नीचे के मूल्यांकन के लिए दो चरणों की आवश्यकता होती है:

ए (क्यू)।
बी (एक्स): - ए (एक्स)।

परिणामों का सेट प्रारंभ में खाली है। पहले कदम पर, A(q) एकमात्र खंड है जिसका शरीर सिद्ध किया जा सकता है (क्योंकि यह खाली है), और A(q) इसलिए परिणामों के वर्तमान सेट में जोड़ा जाता है। दूसरे चरण में, चूंकि A(q) साबित हो गया है, दूसरे खंड का उपयोग किया जा सकता है और B(q) परिणामों में जोड़ा जाता है। चूंकि से कोई अन्य परिणाम सिद्ध नहीं किया जा सकता है {A(q),B(q)}, निष्पादन समाप्त होता है।

ऊपर से नीचे के मूल्यांकन पर नीचे से ऊपर के मूल्यांकन का लाभ यह है कि व्युत्पत्तियों के चक्र एक अनंत लूप का उत्पादन नहीं करते हैं। ऐसा इसलिए है क्योंकि परिणामों के वर्तमान सेट में एक परिणाम जोड़ने से पहले से ही कोई प्रभाव नहीं पड़ता है। एक उदाहरण के रूप में, उपरोक्त कार्यक्रम में तीसरा खंड जोड़ने से शीर्ष-डाउन मूल्यांकन में व्युत्पत्तियों का एक चक्र उत्पन्न होता है:

ए (क्यू)।
बी (एक्स): - ए (एक्स)।
ए(एक्स):-बी(एक्स).

उदाहरण के लिए, लक्ष्य के सभी उत्तरों का मूल्यांकन करते समय A(X), टॉप-डाउन रणनीति निम्नलिखित व्युत्पत्तियों का उत्पादन करेगी:

ए (क्यू)
ए(क्यू):-बी(क्यू), बी(क्यू):-ए(क्यू), ए(क्यू)
ए(क्यू):-बी(क्यू), बी(क्यू):-ए(क्यू), ए(क्यू):-बी(क्यू), बी(क्यू):-ए(क्यू), ए(क्यू)

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

बॉटम-अप रणनीति में वही खामी नहीं है, क्योंकि जो परिणाम पहले ही प्राप्त हो चुके हैं, उनका कोई प्रभाव नहीं पड़ता है। उपरोक्त कार्यक्रम पर, नीचे-ऊपर की रणनीति जोड़ना शुरू हो जाती है A(q) परिणामों के सेट के लिए; दूसरे चरण में, B(X):-A(X) निकालने के लिए प्रयोग किया जाता है B(q); तीसरे चरण में, केवल वही तथ्य हैं जो वर्तमान परिणामों से प्राप्त किए जा सकते हैं A(q) और B(q), जो हालांकि पहले से ही परिणामों के सेट में हैं। नतीजतन, एल्गोरिथ्म बंद हो जाता है।

उपरोक्त उदाहरण में, केवल प्रयुक्त तथ्य ग्राउंड लिटरल थे। सामान्य तौर पर, प्रत्येक खंड जिसमें केवल शरीर में बाधाएँ होती हैं, एक तथ्य माना जाता है। उदाहरण के लिए, एक खंड A(X):-X>0,X<10 तथ्य भी माना जाता है। तथ्यों की इस विस्तारित परिभाषा के लिए, कुछ तथ्य समतुल्य हो सकते हैं, जबकि वाक्यात्मक रूप से समान नहीं। उदाहरण के लिए, A(q) के बराबर है A(X):-X=q और दोनों के बराबर हैं A(X):-X=Y, Y=q. इस समस्या को हल करने के लिए, तथ्यों को सामान्य रूप में अनुवादित किया जाता है जिसमें सिर में सभी अलग-अलग चरों का एक टपल होता है; दो तथ्य तब समतुल्य होते हैं यदि उनके शरीर सिर के चर पर समतुल्य होते हैं, अर्थात, इन चरों तक सीमित होने पर उनके समाधान के सेट समान होते हैं।

जैसा कि वर्णन किया गया है, बॉटम-अप दृष्टिकोण में उन परिणामों पर विचार न करने का लाभ है जो पहले ही प्राप्त हो चुके हैं। हालाँकि, यह अभी भी उन परिणामों को प्राप्त कर सकता है जो उनमें से किसी के बराबर नहीं होने के बावजूद पहले से प्राप्त किए गए हैं। एक उदाहरण के रूप में, निम्न प्रोग्राम का नीचे से ऊपर का मूल्यांकन अनंत है:

A(0).
A(X):-X>0.
A(X):-X=Y+1, A(Y).

बॉटम-अप मूल्यांकन एल्गोरिथम सबसे पहले इसे प्राप्त करता है A(X) के लिए सत्य है X=0 और X>0. दूसरे चरण में, तीसरे खंड के साथ पहला तथ्य व्युत्पत्ति के लिए अनुमति देता है A(1). तीसरे चरण में, A(2) व्युत्पन्न है, आदि। हालाँकि, ये तथ्य पहले से ही इस तथ्य से उलझे हुए हैं A(X) किसी भी अऋणात्मक के लिए सत्य है X. परिणामों के वर्तमान सेट में जोड़े जाने वाले अनिवार्य तथ्यों की जाँच करके इस कमी को दूर किया जा सकता है। यदि नया परिणाम सेट द्वारा पहले से ही उलझा हुआ है, तो उसे इसमें नहीं जोड़ा जाता है। चूंकि तथ्यों को खंड के रूप में संग्रहीत किया जाता है, संभवतः स्थानीय चर के साथ, उनके सिर के चर पर प्रवेश प्रतिबंधित है।

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

Main article: Concurrent constraint logic programming

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

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

अनुप्रयोग

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

इतिहास

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

यह भी देखें

• [[एसडब्ल्यूआई-प्रोलॉग]]
• एनबीआर प्रस्तावना (उर्फ सीएलपी (बीएनआर))
• बाधा प्रबंधन नियम
• सीआओ (प्रोग्रामिंग भाषा)
• सीएलपी (आर)
• ओज़ (प्रोग्रामिंग भाषा)
• ग्रहण
• जीएनयू प्रोलॉग
• SWI-प्रोलॉग

संदर्भ

• Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7. ISBN 1-55860-890-7
• Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press. ISBN 0-521-82583-0. ISBN 0-521-82583-0
• 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. 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.
• Colmerauer, Alain (1987). "Opening the Prolog III Universe". Byte. August.