रिकर्सन और स्टैक ओवरफ्लो एरर

Question

आप इस सरल रिकर्सन उदाहरण को कैसे समायोजित करेंगे ताकि पूंछ कॉल अनुकूलन हो (और StackOverflowError नहीं)?

count 0 = 0 
count n = succ (count (pred n)) 
count 100000 

Answer 1

यह स्टैक ओवरफ्लो का प्रकार है जिसे मैं "लंबाई/फ़ोल्डर" प्रकार कहता हूं। ऐसा होता है, जब रिकर्सिव फ़ंक्शन को फ़ंक्शन एप्लिकेशन के सख्त तर्क की गणना करने के लिए लागू किया जाता है जो परिणाम का गठन करता है। की तुलना करें:

-- naive computation of list length 
-- this is not like it's defined in Frege, of course 
length [] = 0 
length (_:xs) = 1 + length xs 

यह भी foldr f साथ होता है जब f अपनी दूसरी बहस में सख्त है।

1. पूंछ प्रत्यावर्तन:

   वहाँ ढेर अतिप्रवाह (SO) के लिए अन्य संभावित कारण हैं। इसे फ्रीज में सबसे कुशलता से संभाला जाता है, क्योंकि एक पूंछ रिकर्सिव फ़ंक्शन को थोड़ी देर के लिए संकलित किया जाता है। अन्य जेवीएम भाषाओं के विपरीत वास्तव में एसओ का कारण कभी नहीं होगा।

2. स्पष्ट अप्रत्यक्ष पूंछ रिकर्सन: (उदा। a पूंछ b पर कॉल करता है, जो पूंछ c पर कॉल करता है ..., जो पूंछ a पर कॉल करता है)। इसका कभी भी फ्री में एसओ में परिणाम नहीं होना चाहिए।
3. इतने गहरे घोंसले वाले हिस्सों का निर्माण जो एसओ मूल्यांकन पर होता है। हास्केल में foldl में यह होता है। फ्रीज में, मानक fold संचयक में सख्त है और इसलिए कई मामलों में प्रतिरक्षा है। हालांकि, निम्न सूचियों पर निम्नलिखित अभी भी बहती है: fold (<>) mempty (map (Just . Sum) [1..10000])
4. हमारे उदाहरण के रूप में लंबाई/गुना प्रकार की रिकर्सन।
5. गैर पूंछ में Recursion कॉल:

यहाँ पिछले मामले के लिए एक उदाहरण है:

even 0 = true 
    even n = case even (pred n) of 
      true -> false 
      false -> true 

दूसरे समीकरण शब्दार्थ even n = not (even (pred n)) के बराबर है और इस तरह 4 का एक और भी अधिक दुर्भावनापूर्ण संस्करण है।

:

अपने प्रश्न, अपने उदाहरण में एक एक संचायक इस्तेमाल कर सकते हैं एक पूंछ पुनरावर्ती संस्करण बनाने के लिए उत्तर देने के लिए

यह हास्केल में शायद ध्यान देने योग्य है कि आपके उदाहरण भी विफल रहता है:

GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help 
Loading package ghc-prim ... linking ... done. 
Loading package integer-gmp ... linking ... done. 
Loading package base ... linking ... done. 
Prelude> let count 0 = 0; count n = succ (count (pred n)) 
Prelude> count 10000 
10000 
Prelude> count 100000 
100000 
Prelude> count 1000000 
1000000 
Prelude> count 10000000 
10000000 
Prelude> count 100000000 
*** Exception: stack overflow 

कारण यह है कि यह केवल बहुत अधिक संख्या के साथ overflows कि हास्केल आरटीएस एक तरीका है कि बेहतर के लिए अनुकूल है में राम का प्रबंध करती है कार्यात्मक प्रोग्रामिंग, जबकि JVM स्टार्टअप पर एक छोटा डिफ़ॉल्ट स्टैक आवंटित करता है, जो कुछ 1000 की कॉल गहराई को सर्वोत्तम रूप से समायोजित करता है।

आप अपने कार्यक्रम के साथ बहुत अधिक से अधिक संख्या की गणना कर सकता फ्रेज में भी जब आप बड़ा ढेर आवंटित करने के लिए JVM मजबूर:

java -Xss512m .... 

अनुभव से पता चलता है कि आकार 512 एम के एक ढेर के लिए approximatly 10 लाख की एक कॉल गहराई की अनुमति देता है एकल तर्क कार्य।

हालांकि, यह सामान्य समाधान नहीं है, क्योंकि तब JVM इस स्टैक आकार के साथ सभी धागे बनाता है।इस प्रकार कीमती राम बर्बाद हो जाती है। और यहां तक ​​कि जब आपके पास बहुत सी रैम है, तो आप शायद 2 जी से अधिक स्टैक बनाने में सक्षम नहीं होंगे।

फ्रेज का अगला प्रमुख संस्करण में, ढेर अतिप्रवाह प्रकार 3 और 4 के कुछ रोग मामलों (ऊपर देखें) बेहतर प्रबंधित किया जाएगा, उम्मीद है कि। आज के रूप में, हालांकि, ऐसी संरचनाएं केवल छोटी समस्या के आकार के लिए काम करती हैं जो जेवीएम स्टैक फिट करने के लिए होती हैं।