एक स्टेटलेस दुनिया में राज्य को रखने

Question

मैं एक संदर्भ मुक्त व्याकरण को Greibach सामान्य फॉर्म (जीएनएफ) में परिवर्तित कर रहा हूं। मुख्य परिवर्तन (होपक्रॉफ्ट & उलमैन से) व्याकरण के अनुक्रमित चर पर पुनरावृत्तियों का अनुक्रम है। यह अनिवार्य रूप से "स्टेटलेस" है। मैं उचित सूचकांक से अधिक परतों के अनुक्रम के रूप में यह लागू किया है (कार्यान्वयन काफी सीधा है):

gnf :: Ord a => Set (Rule a) -> Set (Rule a) 
gnf rl = foldl step1 rl [1..maxIndex rl] 
where step1 rl' k = foldl step2 rl' [1..k - 1] 
     where step2 rl'' j = noLR k (subst rl'' k j) 

maxIndex rl नियमों का एक सेट में अधिकतम चर सूचकांक रिटर्न; subst rl k jk पर प्रतिस्थापन करता है-जिन नियमों के दाएं हाथ की ओर j -indexed चर के साथ शुरू होता है, द्वारा नियमों के अनुसार नियम। gnf करने के बाद, मुझे रिवर्स ऑर्डर में व्याकरण पर अंतिम पास करने की आवश्यकता है।

समस्या noLR, जो बाएं पुनरावर्ती कश्मीर -indexed नियमों के साथ एक व्याकरण बदल देती है। यह एक "राज्यव्यापी" फ़ंक्शन है, क्योंकि प्रत्येक नियम (या के -indexed नियम) के लिए एक अद्वितीय चर उत्पन्न किया जाना चाहिए, जिसके लिए noLR लागू किया गया है। इसलिए मैं स्टेटफुल समारोह

noLR :: Ord a => Int -> Set (Rule a) -> State [Sym a] (Set (Rule a)) 
noLR rl = do (n:ns) <- get; put ns; 
      let rl' = ... remove left recursion rl n ... 
       in return rl' 

मैं एक साथ कर सकते हैं क्रम noLR अवगत कराने के लिए लिखा था n जो noLR एक पैरामीटर के रूप लेता है। मैं नहीं उपरोक्त फ़ंक्शन में चरण 2 के अंदर noLR निष्पादित करने के लिए सुनिश्चित करें। मैं का उपयोग करने में सक्षम नहीं लगता ... स्कीमा में, क्योंकि राज्यव्यापी गणना कई पुनरावर्ती कार्यों के अंदर एम्बेडेड है।

मुझे क्या करना चाहते हैं n वैश्विक चर के कुछ प्रकार, के n एक स्पष्ट सूत्रण, जो मैं कॉल कर सकते हैं और चरण 2, जिसके कारण मैं मूल रूप से समारोह लिखा अंदर अद्यतन के समान हो है ईटा -expansion (एन के लिए) के साथ एक गुना के रूप में। क्या किसी को इस तरह के प्रभाव को प्राप्त करने के लिए राज्य मोनैड के अंदर gnf संरचना कैसे बना सकता है? गुना में आखिरी गणना के अलावा, कुछ और "राज्यपूर्ण" नहीं है, और मैं "मामूली" उदाहरणों के साथ राज्य मोनैड का उपयोग करके केवल आरामदायक हूं। मैं बल्कि खो गया हूँ।

Answer 1

आदेश प्रकार आप दे दिया है साथ noLR उपयोग करने के लिए, आप निम्न पंक्तियों के साथ अपने GNF समारोह पुनर्लेखन करना होगा:

gnf :: Ord a => Set (Rule a) -> Set (Rule a) 
gnf rl = evalState (foldM step1 rl [1..maxIndex rl]) (... generate the initial state [Sym a] here ...) 
where step1 rl' k = foldM step2 rl' [1..k - 1] 
     where step2 rl'' j = noLR k (subst rl'' k j) 

आपका राज्य चर पूरे परिकलन के दौरान मौजूद है, और है कि तथ्य कोड में स्पष्ट किया जाना है।

यदि आपको केवल इतना आवश्यक है कि नवनिर्मित चर नाम एक-दूसरे के साथ टकराव न करें, तो आप इंडेक्स के और जे से एक नया प्रतीक नाम उत्पन्न करके नोएलआर शुद्ध बना सकते हैं - कुछ के लिए "foo_42_16" == 42 और जे == 16. यदि इनपुट व्याकरण में पहले से ही उस तरह के प्रतीक नाम हैं, तो आप परेशानी में हो सकते हैं।

यदि आपको व्याकरण के भीतर अद्वितीय होने के लिए अपने प्रतीकों की आवश्यकता है, तो बस इतना क्यों न कहें?

newSymbol :: Set (Rule a) -> Sym a 
newSymbol rl = ... find a symbol name not used in rl ... 

यह निश्चित रूप से कुशल नहीं है, हालांकि, जब तक कि आप सेट की जगह (एक नियम) एक अलग प्रकार का है कि आप और अधिक कुशलता से newSymbol आपरेशन लागू करने के लिए अनुमति देता है कर रहा है।

Answer 2

मैं शुद्ध होने के लिए नोएलआर को फिर से लिखने की कोशिश करता हूं। क्या आप वाकई एक प्रतीक उत्पन्न करने के लिए इसे फिर से लिख नहीं सकते हैं जो केवल नियम के नाम पर निर्भर करता है और इसकी अनुक्रमणिका (या कुछ समान)?

noLR k j = noLR' k j $ newSymbol k j 
    where newSymbol k j = ... -- some concatenation of k and j 
      noLR' k j sym = ... -- your now pure function