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

This article is about कंप्यूटर विज्ञान शब्द. For ग्राफ़ सिद्धांत का उपयोग, see ट्रांसिटिव रिडक्सन.

कंप्यूटर विज्ञान में, ग्राफ रिडक्सन गैर-सख्त मूल्यांकन का कुशल वर्जन प्रयुक्त करती है, तथा मूल्यांकन रणनीति जहां किसी फ़ंक्शन के तर्कों का तुरंत मूल्यांकन नहीं किया जाता है। गैर-सख्त मूल्यांकन के इस रूप को लेजी मूल्यांकन के रूप में भी जाना जाता है और इस प्रकार इसका उपयोग फंक्शनल प्रोग्रामिंग में किया जाता है। इस तकनीक को पहली बार 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 में टर्नर द्वारा विकसित किया गया था।

यह भी देखें

• ग्राफ रिडक्सन मशीन
• एसईसीडी मशीन

संदर्भ

• 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.