जावास्क्रिप्ट पूंछ पुनरावृत्ति अनुकरण

यदि किसी और को पता नहीं है कि पूंछ की पुनरावृत्ति क्या है, तो यहां एक विधि का एक सरल उदाहरण है जो 1 से n तक प्राकृतिक संख्या जोड़ता है (n n0):

function add(n,acc) { if(n===0) return acc; return add(n-1,acc+n); } 

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

 function add(n) { if(n===0) return 0; return n+add(n-1); } 

कई कारणों से, जावास्क्रिप्ट में पूंछ पुनरावृत्ति का समर्थन नहीं किया जाता है ( स्टैकऑवरफ़्लो पर इस विषय पर चर्चा होती है)। इसलिए, ऐड (100000.0) जैसी कॉल अपवाद के साथ समाप्त होगी। Habré पर सेटटाइमआउट के माध्यम से इस समस्या को हल करने का प्रयास किया गया था , लेकिन यह बहुत ईमानदार नहीं है और बहुत सुंदर नहीं है। एक स्प्रिंगबोर्ड का उपयोग करके पायथन भाषा के लिए और अधिक सुरुचिपूर्ण समाधान प्रस्तावित किया गया था। जावास्क्रिप्ट के लिए एक समान दृष्टिकोण यहां चर्चा की गई है । लेकिन मैं चाहता था कि यह जल्दी से काम करे और यह कार्य सीधे ऊपर के उदाहरण में लिखा जा सके। आइए देखें कि क्या किया जा सकता है।

इस लेख के ढांचे में, हम एक सीमित, बल्कि लोकप्रिय मामले पर विचार करेंगे, जब कोई फ़ंक्शन केवल पूंछ विधि द्वारा कॉल करता है (यह किसी अन्य फ़ंक्शन को कॉल कर सकता है, लेकिन उनकी कॉल अनुकूलित नहीं होगी)। इस प्रकार, आपको फिर से कॉल करने के बजाय, आपको तर्क मानों को नए के साथ बदलने और वर्तमान फ़ंक्शन की शुरुआत में जाने की आवश्यकता है। जावास्क्रिप्ट में कोई गोटो ऑपरेटर नहीं है, लेकिन आप हमेशा एक फ़ंक्शन को इस तरह से ब्लॉक में लपेट सकते हैं:

 $tail$label:while(true) { < >; return; } 

फिर continue $tail$label हुए फ़ंक्शन की शुरुआत में जाएं। इस तरह के संक्रमण के साथ एक फ़ंक्शन कॉल को कैसे बदलें? मन में आया आसान तरीका फ़ंक्शन को एक और एक के साथ बदलना है जो एक अपवाद फेंकता है। फिर आप इसे पकड़ सकते हैं और मापदंडों को फिर से लिख सकते हैं। यह कुछ इस तरह दिखेगा:

 function add(n,acc) { function add() {throw arguments;} while(true) { try { if(n===0) return acc; return add(n-1,acc+n); } catch($tail$ex) { n = $tail$ex[0]; acc = $tail$ex[1]; } } } 

जैसा कि आप देख सकते हैं, खुद के बजाय, हम अब एक नेस्टेड फ़ंक्शन को कहते हैं जो एक अपवाद को फेंकता है। हम इनायत से इसे पकड़ लेते हैं, तर्कों को फिर से लिखते हैं और लूप के अगले पुनरावृत्ति पर जाते हैं (यहां तक ​​कि लेबल उपयोगी नहीं है)।

लेकिन मैं हर बार यह लिखना नहीं चाहूंगा, कार्य केवल लिखना था। एक में एक साधारण फ़ंक्शन का रीमेक कैसे करें? हम फ़ंक्शन के स्रोत कोड को डिक्रिप्ट करते हैं (उपयोग करते हुए), इसे ठीक करें और इसे इस तरह से eval का उपयोग करके संकलित करें:

 Function.prototype.tail = function() { var funcStr = Object.toString.apply(this); var paramsPos = funcStr.indexOf('('); var paramsEndPos = funcStr.indexOf(')'); var bodyPos = funcStr.indexOf('{'); var bodyEndPos = funcStr.lastIndexOf('}'); var name = funcStr.substring("function".length, paramsPos).replace(/\s*/g, ""); var args = funcStr.substring(paramsPos+1, paramsEndPos).replace(/\s*/g, "").split(","); var body = funcStr.substring(bodyPos+1, bodyEndPos); var paramPassString = ""; for(var i=0; i<args.length; i++) paramPassString += args[i]+"=$tail$ex["+i+"];"; var newBody = "function "+name+"() {throw arguments;} while(true) {try{"+body+ "return;}catch($tail$ex) {"+paramPassString+"}}"; return eval("var $tail$function = function "+name+"("+args.join(",")+") {\n"+ newBody+"};$tail$function"); } 

सबसे पहले, फ़ंक्शन के स्रोत कोड में, इसका नाम, तर्क और निकाय खोजे जाते हैं। फिर, शरीर के सामने और उसके बाद, अतिरिक्त लाइनें उत्पन्न होती हैं, जिसके बाद सब कुछ वापस फ़ंक्शन में एकत्र किया जाता है। इस दृष्टिकोण की निम्नलिखित सीमाएँ हैं:

• फ़ंक्शन का एक नाम होना चाहिए;
• एक फ़ंक्शन को खुद को विशेष रूप से पूंछ तरीके से कॉल करना चाहिए;
• खुद को कॉल एक कोशिश-पकड़ने वाले ब्लॉक में नहीं होना चाहिए (सिद्धांत रूप में, यह पिछले एक से निम्नानुसार है)।

इस प्रकार, जबकि (100000,0) क्रैश, add.tail () (100000,0) सब कुछ पूरी तरह से गिनता है।

लेकिन इस तरह के समाधान की कीमत क्या है? सुविधा के लिए, हम फंक्शन प्रोटोटाइप में सहायक फ़ंक्शन समय जोड़ेंगे:

फ़ंक्शन एक तर्क के रूप में प्रारंभ की संख्या लेता है और समय औसत करता है। इन परीक्षणों को जोड़ें:

 var addTail = add.tail(); (function() {return add(10000,0)}).time(500); (function() {return add(100000,0)}).time(500); (function() {return addTail(10000,0)}).time(500); (function() {return addTail(100000,0)}).time(500); 

अब Google Chrome 25 में यह सब सामग्री चलाएं और निराशाजनक परिणाम देखें:

 Code: return add(10000,0); result: 50005000; time=0.102 Code: return add(100000,0); error: RangeError: Maximum call stack size exceeded; time=0.162 Code: return addTail(10000,0); result: 50005000; time=2.392 Code: return addTail(100000,0); result: 5000050000; time=24.826 

हालाँकि हम अब पुनरावृत्तियों की संख्या तक सीमित नहीं हैं, लेकिन प्रदर्शन में 24-गुना की कमी कृपया नहीं कर सकते। और क्या किया जा सकता है?

स्पष्ट रूप से धीमी चीजों (अपवादों और तर्कों) के बिना करने के लिए, आपको उस फ़ंक्शन के शरीर में प्रवेश करना होगा जिसे हम बदल रहे हैं। यहाँ, निश्चित रूप से, आदर्श रूप से आपको जावास्क्रिप्ट पार्सर ( jslint.js पर आधारित) लिखना चाहिए। लेकिन विचार को स्पष्ट करने के लिए, नियमित रूप से अभिव्यक्ति होगी, हालांकि उन्हें एक निश्चित प्रारूप में कोड की आवश्यकता होती है।

 Function.prototype.tail2 = function() { var funcStr = Object.toString.apply(this); var paramsPos = funcStr.indexOf('('); var paramsEndPos = funcStr.indexOf(')'); var bodyPos = funcStr.indexOf('{'); var bodyEndPos = funcStr.lastIndexOf('}'); var name = funcStr.substring("function".length, paramsPos).replace(/\s*/g, ""); var args = funcStr.substring(paramsPos+1, paramsEndPos).replace(/\s*/g, "").split(","); var body = funcStr.substring(bodyPos+1, bodyEndPos); body = body.replace(new RegExp("return\\s+"+name+"\\s*\\((.+?)\\);", "g"), function(match,argsStr) { var passArgs = argsStr.split(","); var result = ""; for(var i=0; i<args.length; i++) result+="var $tail$arg"+i+"="+passArgs[i]+";" for(var i=0; i<args.length; i++) result+=args[i]+"="+"$tail$arg"+i+";" return "{"+result+"continue $tail$label;}"; }); var newBody = "$tail$label:while(true) {"+body+"return;}"; return eval("var $tail$function = function "+name+"("+args.join(",")+") {"+newBody+"};$tail$function"); } 

यहां हम फॉर्म return < >(val1, val2, ..., valN) की एक स्ट्रिंग की प्रत्येक घटना को चालू करते return < >(val1, val2, ..., valN) एक ब्लॉक में, जहां मध्यवर्ती चर के माध्यम से हम तर्कों को नए मूल्य प्रदान करते हैं, और फिर कॉल जारी रखते हैं। मैं तुरंत ही कहूंगा कि कोड बहुत भोला है और यदि आपके पास अतिरिक्त कोष्ठक हैं या उदाहरण के लिए, तो?:।

हम परीक्षण कर रहे हैं:

 var addTail2 = add.tail2(); (function() {return addTail2(10000,0)}).time(500); (function() {return addTail2(100000,0)}).time(500); 

परिणाम प्रभावशाली हैं:

 Code: return addTail2(10000,0); result: 50005000; time=0.022 Code: return addTail2(100000,0); result: 5000050000; time=0.222 

यह मूल से भी तेज है! बेशक, अब हम फ़ंक्शन कॉल पर बचत कर रहे हैं।

और क्या परीक्षण करना है? उपरोक्त लेख से फाइबोनैचि संख्याओं को खोजने के लिए मूल कार्य करें :

 function cpsFib(n, prev, cur, _return) { if (n < 2) { return _return(cur); } return cpsFib(--n, cur, cur + prev, _return); } function identity(x) {return x} var cpsFibTail = cpsFib.tail(); var cpsFibTail2 = cpsFib.tail2(); (function() {return cpsFib(1300, 0, 1, identity)}).time(5000); (function() {return cpsFibTail(1300, 0, 1, identity)}).time(5000); (function() {return cpsFibTail2(1300, 0, 1, identity)}).time(5000); 

परिणाम:

 Code: return cpsFib(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.0222 Code: return cpsFibTail(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.3436 Code: return cpsFibTail2(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.0036 

यदि हम लेख से कार्यान्वयन लेते हैं, तो यह इस प्रकार है:

 Code: return cpsFib.tco(1300, 0, 1, identity); result: 2.159968028316171e+271; time=0.187 

अपवादों के साथ हमारे संस्करण की तुलना में तेज़, लेकिन अभी भी नियमित पुनरावर्ती रूप की तुलना में 8 गुना धीमा और हमारे अनुकूलित की तुलना में 52 गुना धीमा है।

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