एक कार्यक्रम में अनावश्यक रिकर्सिव कॉल का पता लगाने के लिए एक उपकरण?

Question

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

int BinaryTreeMax(Tree* root) { 
    if (root == null) return INT_MIN; 

    int maxValue = root->value; 
    if (maxValue < BinaryTreeMax(root->left)) 
     maxValue = BinaryTreeMax(root->left); // (1) 
    if (maxValue < BinaryTreeMax(root->right)) 
     maxValue = BinaryTreeMax(root->right); // (2) 

    return maxValue; 
} 

सूचना है कि यह कार्यक्रम संभावित लाइनों में BinaryTreeMax करने के लिए दो पूरी तरह से बेमानी पुनरावर्ती कॉल करता है (1) और (2)। ताकि बस से पहले से मूल्य कैशिंग द्वारा इन अतिरिक्त कॉल के लिए कोई आवश्यकता नहीं है हम इस कोड को फिर से लिखने सकता है:

int BinaryTreeMax(Tree* root) { 
    if (root == null) return INT_MIN; 

    int maxValue = root->value; 
    int leftValue = BinaryTreeMax(root->left); 
    int rightValue = BinaryTreeMax(root->right); 

    if (maxValue < leftValue) 
     maxValue = leftValue; 
    if (maxValue < rightValue) 
     maxValue = rightValue; 

    return maxValue; 
} 

अब, हम हमेशा ठीक दो पुनरावर्ती कॉल करते हैं।

मेरा सवाल यह है कि क्या कोई ऐसा उपकरण है जो किसी प्रोग्राम का स्थिर या गतिशील विश्लेषण करता है (जो भी भाषा आप चाहते हैं; मैं बहुत पसंद नहीं करता!) यह पता लगा सकता है कि कोई प्रोग्राम पूरी तरह से अनावश्यक है या नहीं रिकर्सिव कॉल द्वारा "पूरी तरह से अनावश्यक" मेरा मतलब है कि

1. पुनरावर्ती कॉल, इससे पहले कि बना दिया गया है
पुनरावर्ती क्रिया का एक ही मंगलाचरण द्वारा
2. (या उसके वंश में से एक), और
3. कॉल ही नहीं है देखने योग्य साइड इफेक्ट्स।

यह कुछ ऐसा है आम तौर पर हाथ से निर्धारित किया जा सकता है, लेकिन मुझे लगता है कि यह बहुत अच्छा है, तो वहाँ कुछ उपकरण थे होगा कि स्वचालित रूप से छात्रों को कैसे सरल बनाने से बचने के बारे में प्रतिक्रिया हासिल की मदद करने का एक तरीका के रूप में इस तरह झंडा बातें कर सकते थे लेकिन उनके कार्यक्रमों में महंगे गलतियां जो बड़ी अक्षमताओं में योगदान दे सकती हैं।

क्या कोई इस तरह के उपकरण के बारे में जानता है?

Answer 1

सबसे पहले, 'पूरी तरह से अनावश्यक' की आपकी परिभाषा अपर्याप्त है। यह संभव है कि दो फ़ंक्शन कॉल के बीच कुछ कोड दूसरे फ़ंक्शन कॉल के परिणाम को प्रभावित करता है।

दूसरा, इसका पुनरावृत्ति के साथ कुछ लेना देना नहीं है, वही प्रश्न किसी भी फ़ंक्शन कॉल पर लागू हो सकता है। यदि इसे सटीक समान पैरामीटर के साथ पहले बुलाया गया है, तो इसका दुष्प्रभाव नहीं है, और दो कॉल के बीच कोई कोड फ़ंक्शन तक पहुंचने वाले किसी भी डेटा को नहीं बदला है।

अब, मुझे पूरा यकीन है कि एक आदर्श समाधान असंभव है, क्योंकि यह The Halting Problem को हल करेगा, लेकिन इसका मतलब यह नहीं है कि इन मामलों में से कुछ का पता लगाने और उनमें से कुछ को अनुकूलित करने का कोई तरीका नहीं है।

कुछ कंपाइलर्स जानते हैं कि यह कैसे करें (जीसीसी का एक विशिष्ट ध्वज है जो आपको ऐसा करने पर चेतावनी देता है)। इस मुद्दे के बारे में एक 2003 लेख यहां मिला है: http://www.cs.cmu.edu/~jsstylos/15745/final.pdf।

मुझे इसके लिए कोई उपकरण नहीं मिला, हालांकि, शायद यह कुछ है कि एरिक लिपर्ट जानता है, अगर वह आपके प्रश्न में टक्कर मारता है।

Answer 2

(जैसे जीसीसी) के रूप में कुछ compilers __attribute__((const)) (GCC function attributes देखें) इसके परिणाम केवल अपने तर्क से निर्भर बनाने के लिए और कोई depency प्राप्त करने के लिए समारोह शरीर पर कुछ प्रतिबंध लागू होता तरीके नियत कार्यों को स्पष्ट रूप से चिह्नित करने के लिए (और अधिक सटीक होना करने के लिए है कार्यक्रम की साझा स्थिति या अन्य गैर-निर्धारिती कार्यों से)। फिर वे महंगे कार्यों के लिए डुप्लिकेट कॉल को खत्म करते हैं। कुछ अन्य उच्च स्तरीय भाषा कार्यान्वयन (हास्केल हो सकता है) यह परीक्षण स्वचालित रूप से करता है।

वास्तव में, मुझे ऐसे विश्लेषण के लिए उपकरण नहीं पता (लेकिन अगर मुझे लगता है कि मैं खुश हूं)। और यदि कोई ऐसा व्यक्ति है जो अनावश्यक रिकर्सन का पता लगाता है या सामान्य रूप से, फ़ंक्शन मूल्यांकन (भाषा-अज्ञेय वातावरण में) यह एक निश्चित निर्धारक प्रदाता होगा।

BTW, यह इस तरह के प्रोग्राम लिखने के लिए इतना मुश्किल नहीं है जब आप पहले से ही कोड :)