Пришла мне однажды идея: есть стек вызовов и стек как структура данных. А нельзя ли использовать стек вызовов для хранения данных?
Немного поразмыслив я понял, что можно, только с ограничениями: во первых для обработки значений придётся использовать колбеки (ведь пока значение на стеке, нельзя выходить из того вызова, в котором мы его сохранили). Во вторых доступ строго LIFO.
Реализация — под катом.
В качестве языка я решил использовать Nemerle — знакомый мне .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());
}
}
Для незнакомых с синтаксисом Nemerle:
variant StackAction[T] описывает вариантный generic тип, переменные которого могут принимать значения либо Push, либо Pop. Причём если значение Push, то должны быть поля value (собственно значение, которое мы кладём на стек), и next — колбэк, с пустым списком параметров, возвращающий следующий StackAction. А если Pop, то у него должен быть колбек принимающий в качестве аргумента значение с вершины стека, и также возвращающий следующий StackAction.
Функция Enter реализует саму логику работы со стеком. Внутри неё объявлена локальная функция processNext, которая получает current в качестве замыкания. Тело processNext состоит из одного блока match (сопоставление с образцом). push и pop синонимы next в зависимости от того, какой реальный тип примет значение.
В итоге логика работы Enter: вызвать current.next и передать возвращаемое значение в processNext, возвращаемое из processNext значние вернуть. (В nemerle нет оператора return, и функция возвращает значение из последнего выражения, а match из выполенной ветки)
processNext проверяет переданное ей значение. Если Push, то она вызвает с этим значением Enter, а с результатом выполнения Enter — себя. Таким образом получается цикл — пока колбек не вернёт Pop, выхода из текущего вызова Enter не будет. Если значение next — Pop, то в колбек передаётся из замыкания текущее значение current.value (при этом сама processNext могла уже быть несколько раз рекурсивно вызвана).
В итоге получаем ещё один недостаток: если Pop возьмёт со стека последнее значение и стек опустеет, то вызванный в клиентском коде Enter вернёт то, что вернул последний Pop. Таким образом для работы с нижним значением стека нужно делать отдельный цикл.
В качестве примера использования возьмём вычисление выражения в обратной польской нотации.
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());
Краткое пояснение начиная с конца:
calc реализует логику работы с нижним элементом стэка: если вывалился Push с колбеком processNextToken то снова вызываем calc, если вывалился Push с другим колбеком (fun(){throw Exception(«Bad input, not enough operations.»)), значит вся запись обработана и функция вернула конечный результат. Если вывалился Pop, значит последнему действию не хватило аргументов.
processNextToken обрабатывает токены по порядку. Если достигнут конец записи, берём последнее значение со стека и возвращаем его в calc. Если на стеке больше 1 значение будет вызвана анонимная функция fun(){throw Exception(«Bad input, not enough operations.»)}. Если есть ещё токены, берём текущий. Числовой литерал кладём на стек, для арифметических действий вызываем action. Записи _ + _ — особая магия nemerle — частичное выполнение. В данном случае превращает арифметические операторы в функции с двумя аргументами.
action берёт 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();
}
Ну и конечно статье нужен вывод: даже такие извращения на функциональном языке получаются достаточно ёмкими и понятными (если иметь навык работы с ними). Императивный стиль оказывается многословнее, но всё же для неподготовленного читателя понятнее.
Автор: Vestild
