क्या फ्रीज पूंछ कॉल अनुकूलन करता है?

Question

फ्रेज में अनुकूलित पूंछ कॉल हैं। मुझे पता है कि जावा में न तो टीसीओ है और न ही उन भाषाओं में जो क्लोजर और स्कैला जैसे जेवीएम बाइटकोड को संकलित करते हैं। फ्रीज के बारे में क्या?

Answer 1

फ्रीज बस लूप के दौरान उत्पन्न करके टेल रिकर्सन ऑप्टिमाइज़ेशन करता है।

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

कहा जा रहा है कि, पहले से ही स्थिर स्टैक गहराई जावा की तुलना में एक कार्यात्मक भाषा में प्रकृति से गहरा है। इसलिए, कुछ कार्यक्रमों को एक बड़ा ढेर दिया जाना चाहिए (यानी -Xss1m के साथ)।

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

निम्नलिखित कार्यक्रम होना चाहिए नहीं ढेर अतिप्रवाह लेकिन 2 या 3s के बाद प्रिंट "गलत":

module Test 
    -- inline (odd) 
    where 

even 0 = true 
even 1 = false 
even n = odd (pred n) 

odd n = even (pred n) 

main args = println (even 123_456_789) 

इस रूप में काम करता है: println, मुद्रित करने के लिए एक मान होना चाहिए ताकि मूल्यांकन करने के लिए कोशिश करता है (यहां तक ​​कि n)। लेकिन यह सब एक थंक है (विषम (पूर्व एन))। इसलिए यह इस थंक का मूल्यांकन करने की कोशिश करता है, जो एक और थंक हो जाता है (यहां तक ​​कि (pred (pred n)))। यहां तक ​​कि मूल्यांकन करना चाहिए (pred (pred n)) यह देखने के लिए कि क्या तर्क 0 या 1 था, एक और थंक (odd (pred (n-2)) लौटने से पहले जहां n-2 का मूल्यांकन पहले से किया गया है। इस तरह, सभी कॉलिंग (JVM स्तर पर) println के भीतर से किया जाता है। किसी भी समय वास्तव में अजीब, या इसके विपरीत भी नहीं आते हैं।

यदि कोई इनलाइन निर्देश को अस्वीकार करता है, तो किसी को भी पूंछ रिकर्सिव संस्करण मिलता है, और परिणाम दस बार प्राप्त होता है । तेजी से

कहने के लिए, इस अनाड़ी एल्गोरिथ्म केवल प्रदर्शन के लिए है जरूरत नहीं -। सामान्य रूप से एक एक सा ऑपरेशन के साथ भी सत्ता के लिए जाँच करेगा

यहाँ एक और संस्करण है, कि रोग है और overflo ढेर होगा w:

even 0 = true 
even 1 = false 
even n = not . odd $ n 
odd = even . pred 

समस्या यहाँ है कि not पूंछ कॉल है और वह अपने तर्क में सख्त है (अर्थात, कुछ नकारना करने के लिए, आप पहली बार है कि कुछ है चाहिए)। इसलिए, जब even n गणना की जाती है, तो not को पूरी तरह से odd n का मूल्यांकन करना चाहिए, जो बदले में, even (pred n) का पूरी तरह से मूल्यांकन करना चाहिए और इस प्रकार यह 2 * एन स्टैक फ्रेम लेगा।

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

Answer 2

@ लांदेई टीसीओ पूरी तरह से स्कैला में समर्थित नहीं है ... इसे आजमाएं।

def foo() { def bar() { println("bar"); foo() }; println("foo"); bar() } 

नोट, मेरे पास सीधे टिप्पणी करने के लिए पर्याप्त प्रतिष्ठा नहीं है। टिप्पणी प्राप्त करें मैं मूल प्रश्न की टिप्पणियों में जवाब दे रहा हूं।