तर्क प्रोग्रामिंग का सिंटैक्स और शब्दार्थ

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

घोषणात्मक तर्क कार्यक्रम पूरी तरह से प्रपत्र के नियमों से युक्त होते हैं

H :- B1, ..., BN.

ऐसे प्रत्येक नियम को एक निहितार्थ के रूप में पढ़ा जा सकता है:

$B_{1}\land \ldots \land B_{n}\rightarrow H$

जिसका अर्थ है यदि प्रत्येक $B_{i}$, $H$ ट्रूथ है । तो फिर लॉजिक प्रोग्राम उन तथ्यों के समूह की गणना करते हैं जो उनके नियमों द्वारा निहित हैं।

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

डेटालॉग

Main article: डेटालॉग

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

सिंटेक्स

डेटालॉग प्रोग्राम में नियमों की एक सूची होती है। यदि स्थिरांक और चर क्रमशः स्थिरांक और चर के दो गणनीय सेट हैं और संबंध विधेय चर का एक गणनीय सेट है, तो निम्नलिखित BNF ग्रामर डेटालॉग प्रोग्राम की संरचना को व्यक्त करता है:

<program> ::= <rule> <program> | ""
<rule> ::= <atom> ":-" <atom-list> "."
<atom> ::= <relation> "(" <term-list> ")"
<atom-list> ::= <atom> | <atom> "," <atom-list> | ""
<term> ::= <constant> | <variable>
<term-list> ::= <term> | <term> "," <term-list> | ""

परमाणुओं को शाब्दिक भी कहा जाता है। लिट्रल. के बाईं ओर परमाणु को नियम का :- हेड कहा जाता है; दाहिनी ओर के परमाणु बॉडी हैं। प्रत्येक डेटालॉग प्रोग्राम को इस शर्त को पूरा करना होगा कि नियम के शीर्ष में दिखाई देने वाला प्रत्येक चर मुख्य भाग में भी दिखाई देता है।

खाली निकाय वाले नियमों को तथ्य कहा जाता है। उदाहरण के लिए, निम्नलिखित नियम एक तथ्य है:

r(x) :- .

सिंटैक्टिक शुगर

तर्क प्रोग्रामिंग के कई कार्यान्वयन बिना तथ्यों को लिखने की अनुमति देने के लिए उपरोक्त व्याकरण का विस्तार करते हैं :-, जैसे:

r(x).

कई लोग बिना कोष्ठक के 0-एरी संबंध लिखने की भी अनुमति देते हैं, जैसे:

p :- q.

ये केवल संक्षिप्त रूप (वाक्यात्मक शर्करा) हैं; उनका कार्यक्रम के शब्दार्थ पर कोई प्रभाव नहीं पड़ता है।

उदाहरण

निम्नलिखित प्रोग्राम संबंध की गणना करता है path, जो संबंध का सकर्मक समापन है edge.

edge(x, y).
edge(y, z).
path(A, B) :- 
  edge(A, B).
path(A, C) :- 
  path(A, B), 
  edge(B, C).

शब्दार्थ

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

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

मॉडल सैद्धांतिक

डेटालॉग कार्यक्रम की हेरब्रांड व्याख्याओं का हस्से आरेख

e(x, y).
e(y, z).
p(A, B) :-
  e(A, B).
p(A, C) :- 
  p(A, B),
  e(B, C).

व्याख्या $M$ न्यूनतम हेरब्रांड मॉडल है। इसके ऊपर की सभी व्याख्याएँ भी मॉडल हैं, इसके नीचे की सभी व्याख्याएँ मॉडल नहीं हैं।

एक नियम को ग्राउंड कहा जाता है यदि उसके सभी परमाणु (सिर और शरीर) ग्राउंड हैं। एक जमीनी नियम आर₁ एक अन्य नियम R का जमीनी उदाहरण है₂ यदि आर₁ R में सभी चरों के लिए स्थिरांकों के प्रतिस्थापन (तर्क) का परिणाम है₂.

डेटालॉग प्रोग्राम का हेरब्रांड बेस सभी ग्राउंड परमाणुओं का सेट है जिसे प्रोग्राम में दिखाई देने वाले स्थिरांक के साथ बनाया जा सकता है। एक व्याख्या (डेटाबेस उदाहरण के रूप में भी जाना जाता है) हेरब्रांड आधार का एक सबसेट है। एक व्याख्या में एक जमीनी परमाणु सत्य है I यदि यह का एक तत्व है I. एक व्याख्या में एक नियम सत्य है I यदि उस नियम के प्रत्येक बुनियादी उदाहरण के लिए, यदि मुख्य भाग में सभी खंड सत्य हैं I, तो नियम का शीर्ष भी सत्य है I.

डेटालॉग प्रोग्राम पी का एक मॉडल एक व्याख्या है I का P जिसमें P के सभी जमीनी तथ्य शामिल हैं, और P के सभी नियमों को सत्य बनाता है I. मॉडल-सैद्धांतिक शब्दार्थ बताता है कि डेटालॉग प्रोग्राम का अर्थ इसका न्यूनतम मॉडल (समान रूप से, इसके सभी मॉडलों का प्रतिच्छेदन) है।

उदाहरण के लिए, यह प्रोग्राम:

edge(x, y).
edge(y, z).
path(A, B) :- 
  edge(A, B).
path(A, C) :- 
  path(A, B), 
  edge(B, C).

यह हेरब्रांड ब्रह्मांड है: x, y, z और यह हेरब्रांड आधार: edge(x, x), edge(x, y), ..., edge(z, z), path(x, x), ..., path(z, z) और यह न्यूनतम हर्ब्रांड मॉडल: edge(x, y), edge(y, z), path(x, y), path(y, z), path(x, z)

निश्चित-बिंदु

होने देना I डेटालॉग प्रोग्राम पी की व्याख्याओं का सेट बनें, यानी, I = P(H), जहां H, P का हेरब्रांड आधार है और 'P' सत्ता स्थापित ऑपरेटर है। वह immediate consequence operator P के लिए निम्नलिखित मानचित्र है T से I को I: पी में प्रत्येक नियम के प्रत्येक ग्राउंड इंस्टेंस के लिए, यदि बॉडी में प्रत्येक क्लॉज इनपुट व्याख्या में है, तो ग्राउंड इंस्टेंस के प्रमुख को आउटपुट व्याख्या में जोड़ें। यह मानचित्र T उपसमुच्चय समावेशन द्वारा दिए गए आंशिक रूप से आदेशित सेट के संबंध में मोनोटोनिक फ़ंक्शन है T. नैस्टर-टार्स्की प्रमेय के अनुसार, इस मानचित्र में सबसे कम निश्चित बिंदु है; क्लेन निश्चित-बिंदु प्रमेय द्वारा निश्चित बिंदु श्रृंखला का सर्वोच्च है $T(\emptyset ),T(T(\emptyset )),\ldots ,T^{n}(\emptyset ),\ldots$. का सबसे कम निश्चित बिंदु M कार्यक्रम के न्यूनतम हेरब्रांड मॉडल से मेल खाता है।

फिक्सप्वाइंट सिमेंटिक्स न्यूनतम हेरब्रांड मॉडल की गणना के लिए एक एल्गोरिदम का सुझाव देता है: प्रोग्राम में जमीनी तथ्यों के सेट से शुरू करें, फिर फिक्सपॉइंट तक पहुंचने तक नियमों के परिणामों को बार-बार जोड़ें। इस एल्गोरिदम को Datalog#Naive मूल्यांकन|naive मूल्यांकन कहा जाता है।

प्रमाण-सैद्धांतिक

ज़मीनी परमाणु की व्युत्पत्ति दर्शाने वाला प्रमाण वृक्ष path(x, z) कार्यक्रम से

edge(x, y).
edge(y, z).
path(A, B) :- 
  edge(A, B).
path(A, C) :- 
  path(A, B), 
  edge(B, C).

एक कार्यक्रम दिया P, ए proof tree एक जमीनी परमाणु का A एक वृक्ष (डेटा संरचना) है जिसके मूल को लेबल किया गया है A, तथ्यों के शीर्ष से जमीन के परमाणुओं द्वारा लेबल की गई पत्तियां P, और बच्चों के साथ शाखाएँ $A_{1},\ldots ,A_{n}$ जमीनी परमाणुओं द्वारा लेबल किया गया G जैसे कि एक जमीनी उदाहरण मौजूद है

G :- A1, …, An.

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

अन्य दृष्टिकोण

डेटालॉग के शब्दार्थ का अध्ययन अधिक सामान्य मोटी हो जाओ पर फिक्सप्वाइंट के संदर्भ में भी किया गया है।

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

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

सिंटेक्स

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

शब्दार्थ

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

निषेध

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

सिंटेक्स

निषेध लिखा है not, और किसी नियम के शरीर में किसी भी परमाणु के सामने प्रकट हो सकता है।

<atom-list> ::= <atom> | "not" <atom> | <atom> "," <atom-list> | ""

शब्दार्थ

स्तरीकृत निषेध

निषेध के साथ एक तर्क कार्यक्रम को तब स्तरीकृत किया जाता है जब प्रत्येक संबंध को किसी स्तर पर निर्दिष्ट करना संभव हो, जैसे कि यदि कोई संबंध R किसी संबंध के मुख्य भाग में नकारा हुआ प्रतीत होता है S, तब Rसे निचले तबके में है S. डेटालॉग के मॉडल-सैद्धांतिक और निश्चित-बिंदु शब्दार्थ को स्तरीकृत निषेध को संभालने के लिए बढ़ाया जा सकता है, और ऐसे विस्तारों को समकक्ष साबित किया जा सकता है।

डेटालॉग के कई कार्यान्वयन निश्चित बिंदु शब्दार्थ से प्रेरित बॉटम-अप मूल्यांकन मॉडल का उपयोग करते हैं। चूँकि यह शब्दार्थ स्तरीकृत निषेध को संभाल सकता है, डेटालॉग के कई कार्यान्वयन स्तरीकृत निषेध को लागू करते हैं।

जबकि स्तरीकृत निषेध डेटालॉग का एक सामान्य विस्तार है, ऐसे उचित कार्यक्रम हैं जिन्हें स्तरीकृत नहीं किया जा सकता है। निम्नलिखित कार्यक्रम दो-खिलाड़ियों के खेल का वर्णन करता है जहां एक खिलाड़ी जीतता है यदि उनके प्रतिद्वंद्वी के पास कोई चाल नहीं है:

move(a, b).
win(X) :- move(X, Y), not win(Y).

यह कार्यक्रम स्तरीकृत नहीं है, लेकिन ऐसा सोचना उचित लगता है a खेल जीतना चाहिए.

समापन शब्दार्थ

Main article: Negation as failure § Completion semantics

स्थिर मॉडल शब्दार्थ

Main article: Stable model semantics

स्थिर मॉडल शब्दार्थ किसी प्रोग्राम के कुछ हर्ब्रांड मॉडल को स्थिर कहने के लिए एक शर्त को परिभाषित करता है। सहज रूप से, स्थिर मॉडल विश्वासों के संभावित सेट हैं जो एक तर्कसंगत एजेंट धारण कर सकता है, जिसे [कार्यक्रम] परिसर के रूप में दिया गया है। नकार वाले एक प्रोग्राम में कई स्थिर मॉडल या कोई स्थिर मॉडल नहीं हो सकते हैं। उदाहरण के लिए, प्रोग्राम

p :- not q.
q :- not p.

इसके दो स्थिर मॉडल हैं $\{p\}$, $\{q\}$. एक-नियम कार्यक्रम

p :- not p.

कोई स्थिर मॉडल नहीं है.

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

अच्छी तरह से स्थापित शब्दार्थ

Main article: Well-founded semantics

आगे विस्तार

डेटालॉग के कई अन्य एक्सटेंशन प्रस्तावित और अध्ययन किए गए हैं, जिनमें पूर्णांक स्थिरांक और फ़ंक्शंस के समर्थन वाले वेरिएंट शामिल हैं (डेटालॉगजेड|डेटालॉग सहित)_ℤ), नियमों और समग्र कार्यों के निकायों में असमानता (गणित) बाधाएँ।

बाधा तर्क प्रोग्रामिंग वास्तविक संख्या या पूर्णांक जैसे डोमेन पर बाधाओं को नियमों के मुख्य भाग में प्रदर्शित करने की अनुमति देती है।

यह भी देखें

• हरब्रांड संरचना
• तर्क प्रोग्रामिंग
• असफलता के रूप में नकार
• प्रोलॉग सिंटैक्स और शब्दार्थ

संदर्भ

स्रोत

• Ceri, S.; Gottlob, G.; Tanca, L. (March 1989). "डेटालॉग के बारे में आप हमेशा क्या जानना चाहते थे (और कभी पूछने की हिम्मत नहीं की)" (PDF). IEEE Transactions on Knowledge and Data Engineering. 1 (1): 146–166. CiteSeerX 10.1.1.210.1118. doi:10.1109/69.43410. ISSN 1041-4347.

श्रेणी:प्रोग्रामिंग भाषा सिंटैक्स श्रेणी:तर्क प्रोग्रामिंग