स्टैक कार्यान्वयन के कारण ... कॉल स्टैक

एक बार मेरे पास एक विचार आया: डेटा संरचना के रूप में कॉल स्टैक और स्टैक है। क्या डेटा स्टोर करने के लिए कॉल स्टैक का उपयोग करना संभव है?
थोड़ा विचार के साथ, मुझे एहसास हुआ कि यह संभव है, लेकिन सीमाओं के साथ: सबसे पहले, आपको मूल्यों को संसाधित करने के लिए कॉलबैक का उपयोग करने की आवश्यकता है (आखिरकार, जब तक कि मूल्य स्टैक पर है, आप उस कॉल को नहीं छोड़ सकते हैं जिसमें हमने इसे बचाया है)। दूसरे, एक्सेस का सख्ती से लिफो है।
कार्यान्वयन - कटौती के तहत।

एक भाषा के रूप में, मैंने निमर्ल का उपयोग करने का फैसला किया - एक कार्यात्मक शैली के परिचित .NET + सुविधा।

कार्यान्वयन स्वयं बाह्य रूप से सरल है:

variant StackAction[T]{ | Push{ value : T; next : void -> StackAction[T]; } | Pop { next : T -> StackAction[T]; } } module StackStack{ public Enter[T](current : StackAction[T].Push) : StackAction[T]{ def processNext(next : StackAction[T]): StackAction[T]{ match(next){ | push is StackAction[T].Push => processNext(Enter(push)); | pop is StackAction[T].Pop => pop.next(current.value); } } processNext(current.next()); } } 

निमर्ल सिंटैक्स से अपरिचित लोगों के लिए:
वैरिएंट StackAction [T] एक वैरिएंट जेनेरिक प्रकार का वर्णन करता है, जिनमें से वैरिएबल पुश या पॉप ले सकते हैं। इसके अलावा, यदि मूल्य पुश है, तो वैल्यू फ़ील्ड्स होना चाहिए (वास्तविक मान जिसे हम स्टैक पर रखते हैं), और अगला एक कॉलबैक है जिसमें मापदंडों की एक खाली सूची होती है जो अगला स्टैकएक्शन लौटाती है। और अगर पॉप, तो इसे कॉलबैक होना चाहिए एक तर्क के रूप में स्टैक के शीर्ष से मान, और अगले स्टैकेशन को भी वापस करना चाहिए।

फ़ंक्शन फ़ंक्शन स्टैक के साथ काम करने के बहुत तर्क को लागू करता है। इसके अंदर, एक स्थानीय प्रक्रियाअनुप्रयोग फ़ंक्शन घोषित किया जाता है, जो एक बंद के रूप में वर्तमान प्राप्त करता है। प्रोसेसनेक्स्ट की बॉडी में एक मैच ब्लॉक (पैटर्न मैचिंग) होता है। पुश और पॉप अगले का पर्यायवाची शब्द है, जिसके आधार पर वास्तविक प्रकार मूल्य लेता है।

नतीजतन, एंटर: लॉजिक का तर्क current.next को कॉल करना है और रिटर्न वैल्यू को प्रोसेसनक् पास में भेजना है, प्रोसेक्ट से रिटर्न मान को वापस करने के लिए। (निमरल में कोई रिटर्न स्टेटमेंट नहीं है , और फ़ंक्शन अंतिम अभिव्यक्ति से मान लौटाता है, और निष्पादित शाखा से मेल खाता है)
processNext इसके पास दिए गए मान की जाँच करता है। यदि पुश किया जाता है, तो वह इस मूल्य के साथ Enter दर्ज करता है, और खुद Enter के परिणाम के साथ। यह एक लूप में परिणाम करता है - जब तक कॉलबैक पॉप वापस नहीं आता है, तब तक मौजूदा कॉल से एंटर में कोई निकास नहीं होगा। यदि अगला का मूल्य पॉप है, तो current.value का वर्तमान मूल्य कॉलबैक से बंद करने के लिए पारित किया जाता है (जबकि प्रक्रियाअनुकूल ही पहले से ही कई बार पुनरावृत्ति हो सकती है)।

नतीजतन, हमें एक और कमी मिलती है: यदि पॉप स्टैक से अंतिम मान लेता है और स्टैक खाली है, तो दर्ज करें क्लाइंट कोड में वह वापस आ जाएगा जो अंतिम पॉप वापस आ गया। इस प्रकार, स्टैक के निचले मूल्य के साथ काम करने के लिए, आपको एक अलग चक्र करने की आवश्यकता है।

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

 def items = "7 2 3 * -".Split(array[' ']); mutable currentPosition = 0; def processNextToken(){ def action(operation : double * double -> double){ StackAction.Pop(fun(y){ StackAction.Pop(fun(x){ StackAction.Push(operation(x, y), processNextToken); }); }); } if(currentPosition >= items.Length){ StackAction.Pop(fun(x){ StackAction.Push(x, fun(){throw Exception("Bad input, not enough operations.")}); }); }else{ currentPosition++; mutable value : double; match(items[currentPosition-1]){ | strVal when (Double.TryParse(strVal, out value)) => StackAction.Push(value, processNextToken); | "+" => action(_ + _); | "-" => action(_ - _); | "/" => action(_ / _); | "*" => action(_ * _); | token => throw Exception($"bad token $token"); } } } def calc(current : StackAction[double]){ match(current){ | StackAction.Push (_, next) when (next == processNextToken) => calc(StackStack.Enter(current :> StackAction[double].Push)); | StackAction.Push (res, _) => WriteLine($"Result = $res"); | StackAction.Pop => throw Exception("Bad input, not enough arguments."); } } calc(processNextToken()); 

अंत से संक्षिप्त विवरण:
कैल्क स्टैक के नीचे के तत्व के साथ काम करने के तर्क को लागू करता है: यदि पुश प्रक्रिया-प्रक्रिया के साथ बाहर गिर गया तोकॉटेन कॉलबैक करता है, हम फिर से कैल्क कहते हैं, यदि पुश एक और कॉलबैक (मजेदार) (अपवाद फेंक ("बुरा इनपुट, पर्याप्त संचालन नहीं") के साथ गिर गया, तो पूरा रिकॉर्ड संसाधित है। और फ़ंक्शन ने अंतिम परिणाम लौटा दिया। यदि पॉप बाहर गिर गया, तो अंतिम कार्रवाई में पर्याप्त तर्क नहीं थे।

processNextToken क्रम में टोकन को संसाधित करता है। यदि रिकॉर्ड का अंत पहुँच गया है, तो स्टैक से अंतिम मान लें और इसे कैल्क पर लौटा दें। यदि स्टैक पर 1 से अधिक मान है, तो अनाम फ़ंक्शन मज़ा () {थ्रो एक्ससेप्शन ("खराब इनपुट, पर्याप्त संचालन नहीं।")} कहा जाएगा। यदि अधिक टोकन हैं, तो वर्तमान को लें। हम स्टैक पर एक संख्यात्मक शाब्दिक डालते हैं, कार्रवाई के लिए जिसे हम कार्रवाई कहते हैं। रिकॉर्ड्स _ + _ - विशेष मैजिक नेमारल - आंशिक निष्पादन। इस मामले में, यह अंकगणितीय ऑपरेटरों को दो तर्कों के साथ कार्यों में बदल देता है।

स्टैक से कार्रवाई 2 मान लेती है, इसके पास दिए गए फ़ंक्शन को निष्पादित करता है, और स्टैक पर परिणाम डालता है।

बहुत उलझन सही है? आप सामान्य स्टैक इंटरफ़ेस के साथ एक वर्ग बना सकते हैं यदि आप एक स्टैक को स्थानांतरित करते हैं जो मूल्यों को दूसरे धागे में संग्रहीत करता है।

 enum Action{ | Push | Pop } public class StackEmptyException : Exception{ public this(message : string){ base(message); } } public class ThreadStack[T] : IDisposable{ class Resident{ public mutable volatile action : Action; public mutable volatile value : T; public mutable volatile exception : Exception; public syncIn = AutoResetEvent(false); public syncOut = AutoResetEvent(false); public start() : void{ exception = null; try{ mutable current = next(); while(true){ match(current){ | act is StackAction[T].Push => current = StackStack.Enter(act : StackAction[T].Push); | StackAction.Pop => throw StackEmptyException("Stack is empty"); } } }catch{ | e => {exception = e; _ = syncOut.Set();} } } next() : StackAction[T]{ _ = syncOut.Set(); _ = syncIn.WaitOne(); match(action){ | Push => StackAction.Push(value, next); | Pop => StackAction.Pop(fun(x){ value = x; next();}); } } } private resident : Resident = Resident(); private thread : Thread; public this(){ thread = Thread(ThreadStart(resident.start)); thread.Start(); } public Dispose() : void implements IDisposable.Dispose { try{ thread.Abort(); _ = resident.syncIn.Set(); thread.Join(); (resident.syncIn : IDisposable).Dispose(); (resident.syncOut : IDisposable).Dispose(); }finally{} } private checkException() : void{ when(resident.exception != null) { throw resident.exception; } } private exec() : void{ _ = resident.syncIn.Set(); _ = resident.syncOut.WaitOne(); checkException(); } public Push(val : T) : void{ resident.value = val; resident.action = Action.Push; exec(); } public Pop() : T{ resident.action = Action.Pop; exec(); resident.value; } } 

और यद्यपि बहुत अधिक कोड है, मुझे लगता है कि यह उन लोगों के लिए पहले से ही स्पष्ट होना चाहिए जो C # जानते हैं। केवल एक चीज: "_ =" निर्माण संकलक को बताता है कि हम वापसी मूल्य की उपेक्षा करते हैं।

और यहाँ एक ही रिवर्स पोलिश नोटेशन है:

 def items = "7 2 3 * -".Split(array[' ']); mutable currentPosition = 0; mutable stack : ThreadStack[double]; try{ stack = ThreadStack(); mutable onStack = 0; def execOperation(operation : double * double -> double){ def y = stack.Pop(); def x = stack.Pop(); stack.Push(operation(x, y)); onStack--; } currentPosition = 0; while(currentPosition < items.Length){ currentPosition++; mutable value : double; match(items[currentPosition-1]){ | strVal when (Double.TryParse(strVal, out value)) => { onStack++; stack.Push(value);} | "+" => execOperation(_ + _); | "-" => execOperation(_ - _); | "/" => execOperation(_ / _); | "*" => execOperation(_ * _); | token => throw Exception($"bad token $token"); } } when(onStack > 1){ throw Exception("Bad input, not enough operations."); } WriteLine("Result: " + stack.Pop()); }catch{ | e is StackEmptyException => throw Exception("Bad input, not enough arguments."); }finally{ stack.Dispose(); } 

और निश्चित रूप से, लेख को एक निष्कर्ष की आवश्यकता है: यहां तक ​​कि एक कार्यात्मक भाषा में ऐसी विकृतियां काफी कैपेसिटिव और समझने योग्य हैं (यदि आपके पास उनके साथ काम करने का कौशल है)। अनिवार्य शैली क्रिया है, लेकिन फिर भी अप्रस्तुत पाठक के लिए स्पष्ट है।