पूंछ रिकर्सन का उपयोग करने के लिए एक फ़ंक्शन को परिवर्तित करना - एक औपचारिक अध्ययन

Question

क्या किसी ने औपचारिक पेपर लिखा है जो स्वचालित रूप से फ़ंक्शन को बदलने के लिए एक विधि का वर्णन करता है (स्वचालित रूप से) पूंछ रिकर्सिव होने के लिए? मैं विश्वविद्यालय स्तर के औपचारिक उपचार की तलाश कर रहा हूं जिसमें सीमाएं (कार्यों के प्रकार जिन्हें परिवर्तित किया जा सकता है), रूपांतरण के लिए प्रक्रियाएं, और यदि संभव हो, तो शुद्धता का सबूत? हास्केल में उदाहरण बोनस होंगे।

Answer 1

फ़ंक्शन को स्वचालित रूप से बदलने के लिए एक विधि (स्वचालित रूप से) पूंछ रिकर्सिव होने के लिए?

• मान्यता है कि किसी दिए गए पुनरावर्ती क्रिया एक पूंछ पुनरावर्ती रूप में बदला जा सकता है और कर रही है कि परिवर्तन
• को लागू करने पूंछ एक कुशल तरीके से कहता है हां, तो:

तो वहाँ इस के दो हिस्से हैं परिवर्तन के लायक है।

पूंछ प्रत्यावर्तन

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

उदा। योजना के लोग वर्णन करते हैं:

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

• Compiling Higher-Order Languages into Fully Tail-Recursive Portable C

पूंछ में कार्यों को बदलने कॉल

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

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

• Secrets of the GHC inliner

पूंछ कॉल उन्मूलन

एक बार जब आप एक पूंछ पुनरावर्ती रूप में अपने कार्यों है, तो आप उस effiicently कार्यान्वित करना चाहते हैं। यदि आप एक लूप उत्पन्न कर सकते हैं, तो यह एक अच्छी शुरुआत है।अपने लक्ष्य मशीन नहीं है, तो tail call elimination "कुछ चाल की आवश्यकता होगी। Odersky और Schinz, नीचे उद्धृत के शब्दों में,

विभिन्न तकनीकों सामान्य (और न केवल पुनरावर्ती खत्म करने के लिए पिछले कुछ वर्षों में प्रस्तावित किया गया है) पूंछ कहता है, ज्यादातर compilers को लक्षित सी

के लिए ... एक बड़ा समारोह में पूरे कार्यक्रम रखा और समारोह अनुकरण करने के लिए प्रत्यक्ष छलांग का उपयोग कर या इस समारोह के अंदर बयान स्विच कॉल।

... एक लोकप्रिय तकनीक ट्रामपोलिन का उपयोग करना है। एक ट्रैम्पोलिन एक बाहरी फ़ंक्शन है जो बार-बार एक आंतरिक फ़ंक्शन को कॉल करता है। प्रत्येक बार आंतरिक फ़ंक्शन किसी अन्य फ़ंक्शन को कॉल करने की इच्छा रखता है, यह सीधे इसे कॉल नहीं करता है लेकिन बस ट्रैम्पोलिन में अपनी पहचान (जैसे बंद होने के रूप में) देता है, जो तब कॉल करता है। इस प्रकार असीमित ढेर वृद्धि से बचा जाता है, लेकिन कुछ प्रदर्शन अनिवार्य रूप से खो जाता है, अधिकांशतः क्योंकि ट्रैम्पोलिन द्वारा बनाई गई सभी कॉल को सांख्यिकीय रूप से अज्ञात कार्यों पर कॉल करती हैं।

एक और तकनीक हेनरी बेकर उनकी तकनीक के साथ "चेनी एमटीए पर", कार्यक्रम पहले निरंतरता शैली (सीपीएस) गुजर रहा है, इसलिए पूंछ कॉल में सभी कॉल्स मोड़ करने के लिए परिवर्तित किया जाना है, और फिर हो सकता है संकलित है हमेशा की तरह। रन-टाइम पर, जब स्टैक ओवरफ्लो होने वाला होता है, तो वर्तमान निरंतरता कॉल स्टैक के नीचे ट्रैम्पोलिन "प्रतीक्षा" में निर्मित और लौटा (या लांगजंपेड) है।

• Tail call elimination on the Java Virtual Machine, मिशेल Schinz मार्टिन ओडर्स्की, 2001

• हेनरी जी बेकर, जूनियर कान्स चाहिए नहीं कान्स अपने तर्कों, भाग द्वितीय: एमटीए ड्राफ़्ट संस्करण, जनवरी 1994 पर चेनी ।

Answer 2

बुध में चीजों को स्वचालित रूप से चीजों को बनाने के लिए कुछ अनुकूलन शामिल हैं। (Mercury एक प्रवर्तन-शुद्धता तर्क प्रोग्रामिंग भाषा है, इसलिए यह कार्यों के बजाय भविष्यवाणियों के बारे में बात करता है, लेकिन कई विचार एक ही विचार है जो बुध कार्यक्रमों पर हास्केल के रूप में लागू होते हैं। कार्यात्मक के बजाए तार्किक होने की तुलना में बहुत बड़ा अंतर यह है कि यह है आलसी के बजाय सख्त)

"संचयक परिचय" आवर्ती संचालन को रिकर्सिव कॉल से पहले स्थानांतरित करने की अनुमति देने के लिए एक अतिरिक्त संचयक पैरामीटर के साथ भविष्यवाणियों के विशेष संस्करण उत्पन्न करता है। स्पष्ट रूप से यह ऑप्टिमाइज़ेशन आवश्यक रूप से पूंछ-पुनरावर्ती भविष्यवाणियों के परिणामस्वरूप नहीं होता है, लेकिन अक्सर दूसरे प्रारूप द्वारा अनुकूलित किया जा सकता है:

"अंतिम कॉल मॉड्यूलो कन्स्ट्रक्टर" अनिवार्य रूप से एक रिकर्सिव कॉल की अनुमति देता है केवल कन्स्ट्रक्टर अनुप्रयोगों द्वारा फिर से लिखा जाना चाहिए कि मूल्य का निर्माण पहले "छेद" होता है और फिर रिकर्सिव कॉल सामान्य रिटर्न-वैल्यू-पासिंग सम्मेलन का उपयोग करने के बजाय सीधे "छेद" के मेमोरी पते में अपना आउटपुट देता है। मेरा मानना ​​है कि हास्केल को आलस्य के कारण आसानी से यह अनुकूलन मिल जाएगा।

इन दोनों अनुकूलन पेपर Making Mercury programs tail recursive में वर्णित हैं।