डायरेक्टर स्ट्रिंग: Difference between revisions

From Vigyanwiki
No edit summary
Line 1: Line 1:
गणित में, [[लैम्ब्डा कैलकुलस]] और सं[[गणना]] के क्षेत्र में, डायरेक्टर्स या डायरेक्टर स्ट्रिंग्स एक [[अभिव्यक्ति (गणित)]] में [[मुक्त चर]] का ट्रैक रखने के लिए एक तंत्र हैं। शिथिल रूप से कहें तो, उन्हें मुक्त चरों के लिए एक प्रकार के [[संस्मरण]] के रूप में समझा जा सकता है; अर्थात्, किसी [[शब्द बीजगणित]] या लैम्ब्डा अभिव्यक्ति में मुक्त चर का तेजी से पता लगाने के लिए एक प्रोग्राम अनुकूलन तकनीक के रूप में। निर्देशक स्ट्रिंग्स को 1982 में केनावे और स्लीप द्वारा पेश किया गया था और इसे सिनोट, फर्नांडीज और मैकी द्वारा विकसित किया गया था।<ref>F.-R. Sinot, M. Fernández and I. Mackie. [ftp://nozdr.ru/biblio/kolxoz/Cs/CsLn/R/Rewriting%20Techniques%20and%20Applications,%2014%20conf.,%20RTA%202003(LNCS2706,%20Springer,%202003)(ISBN%203540402543)(526s)_CsLn_.pdf#page=57 Efficient Reductions with Director Strings]. In ''Proc. Rewriting Techniques and Applications''. Springer LNCS vol 2706, 2003</ref> [[बीटा कमी]] की एल्गोरिदम लागत के विश्लेषण को समझने और नियंत्रित करने के लिए एक तंत्र के रूप में।
 
 
गणित में, लैम्ब्डा कैलकुलस और संगणना के क्षेत्र में, डायरेक्टर्स या डायरेक्टर स्ट्रिंग्स एक शब्द में मुक्त चर का ट्रैक रखने के लिए एक तंत्र हैं। शिथिल रूप से कहें तो, उन्हें मुक्त चरों के लिए एक प्रकार के संस्मरण के रूप में समझा जा सकता है; अर्थात्, किसी शब्द बीजगणित या लैम्ब्डा अभिव्यक्ति में मुक्त चरों को तेजी से खोजने के लिए एक अनुकूलन तकनीक के रूप में डायरेक्टर स्ट्रिंग्स को 1982 में केनावे और स्लीप द्वारा प्रस्तुत किया गया था और बीटा कमी की कम्प्यूटेशनल जटिलता निवेश को समझने और नियंत्रित करने के लिए एक तंत्र के रूप में सिनोट, फर्नांडीज और मैकी<ref>F.-R. Sinot, M. Fernández and I. Mackie. [ftp://nozdr.ru/biblio/kolxoz/Cs/CsLn/R/Rewriting%20Techniques%20and%20Applications,%2014%20conf.,%20RTA%202003(LNCS2706,%20Springer,%202003)(ISBN%203540402543)(526s)_CsLn_.pdf#page=57 Efficient Reductions with Director Strings]. In ''Proc. Rewriting Techniques and Applications''. Springer LNCS vol 2706, 2003</ref> द्वारा आगे विकसित किया गया था।


==प्रेरणा==
==प्रेरणा==
बीटा कमी में, बाईं ओर की अभिव्यक्ति का मान दाईं ओर के मान को परिभाषित करता है:
बीटा कमी में, बाईं ओर की अभिव्यक्ति का मान दाईं ओर के मान को परिभाषित करता है:
:<math>(\lambda x.E)y \equiv E[x:= y]\,</math> या <math>(\lambda x.E)y \equiv E[y/x]</math> ((बॉडी) में सभी एक्स को वाई से बदलें)
:<math>(\lambda x.E)y \equiv E[x:= y]\,</math> या <math>(\lambda x.E)y \equiv E[y/x]</math> (''E''(बॉडी) में सभी ''x''  को ''y'' से बदलें)  


हालांकि यह एक वैचारिक रूप से सरल ऑपरेशन है, चरण के एल्गोरिदम का विश्लेषण गैर-तुच्छ हो सकता है: एक अनुभवहीन एल्गोरिदम मुक्त चर x की सभी घटनाओं के लिए अभिव्यक्ति को स्कैन करेगा। ऐसा एल्गोरिदम स्पष्ट रूप से अभिव्यक्ति की लंबाई में (एन) है। इस प्रकार, किसी को अभिव्यक्ति में मुक्त चर की घटनाओं को किसी तरह ट्रैक करने के लिए प्रेरित किया जाता है। कोई भी प्रत्येक मुक्त चर की स्थिति को ट्रैक करने का प्रयास कर सकता है, चाहे वह अभिव्यक्ति में कहीं भी हो, लेकिन भंडारण के मामले में यह स्पष्ट रूप से बहुत महंगा हो सकता है; इसके अलावा, यह विवरण का एक स्तर प्रदान करता है जिसकी वास्तव में आवश्यकता नहीं है। निदेशक स्ट्रिंग्स सुझाव देते हैं कि सही मॉडल घटक शब्दों में उनके उपयोग को ट्रैक करके, पदानुक्रमित फैशन में मुक्त चर को ट्रैक करना है।
चूँकि यह एक वैचारिक रूप से सरल ऑपरेशन है, चरण के एल्गोरिदम का विश्लेषण गैर-तुच्छ हो सकता है: एक अनुभवहीन एल्गोरिदम मुक्त चर x की सभी घटनाओं के लिए अभिव्यक्ति ''E'' को स्कैन करेगा। ऐसा एल्गोरिदम स्पष्ट रूप से अभिव्यक्ति ''E'' की लंबाई में ''O''(''n'') है। इस प्रकार, किसी को अभिव्यक्ति में मुक्त चर की घटनाओं को किसी तरह ट्रैक करने के लिए प्रेरित किया जाता है। कोई भी प्रत्येक मुक्त चर की स्थिति को ट्रैक करने का प्रयास कर सकता है, चाहे वह अभिव्यक्ति में कहीं भी हो, किंतु संचयन के स्थिति में यह स्पष्ट रूप से बहुत मूल्यवान हो सकता है; इसके अतिरिक्त यह विवरण का एक स्तर प्रदान करता है जिसकी वास्तव में आवश्यकता नहीं है। निदेशक स्ट्रिंग्स सुझाव देते हैं कि सही मॉडल घटक शब्दों में उनके उपयोग को ट्रैक करके, पदानुक्रमित फैशन में मुक्त चर को ट्रैक करना है।


==परिभाषा==
==परिभाषा==
सरलता के लिए, एक शब्द बीजगणित पर विचार करें, अर्थात, मुक्त चर, स्थिरांक और ऑपरेटरों का एक संग्रह जिसे स्वतंत्र रूप से संयोजित किया जा सकता है। मान लीजिए कि एक पद t का रूप लेता है
सरलता के लिए एक शब्द बीजगणित पर विचार करें अर्थात मुक्त चर स्थिरांक और ऑपरेटरों का एक संग्रह जिसे स्वतंत्र रूप से संयोजित किया जा सकता है। मान लीजिए कि एक पद t का रूप लेता है
:<math>t ::= f(t_1,t_2,\dots,t_n)</math>
:<math>t ::= f(t_1,t_2,\dots,t_n)</math>
जहाँ f, [[arity]] n का एक फलन (गणित) है, जिसमें कोई मुक्त चर नहीं है, और <math>t_i</math> ऐसे शब्द हैं जिनमें मुक्त चर हो भी सकते हैं और नहीं भी। मान लीजिए V सभी मुक्त चरों के समुच्चय को दर्शाता है जो सभी पदों के समुच्चय में हो सकते हैं। निर्देशक तो नक्शा है
जहाँ f, एरीटी n का एक फलन है, जिसमें कोई मुक्त चर नहीं है, और <math>t_i</math> ऐसे पद हैं जिनमें मुक्त चर हो भी सकते हैं और नहीं भी तो यह मान लीजिए V सभी मुक्त चरों के समुच्चय को दर्शाता है जो सभी पदों के समुच्चय में हो सकते हैं। निर्देशक तो नक्शा है


:<math>\sigma_t: V\to P(\lbrace 1,2,\dots,n\rbrace)</math>
:<math>\sigma_t: V\to P(\lbrace 1,2,\dots,n\rbrace)</math>
मुक्त चर से लेकर [[ सत्ता स्थापित ]] तक <math>P(X)</math> सेट का <math>X=\lbrace 1,2,\dots,n\rbrace</math>. द्वारा लिए गए मान <math>\sigma_t</math> के सूचकांकों की एक सूची मात्र है <math>t_i</math> जिसमें एक दिया गया मुक्त चर होता है। इस प्रकार, उदाहरण के लिए, यदि एक मुक्त चर <math>x\in V</math> में होता है <math>t_3</math> और <math>t_5</math> लेकिन किसी अन्य संदर्भ में, तो किसी के पास नहीं है <math>\sigma_t(x) = \lbrace 3,5\rbrace</math>.
मुक्त चर से लेकर सेट <math>X=\lbrace 1,2,\dots,n\rbrace</math> के पावर सेट <math>P(X)</math> तक <math>\sigma_t</math> द्वारा लिए गए मान केवल <math>t_i</math> के सूचकांकों की एक सूची है जिसमें एक दिया गया मुक्त चर होता है। इस प्रकार, उदाहरण के लिए, यदि एक मुक्त चर <math>x\in V</math><math>t_3</math> और <math>t_5</math> में होता है किंतु किसी अन्य पद में नहीं होता है, तो किसी के पास <math>\sigma_t(x) = \lbrace 3,5\rbrace</math> होता है।


इस प्रकार, प्रत्येक पद के लिए <math>t\in T</math> सभी पदों T के समुच्चय में, कोई एक फलन बनाए रखता है <math>\sigma_t</math>, और केवल पदों t के साथ काम करने के बजाय, कोई जोड़े के साथ काम करता है <math>(t,\sigma_t)</math>. इस प्रकार, टी में मुक्त चर खोजने की समय जटिलता को उन शब्दों की सूची बनाए रखने की स्थान जटिलता के लिए व्यापार किया जाता है जिनमें एक चर होता है।
इस प्रकार, सभी पदों T के समुच्चय में T के प्रत्येक पद के लिए व्यक्ति एक फलन `<math>t\in T</math> बनाए रखता है, और केवल पदों t के साथ काम करने के अतिरिक्त, जोड़े (<math>(t,\sigma_t)</math>) के साथ काम करता है। इस प्रकार, t में मुक्त चर खोजने की समय जटिलता को उन शब्दों की सूची बनाए रखने की स्थान जटिलता के लिए व्यापार किया जाता है जिनमें एक चर होता है।


== सामान्य मामला ==
== सामान्य स्थिति ==
यद्यपि उपरोक्त परिभाषा एक शब्द बीजगणित के संदर्भ में तैयार की गई है, सामान्य अवधारणा अधिक सामान्यतः लागू होती है, और इसे संयुक्त बीजगणित और लैम्ब्डा कैलकुलस दोनों के लिए परिभाषित किया जा सकता है, विशेष रूप से, [[स्पष्ट प्रतिस्थापन]] के ढांचे के भीतर।
यद्यपि उपरोक्त परिभाषा बीजगणित शब्द के संदर्भ में तैयार की गई है, सामान्य अवधारणा अधिक सामान्यतः प्रयुक्त होती है, और इसे विशेष रूप से स्पष्ट प्रतिस्थापन के रूपरेखा  के अंदर संयोजन बीजगणित और लैम्ब्डा कैलकुलस दोनों के लिए परिभाषित किया जा सकता है।


==यह भी देखें==
==यह भी देखें==

Revision as of 08:22, 15 July 2023


गणित में, लैम्ब्डा कैलकुलस और संगणना के क्षेत्र में, डायरेक्टर्स या डायरेक्टर स्ट्रिंग्स एक शब्द में मुक्त चर का ट्रैक रखने के लिए एक तंत्र हैं। शिथिल रूप से कहें तो, उन्हें मुक्त चरों के लिए एक प्रकार के संस्मरण के रूप में समझा जा सकता है; अर्थात्, किसी शब्द बीजगणित या लैम्ब्डा अभिव्यक्ति में मुक्त चरों को तेजी से खोजने के लिए एक अनुकूलन तकनीक के रूप में डायरेक्टर स्ट्रिंग्स को 1982 में केनावे और स्लीप द्वारा प्रस्तुत किया गया था और बीटा कमी की कम्प्यूटेशनल जटिलता निवेश को समझने और नियंत्रित करने के लिए एक तंत्र के रूप में सिनोट, फर्नांडीज और मैकी[1] द्वारा आगे विकसित किया गया था।

प्रेरणा

बीटा कमी में, बाईं ओर की अभिव्यक्ति का मान दाईं ओर के मान को परिभाषित करता है:

या (E(बॉडी) में सभी x को y से बदलें)

चूँकि यह एक वैचारिक रूप से सरल ऑपरेशन है, चरण के एल्गोरिदम का विश्लेषण गैर-तुच्छ हो सकता है: एक अनुभवहीन एल्गोरिदम मुक्त चर x की सभी घटनाओं के लिए अभिव्यक्ति E को स्कैन करेगा। ऐसा एल्गोरिदम स्पष्ट रूप से अभिव्यक्ति E की लंबाई में O(n) है। इस प्रकार, किसी को अभिव्यक्ति में मुक्त चर की घटनाओं को किसी तरह ट्रैक करने के लिए प्रेरित किया जाता है। कोई भी प्रत्येक मुक्त चर की स्थिति को ट्रैक करने का प्रयास कर सकता है, चाहे वह अभिव्यक्ति में कहीं भी हो, किंतु संचयन के स्थिति में यह स्पष्ट रूप से बहुत मूल्यवान हो सकता है; इसके अतिरिक्त यह विवरण का एक स्तर प्रदान करता है जिसकी वास्तव में आवश्यकता नहीं है। निदेशक स्ट्रिंग्स सुझाव देते हैं कि सही मॉडल घटक शब्दों में उनके उपयोग को ट्रैक करके, पदानुक्रमित फैशन में मुक्त चर को ट्रैक करना है।

परिभाषा

सरलता के लिए एक शब्द बीजगणित पर विचार करें अर्थात मुक्त चर स्थिरांक और ऑपरेटरों का एक संग्रह जिसे स्वतंत्र रूप से संयोजित किया जा सकता है। मान लीजिए कि एक पद t का रूप लेता है

जहाँ f, एरीटी n का एक फलन है, जिसमें कोई मुक्त चर नहीं है, और ऐसे पद हैं जिनमें मुक्त चर हो भी सकते हैं और नहीं भी तो यह मान लीजिए V सभी मुक्त चरों के समुच्चय को दर्शाता है जो सभी पदों के समुच्चय में हो सकते हैं। निर्देशक तो नक्शा है

मुक्त चर से लेकर सेट के पावर सेट तक द्वारा लिए गए मान केवल के सूचकांकों की एक सूची है जिसमें एक दिया गया मुक्त चर होता है। इस प्रकार, उदाहरण के लिए, यदि एक मुक्त चर , और में होता है किंतु किसी अन्य पद में नहीं होता है, तो किसी के पास होता है।

इस प्रकार, सभी पदों T के समुच्चय में T के प्रत्येक पद के लिए व्यक्ति एक फलन ` बनाए रखता है, और केवल पदों t के साथ काम करने के अतिरिक्त, जोड़े () के साथ काम करता है। इस प्रकार, t में मुक्त चर खोजने की समय जटिलता को उन शब्दों की सूची बनाए रखने की स्थान जटिलता के लिए व्यापार किया जाता है जिनमें एक चर होता है।

सामान्य स्थिति

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

यह भी देखें

  • टर्म पुनर्लेखन प्रणाली
  • स्पष्ट प्रतिस्थापन
  • संस्मरण

संदर्भ

  1. F.-R. Sinot, M. Fernández and I. Mackie. Efficient Reductions with Director Strings. In Proc. Rewriting Techniques and Applications. Springer LNCS vol 2706, 2003