हफ़्ते में ब्रेनफ़ॉक को जारी रखते हुए और
बुध के साथ उनके
प्रयोगों ने दुभाषिया के अपने संस्करण को लिखा। मैं बुध के बारे में एक "परिचयात्मक" लेख प्रस्तुत नहीं करने के लिए अग्रिम में माफी माँगता हूँ। वास्तव में, वह लिखने की प्रक्रिया में है।
इस बीच, मैं एक समाधान कोड दूंगा जो एक ही समय में बुध भाषा की कई विशेषताओं का वर्णन करेगा।
:- module bf. :- interface. :- import_module io. :- pred main(io::di, io::uo) is det. :- implementation. :- import_module list, string, char, solutions, require, int. :- type bf_cmd ---> plus; minus; step; back; print; cycle(list(bf_cmd)). :- type bf_state ---> bf_state( left :: list(int), cell :: int, right :: list(int) ). hello_world = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++\ .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.\ ------.--------.>+.>.". squares_1_to_1000 = "++++[>+++++<-]>[<+++++>-]+<+[\ >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+\ >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]\ <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-\ ]". fib_1_to_100 = "+++++++++++\ >+>>>>++++++++++++++++++++++++++++++++++++++++++++\ >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>\ +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-\ <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<\ -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]\ >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++\ +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++\ ++++++++++++++++++++++++++++++++++++++++++++.[-]<<\ <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<\ [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]". prog_to_ast(Prog) = Ast :- to_char_list(Prog, Chars), solutions(pred(Ast_::out) is nondet :- ast(Ast_, Chars, []:list(char)), Asts), ( Asts = [], error("Program invalid (parse error)!") ; Asts = [Ast|_] ). :- mode ast(out, in, out) is multi. ast([plus|Cmds]) --> ['+'], ast(Cmds). ast([minus|Cmds]) --> ['-'], ast(Cmds). ast([step|Cmds]) --> ['>'], ast(Cmds). ast([back|Cmds]) --> ['<'], ast(Cmds). ast([print|Cmds]) --> ['.'], ast(Cmds). ast([cycle(Cycle)|Cmds]) --> ['['], ast(Cycle), [']'], ast(Cmds). ast([]) --> []. execute_ast([], !State) --> []. execute_ast([Cmd|Cmds], !State) --> execute_cmd(Cmd, !State), execute_ast(Cmds, !State). execute_cmd(plus, bf_state(L,C,R), bf_state(L, C+1, R)) --> []. execute_cmd(minus, bf_state(L,C,R), bf_state(L, C-1, R)) --> []. execute_cmd(step, bf_state(L,C,R), bf_state([C|L], H, T)) --> {R = [], H=0, T=[]; R = [H|T]}. execute_cmd(back, bf_state(L,C,R), bf_state(T, H, [C|R])) --> {L = [], H=0, T=[]; L = [H|T]}. execute_cmd(print, S @ bf_state(_,C,_), S) --> print(char.det_from_int( C ):char). execute_cmd(Cmd @ cycle(Cmds), !.S @ bf_state(_,C,_), !:S) --> ( {C \= 0} -> execute_ast(Cmds, !S), execute_cmd(Cmd, !S) ; [] ). execute_str(Prog) --> {Ast = prog_to_ast(Prog)}, execute_ast(Ast, bf_state([], 0, []), _). main --> execute_str(hello_world), nl, execute_str(squares_1_to_1000), nl, execute_str(fib_1_to_100).
और तुरंत इस कार्यक्रम का उत्पादन:
D:\stuff\test\mercury>bf.exe Hello World! 0 1 4 9 16 25 36 49 64 81 100 121 ... < > 9025 9216 9409 9604 9801 10000 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
मेरे फैसले के बारे में थोड़ा। इसमें 2 चरण होते हैं
- एएसटी (सार सिंटैक्स ट्री) में टेक्स्ट ब्रेनफक प्रोग्राम बदलना
- लकड़ी संस्करण एएसटी
पहले चरण में, बीएफ कोड के एक टुकड़े से, उदाहरण के लिए, '+++ >> [+ -] <' हमें सूची के रूप में एएसटी संरचना मिलती है [प्लस, प्लस, प्लस, स्टेप, स्टेप, साइकल ([प्लस, माइनस]), वापस]। इसके लिए
nondeterministic predicate ast जिम्मेदार है। उन लोगों के लिए जो इस अवधारणा के बारे में पूरी तरह से स्पष्ट नहीं हैं, मैं सरल करता हूं कि यह एक विधेय है जो एक से अधिक समाधानों को वापस कर सकता है, और इन समाधानों को बैकट्रैकिंग के माध्यम से हल किया जाएगा, जब तक कि पूरी अभिव्यक्ति में यह और इसकी भविष्यवाणी न हो। सच नहीं होगा। यह सिद्धांत एक पार्सर लिखने की सुविधा पर आधारित है जो इन-डेप्थ सर्च विधि का उपयोग करके प्रोग्राम टेक्स्ट को पार्स करता है (हालांकि इस दृष्टिकोण में कई कमियां हैं, यह विषय
इस हेब्रोटोपिका में अच्छी तरह से कवर किया गया है)। यह ध्यान देने योग्य है कि यह चरण, पार्सिंग के साथ, स्वचालित रूप से वाक्यात्मक शुद्धता (अर्थात्, ब्रैकेट संरचना की शुद्धता) की जांच करता है। यदि यह गलत है, तो लक्ष्य ast (Ast_, Chars, []: list (char)) विफल हो जाएगा, और हम त्रुटि "प्रोग्राम अमान्य (पार्स त्रुटि)!" प्राप्त करेंगे। दूसरी टिप्पणी: डीसी प्रजेंटेशन में मूल विधेय लिखा गया है, जो पारा भाषा के साथ-साथ कई पारंपरिक प्रस्तावनाओं द्वारा समर्थित है।
दूसरे चरण में (जो निष्पादित करें * * विधेय के लिए जिम्मेदार हैं), जिसके परिणामस्वरूप वाक्यविन्यास वृक्ष "गणना" है। प्रत्येक निष्पादित_ * विधेय इनपुट के रूप में सेल रिबन की प्रारंभिक स्थिति लेता है, इसे ब्रेनफक प्रोग्राम के एएसटी के अनुसार बदलता है, और इस विधेय को लागू करने के बाद होने वाले परिणाम का उत्पादन करता है (जैसा कि हम जानते हैं, कार्यात्मक भाषाएं परस्पर डेटा संरचनाओं को सहन नहीं कर सकती हैं)।
यहां इसे टेप की स्थिति स्थापित करने की संरचना पर ध्यान दिया जाना चाहिए। जैसा कि आप जानते हैं, (सही ढंग से) चयनित डेटा संरचना इष्टतम (इष्टतम) कार्यान्वयन एल्गोरिथ्म और इसकी जटिलता निर्धारित करती है। इस मामले में, टेप की संरचना दो सूचियों और एक संख्या द्वारा निर्धारित की गई थी: bf_state (LeftCells, Cell, RightCells)। इस दृष्टिकोण के साथ, सेल को बढ़ाना और घटाना सेल -1 से बदल रहा है, और इसे बाएं (दाएं) पर शिफ्ट करना है, यह सूची हेड को लेफ्ट (राइट) सेल से सेल की जगह पर ले जा रहा है और सेल खुद राइट (लेफ्ट) सेल हेड (अच्छी तरह से, एक विशेष केस) असाइनमेंट सेल = 0 लेफ्ट (राइट) सेल्स की खाली सूची के मामले में।
इस दृश्य का लाभ:
- कोई निश्चित-लंबाई सूची (मेमोरी सेविंग) पूर्व-आबाद करने की आवश्यकता नहीं
- असीमित टेप की लंबाई (कंप्यूटर संसाधनों द्वारा लगाए गए प्रतिबंधों को छोड़कर)
एक और स्पष्टीकरण। एक अतुलनीय प्रविष्टि! एस पारा में एक राज्य चर कहा जाता है और चर की एक जोड़ी है!। एस।: एस के साथ और बाहर मोड। यह पूर्व से अगले तक गुजरने वाले मापदंडों के साथ भविष्यवाणी करने के लिए सुविधाजनक है, अर्थात्। अभिलेख
some_pred(In, Out) :- pred1(In, In1), pred2(In1, In2), pred3(In2, Out).
के बराबर:
some_pred(!.S, !:S) :- pred1(!.S, !:S), pred2(!.S, !:S), pred3(!.S, !:S). %
जो बदले में इसके बराबर है:
some_pred(!S) :- pred1(!S), pred2(!S), pred3(!S).
या DCG संकेतन के रूप में:
some_pred --> pred1, pred2, pred3.
लेकिन इसके बारे में और एक लेख में पारे की अन्य विशेषताओं के बारे में अधिक =)