हम हबे पर आइंस्टीन के कार्य के सप्ताह को जारी रखते हैं। प्रस्तुत तीन समाधानों के अतिरिक्त
- नियमित भाषा
- हास्केल
- प्रस्तावना
मुझे
बुध पर एक और परिचय दें।
स्मरण करो
विकिपीडिया :
पारा टाइपिंग के साथ एक कार्यात्मक टाइपिंग भाषा है ...
अभी टिप्पणी करना अच्छा होगा। इस तथ्य के बावजूद कि पारा एक टाइप के रूप में कल्पना की गई थी, जिसका अर्थ है एक सुरक्षित और तेजी से प्रस्तावना, यह मुझे
तर्क के साथ तना हुआ लगता है। मैं समझा दूंगा। प्रस्तावना में, लगभग सबसे महत्वपूर्ण उपकरण तथाकथित
तार्किक चर हैं । यहाँ, शायद, उदाहरणों के साथ समझाना आसान है (प्रस्तावना):
?- A=B, C=B, B=D, D=123. A = 123, B = 123, C = 123, D = 123.
यहां हम चरों के बीच संबंधों को निर्धारित करते हैं और केवल अंत में संक्षिप्त करते हैं। इस मामले में, शेष चर रिश्तों के अनुसार स्वचालित रूप से संक्षिप्त हो जाते हैं।
?- L=[A,B,C], L=[5,5|_], C=Q, Q=B. L = [5, 5, 5], A = 5, B = 5, C = 5, Q = 5.
एक अधिक जटिल उदाहरण। तीन अब तक अज्ञात चर ए, बी और सी की एक सूची एल निर्दिष्ट की गई थी। 5 नंबर के साथ सूची के पहले दो तत्वों को निर्दिष्ट किया गया था। एक ही समय में, चर ए और बी स्वचालित रूप से एक ही नंबर के साथ निर्दिष्ट किए गए थे। तब C को समान संख्या के साथ निर्दिष्ट किया गया था, चूंकि C = Q, Q = B और, जैसा कि यह निकला, B = 5 है।
?- length(L,3). L = [_G328, _G331, _G334].
3 अज्ञात मूल्यों (गैर-विशिष्ट) की एक सूची बनाई गई।
?- length(L,3), nth0(0,L,aaa). L = [aaa, _G461, _G464].
हमने स्पष्ट किया कि सूची का पहला तत्व परमाणु आ के बराबर है। इसके अलावा, सूची को आंशिक रूप से निर्दिष्ट किया गया था।
?- length(L,3), nth0(0,L,aaa), nth0(1,L,bbb). L = [aaa, bbb, _G594].
सूची को और भी अधिक परिष्कृत किया।
?- length(L,3), nth0(0,L,aaa), nth0(1,L,bbb), nth0(2,L,ccc). L = [aaa, bbb, ccc].
हमने आखिरकार सूची निर्धारित की। वास्तव में, शब्दों में, हमने एक परिभाषा दी: लंबाई 3 की एक सूची, जिसका पहला तत्व
aaa , दूसरा
bbb , और तीसरा
ccc । जो सामान्य के बराबर है:
?- L=[aaa,bbb,ccc]. L = [aaa, bbb, ccc].
यही मतलब है। खैर, वह यह है कि प्रस्तावना में, फॉर्म की समस्या को हल करने के लिए दृष्टिकोण बहुत स्वाभाविक है: वे समाधान का रूप निर्धारित करते हैं, फिर, समाधान के दौरान, हम बाद में समाधान को परिष्कृत करते हैं जब तक कि यह पूरी तरह से निर्धारित न हो जाए। यह दृष्टिकोण समाधान को स्वयं (इसका कोड) घोषित करता है, क्योंकि यह एक परिभाषा के रूप में पढ़ा जाता है, और एल्गोरिथ्म के कार्यों के अनुक्रम के रूप में नहीं (यहां, शायद, आपको इनपुट-आउटपुट के बारे में एक आरक्षण करने की आवश्यकता है, जो आप चाहते हैं, लेकिन यह सार में जरूरी है)
तो, पारा
में कोई तार्किक चर नहीं हैं ! = (
दूसरे शब्दों में, पारा आंशिक रूप से परिभाषित डेटा संरचनाओं का समर्थन नहीं करता है।
कहते हैं, यदि हम एक सूची निर्दिष्ट करते हैं, तो उसके सभी तत्वों को परिभाषित किया जाना चाहिए।
इसका मतलब है कि डेटा के एक टुकड़े को स्पष्ट करने का एकमात्र तरीका इसे फेंक देना है, लेकिन इसके आधार पर अधिक विशिष्ट बनाना है। यदि हम सूचियों के बारे में बात करते हैं, तो हम कल्पना कर सकते हैं कि एक अपरिभाषित सूची अनुरूप होगी
L = [no, no, no]
आंशिक रूप से परिभाषित:
L=[yes(aaa), no, no]
लेकिन पूरी तरह से निर्दिष्ट:
L=[yes(aaa), yes(bbb), yes(ccc)].
(हाय,
शायद डेटा प्रकार)।
यह ध्यान दिया जाना चाहिए कि एक ही दुखद भाग्य
दृश्य प्रोलॉग हो सकता है (तार्किक प्रचलन की शब्दावली में तार्किक चर, या संदर्भ डोमेन की अस्वीकृति)। कारण यह है कि उन्हें इस कठोर अनिवार्य दुनिया में शायद ही कभी जरूरत होती है, और उनके बिना संकलक / आभासी मशीन कोड / निष्पादन रणनीति बहुत सरल है। सिक्के का दूसरा पहलू यह है कि आमतौर पर रखे गए कार्यों में काफी हद तक सुधार किया जाता है, और उनका समाधान बहुत कम व्यक्त होता है। हालांकि, लोकप्रिय भाषाओं हास्केल, ओकेमेल पूरी तरह से इन सुविधाओं के बिना रहते हैं =)।
यह इस दृष्टिकोण पर है कि पारा पर तार्किक प्रोग्रामिंग का विचार आधारित है।
ध्यान दें कि इस दृष्टिकोण के साथ, हमें
तार्किक एकीकरण को कोड स्तर पर भी लिखना होगा (प्रस्तावना में, यह आउटपुट मशीन के स्तर पर है)।
तर्क सहायक मॉड्यूल (पारा प्रकार वर्गों का समर्थन करता है, जैसे हैस्केल):
:- module logic. :- interface. :- import_module list, maybe. :- typeclass unifiable(T) where [ func unify(T, T) = T is semidet ]. :- instance unifiable(maybe(T)). :- instance unifiable(list(T)) <= unifiable(T). :- pred unify(T, T, T) <= unifiable(T). :- mode unify(in, in, out) is semidet. :- pred member(T, T, list(T), list(T)) <= unifiable(T). :- mode member(in, out, in, out) is nondet. :- pred member(T, list(T), list(T)) <= unifiable(T). :- mode member(in, in, out) is nondet. :- implementation. :- import_module maybe, list. :- instance unifiable(maybe(T)) where [ func(unify/2) is unify_maybe ]. :- instance unifiable(list(T)) <= unifiable(T) where [ func(unify/2) is unify_lists ]. :- func unify_maybe(maybe(T), maybe(T)) = maybe(T) is semidet. unify_maybe(no, yes(E)) = yes(E). unify_maybe(yes(E), no) = yes(E). unify_maybe(no, no) = no. unify_maybe(yes(E), yes(E)) = yes(E). :- func unify_lists(list(T), list(T)) = list(T) is semidet <= unifiable(T). unify_lists([], []) = []. unify_lists([H|T], [H1|T1]) = [unify(H, H1) | unify_lists(T, T1)]. :- pred unify_lists(list(T), list(T), list(T)) <= unifiable(T). :- mode unify_lists(in, in, out) is semidet. unify_lists(L1, L2, unify_lists(L1, L2)). unify(A, B, unify(A, B)). member(E, E, [], []) :- fail. member(E0, E1, [H | T], [H1 | T1]) :- ( H0 = unify(E0, H), H1 = H0, E1 = H0, T=T1 ; H1 = H, member(E0, E1, T, T1) ). member(E, !L) :- member(E,_,!L).
खैर,
ज़ेबरा पहेली समाधान ही:
:- module einstein. :- interface. :- import_module io. :- pred main(io::di, io::uo) is det. :- implementation. :- import_module maybe, list, solutions, logic. :- type house ---> house(maybe(nationality), maybe(color), maybe(pet), maybe(cigarettes), maybe(drink)). :- type nationality ---> englishman; spaniard; norwegian; ukrainian; japanese. :- type color ---> red; yellow; blue; green; ivory. :- type pet ---> dog; snails; fox; horse; zebra. :- type cigarettes ---> kools; chesterfields; winston; lucky_strike; parliaments. :- type drink ---> orange_juice; tea; coffee; milk; water. :- instance unifiable(house) where [ unify( house(N, C, P, S, D), house(N1, C1, P1, S1, D1)) = house(unify(N, N1), unify(C, C1), unify(P, P1), unify(S, S1), unify(D, D1)) ]. unknown_house = house(no,no,no,no,no). solve(!Street):- % The Englishman lives in the red house logic.member(house(yes(englishman),yes(red),no,no,no), !Street), % The Spaniard owns the dog logic.member(house(yes(spaniard),no,yes(dog),no,no), !Street), % The Norwegian lives in the first house on the left unify([house(yes(norwegian),no,no,no,no),unknown_house,unknown_house,unknown_house,unknown_house], !Street), % Kools are smoked in the yellow house. logic.member(house(no,yes(yellow),no,yes(kools),no), !Street), % The man who smokes Chesterfields lives in the house % next to the man with the fox. next(house(no,no,yes(fox),no,no), house(no,no,no,yes(chesterfields),no), !Street), % The Norwegian lives next to the blue house next(house(yes(norwegian),no,no,no,no), house(no,yes(blue),no,no,no), !Street), % The Winston smoker owns snails. logic.member(house(no,no,yes(snails),yes(winston),no), !Street), % The lucky strike smoker drinks orange juice logic.member(house(no,no,no,yes(lucky_strike),yes(orange_juice)), !Street), % The Ukrainian drinks tea logic.member(house(yes(ukrainian),no,no,no,yes(tea)), !Street), % The Japanese smokes parliaments logic.member(house(yes(japanese),no,no,yes(parliaments),no), !Street), % Kools are smoked in the house next to the house where the horse is kept. next(house(no,no,yes(horse),no,no), house(no,no,no,yes(kools),no), !Street), % Coffee is drunk in the green house logic.member(house(no,yes(green),no,no,yes(coffee)), !Street), % The green house is immediately to the right (your right) of the ivory house left(house(no,yes(ivory),no,no,no), house(no,yes(green),no,no,no), !Street), % Milk is drunk in the middle house. unify([unknown_house,unknown_house,house(no,no,no,no,yes(milk)),unknown_house,unknown_house], !Street), % And, finally, zebra and water :) logic.member(house(no,no,yes(zebra),no,no), !Street), logic.member(house(no,no,no,no,yes(water)), !Street). next(H1, H2, !Street):- left(H1, H2, !Street); left(H2, H1, !Street). left(H1, H2, !Street):- unify([H1,H2,unknown_house,unknown_house,unknown_house], !Street); unify([unknown_house,H1,H2,unknown_house,unknown_house], !Street); unify([unknown_house,unknown_house,H1,H2,unknown_house], !Street); unify([unknown_house,unknown_house,unknown_house,H1,H2], !Street). main --> { solutions(pred(S::out) is nondet :- solve([unknown_house,unknown_house,unknown_house,unknown_house,unknown_house], S), L)}, print_solutions(L). print_solutions(L) --> write_string("Total solutions: "), write_int(length(L)), nl, nl, print_every_sol(L). print_every_sol([]) --> []. print_every_sol([S|SS]) --> print_sol(S), print_every_sol(SS). print_sol([]) --> []. print_sol([H|HH]) --> print_house(H), nl, print_sol(HH). print_maybe(no) --> write_string("unknown"). print_maybe(yes(T)) --> write(T). print_house(house(N, C, P, S, D)) --> write_string("house("), print_maybe(N), write_string(", "), print_maybe(C), write_string(", "), print_maybe(P), write_string(", "), print_maybe(S), write_string(", "), print_maybe(D), write_string(")").
जैसा कि आप देख सकते हैं, प्रस्तावना समाधान की समानता नग्न आंखों को दिखाई देती है, हालांकि कोड परिमाण का एक बड़ा क्रम है, हां ... =)
$ time ./einstein
Total solutions: 1
house(norwegian, yellow, fox, kools, water)
house(ukrainian, blue, horse, chesterfields, tea)
house(englishman, red, snails, winston, milk)
house(spaniard, ivory, dog, lucky_strike, orange_juice)
house(japanese, green, zebra, parliaments, coffee)
real 0m0.031s
user 0m0.015s
sys 0m0.015s