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

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

प्रेरणा

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

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

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

परिभाषा

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

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

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

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

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

इस प्रकार, प्रत्येक पद के लिए $t\in T$ सभी पदों T के समुच्चय में, कोई एक फलन बनाए रखता है $\sigma _{t}$, और केवल पदों t के साथ काम करने के बजाय, कोई जोड़े के साथ काम करता है $(t,\sigma _{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.