The implementation of the stack due to ... call stack

Once an idea came to me: there is a call stack and a stack as a data structure. Is it possible to use the call stack to store data?

After a bit of thinking, I realized that it was possible only with restrictions: firstly, for processing values, we have to use callbacks (after all, as long as the value is on the stack, you cannot leave the call in which we saved it). Secondly access is strictly LIFO.

Implementation - under the cut.



As a language, I decided to use Nemerle - a familiar .NET + convenience of a functional style.



The implementation itself is seemingly simple:

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()); } } 

For those unfamiliar with the Nemerle syntax:

variant StackAction [T] describes a variant generic type, the variables of which can take values ​​either Push or Pop. And if the value is Push, then there must be value fields (the actual value that we put on the stack), and the next is a callback, with an empty parameter list, which returns the next StackAction. And if Pop, then it should have a calbek that takes the value from the top of the stack as an argument, and also returns the next StackAction.

')

The Enter function implements the logic of working with the stack. Inside it, a local processNext function is declared, which receives current as a closure. The processNext body consists of a single match block (pattern matching). push and pop are synonyms next depending on which real type takes on the value.



As a result, the logic of the Enter operation: call current.next and transfer the return value to processNext, the return value from processNext. (In nemerle there is no return operator, and the function returns the value from the last expression, and match from the executed branch)

processNext checks the value passed to it. If Push, then it calls Enter with this value, and with the result of doing Enter, it calls itself. Thus a cycle is obtained - until the callback returns Pop, there will be no exit from the current call to Enter. If the next value is Pop, then the current value of current.value is passed to the callback from the closure (while the processNext itself could already be recursively called several times).



As a result, we get another drawback: if Pop takes the last value from the stack and the stack is empty, then Enter called in the client code will return what the last Pop returned. Thus, to work with the lower stack value, you need to do a separate cycle.



As an example of use, let's take the calculation of an expression in reverse Polish notation .

 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()); 

Brief explanation starting from the end:

calc implements the logic of working with the bottom element of the stack: if Push fell out with the processNextToken callback, then we call calc again, if Push fell out with another callback (fun () {throw Exception (“Bad input, not enough operations.”)), then the entire record is processed and the function returned the end result. If Pop fell out, then the last action did not have enough arguments.



processNextToken processes tokens in order. If the end of the record is reached, take the last value from the stack and return it to calc. If on the stack more than 1 value an anonymous function will be called fun () {throw Exception (“Bad input, not enough operations.”)}. If there are more tokens, we take the current one. We put the numeric literal on the stack, for arithmetic actions we call action. Records _ + _ - special nemerle magic - partial execution. In this case, it turns arithmetic operators into functions with two arguments.



action takes 2 values ​​from the stack, performs the function passed to it with them and puts the result on the stack.



Pretty confusing right? You can make a class with the usual interface of the stack, if you move the stack that stores the values ​​in another thread.

 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; } } 

And although the code is much more, I think it should already be clear to those who know C #. The only thing is that the "_ =" construct tells the compiler that we ignore the return value.



And here is the same reverse Polish notation:

 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(); } 

And of course the article needs a conclusion: even such distortions in a functional language are quite capacious and understandable (if you have the skill of working with them). The imperative style turns out to be more verbose, but still it’s clearer for the unprepared reader.