हास्केल फ़ंक्शन परिभाषा और कैशिंग सरणी

Question

मेरे पास हैस्केल में सरणी का उपयोग करके कैशिंग (ज्ञापन) को लागू करने के बारे में एक प्रश्न है। निम्नलिखित पैटर्न काम करता है:

f = (fA !) 
    where fA = listArray... 

लेकिन यह नहीं है (कार्यक्रम की गति पता चलता है कि सरणी प्रत्येक कॉल या कुछ और निर्मित हो रही है): एक जहां खंड के

f n = (fA ! n) 
    where fA = listArray... 

डिफाइनिंग एफए के बाहर ("वैश्विक दायरे" में) भी पैटर्न के साथ काम करता है।

मैं उम्मीद कर रहा था कि कोई मुझे तकनीकी स्पष्टीकरण की दिशा में इंगित कर सकता है कि उपरोक्त दो पैटर्न के बीच क्या अंतर है।

ध्यान दें कि मैं नवीनतम जीएचसी का उपयोग कर रहा हूं, और मुझे यकीन नहीं है कि यह सिर्फ एक कंपाइलर विशिष्टता या भाषा का हिस्सा है।

संपादित करें:! सरणी के उपयोग के लिए प्रयोग किया जाता है, तो एफए! 5 का अर्थ है सी ++ वाक्यविन्यास में एफए [5]। हास्केल की मेरी समझ यह है कि (एफए!) एन वही होगा (एफए! एन) ... यह भी मेरे लिए "एफ एन = एफए! एन" (कोष्ठक के बिना) लिखने के लिए और अधिक पारंपरिक होता। वैसे भी, मुझे वही व्यवहार मिलता है इससे कोई फर्क नहीं पड़ता कि मैं कैसे संश्लेषित करता हूं।

Answer 1

क्या हो रहा है यह जानने का सबसे अच्छा तरीका है संकलक को -v4 के साथ अपने मध्यवर्ती प्रतिनिधित्व को आउटपुट करना है। आउटपुट विशाल है और पढ़ने के लिए थोड़ा मुश्किल है, लेकिन आपको यह पता लगाने की अनुमति देनी चाहिए कि जेनरेट कोड में क्या अंतर है, और कंपाइलर कैसे पहुंचे।

आपको शायद यह पता चलेगा कि fA आपके पहले उदाहरण पर फ़ंक्शन के बाहर ("वैश्विक दायरे" में) स्थानांतरित हो रहा है। आपके दूसरे उदाहरण पर, शायद यह नहीं है (जिसका अर्थ है कि यह प्रत्येक कॉल पर पुनर्निर्मित किया जाएगा)।

फ़ंक्शन के बाहर स्थानांतरित नहीं होने के लिए एक संभावित कारण यह होगा क्योंकि संकलक सोच रहा है कि यह n के मान पर निर्भर करता है। आपके कामकाजी उदाहरण पर, 10 पर fA पर निर्भर करने के लिए n नहीं है।

लेकिन मुझे लगता है कि संकलक fA आपके दूसरे उदाहरण के बाहर आगे बढ़ने से बच रहा है क्योंकि यह एक अंतरिक्ष रिसाव से बचने की कोशिश कर रहा है। गौर करें कि क्या होगा यदि fA, आपके सरणी के बजाय, एक अनंत सूची थी (जिस पर आपने !! ऑपरेटर का उपयोग किया था)। कल्पना कीजिए कि आपने इसे एक बड़ी संख्या के साथ बुलाया है (उदाहरण के लिए f 10000), और बाद में इसे केवल छोटी संख्याओं (f 2, f 3, f 12 ...) कहा जाता है। पहले कॉल से 10000 तत्व अभी भी मेमोरी पर हैं, अंतरिक्ष बर्बाद कर रहे हैं। इसलिए, इससे बचने के लिए, प्रत्येक बार जब आप अपना फ़ंक्शन कॉल करते हैं तो संकलक fA बनाता है।

अंतरिक्ष रिसाव से बचने का संभवतः आपके पहले उदाहरण पर नहीं होता है क्योंकि उस मामले में f वास्तव में केवल एक बार बुलाया जाता है, एक बंद करने पर लौटता है (अब हम शुद्ध कार्यात्मक और अनिवार्य दुनिया की सीमा पर हैं, इसलिए चीजें मिलती हैं थोड़ा और सूक्ष्म)। यह बंद मूल कार्य को प्रतिस्थापित करता है, जिसे कभी भी कभी नहीं कहा जाएगा, इसलिए fA केवल एक बार बुलाया जाता है (और इस प्रकार अनुकूलक इसे फ़ंक्शन के बाहर ले जाने के लिए स्वतंत्र महसूस करता है)। आपके दूसरे उदाहरण पर, f को बंद करके प्रतिस्थापित नहीं किया जाता है (क्योंकि इसका मान तर्क पर निर्भर करता है), और इस प्रकार फिर से कॉल किया जाएगा।

यदि आप इसे और अधिक समझने की कोशिश करना चाहते हैं (जो -v4 आउटपुट पढ़ने में मदद करेगा), तो आप Spineless Tagless G-Machine पेपर (citeseer link) पर एक नज़र डाल सकते हैं।

आपके अंतिम प्रश्न के अनुसार, मुझे लगता है कि यह एक कंपाइलर विशिष्टता है (लेकिन मैं गलत हो सकता हूं)। हालांकि, यह मुझे आश्चर्य नहीं करेगा अगर सभी कंपाइलर एक ही काम करते हैं, भले ही यह भाषा का हिस्सा न हो।

Answer 2

व्यवहार में अंतर हास्केल मानक द्वारा निर्दिष्ट नहीं है। यह सब कहना है कि कार्य समान हैं (परिणामस्वरूप उसी इनपुट को एक ही आउटपुट दिया जाएगा)।

हालांकि इस मामले में अधिकांश कंपाइलर का पालन करने वाले समय और मेमोरी प्रदर्शन की भविष्यवाणी करने का एक आसान तरीका है। फिर मैं जोर देता हूं कि यह आवश्यक नहीं है, केवल इतना है कि अधिकांश कंपाइलर इसे करते हैं।

पहले, शुद्ध लैम्ब्डा अभिव्यक्ति के रूप में अपने दो उदाहरण पुनर्लेखन अनुभाग का विस्तार:

f = let fA = listArray ... in \n -> fA ! n 
f' = \n -> let fA = listArray ... in fA ! n 

संकलनकर्ता साझा करने से संकेत मिलता है बंधन जाने का उपयोग करें। गारंटी यह है कि किसी दिए गए वातावरण में (स्थानीय चर के सेट, लैम्ब्डा बॉडी, ऐसा कुछ), किसी भी पैरामीटर के साथ बाध्यकारी होने का दाहिने तरफ का मूल्यांकन सबसे अधिक बार किया जाएगा। पूर्व में एफए का माहौल संपूर्ण कार्यक्रम है क्योंकि यह किसी भी लैम्ब्डा के नीचे नहीं है, लेकिन बाद वाला वातावरण लम्बाडा के नीचे से छोटा है।

इसका मतलब यह है कि बाद में, एफए प्रत्येक अलग-अलग एन के लिए एक बार मूल्यांकन किया जा सकता है, जबकि पूर्व में यह प्रतिबंधित है।

हम भी बहु तर्क कार्यों के साथ प्रभाव में इस पैटर्न देख सकते हैं:

g x y = (a ! y) where a = [ x^y' | y' <- [0..] ] 
g' x = (\y -> a ! y) where a = [ x^y' | y' <- [0..] ] 

तब में

:

let k = g 2 in k 100 + k 100 

हम गणना हो सकता है एक बार से 2^100 से है, लेकिन में:

let k = g' 2 in k 100 + k 100 

हम केवल एक बार इसकी गणना करेंगे।

यदि आप ज्ञापन के साथ काम कर रहे हैं, तो मैं हैकेज पर डेटा-मेमोकॉम्बिनेटर की सिफारिश करता हूं, जो विभिन्न आकारों के ज्ञापन सारणी की एक लाइब्रेरी है, इसलिए आपको अपना खुद का रोल नहीं करना है।

Answer 3

कूल, आपके उत्तरों के लिए धन्यवाद जो बहुत मदद करता है, और मैं निश्चित रूप से हैकेज पर डेटा-मेमोकॉम्बिनेटर्स की जांच करूँगा। एक सी ++ - भारी पृष्ठभूमि से आ रहा है, मैं समझने के साथ संघर्ष कर रहा हूं कि एक दिए गए कार्यक्रम के साथ हास्केल क्या करेगा (मुख्य रूप से जटिलता के मामले में), जो ट्यूटोरियल में शामिल नहीं होते हैं।