एस ++ टी बड़े पैमाने पर एक स्टैक ओवरफ़्लो क्यों नहीं लेता है?

Question

क्यों

Prelude> head $ reverse $ [1..10000000] ++ [99] 
99 

एक ढेर अतिप्रवाह त्रुटि लिए नेतृत्व नहीं करता मैं सोच रहा हूँ। प्रस्तावना में ++ सीधे आगे और लगता है गैर पूंछ पुनरावर्ती:

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

संपादित करें: प्रारंभ में, मैंने सोचा था कि इस मुद्दे को विशेष रूप से नए सिरे से लिखना के साथ, जिस तरह ++ प्रस्तावना में परिभाषित किया गया है के साथ क्या करने के लिए कुछ नहीं है नियम, इसलिए सवाल नीचे जारी रहा। चर्चा ने मुझे दिखाया कि यह मामला नहीं है। मुझे लगता है कि अब कुछ आलसी मूल्यांकन प्रभाव कोड को स्टैक ओवरफ़्लो के बिना चलाने का कारण बनता है, लेकिन मुझे यह नहीं पता कि कैसे।

तो बस इसके साथ, इसे एक स्टैक ओवरफ़्लो में चलाया जाना चाहिए, है ना? तो मैं समझ यह शायद GHC जादू कि ++ की परिभाषा इस प्रकार के साथ कुछ है:

{- # नियम "++" [~ 1] forall XS वाईएस। xs ++ ys = augment (\ c n -> foldr c n xs) ys # -}

* क्या यह स्टैक ओवरफ़्लो से बचने में मदद करता है? क्या कोई इस कोड के टुकड़े में क्या हो रहा है इसके लिए कुछ संकेत प्रदान कर सकता है? **

Answer 1

यह दुभाषिया में भी नहीं है - यहां तक ​​कि दुभाषिया में भी, जहां कोई अनुकूलन नहीं है और नियमों को फिर से लिखना नहीं है - क्योंकि यह ढेर का उपयोग नहीं करता है।की परिभाषा को

देखो (++), उदाहरण के लिए ,:

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

मुख्य बात x : (xs ++ ys) है - जो है, यह (:) "विपक्ष" निर्माता द्वारा सुरक्षित प्रत्यावर्तन है। चूंकि हास्केल आलसी है, यह विपक्षी संचालन के लिए एक थंक आवंटित करता है, और रिकर्सिव कॉल इस (ढेर-आवंटित) थंक पर जाता है। तो आपका ढेर आवंटन अब ढेर आवंटन है, जो काफी विस्तार कर सकता है। तो यह सब बड़ी सूची में चलता है, जो ट्रैपिंग वाले लोगों को प्रतिस्थापित करने के लिए ढेर पर नई विपक्षी वस्तुओं को आवंटित करता है। आसान!

"रिवर्स" थोड़ा अलग है:

reverse l = rev l [] 
    where 
    rev []  a = a 
    rev (x:xs) a = rev xs (x:a) 

है यही कारण है कि एक पूंछ पुनरावर्ती, संचायक शैली समारोह है, तो फिर, यह ढेर पर आवंटित करेगा।

तो आप देखते हैं, काम करता है,, ढेर पर विपक्ष कोशिकाओं का उपयोग कर पर भरोसा करने के बजाय ढेर पर इसलिए कोई ढेर अतिप्रवाह।

वास्तव में इस कील करने के लिए, जी सी वी एम से क्रम आंकड़े देखते:

$ time ./B +RTS -s 
99 

     833 MB total memory in use (13 MB lost due to fragmentation) 
     Generation 0: 3054 collections,  0 parallel, 0.99s, 1.00s elapsed 
     %GC time  82.2% (85.8% elapsed) 

आपके बड़ी सूची है - यह ढेर पर आवंटित किया जाता है, और हम समय का 80% खर्च विपक्ष की सफाई नोड्स जो (++) द्वारा बनाए जाते हैं।

सबक: आप अक्सर ढेर के लिए ढेर व्यापार कर सकते हैं।

Answer 2

EDIT: नीचे दिया गया जवाब पूरी तरह से अप्रासंगिक है, अगर गलत नहीं है। डॉन स्टीवर्ट, जो दर्शाता है कि वह वास्तव में आलसी मूल्यांकन को समझता है, सही स्पष्टीकरण है।

---

आप ghc -ddump-simpl चलाते हैं, तो आपको लगता है कि कार्यों इस्तेमाल किया जा रहा GHC.Base.++ और GHC.List.reverse दिखाई देंगे। इन कार्यों को बड़े सूचियों पर ढेर को बहने के लिए इंजीनियर नहीं किया गया है। प्रीलूड में आप जो देखते हैं वह एक "संदर्भ कार्यान्वयन" है, वास्तव में संकलित कोड नहीं है।

यहाँ कुछ कोड मैं GHC स्रोत वितरण से बाहर खोदा है:

reverse     :: [a] -> [a] 
#ifdef USE_REPORT_PRELUDE 
reverse     = foldl (flip (:)) [] 
#else 
reverse l = rev l [] 
    where 
    rev []  a = a 
    rev (x:xs) a = rev xs (x:a) 
#endif 

और यह:

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

{-# RULES 
"++" [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs)  ys 
    #-} 

पहले मामले में, यह स्पष्ट क्या हो रहा है होना चाहिए। दूसरे में, मैं पुनः लिखने के नियमों पर थोड़ा अस्पष्ट हूं ...

Answer 3

प्रस्ताव में ++ सीधे आगे और गैर-पूंछ-पुनरावर्ती लगता है ... तो बस इसके साथ, इसे भागना चाहिए एक ढेर अतिप्रवाह, है ना?

हास्केल में पूंछ-रिकर्सिव की तुलना में अक्सर पूंछ-रिकर्सिव बेहतर नहीं है, क्योंकि पूंछ-रिकर्सिव चीजें आलसी नहीं हो सकती हैं। आपके द्वारा सूचीबद्ध परिभाषा एक पूंछ-पुनरावर्ती व्यक्ति की तुलना में काफी बेहतर है, क्योंकि एक पूंछ-पुनरावर्ती व्यक्ति रिकर्सिंग और पूरी सूची उत्पन्न करेगा, भले ही आपको केवल पहले तत्व की आवश्यकता हो; जबकि एक गैर-पूंछ रिकर्सिव केवल आवश्यकतानुसार उतना ही काम करेगा।