प्रोलॉग पर रिफ्लेक करें। सेवन लाइन्स मैजिक

अगर पहचानने वाली मशीन हाथी की तस्वीर पर "मुरा" संकेत के साथ प्रतिक्रिया करती है, तो ऊंट की छवि भी "मुरा" है और एक प्रमुख वैज्ञानिक का चित्र फिर से "मुरा" है, इसका मतलब यह नहीं है कि यह दोषपूर्ण है। वह सिर्फ दार्शनिक हो सकता है।
व्लादिमीर सवचेन्को, "खुद को खोलना"

1. लव रिफ़ल। इसके तत्काल बाद!

हर कोई जानता है कि इस तरह की एक प्रोग्रामिंग भाषा है - रिफाल। Refal का विकास 1966 में हमारे हमवतन वैलेंटाइन तुरचिन ने किया था। Refal का भाग्य जटिल है, लेकिन उनकी भाषा अभी भी जीवित है और विकसित हो रही है। उन लोगों के लिए, यहाँ कुछ लिंक दिए गए हैं:

• रेफला -5 का स्वतंत्र अध्ययन। छात्र देखो
• पत्रिका "कार्यात्मक प्रोग्रामिंग का अभ्यास", अंक 7 जारी करें (उसे स्मृति के साथ आशीर्वाद दें!)। लेख "वास्तविक भाषा - ओर से एक दृश्य" और "सुपरकंप्लीशन: विचार और विधियाँ"

जोरदार अतिरंजना, हम कह सकते हैं कि रिफाल लिस्प और प्रोलॉग का मिश्रण है। भाषा के सिंटैक्स में एक दिलचस्प विशेषता है - तथाकथित पैटर्न के साथ तुलना। "प्रत्यक्ष निष्कर्ष।"

उदाहरण के लिए, Refal पर एक पैलिंड्रोम के निर्धारण के लिए एक विधेय इस प्रकार लिखा जा सकता है:

Palindrom { = True; s.1 = True ; s.1 e.2 s.1 = <Palindrom e.2> ; e.1 = False ; } 

ब्रेसिज़ में प्रत्येक पंक्ति एक पैटर्न मिलान नियम है। प्रत्येक नियम के शरीर को "=" प्रतीक द्वारा अलग किया जाता है। नमूना तत्वों को एक स्थान से अलग किया जाता है। एक फ़ंक्शन कॉल कोन कोष्ठक में लिखा जाता है। "S" और "e" से शुरू होने वाले वर्ण एक निश्चित प्रकार के चर होते हैं। चर का नाम अवधि के बाद लिखा जाता है।

• "S" प्रकार का एक चर का मतलब है कि अनुक्रम के केवल एक तत्व के लिए मैपिंग सही है
• "E" प्रकार का एक चर का मतलब है कि मैच 0 या अधिक तत्वों के लिए सही है

इस प्रकार पलिंड्रोम की इस परिभाषा को इस तरह पढ़ा जा सकता है:

• खाली सूची के लिए अभिव्यक्ति सही है। यानी एक खाली अनुक्रम को एक पैलिंड्रोम कहा जा सकता है।
• एकल-तत्व सूची के लिए अभिव्यक्ति सही है। यानी एक तत्व के एक अनुक्रम को एक पैलिंड्रोम कहा जा सकता है। एस चर का प्रकार हमें बताता है कि पैटर्न केवल एक तत्व के लिए मान्य है।
• कम से कम 2 तत्वों से युक्त सूची के लिए अभिव्यक्ति सही है, सूची के पहले और अंतिम तत्व के बराबर है। पहले और आखिरी तत्व की समानता समान चर नामों ("1") द्वारा इंगित की जाती है। पहले और अंतिम तत्व (चर "e.2" के बीच की सबलिस्ट, यानी इस तरह के सबलिस्ट की लंबाई 0 या अधिक तत्व हो सकती है) को एक पलिंड्रोम के लिए पुनरावर्ती रूप से जांचना चाहिए।
• यदि उपरोक्त नियम में से किसी ने भी काम नहीं किया है, तो पारित तर्क एक तालमेल नहीं है।

यह रद्द करना आवश्यक है कि मॉडल के साथ रेफल तुलना के आधुनिक कार्यान्वयन में काफी कुशलता से लागू किया जाता है।

2. प्रस्तावना। जादू शुरू होता है!

Refal में प्रोलॉग से बहुत कुछ है। हम प्रोलॉग पर नमूने के साथ रिफालोव्स्की तुलना के तंत्र को लागू करने का प्रयास करेंगे।

शुरू करने से पहले, हम सहायक को "उपसर्ग" की भविष्यवाणी करते हैं। विधेय को यह देखना होगा कि क्या पहला तर्क दूसरे तर्क की शुरुआत है। दूसरे तर्क के शेष को तीसरे तर्क में इंगित किया गया है।

 prefix([], [X|Xs], [X|Xs]). prefix([X|Prefix], [X|List], Rest) :- prefix(Prefix, List, Rest). 

कॉल उदाहरण:

 ?- prefix([1,2], [1,2,3,4], [3,4]). true. ?- prefix([], [1,2,3,4], X). X = [1, 2, 3, 4]. 

अब सब कुछ हमारे लिए तैयार है कि नमूने के साथ मेल खाने वाले रिफ्लेवोव की भविष्यवाणी का निर्धारण करें (आइए हम विधेय "आरएफ" कहते हैं)। यहाँ उदाहरण के रूप में एक ही पैलिंड्रोम का उपयोग करते हुए "rf" का उपयोग करने के उदाहरण हैं (कार्यान्वयन थोड़ा बाद में होगा):

 palindrom([]). palindrom([_]). palindrom(List) :- rf([s(X1), e(Y), s(X1)], List), palindrom(Y). 

जैसा कि आप देख सकते हैं, यह परिभाषा वैसा ही है जैसा हमने पहले रेफल पर लिखा था। रिफालोव उदाहरण में चौथा नियम हमें ज़रूरत नहीं थी, क्योंकि प्रस्तावना स्वयं मानचित्रण की झूठी शाखाओं को काट देगी। ध्यान दें कि उदाहरण में "s" और "e" सामान्य प्रस्तावना शब्द हैं।

हमारे पैलिंड्रोम को कॉल करने के उदाहरण:

 ?- palindrom("abc"). false. ?- palindrom("abcba"). true . ?- palindrom("aa"). true . 

अब rf विधेय की परिभाषा पर चलते हैं:

 rf([X | Pattern], [X|Xs]) :- rf(Pattern, Xs). rf([s(X) | Pattern], [X|Xs]) :- rf(Pattern, Xs). rf([e(X) | Pattern], Xs) :- prefix(X, Xs, Rest), rf(Pattern, Rest). rf([e(X)], X). rf([], []). 

हम अपनी परिभाषा लाइन पर लाइन द्वारा टिप्पणी करते हैं:

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

3. उदाहरण

3.1। पहला उदाहरण

अद्भुत लेख "प्रोलॉग, परिचय" प्रोलॉग पर रिफाल समुदाय में प्रस्तावित समस्या का समाधान प्रदान करता है। समस्या कथन:

इनपुट फ़ाइल में दो ASCII लाइनें हैं, एक में केवल बड़े लैटिन अक्षर हैं, दूसरे में बड़े लैटिन पत्र और दो अन्य विशेष वर्ण हो सकते हैं - * (तारांकन) और? (प्रश्न चिह्न)। स्ट्रिंग्स की लंबाई 1 से 255 वर्ण हो सकती है, यादृच्छिक क्रम में एक फ़ाइल में हो सकती है (लेकिन उनमें से केवल दो हैं, इनपुट डेटा प्रारूप सही है)। केवल अक्षरों वाली एक पंक्ति को एक शब्द कहा जाता है। विशेष पात्रों के साथ एक पंक्ति - एक पैटर्न जिसमें "?" और "*" DOS या यूनिक्स-शेल में फ़ाइल नाम में वाइल्डकार्ड के समान वाइल्डकार्ड वर्णों की भूमिका निभाते हैं, अर्थात "?" बिल्कुल एक मनमाने चरित्र की जगह लेता है, और "*" किसी भी संख्या में मनमाने चरित्रों की जगह लेता है - 0 या अधिक (यानी, यह एक खाली स्ट्रिंग की जगह ले सकता है)। यदि शब्द पैटर्न से मेल खाता है (तो यह मेल खाता है), या नहीं तो कार्यक्रम को एक हां जवाब देना चाहिए।

वापसी के लिए समाधान:

 Match { s.1 e.2 (s.1 e.3) = <Match e.2 (e.3)>; s.1 e.2 ('?' e.3) = <Match e.2 (e.3)>; e.1 ('*' e.3) = { e.1 : e.11 e.12, <Match e.12 (e.3)>; }; /*empty*/ () = /*yes*/; }; 

हम ऊपर बताए गए दृष्टिकोण का उपयोग करते हुए प्रोलॉग पर रेफल विधेय को फिर से लिखते हैं:

 ischar(H, [H]). match([],[]) :- !. match("*",_) :- !. match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), rf([s(T1), e(E2)],Word), match(E1, E2),!. match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), ischar(T1, "?"), rf([s(_T2), e(E2)], Word), match(E1,E2),!. match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), ischar(T1, "*"), rf([e(_E21), e(E22)], Word), match(E1,E22),!. check:- match("ASDFAASDASDAAASDASDASD", "ASDFAASDASDAAASDASDASD"), match("*", "ASDFAASDASDAAASDASDASD"), match("A?DF?A*ASD*ASDA?DASD", "ASDFAASDASDAAASDASDASD"), \+ match("ASDFAASDADAAASDASDASD", "ASDFAASASDAAASDASDASD"). 

ध्यान दें, निश्चित रूप से, "परिभाषा , प्रस्तावना" लेख से समाधान की तुलना में हमारी परिभाषा बहुत कम प्रभावी है।

3.2। दूसरा उदाहरण

यहाँ हमारे विधेय का उपयोग करने का एक और उदाहरण है। हम एक तुच्छ विधेय को परिभाषित करते हैं जो एक स्ट्रिंग में अंकगणितीय अभिव्यक्तियों की गणना करता है।

उपयोग उदाहरण:

 ?- infix("2+2*2", R). R = 6. ?- infix("1+1+1+1", R). R = 4. 

इन्फिक्स को केवल जोड़ और गुणा के ऑपरेशन के बारे में समझें। तब समाधान इस तरह दिख सकता है:

 ischar(H, [H]). infix(A,R) :- rf([e(X), OpPlus, e(Y)], A), ischar(OpPlus, "+"), infix(X,R1), infix(Y,R2), R is R1 + R2,!. infix(A,R) :- rf([e(X), OpMul, e(Y)], A), ischar(OpMul, "*"), infix(X,R1), infix(Y,R2), R is R1 * R2, !. infix(A,R) :- rf([e(X)], A), number_codes(R, X),!. 

हम एक स्वतंत्र अध्ययन के लिए अन्य ऑपरेटरों के कार्यान्वयन को छोड़ देते हैं।

एक निष्कर्ष के बजाय

उपरोक्त कोड अद्वितीय या व्यावहारिक होने का दावा नहीं करता है। हालाँकि, हम यह आशा करते हैं कि यह प्रोलॉग और रेफल जैसी अद्भुत भाषाओं से पाठक को परिचित कराएगा।