Stack implementation due to ... call stack
An idea came to me once: there is a call stack and a stack as a data structure. Is it possible to use the call stack to store data?
With a little thought, I realized that it is possible, but with limitations: firstly, you need to use callbacks to process the values (after all, while 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 - the familiar .NET + convenience of a functional style.
The implementation itself is outwardly simple:
For those unfamiliar with the syntax, Nemerle:
variant StackAction [T] describes a variant generic type whose variables can be either Push or Pop. Moreover, if the value is Push, then there must be value fields (the actual value that we put on the stack), and next is a callback with an empty list of parameters, which returns the next StackAction. And if Pop, then it should have a callback taking as an argument the value from the top of the stack, and also returning the next StackAction.
The Enter function implements the very logic of working with the stack. Inside it, a local processNext function is declared, which receives current as a closure. The body of the processNext consists of one match block (pattern matching). push and pop are synonyms of next, depending on which real type takes on value.
As a result, the logic of the Enter: operation is to call current.next and pass the return value to processNext, the return values from processNext to return. (There is no return statement in nemerle , 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 she calls Enter with this value, and herself with the result of Enter. Thus, a loop is obtained - until the callback returns Pop, there will be no exit from the current call to Enter. If the value of next is Pop, then the current value of current.value is passed from the closure to the callback (while 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, the Enter called in the client code will return what the last Pop returned. Thus, to work with the lower value of the stack, you need to do a separate cycle.
As an example of use, we take the calculation of an expression in reverse Polish notation .
A brief explanation 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 whole record is processed and the function returned the final result. If Pop fell out, then the last action did not have enough arguments.
processNextToken processes the tokens in order. If the end of the record is reached, take the last value from the stack and return it to calc. If there is more than 1 value on the stack, the anonymous function fun () {throw Exception ("Bad input, not enough operations.")} Will be called. If there are more tokens, take the current one. We put a numerical literal on the stack, for action we call action. Records _ + _ - special magic nemerle - partial execution. In this case, it turns arithmetic operators into functions with two arguments.
action takes 2 values from the stack, executes the function passed to it, and puts the result on the stack.
Pretty confusing right? You can make a class with the usual stack interface if you transfer a stack that stores values to another thread.
And although there is much more code, I think it should already be clear to those who know C #. The only thing: the "_ =" construct tells the compiler that we ignore the return value.
And here is the same reverse Polish notation:
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 to work with them). The imperative style is verbose, but nevertheless clearer for the unprepared reader.
With a little thought, I realized that it is possible, but with limitations: firstly, you need to use callbacks to process the values (after all, while 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 - the familiar .NET + convenience of a functional style.
The implementation itself is outwardly 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 syntax, Nemerle:
variant StackAction [T] describes a variant generic type whose variables can be either Push or Pop. Moreover, if the value is Push, then there must be value fields (the actual value that we put on the stack), and next is a callback with an empty list of parameters, which returns the next StackAction. And if Pop, then it should have a callback taking as an argument the value from the top of the stack, and also returning the next StackAction.
The Enter function implements the very logic of working with the stack. Inside it, a local processNext function is declared, which receives current as a closure. The body of the processNext consists of one match block (pattern matching). push and pop are synonyms of next, depending on which real type takes on value.
As a result, the logic of the Enter: operation is to call current.next and pass the return value to processNext, the return values from processNext to return. (There is no return statement in nemerle , 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 she calls Enter with this value, and herself with the result of Enter. Thus, a loop is obtained - until the callback returns Pop, there will be no exit from the current call to Enter. If the value of next is Pop, then the current value of current.value is passed from the closure to the callback (while 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, the Enter called in the client code will return what the last Pop returned. Thus, to work with the lower value of the stack, you need to do a separate cycle.
As an example of use, we 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());
A brief explanation 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 whole record is processed and the function returned the final result. If Pop fell out, then the last action did not have enough arguments.
processNextToken processes the tokens in order. If the end of the record is reached, take the last value from the stack and return it to calc. If there is more than 1 value on the stack, the anonymous function fun () {throw Exception ("Bad input, not enough operations.")} Will be called. If there are more tokens, take the current one. We put a numerical literal on the stack, for action we call action. Records _ + _ - special magic nemerle - partial execution. In this case, it turns arithmetic operators into functions with two arguments.
action takes 2 values from the stack, executes the function passed to it, and puts the result on the stack.
Pretty confusing right? You can make a class with the usual stack interface if you transfer a stack that stores values to 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 there is much more code, I think it should already be clear to those who know C #. The only thing: 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 to work with them). The imperative style is verbose, but nevertheless clearer for the unprepared reader.