एफ # पूंछ पुनरावृत्ति। पानी के नीचे की रेक। भाग 1

विनी द पूह: ओह, आपकी पूंछ का क्या हुआ?
Eeyore: उसके साथ क्या हो सकता है?
विनी द पूह: वह नहीं है।
Eeyore: तुम गलत नहीं थे?
विनी द पूह: पूंछ या तो वहाँ है या बिल्कुल नहीं है! कोई गलती नहीं है।
Eeyore: और फिर वहाँ क्या है?
विनी द पूह: कुछ नहीं!

हमारे प्रोजेक्ट में, सर्वर घटकों में से एक में, अगले रीफैक्टरिंग के बाद, मेमोरी प्रवाहित होने लगी। ऐसा प्रतीत होगा कि .NET, F #, प्रबंधक कोड, कचरा संग्रह, सभी चीजें, लेकिन स्मृति कहीं न कहीं लीक हो गई है। रातों की नींद और खराब हुई नसों की कीमत पर, रिसाव का स्रोत पाया गया था। यह पता चला कि समस्या कोड के एक टुकड़े की वजह से थी, जो कि एफ # ट्यूटोरियल से कॉपी की गई लगभग एक से एक थी।

यह पूरी तरह से पूंछ पुनरावृत्ति में था, या बल्कि, जैसा कि अप्रत्याशित स्थानों में इसकी अनुपस्थिति में निकला था।

पूंछ की पुनरावृत्ति

पुनरावर्तन संभवतः कार्यात्मक प्रोग्रामिंग के शस्त्रागार में सबसे महत्वपूर्ण उपकरणों में से एक है। और चूंकि पुनरावर्ती कॉल एक स्टैक का उपयोग करते हैं, जो कि आप जानते हैं, असीमित नहीं है, ऐसा लग सकता है कि पुनरावृत्ति का उपयोग सीमित है, और पुनरावृत्ति की गहराई परिमित है।

हालांकि, सब कुछ इतना उदास नहीं है, लगभग सभी कार्यात्मक भाषा संकलकों में पूंछ पुनरावृत्ति अनुकूलन के रूप में ऐसी उपयोगी चीज है, जिसके साथ आप स्टैक का उपयोग किए बिना पुनरावृत्ति का उपयोग कर सकते हैं, जो बदले में पुनरावर्तन घोंसले पर प्रतिबंध को हटा देता है।

पूंछ पुनरावृत्ति पुनरावृत्ति का एक विशेष मामला है, जब पुनरावर्ती कॉल को पुनरावृत्ति द्वारा प्रतिस्थापित किया जा सकता है। एक ओर, यह टेल-स्टाइल लॉजिक लिखने के लिए प्रोग्रामर की अंतरात्मा की आवाज बनी हुई है, दूसरी ओर, कंपाइलर को भी पूंछ की पुनरावृत्ति का पता लगाना चाहिए और पुनरावृत्ति को स्पिन करना चाहिए।

आमतौर पर, एक नौसिखिया "कार्यात्मक" जल्दी से आंख और हाथ को भर देता है और हर जगह पूंछ पुनरावृत्ति का उपयोग करता है। लेकिन कुछ विशेष मामले हैं जब एक फ़ंक्शन है कि, ऐसा प्रतीत होता है, वास्तव में एक लोहा "पूंछ" है, ऐसा नहीं है। ये विशेष मामले बहुत अप्रिय परिणाम पैदा कर सकते हैं, और बहुत समय और नसों को मार सकते हैं।

आइए पहले ऐसे मामले को देखें और एक नियम बनाएं जिसके साथ आप "परेशानी" से बच सकते हैं।

आइए सबसे पहले एक सरल कार्य करें जो सभी संख्याओं को एक से N तक ले जाता है:

let rec sum i = if i <= 0L then 0L else i + sum (i - 1L) > sum 10L;; val it : int64 = 55L 

एक बिंदु को छोड़कर, सब ठीक है। यदि हम कम से कम 100,000 के लिए राशि की गणना करने का प्रयास करते हैं, तो हमारे माथे में एक StackOverflowException मिलती है। यानी गणना के लिए हमारे पास पर्याप्त स्टैक नहीं है:

 > sum 100000L;; Process is terminated due to StackOverflowException. 

इस समस्या का उत्तर बैटरी को पुनरावर्ती फ़ंक्शन के तर्क के रूप में उपयोग कर रहा है:

 let sumTailRec i = let rec loop acc i = if i <= 0L then acc else loop (acc + i) (i - 1L) loop 0L i 

हम अपने फ़ंक्शन को इस तरह से फिर से लिखते हैं कि इसमें एक स्टैक की आवश्यकता नहीं है, इसके बजाय वापस राशि पर जाने के लिए, हम बैटरी को एक तर्क के रूप में अग्रेषित करते हैं।

गणना के क्रम (तर्क 5 के लिए) को निम्नानुसार चित्रित किया जा सकता है। बिना पूंछ पुनरावृत्ति:

 sum: 5 + (4 + (3 + (2 + (1 + (0))))) –       ,  ,      .         . 

पूंछ पुनरावृत्ति के साथ:

 sumTailRec: (((0 + 5) + 4) + 3) + 2) + 1) – ,      ,       ,       . 

नया फ़ंक्शन पहले से ही एक मनमाने ढंग से बड़ी संख्या को पच सकता है (जब तक कि int64 पर्याप्त है)।

 > sumTailRec 10000000L;; val it : int64 = 50000005000000L 

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

 let sumFTailRec fi = let rec loop acc i = if i <= 0L then acc else loop (acc + fi) (i - 1L) loop 0L i 

नए संस्करण में, हमारे पास एक और पैरामीटर है - एक फ़ंक्शन, जिसकी गणना परिणाम को सारांशित करने की आवश्यकता है। यहां एक विकल्प है जो संख्याओं को स्वयं संक्षेप में प्रस्तुत करता है:

 > sumFTailRec (fun i -> i) 10000000L val it : int64 = 50000005000000L 

और यहाँ, जो चौकों को बोता है:

 > sumFTailRec (fun i -> i*i) 10000000L val it : int64 = 1291990006563070912L 

अभी तक तो अच्छा है। लेकिन एक छोटी सी बारीकियों है, जो फ़ंक्शन प्रसारित होता है वह एक अपवाद फेंक सकता है। यहाँ एक उदाहरण है:

 > let someProblemFun i = i/((i+1L) % 1000L) > sumFTailRec someProblemFun 10000000L System.DivideByZeroException: Attempted to divide by zero. Stopped due to error 

समस्या

I = 999 के मान के साथ, हमारे पास शून्य से एक विभाजन है। मान लीजिए कि हम एक अपवाद के साथ, गणना को क्रैश करने के लिए नहीं, बल्कि समस्या तत्व को अनदेखा करना चाहते हैं। हमें अपवाद से निपटने की आवश्यकता होगी। एक तार्किक और अपेक्षित समाधान खुद पता चलता है:

 let sumFTailRecWithTry fi = let rec loop acc i = if i <= 0L then acc else try loop (acc + fi) (i - 1L) with exc -> printfn "exn raised:%s" exc.Message loop acc (i - 1L) loop 0L i 

तो कोशिश करें:

 > sumFTailRecWithTry someProblemFun 10000L exn raised:Attempted to divide by zero. ... exn raised:Attempted to divide by zero. val it : int64 = 351405L 

हमें परिणाम मिला, अपवादों को पकड़ा गया, सब कुछ ठीक लग रहा है। अब एक और अधिक गंभीर संख्या को खिलाने की कोशिश करें:

 > sumFTailRecWithTry someProblemFun 10000000L exn raised:Attempted to divide by zero. ... exn raised:Attempted to divide by zero. Process is terminated due to StackOverflowException. 

उफ़ ... क्या बात है? पहली नज़र में, हमारे पास पूंछ पुनरावृत्ति के साथ एक फ़ंक्शन है, स्टैक अचानक क्यों समाप्त हो गया?

जैसा कि आप अनुमान लगा सकते हैं, समस्या निर्माण के साथ ... कोशिश में है। तथ्य यह है कि यदि पुनरावर्ती ब्लॉक में एक पुनरावर्ती कॉल किया जाता है, तो पूंछ पुनरावृत्ति को बंद कर देती है, और यह एक नियमित पुनरावृत्ति बन जाती है। क्यों? क्योंकि किसी भी बाद के पुनरावर्ती कॉल में लूप के लिए, एक अपवाद सैद्धांतिक रूप से फेंक दिया जा सकता है, क्योंकि यदि हमें इसे संसाधित करने की आवश्यकता है, तो हमें उस जगह पर स्टैक को याद रखना होगा जहां अपवाद फेंकने पर हमें वापस लौटना होगा।

निर्णय

इनमें से कौन सी अप्रिय स्थिति है? बहुत सरल, आपको एक कोशिश के साथ एक पुनरावर्ती कॉल को लपेटने की आवश्यकता नहीं है ... ब्लॉक के साथ , क्योंकि हम केवल एक अपवाद की उम्मीद करते हैं जब हम "बाहरी" फ़ंक्शन को कॉल करते हैं, इसलिए हमें केवल इस कॉल को लपेटने की आवश्यकता है:

 let sumFReallyTailRecWithTry fi = let rec loop acc i = if i <= 0L then acc else let fRes = try fi with exc -> //printfn "exn raised:%s" exc.Message 0L loop (acc + fRes) (i - 1L) loop 0L i 

हम कोशिश करते हैं:

 > sumFReallyTailRecWithTry someProblemFun 10000000L val it : int64 = 374200932236L 

देखा! स्टैक इस बार पर्याप्त था, या बल्कि, वह अछूता रह गया था।

तो नियम: एक कोशिश में पूंछ कॉल कभी नहीं ... ब्लॉक के साथ।

दूसरी श्रृंखला में, async {...} और मेलबॉक्सप्रोसेसर के लिए पूंछ पुनरावृत्ति के बारे में चौंकाने वाले खुलासे होंगे।