क्लोजर रूपांतरण और उच्च-आदेश फ़ंक्शन कॉल का अलग संकलन

Question

क्या उच्च-आदेश फ़ंक्शन कॉल संकलित करते समय अलग संकलन और विभिन्न प्रकार के बंद रूपांतरण के बीच बातचीत से निपटने का एक मानक तरीका है?

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

Syntax: | clo(args)     | func(args)  | obj(args) 
-------------------------------------------------------------------------------- 
Codegen: | clo.fnc(&clo.env, args) | func(args)  | cls_call(&obj, args) 
      ^ ^     ^    ^ ^
      fn ptr |      +--"top level" fn --+  | 
        +--- "extra" param, compared to source type -----+ 

(सी ++ में, cls_callT::operator()obj के लिए के वर्ग T सी ++ भी अनुमति देता है आभासी functors होगा, लेकिन है कि है। अनिवार्य रूप से एक अतिरिक्त अविवेक के साथ बंद होने का मामला।)

इस बिंदु पर,, map (x => x > 3) lst और map (x => x > y) lst करने के लिए कॉल अलग map कार्यों आह्वान करना चाहिए, क्योंकि पहले उत्थापन के बाद एक साधारण समारोह सूचक है, और दूसरा एक बंद है। (98) दृष्टिकोण, या तो (क कॉल-साइट आकार लेने औपचारिक पैरामीटर प्रकार के माध्यम से करने के लिए कॉल प्राप्त करने वाला बलों जो

1. सी ++:

   मैं इस मुद्दे से निपटने का चार तरीके के बारे में सोच सकते हैं आभासी functor , फ़ंक्शन पॉइंटर, या गैर वर्चुअल फ़ैक्टर) या टेम्पलेट का उपयोग करके अलग संकलन ड्रॉप करें, नीचे प्रभावी समाधान # 2 निर्दिष्ट करें।

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

3. एक वैश्विक रूप से वर्दी कॉल-साइट आकार को प्रबंधित करें। इसका मतलब है कि सभी शीर्ष-स्तरीय फ़ंक्शंस एक स्पष्ट env तर्क लेते हैं, भले ही उन्हें इसकी आवश्यकता न हो, और गैर-बंद करने वाले तर्कों को लपेटने के लिए "अतिरिक्त" बंद किए जाने चाहिए।

4. शीर्ष-स्तरीय कार्यों के लिए "प्राकृतिक" हस्ताक्षर बनाए रखें, लेकिन यह जरूरी है कि उच्च-आदेश फ़ंक्शन पैरा के सभी हैंडलिंग बंद हो जाएं। पहले से बंद कार्यों के लिए "अतिरिक्त" बंद अप्रयुक्त env पैरामीटर को त्यागने के लिए एक रैपर ट्रैम्पोलिन फ़ंक्शन को कॉल करते हैं। यह विकल्प 3 से अधिक सुरुचिपूर्ण लगता है, लेकिन कुशलतापूर्वक कार्यान्वित करने के लिए कठिन है। या तो संकलक कॉल करने वाले सम्मेलन-indepedent रैपर की एक भीड़ उत्पन्न करता है, या यह कॉल करने वाले सम्मेलन के प्रति संवेदनशील Thunks की एक छोटी संख्या का उपयोग करता है ...

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

फिर भी, सवाल:

• करता है इस मुद्दे को साहित्य में एक स्पष्ट नाम नहीं है?
• क्या उपरोक्त चार के अलावा अन्य दृष्टिकोण हैं?
• क्या दृष्टिकोण के बीच अच्छी तरह से ज्ञात ट्रेडऑफ हैं?

Answer 1

यह बहुत सारी विधियों के साथ एक बहुत गहरा सवाल है, और मैं यहां एक विद्वान लेख नहीं लिखना चाहता हूं। मैं सिर्फ सतह को खरोंच कर दूंगा और आपको कहीं और जानकारी के बारे में बताऊंगा। मैं Glorious Glasgow Haskell Compiler के साथ व्यक्तिगत अनुभव पर और Standard ML of New Jersey के साथ-साथ उन प्रणालियों के बारे में लिखित विद्वानों के कागजात के साथ अपनी प्रतिक्रिया का आधार बना रहा हूं।

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

• एक जाना जाता कॉल एक फोन साइट जहां संकलक वास्तव में जानता है इसका मतलब क्या समारोह बुलाया जा रहा है एक कितने मापदंडों यह उम्मीद है।

• एक अज्ञात कॉल का अर्थ है कि संकलक यह नहीं समझ सकता कि कौन सा फ़ंक्शन कहा जा सकता है।

• एक ज्ञात कॉल पूरी तरह से संतृप्त अगर समारोह बुलाया जा रहा है सभी मापदंडों यह उम्मीद हो रही है, और यह कोड के लिए सीधे जा रहा है। समारोह कम तर्क हो रही है, तो की तुलना में यह उम्मीद है, समारोह आंशिक रूप से लागू किया और कॉल परिणाम केवल एक बंद

उदाहरण के लिए के आवंटन में है, अगर मैं लिखना हास्केल में कार्य

mapints :: (Integer -> a) -> [a] 
mapints f = map f [1..] 

तो map पर कॉल और पूरी तरह से संतृप्त पर कॉल किया गया है।
अगर मैं

inclist :: [Integer] -> [Integer] 
inclist = map (1+) 

लिखना तो map करने के लिए कॉल जाना जाता और आंशिक रूप से लागू किया है।
अंत में, यदि मैं

compose :: (b -> c) -> (a -> c) -> (a -> c) 
compose f g x = f (g x) 

लिखना तो f और g के लिए कॉल दोनों अज्ञात हैं।

मुख्य बात परिपक्व कंपाइलर्स ज्ञात कॉल अनुकूलित करें। इस रणनीति के ऊपर आपके वर्गीकरण में ज्यादातर # 2 के तहत आता है।

• एक समारोह को सभी कॉल साइटों में जाना जाता है, तो एक अच्छा संकलक सिर्फ इतना है कि समारोह के लिए सम्मेलन बुला, जैसे, सिर्फ सही रजिस्टरों में तर्क गुजर बनाने के लिए चीजों को अच्छी तरह से बाहर काम एक विशेष उद्देश्य पैदा करेगा ।

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

• यदि कोई ज्ञात कॉल पूरी तरह से संतृप्त नहीं है, तो कंपाइलर कॉलर में बस बंद करने के लिए कोड उत्पन्न करता है।

बंद के प्रतिनिधित्व (या प्रथम श्रेणी के कार्यों में इस तरह के लैम्ब्डा उठाने या defunctionalization रूप में कुछ अन्य तकनीक द्वारा नियंत्रित किया जाता है) बड़े पैमाने पर अज्ञात कॉल बनाम ज्ञात की हैंडलिंग के लिए ओर्थोगोनल है।

(MLton द्वारा उपयोग किए जाने वाले वैकल्पिक दृष्टिकोण का उल्लेख करने लायक हो सकता है: यह एक संपूर्ण प्रोग्राम कंपाइलर है; यह सभी स्रोत कोड को देखता है; यह एक तकनीक का उपयोग करके सभी कार्यों को पहले क्रम में कम कर देता है। वहाँ अभी भी अज्ञात कॉल कर रहे हैं, क्योंकि उच्च क्रम भाषाओं में सामान्य नियंत्रण प्रवाह विश्लेषण असभ्य है)

---

अपने अंतिम सवाल के बारे में

:।

• मैं इस iss लगता है ue "प्रथम श्रेणी के कार्यों को संकलित करने के लिए" नामक गन्दा समस्या का सिर्फ एक पहलू है। मैंने इस मुद्दे के लिए कभी भी विशेष नाम नहीं सुना है।

• हां, अन्य दृष्टिकोण भी हैं। मैंने एक स्केच किया है और दूसरे का उल्लेख किया है।

• मुझे यकीन नहीं है कि ट्रेडऑफ पर कोई बढ़िया, व्यापक अध्ययन है, लेकिन सबसे अच्छा मुझे पता है, जिसे मैं अत्यधिक अनुशंसा करता हूं, साइमन मार्लो और साइमन पेटन जोन्स द्वारा Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-Order Languages है। इस पेपर के बारे में कई महान चीजों में से एक यह है कि यह बताता है कि फ़ंक्शन का प्रकार क्यों नहीं बताता है कि उस फ़ंक्शन पर कॉल पूरी तरह से संतृप्त है या नहीं।

---

अपने गिने विकल्प लपेट के लिए: नंबर 1 एक nonstarter है। लोकप्रिय कंपाइलर संख्या 2 और 3 से संबंधित एक संकर रणनीति का उपयोग करते हैं। मैंने नंबर 4 जैसा कुछ भी नहीं सुना है; ज्ञात और अज्ञात कॉल के बीच भेद फ़ंक्शन प्रकार के तर्कों से शीर्ष-स्तरीय फ़ंक्शंस को अलग करने से अधिक उपयोगी लगता है।