नियमित अभिव्यक्ति मिलान प्रोलॉग

Question

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

लेकिन जैसे ही मैं इसे एक सूची बना देता हूं, यह विफल हो जाता है। "re_contains (seq (ए, बी), [ए, बी])।" झूठी वापसी मैच को खोजने के लिए सभी संभव संयोजनों के माध्यम से संलग्न होना चाहिए, लेकिन इनमें से कोई भी कार्य सही तरीके से काम नहीं करता है। यह मुझे चीज बनाता है कि शायद मुझे आधार का मामला याद आ रहा है। लेकिन मुझे लगता है "re_contains (एक्स, एल): - एक्स == एल।" इसका ख्याल रखना चाहिए। मुझे यहां कुछ महत्वपूर्ण दिखना चाहिए।

re_contains(empty, []). 

re_contains(X, L) :- 
    X == L. 

re_contains(seq(X, Y), L) :- 
    append(L1, L2, L), 
    re_contains(X, L1), 
    re_contains(Y, L2). 

re_contains(union(X, _), L) :- 
    re_contains(X, L). 

re_contains(union(_, Y), L) :- 
    re_contains(Y, L). 

re_contains(kleene(X), L) :- 
    append([Car|L1], L2, L), 
    re_contains(X, [Car|L1]), 
    re_contains(kleene(X), L2). 

re_contains(kleene(_),[]). 

Answer 1

append/3 बंट जाएगा L, और दोनों L1 और L2 सूचियों होगा:

यहाँ मेरी कोड है।

मैं re_contains(X, [X]).

परिवर्तन के बाद से re_contains(X, L) :- X == L. को बदलने के लिए कोशिश करेगा, re_contains(a,a). असफल हो जायेगी।

आप विभिन्न तरीकों से अनुक्रम का प्रतिनिधित्व कर रहे हैं, और आपका matcher दोनों के लिए प्रदान नहीं करता है। असल में, केवल 'काम करने वाले' मामले अनुक्रम हैं।

Answer 2

कई मुद्दे हैं। यहां सबसे स्पष्ट हैं:

टाइपिंग। आपकी भविष्यवाणी re_contains/2 दूसरी सूची के रूप में एक सूची की अपेक्षा करता है। वह re_contains(a,a). सफलता इरादे से बल्कि संयोग है।

मोनोटोनिसिटी। एक और समस्या यह है कि re_contains([a],[a]) सफल होता है, लेकिन re_contains([X],[a]) विफल रहता है। या, इसे किसी अन्य कोण से देखने के लिए: re_contains([X],[a]) विफल रहता है, लेकिन X = a, re_contains([X],[a]) सफल होता है। लक्ष्य X = a जोड़कर हमने क्वेरी को विशेष रूप से विफल कर दिया है, इस प्रकार मूल रूप से असफल क्वेरी फिर से विफल होनी चाहिए।

पहचान (==/2) के लिए परीक्षण समानता द्वारा प्रतिस्थापित किया जाना चाहिए (=/2) और सुनिश्चित करना है कि हम कुछ सूची है। तो:

 
re_contains(X, L) :- 
    % X == L. 
    X = L, 
    append(X,_,_). 

ध्यान दें, कि append/3 यहाँ प्रयोग किया जाता है केवल यह है कि एक्स सुनिश्चित करने के लिए है एक सूची - वास्तविक appending कार्यक्षमता नहीं किया जाता है।

क्षमता। तीसरी समस्या वास्तविक तरीके से संबंधित है कि आप कैसे सम्मेलन का प्रतिनिधित्व कर रहे हैं। सिर्फ निम्नलिखित नियम पर नजर डालते हैं:

 
re_contains(seq(X, Y), L) :- 
    append(L1, L2, L), 
    re_contains(X, L1), 
    re_contains(Y, L2). 

अब, मान यहाँ है कि हम लंबाई N की एक सूची। लक्ष्य append(L1, L2, L) के लिए कितने जवाब संभव हैं? दरअसल N + 1। और यह, वास्तविक मूल्यों को शामिल किए बिना।अब विचार करें:

?- length(L,1000000), time(re_contains(seq([a],[]),[b|L])). 
% 2,000,005 inferences, 0.886 CPU in 0.890 seconds (100% CPU, 2258604 Lips) 
false. 

re_contains/2 जरूरतों यहाँ समय सूची की लंबाई के अनुपात। लेकिन यह समझने के लिए पहले तत्व को देखना पर्याप्त होगा कि यह असंभव है।

तो पीछे की समस्या append/3 का उपयोग है। Prolog के लिए अंगूठे का एक साधारण नियम है: यदि आप बहुत अधिक उपयोग कर रहे हैं append/3dcg s — असीमित क्लॉज ग्रामर का उपयोग करने पर विचार करें। कृपया अधिक जानकारी के लिए टैग देखें — और एक प्रारंभिक प्रोलॉग टेक्स्ट से परामर्श लें।

 
re_contains(RE, L) :- 
    phrase(re(RE), L). 

re([]) --> []. 
re([E]) --> [E]. 
re(seq(X,Y)) --> 
    re(X), 
    re(Y). 

है जो अब पूरी सूची की जांच:

 
?- length(L,1000000), time(phrase(re(seq([a],[])),[b|L])). 
% 6 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 127313 Lips) 
false. 

Btw, here एक पूरी परिभाषा है आप एक शुरुआत देने के लिए, यहाँ अपनी परिभाषा का एक सबसेट है।

समाप्ति/गैर-समाप्ति। दक्षता से संबंधित समाप्ति की संपत्ति है। आदर्श रूप से, एक क्वेरी समाप्त हो जाती है, अगर समाधानों का सेट अंततः प्रतिनिधित्व किया जा सकता है। यही है, उत्तरों की एक सीमित संख्या से। ठीक है, यह आदर्श है जिसके लिए हम प्रयास कर रहे हैं। प्रोलॉग का सरल लेकिन बहुत ही कुशल निष्पादन एल्गोरिदम कभी-कभी लूप होगा, जब उत्तर की एक सीमित संख्या संभव होगी। गैर-समाप्ति के कारण को समझना कभी-कभी बहुत मुश्किल होता है। सामान्य डीबगिंग रणनीतियों – जैसे डीबगर – के साथ ट्रेसिंग या स्टेपिंग की तरह काम नहीं करते क्योंकि वे आपको बहुत अधिक विस्तार से दिखाते हैं। सौभाग्य से, एक बेहतर तकनीक है:

अपने पूरे कार्यक्रम को देखने के बजाय, मैं फिर से इसके बहुत ही छोटे टुकड़े को देखूंगा। यह खंड failure slice है (अधिक जानकारी के लिए लिंक देखें)। यह काफी छोटा है लेकिन मूल कार्यक्रम — प्रदान की है कि एक शुद्ध, monotonic कार्यक्रम था के बारे में काफी एक बहुत कुछ बताता है:

एक विफलता टुकड़ा समाप्त नहीं करता है, तो मूल कार्यक्रम समाप्त नहीं करता।

तो अगर हमें ऐसी विफलता टुकड़ा मिल जाए तो हम पूरे कार्यक्रम के बारे में तुरंत निष्कर्ष निकाल सकते हैं। बाकी भी पढ़ने के बिना!

यहां इस तरह के एक दिलचस्प विफलता टुकड़ा है:

 
... 
re_contains(X, L) :- false, 
    X = L 
re_contains(seq(X, Y), L) :- 
    append(L1, L2, L), false, 
    re_contains(X, L1), 
    re_contains(Y, L2). 
re_contains(union(X, _), L) :- false, 
    re_contains(X, L). 
... 

लक्ष्य re_contains(seq([],[]),L). आदर्श रूप में अब विचार करें, वहाँ वास्तव में एक ही जवाब L = [] होना चाहिए और लक्ष्य को समाप्त करना चाहिए। हालांकि, यह loops, append(L1, L2, L) समाप्त नहीं होता है। डीसीजी-समाधान के लिए इसे विपरीत करें जो phrase(re(seq([],[])),L) के लिए समाप्त हो जाता है।