ग्राफ रिडक्सन

This article is about the computer science term. For the graph theory use, see transitive reduction.

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

प्रेरणा

अंकगणितीय अभिव्यक्ति के मूल्यांकन का एक सरल उदाहरण इस प्रकार है:

${\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+(2+2))+6\\&{}&=&((2+2)+4)+6\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}$

उपरोक्त कटौती अनुक्रम एक रणनीति को नियोजित करता है जिसे बाहरीतम वृक्ष कटौती के रूप में जाना जाता है। उसी अभिव्यक्ति का मूल्यांकन अंतरतम वृक्ष कटौती का उपयोग करके किया जा सकता है, जिससे कमी अनुक्रम प्राप्त होता है:

${\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+4)+(3+3)\\&{}&=&(4+4)+(3+3)\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}$

ध्यान दें कि कमी का क्रम कोष्ठक जोड़ने से स्पष्ट हो जाता है। इस अभिव्यक्ति का मूल्यांकन केवल दाएँ से बाएँ भी किया जा सकता था, क्योंकि जोड़ एक साहचर्य संक्रिया है।

ट्री डेटा संरचना के रूप में प्रस्तुत, उपरोक्त अभिव्यक्ति इस तरह दिखती है:

यहीं से वृक्ष न्यूनीकरण शब्द आया है। जब इसे एक पेड़ के रूप में दर्शाया जाता है, तो हम आंतरिक कमी को नीचे से ऊपर की ओर काम करने के रूप में सोच सकते हैं, जबकि बाहरी कमी ऊपर से नीचे की ओर काम करती है।

अभिव्यक्ति को एक निर्देशित चक्रीय ग्राफ के रूप में भी दर्शाया जा सकता है, जिससे उप-अभिव्यक्तियों को साझा किया जा सकता है:

जहाँ तक पेड़ों की बात है, सबसे बाहरी और सबसे भीतरी कमी ग्राफ़ पर भी लागू होती है। इसलिए हमारे पास ग्राफ़ में कमी है।

अब सबसे बाहरी ग्राफ़ कटौती के साथ मूल्यांकन निम्नानुसार आगे बढ़ सकता है:

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

संयोजक ग्राफ़ कमी

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

इतिहास

ग्राफ कटौती की अवधारणा जो मूल्यांकन किए गए मूल्यों को साझा करने की अनुमति देती है, सबसे पहले क्रिस वड्सवर्थ ने अपने 1971 पीएच.डी. में विकसित की थी। निबंध। इस शोध प्रबंध को पीटर हेंडरसन और जेम्स एच. मॉरिस जूनियर ने 1976 के पेपर, "एक आलसी मूल्यांकनकर्ता" में उद्धृत किया था। जिसने आलसी मूल्यांकन की धारणा प्रस्तुत की। 1976 में डेविड टर्नर (कंप्यूटर वैज्ञानिक) ने कॉम्बिनेटर का उपयोग करके एसएएसएल प्रोग्रामिंग भाषा में आलसी मूल्यांकन को शामिल किया। एसएएसएल एक प्रारंभिक कार्यात्मक प्रोग्रामिंग भाषा थी जिसे पहली बार 1972 में टर्नर द्वारा विकसित किया गया था।

यह भी देखें

• ग्राफ कम करने वाली मशीन
• SECD मशीन

संदर्भ

• Bird, Richard (1998). Introduction to Functional Programming using Haskell. Prentice Hall. ISBN 0-13-484346-0.

अग्रिम पठन

• Peyton Jones, Simon L. (1987). The Implementation of Functional Programming Languages. Prentice Hall. ISBN 013453333X. LCCN 86020535. Retrieved 2022-04-15.