पूंछ पुनरावृत्ति का उन्मूलन

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



यहाँ एक लंबा जवाब है।



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



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



तीसरा , मैं सभी प्रोग्रामिंग के आधार के रूप में पुनरावृत्ति में विश्वास नहीं करता। यह कुछ प्रोग्रामर्स की मूल धारणा है, खासकर जो स्कीम से प्यार करते हैं और प्रोग्रामिंग सीखना पसंद करते हैं, जो पुनरावृत्ति से शुरू होता है। लेकिन मेरा मानना ​​है कि पुनरावर्तन केवल मौलिक गणित के लिए एक अच्छा सैद्धांतिक दृष्टिकोण है, लेकिन कार्यों को हल करने के लिए एक दैनिक उपकरण नहीं है।



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



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

def f(x): if x > 0: return f(x-1) return 0
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

आप शरीर को इस तरह से बदल सकते हैं:

 if x > 0: x = x-1 <jump to top> return 0
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

यह काफी सरल लगता है, लेकिन अब इसे जोड़ें:

 g = f def f(x): return x g(5)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

जी (5) के लिए कॉल पहले से परिभाषित फ़ंक्शन च को कॉल करता है, लेकिन "पुनरावर्ती" कॉल अब ऐसा नहीं है! रन समय में, 'f' नाम को गैर-पुनरावर्ती फ़ंक्शन में पुनर्परिभाषित किया जाता है, इसलिए लौटाया गया मान 4 है, 0. नहीं। एक ही समय में, मैं मानता हूं कि यह खराब शैली है, लेकिन यह पायथन लैंटिक्स का एक अच्छी तरह से परिभाषित हिस्सा है जिसमें तार्किक बनाने के कई तरीके हैं उपयोग, और संकलक ने इस प्रतिस्थापन को इस उम्मीद में बनाया कि एफ की परिभाषा अपरिवर्तित रहेगी, वास्तविक कोड में काफी त्रुटियों का परिचय देगा।



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

 def fact(n): if n > 1: return n * fact(n-1) return 1
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ऐसे कई कार्य भी हैं जिनमें एक नियमित पुनरावर्ती कॉल के साथ पूंछ पुनरावृत्ति शामिल है; सज्जाकार ऐसे मामलों का समर्थन नहीं करते हैं। एक और सूक्ष्मता है कि ऐसे सज्जाकार संभाल नहीं करते हैं, कोशिश ब्लॉकों में पूंछ पुनरावर्ती कॉल है: ऐसा लग सकता है कि उन्हें समाप्त किया जा सकता है, लेकिन ऐसा इसलिए नहीं किया जा सकता क्योंकि टीआरई अपवाद हैंडलिंग को हटा सकता है। इन सभी कारणों से, मुझे लगता है कि इस तरह के दृष्टिकोण को कम से कम व्यापक दर्शकों के लिए बर्बाद किया जाता है।



हालांकि, अगर किसी को TRE को Cpython (उदाहरण के लिए) में जोड़ने के लिए कॉन्फ़िगर किया गया है, तो आप कंपाइलर को इस तरह बदल सकते हैं। सबसे पहले, "सुरक्षित" पूंछ पुनरावृत्ति बिंदुओं को परिभाषित करें। उदाहरण के लिए, कॉल ऑपरेशन कोड, तुरंत RETURN ऑपरेशन कोड के बाद, जबकि पूरी तरह से कोशिश ब्लॉकों के बाहर। (नोट: मैं विभिन्न CALL_ * कार्यों का उल्लेख नहीं करता हूं जो समान दृष्टिकोण का उपयोग करने के लिए पर्याप्त आसान हैं।) अगला, प्रत्येक ऐसे CALL-RETURN जोड़ी को एक एकल CALL_RETURN ऑपरेशन के साथ बदलें। संकलक को यह जांचने की कोई आवश्यकता नहीं है कि क्या कहा जाता है कि फ़ंक्शन का नाम वर्तमान फ़ंक्शन के समान है: यदि रन टाइम में एक ओवरराइड होता है, तो यह कॉल TRE के लिए लागू नहीं होता है और आपको RETURN कोड के बाद CALL के लिए सामान्य क्रियाएं करने की आवश्यकता होती है। (मुझे लगता है कि आप पुनर्वितरण को गति देने के लिए डायल पीयर द्वारा अनुक्रमित कुछ कैशिंग तंत्र जोड़ सकते हैं)।



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



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



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



एक नरम संस्करण को पहले की तरह ही पायथन स्तर पर स्टैक फ्रेम ऑब्जेक्ट्स बनाने होंगे, लेकिन फिर से स्टैक फ्रेम का उपयोग करना होगा। इसने स्टैकलेस पायथन की तरह कुछ बनाया, हालांकि यह अंतर्निहित सी कॉल को साझा करते हुए सी स्टैक को समाप्त करना अभी भी काफी आसान है। कार्य या विधि।



बेशक, कोई भी दृष्टिकोण मेरे तीन दावों को संतुष्ट नहीं करता है। क्या वास्तव में लूप का उपयोग करने के लिए अपने फ़ंक्शन को फिर से लिखना मुश्किल है?