मुझे प्रोलॉग में बाइनरी जोड़ को लागू करने की आवश्यकता है, जहां बाइनरी संख्याओं को निम्नानुसार दर्शाया गया है:

0:  bot
1 : o(bot)
2 -> 10:  z(o(bot))
3 -> 11:  o(o(bot))
10 -> 1010:  z(o(z(o(bot))))

मैंने यह लिखा है:

add(X,bot,X):-!.
add(bot,X,X):-!.

add(z(X),z(Y),Res):- add(X,Y,D), Res = z(D).
add(z(X),o(Y),Res):- add(X,Y,D), Res = o(D).
add(o(X),z(Y),Res):- add(X,Y,D), Res = o(D).
add(o(X),o(Y),Res):-addc(X,Y,D), Res = z(D).

addc(X,bot,Res):-add(X,o(bot),Res),!.
addc(bot,X,Res):-add(X,o(bot),Res),!.
addc(z(X),z(Y),Res):- add(X,Y,D),Res = o(D).
addc(z(X),o(Y),Res):-addc(X,Y,D),Res = z(D).
addc(o(X),z(Y),Res):-addc(X,Y,D),Res = z(D).
addc(o(X),o(Y),Res):-addc(X,Y,D),Res = o(D).

यह तब काम करता है जब पहले 2 तर्क ठोस होते हैं:

?-add(o(o(bot)),z(o(o(bot))),D).
D = o(z(z(o(bot))))

जब पहले 2 तर्कों में से एक चर है, तो यह एक अनंत रिकर्सन में जाता है:

?-add(o(o(bot)),X,z(o(o(bot)))).
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.1Gb, global: 34.9Mb, trail: 11.6Mb
  Stack depth: 1,524,958, last-call: 50%, Choice points: 762,476
  Possible non-terminating recursion:
    [1,524,958] add(bot, <compound s/1>, _1496)
    [1,524,957] add(bot, <compound s/1>, <compound z/1>)

मैं यह काम किसी एक गैर-ठोस तर्क के लिए कैसे कर सकता हूं?

2
CodeHoarder 25 जिंदा 2020, 11:40

1 उत्तर

सबसे बढ़िया उत्तर

(जिसे अन्यथा zero, null या 0 माना जाता है, उसके लिए bot का उपयोग करना थोड़ा अजीब है। यहां जाली हमारी प्रमुख चिंता नहीं है।)

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

add(bot, X, X).
add(X, bot, X) :- dif(X, bot).

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

add(bot,X,X) :- false.
add(X,bot,X) :- false, dif(X,bot).
add(z(X),z(Y),Res) :- false, add(X,Y,D), Res = z(D).
add(z(X),o(Y),Res) :- false, add(X,Y,D), Res = o(D).
add(o(X),z(Y),Res) :- false, add(X,Y,D), Res = o(D).
add(o(X),o(Y),Res) :- addc(X,Y,D), false, Res = z(D).

addc(bot,X,Res) :- add(X,o(bot),Res), false.
addc(X,bot,Res) :- dif(X, bot), add(X,o(bot),Res), false.
addc(z(X),z(Y),Res) :- false, add(X,Y,D), Res = o(D).
addc(z(X),o(Y),Res) :- false, addc(X,Y,D), Res = z(D).
addc(o(X),z(Y),Res) :- false, addc(X,Y,D), Res = z(D).
addc(o(X),o(Y),Res) :- addc(X,Y,D), false, Res = o(D).

?- add(o(o(bot)),X,z(o(o(bot)))).

~2^23 संभावित विफलता स्लाइस में से, यह न्यूनतम प्रतीत होता है। अर्थात्, आगे कोई भी false प्रोग्राम को समाप्त कर देता है।

आइए इसे देखें: हर जगह Res को या तो नज़रअंदाज़ कर दिया जाता है या फिर आगे बढ़ा दिया जाता है। इसलिए तीसरे तर्क का समाप्ति पर कोई प्रभाव नहीं पड़ता है। लेकिन आप उन सभी Res = समीकरणों को :- के ठीक बाद में रख सकते हैं। वह जल्द से जल्द संभव जगह है।

add(bot,X,X).
add(X,bot,X):- dif(X,bot).
add(z(X),z(Y), z(D)) :- add(X,Y,D).
add(z(X),o(Y), o(D)) :- add(X,Y,D).
add(o(X),z(Y), o(D)) :- add(X,Y,D).
add(o(X),o(Y), z(D)) :- addc(X,Y,D).

addc(bot,X,Res):- add(X,o(bot),Res).
addc(X,bot,Res):- dif(X, bot), add(X,o(bot),Res).
addc(z(X),z(Y),o(D)):- add(X,Y,D).
addc(z(X),o(Y),z(D)):- addc(X,Y,D).
addc(o(X),z(Y),z(D)):- addc(X,Y,D).
addc(o(X),o(Y),o(D)):- addc(X,Y,D).

साथ ही cTI अनुकूल समाप्ति शर्तें देता है:

% NTI summary:  Complete result is optimal.
add(A,B,C)terminates_if b(A),b(B);b(C).
    % optimal. loops found: [add(z(_),z(_),z(_)),add(o(bot),o(o(_)),z(z(_))),add(o(o(_)),o(bot),z(z(_)))]. NTI took    8ms,72i,30i
addc(A,B,C)terminates_if b(A),b(B);b(C).
    % optimal. loops found: [addc(z(z(_)),z(z(_)),o(z(_))),addc(bot,o(_),z(_)),addc(o(_),bot,z(_))]. NTI took    4ms,96i,96i

तो add/3 पहले दो या अंतिम तर्क दिए जाने पर या तो समाप्त हो जाता है। तो आपको पहले तर्क की आवश्यकता नहीं है। इसके बजाय, और भी सामान्य क्वेरी समाप्त हो जाती है:

?- add(X,Y,z(o(o(bot)))).
     X = bot, Y = z(o(o(bot)))
   ; X = z(o(o(bot))), Y = bot
   ; X = z(bot), Y = z(o(o(bot)))
   ; X = z(o(o(bot))), Y = z(bot)
   ; X = z(z(bot)), Y = z(o(o(bot)))
   ; X = z(z(o(bot))), Y = z(o(bot))
   ; X = z(z(z(bot))), Y = z(o(o(bot)))
   ; X = z(z(o(bot))), Y = z(o(z(bot)))
   ; X = z(o(bot)), Y = z(z(o(bot)))
   ; X = z(o(o(bot))), Y = z(z(bot))
   ; X = z(o(z(bot))), Y = z(z(o(bot)))
   ; X = z(o(o(bot))), Y = z(z(z(bot)))
   ; X = o(bot), Y = o(z(o(bot)))
   ; X = o(z(o(bot))), Y = o(bot)
   ; X = o(z(bot)), Y = o(z(o(bot)))
   ; X = o(z(o(bot))), Y = o(z(bot))
   ; X = o(z(z(bot))), Y = o(z(o(bot)))
   ; X = o(z(o(bot))), Y = o(z(z(bot)))
   ; X = Y, Y = o(o(bot))
   ; X = o(o(bot)), Y = o(o(z(bot)))
   ; X = o(o(z(bot))), Y = o(o(bot))
   ; X = Y, Y = o(o(z(bot)))
   ; false.

1 और इससे भी बेहतर, if_/3 लाइब्रेरी reif का उपयोग करें। rel="nofollow noreferrer">SICStus और SWI उन उपबंधों को यथा निर्धारित रखने के लिए मुमकिन।

add(A, B, C) :- if_(A = bot, B = C, ( B = bot, A = C ) ).
2
false 25 जिंदा 2020, 17:13