डायरेक्टर स्ट्रिंग

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

प्रेरणा

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

$(\lambda x.E)y\equiv E[x:=y]\,$ या $(\lambda x.E)y\equiv E[y/x]$ (E(बॉडी) में सभी x को y से बदलें)

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

परिभाषा

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

$t::=f(t_{1},t_{2},\dots ,t_{n})$

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

$\sigma _{t}:V\to P(\lbrace 1,2,\dots ,n\rbrace )$

मुक्त चर से लेकर सेट $X=\lbrace 1,2,\dots ,n\rbrace$ के पावर सेट $P(X)$ तक $\sigma _{t}$ द्वारा लिए गए मान केवल $t_{i}$ के सूचकांकों की एक सूची है जिसमें एक दिया गया मुक्त चर होता है। इस प्रकार, उदाहरण के लिए, यदि एक मुक्त चर $x\in V$, $t_{3}$ और $t_{5}$ में होता है किंतु किसी अन्य पद में नहीं होता है, तो किसी के पास $\sigma _{t}(x)=\lbrace 3,5\rbrace$ होता है।

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

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

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

यह भी देखें

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

संदर्भ

• F.-R. Sinot. "Director Strings Revisited: A Generic Approach to the Efficient Representation of Free Variables in Higher-order Rewriting." Journal of Logic and Computation 15(2), pages 201-218, 2005.